Source-linked AI summary
Finding Sparse Cuts Locally Using Evolving Sets
Reid Andersen, Yuval Peres
TL;DR
Local graph partitioning seeks sparse cuts through limited exploration, but prior approaches used random walks or personalized PageRank. The paper introduces EvoCut, which simulates the volume-biased evolving set process, and reports local conductance, work/volume, and balanced-cut guarantees under explicit graph-query assumptions.
Problem
Local partitioning must find low-conductance sets by exploring a small graph region while keeping complexity tied mainly to the output volume.
Method
EvoCut simulates the volume-biased evolving set process until a stopping time and outputs the resulting vertex set.
Results
EvoCut provides local approximation O(φ^1/2 log^1/2 n) and expected work/volume ratio O(φ^-1/2 polylog(n)); EvoPartition gives balanced cuts with complexity (m + nφ^-1/2) · O(polylog(n)).
Takeaways & Limitations
Evolving sets, previously used as analytical tools, are used here to construct a local partitioning algorithm and a fast balanced-cut algorithm.
Takeaways & Limitations
The analysis assumes graph access supporting neighbor-list queries in time proportional to degree and uniformly sampled-neighbor queries in constant time.
Abstract
from arXiv · showhide
A {\em local graph partitioning algorithm} finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of a large graph $G$, starting from a specified vertex. For the algorithm to be local, its complexity must be bounded in terms of the size of the set that it outputs, with at most a weak dependence on the number $n$ of vertices in $G$. Previous local partitioning algorithms find sparse cuts using random walks and personalized PageRank. In this paper, we introduce a randomized local partitioning algorithm that finds a sparse cut by simulating the {\em volume-biased evolving set process}, which is a Markov chain on sets of vertices. We prove that for any set of vertices $A$ that has conductance at most $φ$, for at least half of the starting vertices in $A$ our algorithm will output (with probability at least half), a set of conductance $O(φ^{1/2} \log^{1/2} n)$. We prove that for a given run of the algorithm, the expected ratio between its computational complexity and the volume of the set that it outputs is $O(φ^{-1/2} polylog(n))$. In comparison, the best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee, but a larger ratio of $O(φ^{-1} polylog(n))$ between the complexity and output volume. Using our local partitioning algorithm as a subroutine, we construct a fast algorithm for finding balanced cuts. Given a fixed value of $φ$, the resulting algorithm has complexity $O((m+nφ^{-1/2}) polylog(n))$ and returns a cut with conductance $O(φ^{1/2} \log^{1/2} n)$ and volume at least $v_φ/2$, where $v_φ$ is the largest volume of any set with conductance at most $φ$.
1 Introduction
EvoCut is a local partitioning algorithm that simulates the volume-biased evolving set process to find sparse cuts while improving the work/volume trade-off. It also supports a fast balanced-cut algorithm with stated conductance, volume, and complexity guarantees.
- Motivation: Local partitioning finds low-conductance vertex sets by exploring only a small graph region near a specified starting vertex.Such algorithms support cluster discovery and fast solutions to other partitioning problems.
- Prior work: Previous methods used random-walk distributions or personalized PageRank, with the latest Spielman–Teng guarantee f(φ) = O(φ^1/2 log^3/2 n) and work/volume ratio O(φ^-2 polylog(n)).Andersen, Chung, and Lang compute one personalized PageRank vector rather than a sequence of random-walk distributions.
- EvoCut: EvoCut simulates the volume-biased evolving set process, a Markov chain on vertex subsets, until a stopping time and outputs the resulting set.Its analysis bounds set growth using conductance and uses boundary-focused simulation to control computational work.
- Balanced cuts: EvoPartition has complexity (m + nφ^-1/2) · O(polylog(n)), and returns conductance O(φ^1/2 log^1/2 n) with volume at least half that of any set of conductance at most φ.It applies the local partitioning technique to balanced cuts and is described as faster by roughly φ^1/2 than existing algorithms with nontrivial approximation guarantees.
- Main result: EvoCut’s main theorem analyzes randomized output sets and work through a work/volume ratio, under graph-query assumptions allowing neighbor-list and uniformly sampled-neighbor access.The theorem takes a starting vertex and target conductance as input.
- Main result: For any set A with conductance at most φ and volume at most (2/3)µ(V), at least half its volume consists of starting vertices achieving the stated output guarantees with probability at least 1/2.The supplied theorem passage specifies the qualifying subset A′ but not the subsequent displayed conditions.
2 Preliminaries
This section introduces random walks, the evolving set process, and its volume-biased variant, then relates their transitions, conductance, and coupling properties.
- The Evolving Set Process: The evolving set process is a Markov chain on vertex subsets whose transitions grow or shrink the current set using a uniformly sampled threshold.The empty set and the full vertex set are absorbing states.
- Evolving Sets and Conductance: The growth gauge satisfies ψ(S) ≥ φ(S)^2/8 for every vertex set S, linking evolving-set growth to conductance.The section also relates conductance to expected volume change in the next ESP step.
- The Volume-Biased Evolving Set Process: The volume-biased ESP is a Markov chain on vertex subsets obtained from the ESP through a Doob h-transform with respect to volume.It is equivalent to conditioning the ESP to be absorbed at the full vertex set.
- The Diaconis-Fill Coupling: The Diaconis-Fill coupling jointly evolves a random walk vertex and an evolving set, first sampling the next walk vertex and then restricting the ESP transition to sets containing it.Conditioned on the evolving-set path, the walk vertex has the stationary distribution restricted to the current set.
- The Diaconis-Fill Coupling: Under the coupling, the vertex sequence is a random walk and the set sequence is a volume-biased ESP started from the singleton start set.These two marginal-process identities connect random-walk behavior to volume-biased evolving sets.
3 Local partitioning using the volume-biased evolving set process
The volume-biased evolving set process is analyzed as a way to find low-conductance sets along sample paths. Under conductance and volume conditions, many starting vertices yield paths containing a sparse set with high probability.
- A set A with µ(A) ≤ (2/3)µ(V) and φ(A) ≤ (100T)^-1 contains a subset A_T of volume at least µ(A)/2.For every starting vertex in A_T, the stated sample-path guarantee holds.
- The proof uses a martingale analysis of volume growth, optional stopping, Jensen’s inequality, and the conductance relation φ(S_j)^2 ≤ 8ψ(S_j).These ingredients yield the logarithmic bound controlling cumulative conductance along the process.
- O(T^-1/2 log^1/2 µ(V)) conductance is achieved by some observed state with high probability along a T-step sample path.The analysis bounds how often high-conductance states occur using the growth of set volume.
- The set A_T consists of vertices whose lazy random walks leave A with probability at most Tφ(A), and Proposition 5 guarantees µ(A_T) ≥ µ(A)/2.This escape condition connects the starting-vertex requirement to the conductance of A.
4 Simulating the volume-biased evolving set process
GenerateSample simulates the volume-biased evolving set process with a stopping rule and outputs its final set. Boundary-focused data structures and a path-cost analysis establish the algorithm’s sampling correctness and work guarantees.
- GenerateSample stops at time T or when path cost exceeds B, then outputs the final state S_τ sampled from the volume-biased process.Its generated path has the volume-biased ESP probability, and its complexity is at most O(B log n).
- O(log n) times the sample-path cost bounds GenerateSample’s complexity.The path cost is defined from boundary-related transitions and volume changes.
- EvoCut directly bounds expected path cost divided by output volume, avoiding the need to guess the output volume required by previous algorithms.This direct ratio analysis is based on a martingale argument and the transform between the ESP and volume-biased ESP.
- Ignoring interior vertices when updating the evolving set is the source of EvoCut’s running-time improvement.The implementation maintains the current set, its two-sided boundary, and transition values for boundary vertices.
5 Finding balanced cuts
EvoPartition adapts Spielman and Teng’s repeated local-cut framework by substituting EvoNibble for RandomNibble. The resulting randomized algorithm provides a balanced-cut procedure with near-linear-style complexity and a stated conductance guarantee.
- Construction: EvoPartition substitutes EvoNibble for RandomNibble in Spielman and Teng’s Partition algorithm, repeatedly removing returned cuts until termination.The construction applies the nibbling subroutine, removes the resulting cut, and repeats.
- Guarantees: O(mφ^-1/2 polylog(n)) is the expected complexity of EvoPartition.The theorem states this bound for the randomized algorithm.
- Guarantees: With probability at least 1/2, EvoPartition satisfies both of its stated output conditions.The supplied theorem fragment introduces these two simultaneous conditions, including the balance-related condition for low-conductance sets.
- Implementation: (m + nφ^-1/2) · O(polylog(n)) is an improved complexity bound obtained by applying Benczúr–Karger sparsification.This improves the preceding O(mφ^-1/2 polylog(n)) bound.
- Comparison: Balanced-cut methods trade conductance approximation against running time, with prior approaches including nearly-linear Partition, flow-based algorithms, and spectral recursion.The comparison discussion reports O(φ log^2 n), O(φ log n), and O(φ log^1/2 n) guarantees for selected alternatives, while recursive spectral partitioning has an Ω(n^2) time bound.