论文阅读：A contrastive variational graph auto-encoder for node clustering

摘要

变分图自编码器（VGAEs）已广泛应用于解决节点聚类任务。然而，现有的最先进方法仍面临诸多挑战。首先，现有的VGAE模型在引入聚类归纳偏置后，未能考虑推断模型和生成模型之间的差异。其次，当前模型容易产生退化解，使得潜在代码与先验模型匹配，而与输入信号无关（即后验崩塌）。第三，现有的VGAEs忽视了噪声聚类分配的影响（即特征随机性）以及聚类与重建之间强烈权衡的影响（即特征漂移）。为了解决这些问题，作者在对比学习设置中提出了一个变分下界。与相应的证据下界（ELBO）相比，作者的下界是对对数似然函数的更紧密近似。得益于新发现的项，作者的下界能够避免后验崩塌，并具有更多的灵活性来考虑推断模型和生成模型之间的差异。此外，作者的解决方案通过两种机制来控制特征随机性和特征漂移之间的权衡。大量实验表明，所提出的方法在多个数据集上取得了最先进的聚类结果。我们提供了有力证据，证明这一改进归因于四个方面：集成对比学习、缓解特征随机性、特征漂移和后验崩塌。

引言

图是最常用的数据结构之一，用于表示和提取知识。图分析的重要性得到了广泛应用的支持，例如社区检测[1,2]、基于骨架的动作识别[3]和药物发现[4]。图结构数据的复杂性阻碍了许多主要针对欧几里得数据设计的机器学习技术的直接应用。在这种背景下，神经网络的表示能力被逐步引入图结构数据中。在过去几年中，已提出多种图神经网络（GNNs）用于解决监督学习问题。然而，大量图数据在实际应用中仍然未标注。与监督学习不同，非监督学习方法不需要昂贵的数据标注来训练图神经网络。在这种背景下，深度聚类作为一种新的范式应运而生，用于执行联合聚类和嵌入特征学习。本质上，深度聚类范式通过两种主要策略来弥补训练标签的缺失：自监督和伪监督。自监督的主要思想是执行一个精心设计的前置任务，涉及学习高级表示。与自监督不同，伪监督通过识别输入数据的语义类别来解决主要任务。更准确地说，它通过对潜在表示应用聚类算法来构建伪标签，然后利用获得的标签来训练模型。

正如Zhang等人[5]所示，神经网络可以在不显著增加时间开销的情况下完美拟合随机标签。因此，在训练过程中识别伪标签中的错误标签是一个具有挑战性的任务。此外，最近的研究[6]发现，在使用伪标签训练后，即使模型仅使用真实标签重新训练，也无法消除噪声标签的影响。伪监督所带来的累计误差导致了特征随机性（FR）[7]。

一种缓解特征随机性影响的可能解决方案是根据自监督调整伪监督损失的梯度。图自监督学习依赖于几种策略。随机游走[8]、邻接重构[9]和互信息最大化[10]是节点聚类的主要自监督技术。所有这些策略可以统一到成对学习框架下，该框架通过训练编码器将相似的成对节点投射到一起，从而捕获高级相似性。对比学习[11]是成对学习框架的特定案例；它具有额外的能力，将不相似的成对节点推得远远的。作者将现有的自监督方法根据成对学习任务的粒度划分为四个类别：节点级、邻接级、聚类级和图级。

受计算机视觉中实例级对比学习成功的启发，节点级对比学习为图数据集建立了相同的思想。它通过将同一节点在两个视图中的潜在代码拉近来进行。新的图是通过应用增强技术获得的。然而，图增强方法提供的语义不变性有限（它们可能任意行为并改变图的语义）[12]，高度依赖于数据集[13]，并且对增强方案的超参数非常敏感[13]。此外，节点级对比学习通过将除目标节点外的所有节点视为负样本，忽视了聚类级别的信息。

随机游走和邻接重构是邻接级自监督方法，它们将邻居节点（不一定是第一阶邻居）的表示编码到一起，并将其他节点的表示推得远远的。在我们之前的工作[14]中，我们已经表明，邻接重构相当于一个加权图邻接系数的成对损失和一个正则化项。类似地，执行短随机游走捕获了图的邻接结构属性。例如，DeepWalk[8]使得同一短游走中的节点具有相似的嵌入，并使用噪声对比估计[15]将这些表示与其他节点的表示进行对比。然而，随机游走和邻接重构都有已知的局限性。这两种策略过于强调可能被图卷积操作捕捉到的邻接信息。此外，基于随机游走的方法对超参数的选择非常敏感[8]。

图级对比学习通过使用读出函数构建图的摘要。然后，它利用该摘要帮助编码器构建潜在代码，关注图的全局特征。此类别的主要过程包括最大化每个节点与图级轮廓之间的相似性，并将此轮廓与扰动后的潜在代码进行对比。然而，这种策略忽视了细粒度的结构。对于聚类任务，学习聚类导向的表示至关重要[16]。

