A local graph partitioning algorithm finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring 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 it outputs, with at most a weak dependence on n, the number 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 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 φ, and 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). The complexity of a local partitioning algorithm is measured by its work/volume ratio, which is the ratio between the computational complexity of the algorithm on a given run, and the volume of the set output. We prove that for our algorithm, the expected value of the work/volume ratio is O(φ −1/2 polylog(n)). The best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee but a larger work/volume ratio of O(φ −1 polylog(n)). As an application of our local partitioning algorithm, we construct a fast algorithm for finding balanced cuts. The resulting algorithm takes as input a graph and a fixed value of φ, has complexity (m + nφ −1/2 )) · O(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 volume of the largest set in the graph with conductance at most φ.
Andersen and Peres REF simulate a volume-biased evolving set process to find sparse cuts.
Finding sparse cuts locally using evolving sets
STOC '09
Mathematics Computer Science