CS Paper Radar

Nearly optimal Personalized PageRank computation

Rong-Hua Li, Quanqing Xu, Yichun Yang, Junjie Zhou

cs.DS cs.CC ·submitted 2026-10-03 16:15 UTC · v2
theory

Abstract

We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph $G$. We focus on the $\eps$-error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 $\&$ Internet Math 2007]. Their classic local push method computes an approximate PPR vector satisfying the ACL $\eps$-error guarantee in $O((α\eps)^{-1})$ time, where $α$ is the teleportation parameter. This problem has a lower bound $Ω(\eps^{-1})$. Working with idealized SDDM solves, we eliminate the dependence on $α$ and present an algorithm that achieves the same error guarantee in $O(\eps^{-1-o(1)})$ time. Consequently, we obtain a nearly optimal algorithm for PPR computation under the ACL error guarantee, and a nearly linear algorithm for local graph clustering with complexity independent of $φ$.

Closest papers

Nearest neighbours by meaning across the whole index.

Accelerating the Local Push Primitive for PageRank Computation

cs.DS ·2026-09-10 ·Guanyu Cui, Zhewei Wei, Mingji Yang
similarity 0.82
Abstract · 32 pages

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)$.

0.39

A Simple Active-Set Method for PageRank-Based Local Graph Clustering

cs.DS ·2026-08-17 ·Zhewei Wei, Mingji Yang
similarity 0.79
Abstract · 17 pages

Local graph clustering aims to find a well-connected cluster near a given seed node without exploring the entire graph. A key step in the classic local clustering algorithm of Andersen, Chung, and Lang (ACL; Internet Math. 2007) is to approximate the PageRank vector from the seed node. Their local push method computes an ACL $\varepsilon$-approximate PageRank vector with teleportation parameter $α$ in $O\bigl(1/(α\varepsilon)\bigr)$ time. We give an algorithm that computes an ACL $\varepsilon$-approximate PageRank vector in $\widetilde{O}\bigl(1 / \varepsilon^2\bigr)$ time with high probability. This bound is independent of the graph size and has only a polylogarithmic dependence on $1 / α$, albeit with a quadratic dependence on $1 / \varepsilon$. As a direct consequence, we obtain a new running-time tradeoff between the target conductance and target volume in local graph clustering. Our method also applies to the optimization problem of $\ell_1$-regularized PageRank and computes an additive approximate minimizer with a polylogarithmic dependence on $1/α$, improving the $1/\sqrtα$ dependence in the previous bound of Martínez-Rubio, Wirth, and Pokutta (COLT 2023). Our algorithm is based on an intuitive process that maintains a growing active set of nodes: it performs push operations on the current set until convergence and then expands the set and repeats the process if necessary. We show that for each active set, the corresponding limiting state is the solution to a symmetric diagonally dominant (SDD) linear system on the set. We apply nearly-linear-time SDD solvers to these systems and prove that the approximation preserves the properties of the push process.

0.47

Instance-Optimality of Single-Pair Personalized PageRank

cs.DS ·2026-11-09 ·Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan
similarity 0.74
Abstract

We consider discounted random walks in a directed simple graph $G=(V,E)$. Such a walk terminates at each step with a constant probability $α\in (0,1)$ and otherwise continues to a uniform random out-neighbor. Given a pair $(s,t)\in V^2$, we denote by $π(s,t)$ the probability of such a discounted random walk starting at $s$ terminates at $t$. This probability is referred to as the Personalized PageRank (PPR) of $t$ with respect to $s$. The problem of estimating $π(s,t)$ within a constant multiplicative factor with constant success probability for a given vertex pair $(s,t)$ is called the single-pair PPR estimation problem. We investigate the instance-optimality of single-pair PPR estimation in directed graphs. We present a new algorithm that aims at instance-optimal running time up to polylogarithmic factors. In other words, no correct algorithm can run faster than our algorithm on any valid graph by more than a polylogarithmic factor. We show that our algorithm is instance-optimal in the standard adjacency-list query model if $n$ is not known (as is often the case for most of the large networks to which PPR is applied). When $n$ is known, our algorithm is still instance-optimal for sparse graphs. For denser graphs, when $n$ is known, we show that no algorithm can achieve general instance-optimality. For the multiplicative approximation of PPR, we also improve the worst-case complexity from $O(mn\log n)$ to the near-optimal $O(m\log n)$. This is not only for the single-pair discussed above, but also for the single-source and single-target variants of the PPR estimation problem.

0.32

Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions

cs.SI ·2026-11-04 ·Parth Gupta, Abhinav Jain, Avishek Mukhopadhyay, Amitabha Bagchi, Sayan Ranu +1 more
similarity 0.65
Abstract · 16 pages, 12 figures

