{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T17:53:04Z","timestamp":1772301184965,"version":"3.50.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,5]],"date-time":"2018-03-05T00:00:00Z","timestamp":1520208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["17200817"],"award-info":[{"award-number":["17200817"]}]},{"name":"Santosh Vempala's NSF","award":["CCF-1217793"],"award-info":[{"award-number":["CCF-1217793"]}]},{"DOI":"10.13039\/100006734","name":"Princeton University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006734","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Simons Collaboration on Algorithms and Geometry"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>The celebrated Cheeger\u2019s Inequality (Alon and Milman 1985; Alon 1986) establishes a bound on the edge expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs. It has remained open to define a suitable spectral model for hypergraphs whose spectra can be used to estimate various combinatorial properties of the hypergraph.<\/jats:p>\n          <jats:p>In this article, we introduce a new hypergraph Laplacian operator generalizing the Laplacian matrix of graphs. In particular, the operator is induced by a diffusion process on the hypergraph, such that within each hyperedge, measure flows from vertices having maximum weighted measure to those having minimum. Since the operator is nonlinear, we have to exploit other properties of the diffusion process to recover the Cheeger\u2019s Inequality that relates hyperedge expansion with the \u201csecond eigenvalue\u201d of the resulting Laplacian. However, we show that higher-order spectral properties cannot hold in general using the current framework.<\/jats:p>\n          <jats:p>\n            Since higher-order spectral properties do not hold for the Laplacian operator, we instead use the concept of procedural minimizers to consider higher-order Cheeger-like inequalities. For any\n            <jats:italic>k<\/jats:italic>\n            \u2208 N, we give a polynomial-time algorithm to compute an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>r<\/jats:italic>\n            )-approximation to the\n            <jats:italic>k<\/jats:italic>\n            th procedural minimizer, where\n            <jats:italic>r<\/jats:italic>\n            is the maximum cardinality of a hyperedge. We show that this approximation factor is optimal under the SSE hypothesis (introduced by Raghavendra and Steurer (2010)) for constant values of\n            <jats:italic>k<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>Moreover, using the factor-preserving reduction from vertex expansion in graphs to hypergraph expansion, we show that all our results for hypergraphs extend to vertex expansion in graphs.<\/jats:p>","DOI":"10.1145\/3178123","type":"journal-article","created":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T13:12:12Z","timestamp":1520341932000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":42,"title":["Spectral Properties of Hypergraph Laplacian and Approximation Algorithms"],"prefix":"10.1145","volume":"65","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong"}]},{"given":"Anand","family":"Louis","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, INDIA"}]},{"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong"}]},{"given":"Chenzi","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2018,3,5]]},"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.1016\/0012-365X(88)90189-6"},{"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.1016\/0167-9260(95)00008-4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330060203"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070018"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_31"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"e_1_2_1_13_1","volume-title":"Internet and Network Economics","author":"Celis L. Elisa","unstructured":"L. Elisa Celis , Nikhil R. Devanur , and Yuval Peres . 2010. Local dynamics in bargaining networks via random-turn games . In Internet and Network Economics . Springer , 133--144. L. Elisa Celis, Nikhil R. Devanur, and Yuval Peres. 2010. Local dynamics in bargaining networks via random-turn games. In Internet and Network Economics. Springer, 133--144."},{"key":"e_1_2_1_14_1","volume-title":"Zhihao Gavin Tang, and Chenzi Zhang","author":"Hubert Chan T.-H.","year":"2016","unstructured":"T.-H. Hubert Chan , Anand Louis , Zhihao Gavin Tang, and Chenzi Zhang . 2016 . Spectral properties of hypergraph Laplacian and approximation algorithms. CoRR abs\/1605.01483. T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang. 2016. Spectral properties of hypergraph Laplacian and approximation algorithms. CoRR abs\/1605.01483."},{"key":"e_1_2_1_15_1","volume-title":"Xiaowei Wu, and Chenzi Zhang.","author":"Hubert Chan T.-H.","year":"2017","unstructured":"T.-H. Hubert Chan , Zhihao Gavin Tang , Xiaowei Wu, and Chenzi Zhang. 2017 . Diffusion operator and spectral analysis for directed hypergraph Laplacian. CoRR abs\/1711.01560. T.-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, and Chenzi Zhang. 2017. Diffusion operator and spectral analysis for directed hypergraph Laplacian. CoRR abs\/1711.01560."},{"key":"e_1_2_1_16_1","volume-title":"Zhihao Gavin Tang, and Chenzi Zhang","author":"Hubert Chan T.-H.","year":"2015","unstructured":"T.-H. Hubert Chan , Zhihao Gavin Tang, and Chenzi Zhang . 2015 . Spectral properties of Laplacian and stochastic diffusion process for edge expansion in hypergraphs. CoRR abs\/1510.01520. Retrieved from http:\/\/arxiv.org\/abs\/1510.01520. T.-H. Hubert Chan, Zhihao Gavin Tang, and Chenzi Zhang. 2015. Spectral properties of Laplacian and stochastic diffusion process for edge expansion in hypergraphs. CoRR abs\/1510.01520. Retrieved from http:\/\/arxiv.org\/abs\/1510.01520."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_18_1","volume-title":"The Laplacian of a hypergraph. Expand. Graphs (DIMACS Ser.)","author":"Chung Fan","year":"1993","unstructured":"Fan Chung . 1993. The Laplacian of a hypergraph. Expand. Graphs (DIMACS Ser.) ( 1993 ), 21--36. Fan Chung. 1993. The Laplacian of a hypergraph. Expand. Graphs (DIMACS Ser.) (1993), 21--36."},{"key":"e_1_2_1_19_1","volume-title":"Spectral Graph Theory","author":"Chung Fan","unstructured":"Fan Chung . 1997. Spectral Graph Theory . American Mathematical Society . http:\/\/www.math.ucsd.edu\/&sim;fan\/research\/revised.html. Fan Chung. 1997. Spectral Graph Theory. American Mathematical Society. http:\/\/www.math.ucsd.edu\/&sim;fan\/research\/revised.html."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2011.11.018"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1899056"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_23_1","volume-title":"22th Annual European Symposium Algorithms (ESA\u201914)","author":"Ene Alina","unstructured":"Alina Ene and Huy L. Nguyen . 2014. From graph to hypergraph multiway partition: Is the single threshold the only route? In 22th Annual European Symposium Algorithms (ESA\u201914) . Springer, Berlin, 382--393. Alina Ene and Huy L. Nguyen. 2014. From graph to hypergraph multiway partition: Is the single threshold the only route? In 22th Annual European Symposium Algorithms (ESA\u201914). Springer, Berlin, 382--393."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294459"},{"key":"e_1_2_1_26_1","article-title":"Uniform hypergraph partitioning: Provable tensor methods and sampling techniques","volume":"18","author":"Ghoshdastidar Debarghya","year":"2017","unstructured":"Debarghya Ghoshdastidar and Ambedkar Dukkipati . 2017 . Uniform hypergraph partitioning: Provable tensor methods and sampling techniques . J. Mach. Learn. Res. 18 (2017), 50:1--50:41. Retrieved from http:\/\/jmlr.org\/papers\/v18\/papers\/v18\/16-100.html. Debarghya Ghoshdastidar and Ambedkar Dukkipati. 2017. Uniform hypergraph partitioning: Provable tensor methods and sampling techniques. J. Mach. Learn. Res. 18 (2017), 50:1--50:41. Retrieved from http:\/\/jmlr.org\/papers\/v18\/papers\/v18\/16-100.html.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/839295.843666"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0916028"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512329"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-013-9596-x"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.12.024"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.58"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488611"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214078"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.13"},{"key":"e_1_2_1_38_1","unstructured":"John Lenz and Dhruv Mubayi. 2012. Eigenvalues and quasirandom hypergraphs. arXiv Preprint arXiv:1208.4863.  John Lenz and Dhruv Mubayi. 2012. Eigenvalues and quasirandom hypergraphs. arXiv Preprint arXiv:1208.4863."},{"key":"e_1_2_1_39_1","unstructured":"John Lenz and Dhruv Mubayi. 2013. Eigenvalues of non-regular linear quasirandom hypergraphs. arXiv Preprint arXiv:1309.3584.  John Lenz and Dhruv Mubayi. 2013. Eigenvalues of non-regular linear quasirandom hypergraphs. arXiv Preprint arXiv:1309.3584."},{"key":"e_1_2_1_40_1","volume-title":"Forum of Mathematics, Sigma","author":"Lenz John","unstructured":"John Lenz and Dhruv Mubayi . 2015. Eigenvalues and linear quasirandom hypergraphs . In Forum of Mathematics, Sigma , Vol. 3 . Cambridge Univ Press , e2. John Lenz and Dhruv Mubayi. 2015. Eigenvalues and linear quasirandom hypergraphs. In Forum of Mathematics, Sigma, Vol. 3. Cambridge Univ Press, e2."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746555"},{"key":"e_1_2_1_43_1","volume-title":"Approximation algorithm for sparsest k-partitioning","author":"Louis Anand","unstructured":"Anand Louis and Konstantin Makarychev . 2014a. Approximation algorithm for sparsest k-partitioning . In SODA. SIAM , 1244--1255. Anand Louis and Konstantin Makarychev. 2014a. Approximation algorithm for sparsest k-partitioning. In SODA. SIAM, 1244--1255."},{"key":"e_1_2_1_44_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201914)","author":"Louis Anand","unstructured":"Anand Louis and Yury Makarychev . 2014b. Approximation algorithms for hypergraph small set expansion and small set vertex expansion . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201914) , Vol. 28 . 339--355. Anand Louis and Yury Makarychev. 2014b. Approximation algorithms for hypergraph small set expansion and small set vertex expansion. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201914), Vol. 28. 339--355."},{"key":"e_1_2_1_45_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Louis Anand","unstructured":"Anand Louis , Prasad Raghavendra , Prasad Tetali , and Santosh Vempala . 2011. Algorithmic extensions of Cheegers inequality to higher eigenvalues and partitions . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 315--326. Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. 2011. Algorithmic extensions of Cheegers inequality to higher eigenvalues and partitions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 315--326."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.46"},{"key":"e_1_2_1_48_1","volume-title":"Montenegro and Prasad Tetali","author":"Ravi","year":"2006","unstructured":"Ravi R. Montenegro and Prasad Tetali . 2006 . Mathematical Aspects of Mixing Times in Markov Chains. Now Publishers . Ravi R. Montenegro and Prasad Tetali. 2006. Mathematical Aspects of Mixing Times in Markov Chains. Now Publishers."},{"key":"e_1_2_1_49_1","unstructured":"Ori Parzanchevski. 2013. Mixing in high-dimensional expanders. arXiv Preprint arXiv:1310.6477.  Ori Parzanchevski. 2013. Mixing in high-dimensional expanders. arXiv Preprint arXiv:1310.6477."},{"key":"e_1_2_1_50_1","unstructured":"Ori Parzanchevski and Ron Rosenthal. 2012. Simplicial complexes: Spectrum homology and random walks. arXiv Preprint arXiv:1211.6775.  Ori Parzanchevski and Ron Rosenthal. 2012. Simplicial complexes: Spectrum homology and random walks. arXiv Preprint arXiv:1211.6775."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3002-x"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00606-1"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2008.07.020"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2014.01.002"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178123","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3178123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:55Z","timestamp":1750215775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,5]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3178123"],"URL":"https:\/\/doi.org\/10.1145\/3178123","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,5]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}