CS Paper Radar

Accelerated Local Algorithms for Personalized and Regularized PageRank

Baojian Zhou

cs.DS ·submitted 2026-09-14 02:08 UTC · v1

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.

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.69
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

Nearly optimal Personalized PageRank computation

cs.DS cs.CC ·2026-10-03 ·Rong-Hua Li, Quanqing Xu, Yichun Yang, Junjie Zhou
theory similarity 0.62
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 $φ$.

0.10

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

cs.DS ·2026-08-17 ·Zhewei Wei, Mingji Yang
similarity 0.60
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

Accelerating Direct Sparse Solvers with Graph Computing Accelerators

cs.DC ·2026-11-09 ·Jiya Su, François-Henry Rouet, Jeff Beisheim, Robert Lucas, Yuqing Wang +4 more
similarity 0.57
Abstract

Solving large sparse linear systems by Gaussian elimination is a challenging computational task due to the introduction of non-zero elements, or fill-in. Practitioners use heuristics such as the nested dissection reordering algorithm to try to reduce fill-in. In practice, reordering codes do not achieve the same parallel scaling as factorization, nor can they exploit AVX instructions or GPUs. Thus, reordering can be the primary runtime bottleneck in large-scale computer-aided engineering applications. We consider the use of a novel accelerator, the UpDown system, to accelerate the METIS multilevel nested dissection reordering algorithm. The UpDown system is designed for a broad class of graph computing and irregular algorithms. We report results for small-scale UpDown systems that will be available commercially in 2027, using validated simulation and FPGA emulation platforms. Our findings indicate that small UpDown systems can speed up METIS by two-orders of magnitude versus a single CPU. Compared to ParMETIS on hundreds of MPI ranks, we anticipate the same small UpDown systems offer speedups of 4 - 7, providing the potential to significantly speed finite element simulations

0.18

Sensitivity Inflation from Cross-Record Precision Routing in Private Quantized Fine-Tuning

cs.LG ·2026-11-01 ·Annan Zhang, Shengjie Song, Wenshuai Yao, Lihao Zhang, Tianmiao
similarity 0.57
Abstract · 13 pages, 5 figures

Private fine-tuning of large language models increasingly pairs DP-SGD with low-rank adapters on frozen, quantized backbones, and every such stack inherits one unstated premise: frozen layers keep each record's clipped gradient a function of that record alone. We show that LLM.int8 breaks this premise. It routes outlier activation columns to a higher-precision path using a union over the whole batch, so one record decides how every other record's activations are computed, even though the weights are frozen and the quantization scales are per row. We bound the resulting sensitivity inflation, state a record-isolation contract that restores the standard bound, and define record-owned precision dispatch that meets it with the same GEMMs as batched LLM.int8, so isolation needs no extra arithmetic. We then audit the native CUDA stack (bitsandbytes, PEFT, Opacus) against four matched controls. A constructed LoRA-Opacus witness reaches $15.0\times$ the add/remove bound. On pretrained OPT-125M with natural text, other records alter 20% of record-layer precision splits at batch size 16. An exploratory re-clipping analysis finds 10 of 64 candidate neighbors above the bound once every gradient is clipped; the top pair, revalidated natively, reaches $1.065C$ while every control stays within $C$, and forcing one layer's outlier mask removes the excess. A two-million-draw audit of the released adapters yields $\varepsilon$ lower bounds ($3.25$ at $δ=10^{-5}$) below the advertised guarantee ($4.38$). Resolving an excess this small at the release level would take about 200 times more draws, whereas checking the sensitivity contract directly exposes it in a few native runs, which makes contract checking the practical audit for private quantized training.

0.28

Finite-Precision Gram-Schmidt Walks

cs.DS ·2026-10-06 ·Emile Anand, Jan van den Brand, Peter Chen
similarity 0.57
Abstract

