Deterministic methods speed up personalized pagerank in large graphs
Accelerated Local Algorithms for Personalized and Regularized PageRank
Data Structures and Algorithms
Summary
Finding important nodes in massive networks like social media or websites requires quick methods that don't need to look at the whole network. The authors present a way to compute personalized PageRank efficiently and reliably, focusing only on a small part of the graph. Their approach guarantees accuracy while working faster by cleverly limiting the search and updates. Unlike other methods that rely on randomization or expensive tools, theirs is deterministic and needs less overhead.
What this means in practice
- •For search engine engineers: Improve web page ranking speed by computing high-accuracy personalized PageRank on local graph neighborhoods without preprocessing the whole web graph.
- •For social network data teams: Quickly identify user-relevant content clusters in large social graphs using deterministic local PageRank approximations for faster community detection.
Authors
Baojian Zhou
Abstract
Local PageRank algorithms seek sparse approximations with work independent of graph size. We give a deterministic algorithm for regularized personalized PageRank with additive objective accuracy $ε$ in $\widetilde{\mathcal{O}}(1/(ρ\sqrtα))$ local work, where $α$ is the lazy teleportation parameter and $ρ$ is the regularizer. Accuracy enters only polylogarithmically. The bound charges discovery, repeated neighborhood scans, numerical updates, certification, and output, without graph-wide preprocessing or a supplied solution support. The algorithm combines regularization continuation with accelerated corrections constrained by a degree-scaled box and a mass cap. Two energies for the same recurrence control objective convergence and the response that activates coordinates. A selected-flow argument bounds cumulative scanned volume, and a sparse threshold reporter realizes the bound. We also specify a bounded-arithmetic implementation for rational inputs. A second, randomized algorithm uses support-safe threshold batches. A block-Cholesky and Chebyshev argument bounds their depth, and certified SDD solves give expected work $\widetilde{\mathcal{O}}(V_*\min\{k_*,α^{-1/2}\})$, where $k_*$ and $V_*$ are the optimal support's cardinality and degree volume. Both methods imply the corresponding accelerated degree-normalized PPR approximation. The concurrent September 2026 preprint of Cui, Wei, and Yang also attains the randomized work scale. Our principal distinction is deterministic local acceleration with only polylogarithmic overhead and no SDD oracle.