Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning

ABSTRACT

We consider the problem of decomposing a weighted graph with n vertices into a collection P of vertex disjoint clusters such that, for all clusters C ε P, the graph induced by the vertices in C and the edges leaving C, has conductance bounded below by φ. We show that for planar graphs we can compute a decomposition P such that |P| < n/ρ, where ρ is a constant, in O(log n) parallel time with O(n) work. Slightly worse guarantees can be obtained in nearly linear time for graphs that have fixed size minors or bounded genus. We show how these decompositions can be used in the first known linear work parallel construction of provably good preconditioners for the important class of fixed degree graph Laplacians. On a more theoretical note, we present upper bounds on the Euclidean distance of eigenvectors of the normalized Laplacian from the space of vectors which consists of the cluster-wise constant vectors scaled by the square roots of the total incident weights of the vertices.

REFERENCES

• 1: Arik Azran , Zoubin Ghahramani, A new approach to data driven clustering, Proceedings of the 23rd international conference on Machine learning, p.57-64, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143852]
• 2: Piotr Berman , Georg Schnitger, On the performance of the minimum degree ordering for Gaussian elimination, SIAM Journal on Matrix Analysis and Applications, v.11 n.1, p.83-88, January 1990 [doi>10.1137/0611005]
• 3: Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777418]
• 4: Erik G. Boman , Bruce Hendrickson, Support Theory for Preconditioning, SIAM Journal on Matrix Analysis and Applications, v.25 n.3, p.694-717, 2003 [doi>10.1137/S0895479801390637]
• 5: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 6: F. Chung. Spectral Graph Theory, volume 92 of Regional Conference Series in Mathematics. American Mathematical Society, 1997.
• 7: Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004 [doi>10.1145/1024074.1024079]
• 8: P. Drineas , A. Frieze , R. Kannan , S. Vempala , V. Vinay, Clustering Large Graphs via the Singular Value Decomposition, Machine Learning, v.56 n.1-3, p.9-33 [doi>10.1023/B:MACH.0000033113.59016.96]
• 9: Michael Elkin , Yuval Emek , Daniel A. Spielman , Shang-Hua Teng, Lower-stretch spanning trees, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060665]
• 10: A. George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10:345--363, 1973.
• 11: J. R. Gilbert , R. E. Tarjan, The analysis of a nested dissection algorithm, Numerische Mathematik, v.50 n.4, p.377-404, FEB. 1987 [doi>10.1007/BF01396660]
• 12: K. Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, Pittsburgh, October 1996. CMU CS Tech Report CMU-CS--96--123.
• 13: 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]
• 14: D. Hochbaum and D. Shmoys. A best possible approximation algorithm for the k-center problem. Math. Oper Re., 10:180--184, 1985.
• 15: Anil Joshi, Topics in optimization and sparse linear systems, University of Illinois at Urbana-Champaign, Champaign, IL, 1997
• 16: 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]
• 17: 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]
• 18: Ioannis Koutis , Gary L. Miller, A linear work, O(n^1/6) time, parallel algorithm for solving planar Laplacians, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1002-1011, January 07-09, 2007, New Orleans, Louisiana
• 19: R. Lipton, D. Rose, and R. Tarjan. Generalized nested dissection. SIAM Journal of Numerical Analysis, 16:346--358, 1979.
• 20: Bruce M. Maggs , Gary L. Miller , Ojas Parekh , R. Ravi , Shan Leung Maverick Woo, Finding effective support-tree preconditioners, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073996]
• 21: Gary L. Miller , Peter C. Richter, Lower bounds for graph embeddings and combinatorial preconditioners, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007929]
• 22: R. Ostrovsky , Y. Rabani, Polynomial time approximation schemes for geometric k-clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.349, November 12-14, 2000
• 23: Christos H. Papadimitriou , Prabhakar Raghavan , Hisao Tamaki , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Journal of Computer and System Sciences, v.61 n.2, p.217-235, Oct. 2000 [doi>10.1006/jcss.2000.1711]
• 24: F. Pellegrini. A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries. In Euro-Par 2007, Parallel Processing, 13th International Euro-Par Conference, Rennes, France, August 28--31, 2007, Proceedings, pages 195--204, 2007.
• 25: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 26: M. Reid-Miller, G. L. Miller, and F. Modugno. List ranking and parallel tree contraction. In J. Reif, editor, Synthesis of Parallel Algorithms, chapter 3, pages 115--194. Morgan Kaufmann, 1993.
• 27: Daniel A. Spielman , Shang-Hua Teng, Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m1.31), Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.416, October 11-14, 2003
• 28: 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]
• 29: G. Stewart and J.-G. Sun. Matrix Perturbation Theory. Academic Press, Boston, 1990.
• 30: N. Tishby and N. Slonim. Data clustering by markovian relaxation and the information bottleneck method. In NIPS, pages 640--646, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Conditioning
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
combinatorial preconditioning, multi-way decompositions, planar graphs, spectral graph theory