{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T06:50:30Z","timestamp":1782802230123,"version":"3.54.5"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2014,12,17]],"date-time":"2014-12-17T00:00:00Z","timestamp":1418774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0644037, CCF-0915251"],"award-info":[{"award-number":["CCF-0644037, CCF-0915251"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1017403"],"award-info":[{"award-number":["CCF-1017403"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005492","name":"Stanford University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005492","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,12,17]]},"abstract":"<jats:p>A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero.<\/jats:p>\n          <jats:p>\n            It has been conjectured that an analogous characterization holds for higher multiplicities: There are\n            <jats:italic>k<\/jats:italic>\n            eigenvalues close to zero if and only if the vertex set can be partitioned into\n            <jats:italic>k<\/jats:italic>\n            subsets, each defining a sparse cut. We resolve this conjecture positively. Our result provides a theoretical justification for clustering algorithms that use the bottom\n            <jats:italic>k<\/jats:italic>\n            eigenvectors to embed the vertices into R\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            , and then apply geometric considerations to the embedding.\n          <\/jats:p>\n          <jats:p>\n            We also show that these techniques yield a nearly optimal quantitative connection between the expansion of sets of size \u2248\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            and \u03bb\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            , the\n            <jats:italic>k<\/jats:italic>\n            th smallest eigenvalue of the normalized Laplacian, where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices. In particular, we show that in every graph there are at least\n            <jats:italic>k<\/jats:italic>\n            \/2 disjoint sets (one of which will have size at most 2\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            ), each having expansion at most\n            <jats:italic>O<\/jats:italic>\n            (\u221a\u03bb\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            log\n            <jats:italic>k<\/jats:italic>\n            ). Louis, Raghavendra, Tetali, and Vempala have independently proved a slightly weaker version of this last result. The \u221alog\n            <jats:italic>k<\/jats:italic>\n            bound is tight, up to constant factors, for the \u201cnoisy hypercube\u201d graphs.\n          <\/jats:p>","DOI":"10.1145\/2665063","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T13:38:51Z","timestamp":1418996331000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":110,"title":["Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities"],"prefix":"10.1145","volume":"61","author":[{"given":"James R.","family":"Lee","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shayan Oveis","family":"Gharan","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794270248"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605051"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_2_1_7_1","volume-title":"Inequalities in Fourier analysis. Ann. of Math. (2) 102, 1","author":"Beckner William","year":"1975","unstructured":"William Beckner . 1975. Inequalities in Fourier analysis. Ann. of Math. (2) 102, 1 ( 1975 ), 159--182. William Beckner. 1975. Inequalities in Fourier analysis. Ann. of Math. (2) 102, 1 (1975), 159--182."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706593"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5802\/aif.357"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276719"},{"key":"e_1_2_1_12_1","volume-title":"Plotkin","author":"Charikar Moses","year":"1998","unstructured":"Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , and Serge A . Plotkin . 1998 b. Approximating a finite metric by a small number of tree metrics. In Proceedings of FOCS. IEEE Computer Society , 379--388. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge A. Plotkin. 1998b. Approximating a finite metric by a small number of tree metrics. In Proceedings of FOCS. IEEE Computer Society, 379--388."},{"key":"e_1_2_1_13_1","volume-title":"Paul Erd\u0151s Is Eighty","volume":"2","author":"Chung F. R. K.","year":"1996","unstructured":"F. R. K. Chung . 1996 . Laplacians of graphs and Cheeger's inequalities. In Combinatorics , Paul Erd\u0151s Is Eighty , Vol. 2 (Keszthely, 1993). Bolyai Soc. Math. Stud. , Vol. 2. J\u00e1nos Bolyai Math. Soc., Budapest, 157--172. F. R. K. Chung. 1996. Laplacians of graphs and Cheeger's inequalities. In Combinatorics, Paul Erd\u0151s Is Eighty, Vol. 2 (Keszthely, 1993). Bolyai Soc. Math. Stud., Vol. 2. J\u00e1nos Bolyai Math. Soc., Budapest, 157--172."},{"key":"e_1_2_1_14_1","volume-title":"Spectral Graph Theory. CBMS Regional Conference Series in Mathematics","volume":"92","author":"Chung Fan R. K.","year":"1997","unstructured":"Fan R. K. Chung . 1997 . Spectral Graph Theory. CBMS Regional Conference Series in Mathematics , vol. 92 . (Published for the Conference Board of the Mathematical Sciences, Washington, DC) Fan R. K. Chung. 1997. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol. 92. (Published for the Conference Board of the Mathematical Sciences, Washington, DC)"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2012.02.009"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of 6th Workshop on Approximation, Randomization, and Combinatorial Optimization Lecture Notes in Computer Science","volume":"2764","author":"Fakcharoenphol J.","unstructured":"J. Fakcharoenphol and K. Talwar . 2003. An improved decomposition theorem for graphs excluding a fixed minor . In Proceedings of 6th Workshop on Approximation, Randomization, and Combinatorial Optimization Lecture Notes in Computer Science , vol. 2764 , Springer, 36--46. J. Fakcharoenphol and K. Talwar. 2003. An improved decomposition theorem for graphs excluding a fixed minor. In Proceedings of 6th Workshop on Approximation, Randomization, and Combinatorial Optimization Lecture Notes in Computer Science, vol. 2764, Springer, 36--46."},{"key":"e_1_2_1_17_1","volume-title":"Lee","author":"Gupta Anupam","year":"2003","unstructured":"Anupam Gupta , Robert Krauthgamer , and James R . Lee . 2003 . Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of FOCS. IEEE Computer Society , 534--543. Anupam Gupta, Robert Krauthgamer, and James R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of FOCS. IEEE Computer Society, 534--543."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-011-0132-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-20212-4","volume-title":"Probability in Banach Spaces: Isoperimetry and Processes","author":"Ledoux Michel","year":"1991","unstructured":"Michel Ledoux and Michel Talagrand . 2011. Probability in Banach Spaces: Isoperimetry and Processes , Springer-Verlag , Berlin . Reprint of the 1991 edition. Michel Ledoux and Michel Talagrand. 2011. Probability in Banach Spaces: Isoperimetry and Processes, Springer-Verlag, Berlin. Reprint of the 1991 edition."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0400-5"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of SODA. SIAM, 193--201","author":"Lee J. R.","unstructured":"J. R. Lee and A. Sidiropoulos . 2010. Genus and the geometry of the cut graph . In Proceedings of SODA. SIAM, 193--201 . J. R. Lee and A. Sidiropoulos. 2010. Genus and the geometry of the cut graph. In Proceedings of SODA. SIAM, 193--201."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033252.2033280"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"e_1_2_1_28_1","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"Matou\u0161ek J.","unstructured":"J. Matou\u0161ek . 2002. Lectures on Discrete Geometry. Graduate Texts in Mathematics , vol. 212 , Springer-Verlag , NY. J. Matou\u0161ek. 2002. Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212, Springer-Verlag, NY."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-007-0115-9"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Laurent Miclo. 2013. On hyperboundedness and spectrum of Markov operators. Preprint.  Laurent Miclo. 2013. On hyperboundedness and spectrum of Markov operators. Preprint.","DOI":"10.1007\/s00222-014-0538-8"},{"key":"e_1_2_1_31_1","volume-title":"On spectral clustering: Analysis and an algorithm","author":"Ng Andrew","unstructured":"Andrew Ng , Michael Jordan , and Yair Weiss . 2002. On spectral clustering: Analysis and an algorithm . In Proceedings of NIPS. MIT Press , 849--856. Andrew Ng, Michael Jordan, and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. In Proceedings of NIPS. MIT Press, 849--856."},{"key":"e_1_2_1_32_1","unstructured":"Ryan O'Donnell and David Witmer. 2012. Improved small-set expansion from higher eigenvalues. arXiv:1204.4688.  Ryan O'Donnell and David Witmer. 2012. Improved small-set expansion from higher eigenvalues. arXiv:1204.4688."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.85"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806776"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(72)90008-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2006.129"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000054"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2665063","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2665063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:25Z","timestamp":1750227205000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2665063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,17]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12,17]]}},"alternative-id":["10.1145\/2665063"],"URL":"https:\/\/doi.org\/10.1145\/2665063","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,17]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}