论文阅读“Graph Contrastive Clustering”

Zhong H, Wu J, Chen C, et al. Graph Contrastive Clustering[J]. arXiv preprint arXiv:2104.01429, 2021.

摘要翻译

最近，人们提出了一些对比学习方法来同时学习表征和聚类分配，取得了明显的改善。然而，这些方法并没有考虑到类别信息和聚类目标，因此学习到的表征并不是最优的聚类方法，其聚类性能可能会受到限制。为了解决这个问题，我们首先提出了一个新的图对比学习框架，然后将其应用于聚类任务，形成了图对比聚类（Graph Constrastive Clustering, GCC）方法。基本的对比聚类只假设一个样本图像实例及其扩展应该具有相似的表示和聚类分配，与此不同的是，我们将实例的级别一致性提升为类簇级别一致性，并假设一个簇中的样本及其扩展都应该相似。具体来说，一方面，我们提出了基于图拉普拉斯的对比性损失，以学习更多的鉴别性和有利于聚类的特征。另一方面，我们提出了一种新的基于图的对比性学习策略来学习更紧凑的聚类分配。这两种方法都包含了潜在的类别信息，以减少集群内的差异，并增加集群间的差异。在六个常用数据集上的实验表明，我们提出的方法优于目前最先进的方法。

先给出概念当前论文核心概念图：

Motivation of the proposed GCC

(a) 现有的基于对比学习的聚类方法主要集中于实例一致性，从而最大化自增强样本之间的相关性，并将所有其他样本视为负样本。这种基于实例的一致性，可能在选取负样本的时候出自同一类簇的，从而学习到的特征表示对聚类不太友好。
(b) 论文提出的GCC结合了类别信息，在实例和集群级别上执行对比学习，这可以更好地最小化集群内的方差，并最大化集群间的方差。更适合聚类任务。

Graph Contrastive Clustering模型浅析

(1)问题形式化

给定来自 $K$ 个类簇的 $N$ 个图片样本 $I = \left\{I_1,I_2,...,I_N\right\}$ 。目标是学习一个基于CNN网络的深度映射函数 $Φ$ ，每个图像 $I_i$ 都可以映射到 $(z_i，p_i)$ ，其中 $z_i$ 是具有正则化的d维表示特征 $||z_i||_2=1$ ， $p_i$ 是满足 $\sum _{j=1}^K p_{ij}=1$ 的 $K$ 维分配概率。因此，在聚类中，样本图像 $I_i$ 最后所属的类簇即为 $l_i = {arg max}_ j(p_{ij} ), 1 ≤ j ≤ K.$

(2)Graph Contrastive提出

给定无向图 $G$ 及其度矩阵 $D$ ，论文给出了正则化的对称图拉普拉斯定义 $L=I−D^{-1/2} AD^{-1/2}$ 。
易得，

根据临接矩阵 $A$ 的性质，给定 $N$ 个表示特征 $x=\left\{x_1,…,x_N\right\}$ 对于单位 $L_2$ 范数，GC的直觉是，如果 $A_{ij}>0$ ， $x_i$ 应该接近 $x_j$ ，而如果 $A_{ij}=0$ ， $x_i$ 应该远离 $x_j$ 。从图结构数据的观点出发，假设图可以被划分为几个社区，GC的直觉告诉我们，同一社区中特征表示的相似性应该比它在其他社区之间更大。即，有临接关系的样本之间的相似性比没有临接关系的样本相似性更大。

根据图结构中的这种特性，论文给出了两种类型的相似度度量：
社区内的总相似度

intra

社区间的总相似度

inter

其中， $S(x_i, x_j )$ 是 $x_i$ 和 $x_j$ 之间的相似性。
为了同时增加类簇内总相似度，降低类簇间总相似度，提高特征的可分性，使得学习到的特征表示与图结构一致。论文构造了 $L_{GC}$ 如下：

Graph Contrastive 损失

最小化损失 $L_{GC}$ 相当于最大化样本邻域中的对数似然。即最大化分子部分（社区内的总相似度），最小化分母部分（社区间的总相似度）。

(3)总体Graph Contrastive Clustering模型

通过将GC应用于表示学习和分配学习，引入了一种新的端到端深度聚类框架。

GCC

图的构建
由于深度学习模型通常在训练过程中发生波动，一个epoch的表示特征可能有很大的偏差。在图的构建之前利用移动平均来减少这种偏差。假设 $Φ_θ^{(t)}$ 是模型， $Z(t)=(z^{(t)}_1、···、z^{(t)}_N)=(Φ^{(t)}_θ(I_1)、···、Φ^{(t)}_θ(I_N))$ 是第 $t$ 个epoch的表示特征，是表示特征的移动平均可以定义为：

moving average

其中 $α$ 是一个参数来权衡当前和过去的效果 $\overline{z}^{(0)}_i=z^{(0)}_i$ 。由此，我们可以构建第 $t$ 个epoch的KNN临接矩阵，

第t个epoch的临接矩阵

并计算 $L^{(t)}$ 。
相似性函数
使用的是高斯核函数计算相似度。

similarity(1)

其中， $τ$ 是一个表示方差或温度的参数。上式可写成 $∥x_i − x_j∥^2_2 = ∥x_i∥^2_2 + ∥xj∥^2_2 − 2x_i · x_j = 2 − 2x_i · x_j$ ，由此

similarity(2)
图对比表示(Representation Graph Contrastive)损失
假设 $I^{'}=\left\{I_1^{'},…,I_N^{'}\right\}$ 是原始图像的随机变换，其对应特征为 $z^{'}=(z_1^{'},···,z_N^{'})$ 。根据对比图的直觉，如果 $z_i^{'}$ 和 $z_j^{'}$ 有边连接，它们应该是相似的，而如果它们无边邻接，它们应该不太相似。通过将原始样本表示 $x_i$ 转换为 $z_i$ ，上述Graph Contrastive 损失在RGC中的应用可以转换为：

RGC Loss
图对比聚类分配( Assignment Graph Contrastive)损失
对于传统的基于对比学习的聚类，图像及其增强应该共享相似的聚类分配分布，即实例及其对应的增强在聚类中是一致的。它是合理的，但没有利用聚类信息。随着模型在训练过程中越来越好，图像和其邻居也应该具有高概率的相似的聚类分配分布。由此提出了图对比聚类分配学习。
假设 $I^{'}=\left\{I_1^{'},…,I_N^{'}\right\}$ 是原始图像的随机增强， $\tilde{I}^{'}=\left\{\tilde{I}_1^{'},…,\tilde{I}_N^{'}\right\}$ 满足 $\tilde{I}_i^{'}$ 是 $I_i$ 根据图邻接矩阵 $A(t)$ 选择的随机邻居的转换， $I^{'}$ 和 $\tilde{I}^{'}$ 的分配概率矩阵可以定义为从全体样本的角度看概率分配:

增强实例和邻居实例的概率分配矩阵(1)

然后从列的角度对上述分配矩阵进行重新定义从单个样本的角度看概率分配，即

增强实例和邻居实例的概率分配矩阵(2)

上述Graph Contrastive 损失在AGC中的应用可以转换为

AGC Loss
聚类正则损失
在深度聚类中，很容易落入一个局部最优解决方案，将大多数样本分配到少数集群中。由此，论文增加了聚类正则损失：

Cluster Regularization Loss

关于H的表达将会在后续论文“Deep semantic clustering by partition confidence maximisation” 的阅读中阐述，如有需要请自行查看