Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal

We propose a simple and optimal algorithm, BackMC, for local PageRank estimation in undirected graphs: given an arbitrary target node in an undirected graph comprising nodes and edges, BackMC accurately estimates the PageRank score of node while assuring a small relative error and a high success probability. The worstcase computational complexity of BackMC is upper bounded by 1 min • min , 1/2 , where min denotes the minimum degree of , and denotes the degree of , respectively. Compared to the previously best upper bound of log • min , 1/2 (VLDB '23), which is derived from a significantly more complex algorithm and analysis, our BackMC improves the computational complexity for this problem by a factor of Θ log min with a much simpler algorithm. Furthermore, we establish a matching lower bound of Ω 1 min • min , 1/2 for any algorithm that attempts to solve the problem of local PageRank estimation, demonstrating the theoretical optimality of our BackMC. We conduct extensive experiments on various large-scale real-world and synthetic graphs, where BackMC consistently shows superior performance. CCS Concepts • Mathematics of computing → Graph algorithms; • Information systems → Data mining.