DDGC：一种基于扩散的动态图聚类方法

《Neural Networks》：DDGC: A Diffusion-Based Approach for Dynamic Graph Clustering

　　动态图聚类方法融合扩散模型与密度估计，通过密度波动检测新类别并优化样本分布，解决动态环境中类数变化和稀疏样本问题，实验验证其优于现有方法。

　　

沈胜涛|叶旭伦|赵洁宇

宁波大学电气工程与计算机科学学院，中国宁波，315211

摘要

在本文中，我们提出了一种基于扩散模型的动态图聚类方法，以应对图结构演变的挑战，其中新节点可能属于未知类别。现有的深度图聚类方法在静态图上表现优异，但无法处理图拓扑和节点类别随时间演变的动态场景。此外，很少有现有的动态图聚类方法讨论少数类样本和动态类增长共存的复杂情况。我们的方法将图卷积网络（GCN）与扩散模型相结合，利用嵌入空间中的数据密度波动为无监督学习分配伪标签。具体来说，我们通过引入核密度估计和Tweedie公式来扩展扩散模型，以指导低密度区域的密度规范化，从而提高新类别识别的准确性。该方法还引导数据向高密度区域收敛，从而在密度变化较小的情况下提高模型的性能和鲁棒性。在基准数据集上的实验结果表明，我们的方法在动态图聚类任务中优于现有的最佳方法，特别是在涉及新兴未知类别的场景中。所提出的框架实现了自适应类别发现和样本增强，在静态和动态图环境中都表现出强大的性能。这项工作弥合了传统静态图聚类与现实世界动态应用之间的差距，为在线图理解提供了一个模块化解决方案。

引言

图聚类是一种传统的无监督学习任务（Meng等人，2015年；Peng等人，2023年；Shi等人，2020年；Wu等人，2020年）。作为最有效的方法之一，基于图卷积网络的聚类方案在准确性和嵌入学习能力方面表现出色。然而，传统的图卷积网络聚类假设应用场景是静态的，这与图结构动态演变的现实情况不符，如图1所示。这种动态变化导致了以下问题：（1）新类别的出现导致簇的数量发生变化，而传统的图聚类网络无法自适应地调整簇的数量，从而降低了聚类性能；（2）新数据的数量相对有限，传统方法无法将其检测为独立的类别；（3）每个类别中的边数据难以区分。

为了解决这些挑战，我们提出了一种新的图聚类方法。首先，为了解决问题（1），我们引入了一个基于图演变导致数据密度变化的假设的新类别检测模块。然后，我们将提出的基于密度的类别检测模型与图卷积相结合，以促进新类别的发现。对于问题（2），我们扩展了扩散模型，并将其与梯度结合，以解决样本不足的问题。对于问题（3），我们利用扩散的梯度特性和核密度极值共同引导数据向高密度区域收敛，从而区分不同的类别。这减少了边数据的影响。最后，我们将这两个模块整合到一个统一的图聚类网络中，以解决动态图聚类任务。我们的主要贡献如下：

(1)

我们提出了一个简单的模块，该模块结合了密度和贝叶斯推断，在动态环境中发现新类别，可以无缝集成到任何现有的图聚类模型中。

(2)

我们将扩散模型应用于动态图学习领域。通过将扩散模型与Tweedie公式相结合，我们解决了少样本增强和新类别发现相关的问题。

(3)

我们提出了一种新的动态图聚类方法，在多个数据集上表现出比最新的深度图聚类方法更优越的性能。

章节片段

动态图学习

图结构由特征结构和边结构组成，研究人员对此进行了广泛的研究。然而，大多数图神经网络（GNN）主要处理静态环境中的数据。在现实世界中，数据通常是动态的，这意味着动态图中的节点和边会随时间变化。此外，新数据可能属于已知或未知的类别。这个问题增加了动态图任务的复杂性。为了解决这一挑战，许多研究人员

问题阐述

在本节中，我们将介绍问题的定义和图结构的数学表示。首先，图可以定义为$G_{old}=(V_{old},E_{old},X_{old},Y_{old})$. 这里，V_old是图中的旧节点集；E_old是边集；X_old是特征矩阵，表示每个节点的特征，Y_old是旧节点标签，表示每个节点的类别。在我们的应用中，V_old、E_old和X_old不是静态的，会随时间演变。

实验

为了验证DDGC模型的有效性，我们在几个广泛使用的基准数据集上进行了测试和消融实验。我们将这种方法与其他一些最近的图聚类算法进行了比较。这些方法的数据来自GitHub上相应论文提供的代码。有关实验中使用的数据集的详细信息，请参见表3。为了模拟类别数量不断增加的动态环境，我们将数据集

结论

在这项研究中，我们介绍了DDGC（开放世界动态图聚类），这是一种旨在解决动态图聚类挑战的新模型。该框架明确解决了两个核心问题：新类别的发现和样本不足的问题。对于新类别的识别，我们提出了GDD（图密度检测）框架，该框架利用核密度估计和历史数据的方差分析来量化传入数据属于某个类别的概率

未引用的参考文献

图2和图8以及算法1。

数据可用性

作者没有权限共享数据。

CRediT作者贡献声明

沈胜涛：撰写——原始草案，调查，数据整理，概念化。叶旭伦：撰写——审稿与编辑，项目管理。赵洁宇：资源获取，资金筹集。

利益冲突声明

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

致谢

本工作得到了中国国家自然科学基金（项目编号62471266、62006131、62071260）；浙江省自然科学基金（项目编号LQ21F020009、LGF21F020008、LQ22F020020）；以及宁波市公益科技研究项目（项目编号2022S134）的支持。