基于全局对抗负样本的图对比学习方法

岑科廷,沈华伟,曹 婍,徐冰冰,程学旗

(1.中国科学院 计算技术研究所 数据智能系统研究中心,北京 100190;2.中国科学院大学,北京 101408;3. 中国科学院 计算技术研究所 网络数据科学与技术重点实验室,北京 100190)

0 引言

图表示学习期望给每个节点学到保留图结构和节点属性的低维表示[1]。这类方法在很多重要的图分析任务上取得了显著的成果,例如,节点分类[1]、链路预测等[2]。最近,基于图对比学习的节点表示学习方法展现了前所未有的性能[3-5],正在成为该领域的主流方法。

图对比学习期望通过拉近正样本对之间的距离,推远负样本之间的距离来为每个节点学习表示[6-8]。传统的图对比学习方法将同一个节点经过两种不同数据增强后得到的节点视为正样本对,将其与图上其它节点都视为负样本对[3](图1(a))。由于每个节点都将其余节点视为负样本,因此这类方法的时间复杂度是关于节点数的平方,导致此类方法难以被应用到实际场景中。

图1 负样本选择方式对比

为了降低时间复杂度,一种直观的方式是给每个节点选择一些节点作为负样本。具体来说研究者们试图通过随机采样特定个负样本的方式加速模型[9](图1(b))。该方法将所有负样本视为同等重要,并通过均匀采样的方式为每个节点生成对应的负样本。然而,该方法已经被证实需要大量的负样本才能使模型达到较好的效果[10]。

为了提升图对比学习方法的性能和效率,一些方法改进了负样本选择的策略。最近的一些工作从理论和实验上发现难的负样本(即难以与正样本对区分的样本)有助于学习更强大的表示。因此,大量现有方法希望启发式地为每个节点选择若干难的负样本(图1(c))。常见的选择标准有节点间路径长度[10-11]和节点表示间的余弦相似度[10]等。基于节点间路径长度的标准认为,距离目标节点越近的节点,作为负样本的重要性越高。而基于节点表示间的余弦相似度的标准认为,与目标节点表示的余弦相似度越大的节点,作为负样本的重要性越高。然而,这类启发式定义的重要性度量标准无法保证选出来的负样本对于模型是难的。同时这些方法在为每个点筛选负样本时,需要计算其与图上所有其它节点之间的相似度,并进行排序选择前K个节点,引入了额外的时间复杂度。

为了解决上述问题,本文提出基于全局对抗负样本的图对比学习方法。通过将负样本参数化,直接学习模型需要的难负样本。通过最大化模型损失函数,更新该负样本参数,不再需要通过人为先验来进行启发式选择。同时,与之前方法分别为每个节点构建难负样本不同,我们为所有节点学习一个全局的负样本(图1(d)),从而显著提高了效率。另一种有效的方式是为每个节点都学习一个负样本,然而这样会引入大量的参数,导致过拟合问题,同时也带来了高昂的内存代价。因此我们选择为所有节点学习一个共享的全局的负样本。具体来说,我们将同一个节点在两个不同增强图上的表示作为正样本对,将节点与待学习的全局负样本视为负样本对。受Hu等人[12]的启发,我们通过将模型形式化成一个最大最小化问题进行求解。具体来说,我们的模型包含两个互相对抗的参与者: 待学习的全局负样本和将每个节点映射到隐层表示空间的图编码器。我们通过交替优化的方式更新图编码器的参数和全局负样本的参数。一方面,我们固定全局负样本表示,通过最小化对比损失来训练图编码器,即鼓励模型能正确区分正负样本对。另一方面,我们固定图编码器参数,通过最大化对比损失来更新全局负样本,即产生让模型无法分对的最难的负样本。

此外,本文进一步对提出的方法进行了深入分析,发现更新全局负样本的梯度为图中所有节点表示的加权线性组合。同时证明,最小化与该全局负样本的对比损失函数等价于最大化图上节点之间的加权平均距离。多个基准数据集上充分的实验结果证明了我们模型的有效性和效率。

1 相关工作

1.1 传统图表示学习

图表示学习旨在为每个节点学习一个保留网络结构性质或者节点属性的低维节点表示。 以前的方法通常通过解决一个预定义任务来学习节点表示[13]。 大多数传统的网络嵌入方法采用结构重建[14-15]或属性预测[16-17]作为预定义任务。

