TNNLS'23 | 简单高效的图对比学习聚类

Houye

发布于 2024-01-29 14:35:27

2470

发布于 2024-01-29 14:35:27

编译 | 朱江跃审稿 | 苟丛林

今天给大家分享的是国防科技大学刘新旺老师团队发表在IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS的论文"Simple Contrastive Graph Clustering"。论文提出了一种简单高效的图对比学习聚类方法SCGC，SCGC十分轻量，并且和一般的深度图聚类相比，不需要花大量时间去预训练。文章提出了一种新的对比学习数据增强方法，设计了一种新颖的基于邻居节点的对比loss。

1、摘要

近期，对比学习在深度图聚类中受到了广泛关注，因为其表现出了良好的性能。然而，复杂的数据增强和耗时的图卷积操作却降低了这些方法的效率。为了解决这个问题，作者提出了一种简单的对比图聚类（SCGC）算法，从网络架构、数据增强和目标函数等方面改进了现有的方法。在架构方面，本文的网络包括两个主要部分：预处理和网络主干。一个简单的低通去噪操作作为独立的预处理进行邻居信息聚合，只有两个多层感知器（MLPs）作为模型主体。对于数据增强，作者没有引入复杂的图操作，而是通过设计参数不共享的MLP编码器和直接扰动节点嵌入，构建了同一顶点的两个增强视图。最后，对于目标函数，为了进一步提升聚类性能，作者设计了一种新的跨视图结构一致性目标函数，以增强学习网络的判别能力。在七个基准数据集上的广泛实验结果证实了本文提出的算法的有效性和优越性。显著的是，本文的算法在平均性能上至少比最近的对比深度聚类算法平均快七倍。

2、方法

符号与问题定义

首先定义图的节点集为

\mathcal{V}=\{v_{1},v_{2},\ldots,v_{N}\}

，节点的属性表示为

\mathbf{X}\in\mathbb{R}^{N\times D}

。以此为基础，可以构建一个无向图

\mathcal{G}=\{\mathbf{X},\mathbf{A}\}

。图的度定义为

\mathbf{D}=\mathrm{diag}(d_{1},d_{2},\ldots,d_{N})\in\mathbb{R}^{N\times N}

，而图的拉普拉斯矩阵表示为

\mathbf{L}=\mathbf{D}-\mathbf{A}

。通过使用图卷积网络（GCN）中的重整化技巧，得到图的对称归一化拉普拉斯矩阵

\widetilde{\mathbf{L}}=\mathbf{I}-\widehat{\mathbf{D}}^{-(1/2)}{\widehat{\mathbf{A}}\widehat{\mathbf{D}}}^{-(1/2)}

。

深度图聚类的目标是将图的节点分割为几个独立的群体。更具体地说，可以使用无监督方式预训练一个神经网络

\mathcal{F}

，该网络能够编码图的节点和结构信息，表示为：

\mathbf{E}=\mathcal{F}(\mathbf{A},\mathbf{X})

编码完成后，可以使用K-means、谱聚类等聚类算法

\mathcal{C}

，将节点的嵌入划分为独立的群组：

\Phi=\mathcal{C}(\mathbf{E})

整体框架

SCGC的整体架构

SCGC主要包含了低通噪声滤波、结构对比模块两个部分。

低通滤波处理噪声

近期的研究表明，拉普拉斯滤波器能够实现与图卷积网络（GCN）相同的效果。受此启发，作者提出了一种低通滤波操作，用于聚合邻近节点的信息，从而有效地过滤掉属性中的高频噪声。具体来说，作者引入了图拉普拉斯滤波器：

\mathbf{H}=\mathbf{I}-\tilde{\mathbf{L}}

其中，

\tilde{\mathbf{L}}

代表对称归一化的图拉普拉斯矩阵。作者将

个图拉普拉斯滤波器进行了堆叠：

\begin{aligned}\mathbf{X}_s&=\left(\prod_{i=1}^t\mathbf{H}\right)\mathbf{X}\\&=\mathbf{H}^t\mathbf{X}\end{aligned}

这种低通滤波的降噪操作有效地过滤了高频噪声，从而提升了聚类性能和训练效率。

结构对比模块的优化

作者提出了一种称为SCM的方法，旨在保持两个不同视图之间的结构一致性，以此提升网络的判别能力。具体来讲，作者首先对平滑后的属性

\mathbf{X}_s

使用MLP编码器编码，然后将得到的结点嵌入进行L2规范化：

\begin{aligned}\mathbf{Z}^{v_1}&=\mathrm{MLP}_1(\mathbf{X}_s),\quad\mathbf{Z}^{v_1}=\frac{\mathbf{Z}^{v_1}}{\left|\left|\mathbf{Z}^{v_1}\right|\right|_2}\\\mathbf{Z}^{v_2}&=\mathrm{MLP}_2(\mathbf{X}_s),\quad\mathbf{Z}^{v_2}=\frac{\mathbf{Z}^{v_2}}{\left|\left|\mathbf{Z}^{v_2}\right|\right|_2}\end{aligned}

其中

\mathbf{z}^{v_1}

和

\mathbf{z}^{v_2}

表示学习到的节点嵌入的两个增强视图。为了进一步保持两个视图的不一致性，作者在嵌入中添加了高斯噪声：

\mathbf{Z}^{v_2}=\mathbf{Z}^{v_2}+\mathbf{N}

作者设计了两个参数不共享的MLP编码器来实现视图的增强，这种增强方式仅通过扰动嵌入而非采用复杂的图增强方式，效果显著。此外，最近的一些研究显示，复杂的图数据增强方式，例如增加、减少边、图扩散等，可能会导致语义偏移，这也得到了作者后续实验的证实。

接着，作者提出了一种新颖的、面向邻居的对比损失函数，以保持跨视图的一致性。具体来说，作者计算了跨视图采样的相似度矩阵：

\mathbf{S}_{ij}=\mathbf{Z}_i^{v_1}\cdot\left(\mathbf{Z}_j^{v_2}\right)^\mathrm{T}\quad\forall i,j\in[1,N]

其中

\mathbf{S}_{ij}

代表第i个节点和第j个节点的嵌入的余弦相似度。然后，作者强制让跨视图采样的相似度矩阵与自环邻接矩阵保持一致：

\begin{aligned} \text{L}& =\frac1{N^2}\sum\left(\mathbf{S}-\widehat{\mathbf{A}}\right)^2 \\ &=\frac1{N^2}\left(\sum_i\sum_j\mathbb{1}_{ij}^1\left(\mathbf{S}_{ij}-1\right)^2+\sum_i\sum_j\mathbb{1}_{ij}^0\mathbf{S}_{ij}^2\right) \end{aligned}

在这里，作者将跨视图的邻居节点视为正采样，非邻居节点视为负采样，优化的目标是将正采样拉近，负采样推远。