Faster local algorithm speeds up pagerank and graph analysis
Accelerating the Local Push Primitive for PageRank Computation
Data Structures and Algorithms
Summary
PageRank is a way to rank important points in a big network, like webpages on the internet. The authors found a way to calculate an approximate PageRank faster than before using a new method. Their approach improves the speed, especially for parts of the network, which can help with tasks like grouping related parts of the network quickly. This advance answers an open question from past research and could speed up many uses of PageRank in analyzing networks.
What this means in practice
- •For data engineers: Create faster local clusters in large network data by integrating the improved PageRank computation.
- •For network analysts: Estimate electrical network effective resistance more efficiently using the accelerated local push approach.
Authors
Guanyu Cui, Zhewei Wei, Mingji Yang
Abstract
We propose a local algorithm that computes an $\varepsilon$-approximate PageRank vector in the sense of Andersen, Chung, and Lang (ACL; Internet Math. 2007) with teleportation parameter $α$ in $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, \varepsilon\bigr)\bigr)$ time with high probability, improving the $O\bigl(1/(α\varepsilon)\bigr)$ running time of their original local push method. Our method also applies to the $\ell_1$-regularized PageRank problem with a running time of $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, ρ\bigr)\bigr)$ for regularization parameter $ρ$, giving a positive answer to the open problem posed by Fountoulakis and Yang (COLT 2022). Our faster primitive has the potential to improve a broad range of graph algorithms that rely on local push. For example, substituting our primitive into the ACL framework directly yields faster PageRank-based local graph clustering, and we also develop reductions that lead to faster algorithms for effective resistance estimation. Our main technical contribution is a potential-function analysis of a refinement of the active-set method of Wei and Yang (preprint 2026), which repeatedly invokes an SDD solver on the current active set of nodes and expands the set. We relate the potential decreases over consecutive blocks of expansions to show that the number of expansions is bounded by $\widetilde{O}\bigl(1 / \sqrtα\bigr)$.