An algorithm for improving graph partitions

ABSTRACT

We present an algorithm called Improve that improves a proposed partition of a graph, taking as input a subset of vertices and returning a new subset of vertices with a smaller quotient cut score. The most powerful previously known method for improving quotient cuts, which is based on parametric flow, returns a partition whose quotient cut score is at least as small as any set contained within the proposed set. For our algorithm, we can prove a stronger guarantee: the quotient score of the set returned is nearly as small as any set in the graph with which the proposed set has a larger-than-expected intersection. The algorithm finds such a set by solving a sequence of polynomially many s -- t minimum cut problems, a sequence that cannot be cast as a single parametric flow problem. We demonstrate empirically that applying Improve to the output of various graph partitioning algorithms greatly improves the quality of cuts produced without significantly impacting the running time.

REFERENCES

• 1: N. Alon and V. Milman. Isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory B, 38:73--88, 1985.
• 2: 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]
• 3: M. Balinski. On a selection problem. Management Science, (17):230--231, 1970.
• 4: S. Bhatt and F. Leighton. A framework for solving vlsi graph layout problems. J. Computer Systems Sciences, 28:300--343, 1984.
• 5: R. B. Boppana. Eigenvalues and graph bisection: An average-case analysis (extended abstract). In FOCS, pages 280--285, 1987.
• 6: Christian Borgs , Jennifer Chayes , Mohammad Mahdian , Amin Saberi, Exploring the community structure of newsgroups, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1016914]
• 7: Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. In ICCV (1), pages 377--384, 1999.
• 8: T. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. In FOCS, pages 181--192, 1984.
• 9: J. Carrasco, D. Fain, K. Lang, and L. Zhukov. Clustering of bipartite advertiser-keyword graph, 2003.
• 10: F. Chung. Spectral graph theory, volume Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
• 11: Anirban Dasgupta , John Hopcroft , Ravi Kannan , Pradipta Mitra, Spectral clustering by recursive partitioning, Proceedings of the 14th conference on Annual European Symposium, p.256-267, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_25]
• 12: Tassos Dimitriou , Russell Impagliazzo, Go with the winners for graph bisection, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.510-520, January 25-27, 1998, San Francisco, California, United States
• 13: U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmica, 29(3):410--421, 2001.
• 14: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 15: G. Gallo , M. D. Grigoriadis , R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM Journal on Computing, v.18 n.1, p.30-55, Feb. 1989 [doi>10.1137/0218003]
• 16: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 17: A. V. Goldberg, Finding a Maximum Density Subgraph, University of California at Berkeley, Berkeley, CA, 1984
• 18: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 19: M. Jerrum and G. B. Sorkin. Simulated annealing for graph bisection. In IEEE Symposium on Foundations of Computer Science, pages 94--103, 1993.
• 20: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning, Operations Research, v.37 n.6, p.865-892, Nov–Dec. 1989
• 21: Ravi Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004 [doi>10.1145/990308.990313]
• 22: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 23: B. Kernighan and S. Lin. An effective heuristic procedure for partitioning graphs. The Bell System Technical Journal, pages 291--308, 1970.
• 24: K. Lang and S. Rao. A flow-based method for improving the expansion or conductance of graph cuts. In IPCO, pages 325--337, 2004.
• 25: F. T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In FOCS, pages 422--431, 1988.
• 26: M. Narasimhan and J. Bilmes. Local search for balanced submodular clusterings. In IJCAI, pages 981--986, 2007.
• 27: Sachin B. Patkar , H. Narayanan, Improving graph partitions using submodular functions, Discrete Applied Mathematics, v.131 n.2, p.535-553, 12 September 2003 [doi>10.1016/S0166-218X(02)00472-9]
• 28: J.-C. Picard and M. Queyranne. Selected applications of minimum cuts in networks. INFORM, 20(4):394--422, 1982.
• 29: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 30: J. Rhys. A selection problem of shared fixed costs and network flows. Management Science, (17):200--207, 1970.
• 31: D. Shmoys. Cut problems and their applications to divide-and-conquer, 1996.
• 32: Horst D. Simon , Shang-Hua Teng, How Good is Recursive Bisection?, SIAM Journal on Scientific Computing, v.18 n.5, p.1436-1445, Sept. 1997 [doi>10.1137/S1064827593255135]
• 33: A. J. Soper, C. Walshaw, and M. Cross. A combined evolutionary search and multilevel approach to graph partitioning. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 674--681, Las Vegas, Nevada, USA, 10-12 2000. Morgan Kaufmann.