打破结构孤立：通过社区感知采样和结构熵的可扩展图聚类

# 打破结构隔离：基于社区感知采样与结构熵的可扩展图聚类  
**来源：** https://arxiv.org/html/2607.05469  

###### 摘要。  
无监督图聚类是发现大规模网络中潜在语义模式的基础技术。尽管图对比学习已展现出良好性能，现有方法在小批量训练过程中常遭受“结构隔离”问题，难以捕获表征全局拓扑分布的凝聚社区结构。为解决这些挑战，我们提出 **SCISE**——一个通过协同社区感知采样与约束结构熵来保持结构完整性的可扩展无监督图聚类框架。具体而言，我们首先引入结构熵社区约束算子（SECC），在受约束的解空间内优化结构信息，以减少社区碎片化并增强分区凝聚力。其次，为防止批训练中全局信息丢失，我们设计了一种社区感知采样扩展（CSampE）机制，将目标节点的社区上下文纳入采样批次，有效打破结构屏障并保持拓扑完整性。最后，我们开发了结构对比学习（StructCL）模块，基于批内结构相似性细化边权重，引导编码器在高阶结构空间中学习表示。在六个主流基准数据集上的大量实验表明，SCISE 显著优于现有最先进算法，消融研究和鲁棒性分析进一步验证了其在实际大规模图中的有效性和可靠性。  

