{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:07:04Z","timestamp":1787360824949,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1216642"],"award-info":[{"award-number":["1216642"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph $G$, $\\lambda_2 = \\Omega( \\phi^V(G) \\phi(G) )$, where $\\phi^V(G)$ denotes the robust vertex expansion of $G$ and $\\phi(G)$ denotes the edge expansion of $G$. The second generalization relates the second eigenvalue to the edge expansion and the expansion profile of $G$, for all $k \\geq 2$, $ \\lambda_2 = \\Omega( \\phi_k(G) \\phi(G) \/ k )$, where $\\phi_k(G)$ denotes the $k$-way expansion of $G$. These show that the spectral partitioning algorithm has better performance guarantees when $\\phi^V(G)$ is large (e.g., planted random instances) or $\\phi_k(G)$ is large (instances with few disjoint nonexpanding sets). Both bounds are tight up to a constant factor. Our approach is based on a method to analyze solutions of Laplacian systems, and this allows us to extend the results to local graph partitioning algorithms. In particular, we show that our approach can be used to analyze personal pagerank vectors and to give a local graph partitioning algorithm for the small-set expansion problem with performance guarantees similar to the generalizations of Cheeger's inequality. We also present a spectral approach to prove similar results for the truncated random walk algorithm. These show that local graph partitioning algorithms almost match the performance of the spectral partitioning algorithm, with the additional advantages that they apply to the small-set expansion problem and their running time could be sublinear. Our techniques provide common approaches to analyze the spectral partitioning algorithm and local graph partitioning algorithms.<\/jats:p>","DOI":"10.1137\/16m1079816","type":"journal-article","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T11:14:56Z","timestamp":1494501296000},"page":"890-910","source":"Crossref","is-referenced-by-count":4,"title":["Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile"],"prefix":"10.1137","volume":"46","author":[{"given":"Tsz Chiu","family":"Kwok","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,5,11]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"R. Andersen and F. R. K. Chung,\n                      Detecting sharp drops in pagerank and a simplified local partitioning algorithm\n                      , in Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, 2007, pp. 1-12.","DOI":"10.1007\/978-3-540-72504-6_1"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"R. Andersen, F. R. K. Chung, and K. J. Lang,\n                      Local graph partitioning using PageRank vectors\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 475-486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"R. Andersen and Y. Peres,\n                      Finding sparse cuts locally using evolving sets\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 235-244.","DOI":"10.1145\/1536414.1536449"},{"key":"atypb6","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, 2010, pp. 563-572.","DOI":"10.1109\/FOCS.2010.59"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"R. Boppana,\n                      Eigenvalues and graph bisection: An average-case analysis\n                      , in Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 280-285.","DOI":"10.1109\/SFCS.1987.22"},{"key":"atypb8","first-page":"195","author":"Cheeger J.","year":"1970","journal-title":"NJ"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.07.018"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007504"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"T. C. Kwok and L. C. Lau,\n                      Finding small sparse cuts by random walk\n                      , in Proceedings of the 16th International Workshop on Randomization and Computation, 2012, pp. 615-626.","DOI":"10.1007\/978-3-642-32512-0_52"},{"key":"atypb14","unstructured":"T. C. Kwok and L. C. Lau,\n                      Lower bounds on expansions of graph powers\n                      , in Proceedings of the 17th Annual International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2014, pp. 313-324."},{"key":"atypb15","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 Symposium on Theory of Computing, 2013, pp. 11-20.","DOI":"10.1145\/2488608.2488611"},{"key":"atypb16","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 Symposium on Theory of Computing, 2012, pp. 1117-1130.","DOI":"10.1145\/2213977.2214078"},{"key":"atypb17","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, 2012, pp. 1131-1140.","DOI":"10.1145\/2213977.2214079"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz and R. Kannan,\n                      Faster mixing via average conductance\n                      , in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 282-287.","DOI":"10.1145\/301250.301317"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz and M. Simonovits,\n                      The mixing time of Markov chains, an isoperimetric inequality, and computing the volume\n                      , in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, pp. 346-354.","DOI":"10.1109\/FSCS.1990.89553"},{"key":"atypb20","first-page":"101","volume":"10","author":"Margulis G. A.","year":"1974","journal-title":"Problemy Peredachi Informatsii"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"F. McSherry,\n                      Spectral partitioning of random graphs\n                      , in Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001, pp. 529-537.","DOI":"10.1109\/SFCS.2001.959929"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0434-7"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"S. Oveis Gharan and L. Trevisan,\n                      Approximating the expansion profile and almost optimal local graph clustering\n                      , in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 187-196.","DOI":"10.1109\/FOCS.2012.85"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"atypb25","unstructured":"Z. A. Zhu, S. Lattanzi, and V. Mirrokni,\n                      Local graph clustering beyond Cheeger's inequality\n                      , in Proceedings of the 30th International Conference on Machine Learning, 2013, pp. 396-404."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1079816","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:00Z","timestamp":1787338080000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1079816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1079816"],"URL":"https:\/\/doi.org\/10.1137\/16m1079816","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}