Source-linked AI summary
A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
Daniel A. Spielman, Shang-Hua Teng
TL;DR
The paper addresses how to find graph structure near a given vertex without examining a massive graph in its entirety. It introduces local clustering based on random-walk proximity and uses it for nearly-linear-time graph partitioning, with further applications developed in companion papers.
Problem
The paper asks how to find a small cluster around a given vertex in time proportional to the cluster size while examining only nearby vertices in a massive graph.
Method
The paper introduces Nibble, which orders exploration by short random-walk likelihood and truncates walk distributions to search efficiently for low-conductance clusters near the input vertex.
Results
The local clustering algorithm supports a nearly-linear-time graph partitioning algorithm with nearly optimal balance among cuts approximating a target conductance.
Takeaways & Limitations
The local clustering algorithm serves as a primitive for fast graph partitioning and for companion algorithms for graph sparsification and symmetric, diagonally-dominant linear systems.
Takeaways & Limitations
For partition construction, conductance and vertex volumes in induced subgraphs are measured using the original graph's vertex degrees.
Abstract
from arXiv · showhide
We study the design of local algorithms for massive graphs. A local algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a non-empty local cluster, is nearly linear in the size of the cluster it outputs. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly-linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly-linear time algorithm for solving linear systems in symmetric, diagonally-dominant matrices. The linear system solver also leads to a nearly linear-time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers.
1 Introduction
The paper develops local graph algorithms that explore neighborhoods defined by short random walks, then uses local clustering as a primitive for nearly-linear-time partitioning and related algorithms.
- Local algorithms: Local algorithms seek small clusters near a given vertex while examining only nearby vertices and spending time proportional to the output size.The paper defines nearness through graph exploration and short random walks rather than requiring inspection of the entire graph.
- Applications: The partitioning algorithm serves as a basis for companion-paper algorithms for graph sparsification, symmetric diagonally-dominant linear systems, and Laplacian eigenvalue approximation.These applications are presented in the two companion papers rather than developed fully here.
- Local clustering: For a cluster C0 with conductance at most α · φ2/log3 n, Nibble returns a mostly internal cluster of conductance at most φ with probability at least 1/2 from a degree-sampled vertex.This guarantee applies for a constant α > 0 and may not succeed for every input vertex.
- Local clustering: Nibble maintains a truncated random-walk distribution, restricting searches to high-probability nodes so its support remains close to the produced cluster size.The truncation is what makes the local clustering procedure output sensitive.
- Motivation: Nearly-linear-time graph primitives are motivated by graph and computational problem sizes that have grown beyond the practical reach of slower algorithms.The paper cites web graphs with hundreds of billions of nodes and linear systems with hundreds of millions of variables.
- Graph partitioning: The local clustering algorithm is used to construct a randomized graph-partitioning algorithm with nearly-linear running time and approximately optimal balance for approximate sparsest cuts.The paper describes this as the first nearly linear-time algorithm with that balance guarantee, to the authors’ knowledge.
2 Clusters and Conductance
This section defines clusters through conductance and develops Nibble, a local random-walk algorithm that returns low-conductance sets under explicit volume and probability-mass conditions.
- Clusters and conductance: A cluster is richly connected internally and sparsely connected externally, with quality measured by conductance.Conductance is the ratio of external connections to total connections.
- The Algorithm Nibble: Nibble evolves a random walk from a seed vertex, truncating small probability entries before examining sweep sets ranked by normalized probability.The truncation threshold is d(u)ε, and sweep sets maximize p(u)/d(u).
- The Algorithm Nibble: Nibble returns a sweep set when it has conductance at most φ, volume between 2^b and (5/6)µ(V), and sufficient probability density at 2^b.These conditions respectively control cluster quality, balance, minimum size, and concentrated probability mass.
- Performance: Nibble runs in time O(2^b(log^6 m)/φ^4) on all inputs.The theorem gives this as a worst-case implementation bound.
- Guarantees: The analysis guarantees that a non-empty output has low conductance and bounded volume, while suitable input sets contain a large-volume subset of successful starting vertices.For v in the good subset, a non-empty output captures volume at least 2^(b−1) from the input set.
Step 1: Sg and its properties
The first analysis step identifies vertices whose random walks remain sufficiently within a low-conductance set, then proves that many such vertices exist and Nibble captures substantial volume from them.
- Defining S^g: S^g consists of vertices in S whose random walks are reasonably likely to remain in S through the last analyzed time.The definition uses a bound on the probability of escaping S by time t_last.
- Volume guarantee: The good subset has volume at least half the volume of S.The bound is µ(S^g) ≥ µ(S)/2.
- Nibble guarantee: If Nibble starts at v ∈ S^g and outputs a non-empty set C, then µ(C ∩ S) ≥ 2^(b−1).This guarantee applies when S has conductance at most f_1(φ).
Step 2: Refining Sg
The second analysis step refines S^g using random-walk curve inequalities, partitions good starting vertices into classes, and proves that Nibble finds a qualifying low-conductance set for those vertices.
- Step 2: Refining S^g: The Lovász–Simonovits curve I(p, x) is concave, and the curve after one walk step lies below the preceding curve.The analysis uses this monotonicity together with conductance-dependent drops at sweep-set points.
- Step 2: Refining S^g: The proof restricts the conductance-drop inequality to points x = λ_j(Mp), avoiding a stronger claim that it holds for every x.The paper notes that the unrestricted claim in was false, while the restricted form suffices here.
- Refined subsets: Vertices in S^g are partitioned into subsets S^g_b using thresholds x_h and stopping indices h_v, with x_{h−1} < x_h.The quantities h_v are well-defined and determine the partition.
- Proof of success: If no iteration and sweep index satisfy the acceptance conditions, the curve I(q_t, ·) becomes too low, contradicting the lower-bound analysis.The contradiction is established through separate cases based on x_ℓ and the endpoint x_{h_v}.
- Proof of success: Under the stated low-conductance and volume assumptions, some t and j satisfy conditions (C.1)–(C.3), while condition (C.4) holds throughout the relevant interval.Consequently, Nibble outputs a non-empty set for the corresponding good starting vertices.
3 Nearly Linear-Time Graph Partitioning
Partition uses Random Nibble, which repeatedly invokes the local clustering procedure to find an approximate sparsest cut with nearly optimal balance in nearly linear time.
- Guarantee: With high probability, if G contains a cut S of sparsity α · θ2/ log3 n and balance b ≤1/2, Partition finds D with ΦV (D) ≤θ and bal (D) ≥b/2.Here α > 0 is a constant, and the output preserves half the supplied balance while meeting the target conductance.
- Running time: Partition runs in expected time O(m log7 n/φ4), where m is the number of graph edges.The algorithm is therefore suited to quickly finding crude cuts.
- Procedure: Random Nibble selects a vertex according to ψV and a parameter b from 1 through ⌈log m⌉, then invokes Nibble with randomly chosen parameters.Its expected running time is small, and it is expected to remove only a small fraction of any low-conductance set.
- Procedure: If Random Nibble outputs a non-empty set C, then µ (C) ≤(5/6)µ (V ).This bound is used in Partition's analysis to control the accumulated output volume.
- Algorithm: Partition maintains residual sets Wj and accumulates disjoint output sets Dj until it stops, with φ set to θ/7.The output is D = D1 ∪· · · ∪Djout.
- Guarantee: For every low-conductance set S, with high probability D is either a large fraction of S or a large fraction of the entire graph.The two alternatives accommodate cases where no large, low-conductance output exists and cases where a small S leads to a large output.
- Analysis: The output has volume at most (7/8)µ (V ), and when µ (D) ≤µ (V )/2, its conductance satisfies ΦV (D) ≤φ.The proof also establishes the high-probability alternative underlying property (P.3).