节点级、邻接级和图级自监督技术不足以解决聚类任务。相反，这些策略用于预训练模型，并作为辅助目标来减少特征随机性的影响。然而，结合伪监督和自监督会导致两者任务之间的强烈权衡。伪监督学习的判别性特征容易受到自监督引起的漂移效应的影响。这一问题被称为特征漂移（FD）[7]。例如，聚类目标旨在减少每个聚类的方差，而节点级任务将同一聚类中的所有节点视为负样本。此外，伪监督与自监督之间的激烈竞争增加了对平衡超参数的敏感性[7]。

与几种自监督技术不同，变分图自编码器（VGAEs）具有坚实的概率基础。由于后验分布是不可处理的，因此应用变分方法来逼近真实后验。引入了由编码网络参数化的可微且可处理的变分后验，以推导出ELBO。现有VGAE模型的典型下界通常包括重建项和正则化项。正则化是基于Kullback-Leibler（KL）散度，衡量先验与变分后验之间的差异。

不幸的是，ELBO的学习能力受限于后验崩溃（PC）问题[17]。最小化正则化项使得变分后验与先验匹配，而不依赖于输入变量，这导致了一个退化的局部最小值。在这种情况下，解码器学习从完全随机的噪声中重建输入。ELBO的另一个局限性是，最大化这一项等价于最小化真实后验与变分后验之间的KL散度。这是一个强假设，因为变分后验受到以下：（1）编码灵活性，（2）为了确保可处理性，在条件共轭指数分布族内，以及（3）在训练过程中需要与先验分布匹配，这由正则化项引起。因此，假设一个好的变分下界应考虑真实后验与变分后验之间的差异。最后，ELBO目标无法建立对比学习框架，而这是最近方法的主要策略。

之前的VGAEs[18]通过利用Jensen不等式来获得ELBO。在本工作中，提出了一个更紧的变分下界。更准确地说，构造了一个可处理且可微的项，用以考虑推理模型与生成模型之间的差异。这个新项来源于应用Jensen不等式时丢弃的量（即，真实后验与变分后验之间的KL散度）。因此，它可以使变分后验（聚类任务的判别方面）与真实后验（生成方面）相区分。它还通过引入负样本建立了一个对比学习框架。方法的另一个有趣方面是能够处理PC问题。典型的VAE没有任何机制来避免PC。例如，[19]的作者提出通过将互信息与ELBO结合来避免这个问题。通过引入外部损失函数，[19]的最终目标不再能保证是数据对数似然的下界。此外，[19]中需要额外的超参数来控制两个组件之间的权衡。在作者的情况下，通过实验证明，新发现的项有助于解决PC问题。

节点级、邻接级和图级对比学习策略未能考虑聚类级别的信息。为此，提出了一种变分自编码器，逐步从邻接级学习转向聚类级学习。基于训练过程中构建的面向聚类的图，逐步形成潜在聚类，并将学习到的表示与锚图中的表示进行对比。此外，提出的模型配备了两种机制，以减轻FR和FD的影响。在之前的工作[14]中，提出为图自编码器提供两种操作符，可以控制FR和FD之间的权衡。在本工作中，证明这些操作符可以在最大化图对数似然的变分框架内得到解析推导。其他控制FR和FD的机制可以自然地集成到我们的变分框架中，同时仍然优化相同的目标函数（即，图对数似然）。方法的优点可以从三个角度描述：

• 变分图自编码器：提出了一种新的图对数似然的变分下界，推广了ELBO。与现有VGAEs相比，解决方案有三个优势。首先，作者的下界与对比学习一致。其次，它构成了一个比对应ELBO更紧的下界。第三，作者下界中的新项可以减轻PC问题，并为考虑真实后验与变分后验之间的差异提供更大的灵活性。

• 对比学习：提出了一种面向聚类的对比学习方法，偏离了节点级、邻接级和图级方法。模型有两个操作符来减轻FR和FD的影响。这些操作符在最大化对数似然函数的变分框架下得到解析推导。 • 实验：进行了广泛的实验，以探索我们方法相较于（1）现有VGAE模型和（2）对比学习策略的优势。结果提供了有力的证据，表明提出的方法在聚类效果上带来了显著的改进，并缓解了FR、FD和PC问题。

模型

