结合多尺度注意力和动态构建的非均匀超图聚类模型

doi:10.3778/j.issn.1002-8331.2309-0115

摘要/Abstract

摘要： 单个较大非均匀超图聚类旨在将非均匀超图包含的节点划分为多个簇，使得同一簇内的节点更相似，而不同簇中的节点更不相似，具有广泛的应用场景。目前，最优的基于超图神经网络的非均匀超图聚类方法CIAH（co-cluster the interactions via attentive hypergraph neural network）虽然较好地学习了非均匀超图的关系信息，但仍存在两点不足：（1）对于局部关系信息的挖掘不足；（2）忽略了隐藏的高阶关系。因此，提出一种基于多尺度注意力和动态超图构建的非均匀超图聚类模型MADC（non-uniform hypergraph clustering combining multi-scale attention and dynamic construction）。一方面，使用多尺度注意力充分学习了超边中节点与节点之间的局部关系信息；另一方面，采用动态构建挖掘隐藏的高阶关系，进一步丰富了超图特征嵌入。真实数据集上的大量实验结果验证了MADC模型在非均匀超图聚类上的聚类准确率（accuracy，ACC）、标准互信息（normalized mutual information，NMI）和调整兰德指数（adjusted Rand index，ARI）均优于CIAH等所有Baseline方法。

关键词: 非均匀超图, 超图聚类, 超图神经网络, 多尺度注意力

Abstract: A single large non-uniform hypergraph clustering is designed to divide the nodes contained in non-uniform hypergraphs into multiple clusters, so that the nodes in the same cluster are more similar, while the nodes in different clusters are less similar, which has a wide range of application scenarios. At present, the optimal hypergraph clustering method based on hypergraph neural network is CIAH (co-cluster the interactions via attentive hypergraph neural network). Although it can learn the relationship information of non-uniform hypergraphs better, there are still two deficiencies: (1) local relation information mining is insufficient; (2) the hidden higher-order relationship is ignored. Therefore, a non-uniform hypergraph clustering model based on multi-scale attention and dynamic hypergraph construction MADC (non-uniform hypergraph clustering combining multi-scale attention and dynamic construction) is proposed. On the one hand, multi-scale attention is used to fully learn the local relation information between nodes in the hyperedge. On the other hand, dynamic construction is used to mine hidden higher-order relationships, which further enriches hypergraph feature embedding. Extensive experiments on real datasets demonstrate that the clustering accuracy (ACC), normalized mutual information (NMI) and adjusted Rand index (ARI) of MADC model on non-uniform hypergraph clustering are better than all Baseline methods such as CIAH.

Key words: non-uniform hypergraph, hypergraph clustering, hypergraph neural network, multi-scale attention

朱峰冉, 王慧颖, 林晓丽, 李全鑫, 庞俊. 结合多尺度注意力和动态构建的非均匀超图聚类模型[J]. 计算机工程与应用, 2025, 61(2): 200-207.

ZHU Fengran, WANG Huiying, LIN Xiaoli, LI Quanxin, PANG Jun. Non-Uniform Hypergraph Clustering Model Combining Multi-Scale Attention and Dynamic Construction[J]. Computer Engineering and Applications, 2025, 61(2): 200-207.

参考文献

