{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:22:09Z","timestamp":1768108929043,"version":"3.49.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>Hypergraphs, which use hyperedges to capture groupwise interactions among different entities, have gained increasing attention recently for their versatility in effectively modeling real-world networks. In this paper, we study the problem of computing hyper-triangles (formed by three fully-connected hyperedges), which is a basic structural unit in hypergraphs. Although existing approaches can be adopted to compute hyper-triangles by exhaustively examining hyperedge combinations, they overlook the structural characteristics distinguishing different hyper-triangle patterns. Consequently, these approaches lack specificity in computing particular hyper-triangle patterns and exhibit low efficiency. In this paper, we unveil a new formation pathway for hyper-triangles, transitioning from hyperedges to hyperwedges before assembling into hyper-triangles, and classify hyper-triangle patterns based on hyperwedges. Leveraging this insight, we introduce a two-step framework to reduce the redundant checking of hyperedge combinations. Under this framework, we propose efficient algorithms for computing a specific pattern of hyper-triangles. Approximate algorithms are also devised to support estimated counting scenarios. Furthermore, we introduce a fine-grained hypergraph clustering coefficient measurement that can reflect diverse properties of hypergraphs based on different hyper-triangle patterns. Extensive experimental evaluations conducted on 11 real-world datasets validate the effectiveness and efficiency of our proposed techniques.<\/jats:p>","DOI":"10.14778\/3712221.3712238","type":"journal-article","created":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:03:04Z","timestamp":1744048984000},"page":"729-742","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Computation of Hyper-Triangles on Hypergraphs"],"prefix":"10.14778","volume":"18","author":[{"given":"Haozhe","family":"Yin","sequence":"first","affiliation":[{"name":"The University of New South Wales"}]},{"given":"Kai","family":"Wang","sequence":"additional","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiao Tong University"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University"}]},{"given":"Ruijia","family":"Wu","sequence":"additional","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiao Tong University"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiao Tong University"}]}],"member":"320","published-online":{"date-parts":[[2025,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_2_1_2_1","volume-title":"On sampling from massive graph streams. arXiv preprint arXiv:1703.02625","author":"Ahmed Nesreen K","year":"2017","unstructured":"Nesreen K Ahmed, Nick Duffield, Theodore Willke, and Ryan A Rossi. 2017. On sampling from massive graph streams. arXiv preprint arXiv:1703.02625 (2017)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjds\/s13688-020-00231-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380152"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-00080-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1873951.1874005"},{"key":"e_1_2_1_9_1","volume-title":"Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs. arXiv preprint arXiv:2306.00893","author":"Cai Xinwei","year":"2023","unstructured":"Xinwei Cai, Xiangyu Ke, Kai Wang, Lu Chen, Tianming Zhang, Qing Liu, and Yunjun Gao. 2023. Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs. arXiv preprint arXiv:2306.00893 (2023)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_11_1","series-title":"SIAM Journal on computing 14, 1","volume-title":"Arboricity and subgraph listing algorithms","author":"Chiba Norishige","year":"1985","unstructured":"Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing 14, 1 (1985), 210--223."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_2_1_13_1","volume-title":"Subgraph centrality and clustering in complex hyper-networks. Physica A: Statistical Mechanics and its Applications 364","author":"Estrada Ernesto","year":"2006","unstructured":"Ernesto Estrada and Juan A Rodr\u00edguez-Vel\u00e1zquez. 2006. Subgraph centrality and clustering in complex hyper-networks. Physica A: Statistical Mechanics and its Applications 364 (2006), 581--594."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Song Feng Emily Heath Brett Jefferson Cliff Joslyn Henry Kvinge Hugh D Mitchell Brenda Praggastis Amie J Eisfeld Amy C Sims Larissa B Thackray et al. 2021. Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC bioinformatics 22 1 (2021) 287.","DOI":"10.1186\/s12859-021-04197-2"},{"key":"e_1_2_1_16_1","volume-title":"Beyond Graphs: Can Large Language Models Comprehend Hypergraphs? arXiv preprint arXiv:2410.10083","author":"Feng Yifan","year":"2024","unstructured":"Yifan Feng, Chengwu Yang, Xingliang Hou, Shaoyi Du, Shihui Ying, Zongze Wu, and Yue Gao. 2024. Beyond Graphs: Can Large Language Models Comprehend Hypergraphs? arXiv preprint arXiv:2410.10083 (2024)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00244"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"325","DOI":"10.3934\/mbe.2024015","article-title":"Prediction of influential proteins and enzymes of certain diseases using a directed unimodular hypergraph","volume":"21","author":"Gopalakrishnan Sathyanarayanan","year":"2024","unstructured":"Sathyanarayanan Gopalakrishnan and Swaminathan Venkatraman. 2024. Prediction of influential proteins and enzymes of certain diseases using a directed unimodular hypergraph. Mathematical Biosciences and Engineering 21, 1 (2024), 325--345.","journal-title":"Mathematical Biosciences and Engineering"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom.2013.51"},{"key":"e_1_2_1_20_1","first-page":"1","article-title":"Triangle-free hypergraphs","volume":"15","author":"Gy\u0151ri Ervin","year":"2006","unstructured":"Ervin Gy\u0151ri. 2006. Triangle-free hypergraphs. Combinatorics, Probability and Computing 15, 1-2 (2006), 185--191.","journal-title":"Combinatorics, Probability and Computing"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452815"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.37"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3143612"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30115-8_22"},{"key":"e_1_2_1_26_1","volume-title":"2020 IEEE International Conference on Data Mining (ICDM). IEEE, 272--281","author":"Kook Yunbum","year":"2020","unstructured":"Yunbum Kook, Jihoon Ko, and Kijung Shin. 2020. Evolution of real-world hyper-graphs: Patterns and models without oracles. In 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 272--281."},{"key":"e_1_2_1_27_1","volume-title":"Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1-3","author":"Latapy Matthieu","year":"2008","unstructured":"Matthieu Latapy. 2008. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1-3 (2008), 458--473."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407823"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-023-01837-2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2487802"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the sixth ACM international conference on Web search and data mining. 305--314","author":"Li Lei","year":"2013","unstructured":"Lei Li and Tao Li. 2013. News recommendation via hypergraph learning: encapsulation of user behavior and news content. In Proceedings of the sixth ACM international conference on Web search and data mining. 305--314."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 685--694","author":"Lim Yongsub","year":"2015","unstructured":"Yongsub Lim and U Kang. 2015. Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 685--694."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1093\/bioinformatics\/btaa768","article-title":"Classification in biological networks with hypergraphlet kernels","volume":"37","author":"Lugo-Martinez Jose","year":"2021","unstructured":"Jose Lugo-Martinez, Daniel Zeiberg, Thomas Gaudelet, No\u00ebl Malod-Dognin, Natasa Przulj, and Predrag Radivojac. 2021. Classification in biological networks with hypergraphlet kernels. Bioinformatics 37, 7 (2021), 1000--1007.","journal-title":"Bioinformatics"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1093\/bioinformatics\/btab652","article-title":"Hypergraph-based logistic matrix factorization for metabolite-disease interaction prediction","volume":"38","author":"Ma Yingjun","year":"2022","unstructured":"Yingjun Ma and Yuanyuan Ma. 2022. Hypergraph-based logistic matrix factorization for metabolite-disease interaction prediction. Bioinformatics 38, 2 (2022), 435--443.","journal-title":"Bioinformatics"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"197605","DOI":"10.1007\/s11704-024-40663-9","article-title":"A survey on lora of large language models","volume":"19","author":"Mao Yuren","year":"2025","unstructured":"Yuren Mao, Yuhang Ge, Yijiang Fan, Wenyi Xu, Yu Mi, Zhonghao Hu, and Yunjun Gao. 2025. A survey on lora of large language models. Frontiers of Computer Science 19, 7 (2025), 197605.","journal-title":"Frontiers of Computer Science"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCSW.2010.41"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0136497"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-021-02388-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297929"},{"key":"e_1_2_1_44_1","volume-title":"Advances in Computers.","author":"Ravichandran Kaushik","unstructured":"Kaushik Ravichandran, Akshara Subramaniasivam, PS Aishwarya, and NS Kumar. 2023. Fast exact triangle counting in large graphs using SIMD acceleration. In Advances in Computers. Vol. 128. Elsevier, 233--250."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2732587.2732595"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11224"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2742839"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0023176"},{"key":"e_1_2_1_51_1","volume-title":"Truss decomposition in massive networks. arXiv preprint arXiv:1205.6693","author":"Wang Jia","year":"2012","unstructured":"Jia Wang and James Cheng. 2012. Truss decomposition in massive networks. arXiv preprint arXiv:1205.6693 (2012)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411862"},{"key":"e_1_2_1_53_1","first-page":"3245","article-title":"Hypergraph collaborative network on vertices and hyperedges","volume":"45","author":"Wu Hanrui","year":"2022","unstructured":"Hanrui Wu, Yuguang Yan, and Michael Kwok-Po Ng. 2022. Hypergraph collaborative network on vertices and hyperedges. IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 3 (2022), 3245--3258.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Dingqi Yang Bingqing Qu Jie Yang and Philippe Cudre-Mauroux. 2019. Revisiting user mobility and social relationships in lbsns: a hypergraph embedding approach. In The world wide web conference. 2147--2157.","DOI":"10.1145\/3308558.3313635"},{"key":"e_1_2_1_55_1","volume-title":"Identifying potential association on gene-disease network via dual hypergraph regularized least squares. BMC genomics 22","author":"Yang Hongpeng","year":"2021","unstructured":"Hongpeng Yang, Yijie Ding, Jijun Tang, and Fei Guo. 2021. Identifying potential association on gene-disease network via dual hypergraph regularized least squares. BMC genomics 22 (2021), 1--16."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00083"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of The Web Conference","author":"Song Hyungseok","year":"2020","unstructured":"Se-eun Yoon, Hyungseok Song, Kijung Shin, and Yung Yi. 2020. How much and when do we need higher-order information in hypergraphs? a case study on hyperedge prediction. In Proceedings of The Web Conference 2020. 2627--2633."},{"key":"e_1_2_1_59_1","volume-title":"Database Systems for Advanced Applications: 25th International Conference, DASFAA 2020, Jeju, South Korea, September 24--27, 2020, Proceedings, Part II 25","author":"Yu Michael","year":"2020","unstructured":"Michael Yu, Lu Qin, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2020. Aot: Pushing the efficiency boundary of main-memory triangle listing. In Database Systems for Advanced Applications: 25th International Conference, DASFAA 2020, Jeju, South Korea, September 24--27, 2020, Proceedings, Part II 25. Springer, 516--533."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626753"},{"key":"e_1_2_1_61_1","volume-title":"Efficiently Counting Triangles for Hypergraph Streams by Reservoir-Based Sampling","author":"Zhang Lingling","year":"2023","unstructured":"Lingling Zhang, Zhiwei Zhang, Guoren Wang, Ye Yuan, and Kangfei Zhao. 2023. Efficiently Counting Triangles for Hypergraph Streams by Reservoir-Based Sampling. IEEE Transactions on Knowledge and Data Engineering (2023)."},{"key":"e_1_2_1_62_1","volume-title":"Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems 19","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 19 (2006)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3712221.3712238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:57:49Z","timestamp":1744052269000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3712221.3712238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["10.14778\/3712221.3712238"],"URL":"https:\/\/doi.org\/10.14778\/3712221.3712238","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,11]]},"assertion":[{"value":"2025-04-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}