模型提出了一种将对比学习和变分自编码器统一视角的方法，用于最大化数据的似然。对于矩阵 M，表达式 M[i, ⁣:]表示矩阵的第 i 行，而 M[ ⁣:,j]表示矩阵的第 j 列。给定一个无向属性图 G=(V,E,X)，其中 V={v1,v2,…,vN}是 N 个节点的集合，E={eij,1≤i,j≤N}是边的集合，X∈RN×J是特征矩阵。向量 xi∈RJ表示与第 i 个节点关联的特征向量，J 是输入空间的维度。图 G的拓扑由邻接矩阵 A=(aij)∈RN×N捕捉，其中 aij=1如果 (vi,vj)∈E，否则 aij=0。我们用 D 表示 A 的度矩阵，其中 D=diag(d1,…,dN)，且 d_i = \sum_{j=1}^{N} A_{ij}。认为图 G的节点可以分为 K 个簇。向量 C∈{1,…,K}N 定义了不同节点的簇归属关系，其中 ci表示第 i 个节点的簇。

CVGAE（对比变分图自编码器）方法包含两个组件：一个图卷积编码器 [46]，记作 E，和一个解码器，记作 U。编码器将输入图映射到一个低维矩阵 Z∈RN×d，其中 d 是潜在空间的维度。潜在表示的计算根据逐层传播规则进行：

其中 Z(l)和 W(l)分别表示第 l 层的输出和权重矩阵，且 Z(0)=X。函数 ϕ表示该层的激活函数。拉普拉斯平滑通过矩阵\tilde{A} 和 \tilde{D} 定义，其中\tilde{A} = A + I_n 和 \tilde{D} = D + I_n。设 W={W(l)} 为所有可训练权重的集合。编码器由两层组成，具体为：

模型有两个训练阶段。第一阶段是最大化与\mathcal{N}-VGAE 相似的 ELBO。为了使本工作自成一体，作者提供了预训练阶段的完整描述。然而，作者的贡献主要与聚类阶段相关。

预训练

假设图的拓扑结构可以通过一个涉及分布 𝑝(𝐴𝑔𝑒𝑛, 𝑍) 的随机过程生成，其中 𝐴𝑔𝑒𝑛 是生成的图结构。这个分布可以分解为 𝑝(𝐴𝑔𝑒𝑛, 𝑍) = 𝑝(𝐴𝑔𝑒𝑛 | 𝑍) 𝑝(𝑍)，其中：

其中 𝑝(𝑎𝑔𝑒𝑛_{𝑖𝑗} | 𝑧𝑖, 𝑧𝑗) 是一个伯努利分布 Bern(𝛽𝑖𝑗)，其中 𝛽_{𝑖𝑗} = Sigmoid(𝑧𝑖^T 𝑧𝑗) 用于每个生成的边。在预训练阶段，我们设置 𝐴𝑔𝑒𝑛 = 𝐴。先验分布 𝑝(𝑍) 可以基于潜在变量的性进行分解，因此每个 𝑝(𝑧𝑖) 表示一个高斯分布 N(𝑧𝑖∣0,𝐼)。

变分自编码器的一般框架包括最大化输入数据的对数似然。由于后验分布是不可处理的，典型的变分方法旨在逼近真实的后验分布。具体来说，一个由编码网络参数化的明确定义的变分后验 q(𝑍∣𝑋,𝐴)形成了推断模型，并用于这种逼近。分布 q(𝑍∣𝑋,𝐴) 可以表示为：

其中

基于推断和生成分布 q(𝑍∣𝑋,𝐴) 和 p(𝐴𝑔𝑒𝑛,𝑍)提供的分解和说明，生成图的对数似然可以表示为：

其中 \mathcal{L}_{\text{ELBO}_{\text{pre}}}(𝑋, 𝐴)表示预训练阶段的ELBO。 \mathcal{L}_{\text{ELBO}_{\text{pre}}}(𝑋, 𝐴)的第一项表示邻接矩阵的重构，第二项表示正则化，用于对潜在空间施加特定结构，从而确保生成任务的简单采样。项 KL(q(𝑧𝑖,𝑧𝑗∣𝑋,𝐴)∣∣p(𝑧𝑖,𝑧𝑗∣𝑎𝑔𝑒𝑛𝑖𝑗)) 吸收了真实后验和变分后验之间的差异。由于KL散度始终是正值，因此可以看到 LpreELBO(𝑋,𝐴) 是 log⁡(p(𝐴𝑔𝑒𝑛)) 的下界。

3.2 聚类

在第一阶段中，学习了变分后验分布，以近似真实的后验分布，而无需强加聚类结构。然而，引入聚类归纳偏差（inductive bias）会导致推断模型和生成模型之间产生差异。为了解决这个问题，作者引入了第二阶段的训练，使变分后验分布在不影响解码过程的前提下，摧毁非判别性信息。更具体地，推导出一个新项，用于吸收推断模型与生成模型之间的差异。基于这一新项，解码过程可以恢复被编码过程摧毁的非判别性信息。为实现这一目标，首先介绍聚类阶段的推断模型和生成模型，然后推导下界公式。