PageRank is widely used to quantify the importance of nodes in directed networks. In applications such as recommendation systems, it is increasingly important that the PageRank distribution provides a fair representation of node exposure. This motivates the problem of making minimal changes to a graph so that the PageRank values of a given set of target nodes $T$ match a desired vector $\boldsymbol{t}$. In this paper, we study this problem under an edge-addition budget $B$, where exactly $B$ edges may be added to the graph. We show that deciding whether a multiset of exactly $B$ added edges can make the target nodes attain their desired absolute PageRank scores is NP-complete. After this, we define the $\ell_1$ Target PageRank problem in which we seek to minimize the $\ell_1$ distance between the target vector and resultant vector. We show that this optimization problem admits no polynomial-time multiplicative constant-factor approximation unless $P=NP$. Motivated by these hardness results, we propose two greedy heuristics for approaching the target PageRank vector. We additionally propose a Random Walk Hungarian (RWH) heuristic that addresses the addition of edges between dissimilar nodes by incorporating a penalty for such edges. Finally, we evaluate the proposed heuristics on several real-world and synthetic datasets and compare their performance in terms of PageRank accuracy, computational efficiency, and the relevance of the added edges.

0.17

Fast Sparse $α$-Navigable Graph Construction with Improved Resource Augmentation

cs.DS ·2026-10-28 ·Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Ben Landrum, Christopher Musco +3 more
top venue similarity 0.62
Abstract · 26 pages. To appear in SODA 2027

Graph-based nearest neighbor search methods, which run greedy search on a directed graph over the data points, have surged in popularity in recent years. A common goal is to construct a search graph with the $α$-navigability property, which ensures that greedy search returns provably good approximate nearest neighbors and converges in few iterations. Increasing $α\geq 1$ improves accuracy and convergence rate, but requires more edges, which increases both space and search time. This tradeoff has motivated the study of algorithms for constructing a sparsest $α$-navigable graph for a given set of points. For any point set and any distance function, we show how to compute an $α$-navigable graph with at most $O(\log n)$ times as many edges as the sparsest $(1+\varepsilon)α$-navigable graph, in $O(n^ω\log(Δ)/\varepsilon)$ time, where $ω< 2.372$ is the matrix multiplication exponent and $Δ$ is the aspect ratio of the input. This improves on Khanna, Padaki, and Waingarten (SODA 2026), who achieve the same runtime but are only competitive with the sparsest $2(1+\varepsilon)α$-navigable graph. Since sparsity often increases rapidly with $α$ (typically $α\leq 1.1$), their bound can be significantly weaker. Previously, the best algorithm competing with the sparsest $(1+\varepsilon)α$-navigable graph required $\widetilde{O}(n^{2.5})$ time. Our techniques also extend to constructing sparse $τ$-monotonic graphs, another popular target in nearest neighbor search. Finally, we give a fine-grained complexity analysis suggesting that improving the $O(n^ω)$ running time is unlikely, or would require a very different approach. It is based on hardness results for problems related to verifying whether a graph is navigable, a topic of independent interest.

0.37

Accelerated Local Algorithms for Personalized and Regularized PageRank

cs.DS ·2026-09-14 ·Baojian Zhou
similarity 0.62
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.

0.30

Variants of Beam Search for DiskANN

cs.DS cs.DBcs.IR ·2026-11-19 ·Viraj Agrawal, Kirankumar Shiragur
similarity 0.62
Abstract · 22 pages, 1 figure, 9 tables

Graph-based data structures such as DiskANN, HNSW, and NSG constitute the state of the art for large-scale approximate nearest-neighbor (ANN) search. Indyk and Xu introduced the notion of $α$-reachable graphs, which include graphs built by DiskANN's slow-preprocessing construction, and proved that greedy search achieves an approximation factor of $\tfrac{α+1}{α-1}$. Independently, Al-Jazzazi et al. proposed adaptive beam search (ABS) with a relaxation parameter $γ> 0$, showing a $\tfrac{2}γ$ approximation on navigable graphs ($α\approx 1$), where greedy search admits no guarantees. In this work, we unify and generalize these results by proving that ABS with parameter $γ$ on $α$-reachable graphs achieves an approximation of $\tfrac{α+1}{α(γ+1)-1}$ for any metric. Moreover, on sorted $α$-reachable graphs (introduced by Gollapudi et al.) under the $\ell_2$ metric, we obtain the tighter bound $\max\bigl(\tfracα{α(γ+1)-1}, \tfrac{α^{2}+1}{α^{2}(γ+1)-1}\bigr)$. Beyond these theoretical results, we design a beam predictor using features inspired by fine-grained analysis of ABS, trained via a constrained objective that minimizes mean distance computations subject to a target recall. On three 100-million-point benchmarks, using graphs built by DiskANN's practical construction, beam predictor lowers mean query latency on SSD-resident indices at matched recall by up to $29.6\%$ relative to classical beam search (CBS). Relative to ABS, it is faster in $11$ of $15$ settings, by up to $6.5\%$, and at most $1.4\%$ slower in the other $4$; at $95\%$ recall, its advantage over ABS grows from $0.8$--$4.2\%$ for $100$ neighbors to $4.6$--$5.6\%$ for $500$ neighbors. In memory, it needs $1.3$--$23.7\%$ fewer distance computations than CBS and $0.0$--$3.9\%$ fewer than ABS.

0.15

On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search

cs.DS cs.LG ·2026-10-28 ·Majid Daliri, Mohammadreza Daneshvaramoli, Purna Dutta, Edo Liberty, Cameron Musco +2 more
theory similarity 0.61
Abstract

Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}(n^{1/(c-1)})$. We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods.

0.21