The Gram-Schmidt Walk is a randomized vector-balancing algorithm whose subgaussian guarantees support applications in discrepancy, experimental design, and data compression; however, these theoretical guarantees are established in exact arithmetic, whereas implementations must approximate least-squares directions, boundary updates, and sampling probabilities in finite precision. This is important because small numerical errors can change which coordinates freeze and thereby alter the subsequent trajectory. We analyze the concentration of the perturbed Gram-Schmidt walk directly under bounded, potentially biased and history-dependent errors. For $n$ input vectors of Euclidean norm at most one, we obtain a modified MGF bound depending on key error sources which recovers the original result as the error goes to zero. We also construct a full-column-rank instance in which bounded update errors produce bias of order $\min\{n^2\varepsilon,n\}$, showing that updates accumulate error unavoidably under this model. Finally, we validate our findings in a variety of settings by ablating on the bit precision and problem size.

0.37

Certified Sparse Attention via Perturbed Retrieval

cs.LG cs.CL ·2026-10-18 ·Runguo Li
similarity 0.57
Abstract · 58 pages (10 pages main text, 48 pages appendix), 10 figures, 35 tables

Sparse attention speeds up long-context decoding by reading few keys of the KV cache, but existing methods do not control the error of a query, and on real KV caches their errors have heavy tails. We show that perturbing the score of every key with an independent Exp(1) variable turns threshold retrieval into sampling keys with probability proportional to their attention weights. Lowering the threshold along a geometric grid gives nested samples, a Horvitz--Thompson estimate of the output at every level, and confidence bounds that hold simultaneously over all levels, so each head stops at the first level whose certificate meets the target error $\varepsilon$. With fresh perturbations at every decoding step, each certificate fails with probability at most $δ$ during generation. At a suitable threshold, the estimator reads $O(\varepsilon^{-2}\log(1/δ))$ values regardless of the context length, and no adaptive method reads fewer, up to constants. A 4-bit scan with deterministic bounds, shared across a grouped-query-attention group, generates the candidates exactly but reads every key. On three LLMs and ten settings at 16K--128K tokens, no certificate is violated, and at equal keys read our 90th-percentile error is 4.6--7.9$\times$ lower than that of the best of 15 baseline families. At equal bytes, the best baselines have 0.6--1.6 times our 90th-percentile error and at least 4.9 times our largest. End to end, our method stays within one point of dense attention on tasks and within 0.1\% in PG-19 perplexity, and the strongest baselines at equal bytes score as well. On CPU, decoding steps at 32K--128K tokens run 1.1--1.4$\times$ faster than dense attention on the same 16-bit cache.

0.11

Batch-Dynamic Coreness and Applications with Logarithmic Work via Balanced Pressures

cs.DS ·2026-11-18 ·Quinten De Man, Laxman Dhulipala, Kishen N Gowda, Zhongqi Wang
similarity 0.57
Abstract

We give a parallel algorithm that maintains a one-sided $(2+\varepsilon)$-approximation of all core numbers under batches of edge insertions and deletions. For fixed $\varepsilon>0$, the expected amortized work is $O(\log n)$ per edge update, and each batch has deterministic polylogarithmic depth. This improves on the previously known $(4+\varepsilon)$-approximation and $O(\log^2 n)$ amortized work bounds. This approximation factor approaches the factor-two limit for polylogarithmic update and query time under the OMv conjecture. Our algorithm is based on assigning each vertex a "pressure" and splits each edge's unit load smoothly between its endpoints according to their pressures. After each batch of updates, our dynamic algorithm adjusts the pressures of vertices in parallel to restore balance between the pressures and loads. We show that by maintaining balanced pressures we can obtain good approximations of core numbers. Our construction also gives a $(1+\varepsilon)$-approximation of the densest-subgraph value with logarithmic expected amortized work and supports batch-dynamic maximal matching, clique counting, forest decomposition, and coloring in low-arboricity graphs with improved or matching work bounds. We give a practical implementation of our batch-dynamic coreness algorithm and find that it is able to achieve smaller empirical error than the state-of-the-art parallel batch-dynamic implementation, while running faster. On six real-world graphs, it runs $32\times$ faster than that implementation in geometric mean and $4.1\times$ faster than a state-of-the-art heuristic baseline. On three graphs with up to 1.8 billion edges, it is $9.2\times$ faster than the heuristic baseline.

0.30