Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

ABSTRACT

We introduce and study a new notion of graph partitioning, intimately connected to spectral clustering and k-means clustering. Formally, given a graph G on n vertices, we ask to find a graph H that is the union of k cliques on n vertices, such that L_G > λ L_H where λ is maximized. Here L_G and L_H are the (normalized) Laplacians of the graphs G and H respectively. Informally, our graph partitioning objective asks for the optimal spectral simplification of a given graph as a disjoint union of k cliques.

We justify this objective function in several ways. First and foremost, we show that a commonly used spectral clustering algorithm implicitly optimizes this objective function, up to a factor of O(k). Using this connection, we immediately get an O(k)-approximation algorithm to our new objective function by simply using the spectral clustering algorithm on G. Next, we demonstrate another application of our objective function: we use it as a means to proving that simple spectral clustering algorithms can solve some well-studied graph partitioning problems (such as partitioning into expanders). Additionally, we also show that (a relaxation of) this optimization problem naturally arises as the dual problem to the question of finding the worst-case integrality gap instance for the classical k-means SDP. Finally, owing to these close connection between some classical clustering techniques (such as k-means and spectral clustering), we argue that a more complete understanding of this optimization problem could lead to new algorithmic insights and techniques for the area of graph partitioning.

References

1. N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83--96, 1986.
2. N. Alon, A. Lubotzky, and A. Wigderson. Semi-direct product in groups and zig-zag product in graphs: connections and applications. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 630--637. IEEE, 2001.
3. N. Alon and V. D. Milman. λ₁, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1):73--88, 1985.
4. S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 227--236. ACM, 2007.
5. S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 227--236. ACM, 2007.
6. S. Arora, J. Lee, and A. Naor. Euclidean distortion and the sparsest cut. Journal of the American Mathematical Society, 21(1):1--21, 2008.
7. S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):5, 2009.
8. G. Arzhantseva and R. Tessera. Relatively expanding box spaces with no expansion. arXiv preprint arXiv:1402.1481, 2014.
9. J. Batson, D. A. Spielman, and N. Srivastava. Twice-ramanujan sparsifiers. SIAM Journal on Computing, 41(6):1704--1721, 2012.
10. P. Biswal, J. R. Lee, and S. Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. Journal of the ACM (JACM), 57(3):13, 2010.
11. E. G. Boman and B. Hendrickson. Support theory for preconditioning. SIAM Journal on Matrix Analysis and Applications, 25(3):694--717, 2003.
12. J. Cheeger. A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis, 625:195--199, 1970.
13. E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864--894, 1994.
14. I. Dhillon, Y. Guan, and B. Kulis. A unified view of kernel k-means, spectral clustering and graph cuts. Citeseer, 2004.
15. I. S. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 551--556. ACM, 2004.
16. N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi) cut theorems and their applications. SIAM Journal on Computing, 25(2):235--251, 1996.
17. S. O. Gharan and L. Trevisan. Partitioning into expanders. In SODA, pages 1256--1266. SIAM, 2014.
18. O. Goldschmidt and D. S. Hochbaum. Polynomial algorithm for the k-cut problem. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 444--451. IEEE, 1988.
19. N. J. Harvey and N. Olver. Pipage rounding, pessimistic estimators and matrix concentration. In SODA, pages 926--945. SIAM, 2014.
20. J. Hopcroft and R. Kannan. Foundations of Data Science. 2014.
21. K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM (JACM), 48(2):274--296, 2001.
22. R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. Journal of the ACM (JACM), 51(3):497--515, 2004.
23. J. A. Kelner. Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. SIAM Journal on Computing, 35(4):882--902, 2006.
24. N. L. D. Khoa and S. Chawla. Large scale spectral clustering using resistance distance and spielman-teng solvers. In Discovery Science, pages 7--21. Springer, 2012.
25. N. L. D. Khoa and S. Chawla. A scalable approach to spectral clustering with sdd solvers. Journal of Intelligent Information Systems, pages 1--20, 2013.
26. A. Kumar and R. Kannan. Clustering with spectral norm and the k-means algorithm. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 299--308. IEEE, 2010.
27. J. R. Lee, S. Oveis Gharan, and L. Trevisan. Multi-way spectral partitioning and higher-order cheeger inequalities. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1117--1130. ACM, 2012.
28. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787--832, 1999.
29. M. Lichman. UCI machine learning repository, 2013.
30. A. Louis, P. Raghavendra, P. Tetali, and S. Vempala. Many sparse cuts via higher eigenvalues. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1131--1140. ACM, 2012.
31. F. McSherry. Spectral partitioning of random graphs. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 529--537. IEEE, 2001.
32. M. Meila and J. Shi. A random walks view of spectral segmentation. 2001.
33. A. Y. Ng, M. I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2:849--856, 2002.
34. H. Qiu and E. R. Hancock. Clustering and embedding using commute times. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29(11):1873--1890, 2007.
35. J. Shi and J. Malik. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 22(8):888--905, 2000.
36. D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913--1926, 2011.
37. D. A. Spielman and S.-H. Teng. Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra and its Applications, 421(2):284--305, 2007.
38. D. A. Spielman and S.-H. Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981--1025, 2011.
39. L. Trevisan. Is cheeger-type approximation possible for nonuniform sparsest cut? arXiv preprint arXiv:1303.2730, 2013.
40. Y. Weiss. Segmentation using eigenvectors: a unifying view. In Computer vision, 1999. The proceedings of the seventh IEEE international conference on, volume 2, pages 975--982. IEEE, 1999.
41. E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems, volume 15, 2003.
42. E. Xing, E. P. Xing, M. Jordan, and M. I. Jordan. On semidefinite relaxations for normalized k-cut and connections to spectral clustering. 2003.
43. D. Yan, L. Huang, and M. I. Jordan. Fast approximate spectral clustering. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 907--916. ACM, 2009.

Index Terms

• Theory of computation

  • Design and analysis of algorithms