# Accelerated Evolving Set Processes for Local PageRank Computation

arXiv: https://arxiv.org/abs/2510.08010 · HTML: https://mlsanity.com/paper/2510.08010/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 9 Oct 2025.

## Builds on (most cited first, 27 of 27)

- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Efficient Algorithms for Personalized PageRank Computation: A Survey](https://mlsanity.com/paper/2403.05198/) (2024)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions](https://mlsanity.com/paper/1606.09365/) (2016)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Iterative Methods via Locally Evolving Set Process](https://mlsanity.com/paper/2410.15020/) (2024)
- [Efficient Algorithms for Personalized PageRank](https://mlsanity.com/paper/1512.04633/) (2015)
- [Breaking Locality Accelerates Block Gauss-Seidel](https://mlsanity.com/paper/1701.03863/) (2017)
- [Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank](https://mlsanity.com/paper/1508.07607/) (2015)
- [Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond](https://mlsanity.com/paper/2303.12875/) (2023)
- [A note on the optimal convergence rate of descent methods with fixed step sizes for smooth strongly convex functions](https://mlsanity.com/paper/2106.08020/) (2021)
- [Efficient and Local Parallel Random Walks](https://mlsanity.com/paper/2112.00655/) (2021)
- [Revisiting Local Computation of PageRank: Simple and Optimal](https://mlsanity.com/paper/2403.12648/) (2024)
- [Dynamic PageRank: Algorithms and Lower Bounds](https://mlsanity.com/paper/2404.16267/) (2024)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)

## Abstract (arXiv)

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 mintildeO(R2/ε2), tildeO(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 tildeO(1/√α) such linear systems, where α is the damping factor. When 1/ε2ll m, this implies the existence of an algorithm that computes an  epsilon -approximation of the PPR vector with an overall time complexity of tildeOleft(R2 / (√αε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.