**PVLDB 引用格式：** PVLDB, 19(1): XXX-XXX, 2026. doi:XX.XX/XXX.XX (https://doi.org/XX.XX/XXX.XX)  
†† 本文采用知识共享署名-非商业性-禁止演绎 4.0 国际许可协议。访问 https://creativecommons.org/licenses/by-nc-nd/4.0/ 可查看该许可协议副本。对于协议涵盖范围之外的任何使用，请发送邮件至 [email protected] (https://arxiv.org/html/2607.05469v1/mailto:[email protected]) 获取许可。版权归作者/所有者所有，出版权授予 VLDB 最终委员会。  

**PVLDB 可用性：** 源代码、数据和/或其他工件可在 https://github.com/SELGroup/SCISE 获取。  

---

## 1. 引言  

图结构数据已广泛应用于表示复杂关系信息，涵盖社交网络、引文网络和生物系统等多个领域（Hamilton et al., 2017 (https://arxiv.org/html/2607.05469#bib.bib13); Kipf and Welling, 2017 (https://arxiv.org/html/2607.05469#bib.bib30)）。作为网络分析的基本任务，无监督图聚类旨在将具有高拓扑和属性亲和力的节点划分为社区，无需依赖人工标注，从而揭示复杂网络中的潜在语义模式和结构主题（Fortunato, 2010 (https://arxiv.org/html/2607.05469#bib.bib31); Xie et al., 2016 (https://arxiv.org/html/2607.05469#bib.bib32)）。这一能力对于社区检测、定向推荐和异常发现等下游应用至关重要（Ying et al., 2018 (https://arxiv.org/html/2607.05469#bib.bib33); Akoglu et al., 2015 (https://arxiv.org/html/2607.05469#bib.bib34)）。随着图数据呈指数级增长以及人工标注成本高昂，开发有效且可扩展的无监督聚类框架对于从未标注的大规模关系数据中提取有意义的结构信息至关重要（Wu et al., 2020 (https://arxiv.org/html/2607.05469#bib.bib35); Veličković et al., 2018 (https://arxiv.org/html/2607.05469#bib.bib36)）。  

图 1：采样策略对比。(a) 随机采样：将社区碎片化到不同批次。(b) 局部采样：限于邻域上下文。(c) SCISE（我们的方法）：融入全局社区上下文，在小批量中保持结构完整性。

当前无监督图聚类的主流范式已转向将图神经网络（GNN）与图对比学习（GCL）相结合，以学习判别性语义嵌入（Bo et al., 2020 (https://arxiv.org/html/2607.05469#bib.bib38); Li et al., 2025 (https://arxiv.org/html/2607.05469#bib.bib39)）。通常，这些方法利用消息传递机制和一致性正则化来加强簇内节点间的特征相似性（Zhu et al., 2021 (https://arxiv.org/html/2607.05469#bib.bib40)）。然而，随着真实网络规模呈指数级增长，这些框架面临一个严峻瓶颈：计算可扩展性与结构完整性之间的权衡（Gao et al., 2018 (https://arxiv.org/html/2607.05469#bib.bib41); Hamilton et al., 2017 (https://arxiv.org/html/2607.05469#bib.bib13)）。为处理大规模图，现有方法主要通过多种随机采样策略采用小批量训练（Zeng et al., 2019 (https://arxiv.org/html/2607.05469#bib.bib52)）。尽管 GCL 在表示学习方面表现出色，但其在大规模数据上的有效性受到批操作引起的“结构隔离”问题的严重阻碍（Shi et al., 2024 (https://arxiv.org/html/2607.05469#bib.bib42)）。由于传统采样器主要关注局部邻域可达性，它们不可避免地切断了全局社区上下文，将同一语义簇中的节点隔离到不同的批次中。这一局限在图 1 (https://arxiv.org/html/2607.05469#S1.F1) 中直观展示，其中传统随机采样 (a) 和局部邻域采样 (b) 未能保持小批量内的社区连贯性。这种结构隔离从根本上削弱了全局拓扑感知，而当前技术路径的固有局限性进一步加剧了该问题：基于对比的框架（Liu et al., 2022a (https://arxiv.org/html/2607.05469#bib.bib2); Kulatilleke et al., 2025 (https://arxiv.org/html/2607.05469#bib.bib37); Yang et al., 2023b (https://arxiv.org/html/2607.05469#bib.bib3); Shen et al., 2023 (https://arxiv.org/html/2607.05469#bib.bib43)）通常缺乏弥补这种采样引起碎片化的机制，而结构感知方法（Sun et al., 2024 (https://arxiv.org/html/2607.05469#bib.bib6); Liu et al., 2023b (https://arxiv.org/html/2607.05469#bib.bib4); Tsitsulin et al., 2023 (https://arxiv.org/html/2607.05469#bib.bib5)）往往依赖有噪声、未精炼的图统计量。因此，全局拓扑意识的缺失使得模型难以捕获凝聚的社区结构，导致表示碎片化，无法反映底层的语义组织。

为解决上述挑战，我们提出 **SCISE**，一个通过社区感知采样与约束结构熵协同作用来保持结构完整性的可扩展无监督图聚类框架。SCISE 通过三个协同组件调和了计算可扩展性与社区凝聚力之间的固有矛盾。首先，我们引入结构熵社区约束算子（SECC）来显式量化和增强社区紧凑性。与传统的结构熵度量（在无标注场景下常导致过度划分）不同，SECC 在受目标社区数量约束的有界解空间内优化结构信息，使模型能保持最小熵，同时有效减少社区碎片化。其次，为应对小批量训练中固有的信息丢失，我们设计了社区感知采样扩展（CSampE）机制。通过在每次采样批次中识别并融入目标节点的全局社区上下文，CSampE 拆除了批次间的结构屏障，恢复了稳定优化所需的拓扑连续性。最后，我们开发了结构对比学习（StructCL）方法，引导编码器朝向更具判别性的表示空间。与依赖有噪声原始拓扑的传统范式不同，StructCL 基于批内节点间的潜在结构相似性来细化高阶边权重。这些精炼的亲和力作为结构指导，最大化相似节点间的一致性，最终产生高质量嵌入，并划分为最终簇。

为评估所提 SCISE 的有效性，我们在三个中等规模数据集（Photo, Computer, Pubmed）和三个大规模数据集（Ogbn-arxiv, Reddit, Ogbn-products）上进行了大量实验。定量结果揭示了几个关键洞察：首先，全面的性能分析表明，SCISE 在与十种最先进基线的比较中取得了整体优越性能，证实了其在中等和大规模场景中的一致有效性。其次，严格的消融研究剖析了各模块的协同效应，验证了 SECC、CSampE 和 StructCL 对保持结构完整性都不可或缺。最后，稳定性分析评估了模型对超参数变化的鲁棒性，强调了其在真实大规模系统中的鲁棒性和部署潜力。

本文的主要贡献总结如下：  

- **可扩展框架 (SCISE)**：我们提出 SCISE，一种无监督图聚类框架，通过社区感知采样与约束结构熵的协同作用，有效调和了计算可扩展性与结构完整性之间的冲突。  
- **社区感知采样扩展 (CSampE)**：我们开发了 CSampE 机制，通过自适应地将全局社区上下文融入小批量，从而弥合“结构隔离”，恢复小批量训练中的拓扑连续性。  
- **结构熵社区约束 (SECC)**：我们引入了 SECC 算子，在受约束空间内显式量化社区紧凑性，显著减少划分碎片化，确保全局社区完整性。  
- **广泛验证与洞察**：通过在六个基准数据集上的大量评估，我们展示了 SCISE 的整体优越性能和鲁棒性，同时识别了其核心组件的协同互补效应。  

图 2：SCISE 的整体框架。

---

## 2. 相关工作  

### 2.1. 无监督图聚类  

无监督图聚类从传统统计方法演变到复杂的深度学习范式。系统性综述（Liu et al., 2022b (https://arxiv.org/html/2607.05469#bib.bib44); Ren et al., 2024 (https://arxiv.org/html/2607.05469#bib.bib45)）建立了综合分类法，将该领域归为基于 GNN 和基于对比学习的方法，同时分析了生成模型与判别模型之间的权衡。在 GNN 范式中，DMoN（Tsitsulin et al., 2023 (https://arxiv.org/html/2607.05469#bib.bib5)）通过模块度最大化实现端到端社区检测，而 DeepCut（Aflalo et al., 2023 (https://arxiv.org/html/2607.05469#bib.bib46)）和 RGC（Liu et al., 2023a (https://arxiv.org/html/2607.05469#bib.bib47)）分别将这些技术扩展到无监督图像分割和基于强化学习的自动簇数确定。最近，对比学习已成为增强判别能力的主流趋势；例如，SCGC（Kulatilleke et al., 2025 (https://arxiv.org/html/2607.05469#bib.bib37)）通过面向邻居的损失简化对比架构，而 CCGC（Yang et al., 2023a (https://arxiv.org/html/2607.05469#bib.bib48)）和 DCGL（Chen et al., 2024 (https://arxiv.org/html/2607.05469#bib.bib49)）利用聚类导向指导来精炼表示学习。与这些算法进展并行，结构熵引入了稳健的信息论视角来捕获图层次结构，如 USER（Wang et al., 2023 (https://arxiv.org/html/2607.05469#bib.bib19)）和基于洛伦兹的 LSEnet（Sun et al., 2024 (https://arxiv.org/html/2607.05469#bib.bib6)）等方法推动了准确性和免参数聚类的边界。此外，将结构熵应用于无监督图聚类（Zhang et al., 2025a (https://arxiv.org/html/2607.05469#bib.bib8)）为结构信息理论与神经网络的协同开辟了新途径。  

### 2.2. 结构信息理论  

结构信息理论已在诸多应用中得到验证。在神经网络中引入结构熵能够捕获底层的拓扑连通性并减少随机干扰（Wang et al., 2023 (https://arxiv.org/html/2607.05469#bib.bib19); Zhang et al., 2025a (https://arxiv.org/html/2607.05469#bib.bib8)）。结构熵编码树的层次性质为图神经网络中的层次结构池化（Wu et al., 2022 (https://arxiv.org/html/2607.05469#bib.bib20)）、无监督图像分割（Xie et al., 2025 (https://arxiv.org/html/2607.05469#bib.bib60); Huang et al., 2026 (https://arxiv.org/html/2607.05469#bib.bib57)）、维度估计（Yang et al., 2023c (https://arxiv.org/html/2607.05469#bib.bib22)）、强化学习中的状态抽象（Zeng et al., 2023 (https://arxiv.org/html/2607.05469#bib.bib23), 2026b (https://arxiv.org/html/2607.05469#bib.bib59)）、社交机器人检测（Peng et al., 2024 (https://arxiv.org/html/2607.05469#bib.bib26); Zeng et al., 2025 (https://arxiv.org/html/2607.05469#bib.bib58)）、无监督社交事件检测（Cao et al., 2024b (https://arxiv.org/html/2607.05469#bib.bib24)）以及推荐系统（Zhang et al., 2025b (https://arxiv.org/html/2607.05469#bib.bib29)）提供了新方法。此外，在层次编码树上重构图结构可抑制边噪声并增强图结构的学习能力（Zou et al., 2024 (https://arxiv.org/html/2607.05469#bib.bib61)）。更进一步，基于最小化结构熵修改网络结构，可实现对社区结构的最大欺骗（Liu et al., 2019 (https://arxiv.org/html/2607.05469#bib.bib28)）。类似地，SEGA（Wu et al., 2023a (https://arxiv.org/html/2607.05469#bib.bib17)）和 SEPC（Huang et al., 2025 (https://arxiv.org/html/2607.05469#bib.bib62)）在结构熵最小化原则的指导下，提高了图对比学习的性能。基于同构图结构熵，对多关系图 SE（Cao et al., 2024a (https://arxiv.org/html/2607.05469#bib.bib16)）和超图 SE（Zhang et al., 2025b (https://arxiv.org/html/2607.05469#bib.bib29); Zeng et al., 2026a (https://arxiv.org/html/2607.05469#bib.bib63)）的研究进一步扩展了结构信息理论，使其适用于更复杂的场景。  

### 2.3. 大规模图学习  

大规模图学习已经发展以解决传统图神经网络（GNN）的可扩展性瓶颈。作为基础工作，GraphSAGE（Hamilton et al., 2017 (https://arxiv.org/html/2607.05469#bib.bib13)）引入了邻居采样用于归纳表示学习，而 VR-GCN（Chen et al., 2018 (https://arxiv.org/html/2607.05469#bib.bib50)）采用方差缩减来稳定随机训练。