{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T07:31:09Z","timestamp":1794036669035,"version":"4.8.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["ECS No. 25201221"],"award-info":[{"award-number":["ECS No. 25201221"]}]},{"DOI":"10.13039\/100015803","name":"Tencent","doi-asserted-by":"publisher","award":["P0039546"],"award-info":[{"award-number":["P0039546"]}],"id":[{"id":"10.13039\/100015803","id-type":"DOI","asserted-by":"publisher"}]},{"name":"RGC Direct Allocation Grant","award":["P0036831"],"award-info":[{"award-number":["P0036831"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62202404"],"award-info":[{"award-number":["62202404"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001348","name":"A*STAR","doi-asserted-by":"crossref","award":["A19E3b0099"],"award-info":[{"award-number":["A19E3b0099"]}],"id":[{"id":"10.13039\/501100001348","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Hypergraphs are an omnipresent data structure used to represent high-order interactions among entities. Given a hypergraph H wherein nodes are associated with attributes, attributed hypergraph clustering (AHC) aims to partition the nodes in H into k disjoint clusters, such that intra-cluster nodes are closely connected and share similar attributes, while inter-cluster nodes are far apart and dissimilar. It is highly challenging to capture multi-hop connections via nodes or attributes on large attributed hypergraphs for accurate clustering. Existing AHC solutions suffer from issues of prohibitive computational costs, sub-par clustering quality, or both. In this paper, we present AHCKA, an efficient approach to AHC, which achieves state-of-the-art result quality via several algorithmic designs. Under the hood, AHCKA includes three key components: (i) a carefully-crafted K-nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, (ii) a joint hypergraph random walk model to devise an effective optimization objective towards AHC, and (iii) a highly efficient solver with speedup techniques for the problem optimization. Extensive experiments, comparing AHCKA against 15 baselines over 8 real attributed hypergraphs, reveal that AHCKA is superior to existing competitors in terms of clustering quality, while often being up to orders of magnitude faster.<\/jats:p>","DOI":"10.1145\/3589261","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T16:26:45Z","timestamp":1687278405000},"page":"1-23","source":"Crossref","is-referenced-by-count":19,"title":["Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4476-016X","authenticated-orcid":false,"given":"Yiran","family":"Li","sequence":"first","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7284-3096","authenticated-orcid":false,"given":"Renchi","family":"Yang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0465-1551","authenticated-orcid":false,"given":"Jieming","family":"Shi","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"396","article-title":"A Local Algorithm for Finding Well-Connected Clusters","volume":"28","author":"Zhu Zeyuan Allen","year":"2013","unstructured":"Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab Mirrokni. 2013. A Local Algorithm for Finding Well-Connected Clusters. In ICML, Vol. 28. 396--404.","journal-title":"ICML"},{"key":"e_1_2_2_2_1","volume-title":"Graph regularized nonnegative matrix factorization for data representation","author":"Cai Deng","year":"2010","unstructured":"Deng Cai, Xiaofei He, Jiawei Han, and Thomas S Huang. 2010. Graph regularized nonnegative matrix factorization for data representation. IEEE transactions on pattern analysis and machine intelligence, Vol. 33, 8 (2010), 1548--1560."},{"key":"e_1_2_2_3_1","first-page":"1","article-title":"Hypergraph-Structured Autoencoder for Unsupervised and Semisupervised Classification of Hyperspectral Image. IEEE Geosci","volume":"19","author":"Cai Yaoming","year":"2022","unstructured":"Yaoming Cai, Zijia Zhang, Zhihua Cai, Xiaobo Liu, and Xinwei Jiang. 2022. Hypergraph-Structured Autoencoder for Unsupervised and Semisupervised Classification of Hyperspectral Image. IEEE Geosci. Remote. Sens. Lett., Vol. 19 (2022), 1--5.","journal-title":"Remote. Sens. Lett."},{"key":"e_1_2_2_4_1","volume-title":"Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators. arXiv:1804.11128 [cs]","author":"Hubert Chan T.-H.","year":"2018","unstructured":"T.-H. Hubert Chan and Zhibin Liang. 2018. Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators. arXiv:1804.11128 [cs] (2018)."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921632.1921638"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-017-0578-x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Barakeel Fanseu Kamhoua Lin Zhang Kaili Ma James Cheng Bo Li and Bo Han. 2021. HyperGraph Convolution Based Attributed HyperGraph Clustering. In CIKM. 453--463.","DOI":"10.1145\/3459637.3482437"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty570"},{"key":"e_1_2_2_9_1","first-page":"1","article-title":"Parallel Flow-Based Hypergraph Partitioning","volume":"233","author":"Gottesb\u00fcren Lars","year":"2022","unstructured":"Lars Gottesb\u00fcren, Tobias Heuer, and Peter Sanders. 2022. Parallel Flow-Based Hypergraph Partitioning. In SEA, Vol. 233. 5:1--5:21.","journal-title":"SEA"},{"key":"e_1_2_2_10_1","first-page":"3887","article-title":"Accelerating Large-Scale Inference with Anisotropic Vector Quantization","volume":"119","author":"Guo Ruiqi","year":"2020","unstructured":"Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In ICML, Vol. 119. 3887--3896.","journal-title":"ICML"},{"key":"e_1_2_2_11_1","volume-title":"Cheong Hee Park, and Haesun Park","author":"Hayashi Koby","year":"2020","unstructured":"Koby Hayashi, Sinan G. Aksoy, Cheong Hee Park, and Haesun Park. 2020. Hypergraph Random Walks, Laplacians, and Clustering. In CIKM. 495--504."},{"key":"e_1_2_2_12_1","volume-title":"NeurIPS","volume":"26","author":"Hein Matthias","year":"2013","unstructured":"Matthias Hein, Simon Setzer, Leonardo Jost, and Syama Sundar Rangapuram. 2013. The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited. In NeurIPS, Vol. 26."},{"key":"e_1_2_2_13_1","volume-title":"Yu","author":"Huang Ling","year":"2021","unstructured":"Ling Huang, Chang-Dong Wang, and Philip S. Yu. 2021. Higher Order Connection Enhanced Community Detection in Adversarial Multiview Networks. IEEE Transactions on Cybernetics (2021), 1--15."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Jinhong Jung Namyong Park Sael Lee and U Kang. 2017. BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart. In SIGMOD. 789--804.","DOI":"10.1145\/3035918.3035950"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_2_18_1","volume-title":"NeurIPS","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. In NeurIPS, Vol. 24."},{"key":"e_1_2_2_19_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR."},{"key":"e_1_2_2_20_1","volume-title":"Hypergraph Clustering: A Modularity Maximization Approach. arXiv:1812.10869 [cs, stat]","author":"Kumar Tarun","year":"2018","unstructured":"Tarun Kumar, Sankaran Vaidyanathan, Harini Ananthapadmanabhan, Srinivasan Parthasarathy, and Balaraman Ravindran. 2018. Hypergraph Clustering: A Modularity Maximization Approach. arXiv:1812.10869 [cs, stat] (2018)."},{"key":"e_1_2_2_21_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_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_23_1","volume-title":"From Usenet to CoWebs: interacting with social information spaces","author":"Lueg Christopher","unstructured":"Christopher Lueg. 2003. From Usenet to CoWebs: interacting with social information spaces. Springer Science & Business Media."},{"key":"e_1_2_2_24_1","unstructured":"Jianmo Ni Jiacheng Li and Julian McAuley. 2019. Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In EMNLP-IJCNLP. 188--197."},{"key":"e_1_2_2_25_1","volume-title":"2017 IEEE International Conference on Big Data (Big Data). 756--765","author":"Park Haekyu","unstructured":"Haekyu Park, Jinhong Jung, and U. Kang. 2017. A comparative study of matrix factorization and random walk with restart in recommender systems. In 2017 IEEE International Conference on Big Data (Big Data). 756--765."},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Matthew J. Rattigan Marc Maier and David Jensen. 2007. Graph Clustering with Network Structure Indices. In ICML. 783--790.","DOI":"10.1145\/1273496.1273595"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081080290011692"},{"key":"e_1_2_2_28_1","volume-title":"Numerical Methods for Large Eigenvalue Problems. Algorithms and Architectures for Advanced Scientific Computing","author":"Y SAAD.","year":"1992","unstructured":"Y SAAD. 1992. Numerical Methods for Large Eigenvalue Problems. Algorithms and Architectures for Advanced Scientific Computing (1992)."},{"key":"e_1_2_2_29_1","volume-title":"High-Quality Hypergraph Partitioning. ACM J. Exp. Algorithmics","author":"Schlag Sebastian","year":"2022","unstructured":"Sebastian Schlag, Tobias Heuer, Lars Gottesb\u00fcren, Yaroslav Akhremtsev, Christian Schulz, and Peter Sanders. 2022. High-Quality Hypergraph Partitioning. ACM J. Exp. Algorithmics (2022)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_2_31_1","volume-title":"Bo-June Paul Hsu, and Kuansan Wang","author":"Sinha Arnab","year":"2015","unstructured":"Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Paul Hsu, and Kuansan Wang. 2015. An Overview of Microsoft Academic Service (MAS) and Applications. In WWW. 243--246."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098098"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Yuuki Takai Atsushi Miyauchi Masahiro Ikeda and Yuichi Yoshida. 2020. Hypergraph Clustering Based on PageRank. In KDD. 1970--1978.","DOI":"10.1145\/3394486.3403248"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Hanghang Tong Christos Faloutsos and Jia-yu Pan. 2006. Fast Random Walk with Restart and Its Applications. In ICDM. 613--622.","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1321048"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377378"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1363388"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Lei Wu Yufeng Hu Yajin Zhou Haoyu Wang Xiapu Luo Zhi Wang Fan Zhang and Kui Ren. 2021. Towards Understanding and Demystifying Bitcoin Mixing Services. In WWW. 33--44.","DOI":"10.1145\/3442381.3449880"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/JBHI.2019.2948456"},{"key":"e_1_2_2_40_1","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."},{"key":"e_1_2_2_41_1","unstructured":"Naganand Yadati Madhav Nimishakavi Prateek Yadav Vikram Nitin Anand Louis and Partha Talukdar. 2019. HyperGCN: a new method of training graph convolutional networks on hypergraphs. In NeurIPS. Number 135. 1511--1522."},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Renchi Yang Jieming Shi Yin Yang Keke Huang Shiqi Zhang and Xiaokui Xiao. 2021. Effective and Scalable Clustering on Massive Attributed Graphs. In WWW. 3675--3687.","DOI":"10.1145\/3442381.3449875"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Tianbao Yang Rong Jin Yun Chi and Shenghuo Zhu. 2009. Combining Link and Content for Community Detection: A Discriminative Approach. In KDD. 927--936.","DOI":"10.1145\/1557019.1557120"},{"key":"e_1_2_2_44_1","volume-title":"Yu and Jianbo Shi","author":"Stella","year":"2003","unstructured":"Stella X. Yu and Jianbo Shi. 2003. Multiclass Spectral Clustering. In ICCV. 313."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077466"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Xiaotong Zhang Han Liu Qimai Li and Xiao-Ming Wu. 2019. Attributed Graph Clustering via Adaptive Graph Convolution. In IJCAI. 4327--4333.","DOI":"10.24963\/ijcai.2019\/601"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/7503.003.0205"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687709"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.41"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589261","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T13:48:54Z","timestamp":1750168134000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589261"],"URL":"https:\/\/doi.org\/10.1145\/3589261","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}