Hanzhi Wang   /   王涵之

I am currently a final year PhD candidate at School of Information, Renmin University of China, where I am very fortunate to be advised by Prof. Zhewei Wei.

Before that, I received my B.E. degree in Computer Science and Technology at School of Information, Renmin University of China in June 2019.

Email  /  Github  /  Google Scholar

profile photo
Research Interests

My research focuses on the development of provably-good scalable algorithms for graph data. In particular, I am interested in designing nearly linear or sub-linear time algorithms for large-scale graph analysis and learning problems. Specifically, my research can be categorized into three aspects:

  • improving the computational complexities of various node proximity metrics, especially for PageRank, Personalized PageRank and Heat Kernel PageRank;
  • designing algorithms for efficiently estimating the popular node similarity metric, SimRank, on large graphs;
  • designing scalable Graph Neural Network (GNN) models on large graphs.

  • News

    [03/2024] One paper was accepted to TKDE 2024. The paper's reviewing process spanned over one year, but very happily, it concluded with an encouraging outcome. Special thanks to Mingji!

    [02/2024] One paper was accepted to STOC 2024.

    [08/2023] I am attending VLDB 2023 in person to present our paper in Session G4 this Wednesday (Aug. 30th, 1:30 PM - 3:00 PM). Warmly welcome to stop by and chat with me!

    [08/2023] I was awarded a certificate of excellence in reviewing at KDD 2023.

    [05/2023] I will take an academic visit to The University of Melbourne (UoM) from June 2023, advised by Dr. Junhao Gan.

    [05/2023] One paper, with a focus on the single-node PageRank computation, was accepted to VLDB 2023.

    [05/2023] One paper was accepted to KDD 2023 with the rating of 'Accept' across the board (4/4/4/4). We appreciate the recognition from all the anonymous reviewers!

    [12/2022] I will spend a couple of months at National University of Singapore (NUS) as an exchange student under the supervision of Prof. Xiaokui Xiao.


    Note: Papers marked with use alphabetic ordering of authors, following the convention of theoretical computer science.

    Revisiting Local Computation of PageRank: Simple and Optimal.
    Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang
    STOC, 2024
    Technical Report

    We establish matching upper and lower bounds for the worst-case computational complexity of single-node PageRank computation on directed graphs. Additionally, for the celebrated ApproxContributions algorithm (also known as Backward Push or Local Push, proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng in WAW 2007), we upper bound its worst-case computational complexity on directed graphs and prove its optimality by establishing a matching lower bound.

    Efficient Algorithms for Personalized PageRank Computation: A Survey.
    Mingji Yang, Hanzhi Wang, Zhewei Wei, Sibo Wang, Ji-Rong Wen
    TKDE, 2024
    Technical Report

    We recap several frequently used techniques for Personalized PageRank (PPR) computation and conduct a comprehensive survey of various recent PPR algorithms from an algorithmic perspective.

    Estimating Single-Node PageRank in O(min(dt, m1/2)) Time.
    Hanzhi Wang, Zhewei Wei
    VLDB, 2023
    Technical Report / code / slide / poster

    For the problem of estimating a single node's PageRank score in an undirected graph, we tighten the upper bound for query time complexity from O((ndt)1/2) to O(min(dt, m1/2)) (omitting logarithmic factors). Here n and m denote the number of nodes and edges in the given graph, respectively. dt denotes the degree of the given target node t.

    Optimal Dynamic Subset Sampling: Theory and Applications.
    Lu Yi, Hanzhi Wang, Zhewei Wei
    KDD, 2023
    Technical Report / slide / poster

    We study the fundamental problem of sampling indepedent events (called subset sampling) in a dynamic setting. We present the ODSS algorithm, which is the first to achieve the optimal time complexity per sample and per update simultaneously.

    Edge-based Local Push for Personalized PageRank.
    Hanzhi Wang, Zhewei Wei, Junhao Gan, Ye Yuan, Xiaoyong Du, Ji-Rong Wen
    VLDB, 2022
    Technical Report / code / slide

    The state-of-the-art algorithm, LocalPush, for Personalized PageRank computation can be rather inefficient on weighted graphs. In this paper, we propose an Edge-based Push Method (EdgePush), which decomposes the push operation of LocalPush into separate edge-based push operations and achieves superior query efficiency over LocalPush on weighted graphs.

    Instant Graph Neural Networks for Dynamic Graphs.
    Yanping Zheng, Hanzhi Wang, Zhewei Wei, Jiajun Liu, Sibo Wang
    KDD, 2022
    Technical Report / code

    We propose Instant Graph Neural Network (InstantGNN), an incremental computation approach to support instant updates of graph representation results on dynamic graphs.

    Approximate Graph Propagation
    Hanzhi Wang, Mingguo He, Zhewei Wei, Sibo Wang, Ye Yuan, Xiaoyong Du, Ji-Rong Wen
    KDD, 2021
    Technical Report / code / slide / poster

    We propose Approximate Graph Propagation (AGP), a unified randomized algorithm that computes various proximity queries and GNN feature propagation in almost optimal time complexity.

    ExactSim: benchmarking single-source SimRank algorithms with high-precision ground truths
    Hanzhi Wang, Zhewei Wei, Yu Liu, Ye Yuan, Xiaoyong Du, Ji-Rong Wen
    VLDB Journal, 2021

    This work is an extended version of the conference paper "Exact Single-Source SimRank Computation on Large Graphs" accepted by SIGMOD 2020. With the ground truths computed by ExactSim, we conduct the first experimental study of the accuracy/cost trade-offs of existing approximate SimRank algorithms on large graphs.

    Personalized PageRank to a Target Node, Revisited
    Hanzhi Wang, Zhewei Wei, Junhao Gan, Sibo Wang, Zengfeng Huang
    KDD, 2020
    Technical Report / code / slide

    We propose Randomized Backward Search (RBS), a novel algorithm that answers approximate single-target personalized PageRank queries (also known as PageRank contribution queries) with near optimal time complexity.

    Exact Single-Source SimRank Computation on Large Graphs
    Hanzhi Wang, Zhewei Wei, Ye Yuan, Xiaoyong Du, Ji-Rong Wen
    SIGMOD, 2020
    Technical Report / code / slide

    We propose ExactSim, the first algorithm that enables probabilistic exact single-source SimRank queries on large graphs. ExactSim can provide the ground truth with a precision up to 7 decimal places for single-source SimRank queries on large graphs within a reasonable query time.


    A Friend Recommendation Method based on Personalized PageRank
    Zhewei Wei, Hanzhi Wang, Junhao Gan, Sibo Wang, Zengfeng Huang
    Chinese National Patent, ZL202010850777.2

    A Friend Recommendation Method based on the Exact Results of Single-Source SimRank
    Zhewei Wei, Hanzhi Wang, Ye Yuan, Ji-Rong Wen, Xiaoyong Du
    Chinese National Patent, ZL202010536506.X

    A Collaborative Filtering Recommendation Method based on Single-Source SimRank Results
    Zhewei Wei, Xiaodong He, Hanzhi Wang, Xiaokui Xiao, Sibo Wang, Yu Liu, Xiaoyong Du
    Chinese National Patent, ZL201910577524.X
    Honors and Awards
    • Certified Excellence in Reviewing for KDD 2023.
      • Microsoft Research Asia Fellowship, 2022 (awarded to twelve PhD students in the Asia-Pacific region).
      • Baidu Scholarship, 2021 (awarded to ten Chinese students worldwide).
        • National Scholarship, 2021.
          • The Outstanding Innovative Talents Cultivation Funded Programs of Renmin University of China, 2020.
            • China National Petroleum Corporation (CNPC) Scholarship, 2020.
            • Academic Services

                PC member/Reviewer:

              • Annual Conference on Neural Information Processing Systems (NeurIPS), 2023
              • International Conference on Knowledge Discovery and Data Mining (KDD), 2023/2024
              • International Conference on Learning Representations (ICLR), 2024
              • ACM International Conference on Web Search and Data Mining (WSDM), 2023/2024
              • SIAM International Conference on Data Mining (SDM), 2024
              • Australasian Database Conference (ADC), 2023
              • IEEE Communications Magazine
              • Information Retrieval Journal
              • International Conference on Machine Learning (ICML), 2022
              • Invited Talks
                  Approximate Graph Propagation. [slide]
                  Online, Oct. 2021
                    Efficient Computation of Random Walk and the Applications in Graph Representation Learning. [slide]
                    Online, Aug. 2021
                      A Near Optimal Algorithm for Single-Target Personalized PageRank. [slide]
                      The 9th National Social Media Processing Conference (SMP, 2020)
                      Online, Sept. 2020

                      Last update: Mar. 2024      Template