A Simple Active-Set Method for PageRank-Based Local Graph Clustering
2026-08-17 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a way to find small, well-connected groups in a large network near a starting point without looking at the whole network. They improve a classic method by creating a faster algorithm that estimates a special ranking of nodes called PageRank, doing so in a time that depends only on the accuracy needed and not on the network size. Their approach uses a process that grows a set of active nodes and solves linear systems efficiently to get accurate results. This work also improves previous methods related to a regularized version of PageRank and provides better theoretical guarantees on running time.
local graph clusteringPageRankapproximate PageRank vectorteleportation parameterlocal push methodsymmetric diagonally dominant (SDD) linear systemSDD solversconductancel1-regularized PageRankgraph algorithms
Authors
Zhewei Wei, Mingji Yang
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.