结构重构任务期望利用节点表表示H恢复某些结构相关的矩阵,例如,邻接矩阵A[14]。GAE[14]利用图卷积神经网络将节点的结构和属性映射到隐层表示空间,同时利用节点vi和vj表示的点积来重构他们之间的连边概率A′ij。GAE通过约束重构的邻接矩阵A′尽可能和输入的邻接矩阵A保持一致来训练模型。

基于属性重构的网络表示学习方法,将利用节点表示H重构输入属性矩阵X作为目标训练模型[16-17]。例如,ANRL[17]将节点的邻接矩阵A作为输入,经过多层自编码器后输出预测的节点属性矩阵X′,通过约束输出属性矩阵X′尽可能接近输入属性X来训练表示学习模型。

1.2 图对比学习

最近,图对比学习已成为无监督图表示学习中最受关注的一种技术。图对比学习期望学到一个表示学习模型,使得相似的节点(正样本)得到相似的表示,不相似的节点(负样本)得到差异较大的表示[3-8,18]。

传统的图对比学习将所有负样本视为同等重要,其不同点在于对正样本的定义。例如,GRACE[3]将同一节点的不同增强版本定义为正样本对,而将图上剩下其它所有节点都当成负样本。DGI[19]将图表示和图上节点表示视为正样本对,将图表示和随机打乱后图上节点表示视为负样本对。

最近一些方法通过启发式的方式来定义重要的负样本,从而提升图对比学习的效果。例如,Yang等人[9]认为节点的度反映其作为负样本的重要性,因此该方法提出负样本的采样概率与其度成正比,即度越大的节点越重要。GraphCL[10]定义负样本节点与目标节点的余弦相似度为其重要性,对于每个节点利用余弦相似度挑选最像的K个节点作为负样本。Kalantidis等人[20]提出利用得到的负样本进行线性混合,生成更难的负样本。

此外,近些年图对比学习在可解释性和数据增强方式上也有新的进展。DGCL[21]利用解耦表示提升了图对比学习的可解释性。ARIEL[22]利用对抗训练的方式生成增强样本。

2 模型

本节首先回顾传统图对比学习,分析它的局限性,并介绍我们工作的动机。之后详细介绍我们模型的框架,以及如何更新模型的参数和我们的全局负样本。最后,通过分析更新全局负样本的梯度,更好地揭示了模型背后的含义。

2.1 动机

(1)

现有方法通过均匀采样的方式从图上采样负样本,即每个点被当成负样本的概率相同。由于采样过程与模型无关,难以保证采样到的负样本对于模型是难的。因此现有方法往往需要较大的负样本个数K,例如,GRACE将图上所有其它节点视为负样本即K=N,使得模型具有较高的时间复杂度。最近,Hafidi等人[11]将余弦相似度定义为负样本的重要性,通过并依此为每个节点筛选负样本。然而启发式定义的余弦相似度并不能真正反映负样本的重要性。同时由于需要在迭代中对节点按余弦相似度排序,使得模型又引入了额外高昂的时间代价。为了克服上述困难,我们提出直接学习全局负样本。即通过对抗训练学到使得图对比学习模型损失函数最大的全局对抗负样本。考虑到该负样本是基于全局损失函数学到的,因此该负样本兼顾了所有节点需要的负样本的性质,我们让所有节点共享该负样本,因此将负样本个数降低为1,极大地提升了模型的效率。

2.2 基于全局对抗负样本图对比学习

本节形式化地介绍基于全局对抗负样本图对比学习的节点表示学习方法ANGCL。

2.2.1 模型框架

如图2所示,我们的ANGCL模型包含两个对抗性参与者: 图编码器θ和可学习的全局负样本n。图编码器旨在通过最小化对比损失来学习将正样本与负样本区分开来的节点表示。而全局负样本n则是指最容易让模型做错的负样本,即最大化对比损失的负样本。我们将求解图编码器θ和对抗负样本n的过程抽象成最大最小化问题,其形式化如式(2)所示。

图2 ANGCL模型框架图

(2)

