{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T03:41:04Z","timestamp":1792640464024,"version":"4.5.0"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>In this paper we study variants of the widely used spectral clustering that partitions a graph into $k$ clusters by (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix and (2) grouping the embedded points into $k$ clusters via $k$-means algorithms. We show that, for a wide class of graphs, spectral clustering gives a good approximation of the optimal clustering. While this approach was proposed in the early 1990s and has comprehensive applications, prior to our work similar results were known only for graphs generated from stochastic models. We also give a nearly linear time algorithm for partitioning well-clustered graphs based on computing a matrix exponential and approximate nearest neighbor data structures.<\/jats:p>","DOI":"10.1137\/15m1047209","type":"journal-article","created":{"date-parts":[[2017,3,30]],"date-time":"2017-03-30T11:55:29Z","timestamp":1490874929000},"page":"710-743","source":"Crossref","is-referenced-by-count":25,"title":["Partitioning Well-Clustered Graphs: Spectral Clustering Works!"],"prefix":"10.1137","volume":"46","author":[{"given":"Richard","family":"Peng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"He","family":"Sun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Zanetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,3,30]]},"reference":[{"key":"atypb1","unstructured":"Z. Allen-Zhu, S. Lattanzi, and V. S. Mirrokni,\n                      A local algorithm for finding well-connected clusters\n                      , in Proceedings of the 30th International Conference on Machine Learning (ICML'13), 2013, pp. 396-404."},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"S. Arora, B. Barak, and D. Steurer,\n                      Subexponential algorithms for unique games and related problems\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS'10), 2010, pp. 563-572.","DOI":"10.1109\/FOCS.2010.59"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Kale,\n                      A combinatorial, primal-dual approach to semidefinite programs\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC'07), 2007, pp. 227-236.","DOI":"10.1145\/1250790.1250823"},{"key":"atypb5","first-page":"56","author":"Arora S.","year":"2009","journal-title":"J. ACM"},{"key":"atypb6","unstructured":"D. Arthur and S. Vassilvitskii,\n                      $k$-means++: The advantages of careful seeding\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07), 2007, pp. 1027-1035."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.006"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"S. Ben-David,\n                      A theoretical approach to the clustering selection problem\n                      , in Proceedings of the 4th MultiClust Workshop on Multiple Clusterings, Multi-view Data, and Multi-source Knowledge-driven Clustering, 2013.","DOI":"10.1145\/2501006.2501007"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10390643"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1979.11327"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/0707001"},{"key":"atypb13","unstructured":"T. K. Dey, A. Rossi, and A. Sidiropoulos,\n                      Spectral Concentration, Robust $k$-Center, and Simple Clustering\n                      , arXiv:1404.3918, 2014."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"atypb15","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, Cambridge, 2012."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"P. Indyk and R. Motwani,\n                      Approximate nearest neighbors: Towards removing the curse of dimensionality\n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98), 1998, pp. 604-613.","DOI":"10.1145\/276698.276876"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford,\n                      An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations\n                      , in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), 2014, pp. 217-226.","DOI":"10.1137\/1.9781611973402.16"},{"key":"atypb19","unstructured":"P. Kolev and K. Mehlhorn,\n                      A Note on Spectral Clustering\n                      , CoRR, abs\/1509.09188, 2015."},{"key":"atypb20","unstructured":"I. Koutis, A. Levin, and R. Peng,\n                      Improved spectral sparsification and numerical algorithms for SDD matrices\n                      , in Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS'12), 2012, pp. 266-277."},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"T. C. Kwok, L. C. Lau, Y. T. Lee, S. Oveis Gharan, and L. Trevisan,\n                      Improved Cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap\n                      , in Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC'13), 2013, pp. 11-20.","DOI":"10.1145\/2488608.2488611"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"J. R. Lee, S. Oveis Gharan, and L. Trevisan,\n                      Multi-way spectral partitioning and higher-order Cheeger inequalities\n                      , in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12), 2012, pp. 1117-1130.","DOI":"10.1145\/2213977.2214078"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"A. Louis, P. Raghavendra, P. Tetali, and S. Vempala,\n                      Many sparse cuts via higher eigenvalues\n                      , in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12), 2012, pp. 1131-1140.","DOI":"10.1145\/2213977.2214079"},{"key":"atypb25","unstructured":"K. Makarychev, Y. Makarychev, and A. Vijayaraghavan,\n                      Correlation clustering with noisy partial information\n                      , in Proceedings of the 28th Conference on Learning Theory (COLT'15), 2015, pp. 1321-1342."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90133-W"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"F. McSherry,\n                      Spectral partitioning of random graphs\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'01), 2001, pp. 529-537.","DOI":"10.1109\/SFCS.2001.959929"},{"key":"atypb28","first-page":"849","volume":"2","author":"Ng A. Y.","year":"2002","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"L. Orecchia, S. Sachdeva, and N. K. Vishnoi,\n                      Approximating the exponential, the Lanczos method and an $\\tilde{O}(m)$-time spectral algorithm for balanced separator\n                      , in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12), 2012, pp. 1141-1160.","DOI":"10.1145\/2213977.2214080"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"L. Orecchia, L. J. Schulman, U. V. Vazirani, and N. K. Vishnoi,\n                      On partitioning graphs via single commodity flows\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08), 2008, pp. 461-470.","DOI":"10.1145\/1374376.1374442"},{"key":"atypb31","first-page":"59","author":"Ostrovsky R.","year":"2012","journal-title":"J. ACM"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"S. Oveis Gharan and L. Trevisan,\n                      Partitioning into expanders\n                      , in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), 2014, pp. 1256-1266.","DOI":"10.1137\/1.9781611973402.93"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS887"},{"key":"atypb34","first-page":"301","author":"Saloff-Coste L.","year":"1997","journal-title":"Berlin"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"J. Sherman,\n                      Breaking the multicommodity flow barrier for ${O}(\\sqrt{\\log n})$-approximations to sparsest cut\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09), 2009, pp. 363-372.","DOI":"10.1109\/FOCS.2009.66"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a005"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"atypb41","unstructured":"V. Vu,\n                      A Simple SVD Algorithm for Finding Hidden Partitions\n                      , arXiv:1404.3918, 2014."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1047209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:21:12Z","timestamp":1787340072000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1047209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1047209"],"URL":"https:\/\/doi.org\/10.1137\/15m1047209","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}