arXiv:2510.08010v3 Announce Type: replace
Abstract: This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $min{tilde{mathcal{O}}(R^2/epsilon^2), tilde{mathcal{O}}(m)}$ to obtain an $epsilon$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $tilde{mathcal{O}}(1/sqrt{alpha})$ such linear systems, where $alpha$ is the damping factor. When $1/epsilon^2ll m$, this implies the existence of an algorithm that computes an $ epsilon $-approximation of the PPR vector with an overall time complexity of $tilde{mathcal{O}}left(R^2 / (sqrt{alpha}epsilon^2)right)$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.