{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:40:19Z","timestamp":1756485619904,"version":"3.44.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p>\n            Truss decomposition is a fundamental approach in graph theory that focuses on uncovering cohesive subgraphs within networks. However, many networks involve groupwise rather than pairwise relationships and are often represented as hypergraphs. Modeling and capturing\n            <jats:italic toggle=\"yes\">k-truss<\/jats:italic>\n            in hypergraphs is essential for uncovering tight-knit relationships in such multi-relational networks. In this paper, we tackle the problem of truss decomposition in hypergraph. A\n            <jats:italic toggle=\"yes\">hyper k-truss<\/jats:italic>\n            is a subgraph in which each node is part of at least k hyper-triangles. We first introduce a framework for hyper-truss decomposition and determine that the most time-consuming component is counting hyper-triangles. To count all hyper-triangles efficiently, we propose an edge-iterator algorithm. To further reduce redundant computations, we present an improved algorithm that combines edge-iterator and node-iterator techniques to prune non-promising nodes. Next, to handle common nodes in hypergraphs, we develop a novel prefix forest technique to encode all hyperedges and count triangles within this prefix forest. We also propose several optimization strategies that reorder nodes and hyperedges to improve work balancing. Finally, we conduct extensive experiments on real-world hypergraph datasets, demonstrating the efficiency and effectiveness of our algorithms.\n          <\/jats:p>","DOI":"10.14778\/3734839.3734854","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:06Z","timestamp":1756483266000},"page":"2185-2197","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Truss Decomposition in Hypergraphs"],"prefix":"10.14778","volume":"18","author":[{"given":"Hongchao","family":"Qin","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guang","family":"Zeng","sequence":"additional","affiliation":[{"name":"Ant Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longlong","family":"Lin","sequence":"additional","affiliation":[{"name":"Southwest University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Seher Acer Abdurrahman Yasar Sivasankaran Rajamanickam Michael M. Wolf and \u00dcmit V. \u00c7ataly\u00fcrek. 2019. Scalable Triangle Counting on Distributed-Memory Systems. In HPEC. 1\u20135.","DOI":"10.1109\/HPEC.2019.8916302"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598582"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3219096"},{"key":"e_1_2_1_5_1","article-title":"Finding Subgraphs with Maximum Total Density and Limited Overlap in Weighted Hypergraphs","volume":"18","author":"Balalau Oana","year":"2024","unstructured":"Oana Balalau, Francesco Bonchi, T.-H. Hubert Chan, Francesco Gullo, Mauro Sozio, and Hao Xie. 2024. Finding Subgraphs with Maximum Total Density and Limited Overlap in Weighted Hypergraphs. ACM Trans. Knowl. Discov. Data 18, 4 (2024), 95:1\u201395:21.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2015.1037030"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Francesco Bonchi Francesco Gullo Andreas Kaltenbrunner and Yana Volkovich. 2014. Core decomposition of uncertain graphs. In KDD. 1316\u20131325.","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Francesco Bonchi Arijit Khan and Lorenzo Severini. 2019. Distance-generalized Core Decomposition. In SIGMOD. 1006\u20131023.","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-00080-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-023-00956-2"},{"key":"e_1_2_1_11_1","first-page":"49","article-title":"A Method for Constructing Open-Domain Chinese Entity Hypernym Hierarchical Structure","volume":"15","author":"Cai Hongbo","year":"2017","unstructured":"Hongbo Cai, Hong Chen, and ShenLiu. 2017. A Method for Constructing Open-Domain Chinese Entity Hypernym Hierarchical Structure. ZTE Communications 15, 1 (2017), 49\u201354.","journal-title":"ZTE Communications"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Lijun Chang and Lu Qin. 2019. Cohesive Subgraph Computation Over Large Sparse Graphs. In ICDE. 2068\u20132071.","DOI":"10.1109\/ICDE.2019.00241"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3137955"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Qiangqiang Dai Rong-Hua Li Lu Qin Guoren Wang Weihua Yang Zhiwei Zhang and Ye Yuan. 2021. Scaling Up Distance-generalized Core Decomposition. In CIKM. 312\u2013321.","DOI":"10.1145\/3459637.3482294"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Kasimir Gabert Ali Pinar and \u00dcmit V. \u00c7ataly\u00fcrek. 2021. A Unifying Framework to Identify Dense Subgraphs on Streams: Graph Nuclei to Hypergraph Cores. In WSDM. 689\u2013697.","DOI":"10.1145\/3437963.3441790"},{"key":"e_1_2_1_16_1","volume-title":"HPEC","author":"Ghosh Sayan","year":"2020","unstructured":"Sayan Ghosh and Mahantesh Halappanavar. 2020. TriC: Distributed-memory Triangle Counting by Exploiting the Graph Structure. In HPEC 2020. 1\u20136."},{"key":"e_1_2_1_17_1","volume-title":"SIGMOD '21","author":"Gou Xiangyang","year":"2021","unstructured":"Xiangyang Gou and Lei Zou. 2021. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. In SIGMOD '21. 645\u2013657."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1226"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Loc Hoang Vishwesh Jatala Xuhao Chen Udit Agarwal Roshan Dathathri Gurbinder Gill and Keshav Pingali. 2019. DistTC: High Performance Distributed Triangle Counting. In HPEC. 1\u20137.","DOI":"10.1109\/HPEC.2019.8916438"},{"key":"e_1_2_1_20_1","volume-title":"Accelerating Triangle Counting on GPU. In SIGMOD '21","author":"Hu Lin","year":"2021","unstructured":"Lin Hu, Lei Zou, and Yu Liu. 2021. Accelerating Triangle Counting on GPU. In SIGMOD '21. 736\u2013748."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2023.3236669"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Xin Huang Hong Cheng Lu Qin Wentao Tian and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In SIGMOD. 1311\u20131322.","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_24_1","volume-title":"APPROX\/RANDOM","volume":"207","author":"Jayaram Rajesh","year":"2021","unstructured":"Rajesh Jayaram and John Kallaugher. 2021. An Optimal Algorithm for Triangle Counting in the Stream. In APPROX\/RANDOM 2021, Vol. 207. 11:1\u201311:11."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Dahee Kim Junghoon Kim Sungsu Lim and Hyun Ji Jeong. 2023. Exploring Cohesive Subgraphs in Hypergraphs: The (k g)-core Approach. In CIKM. 4013\u20134017.","DOI":"10.1145\/3583780.3615275"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"1491","DOI":"10.1016\/j.jcta.2013.04.009","article-title":"Hypergraph Ramsey numbers: Triangles versus cliques","volume":"120","author":"Kostochka Alexandr V.","year":"2013","unstructured":"Alexandr V. Kostochka, Dhruv Mubayi, and Jacques Verstra\u00ebte. 2013. Hypergraph Ramsey numbers: Triangles versus cliques. J. Comb. Theory, Ser. A 120, 7 (2013), 1491\u20131507.","journal-title":"J. Comb. Theory, Ser. A"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_28_1","volume-title":"Xiaokui Xiao, Nong Xiao, and Zibin Zheng.","author":"Li Rong-Hua","year":"2018","unstructured":"Rong-Hua Li, Lu Qin, Fanghua Ye, Jeffrey Xu Yu, Xiaokui Xiao, Nong Xiao, and Zibin Zheng. 2018. Skyline Community Search in Multi-valued Networks. In SIGMOD. 457\u2013472."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529340"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3033829"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_34_1","first-page":"707","article-title":"Exploring Truss Maintenance in Fully Dynamic Graphs: A Mixed Structure-Based Approach","volume":"72","author":"Luo Qi","year":"2023","unstructured":"Qi Luo, Dongxiao Yu, Xiuzhen Cheng, Hao Sheng, and Weifeng Lyu. 2023. Exploring Truss Maintenance in Fully Dynamic Graphs: A Mixed Structure-Based Approach. IEEE Trans. Computers 72, 3 (2023), 707\u2013718.","journal-title":"IEEE Trans. Computers"},{"key":"e_1_2_1_35_1","volume-title":"Triangle and Four Cycle Counting in the Data Stream Model. In PODS","author":"McGregor Andrew","year":"2020","unstructured":"Andrew McGregor and Sofya Vorotnikova. 2020. Triangle and Four Cycle Counting in the Data Stream Model. In PODS 2020. 445\u2013456."},{"key":"e_1_2_1_36_1","volume-title":"Elements of algebraic topology","author":"Munkres James R","unstructured":"James R Munkres. 2018. Elements of algebraic topology. CRC press."},{"key":"e_1_2_1_37_1","volume-title":"Triangle-Free Subgraphs of Hypergraphs. Graphs and Combinatorics","author":"Nie Jiaxi","year":"2021","unstructured":"Jiaxi Nie, Sam Spiro, and Jacques Verstra\u00ebte. 2021. Triangle-Free Subgraphs of Hypergraphs. Graphs and Combinatorics (2021), 1\u201316."},{"key":"e_1_2_1_38_1","volume-title":"HPCC\/SmartCity\/DSS","author":"Ouyang Zhiyou","year":"2019","unstructured":"Zhiyou Ouyang, Shanni Wu, Tongtong Zhao, Dong Yue, and Tengfei Zhang. 2019. Memory-Efficient GPU-Based Exact and Parallel Triangle Counting in Large Graphs. In HPCC\/SmartCity\/DSS 2019. 2195\u20132199."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3064892"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Thomas Schank and Dorothea Wagner. 2005. Finding Counting and Listing All Triangles in Large Graphs an Experimental Study. In Experimental and Efficient Algorithms. 606\u2013609.","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_42_1","article-title":"CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams","volume":"15","author":"Shin Kijung","year":"2021","unstructured":"Kijung Shin, Euiwoong Lee, Jinoh Oh, Mohammad Hammoud, and Christos Faloutsos. 2021. CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams. ACM Trans. Knowl. Discov. Data 15, 3 (2021), 38:1\u201338:30.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_2_1_43_1","first-page":"53","article-title":"Community Discovery with Location-Interaction Disparity in Mobile Social Networks","volume":"13","author":"Song Guojie","year":"2015","unstructured":"Guojie Song, Ping Lu, Wei Wei, and Danmeng Liu. 2015. Community Discovery with Location-Interaction Disparity in Mobile Social Networks. ZTE Communications 13, 2 (2015), 53\u201361.","journal-title":"ZTE Communications"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3040762"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523214"},{"key":"e_1_2_1_46_1","first-page":"2","volume-title":"Proc. ACM Manag. Data 1","author":"Sun Zitan","year":"2023","unstructured":"Zitan Sun, Xin Huang, Qing Liu, and Jianliang Xu. 2023. Efficient Star-based Truss Maintenance on Dynamic Graphs. Proc. ACM Manag. Data 1, 2 (2023), 133:1\u2013133:26."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598592"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_49_1","volume-title":"Efficient Bitruss Decomposition for Large-scale Bipartite Graphs","author":"Wang Kai","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2020. Efficient Bitruss Decomposition for Large-scale Bipartite Graphs. In ICDE. IEEE, 661\u2013672."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Xinzhou Wang Yinjia Chen Zhiwei Zhang Pengpeng Qiao and Guoren Wang. 2022. Efficient Truss Computation for Large Hypergraphs. In WISE. 290\u2013305.","DOI":"10.1007\/978-3-031-20891-1_21"},{"key":"e_1_2_1_51_1","unstructured":"Michael M. Wolf Mehmet Deveci Jonathan W. Berry Simon D. Hammond and Sivasankaran Rajamanickam. 2017. Fast linear algebra-based triangle counting with KokkosKernels. In HPEC. 1\u20137."},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Bohua Yang Dong Wen Lu Qin Ying Zhang Lijun Chang and Rong-Hua Li. 2019. Index-Based Optimal Algorithm for Computing K-Cores in Large Uncertain Graphs. In ICDE. 64\u201375.","DOI":"10.1109\/ICDE.2019.00015"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3093240"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3239409"},{"key":"e_1_2_1_55_1","first-page":"3","volume-title":"Proc. ACM Manag. Data 1","author":"Yu Kaiqiang","year":"2023","unstructured":"Kaiqiang Yu and Cheng Long. 2023. Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach. Proc. ACM Manag. Data 1, 3 (2023), 211:1\u2013211:26."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3311398"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2020.02.077"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3236335"},{"key":"e_1_2_1_59_1","volume-title":"Weifa Liang, Baichen Chen, and Jianxin Li.","author":"Zhou Rui","year":"2012","unstructured":"Rui Zhou, Chengfei Liu, Jeffrey Xu Yu, Weifa Liang, Baichen Chen, and Jianxin Li. 2012. Finding maximal k-edge-connected subgraphs from a large graph. In EDBT. 480\u2013491."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3734839.3734854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:02:04Z","timestamp":1756483324000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3734839.3734854"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":59,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.14778\/3734839.3734854"],"URL":"https:\/\/doi.org\/10.14778\/3734839.3734854","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,3]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}