论文标题：ClusterSCL: Cluster-Aware Supervised Contrastive Learning on Graphs
论文作者：Yanling Wang, Jing Zhang, Haoyang Li, Yuxiao Dong, Hongzhi Yin, Cuiping Li
论文来源：2020, ICML
论文地址：download
论文代码：download
图上的监督对比学习很难处理拥有较大的类内（intra-class）差异，类间（inter-class）相似性的数据集。
Figure 1(a) 顶部中 $(u_1,u_3)$ 、$(u_2,u_4)$ 属于同一个类，但在不同的图社区（intra-class variances），而 $(u_1,u_2)$、$(u_3,u_4)$ 来自不同的类但在同一图社区（inter-class similarities）。针对上述问题，需要找出一个复杂的决策边界，见 Figure 1(a) 底部。
当执行自监督对比（SupCon）为 $u_{2}$ 寻找锚节点，如 Figure 1(b) 所示，正样本对属于同一类但位于不同的簇，如 $left(u_{2}, u_{4}right)$。简单地把正对（相同标签节点）放在同一嵌入空间，可能间接把不同类的节点，如 $left(u_{2}, u_{3}right)$ 看成正对，因为 $u_{3}$ 和 $u_{4}$ 社区结构类似。同时，对属于不同类但位于同一簇中的负样本对，如 $left(u_{2}, u_{1}right)$，简单地把它们推开可能间接推开同一类的节点，如 $left(u_{2}, u_{5}right)$，因为 $u_{5}$ 在结构上与 $u_{1}$ 相似。
上述问题总结为：简单的执行类内差异小，类间方差大的思想，可能会造成分类错误，导致 Figure 1(c) 顶部显示的更复杂的决策边界。
本文的想法简单的如 Figure 1(b) 底部所示。
对一个 batch 内的节点 $v_{i}$ ，其正样本下标集合 $S_{i}$，$s_{i} in S_{i}$ 是 $v_{i}$ 正样本的索引。SupCon 损失函数如下：
${large mathcal{L}_{text {SupCon }}=-sumlimits _{v_{i} in B} frac{1}{left|S_{i}right|} sumlimits _{s_{i} in S_{i}} log frac{exp left(mathbf{h}_{i}^{top} mathbf{h}_{s_{i}} / tauright)}{sumlimits _{v_{j} in B backslashleft{v_{i}right}} exp left(mathbf{h}_{i}^{top} mathbf{h}_{j} / tauright)}} quadquadquad(3)$
其中 $mathbf{h}$ 代表着经 $ell_{2}$-normalized 处理后的表示。
假设 SupCon 学习过程中有 $M$ 个潜在簇，引入潜在变量 $c_{i} in{1,2, ldots, M}$ 来指示节点 $v_{i}$ 归于哪个簇。给定一个锚节点 $v_{i}$ 和一个节点 $v_{j}$，CDA 通过以下线性插值，在特征级构造了一个 $v_{j}$ 的加强版本：
$tilde{mathbf{h}}_{j}=alpha mathbf{h}_{j}+(1-alpha) mathbf{w}_{c_{i}} quadquadquad(4)$
其中，$mathbf{w}=left{mathbf{w}_{m}right}_{m=1}^{M}$ 表示簇原型。$tilde{mathbf{h}}_{j}$ 包含来自 $v_{j}$ 的信息，并且包含了节点 $v_{i}$ 所属的簇的信息。这种方式缩小了 SupCon 的特征空间。并拉近了远正样本对之间的距离和拉远了近负样本对之间的距离，帮助保留节点的聚类分布。$alpha$ 控制着拉近还是拉远，图解如 Figure 2 所示：
如果锚节点 $v_{i}$ 和对比样本 $v_{j}$ 本身在嵌入空间已经足够相近，那么可以选择直接对比，也可以为其分配一个更大的 $alpha$ ，使 $v_{j}$ 包含更多自身信息。相反，若 $v_{i}$ 和 $v_{j}$ 在嵌入空间中彼此远离，那么使用较小的 $alpha$ 来衰减来自 $v_{j}$ 的信息，以保证锚点和增强样本之间不会太远。
$text{Eq.3}$ 模拟的是拉近正对，并没有考虑拉远负对。本文从从正负样本对的角度设计了调整 $alpha$ 的原则，计权重 $alpha$ 计算方式为：
${large alpha=frac{exp left(mathbf{h}_{i}^{top} mathbf{h}_{j}right)}{exp left(mathbf{h}_{i}^{top} mathbf{h}_{j}right)+exp left(mathbf{h}_{i}^{top} mathbf{w}_{c_{i}}right)}} quadquadquad(5)$
$mathbf{h}_{i}$ 和 $mathbf{h}_{j}$ 位于半径为 $1$ 的超球面的表面上，我们有 $left|mathbf{h}_{i}-mathbf{h}_{j}right|^{2}=2-2 mathbf{h}_{i}^{top} mathbf{h}_{j}$，即表示内积越大代表着表示之间的欧几里得距离小。
mixup 和 CDA 都采用线性插值操作来生成虚拟数据点。在这里，阐述 CDA 与 mixup 之间的区别：
Integrating Clustering and CDA into SupCon Learning
流程如下：
在执行 CDA 之前，需要通过下式知道锚节点 $v_i$ 属于哪个簇：
${large pleft(c_{i} mid v_{i}right)=frac{exp left(mathbf{h}_{i}^{top} mathbf{w}_{c_{i}} / kapparight)}{sumlimits _{m=1}^{M} exp left(mathbf{h}_{i}^{top} mathbf{w}_{m} / kapparight)}} quadquadquad(7)$
其中，$kappa$ 为用于调整聚类分布的温度参数，$pleft(c_{i} mid v_{i}right) $ 可以视为一个基于原型的软聚类模块。
基于 CDA 推导出的节点版本（即已经使用了线性插值），对以下实例识别任务进行建模（聚类感知识别器）：
${large begin{aligned}pleft(s_{i} mid v_{i}, c_{i}right) &=frac{exp left(mathbf{h}_{i}^{top} tilde{mathbf{h}}_{s_{i}} / tauright)}{sumlimits _{v_{j} in V backslashleft{v_{i}right}} exp left(mathbf{h}_{i}^{top} tilde{mathbf{h}}_{j} / tauright)} \&=frac{exp left(mathbf{h}_{i}^{top}left(alpha mathbf{h}_{s_{i}}+(1-alpha) mathbf{w}_{c_{i}}right) / tauright)}{sumlimits _{v_{j} in V backslashleft{v_{i}right}} exp left(mathbf{h}_{i}^{top}left(alpha mathbf{h}_{j}+(1-alpha) mathbf{w}_{c_{i}}right) / tauright)}end{aligned}} quadquadquad(6)$
由于我们已经对软聚类模块 $pleft(c_{i} mid v_{i}right)$ 和聚类感知识别器 $pleft(s_{i} mid v_{i}, c_{i}right)$ 进行了建模，因此ClusterSCL 可以建模为以下实例识别任务：
$pleft(s_{i} mid v_{i}right)=int pleft(c_{i} mid v_{i}right) pleft(s_{i} mid v_{i}, c_{i}right) d c_{i} quadquadquad(8)$
Inference and Learning
实际上，由于对数操作内的求和，最大化整个训练数据的对数似然值是不平凡的。我们可以采用 EM 算法来解决这个问题，其中我们需要计算后验分布：
${large pleft(c_{i} mid v_{i}, s_{i}right)=frac{pleft(c_{i} mid v_{i}right) pleft(s_{i} mid v_{i}, c_{i}right)}{sumlimits _{m=1}^{M} pleft(m mid v_{i}right) pleft(s_{i} mid v_{i}, mright)} } quadquadquad(9)$
然而，由于对整个节点的求和 $sumlimits _{v_{j} in V backslashleft{v_{i}right}} exp left(mathbf{h}_{i}^{top} tilde{mathbf{h}}_{j} / tauright)$，计算后验分布是禁止的。我们最大化了由以下方法给出的 $log pleft(s_{i} mid v_{i}right)$ 的 evidence 下界(ELBO)：
${large begin{array}{l}log pleft(s_{i} mid v_{i}right) &geq mathcal{L}_{operatorname{ELBO}}left(boldsymbol{theta}, mathbf{w} ; v_{i}, s_{i}right)\&begin{aligned}:=& mathbb{E}_{qleft(c_{i} mid v_{i}, s_{i}right)}left[log pleft(s_{i} mid v_{i}, c_{i}right)right] -operatorname{KL}left(qleft(c_{i} mid v_{i}, s_{i}right) | pleft(c_{i} mid v_{i}right)right)end{aligned}\end{array}} quadquadquad(10)$
其中 $qleft(c_{i} mid v_{i}, s_{i}right)$ 是一个近似后 $pleft(c_{i} mid v_{i}, s_{i}right)$。ELBO的推导在附录a中提供。在这里，我们将变分分布形式化为：
${large qleft(c_{i} mid v_{i}, s_{i}right)=frac{pleft(c_{i} mid v_{i}right) tilde{p}left(s_{i} mid v_{i}, c_{i}right)}{sumlimits _{m=1}^{M} pleft(m mid v_{i}right) tilde{p}left(s_{i} mid v_{i}, mright)}} quadquadquad(11)$
其中 $tilde{p}left(s_{i} mid v_{i}, c_{i}right)=exp left(mathbf{h}_{i}^{top} tilde{mathbf{h}}_{s_{i}} / tauright) / sum_{v_{j} in B backslashleft{v_{i}right}} exp left(mathbf{h}_{i}^{top} tilde{mathbf{h}}_{j} / tauright)$ 在一个批次 $B$ 内计算。请注意，$v_{i}$ 和 $v_{s_{i}}$ 都在该批处理中。此外，我们应用 $tilde{p}left(s_{i} mid v_{i}, c_{i}right)$ 来估计 $text{Eq.10}$ 中的 $pleft(s_{i} mid v_{i}, c_{i}right)$、并在附录B中作出说明。
我们通过一种变分EM算法来优化模型参数，其中我们在 E 步推断 $qleft(c_{i} mid v_{i}, s_{i}right)$，然后在 M 步优化ELBO。对一批节点进行采样，我们可以最大化以下目标：
${large mathcal{L}_{mathrm{ELBO}}(boldsymbol{theta}, mathbf{w} ; B) approx frac{1}{|B|} sumlimits _{v_{i} in B} frac{1}{left|S_{i}right|} sumlimits _{s_{i} in S_{i}} mathcal{L}_{operatorname{ELBO}}left(boldsymbol{theta}, mathbf{w} ; v_{i}, s_{i}right) } quadquadquad(12)$
我们观察到，只有对集群原型使用随机更新才能得到平凡的解决方案，即大多数实例被分配给同一个集群。为了缓解这一问题，我们在每个训练阶段后应用以下更新：
${large mathbf{w}_{m}=frac{1}{left|bar{V}_{m}right|} sumlimits_{v_{i} in bar{V}_{m}} mathbf{h}_{i}, m=1,2, cdots, M } quadquadquad(13)$
其中，$bar{V}_{m}$ 表示由 METIS 导出的第 $m$ 个图社区中的节点集。在训练之前，我们根据节点间的互连将整个图 $G$ 划分为 $M$ 个图社区。我们使用社区来粗略地描述集群，并对每个社区中的节点嵌入进行平均，以在每个训练阶段后更新集群原型。请注意，ClusterSCL 采用了 $Eq. 7$，为每个节点推导出一个细化的软集群分布。METIS 输出的硬集群分布仅用于原型更新。此外，我们观察到需要对 $kappa$ 进行细粒度搜索，这是低效的。根据经验，我们使用一个小的 $kappa$ 来推导一个相对可靠的聚类预测，并引入一个熵项来平滑预测的聚类分布。通过这样做，我们可以避免在 $kappa$ 上的细粒度搜索。最后，将 ClusterSCL 损失函数形式化为：
${large mathcal{L}(boldsymbol{theta}, mathbf{w} ; B)=-mathcal{L}_{mathrm{ELBO}}(boldsymbol{theta}, mathbf{w} ; B)+frac{eta}{|B|} sumlimits _{v_{i} in B} sumlimits _{c_{i}=1}^{M} pleft(c_{i} mid v_{i}right) log pleft(c_{i} mid v_{i}right)} quadquadquad(14)$
其中，$eta in(0,1]$ 为控制平滑强度的熵项的权值。
Algorithm 1 显示了使用Clusterscl进行训练的伪代码。我们在附录C中提供了 ClusterSCL 的复杂性分析。
实验通过回答以下研究问题来展开：（1）ClusterSCL 如何在节点分类任务上执行？（2）CDA是否生效？（3）ClusterSCL 在不同大小的标记训练数据下表现如何？
节点分类
CDA 有效性验证
在不同大小的标记训练数据下的 ClusterSCL 的研究
这项工作初步研究了用于节点分类的图神经网络的监督学习。我们提出了一种简单而有效的对比学习方案，称为聚类感知监督对比学习(聚类scl)。ClusterSCL改进了监督对比(SupCon)学习，并强调了在SupCon学习过程中保留内在图属性的有效性，从而减少了由类内方差和类间相似性引起的负面影响。ClusterSCL比流行的交叉熵、SupCon和其他图对比损失更具有优势。我们认为，ClusterSCL的思想并不局限于图上的节点分类，并可以启发表示学习的研究。
