# Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2023.

## Built on by (most cited first, 3 of 3)

- [Local Graph Clustering with Noisy Labels](https://mlsanity.com/paper/2310.08031/) (2023)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)
- [Complexity of Classical Acceleration for ℓ1-Regularized PageRank](https://mlsanity.com/paper/2602.21138/) (2026)

## Abstract (arXiv)

It has recently been shown that ISTA, an unaccelerated optimization method, presents sparse updates for the ℓ1-regularized personalized PageRank problem, leading to cheap iteration complexity and providing the same guarantees as the approximate personalized PageRank algorithm (APPR) [FRS+19]. In this work, we design an accelerated optimization algorithm for this problem that also performs sparse updates, providing an affirmative answer to the COLT 2022 open question of [FY22]. Acceleration provides a reduced dependence on the condition number, while the dependence on the sparsity in our updates differs from the ISTA approach. Further, we design another algorithm by using conjugate directions to achieve an exact solution while exploiting sparsity. Both algorithms lead to faster convergence for certain parameter regimes. Our findings apply beyond PageRank and work for any quadratic objective whose Hessian is a positive-definite M-matrix.