{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T07:31:12Z","timestamp":1794036672861,"version":"4.8.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100009193","name":"Marsden Fund","doi-asserted-by":"publisher","award":["UOA1732"],"award-info":[{"award-number":["UOA1732"]}],"id":[{"id":"10.13039\/501100009193","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1936205"],"award-info":[{"award-number":["U1936205"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong","award":["#MMT-p2-23"],"award-info":[{"award-number":["#MMT-p2-23"]}]},{"name":"Ministry of Business, Innovation and Employment, New Zealand","award":["UOAX2001"],"award-info":[{"award-number":["UOAX2001"]}]},{"name":"Research Grants Council, University Grants Committee, Hong Kong","award":["CUHK 14217622"],"award-info":[{"award-number":["CUHK 14217622"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,11,13]]},"abstract":"<jats:p>A graph models the connections among objects. One important graph analytical task is clustering which partitions a data graph into clusters with dense innercluster connections. A line of clustering maximizes a function called modularity. Modularity-based clustering is widely adopted on dyadic graphs due to its scalability and clustering quality which depends highly on its selection of a random graph model. The random graph model decides not only which clustering is preferred - modularity measures the quality of a clustering based on its alignment to the edges of a random graph, but also the cost of computing such an alignment. Existing random hypergraph models either measure the hyperedge-cluster alignment in an All-Or-Nothing (AON) manner, losing important group-wise information, or introduce expensive alignment computation, refraining the clustering from scaling up. This paper proposes a new random hypergraph model called Hyperedge Expansion Model (HEM), a non-AON hypergraph modularity function called Partial Innerclusteredge modularity (PI) based on HEM, a clustering algorithm called Partial Innerclusteredge Clustering (PIC) that optimizes PI, and novel computation optimizations. PIC is a scalable modularity-based hypergraph clustering that can effectively capture the non-AON hyperedge-cluster relation. Our experiments show that PIC outperforms eight state-of-the-art methods on real-world hypergraphs in terms of both clustering quality and scalability and is up to five orders of magnitude faster than the baseline methods.<\/jats:p>","DOI":"10.1145\/3617335","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T17:28:39Z","timestamp":1699896519000},"page":"1-25","source":"Crossref","is-referenced-by-count":12,"title":["Modularity-based Hypergraph Clustering: Random Hypergraph Model, Hyperedge-cluster Relation, and Computation"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9746-8253","authenticated-orcid":false,"given":"Zijin","family":"Feng","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8374-140X","authenticated-orcid":false,"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[{"name":"The University of Auckland, Auckland, New Zealand"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4673-2587","authenticated-orcid":false,"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","unstructured":"Sameer Agarwal Jongwoo Lim Lihi Zelnik-Manor Pietro Perona David~J. Kriegman and Serge~J. Belongie. 2005. Beyond Pairwise Clustering. In CVPR. 838--845. https:\/\/doi.org\/10.1109\/CVPR.2005.89","DOI":"10.1109\/CVPR.2005.89"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315373515"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","unstructured":"021)]% aghdaei2021hypersf Ali Aghdaei Zhiqiang Zhao and Zhuo Feng. 2021. HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering. In ICCAD. 1--9. https:\/\/doi.org\/10.1109\/ICCAD51958.2021.9643555","DOI":"10.1109\/ICCAD51958.2021.9643555"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","unstructured":"William Aiello Fan Chung and Linyuan Lu. 2000. A random graph model for massive graphs. In STOC. 171--180. https:\/\/doi.org\/10.1145\/335305.335326","DOI":"10.1145\/335305.335326"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","unstructured":"Ilya Amburg Nate Veldt and Austin Benson. 2020. Clustering in graphs and hypergraphs with categorical edge labels. In WWW. 706--717. https:\/\/doi.org\/10.1145\/3366423.3380152","DOI":"10.1145\/3366423.3380152"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367--2630"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742--5468"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4612-0619--4"},{"key":"e_1_2_2_10_1","first-page":"1","article-title":"Scikit-network: Graph Analysis in Python","volume":"21","author":"Bonald Thomas","year":"2020","unstructured":"Thomas Bonald, Nathan de Lara, Quentin Lutz, and Bertrand Charpentier. 2020. Scikit-network: Graph Analysis in Python. J. Mach. Learn. , Vol. 21, 185 (2020), 1--6.","journal-title":"J. Mach. Learn."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319-00080-0"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","unstructured":"Jiajun Bu Shulong Tan Chun Chen Can Wang Hao Wu Lijun Zhang and Xiaofei He. 2010. Music recommendation by unified hypergraph: combining social media information and music content. In ACM Multimedia. 391--400. https:\/\/doi.org\/10.1145\/1873951.1874005","DOI":"10.1145\/1873951.1874005"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1126\/sciadv.abh1303"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.027104"},{"key":"e_1_2_2_19_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Paul","year":"1960","unstructured":"Paul ErdHo s, Alfr\u00e9d R\u00e9nyi, et al. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci , Vol. 5, 1 (1960), 17--60.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.09.002"},{"key":"e_1_2_2_23_1","first-page":"27683","article-title":"Local hyper-flow diffusion","volume":"34","author":"Fountoulakis Kimon","year":"2021","unstructured":"Kimon Fountoulakis, Pan Li, and Shenghao Yang. 2021. Local hyper-flow diffusion. NeurIPS , Vol. 34 (2021), 27683--27694.","journal-title":"NeurIPS"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","unstructured":"Koby Hayashi Sinan~G Aksoy Cheong~Hee Park and Haesun Park. 2020. Hypergraph random walks laplacians and clustering. In CIKM. 495--504. https:\/\/doi.org\/10.1145\/3340531.3412034","DOI":"10.1145\/3340531.3412034"},{"key":"e_1_2_2_25_1","volume-title":"Functional analysis and semi-groups","author":"Hille Einar","unstructured":"Einar Hille and Ralph~Saul Phillips. 1996. Functional analysis and semi-groups. Vol. , Vol. 31. American Mathematical Soc."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2903410"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908075"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0224307"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687698"},{"key":"e_1_2_2_30_1","volume-title":"NIPS","volume":"24","author":"Kim Sungwoong","year":"2011","unstructured":"Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang Yoo. 2011. Higher-order correlation clustering for image segmentation. NIPS , Vol. 24 (2011), 1530--1538."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--36687--2_24"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-020-00300--3"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","unstructured":"Geon Lee Minyoung Choe and Kijung Shin. 2021. How Do Hyperedges Overlap in Real-World Hypergraphs? - Patterns Measures and Generators. In WWW. 3396--3407. https:\/\/doi.org\/10.1145\/3442381.3450010","DOI":"10.1145\/3442381.3450010"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","unstructured":"Lei Li and Tao Li. 2013. News recommendation via hypergraph learning: encapsulation of user behavior and news content. In WSDM. 305--314. https:\/\/doi.org\/10.1145\/2433396.2433436","DOI":"10.1145\/2433396.2433436"},{"key":"e_1_2_2_38_1","volume-title":"NIPS","author":"Li Pan","unstructured":"Pan Li and Olgica Milenkovic. 2017. Inhomogeneous Hypergraph Clustering with Applications. In NIPS, Vol. , Vol. 30. 2308--2318."},{"key":"e_1_2_2_39_1","unstructured":"Pan Li and Olgica Milenkovic. 2018. Submodular hypergraphs: p-laplacians cheeger inequalities and spectral clustering. In ICML. 3014--3023."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","unstructured":"Wentao Li Miao Qiao Lu Qin Lijun Chang Ying Zhang and Xuemin Lin. 2022. On Scalable Computation of Graph Eccentricities. In SIGMOD. 904--916. https:\/\/doi.org\/10.1145\/3514221.3517874","DOI":"10.1145\/3514221.3517874"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317803"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","unstructured":"Meng Liu Nate Veldt Haoyu Song Pan Li and David~F Gleich. 2021. Strongly local hypergraph diffusions for clustering and semi-supervised learning. In WWW. 2092--2103. https:\/\/doi.org\/10.1145\/3442381.3449887","DOI":"10.1145\/3442381.3449887"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","unstructured":"Marios Papachristou and Jon Kleinberg. 2022. Core-Periphery Models for Hypergraphs. In KDD. 1337--1347. https:\/\/doi.org\/10.1145\/3534678.3539272","DOI":"10.1145\/3534678.3539272"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","unstructured":"Emad Ramadan Arijit Tarafdar and Alex Pothen. 2004. A hypergraph model for the yeast protein complex network. In IPDPS. 189. https:\/\/doi.org\/10.1109\/IPDPS.2004.1303205","DOI":"10.1109\/IPDPS.2004.1303205"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.016110"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","unstructured":"Sucheta Soundarajan and John~E. Hopcroft. 2012. Using community information to improve the precision of link prediction methods. In WWW. 607--608. https:\/\/doi.org\/10.1145\/2187980.2188150","DOI":"10.1145\/2187980.2188150"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","unstructured":"Yuuki Takai Atsushi Miyauchi Masahiro Ikeda and Yuichi Yoshida. 2020. Hypergraph Clustering Based on PageRank. In KDD. 1970--1978. https:\/\/doi.org\/10.1145\/3394486.3403248","DOI":"10.1145\/3394486.3403248"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.3389\/fnins.2014.00167"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","unstructured":"Nate Veldt Austin~R Benson and Jon Kleinberg. 2020a. Minimizing localized ratio cut objectives in hypergraphs. In KDD. 1708--1718. https:\/\/doi.org\/10.1145\/3394486.3403222","DOI":"10.1145\/3394486.3403222"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","unstructured":"Nate Veldt Anthony Wirth and David~F Gleich. 2020b. Parameterized correlation clustering in hypergraphs and bipartite graphs. In KDD. 1868--1876. https:\/\/doi.org\/10.1145\/3394486.3403238","DOI":"10.1145\/3394486.3403238"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007--9033-z"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","unstructured":"Zhiqiang Xu Yiping Ke Yi Wang Hong Cheng and James Cheng. 2012. A model-based approach to attributed graph clustering. In SIGMOD. 505--516. https:\/\/doi.org\/10.1145\/2213836.2213894","DOI":"10.1145\/2213836.2213894"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","unstructured":"Hao Yin Austin~R Benson Jure Leskovec and David~F Gleich. 2017. Local higher-order graph clustering. In KDD. 555--564. https:\/\/doi.org\/10.1145\/3097983.3098069","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","unstructured":"Chen Zhe Aixin Sun and Xiaokui Xiao. 2019. Community Detection on Large Complex Attribute Network. In KDD. 2041--2049. https:\/\/doi.org\/10.1145\/3292500.3330721","DOI":"10.1145\/3292500.3330721"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","unstructured":"Dengyong Zhou Jiayuan Huang and Bernhard Sch\u00f6 lkopf. 2006. Learning with Hypergraphs: Clustering Classification and Embedding. In NeurIPS. 1601--1608. https:\/\/doi.org\/10.7551\/mitpress\/7503.003.0205 io","DOI":"10.7551\/mitpress"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617335","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:45:53Z","timestamp":1750164353000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.1145\/3617335"],"URL":"https:\/\/doi.org\/10.1145\/3617335","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]}}}