基于动态负采样与多尺度难样本挖掘的对比图聚类

《Neurocomputing》：Contrastive graph clustering via dynamic negative sampling and multi-scale hard sample mining

　　

摘要 深度图对比学习通过最小化类内节点之间的距离并建立明显的类间边界来增强特征表示。然而，它面临两个基本挑战：首先，负采样过程容易受到"伪负例"的影响，从而限制了所学习表示的判别能力和鲁棒性；其次，原始图中固有的异质性和噪声会削弱关键的判别信号，导致特征过度平滑和可分性降低。为了解决这些问题，本文提出了一种面向深度图聚类的动态负采样与多尺度难样本挖掘策略（DNMH）。首先，引入了一种基于课程学习的动态负采样机制。该机制通过整合特征相似性与语义一致性来区分高度可信的负例对。此外，采用了一种基于课程学习的动态自步函数，随着训练的进行调整筛选标准，显著减轻了伪负例对的干扰。其次，设计了一种多尺度难样本挖掘策略，从全局语义结构和局部邻域细节两个维度来评估样本难度。并引入了自适应重加权机制，动态平衡难例对和易例对的损失贡献，从而增强特征的鲁棒性。最后，构建了一个综合对比学习框架，包含三个协同分支：节点-节点、节点-子图和子图-子图。通过整合多层级结构信息，所提出的框架显著提升了图表示的判别能力和鲁棒性。在六个公开数据集上与九种对比算法的实验结果表明，DNMH获得了更高的聚类精度。

引言 深度图聚类旨在利用图数据的拓扑结构和节点属性，将节点划分为多个互不相交的语义簇[1]。得益于其从复杂交互中提炼结构化知识的能力，图聚类已成为分析真实世界复杂系统的重要工具[2]。在个性化推荐领域，图聚类通过聚合兴趣相似的用户来促进精准的个性化推荐[3]、[4]。在生物医学领域，图聚类被广泛应用于蛋白质功能模块的识别和致病因素的分析[5]、[6]。在网络安全和反欺诈场景中，图聚类能够处理大规模且高度嘈杂的金融和电信数据，为风险防控提供关键的结构化决策支持[7]、[8]。

在现有的深度图聚类范式[9]中，基于对比学习的方法通过聚焦节点间的判别关系，拉近正例对、推远负例对，展现了强大的表示学习能力。图对比学习在训练过程中无需人工标注标签，仅基于样本间的相似性关系学习图表示，因此在图聚类方面展现出巨大潜力。Veli?kovi?等人提出了深度图信息最大化（DGI）[10]，通过最大化局部节点补丁与全局图摘要之间的互信息来学习高质量的节点嵌入，为后续的图对比表示学习和图聚类研究奠定了基础。

对比学习的有效性不仅取决于对比视图的构建，还高度依赖于正负样本对选择的质量。尽管上述基于对比的图表示学习方法在下游任务中表现出显著效果，但仍面临一个关键挑战：负采样过程容易受到"伪负例"的影响，从而限制了特征表示的判别能力和鲁棒性。从本质上讲，对比学习的根本目标是使学习到的编码器将正例对映射得更近，同时将负例对推得更远。显然，实现这一目标高度依赖于正负样本对的精确选择；高质量的样本对可以引导模型学习更具判别性的聚类边界。作为无标签的自监督学习范式，图对比学习通常可以通过图增强[11]或图挖掘[12]来生成可靠的正例对。然而，负样本的选择通常依赖于均匀随机采样策略。这种机制未能考虑图结构化数据中固有的潜在标签分布。在实践中，这种传统的简单采样方法不可避免地会引入伪负例，即具有相同语义标签的节点被错误地识别为负样本，从而产生错误的排斥效果[13]。这一过程破坏了簇内结构，严重损害了嵌入特征表示。

现有对比学习中负样本获取的方法大致可分为两类：一类直接从原始图中选择负样本[14]、[15]，另一类通过额外的生成策略构建人工负样本[16]、[17]。尽管这些方法在一定程度上提高了负样本的质量，但在负样本的可靠性识别和其难度自适应调整方面仍存在局限。具体而言，随机负样本选择容易引入伪负例，从而破坏聚类空间的一致性。同时，固定难度的负样本难以适应不同的训练阶段，使模型在训练早期阶段容易受到噪声样本的影响。相比之下，虽然人工生成的负样本可以提高样本多样性，但它们通常需要额外的生成过程或优化步骤，这增加了模型复杂度，同时其语义质量在训练过程中也难以稳定控制。因此，如何选择适当的负样本仍然是图对比学习中的一个挑战性问题。

