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 t in an undirected graph G comprising n nodes and m edges, BackMC accurately estimates the PageRank score of node t while assuring a small relative error and a high success probability. The worst-case computational complexity of BackMC is upper bounded by O(1dₘᵢₙ· min(dₜ, m1/2)), where dₘᵢₙ denotes the minimum degree of G, and dₜ denotes the degree of t, respectively. Compared to the previously best upper bound of O(logn· min(dₜ, m1/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 Θ(logndₘᵢₙ) with a much simpler algorithm. Furthermore, we establish a matching lower bound of Ω(1dₘᵢₙ· min(dₜ, m1/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.