[1] ZHU C J, LIU Q Q, BI J B. Communication efficient distributed hypergraph clustering[C]//Proceedings of the 44th International Conference on Research and Development in Information Retrieval, Virtual Event, 2021: 2131-2135.
[2] YANG T C, ZHANG L H, YANG C, et al. Hypergraph clustering network for interaction data[J]. IEEE Data Engineering Bulletin, 2022, 45(4): 88-101.
[3] 喻莉敏. 基于超图聚类挖掘微生物高阶模块的研究[D]. 武汉: 华中师范大学, 2020.
YU L M. Mining microbial high-order modules based on hypergraph clustering[D]. Wuhan: Central China Normal University, 2020.
[4] 胡秉德, 王新根, 王新宇, 等. 超图学习综述: 算法分类与应用分析[J]. 软件学报, 2022, 33(2): 498-523.
HU B D, WANG X G, WANG X Y, et al. Survey of hypergraph learning: method and application analysis[J]. Journal of Software, 2022, 33(2): 498-523.
[5] ZHOU D Y, HUANG J Y, BERNHARD S. Learning with hypergraphs: clustering, classification, and embedding[C]//Proceedings of the 20th Annual Conference on Neural Information Processing Systems, 2006: 1601-1608.
[6] YANG T C, YANG C, ZHANG L H, et al. Co-clustering interactions via attentive hypergraph neural network[C]//Proceedings of the 45th International Conference on Research and Development in Information Retrieval, 2022: 859-869.
[7] JIANG J, WEI Y, FENG Y, et al. Dynamic hypergraph neural networks[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019: 2635-2641.
[8] YANG H Z, GAO Q X, XIA W, et al. Multiview spectral clustering with bipartite graph[J]. IEEE Transactions on Image Processing, 2022, 31: 3591-3605.
[9] DALL’AMICO L, COUILLET R, TREMBLAY N. A unified framework for spectral clustering in sparse graphs[J]. Journal of Machine Learning Research, 2021, 22(1): 9859-9914.
[10] 黄展鹏, 吴杰康, 易法令. 自适应图融合的缺失多视图聚类算法[J]. 计算机工程与应用, 2023, 59(9): 176-181.
HUANG Z P, WU J K, YI F L. Incomplete multi-view clustering algorithm with adaptive graph fusion[J]. Computer Engineering and Applications, 2023, 59(9): 176-181.
[11] 龚卫华, 沈松, 裴小兵, 等. 基于位置的社交网络中双重异质社区的聚类与关联方法[J]. 计算机学报, 2020, 43(10): 1909-1923.
GONG W H, SHEN S, PEI X B, et al. Clustering and associating method of dual heterogeneous communities in location based social networks[J]. Chinese Journal of Computers, 2020, 43(10): 1909-1923.
[12] 张天成, 田雪, 孙相会, 等. 知识图谱嵌入技术研究综述[J]. 软件学报, 2023, 34(1): 277-311.
ZHANG T C, TIAN X, SUN X H, et al. Overview on knowledge graph embedding technology research[J]. Journal of Software, 2023, 34(1): 277-311.
[13] 陈子睿, 王鑫, 王晨旭, 等. 面向时间感知的知识超图链接预测[J]. 软件学报, 2023, 34(10): 4533-4547.
CHEN Z R, WANG X, WANG C X, et al. Towards time-aware knowledge hypergraph link prediction[J]. Journal of Software, 2023, 34(10): 4533-4547.
[14] WANG C, PAN S R, HU R Q, et al. Attributed graph clustering: a deep attentional embedding approach[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019: 3670-3676.
[15] HU Z N, DONG Y X, WANG K S, et al. Heterogeneous graph transformer[C]//Proceedings of The Web Conference 2020, 2020: 2704-2710.
[16] 腊志垚, 钱育蓉, 冷洪勇, 等. 基于随机游走的图嵌入研究综述[J]. 计算机工程与应用, 2022, 58(13): 1-13.
LA Z Y, QIAN Y R, LENG H Y, et al. Overview of research on graph embedding based on random walk[J]. Computer Engineering and Applications, 2022, 58(13): 1-13.
[17] FENG Y F, YOU H X, ZHANG Z Z, et al. Hypergraph neural networks[C]//Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019: 3558-3565.
[18] WU C H, WU F Z, GE S Y, et al. Neural news recommendation with multi-head self-attention[C]//Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, 2019: 6388-6393.
[19] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 5998-6008.
[20] 庞俊, 刘小琪, 谷峪, 等. 基于多粒度注意力网络的知识超图链接预测[J]. 软件学报, 2023, 34(3): 1259-1276.
PANG J, LIU X Q, GU Y, et al. Knowledge hypergraph link prediction based on multi-granular attention network[J]. Journal of Software, 2023, 34(3): 1259-1276.
[21] BEER A, DRAGANOV A, HOHMA E, et al. Connecting the dots-density-connectivity distance unifies dbscan, k-center and spectral clustering[C]//Proceedings of the 29th Conference on Knowledge Discovery and Data Mining, 2023: 80-92.
[22] FARD M M, THONET T, GAUSSIER é. Deep K-means: jointly clustering with K-means and learning representations[J]. Pattern Recognition Letters, 2020, 138: 185-192.
[23] GROVER A, LESKOVEC J. node2vec: scalable feature learning for networks[C]//Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, 2016: 855-864.
[24] HU Y P, LI X K, WANG Y J, et al. Adaptive hypergraph auto-encoder for relational data clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(3): 2231-2242.