Hanzhi Wang   /   王涵之

I will begin my PostDoc at BARC (Basic Algorithms Research Copenhagen), University of Copenhagen in November 2024, working with Prof. Mikkel Thorup. I obtained my Ph.D. in Computer Science and Technology from the School of Information at Renmin University of China in May 2024, under the supervision of Prof. Zhewei Wei. I received my B.E. degree in Computer Science and Technology from the School of Information at Renmin University of China in June 2019.

I am currently a research assistant at the Microsoft Research Asia, hosted by Dr. Wei Chen. I was a visiting scholar from June 2023 to August 2023 in School of Computing and Information Systems at The University of Melbourne (UoM), advised by Dr. Junhao Gan. I was an exchange student from December 2022 to May 2023 in School of Computing at National University of Singapore (NUS), advised by Prof. Xiaokui Xiao.

hzwang.helen@gmail.com  /  Github  /  Google Scholar

My research interests are graph algorithms, with a particular focus on the design of scalable algorithms for large graphs. My previous work primarily centers on sublinear-time algorithms for random-walk probability estimation. I am also interested in local clustering and graph neural networks.

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

We study the fundamental subset sampling problem in a general dynamic setting and achieve optimal complexity results for both query and update time simultaneously.

We establish matching upper and lower bounds for the worst-case computational complexity of single-node PageRank computation on undirected graphs, using surprisingly simple algorithms and analysis.

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.

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.

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((nd_t)^1/2) to O(min(d_t, m^1/2)) (omitting logarithmic factors). Here n and m denote the number of nodes and edges in the given graph, respectively. d_t denotes the degree of the given target node t.

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.

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.

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

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

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.

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.

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.

PC member/Reviewer:

Last update: Sept. 2024      Template