结构缺失的图级聚类网络

《Neural Networks》：Structure-Missing Graph-Level Clustering Network

针对图级聚类中缺失关系导致的结构信息失真问题，提出SMGCN方法，包含低秩矩阵补全结构增强模块、基于匈牙利算法的簇匹配锚点定位机制及联合对比优化，有效提升缺失结构下的聚类性能。

　　

胡天宇|韩仁达|刘茂|陈静|谢霞

海南大学计算机科学与技术学院，海口，570000，海南，中国

摘要

图级聚类旨在根据图之间的共享结构特征或语义相似性将图划分为不同的簇。然而，现有的图级聚类方法通常假设输入图的结构是完整的，忽略了现实世界场景中常见的缺失关系问题。这些未建模的缺失关系会在图表示学习过程中导致结构信息失真，从而显著降低聚类性能。为此，我们提出了一种新的方法——结构缺失图级聚类网络（SMGCN），该方法包括结构增强模块LR-SEA、锚点定位机制和联合对比优化。具体来说，我们首先基于低秩矩阵补全输出增强图，然后使用匈牙利算法进行簇匹配以获得锚点，接着强制相同的聚类图在嵌入空间中收敛到相应的锚点。据我们所知，这是首次提出处理缺失关系的图级聚类任务，并且通过五个基准数据集的实验证明了我们方法的优越性，与现有最先进方法相比。我们的源代码可在以下链接获取：https://github.com/MrHuSN/SMGCN。

引言

图级聚类的目的是量化图之间的相似性，并将具有相似拓扑和属性特征的图分类到同一个簇中，而无需标签（Liang, Liu, Zhou, Tu, Wen, Yang, Dong, Liu, 2023a; Liang, Meng, Li, Liu, Wang, Zhou, Liu, He, 2024）。它广泛应用于包含复杂群体结构信息的领域，如语义网络分析（Wang, Dong, Jin, Li, Wang, Dang, 2023; Wang, Wang, He, Yu, Li, Wang, Dang, Jin, 2025b）、金融风险预测（Li, 2023）和社交网络（Souza et al., 2013）。

为了实现有效的无监督划分，人们进行了大量研究以提高表示的鲁棒性和计算效率。（Gai and Liu, 2025）通过将可微分的ONMF与稀疏自编码器结合实现了可解释的聚类。为了减轻噪声，（Yang et al., 2022b）在正交概念分解中使用了基于相关度的度量来增强优化鲁棒性。在涉及高维或复杂多源数据的场景中，谱方法和多视图方法已成为主流。（Yang et al., 2025）提出了一个可扩展的min-max框架来解决多视图谱聚类问题，有效处理大规模数据集。（Yang et al., 2022c）利用谱嵌入加速多视图聚类过程，同时平衡速度和准确性（Li et al., 2026）。此外，（Wang and Liu, 2025）探索了双空间拓扑同构来最大化预测多样性，为跨领域的无监督适应和特征对齐提供了新的见解。

在图分析的具体背景下，深度学习（Gao, Zhou, Gu, Wu, Liu, Zhou, Wang, 2025; Lv, Lv, Wang, Zhao, Tian, Zhou, Zeng, Wan, Liu, 2025; Wen, Gao, Li, Zhang, Zhang, Chen, 2025; Zhang, Luo, Zhong, Ma, Liu, Li, 2019）已经发展出有效编码拓扑结构的方法，为图级任务提供了新的解决方案。（Cai et al., 2024a）通过优化图级表示来提高聚类性能；（Liu, Liang, Hu, Yu, Liu, Meng, Tu, Zhou, Liu, 2023; Liu, Liang, Yu, Meng, Wang, Zhou, Liu, 2025; Liu, Yang, Wang, Su, 2024d）通过优化时间图级表示来提高性能；（Han, Yao, Zhang, Li, Xin, Lei, Li, Zhang, Du, & Tian, Li, Han, Hu, Li, Li, 2025）通过不同的感受野探索了节点和图之间的各种连接。此外，对比学习（Hu, Chen, Liu, Zhang, Liao, & Zheng, Ju, Gu, Chen, Sun, Qin, Liu, Luo, Zhang, 2023）也是研究的重点。

