Nearly optimal Personalized PageRank computation

We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph $G$. We focus on the $\text{eps}$-error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 $\mathrm{\&}$ Internet Math 2007]. Their classic local push method computes an approximate PPR vector satisfying the ACL $\text{eps}$-error guarantee in $O((\alpha \text{eps}{)}^{-1})$ time, where $\alpha$ is the teleportation parameter. In this paper, we eliminate the dependence on $\alpha$ and present an algorithm that achieves the same error guarantee in $O({\text{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 $\phi$.