Finding sparse cuts locally using evolving sets

ABSTRACT

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 polylognoparen(φ^-1/2). The best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee but a larger work/volume ratio of polylognoparen(φ^-1). 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 polylog{m+nφ^-1/2), 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 φ.

REFERENCES

• 1: Reid Andersen , Fan Chung , Kevin Lang, Local Graph Partitioning using PageRank Vectors, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.475-486, October 21-24, 2006 [doi>10.1109/FOCS.2006.44]
• 2: Reid Andersen , Kevin J. Lang, Communities from seed sets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135814]
• 3: Sanjeev Arora , Elad Hazan , Satyen Kale, 0(\sqrt {\log n)} Approximation to SPARSEST CUT in Õ(n²) Time, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.238-247, October 17-19, 2004 [doi>10.1109/FOCS.2004.1]
• 4: Sanjeev Arora , Satyen Kale, A combinatorial, primal-dual approach to semidefinite programs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250823]
• 5: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 6: András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
• 7: F. Chung. Spectral graph theory, volume Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: P. Diaconis and J. A. Fill. Strong stationary times via a new form of duality. The Annals of Probability, (18):1483--1522, 1990.
• 10: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 11: Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
• 12: Rohit Khandekar , Satish Rao , Umesh Vazirani, Graph partitioning using single commodity flows, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132574]
• 13: Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , Michael W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367591]
• 14: D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009.
• 15: M. Mihail, Conductance and convergence of Markov chains-a combinatorial treatment of expanders, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.526-531, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63529]
• 16: R. Montenegro. Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels. Electron. Comm. Probab., 12:377--389 (electronic), 2007.
• 17: Ravi Montenegro, The simple random walk and max-degree walk on a directed graph, Random Structures & Algorithms, v.34 n.3, p.395-407, May 2009 [doi>10.1002/rsa.v34:3]
• 18: Ben Morris , Yuval Peres, Evolving sets and mixing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780585]
• 19: Lorenzo Orecchia , Leonard J. Schulman , Umesh V. Vazirani , Nisheeth K. Vishnoi, On partitioning graphs via single commodity flows, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374442]
• 20: D. A. Spielmat, Spectral partitioning works: planar graphs and finite element meshes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.96, October 14-16, 1996
• 21: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 22: D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs/cs/0607105, 2006.
• 23: D. A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR, abs/0809.3232, 2008.
• 24: D. Williams. Probability with martingales. Cambridge University Press, 1991.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
evolving sets, graph partitioning, local algorithms