arXiv · Oct 3, 2026
Nearly optimal Personalized PageRank computation
By Rong-Hua Li, Yichun Yang, Junjie Zhou
We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph G. We focus on the eps-error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 & Internet Math 2007]. Their classic local push method computes an approximate PPR vector satisfying the ACL eps-error guarantee in O((αeps)⁻¹) time, where α is the teleportation parameter. In this paper, we eliminate the dependence on α and present an algorithm that achieves the same error guarantee in O(eps^(-1-o(1))) time. Consequently, we obtain a nearly optimal algorithm for PPR computation under the ACL error guarantee, and a nearly linear algorithm for local graph clustering with complexity independent of ϕ.