伪负例指的是具有相同或相似语义但被错误地视为负例的节点对，而难样本则是指在表示空间中难以区分的样本，通常位于潜在聚类边界附近。仅仅选择高质量的负样本仍然不足以充分增强图对比表示的判别能力。在对比学习过程中，不同的样本对对模型优化的贡献不同，位于决策边界附近且未被充分拉近或推远的难样本通常提供更大的优化价值。然而，传统的对比图聚类方法通常将图中几乎所有节点对同等对待。大量的易样本可能会占用过多的计算资源并稀释有效梯度，从而直接破坏簇结构和簇内边界[18]、[19]。因此，难样本挖掘逐渐成为图对比学习中的一个重要研究方向[20]。例如，Chu等人提出了CuCo [21]，通过课程学习逐步引入难样本。Liu等人提出了HSAN [18]，进一步加强了难样本在图聚类过程中的作用。尽管现有方法取得了一定的进展，但仍存在两个问题。首先，现有研究往往将全局聚类结构和局部边界的协同建模解耦，难以同时兼顾全局和局部难样本。其次，依赖静态或单尺度权重调度机制使模型在训练早期阶段容易受到噪声干扰。这表明，构建一个能够整合多尺度视角的动态难样本挖掘框架对于进一步增强图聚类的鲁棒性至关重要。

基于上述分析和洞察，本文提出了一种通过动态负采样和多尺度难样本挖掘的对比图聚类方法（DNMH），主要由以下三个核心组件组成：（1）基于课程学习的动态负采样机制：为解决现有方法在随机采样过程中容易引入伪负样本从而破坏聚类结构的问题，通过整合k近邻（NN）图结构与聚类伪标签信息构建高置信度负样本选择池。同时，受课程学习理念启发，引入动态自步函数，随着训练的进行自适应调整负样本的筛选难度和规模。（2）全局-局部协同多尺度难样本挖掘策略：为克服现有难样本挖掘方法往往将全局和局部结构解耦并依赖单一权重调度机制的局限，设计了全局-局部多尺度难样本挖掘机制。在全局层面，采用互信息判别器识别语义边界模糊的节点；在局部层面，基于跨视图邻域一致性捕捉局部结构中的难样本。通过自适应加权机制，模型动态放大"真实难"样本的学习信号，从而建立更清晰的类间边界。（3）三重一致性对比学习：为全面增强图表示的鲁棒性，该模块构建了涵盖节点-节点、节点-子图和子图-子图关系的三个对比分支。在多尺度难样本挖掘策略的指导下，该框架不仅增强了节点的判别性，还通过邻域子图特征捕获了高阶信息，从而实现了更准确和全面的特征对齐。本文的主要贡献总结如下：

（1）提出了一种基于课程学习的动态负采样机制，克服了传统随机采样的局限，有效抑制了训练过程中伪负样本引入的噪声干扰。（2）设计了一种全局-局部协同的多尺度难样本挖掘策略，从全局语义结构和局部邻域结构两个维度共同衡量样本难度，从而建立更清晰的类间边界。（3）构建了一个三重一致性对比学习框架，包含三个对比分支：节点-节点、节点-子图和子图-子图。该框架增强了模型表示复杂语义信息的能力，提升了最终的聚类性能。

本文其余部分组织如下。第2节回顾了图表示学习的相关工作。第3节详细介绍了DNMH的设计和整体框架。第4节呈现了实验结果和相应分析。最后，第5节总结了本文。

相关工作片段 图对比学习通过在不同视图或语义层级上构建对比关系来学习判别性节点表示，无需人工标注标签，已成为图表示学习和深度图聚类的重要研究方向。Veli?kovi?等人提出了DGI [10]，通过最大化局部节点补丁与全局图摘要之间的互信息来执行表示学习。Zhu等人提出了GRACE [22]，该

方法

本文提出了一种通过动态负采样和多尺度难样本挖掘的对比图聚类方法，命名为DNMH。所提算法的整体框架如图1所示。

如图1所示，所提出的算法旨在通过联合优化动态负采样和多尺度难样本挖掘来增强图聚类的判别能力。该框架主要由四个阶段组成：（1）多视图增强与表示 实验结果与分析 本节介绍了用于评估DNMH算法的数据集、基线算法和实验设置，并对实验结果进行了分析。通过消融研究，验证了动态负采样模块、全局-局部难样本挖掘策略和三重一致性对比学习框架的重要性。此外，还分析了算法中涉及参数的敏感性。结论 本文提出了一种通过动态负采样和多尺度难样本挖掘的对比图聚类方法（DNMH），以解决现有深度图聚类方法中普遍存在的伪负例干扰和难样本挖掘不足的问题。首先，通过引入基于课程学习的动态负采样机制，缓解了图对比学习中引入伪负例对的问题。通过联合评估节点的邻域 CRediT作者贡献声明 Gao Zexin：撰写——初稿，方法论。Zhang Weitong：撰写——审阅与编辑，方法论，资金获取。Zhu Xuerong：撰写——审阅与编辑，数据整理。利益冲突声明 作者声明他们没有已知的可能影响本文所述工作的竞争性经济利益或个人关系。致谢 本工作部分由中国国家自然科学基金（批准号62406237、62176200和12326617）、中国博士后科学基金（资助号2024M752536）、陕西省博士后研究项目（资助号2023BSHTBZZ30）和陕西省自然科学基础研究计划（资助号2022JC-45）资助。Gao Zexin于2024年获得中国西安电子科技大学计算机科学与技术学院的学士学位。他目前正在中国西安电子科技大学人工智能学院攻读硕士学位。他目前的研究兴趣包括深度图表示学习和聚类。Gao Zexin | Zhang Weitong | Zhu Xuerong