其中,θ*表示最优的图编码器的参数,n*表示最优的全局负样本,L(θ,n)是对比损失函数。正如许多现有的对抗性训练算法所示,找到此类问题的鞍点既困难又耗时[12,23]。 因此,我们采用了被广泛使用的快速梯度法[23],通过交替更新它们,直到收敛。即在更新图编码器参数时,保持全局负样本不变。在更新全局负样本时,保持图编码器参数不变。该过程形式化为以下等式:

其中,ηθ和ηn分别是更新图编码器θ和全局负样本n的学习率。下文将详细介绍图编码器的实现,以及全局负样本更新的具体形式及其意义。

2.2.2 图编码器实现

如图2所示,对于一张图我们首先通过数据增强函数t1和t2,分别生成对应的增强图(A(1),X(1))和(A(2),X(2)),之后通过图编码器θ得到对应的节点表示。

为了公平对比,我们使用与之前的方法相同的数据增强函数。增强函数包含两个算子,连边去除和特征掩蔽。连边去除通过随机丢弃一些边来生成增强图。具体来说,对于每条边,我们随机生成一个遵循伯努利分布B(1-pe)的指示Re。其中,pe是边移除的概率。如果Re=1,则删除边e以生成增广图。类似地,我们生成一个遵循伯努利分布B(1-pf)的指标Rf,pf表示特征掩蔽的概率。如果Rf=1,我们将图中所有节点的特征f设置为零。t1和t2的区别在于概率pe和pf不同。图编码器θ用于将每个节点嵌入到隐藏空间中,可以使用任何图神经网络[24-26]来构建。为了同之前的方法进行公平的对比,我们采用与其相同的架构,即堆叠两层 GCN[24]以形成图形编码器。具体来说,它形式化为:

(5)

2.2.3 负样本更新

首先,我们给出模型对比损失函数的定义。与之前的方法不同,ANGCL通过约束同一节点在不同增强图(A(1),X(1))和(A(2),X(2))中的表示相近,与全局负样本表示n相远来实现,其形式化如式(6)所示。

(6)

(7)

如果我们将左侧的分式子视为权重,即

(8)

那么,全局负样本更新的梯度可以视为对图上所有节点表示的线性组合,其形式化如式(9)所示。

(9)

由上述公式可知,我们的全局负样本是沿图上所有节点表示加权平均的方向更新。其中每个节点的权重wi由其与当前全局负样本的相似度和其与正样本的相似度一同决定的。换句话说,一个节点表示与当前全局负样本的相似度相比于该节点与对应正样本的相似度越大,则它对更新全局负样本的贡献就越大。即那些难以将全局负样本与其正样本区分开的节点,对与全局负样本的更新贡献更大。按此方式更新后的全局对抗样本对于模型更具有挑战性,因为对于每个节点都难将其与正样本区分开。将该全局负样本用于图编码器的参数更新,可以进一步提升图编码器的质量,得到在下游任务表现更好的节点表示。

2.3 时间复杂度对比

本节分析了我们的模型和基于图对比学习的基准方法GRACE和GraphCL的时间复杂度。

首先所有模型都采用了相同的数据增强方式,连边去除和特征掩藏,其时间复杂度为O(E+F)。此外所有模型的编码器采用了相同的结构,即图卷积神经网络[14],其时间复杂度为O(lEF+lNF2)。其中,l表示图卷积神经网络的层数,E表示图上的连边数,N表示节点数,F表示特征维度,我们假设每层输出的表示维度不变。

下面介绍各方法损失函数的时间复杂度。GRACE[3]对于每个节点将图上剩下所有节点视为负样本,因此在计算损失函数时依赖于所有节点对,其时间复杂度为O(N2)。若GRACE采样K个负样本,则其时间复杂度降低为O(KN),我们将该模型记做GRACE(K)。然而在实验中发现,随着负样本数K减少,GRACE(K)效果显著下降。GraphCL[11]对于每个点选择最相似的K个负样本,因此其损失函数时间复杂度为O(KN)。然而对于每个点挑选其对应K个负样本的过程中,依赖于对剩下所有点计算相似度,同时对结果进行排序,因此其时间复杂度为O(N+NlogN)。图上共有N个节点,因此GraphCL损失函数总时间复杂度为O(KN+N2+NlogN2)。我们的ANGCL只有一个负样本,因此其损失函数时间复杂度为O(2N)。虽然我们引入了额外的更新对抗负样本的时间复杂度,但是由于每轮迭代更新的梯度为所有节点表示的线性组合,即这部分的时间复杂度为O(N)。所有方法的时间复杂度总结如表1所示。我们发现我们方法的时间复杂度与采样版的图对比学习方法GRACE(K)相当,且低于其它方法。