然而，上述方法通常遵循一个前提，即处理后的图数据结构是完整的。（Braun, Tyagi, Biernacki, 2021; Dong, Jin, Xiao, Xiao, Wang, Liu, Zhu, 2024）发现了这一问题并提出了处理节点缺失的解决方案，但他们忽略了图中可能存在的潜在连接（未观察到的边）。图级聚类任务需要在无标签数据中挖掘结构特征，因此缺失的边将导致无法表示真实网络，从而降低聚类性能。

为了解决上述问题，我们提出了一种名为结构缺失图级聚类网络（SMGCN）的新解决方案，该方案包括结构增强模块LR-SEA、锚点定位机制和联合对比优化。具体来说，首先通过最小化矩阵核范数和观测误差的加权和来恢复未观察到的潜在连接，从而构建包含潜在边的增强图结构。随后，基于原始图和增强图的图级特征进行K-means聚类。对于聚类结果，我们首先使用匈牙利算法（Kuhn, 1955）来解决最优关系。匈牙利算法是一种用于解决分配问题的匹配算法，可以找到最低成本或最高收益的分配方案。然后，我们根据簇匹配和质心距离选择锚点。为了优化聚类，我们提出了一个联合目标函数来构建原始图和增强图。我们的贡献总结如下：

1.

根据我们对现有工作的研究，这是第一个针对缺失关系的图级聚类任务，我们阐明了其作为缺失结构分支的重要性，并在这一领域提出了新的挑战。

2.

对于这个任务，我们提出了一个名为SMGCN的新聚类框架，它依赖于结构增强模块（LR-SEA）、锚点定位机制和联合对比优化的协调，旨在为这一领域提供一个参考范例。

3.

通过在五个基准数据集上的大量实验，证明了我们方法相对于现有最先进方法的优越性。

部分摘录

图级聚类

在传统解决方案中，基于相似性度量的方法包括图核类（Shervashidze, Schweitzer, Van Leeuwen, Mehlhorn, Borgwardt, 2011; Vishwanathan, Schraudolph, Kondor, Borgwardt, 2010）和图编辑距离类（Neuhaus and Bunke, 2007）。这些算法通过定义图之间的不同相似性指数来构建相似性矩阵。谱方法（Shi, Malik, 2000; Von Luxburg, 2007）利用拉普拉斯矩阵进行特征值分解。

低秩矩阵补全

在实际应用中，图邻接矩阵通常表现出低秩特性，这一现象在多个领域中被广泛观察到（Chen et al., 2021）。具体来说，当图具有社区结构或块结构时，它们的邻接矩阵可以近似为低秩矩阵的叠加（Holland et al., 1983）。在我们的图级聚类场景中，同一类别内的图通常具有相似的结构模式，这是低秩的基础。

方法论

在本节中，我们讨论了如何充分利用默认图数据的现有结构信息来实现更准确的图级聚类算法。结构缺失图级聚类网络（SMGCN）包括基于低秩矩阵补全的结构增强模块（LR-SEA）、锚点定位机制（簇匹配和锚点选择）和联合对比优化。

实验设置

在联合对比学习收敛后，我们以以下方式获得最终的聚类结果。所有缺失结构的图都被输入到训练好的模型中。首先，通过结构增强模块LR-SEA获得增强图，然后从增强视图中提取图级表示。这些表示使用我们提出的框架进行优化，使其既具有区分能力又对缺失结构具有鲁棒性，然后作为输入

消融实验

在本节中，我们首先讨论SMGCN每个模块的合作机制，然后分析超参数R对实验结果的影响，最后可视化我们方法的聚类结果。

结论

本文提出了一种新的结构缺失图级聚类网络（SMGCN），用于解决具有缺失关系的图级聚类问题。首先，引入了一个基于低秩矩阵补全的结构增强模块（LR-SEA），利用图结构的低秩特性来重建潜在边，从而减轻了缺失边引起的特征歧义。同时，采用了一种由簇中心引导的跨视图锚点协作机制

未引用的内容

算法1、图1和表10。

CRediT作者贡献声明

胡天宇：方法论、资金获取、形式分析、概念化。韩仁达：监督、项目管理、形式分析、数据整理、概念化。刘茂：监督、软件开发。陈静：可视化、监督。谢霞：监督、资源管理、项目管理、方法论、调查、资金获取、数据整理。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。