生成模型旨在捕获联合分布 p(Agen,Z,C)。与预训练阶段相比，该模型拥有两个任务头，分别处理图生成和聚类任务。因此，分布 p(C∣Z)定义如下：

其中 pij=p(ci=j∣zi)，\{\Omega_j\}_{j=1}^K 表示可训练的聚类中心集合。聚类中心使用 k-均值算法初始化。分布 p(ci∣zi)计算软聚类分配，在公式 (11) 中使用学生 t分布来评估潜在编码和聚类中心之间的相似性。

推断模型捕获分布 q(Z,C∣X,A)q(Z, C | X, A)。与预训练阶段相比，我们的模型除了推断潜在编码外，还推断每个节点的聚类标签。因此，联合分布被分解为：
q(Z,C∣X,A)=q(Z∣X,A),
其中 q(Z∣X,A)保留了预训练阶段定义的分布（公式 (7)）。分布 q(C∣Z)描述如下：

其中 qij=q(ci=j∣zi)。分布 q(ci∣zi)通过将软聚类分配转化为硬分配，增强了判别性特征。这种方法逐步减小了簇内方差并增大了簇间方差。具体而言，我们比较了 p(ci∣zi)的第一和第二高置信分配分数之间的差值 (λ1i−λ2i) 与超参数 α，以逐步构建 q(ci∣zi)q的硬聚类分配。节点 i 的第一和第二分数分别定义为：

根据推断和生成分布 q(Z,C∣X,A)的分解与定义，发现聚类阶段的证据下界（ELBO）为：

相比预训练阶段的下界，新的下界公式多出了一项，即聚类目标，该目标附带一种对抗伪代表性的机制。特别地，它促使具有较大第一与第二高置信分配分数差值的节点的聚类分配更接近目标分配。设 Θ(t)={i∈V∣(λ1i−λ2i)≥α}为迭代 t 中聚类分配可靠的节点集合。基于之前迭代中学习到的判别特征，该集合会逐渐扩展，包含更多可靠节点。

现有的证据下界不足以支持对比学习，而对比学习是无监督学习的最先进策略。为弥补这一差距，作者通过发展基于证据下界 (ELBO) 方法所丢弃的项，分析性地为变分自编码器 (VAE) 建立了一个对比框架。研究从定义正负信号开始。

从原始图 G 构造了两个属性图：Gₚₒₛ 和Gₙₑ₉。第一个图Gₚₒₛ 的邻接矩阵为 𝐴ₚₒₛ = (𝑎ₚₒₛᵢⱼ) ∈ Rᴺ×ᴺ，特征矩阵为 𝑋ₚₒₛ；第二个图 Gₙₑ₉ 的结构为 𝐴ₙₑ₉ = (𝑎ₙₑ₉ᵢⱼ) ∈ Rᴺ×ᴺ，特征矩阵为 𝑋ₙₑ₉。

将 𝑋ₚₒₛ 设为 𝑋，并通过逐步变换原始图结构构建一个面向聚类的图结构 𝐴ₚₒₛ。所采用的方案包括根据可靠节点的聚类分配添加和删除边。具体而言，删除连接不同聚类节点的边，同时在每个聚类的中心节点与同一聚类的其他节点之间添加缺失的边。聚类中心节点通过寻找最近邻于潜在中心的节点索引来确定。需要注意的是，仅对节点集 𝛩 中的节点进行上述操作（即添加和删除边）。构建 𝐴ₚₒₛ 的函数 𝛶 提供在附录 D 中。

对于第二个图，设置 𝑋ₙₑ₉ = 𝑋 和 𝐴ₙₑ₉ = 𝐴，以对比面向聚类的图和原始图。

除了输入图 Gₚₒₛ 和 Gₙₑ₉，还构建了第三个图 Gₑₙ，作为解码过程的自监督信号。该图由邻接矩阵 𝐴₉ₑₙ = (𝑎₉ₑₙᵢⱼ) ∈ Rᴺ×ᴺ 定义。与预训练阶段不同，解码器并不重建原始图。相反，模型被训练为构建一个增强的图结构，以适应聚类任务。具体而言，构建 𝐴₉ₑₙ 的方案与构建 𝐴ₚₒₛ 时的操作类似，逐步添加边以增加聚类内的相似性，从而减小聚类-重构权衡引起的频率偏差 (FD) 影响。然而，作者避免删除边，以保留聚类间的相似性，这对于生成过程至关重要。构建 𝐴₉ₑₙ 的函数 𝛹 在附录 E 中概述。

在指定了编码和解码模型，以及输入和自监督信号后，作者根据定理 1（证明见附录 C），推导了生成图对数似然的对比变分下界。

实验

文中涉及了很多推导，要仔细推才行。。。