表1 方法时间复杂度对比

2.4 模型分析

根据2.2.3节我们可以得到全局负样本的更新方式,本节将分析该负样本对模型的意义。

(10)

其中,C是常数项。我们发现最小化该损失函数等价于最大化图上所有节点对之间的加权距离。

定理1:L′(θ)是所有节点对之间的加权距离和的上界。

证明:

根据定理1,可以得出最小化与我们的全局负样本的对比损失函数等价于最大化所有节点对之间的加权距离,其权重为节点参与更新全局负样本梯度的权重。即如果两个点都很靠近当前的全局负样本,则会给这两个点较大的权重,从而让模型更关注于将这两个节点推开。

同时,我们发现该损失函数与节点分布的均匀性之间存在关联。均匀性是指学到的节点表示均匀分布在球面上,从而保留最大的信息量。均匀性的形式化度量如式(11)所示。

(11)

该式子要求任意两个节点表示之间尽可能分开,且任意节点之间的重要性相同。一些研究者指出,传统图对比学习方法[27-28],通过推远与所有负样本之间的距离实现了均匀性[29]。这类传统的图对比学习方法将所有节点视为同等重要,而我们的模型相当于实现了加权的均匀性。同时当所有的权重wi=1时,我们的模型退化成了传统的图对比学习方法。

3 实验

本节我们对提出的ANGCL模型进行实验,并将其与现有的无监督表示学习方法在节点分类任务上进行比较。最后,我们进一步深入探讨、分析了模型的有效性。

3.1 实验细节设置

本节首先介绍数据集、基准方法以及实验的基本设置。

3.1.1 数据集

本文使用7个广泛使用的具有节点分类任务的基准数据集的基线[3,30]。Cora、Citeseer、Pubmed是三个引用网络,其中每个节点表示一篇论文,每条边表示一个引用关系。Amazon Computers(Am.C)、Amazon Photos(Am.P)是从亚马逊共同购买图中提取的,其中节点代表产品,边代表经常一起购买的成对商品。Coauthor CS(Co.CS)、Coauthor Physics(Co.Phy)是共同创作的图表,其中节点代表作者,而作者之间的边则代表共同撰写的论文。上述数据集的统计信息如表2所示,其中类别数表示图上所有不同标签的数量,且每个节点只有一个标签。该标签用于构建下游节点分类任务。

表2 数据集统计信息

3.1.2 基准方法介绍

文本的基准方法包含传统的网络表示学习方法和基于图对比学习的方法两类。对于传统的网络表示学习方法,我们选择了最受关注的Deepwalk(DW)[31]方法。同时将节点属性和Deepwalk得到的表示拼接作为同时刻画结构和属性的基准方法,记作DW+F。对于图对比学习方法,我们选择了利用随机采样负样本的方法DGI和GRACE[3]。以及利用相似度选取难负样本的方法GraphCL[11]。对于每个节点,GraphCL只使用与其相似度最高的20个节点作为负样本。对于基于图对比学习的方法GRACE,GraphCL,DGI[19],我们设定其迭代轮数为500。

3.1.3 模型设置

我们利用Tensorflow2.3实现模型。模型参数通过Glorot算法进行初始化,并且利用Adam优化器最小化对比损失函数L(θ,n)进行优化,学习率为0.001,并且设定迭代轮数为300。对于控制超参数τ的选择范围是{0.05, 0.1, 0.5, 1.0}。对于Dropout概率,随机丢边的概率,随机删除节点属性的概率的选择范围都为{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9},最优的τ=0.1,Dropout=0.6。

3.1.4 下游任务设置

我们在无监督范式下训练我们的模型和基准方法,并利用节点表示在下游任务上的表现来评价[2-5,32]。本文将节点分类任务作为下游任务,其具体流程如下。我们将学到的节点表示作为输入,根据数据划分,利用训练集中的节点表示训练线性分类器。同时利用验证集调整超参数,利用测试集评价模型。

