{"ID":2858052,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08010","arxiv_id":"2510.08010","title":"Accelerated Evolving Set Processes for Local PageRank Computation","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/ε^2), \\tilde{\\mathcal{O}}(m)\\}$ to obtain an $ε$-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α)$ such linear systems, where $α$ is the damping factor. When $1/ε^2\\ll 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αε^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.","short_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...","url_abs":"https://arxiv.org/abs/2510.08010","url_pdf":"https://arxiv.org/pdf/2510.08010v4","authors":"[\"Binbin Huang\",\"Luo Luo\",\"Yanghua Xiao\",\"Deqing Yang\",\"Baojian Zhou\"]","published":"2025-10-09T09:47:40Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}