CS Paper Radar

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

Zhewei Wei, Mingji Yang

cs.DS ·submitted 2026-08-17 09:45 UTC · v1

Abstract

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.

Comment
17 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Nearly optimal Personalized PageRank computation

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

Accelerating the Local Push Primitive for PageRank Computation

cs.DS ·2026-09-10 ·Guanyu Cui, Zhewei Wei, Mingji Yang
similarity 0.78
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

Competitive Random-Order Correlation k-Clustering

cs.DS ·2026-09-28 ·Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman, Omer Wasim, Tegan Wilson
theory similarity 0.64
Abstract · 58 pages, 5 figures, 1 table

Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is to compute a partition of the vertex set such that the total number of disagreements, i.e. the sum of edges between clusters, and non-edges within clusters, is minimized. In this paper, we study correlation $k$-clustering, in which the total number of clusters is restricted to $k$. Correlation $k$-clustering is NP-hard, and while previous work has presented a polynomial time approximation scheme for constant $k$, there are no known results for general $k$. Our first result is a polynomial-time constant-factor approximation algorithm for correlation $k$-clustering for general $k$. The main focus of this work is in the more challenging online setting. Noting that the best competitive ratio under adversarial arrivals is known to be $Ω(n)$, we concentrate on the well-studied random-order model, where vertices arrive in random order and on arrival of a vertex, edges to its earlier-arrived neighbors are revealed. We prove a surprising lower bound of $Ω(\log k)$-competitiveness for any online algorithm, which can be extended to $Ω(\log n)$ when $k = \text{poly}(n)$. Finally, the main result of this paper is a polylogarithmic upper bound on the competitive ratio for correlation $k$-clustering, using an algorithm inspired by the classic Pivot algorithm for correlation clustering. All theorems have been verified using Lean.

0.19

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

Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee

cs.DS ·2026-11-04 ·He Sun, Yong Zhang, Yacong Zhou
theory similarity 0.62
Abstract · 41 pages, 3 figures, 1 table

Partitioning the vertex set of a graph $G=(V,E)$ into clusters is a classical problem in computer science. As vertices within clusters should be well connected and cuts between clusters sparse, Oveis Gharan and Trevisan (SODA 2014, [OGT14]) proposed to measure the partition quality using inner and outer conductance, i.e., the bi-criteria guarantee. Specifically, when partitioning $V$ into vertex-disjoint subsets $P_1,\ldots, P_k$, every subgraph induced by $P_i$ should have high conductance, while the conductance of $P_i$ in $G$ should be low. They studied the existence of such a partition and designed a polynomial-time algorithm achieving this guarantee. For more than a decade, their algorithm remained the only one achieving this guarantee on its output clusters. In this paper, we study faster cluster decomposition algorithms under the same setup as [OGT14] and prove three results: 1. We make their existential result algorithmic: Our algorithms run in nearly-linear time, and achieve the same bi-criteria guarantee as the one in [OGT14] up to constant factors, including the asymptotically tight dependence on $k$. 2. We prove that their existential result holds algorithmically under a much weaker condition on the initial disjoint subsets. To achieve this, we develop a general algorithm framework that boosts the approximation guarantee of a solution: given an $α$-approximate solution to the $k$-way conductance problem, if $ρ_G(k+1)/ρ_G(k)=Ω\left(α/\varepsilon\right)$, then a $(1+\varepsilon)$-approximate solution can be obtained using only $O(k(1+\logα))$ minimum $s$-$t$ cut computations. 3. We present a nearly-linear time algorithm that finds clusters with the bi-criteria guarantee. Our algorithm has the same guarantee as the one in [OGT14], which, for any unweighted graph of $n$ vertices and $m$ edges, runs in $\widetilde{O}(knm^2)$ time.

0.33

Introvert Clustering for Distributed Graph Algorithms

cs.DC cs.DS ·2026-09-09 ·Yi-Jun Chang, Nima Dolatabadi
similarity 0.62
Abstract

We introduce a graph decomposition primitive called introvert clustering, which strengthens standard low-diameter clustering by guaranteeing that every clustered vertex keeps at least a $\left(\frac12-\varepsilon\right)$-fraction of its relevant neighbors in its own cluster. Repeatedly applying this primitive yields a layered introvert network decomposition with $O(\log n)$ layers and weak diameter $O(\log n)$. We give two applications in the $\mathsf{LOCAL}$ model. For every constant $\varepsilon>0$, we obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for list $\left(\frac32+\varepsilon\right)Δ$-edge coloring on graphs of maximum degree $Δ\geqΔ_0(\varepsilon)$; for bipartite graphs, the result holds for all $Δ$. For every constant $0<\varepsilon<1/4$, we also obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for a $\left(\frac14-\varepsilon\right)$-locally balanced cut, where every vertex has at least a $\left(\frac14-\varepsilon\right)$-fraction of its neighbors on the opposite side. The resulting algorithms are remarkably simple: edge coloring processes the layers in reverse order and colors each cluster, while locally balanced cut processes them forward and computes a locally maximum cut within each cluster. The introvert guarantee enables these procedures beyond the usual greedy regime of network decomposition. We construct the decomposition in $O(\log^2 n)$ randomized rounds using Miller--Peng--Xu low-diameter clustering and a simple trimming procedure, and deterministically in $\widetilde O(\log^2 n)$ rounds via a white-box adaptation of the recursive network decomposition algorithm of Ghaffari and Grunau [FOCS 2024].

0.26

Accelerated Local Algorithms for Personalized and Regularized PageRank

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

Sublogarithmic Online Graph Exploration

cs.DS cs.DM ·2026-11-10 ·Julia Baligacs
similarity 0.60
Abstract

We study the online graph exploration problem, in which an agent must visit every vertex of an initially unknown weighted graph on $n$ vertices and return to its starting vertex. In this model, a vertex's incident edges and their weights are revealed when it is first visited. Despite extensive research, the best known competitive guarantee for general graphs had remained $\mathcal{O}(\log n)$, a bound already established in 1977 for the greedy TSP heuristic Nearest Neighbor. Subsequent approaches, including hierarchical depth-first search (hDFS) and Blocking, achieve better guarantees on restricted graph classes but have logarithmic or worse competitive ratios on general graphs. This raises the question of whether the logarithmic barrier is inherent and Nearest Neighbor is asymptotically optimal. We answer this question in the negative by giving an $\mathcal{O}(\log n/\log \log n)$-competitive algorithm. Our algorithm is a slight modification of hDFS, and we establish its competitive guarantee with a surprisingly short proof.

0.22