arXiv preprint ·
Accelerating the Local Push Primitive for PageRank Computation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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)$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
A deterministic $(1+\varepsilon)^n$ approximation for the permanent of a nonnegative matrix
Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.