我们使用常用的线性支撑向量机(SVM)来作为下游节点分类任务的分类器[3,11]。对于 Cora、Citeseer和 Pubmed,我们遵循之前论文中的固定划分,构建下游任务缺乏标签数据的情况,即每类只有30个训练标签。对于其余四个数据集,我们将节点随机拆分为训练/验证/测试集,其比例为(80%/10%/10%)。对于所有实验,我们重复10次,并展示了平均结果和方差。

3.2 节点分类实验

节点分类任务的结果如表3所示,其中最优值加粗展示,次优解用下划线展示,OOM表示超过GPU内存限制,本文使用的是32G内存的V100显卡,是当前最被广泛使用的先进显卡。从表3中,可以发现基于图对比学习的方法优于传统的图表示学习方法。由于较高的空间复杂度,GraphCL在较大的数据集上会超过内存限制,导致无法成功运行,说明基于余弦相似度筛选负样本的的方法难以适用于大规模的网络。

表3 节点分类准确率 (单位: %)

我们发现ANGCL方法优于除了GraphCL的所有基准方法。该结果说明相比于基于全局、随机负样本的GRACE方法,我们的ANGCL模型通过对抗训练的方式找到了对于模型难的负样本,从而提升了节点表示的质量,使其在下游任务中表现更好。同时我们也观察到针对每个节点选择合适负样本的方法GraphCL在结果上优于我们的ANGCL。这是由于ANGCL是全局共享了负样本,没有为每个节点自适应的选择合适的负样本。但通过全局共享负样本,使我们的模型在计算代价上明显低于GraphCL。

3.3 效率对比实验

在本节中,我们比较了不同方法在Cora数据集上迭代一轮需要消耗的时间,以及模型训练总耗时。同时展示了各个方法在节点分类任务上准确率。所有结果如表4所示,其中2 708为Cora数据集的节点数,即GRACE方法将图上所有节点都视为负样本。我们发现ANGCL运行的时间少于GRACE同时也取得了更好的节点分类效果。虽然ANGCL在得到全局负样本时,引入了额外的计算,但是其整体的时间消耗仍然低于利用所有负样本的图对比学习方法。

表4 模型运行时间对比

同时我们观察到虽然GraphCL取得了最优的效果,但时间消耗明显高于其他的方法。因为该方法在为每个节点筛选其对应K个最难的负样本时,需要与图上剩余所有节点计算相似度,并排序,从而引入了高昂的时间代价。当数据规模较大时,这种高昂的时间代价是不可忍受的。而我们的ANGCL在并没有降低很多效果的情况下,明显提升了模型的速度。

3.4 节点表示分布度量

本节我们对比了ANGCL和传统图对比学习方法GRACE学到的节点表示分布之间的差异。我们比较了不同方法学到的节点表示,在下游任务标签下,类内节点间的平均距离和类间节点间的平均距离。其结果如表5所示。

表5 节点表示在下游任务中的类内与类间距离度量

我们发现相比于原始的节点属性,图对比学习方法都增加了类内距离和类间距离之间的差距。该结果反映了这类方法能取得较好节点分类结果的原因。同时我们发现,ANGCL模型相对于GRACE,又进一步提升了两者距离之间的差异。该结果表明全局负样本的有效性。但同时我们基于全局共享负样本的方法ANGCL在效果上弱于针对每个样本选择合适负样本的方法GraphCL。

3.5 模型超参数分析

本节我们分别分析超参数边移除概率pe、特征移除概率pf以及τ对模型的影响,其结果分别如图3(a)、图3(b)、图3(c)所示。我们发现pe、pf值对模型效果影响不大,但是随着概率增大,结果的方差增大。这可能是由于超参数边移除概率pe、特征移除概率pf过大每次迭代中得到的增强图差异比较大导致。此外我们发现随着τ增大模型效果有下降,这是由于τ变大,缩小了表示相似度之间的差异,使得正样本和负样本间的差异变小,导致效果下降。

图3 Cora数据集上模型超参数对分类准确率的影响

4 总结

本文提出了基于对抗负样本的图对比学习模型,该模型利用对抗学习的框架,让模型自动学习需要的难负样本。ANGCL通过全局共享该负样本,减少了每个节点需要比较的负样本个数,大幅降低了模型的时间复杂度。同时通过对抗学习框架,使得每轮得到的负样本从梯度角度都是对于模型较难的,从而保证模型的效果。本文通过大量的实验,验证了模型的有效性。