Recently, one paper titled “Revisiting Local Computation of PageRank: Simple and Optimal” has been accepted by the Annual ACM Symposium on Theory of Computing (STOC), the top international conference in theoretical computer science. The authors of this paper are Prof. Zhewei Wei, Prof. Ji-Rong Wen, along with doctoral students Hanzhi Wang and Mingji Yang, all from Renmin University of China. The upcoming STOC conference is scheduled to be held from June 24 to June 28, 2024, in Vancouver, Canada.

Established in 1969, the STOC conference is esteemed across the computer science field for its rigorous standards and academic excellence. This paper represents the first independent STOC submission by faculty and students from Renmin University of China, marking a significant milestone for our institution. Additionally, it is the second STOC paper affiliated with our school, following a publication in June 2023 by Dr. Zihe Wang and Zeyu Ren.

Paper Introduction

Paper Title: Revisiting Local Computation of PageRank: Simple and Optimal

Authors: Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang

(Equal contribution, the authors areordered alphabetically by the first letter of their last names, following the convention of theoretical computer science)

Corresponding Author: Zhewei Wei

Paper Overview: PageRank is an important graph analysis metric, initially proposed by the founders of Google to compute the importance ranking of web pages on the Google search engine.PageRank later becomes a classic measure of node centrality in graphs and is widely used in social networks, information retrieval, recommendation systems, and even in fields such as biology, chemistry, and neuroscience.

In 2007, Reid Andersen, Christian Borgs, Jennifer Chayes, John E. Hopcroft, Vahab S. Mirrokni, and Shang-Hua Teng began to study the problem of computing PageRank contributions on large graphs, i.e., given a target node t in a graph, finding all nodes in the graph that significantly affect the PageRank score of t; they jointly proposed the ApproxContributions algorithm, which uses local search on large graphs to compute the PageRank contributions. Since its proposal, the ApproxContributions algorithm (later also known as LocalPush, Backward Search, Backward Push, etc.) has received widespread attention and has become a cornerstone algorithm for PageRank computation, with its various modifications being widely applied to solving a variety of graph analysis problems such as node proximity and similarity computation, random-walk probability computation, and community discovery.

However, since its proposal, the ApproxContributions algorithm has lacked meaningful analytical results in terms of worst-case computational complexity. The open question of 'Whether the worst-case time complexity of the ApproxContributions algorithm can be made independent of the degrees of nodes in the graph?' left by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng at the WAW conference in 2007 has remained unsolved despite years of research.

This paper provides an upper bound on the worst-case time complexity of the ApproxContributions algorithm under the arc-centric graph-access model, along with a matching theoretical lower bound, thereby answering the aforementioned open question posed in 2007. Notably, the analysis presented in this paper is very concise, and the results have reached optimality.

Furthermore, this paper applies the results to the problem of single-node PageRank computation on directed graphs under the arc-centric graph-access model, providing both an upper bound on the worst-case time complexity and a matching theoretical lower bound. Consequently, it resolves the previously unanswered question raised by Marco Bressan, Enoch Peserico, and Luca Pretto in FOCS 2018 and SICOMP 2023: 'Is it possible to bridge the theoretical gap between the upper and lower bounds onthe time complexity of computing single-node PageRank?' This paper’s analysis process for this problem is also very concise, and theresults have reached optimality.