{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T22:38:11Z","timestamp":1783204691199,"version":"3.54.6"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,10,1]]},"abstract":"<jats:p>\n                    We present the first analysis of diffusion on hypergraphs based on the Lov\u00e1sz-Simonovits theory. We demonstrate that an averaging-based diffusion operator is the appropriate generalization of the lazy random walk diffusion on 2-graphs because the diffusion rapidly converges to its stationary state from any initial state. By proving a Lov\u00e1sz-Simonovits-like theorem for this diffusion, we show that the diffusion rate depends on the hypergraph's conductance. To use averaging-based diffusion for clustering, we define a generalization of personalized page rank for hypergraphs, which we call ''Averaging-based Personalized Page Rank for Hypergraphs'' (APPRH). The fact that averaging-based diffusion is linear, unlike previous hypergraph diffusions used for clustering in the literature, allows us to use the Forward Push algorithm to compute APPRH efficiently. Using this method, we obtain theoretical bounds for the conductance of our clustering that are at least a constant times better than the best-known bounds in the literature. We compare our algorithm A-\n                    <jats:sc>HyperCut<\/jats:sc>\n                    against baselines on million-scale hypergraphs and find that our method is an order of magnitude faster while being competitive regarding the conductance of the local clusters produced.\n                  <\/jats:p>","DOI":"10.1145\/3677126","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T17:41:44Z","timestamp":1727718104000},"page":"1-27","source":"Crossref","is-referenced-by-count":3,"title":["A Lov\u00e1sz-Simonovits Theorem for Hypergraphs with Application to Local Clustering"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-7079-5040","authenticated-orcid":false,"given":"Raj","family":"Kamal","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Delhi, New Delhi, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0694-0602","authenticated-orcid":false,"given":"Amitabha","family":"Bagchi","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Delhi, New Delhii, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143847"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.89"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266275"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129139"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505525"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2020.01.012"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 2013 International Conference on Applied Mathematics and Computational Methods, Venice Italy. 187--194","author":"Bellaachia Abdelghani","year":"2013","unstructured":"Abdelghani Bellaachia and Mohammed Al-Dhelaan. 2013. Random walks in hypergraph. In Proceedings of the 2013 International Conference on Applied Mathematics and Computational Methods, Venice Italy. 187--194."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129116"},{"key":"e_1_2_2_12_1","volume-title":"The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems","author":"Brin Sergey","year":"1998","unstructured":"Sergey Brin and Lawrence Page. 1998. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, Vol. 30, 1--7 (1998), 107--117."},{"key":"e_1_2_2_13_1","volume-title":"Random walks on hypergraphs. Physical review E","author":"Carletti Timoteo","year":"2020","unstructured":"Timoteo Carletti, Federico Battiston, Giulia Cencetti, and Duccio Fanelli. 2020. Random walks on hypergraphs. Physical review E, Vol. 101, 2 (2020), 022308."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1088\/2632-072X\/abe27e"},{"key":"e_1_2_2_15_1","first-page":"673","article-title":"Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication","volume":"10","author":"Catalyurek Umit","year":"1999","unstructured":"Umit Catalyurek and Cevdet Aykanat. 1999. Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE TPDS, Vol. 10, 7 (1999), 673--693.","journal-title":"IEEE TPDS"},{"key":"e_1_2_2_16_1","unstructured":"\u00dcmit V cCataly\u00fcrek and Cevdet Aykanat. 2011. PaToH (Partitioning Tool for Hypergraphs). https:\/\/faculty.cc.gatech.edu\/ umit\/PaToH\/manual.pdf."},{"key":"e_1_2_2_17_1","unstructured":"Tanmoy Chakraborty Ayushi Dalmia Animesh Mukherjee and Niloy Ganguly. 2016. Metrics for Community Analysis: A Survey. arXiv:1604.03512 [cs.SI]."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178123"},{"key":"e_1_2_2_19_1","volume-title":"International conference on machine learning. PMLR, 1172--1181","author":"Chitra Uthsav","year":"2019","unstructured":"Uthsav Chitra and Benjamin Raphael. 2019. Random walks on hypergraphs with edge-dependent vertex weights. In International conference on machine learning. PMLR, 1172--1181."},{"key":"e_1_2_2_20_1","volume-title":"Random walk with restart on hypergraphs: fast computation and an application to anomaly detection. Data Mining and Knowledge Discovery","author":"Chun Jaewan","year":"2023","unstructured":"Jaewan Chun, Geon Lee, Kijung Shin, and Jinhong Jung. 2023. Random walk with restart on hypergraphs: fast computation and an application to anomaly detection. Data Mining and Knowledge Discovery (2023), 1--36."},{"key":"e_1_2_2_21_1","article-title":"Spectra of Random Regular Hypergraphs","volume":"28","author":"Dumitriu Ioana","year":"2021","unstructured":"Ioana Dumitriu and Yizhe Zhu. 2021. Spectra of Random Regular Hypergraphs. Electron. J. Comb., Vol. 28, 3 (2021).","journal-title":"Electron. J. Comb."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000022288.19776.77"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.1996.0109"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_2_25_1","volume-title":"Community detection in graphs. Physics reports","author":"Fortunato Santo","year":"2010","unstructured":"Santo Fortunato. 2010. Community detection in graphs. Physics reports, Vol. 486, 3--5 (2010), 75--174."},{"key":"e_1_2_2_26_1","volume-title":"Advanced flow-based multilevel hypergraph partitioning. arXiv preprint arXiv:2003.12110","author":"Gottesb\u00fcren Lars","year":"2020","unstructured":"Lars Gottesb\u00fcren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner. 2020. Advanced flow-based multilevel hypergraph partitioning. arXiv preprint arXiv:2003.12110 (2020)."},{"key":"e_1_2_2_27_1","volume-title":"Parallel flow-based hypergraph partitioning. arXiv preprint arXiv:2201.01556","author":"Gottesb\u00fcren Lars","year":"2022","unstructured":"Lars Gottesb\u00fcren, Tobias Heuer, and Peter Sanders. 2022. Parallel flow-based hypergraph partitioning. arXiv preprint arXiv:2201.01556 (2022)."},{"key":"e_1_2_2_28_1","volume-title":"Scalable Shared-Memory Hypergraph Partitioning. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 16--30","author":"Gottesb\u00fcren Lars","year":"2021","unstructured":"Lars Gottesb\u00fcren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. 2021. Scalable Shared-Memory Hypergraph Partitioning. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 16--30."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412034"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.37"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0122"},{"key":"e_1_2_2_34_1","unstructured":"Sepandar D Kamvar Taher H Haveliwala Christopher Manning and Gene H Golub. 2003. Exploiting the block structure of the web for computing pagerank. Technical Report. Technical report Stanford University."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DAC.1997.597203"},{"key":"e_1_2_2_36_1","volume-title":"A hypergraph partitioning package","author":"Karypis George","year":"1998","unstructured":"George Karypis and Vipin Kumar. 1998. A hypergraph partitioning package. Army HPC Research Center, Department of Computer Science & Engineering, University of Minnesota (1998)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623706"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772755"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209219.3213595"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623745"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89553"},{"key":"e_1_2_2_43_1","volume-title":"Random walks in a convex body and an improved","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1993","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Mikl\u00f3s Simonovits. 1993. Random walks in a convex body and an improved volume algorithm. Random structures & algorithms, Vol. 4, 4 (1993), 359--412."},{"key":"e_1_2_2_44_1","first-page":"526","article-title":"Conductance and convergence of markov chains-a combinatorial treatment of expanders","volume":"89","author":"Mihail Milena","year":"1989","unstructured":"Milena Mihail. 1989. Conductance and convergence of markov chains-a combinatorial treatment of expanders. In FOCS, Vol. 89. 526--531.","journal-title":"FOCS"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2022.04.009"},{"key":"e_1_2_2_46_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1998. The pagerank citation ranking: Bring order to the web. Technical Report. Technical report stanford University."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2742839"},{"key":"e_1_2_2_48_1","series-title":"SIAM Journal on computing","volume-title":"A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning","author":"Spielman Daniel A","year":"2013","unstructured":"Daniel A Spielman and Shang-Hua Teng. 2013. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on computing, Vol. 42, 1 (2013), 1--26."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403248"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037676.2037679"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939804"},{"key":"e_1_2_2_53_1","volume-title":"Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems","author":"Zhou Dengyong","year":"2006","unstructured":"Dengyong Zhou, Jiayuan Huang, and Bernhard Sch\u00f6lkopf. 2006. Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, Vol. 19 (2006)."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.784130"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677126","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:10:46Z","timestamp":1774977046000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,1]]}},"alternative-id":["10.1145\/3677126"],"URL":"https:\/\/doi.org\/10.1145\/3677126","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]}}}