论文阅读“Simple Contrastive Graph Clustering”

Liu Y, Yang X, Zhou S, et al. Simple Contrastive Graph Clustering[J]. arXiv preprint arXiv:2205.07865, 2022.

摘要导读

复杂的数据增强（ complicated data augmentations）和较为耗时的图卷积操作（time-consuming graph convolutional operation）影响了对比学习在图聚类的应用。对此，本文聚焦网络结构、数据增强和目标函数三个方面，提出了一个简单的对比图聚类结构。该结构分为预处理和网络backbone两个部分。
从结构上来说，本文使用了一个简单的低通去噪操作将邻居信息聚合作为一个独立的预处理操作，骨干（backbone）部分只包括两个多层感知器（MLP）。
对于数据增强，通过设计参数不共享的连体编码器和直接corrupt节点嵌入来构建同一顶点的两个增强视图。
最后，在目标函数方面，为了进一步提高聚类性能，设计了一个新的跨视图结构一致性目标函数，以提高网络的判别能力。

模型浅析

相关说明和问题定义
$\mathcal{V}=\{v_1, v_2, \cdots, v_N\}$ 是来自 $C$ 个类簇的 $N$ 个节点， $\mathcal{E}$ 为这些节点所对应的边。矩阵 $X$ 和 $A$ 分别为属性矩阵和原始的邻接矩阵。图 $\mathcal{G}=\{X,A\}$ 被记为无向图。 $D=diag(d_1, d_2, \cdots, d_N)$ 为度矩阵， $d_i=\sum_{(v_i,v_j) \in \mathcal{E}}a_{ij}$ 。图的拉普拉斯矩阵 $L=D-A$ 。根据对应的重正则化技巧， $\hat{A}=A+I$ 是加入自环的邻接矩阵，因此对应改变了 $D$ 的计算，得到了对应的 $\hat{D}$ 和 $\hat{L}$ ，此时对称的正则图拉普拉斯矩阵可以重新计算：
本文的任务是使用无监督的方式学习面向聚类的节点embedding，在其上直接应用k-means进行聚类。模型的整体结构如图所示：

其流程主要包含三个部分，低通去噪操作，结构对比模块，以及最后的聚类过程。
低通去噪操作
已经有文献指出（Adaptive graph encoder for attributed graph embedding & Deeper insights into graph
convolutional networks for semi-supervised learning & Simplifying graph convolutional networks），拉普拉斯滤波器（Laplacian filter）可以实现和图卷积类似的效果。受其启发，本文引入低通去噪操作来进行近邻信息的聚合，该过程是独立于后续模块的独立操作。使用的滤波器公式如下：

其中， $\tilde{L}$ 是前序提到的对称正则的图拉普拉斯矩阵， $k$ 为实值，这里固定为 $\frac{2}{3}$ 。该部分采用了堆叠 $t$ 层拉普拉斯过滤器：

$X$ 为原始输入的属性矩阵，而 $X_s$ 为平滑过后的属性矩阵。通过该低通去噪操作，属性中的高频噪声会被过滤掉，从而可以提高聚类的性能和训练的效率。
结构对比模块
该模块的目的是保持两个不同视图表示的结构一致性，以提高网络的辨别能力。
通过设计两个结构一致但参数不共享的MLP学习两种不同的正则化的视图表示：

因此， $Z^{v_1}$ 和 $Z^{v_2}$ 可以在训练中学习到不同的语义信息。
在此基础上，为了保证两个视图表示的差异性，对 $Z^{v_2}$ 添加了随机高斯噪声的扰动：

在简化数据增强的操作之上，本文还设计了一个面向近邻的对比损失来确保跨视图之间的结构一致性。首先需要计算两个视图之间的样本相似性矩阵 $S \in \mathbb{R} ^ {N \times N}$ ：

对于给定样本数据而言，其邻接矩阵只存在一个。因此，可以利用两个增强视图的相似性来构造与输入的损失而进行自监督学习。最简单的方式是强制跨视图之间的相似性矩阵 $S$ 与自环邻接矩阵是相等的，来保持结构学习的一致性。

这里，将同一节点的跨视图邻居视为正样本，而将其他非邻居节点视为负样本。具体而言，上述式子中的第一项迫使节点即使在两个不同的视图中也与它们的邻居保持一致，而第二项则使节点与其非邻居之间的一致性最小化。这种面向近邻的对比目标函数通过保持跨视图结构的一致性，提高了网络的鉴别能力，从而提高了聚类性能。
融合和聚类
前序学到了两个增强视图的节点嵌入表示 $Z^{v_1}$ 和 $Z^{v_2}$ ，并采用线性组合的方式进行融合：

所获得的 $Z \in \mathbb{R}^{N \times d}$ 是面向聚类的节点表示。在此基础上，直接应用k-means得出聚类结果。
整体算法流程

从论文给出的结果来看，虽然没有依赖KL的聚类回调聚类分配和特征表示，但是依然获得了较好的效果，特别是在图数据集上获得了明显的效果。说明无论是低通去噪操作还是后续设计的面向近邻的对比损失，对节点的表示学习是有很大作用的。特别是使用高斯噪声对增强视图的构造方式，不仅降低了计算成本，也降低了在数据增强中与 $\mathcal{G}=\{X,A\}$ 的耦合性，很巧妙。
在组里之前的工作中也用到了类似的方式进行损失的构造，但是没从对比学习的思路去思考。。感觉这是一个很好的启发。