We propose a local algorithm that, with high probability, computes an $\varepsilon$‑approximate PageRank vector in the sense of Andersen, Chung, and Lang (ACL; Internet Math. 2007) with teleportation parameter $\alpha$, running in $\widetilde{O}\bigl(1 / (\sqrt{\alpha}\,\varepsilon)\bigr)$ time, substantially improving the original local‑push method’s $O\bigl(1/(\alpha\varepsilon)\bigr)$ bound.
The same technique applies to the $\ell_1$‑regularized PageRank problem, achieving a runtime of $\widetilde{O}\bigl(1 / (\sqrt{\alpha}\,\rho)\bigr)$ for regularization parameter $\rho$, thereby answering the open question posed by Fountoulakis and Yang (COLT 2022).
This faster primitive can accelerate a wide range of graph algorithms that rely on local push. For instance, plugging it directly into the ACL framework yields faster PageRank‑based local graph clustering, and we also devise reductions that speed up effective‑resistance estimation.
The main technical contribution is a potential‑function analysis of a refined active‑set method by Wei and Yang (2026). The algorithm repeatedly invokes an SDD solver on the current active set of nodes and expands the set. By relating potential decreases across consecutive expansion blocks, we show that the number of expansions is bounded by $\widetilde{O}\bigl(1/\sqrt{\alpha}\bigr)$.
Review: By leveraging a novel potential‑function argument, the work reduces the local‑push complexity from $1/(\alpha\varepsilon)$ to $1/(\sqrt{\alpha}\varepsilon)$, offering a more practical tool for large‑scale graph locality tasks and opening new avenues for optimizing regularized PageRank.