图是一种非常常见的数据结构，社交网络、引用网络、分子网络、交通网络等通常采用图结构来建模数据。图神经网络作为目前处理图结构数据最为有效的方式，极大地促进了各类图分析应用如节点分类^{[1, 2]}、链路预测^{[3, 4]}、图分类^{[5, 6]}等的研究。进一步地，图学习在推荐系统，分子预测，蛋白质预测等应用领域也取得了巨大的成功。然而由于有标签数据过于昂贵且不易获得，导致有监督学习的成本较高，因此越来越多的研究开始转向自监督学习领域，对比学习便是目前自监督学习领域最为流行的一种学习方法。对比学习在计算机视觉领域取得了非常好的效果，催生了一系列图对比学习(graph contrastive learning, GCL)方法，如DGI^[7]、MVGRL^[8]、GRACE^[9]等。

虽然深度神经网络方法对于复杂问题的求解有着很好的性能表现，但是研究表明深度神经网络在对抗攻击下表现出一定程度的脆弱性，图卷积网络(graph convolutional network, GCN)也未能幸免，即使对节点特征或者图结构进行微小的扰动也会导致完全错误的预测结果^[10-11]。而自监督的GCL方法中也存在此类问题。到目前为止，仍然没有一个有效的算法可以验证一个GCL算法是否具有鲁棒性。

本文提出了基于节点特征对抗性攻击的图对比学习鲁棒性验证算法。首先，定义了图对比学习中的鲁棒性问题，并将其建模为一个动态规划问题。然后，针对该动态规划问题求解中的困难，提出了负例样本采样、二元离散特征放松到连续域、非线性激活函数放松等解决方法，并通过对偶问题进行高效求解。该算法具有不依赖特定攻击算法、数据标签以及下游任务的优势。最后，通过充分的实验说明该图对比学习鲁棒性验证算法的有效性，并验证了针对特定攻击算法设计的鲁棒的图对比学习算法可能不能在其他攻击上泛化其鲁棒性。

1 相关工作 1.1 图对比学习

早期图上的自监督方法如DeepWalk^[12]和node2vec^[13]方法基于随机游走采样得到正例对和负例对。受计算机视觉领域对比学习的启发，DGI^[7]借鉴了Deep InfoMax^[14]，相比早期的随机游走方法实现了巨大的性能提升。GMI^[15]采用了和DGI一样的框架，但是将互信息的概念从向量空间泛化到了图领域中。MVGRL^[8]通过将图扩散引入到图对比学习中进一步提升了DGI方法的性能。近期的工作通常沿用计算机视觉领域SimCLR^[16]和MoCo^[17]中提出的数据增广方法，将从相同数据实例增强出来的数据作为正例，不同数据实例增强出来的数据作为负例。GRACE^[9]通过均匀随机采样同时对边和节点特征进行扰动，来产生2个视图，并采用类似SimCLR的框架进行训练。GCA^[18]是GRACE方法的改进版，不再采用均匀随机采样，而是根据节点以及边的重要性进行随机采样扰动。最近，人们开始从谱域角度研究GCL，SpCo^[19]从谱图角度揭示了GCL的最佳增广方式，SPAN^[20]也从谱域的角度设计GCL的数据增广。考虑到图的同质性，NeCo^[21]将GCL与同质性联系起来，在节点分类任务上也取得很好的效果。

1.2 图鲁棒性验证工作

神经网络以及图神经网络面对微小的对抗扰动展现出高度的敏感性，GCL中也存在此类情况。近年来有很多启发式增强图模型鲁棒性的方法如对抗训练、可训练边权重、迁移学习等出现。然而这些方法都没有提供可证明的鲁棒性保证。文[22]是第一篇图学习领域的鲁棒性验证方法，主要围绕节点特征扰动的鲁棒性验证问题进行讨论。文[23]则主要聚焦于图结构扰动，对GCN的鲁棒性验证问题进行讨论。这2篇文章都面向节点分类任务，文[24]则是面向图级别分类任务中结构攻击的鲁棒性验证算法。文[22-24]均是采用通过对ReLU激活函数进行凸放松的方式求解。文[25]采用一个新的随机平滑方法来求解鲁棒性验证问题。文[26]提出之前的图鲁棒性验证工作都是节点对级别的，对于图分类任务可能并不合适，于是提出结构级别的图鲁棒性验证。

尽管已经有了一些针对有监督图学习的鲁棒性验证算法，但却缺少对GCL进行鲁棒性验证的工作，本文针对图上的节点特征扰动，设计了GCL的鲁棒性验证算法，并且避免了对攻击算法、数据标签以及下游任务的依赖，仅仅需要编码器产生的节点嵌入表示就可进行鲁棒性验证。

1.3 图对比对抗训练

对抗训练(adversarial training, AT)是提升模型鲁棒性至关重要的一大类方法。对抗训练方法从原本干净的图中动态生成对抗节点样本，通过将对抗节点样本加入到训练集中，以此来增强训练过程。GAD^[27]采用对抗训练，不仅研究节点的局部平滑度，还考虑图结构之间的关系，从而训练得到在图结构上平滑预测的鲁棒图神经网络。GACN^[28]将GCL与生成对抗网络(generative adversarial network, GAN)结合起来，通过使用GAN生成另1个视图，使得GCL学到更高质量、更加鲁棒的嵌入表示。ARIEL^[29]将对抗训练的思想引入到GCL中。该方法采用投影梯度下降(projected gradient descent，PGD)攻击^[30]来生成对抗样本，对PGD攻击具有较高的鲁棒性，但是可能并不具有可泛化的鲁棒性，本文的图对比学习鲁棒性验证方法通过实验证实了这一点。

2 预备知识 2.1 记号

本文主要符号如表 1所示。N_l(t)表示节点v_t的l跳邻居集合，即从节点v_t出发经过最多l跳可达到的所有节点(包含v_t本身)的集合。给定矩阵X，使用[X]₊=max(X, 0)表示其中大于0的所有元素，使用[X]_-=min(X, 0)表示其中小于0的所有元素；使用Tr[X]表示矩阵的迹。d^(l)表示第l层GCN输出的隐藏空间的维度，即$ \boldsymbol{H}^{(l)} \in \mathbb{R}^{n \times d^{(l)}}$，其中H^(l)是第l层GCN输出，n表示节点数量。进一步，使用X[i，: ]表示矩阵X的第i行，X[: ，j]表示矩阵X的第j列。

2.2 图对比学习

本文基于GRACE^[9]的框架来介绍图对比学习。给定图G=(A, X)，其中A∈{0, 1}^n×n，当节点对(v_i, v_j)之间存在一条边时，A[i, j]=1，否则A[i, j]=0。X∈{0, 1}^n×d是节点特征矩阵。通过数据增广生成原图的2个不同的视图G₁=(A₁, X₁)和G₂=(A₂, X₂)。通过g_θ，可以得到这2个视图的节点嵌入表示H₁=g_θ(A₁, X₁)和H₂=g_θ(A₂, X₂)。2个视图中对应节点作为正例样本对，其余所有节点都是其负例样本。定义节点u和v的相似度为sim(u, v)，通常将u和v的嵌入表示投影后计算得到的两者余弦相似度作为sim(u, v)。标记u_i=H₁[i, : ]和v_i=H₂[i, : ]，对比损失函数定义如下：

$ \begin{array}{c} L_{\text {con }}\left(\boldsymbol{G}_{1}, \boldsymbol{G}_{2}\right)=\frac{1}{2 n} \sum\limits_{i=1}^{n}\left(l\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{i}\right)+l\left(\boldsymbol{v}_{i}, \boldsymbol{u}_{i}\right)\right), \\ l\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{i}\right)= \\ -\log \frac{\mathrm{e}^{\operatorname{sim}\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{i}\right) / \tau}}{\mathrm{e}^{\operatorname{sim}\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{i}\right) / \tau}+\sum\limits_{j \neq i} \mathrm{e}^{\operatorname{sim}\left(\boldsymbol{u}_{i}, \boldsymbol{v}_{j}\right) / \tau}+\sum\limits_{j \neq i} \mathrm{e}^{\operatorname{sim}\left(\boldsymbol{u}_{i}, \boldsymbol{u}_{j}\right) / \tau}} . \end{array} $

其中τ是一个温度参数。

2.3 切片矩阵及切片图卷积网络

在图表示学习中，对于1个L层的GCN而言，其中1个节点v_t的输出H_t^(L)只与其(L-1)跳的邻居集合N_L-1(t)相关。因此，为了获得某个节点的嵌入表示，并不需要整张图上所有的节点特征，只需要知道其(L-1)跳的邻居集合N_L-1(t)即可。定义切片邻接矩阵和切片特征矩阵如下：

$ \begin{gathered} \dot{\boldsymbol{A}}^{(l)}=\hat{\boldsymbol{A}}^{(l)}\left[N_{L-l}(t), N_{L-l+1}(t)\right], \\ \quad l=1, 2, \cdots, L-1 ; \\ \dot{X}=X\left[N_{L-l}(t):\right], l=1, 2, \cdots, L-1 . \end{gathered} $

其中，$ \hat{\boldsymbol{A}}=\widetilde{\boldsymbol{D}}^{-\frac{1}{2}} \widetilde{\boldsymbol{A}} \widetilde{\boldsymbol{D}}^{-\frac{1}{2}}$是图消息传递矩阵，$ \widetilde{\boldsymbol{A}}=\boldsymbol{A}+ \boldsymbol{I}_{n \times n}$是加入自环后的邻接矩阵，$ \widetilde{\boldsymbol{D}}$是$ \widetilde{\boldsymbol{A}}$的度矩阵，$ \widetilde{\boldsymbol{D}}[i, i]={\mathit{\Sigma}}_{j} \widetilde{\boldsymbol{A}}[i, j], \hat{\boldsymbol{A}}^{(l)}\left[N_{1}(t), N_{2}(t)\right]$表示$ \hat{\boldsymbol{A}}^{(l)}$中以v_t的1阶邻居为下标的行和二阶邻居为下标的列组成的子矩阵。可见，随着GCN层数的加深，所需的切片矩阵越来越小，最后的输出层只需要知道节点v_t的1阶邻居即可。

有了切片邻接矩阵和切片特征矩阵，可以进一步定义切片GCN如下：

$ \begin{gathered} \left\{ \begin{array}{l} \hat{\boldsymbol{H}}^{(l)}=\dot{\boldsymbol{A}}^{(l-1)} \boldsymbol{H}^{(l-1)} \boldsymbol{W}^{(l-1)}+\boldsymbol{b}^{(l-1)}, \\ \boldsymbol{H}^{(l)}=\operatorname{ReLU}\left(\hat{\boldsymbol{H}}^{(l)}\right), \end{array} \right. \\ \quad l=2, 3, \cdots, L . \end{gathered} $

(1)

其中$ \boldsymbol{H}^{(1)}=\dot{\boldsymbol{X}}, \hat{\boldsymbol{H}}^{(l)}$是ReLU激活函数激活前的输入。这里去掉了最后一层的ReLU激活函数，W^(l)和b^(l)分别是第l层GCN的变换矩阵和偏移向量。最终，可以将编码器得到的嵌入表示标记为$ \boldsymbol{g}_{\boldsymbol{\theta}}(\dot{\boldsymbol{A}} , \;\dot{\boldsymbol{X}})=\hat{\boldsymbol{H}}^{(L)} \in \mathbb{R}^{d^{\prime}}$，d′最终输出的嵌入表示的维度。这里的θ={W^(l), b^(l)|l=1, 2, …, L-1}。

3 方法 3.1 扰动空间

与常见的鲁棒性测度不同，本文提出的图对比学习鲁棒性验证算法不再依赖于特定的攻击算法，而是考虑将节点特征的扰动限制在一定的扰动空间，在该扰动空间内去寻找一个最差的对抗样本。

考虑到图数据通常是二元离散的特征，因此不能直接采用范数约束来定义扰动空间。受到图对抗攻击领域已有的工作^{[10, 22]}的启发，通过限制扰动的特征数量来定义这样的一个扰动空间，具体来说，通过一个参数Q∈$ \mathbb{N}$来衡量$ \dot{\boldsymbol{X}}$受扰动前后的L₀范数变化。注意这里的$ \dot{\boldsymbol{X}}$包含目标节点及其(L-1)跳邻居的所有节点，因为在图学习领域，对于1个L层的GCN，1个节点的嵌入表示不仅与其本身相关，同时其(L-1)跳邻居也会对目标节点的表示产生影响。因此，参数Q衡量了一个全局的扰动空间。同时，为了不对某个节点的特征做过多扰动，这就需要继续定义1个局部扰动空间来限制单个节点特征的扰动不要太大。可以通过一个参数q∈$ \mathbb{N}$来实现这一约束。

综上，可以将特征扰动空间定义为如下形式：

$ \begin{gathered} X_{q, Q}(\dot{\boldsymbol{X}})=\\ \left\{\widetilde{\boldsymbol{X}} \mid \widetilde{\boldsymbol{X}}[i, j] \in\{0, 1\} \wedge\|\widetilde{\boldsymbol{X}}-\dot{\boldsymbol{X}}\|_{0} \leqslant Q \wedge\right. \\ \left.\|\widetilde{\boldsymbol{X}}[i, :]-\dot{\boldsymbol{X}}[i, :]\|_{0} \leqslant q, \forall v_{i} \in N_{L-1}\right\} . \end{gathered} $

(2)

3.2 图对比学习鲁棒性验证算法

通过定义扰动空间，避免了本文提出的图对比学习鲁棒性验证算法对特定攻击算法的依赖。已有的GCN鲁棒性算法通过对比受扰动前后节点的预测输出是否改变作为其是否鲁棒的依据，即对于目标节点 v_t，在其特征扰动空间内寻找1个最差的对抗样本$ \widetilde{v}_{t}$，若它们经过GCN分类器得到的预测分类结果是相同的(或者对抗样本也能预测分类正确)，则认为该目标节点在这样1个GCN分类器下是鲁棒的。但是，考虑到本文的目标是要设计实现一个图对比学习的鲁棒性验证算法，在自监督学习的设定下，不应当对数据标签和下游任务有任何依赖，这促使本文尝试在不依赖数据标签和下游任务的前提下去说明1个节点在GCL下是否是鲁棒的。

可以发现GCL的要点在于需要从原图中增广出2个不同的视图，2个视图中对应节点作为正例样本对，其余所有节点都是其负例样本。受此启发以及借鉴文[31]，本文设计了GCL中节点鲁棒性的定义：给定1个目标节点 v_t，定义其负例样本集合为V_t^-，对于GRACE^[9]和GCA^[18]方法，V_t^-= V-v_t。对目标节点在其特征扰动范围 X_{q, Q}($ \dot{\boldsymbol{X}}$)内做扰动，得到其对抗嵌入表示g_θ($ \widetilde{\boldsymbol{X}}$, A)，简记为$ \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}$。对于1个负例样本v_k∈V_t^-，如果sim(g_θ^t, $ \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}$)＞sim(g_θ^k, $ \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}$)，即对抗样本的嵌入表示与目标节点之间的相似度大于与该负例样本之间的相似度，就可以认为该对抗样本攻击失败。若对于∀v_k∈V_t^-，在特征扰动空间$ \mathcal{X}_{q, Q}$($ \dot{\boldsymbol{X}}$)内找不到1个对抗样本使得其攻击成功，则可以认为v_t在$ \mathcal{X}_{q, Q}$($ \dot{\boldsymbol{X}}$)下对于编码器g_θ是鲁棒的，反之则是非鲁棒的。当相似度函数sim(·, ·)采用余弦相似度函数时，sim(g_θ^t, $ \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}$)＞sim(g_θ^k, $ \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}$)可以写成(norm(g_θ^t)-norm(g_θ^k))^T$ \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}$＞0，其中norm(u) =u/‖u‖₂。算法见图 1，其中GCN编码器通过GCL训练得到。

接下来给出图对比学习鲁棒性验证问题的形式化描述: 给定G、v_t、V_t^-和一个由θ参数化的g_θ，定义对抗嵌入表示与正负例样本嵌入表示之间相似度差异在特征扰动空间内的最差情况为

$ \begin{gathered} \omega(t, k):=\min \left(\operatorname{norm}\left(\boldsymbol{g}_{\boldsymbol{\theta}}^{t}(\dot{\boldsymbol{X}}, \dot{\boldsymbol{A}})\right)-\right. \\ \left.\operatorname{norm}\left(\boldsymbol{g}_{\boldsymbol{\theta}}^{k}(\dot{\boldsymbol{X}}, \dot{\boldsymbol{A}})\right)\right)^{\mathrm{T}} \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}(\widetilde{\boldsymbol{X}}, \dot{\boldsymbol{A}}), \\ \text { s.t. } \widetilde{\boldsymbol{X}} \in \mathcal{X}_{q, Q}(\dot{\boldsymbol{X}}) . \end{gathered} $

(3)

如果对于∀v_k∈V_t^-都有ω(t, k)＞0，就可以说对于v_t，在$ \mathcal{X}_{q, Q}$($ \dot{\boldsymbol{X}}$) 下g_θ是验证为鲁棒的。

3.3 困难及挑战

在3.2节中，已经将本文的图对比学习鲁棒性验证算法形式化建模为一个动态规划问题。但仍有3个主要的障碍使得不能有效求解该动态规划问题。首先，V_t^-的样本空间大小为(2n-2)，如果对∀v_k∈V_t^-都去验证ω(t, k)＞0，会产生巨大的时间开销。其次，由于g_θ中含有非线性激活函数，这使得g_θ是非凸的，从而无法有效求解该动态规划问题。最后，由于图的数据域通常是二元离散的，即对于任意$ \widetilde{\boldsymbol{X}}$ ∈$ \mathcal{X}_{q, Q}$($ \dot{\boldsymbol{X}}$)都满足$ \widetilde{\boldsymbol{X}}$ ∈{0, 1}^N_L-1×d，这会使该动态规划问题难以直接求解。

针对上述的3个问题，本文分别设计了相应的解决方案。

3.4 负例样本空间采样策略

本文考虑采用从负例样本空间中随机采样K个负例样本，验证是否满足ω(t, k)＞0的方式来近似验证节点的鲁棒性。具体来说，采样方法如下：首先，使用已经训练好的g_θ获得所有节点的嵌入表示并对其归一化，即Z=norm(g_θ(X))∈$ \mathbb{R}^{n \times d^{\prime}}$，然后获得其任意2个节点之间嵌入表示的相似度矩阵Y=ZZ^T，这是一个对称矩阵，Y[i, j]为节点v_i、v_j的余弦相似度。然后本文对节点对之间的相似度运用Softmax函数来得到采样该样本的权重Softmax(Y)。同时为了后续采样方便，本文设置Softmax(Y)[i, i]=0，即避免采样到该节点本身。直观来说，对于v_t，若Softmax(Y)[t, k]越大，则说明v_k的嵌入表示与v_t的嵌入表示越相似，v_k被采样到的概率也越大。

式(3)中的对抗样本$ \widetilde{\boldsymbol{X}}$并非固定的，而是在特征扰动空间内所有可能的样本，因此需要根据节点对(v_t, v_k)去寻找一个最差的对抗样本。考虑到扰动特征空间是以v_t为中心的一个球，这约束了对抗样本不会距离v_t太远。同时希望找到的负样本应该距离对抗样本较近，因此选择的负样本也应当距离v_t较近。尽管可能存在距离v_t较远但距离对抗样本更近的负样本，但通过增大采样数量可以有效缓解该问题，后续的实验也证明了这一点。

3.5 激活函数凸放松

为了使得上述动态规划问题变为凸的从而可以有效求解，本文需要对ReLU激活函数进行凸放松。本文采用文[32]中提出的方法。其核心思想为，首先将矩阵H^(·)和$ \hat{\boldsymbol{H}}^{(\cdot)}$看作是可优化的变量而不是一个确定的值。在这一视角下，式(1)就变成了这些变量必须满足的约束条件。然后，即可将非线性ReLU激活函数放松为一个凸包。

具体来说，考虑式(1)，$ \hat{\boldsymbol{H}}^{(l)}$[i, j]表示ReLU激活函数的输入，假设基于可能的扰动空间，可以得到该输入$ \hat{\boldsymbol{H}}^{(l)}$[i, j]的上界S^(l)[i, j]和下界 R^(l)[i, j]，即R^(l)[i, j]≤$ \hat{\boldsymbol{H}}^{(l)}$[i, j]≤S^(l)[i, j]。定义集合Ψ^(l)包含第l层的所有使得R^(l)[i, j]＜0＜S^(l)[i, j]的元组(i, j)。类似地，定义Ψ₊^(l)包含第l层的所有使得0≤R^(l)[i, j]＜S^(l)[i, j]的元组(i, j), Ψ_-^(l)包含第l层的所有使得R^(l)[i, j]＜S^(l)[i, j]≤0的元组(i, j)。

当(i, j)∈Ψ^(l)时，可以将ReLU函数的结果放松为一个凸包如下：

$ \begin{gathered} H^{(l)}[i, j]>\hat{H}^{(l)}[i, j], \\ H^{(l)}[i, j] \geqslant 0, \\ H^{(l)}[i, j]\left(S^{(l)}[i, j]-R^{(l)}[i, j]\right) \leqslant \\ S^{(l)}[i, j]\left(\hat{H}^{(l)}[i, j]-R^{(l)}[i, j]\right), \\ (i, j) \in \varPsi^{(l)} . \end{gathered} $

这一思想可使用图 2进行解释。可以发现，此时H^(l)[i, j]不再是ReLU激活函数的确定性输出，而是一个被约束在一定范围内的可优化变量。

相应地，对于(i, j)∈Ψ₊^(l)和(i, j)∈Ψ_-^(l)的情况，会有

$ \boldsymbol{H}^{(l)}[i, j]= \begin{cases}\hat{\boldsymbol{H}}^{(l)}[i, j], & (i, j) \in \varPsi_{+}^{(l)}; \\ 0 . & (i, j) \in \varPsi_{-}^{(l)} .\end{cases} $

对于这2种确定情况，本文并不需要进行放松。到这里，即可以将ReLU激活函数放松为一系列凸的线性约束。再加上式(1)表示的对矩阵H^(·)和$ \hat{\boldsymbol{H}}^{(\cdot)}$的线性约束，现在可以对式(3)动态规划问题形式化描述的图对比学习鲁棒性验证算法进行改写如下：

$ \begin{gathered} \quad \widetilde{\omega}(t, k):=\min \left(\operatorname{norm}\left(\boldsymbol{g}_{\boldsymbol{\theta}}^{t}(\dot{\boldsymbol{X}}, \dot{\boldsymbol{A}})\right)-\right. \\ \left.\operatorname{norm}\left(\boldsymbol{g}_{\theta}^{k}(\dot{\boldsymbol{X}}, \dot{\boldsymbol{A}})\right)\right) \widetilde{\boldsymbol{g}}_{\boldsymbol{\theta}}^{t}(\widetilde{\boldsymbol{X}}, \dot{\boldsymbol{A}})=\min \boldsymbol{c}^{\mathrm{T}} \hat{\boldsymbol{H}}^{(L)}, \\ \text { s.t. } \widetilde{\boldsymbol{X}} \in \mathcal{X}_{q, Q}(\dot{\boldsymbol{X}}), \left[\boldsymbol{H}^{(\cdot)}, \hat{\boldsymbol{H}}^{(\cdot)}\right] \in \varPsi_{q, Q}(\widetilde{\boldsymbol{X}}) . \end{gathered} $

(4)

$ \boldsymbol{c}=\operatorname{norm}\left(\boldsymbol{g}_{\boldsymbol{\theta}}^{t}(\dot{\boldsymbol{X}}, \dot{\boldsymbol{A}})\right)-\operatorname{norm}\left(\boldsymbol{g}_{\boldsymbol{\theta}}^{k}(\dot{\boldsymbol{X}}, \dot{\boldsymbol{A}})\right) \in \mathbb{R}^{d^{\prime} \times 1}$，并且g_θ^t($ \widetilde{\boldsymbol{X}}$, $ \dot{\boldsymbol{A}}$)=H^(L)。Ψ_{q, Q}($ \widetilde{\boldsymbol{X}}$)表示对H^(·)和$ \hat{\boldsymbol{H}}^{(\cdot)}$的所有约束条件集合，注意到由于H⁽¹⁾=$ \widetilde{\boldsymbol{X}}$，所以约束条件集合Ψ_{q, Q}是依赖于$ \widetilde{\boldsymbol{X}}$的。

由于构造了[H^(·), $ \hat{\boldsymbol{H}}^{(\cdot)}$]∈Ψ_{q, Q}($ \widetilde{\boldsymbol{X}}$)，式(4)描述的动态规划问题是在这整个集合Ψ_{q, Q}($ \widetilde{\boldsymbol{X}}$)上优化的，所以其得到的$ \widetilde{\omega}$(t, k)不可能大于ω(t, k), 即$ \widetilde{\omega}$(t, k)≤ω(t, k)。因此，只需要验证在采样的K个负例样本上都有$ \widetilde{\omega}$(t, k)＞0，即可近似验证对于v_t，在$ \mathcal{X}_{q, Q}$($ \dot{\boldsymbol{X}}$) 下g_θ是验证为鲁棒的。

3.6 离散数据域放松

在常用的图数据中，其节点特征是二元离散的，这会使得难以直接求解3.5节中提出的动态规划问题。针对这一问题，本文对数据域是二元离散的这一条件进行适当放松到实数域[0, 1]中，即使得$ \widehat{\mathcal{X}}_{q, Q}$($ \dot{\boldsymbol{X}}$)∈[0, 1]^N_L-1×d，这样就可以有效求解上述动态规划问题。具体来说，将集合$ \mathcal{X}_{q, Q}$($ \dot{\boldsymbol{X}}$)放松到如下形式：

$ \begin{array}{c} \widehat{\mathcal{X}}_{q, Q}(\dot{\boldsymbol{X}})= \\ \left\{\widetilde{\boldsymbol{X}} \mid \widetilde{\boldsymbol{X}}[i, j] \in[0, 1] \wedge\|\widetilde{\boldsymbol{X}}-\dot{\boldsymbol{X}}\|_{1} \leqslant Q \wedge\right. \\ \left.\|\tilde{\boldsymbol{X}}[i, :]-\dot{\boldsymbol{X}}[i, :]\|_{1} \leqslant q, \forall \boldsymbol{v}_{\boldsymbol{i}} \in N_{L-1}\right\} . \end{array} $

注意，这里将式(2)中的L₀范数改为L₁范数，以适应二元离散特征到[0, 1]之间连续特征的改变。对二元离散的数据域放松之后，可以继续改写由式(3)动态规划问题形式化描述的图对比学习鲁棒性验证算法如下：

$ \begin{array}{c} \hat{\omega}(t, k):=\min \boldsymbol{c}^{\mathrm{T}} \hat{\boldsymbol{H}}^{(L)}, \\ \text { s.t. } \widetilde{\boldsymbol{X}} \in \widehat{\mathcal{X}}_{q, Q}(\dot{\boldsymbol{X}}), \left[\boldsymbol{H}^{(\cdot)}, \hat{\boldsymbol{H}}^{(\cdot)}\right] \in \varPsi_{q, Q}(\widetilde{\boldsymbol{X}}) \text {. } \end{array} $

(5)

至此，式(5)描述的动态规划问题的优化目标以及所有约束条件都是线性的。由于$ \mathcal{X}_{q, Q}$($ \dot{\boldsymbol{X}}$)⊂$ \widehat{\mathcal{X}}_{q, Q}$($ \dot{\boldsymbol{X}}$)，那么可以知道，式(5)的动态规划解出来的最优解$ \hat{\omega}$(t, k)是式(4)解出来的最优解$ \widetilde{\omega}$(t, k)的下界，即$ \hat{\omega}$(t, k)≤$ \widetilde{\omega}$(t, k)。不仅如此，文[22]证明了即使对离散数据域进行了放松，由式(5)解出来的最优情况下的$ \widetilde{\boldsymbol{X}}$是一个二元整数解，即$ \widetilde{\boldsymbol{X}}$ ∈{0, 1}^N_L-1×d。进一步可以知道$ \hat{\omega}$(t, k)=$ \widetilde{\omega}$(t, k)，所以可以有效解决二元离散数据域的问题。

3.7 ReLU激活函数的上界及下界

在3.5节中，本文说明了对非线性ReLU激活函数进行放松的方法，其中一个关键点在于找到S^(l)[i, j]和R^(l)[i, j]。越紧的上界和下界会使得对ReLU激活函数进行放松导致的误差越小，所以如何获得一个好的上界和下界对本文的图对比学习鲁棒性验证算法是非常重要的。

这里采用文[22]中提出的解决办法，假设考虑目标节点为v_t，对于其(L-2)跳的任意邻居，即对于所有节点v_m∈N_L-2(t)，需要计算它在第2层GCN中的第j维的上界S⁽²⁾[m, j]如下：

$ \begin{gathered} \boldsymbol{S}^{(2)}[m, j]=\hat{\boldsymbol{H}}^{(2)}[m, j]+\text { sum_top_}Q \cdot \\ \left(\left[\dot{\boldsymbol{A}}^{(1)}[m, p] \hat{\boldsymbol{S}}^{(2)}[p, j, i]\right]_{v_{p} \in N_{1}(m), i \in\{1, \cdots, q\}}\right), \\ \hat{\boldsymbol{S}}^{(2)}[p, j, i]=i \text {-th_largest } \cdot \\ \left((1-\dot{\boldsymbol{X}}[p, :]) \odot\left[\boldsymbol{W}^{(1)}[:, j]\right]_{+}+\right. \\ \left.(\dot{\boldsymbol{X}}[p, :]) \odot\left[\boldsymbol{W}^{(1)}[:, j]\right]_{-}\right) \end{gathered} $

(6)

其中i-th_largest(·)表示从相应向量中选择出第i大的元素，sum_top_Q(·)表示从相应列表中选择Q个最大元素求和。式(6)的第1项是由未受扰动的输入$ \dot{\boldsymbol{X}}$计算得到的隐藏层激活函数的输入，即$ \dot{\boldsymbol{H}}^{(2)}=\dot{\boldsymbol{A}}^{(1)} \dot{\boldsymbol{X}} \boldsymbol{W}^{(1)}+\boldsymbol{b}^{(1)}$；第2项反映了在$ \dot{\boldsymbol{X}}$的扰动空间内，第1个隐藏层激活函数输入的节点v_m的嵌入表示第j维值的改变的上界。总的来说，获得了$ \widehat{\mathcal{X}}_{q, Q}$($ \dot{\boldsymbol{X}}$)内的扰动输入$ \widetilde{\boldsymbol{X}}$在第1个隐藏层的激活函数输入值的上界。注意，v_m的隐藏层激活函数的输入值上界不仅与v_m有关，还依赖v_m邻居节点，这也反映了图数据的特性。

类似地，可以计算第2层GCN中的第j维的下界R⁽²⁾[m, j]：

$ \begin{array}{c} \boldsymbol{R}^{(2)}[m, j]=\hat{\boldsymbol{H}}^{(2)}[m, j]- \\ \text { sum_top_ } Q\left(\left[\dot{\boldsymbol{A}}^{(1)}[m, p] \cdot\right.\right. \\ \left.\left.\hat{\boldsymbol{R}}^{(2)}[p, j, i]\right]_{v_{p} \in N_{1}(m), i \in\{1, \cdots, q\}}\right), \\ \hat{\boldsymbol{R}}^{(2)}[p, j, i]=i \text {-th_largest } \cdot \\ \left(\dot{\boldsymbol{X}}[p, :] \odot\left[\boldsymbol{W}^{(1)}[:, j]\right]_{+}+\right. \\ \left.(1-\dot{\boldsymbol{X}}[p, :]) \odot\left[\boldsymbol{W}^{(1)}[:, j]\right]_{-}\right) . \end{array} $

对于剩下的GCN层，继续采用在文[22]中提出的上界和下界：

$ \begin{gathered} \boldsymbol{R}^{(l)}=\dot{\boldsymbol{A}}^{(l-1)}\left(\boldsymbol{R}^{(l-1)}\left[\boldsymbol{W}^{(l-1)}\right]_{+}-\boldsymbol{S}^{(l-1)}\left[\boldsymbol{W}^{(l-1)}\right]_{-}\right), \\ \boldsymbol{S}^{(l)}=\dot{\boldsymbol{A}}^{(l-1)}\left(\boldsymbol{S}^{(l-1)}\left[\boldsymbol{W}^{(l-1)}\right]_{+}-\boldsymbol{R}^{(l-1)}\left[\boldsymbol{W}^{(l-1)}\right]_{-}\right), \\ l=3, 4, \cdots, L-1 . \end{gathered} $

(7)

以上界R^(l)为例，对式(7)做一个直观的解释：对于权重为正的部分即[W^(l-1)]₊，采用前一层激活函数输入值的上界R^(l-1)，而对于权重为负的部分即[W^(l-1)]_-，采用前一层激活函数输入值的下界S^(l-1)。对于下界S^(l)则相反。

3.8 对偶优化有效求解下界

到此，事实上已经可以通过求解式(5)描述的动态规划问题来实现图对比学习鲁棒性验证算法。但由于该线性规划问题的变量过多，直接采用式(5)的线性规划来求解效率会很低。一个线性规划问题的对偶问题的可行解是原线性规划问题解的下界，于是考虑采用对偶优化的方式来高效求解。

参考文[22]和[32]，给出式(5)的对偶问题的形式化定义：

$ \begin{gathered} \max \xi_{q, Q}^{t}(\dot{\boldsymbol{X}}, \boldsymbol{c}, \boldsymbol{\varOmega}, \boldsymbol{\eta}, \rho) \\ \text { s.t. } \quad \boldsymbol{\varOmega}^{(l)} \in[0, 1]^{\left|N_{L-1}\right| \times d^{(l)}}, \\ \quad l=L-1, L-2, \cdots, 2 \\ \quad \boldsymbol{\eta} \in \mathbb{R}_{\geqslant 0}^{\left|N_{L-1}\right|}, \rho \in \mathbb{R}_{\geqslant 0} . \end{gathered} $

(8)

其中：$ \mathbb{R}_{\geqslant 0}$表示非负实数集合，

$ \begin{gathered} \xi_{q, Q}^{t}(\dot{\boldsymbol{X}}, \boldsymbol{c}, \boldsymbol{\varOmega}, \boldsymbol{\eta}, \rho)= \\ \sum\limits_{l=2}^{L-1} \sum\limits_{(i, j) \in \varPsi^{(l)}} \frac{\boldsymbol{S}^{(l)}[i, j] \boldsymbol{R}^{(l)}[i, j]}{\boldsymbol{S}^{(l)}[i, j]-\boldsymbol{R}^{(l)}[i, j]}\left[\hat{\boldsymbol{\varPhi}}^{(l)}[i, j]_{+}\right]- \\ \sum\limits_{l-1}^{L-1} 1^{\mathrm{T}} \boldsymbol{\varPhi}^{(l+1)} b^{(l)}-\operatorname{Tr}\left[\dot{\boldsymbol{X}} \dot{\boldsymbol{\varPhi}}^{(1)}\right]-\|\boldsymbol{\varGamma}\|_{1}- \\ q \sum\limits_{i} \boldsymbol{\eta}_{i}-Q_{\rho}, \end{gathered} $

并且

$ \begin{gathered} \boldsymbol{\varPhi}^{(L)}=-\boldsymbol{c} \in \mathbb{R}^{d^{\prime}} . \\ \hat{\boldsymbol{\varPhi}}^{(l)}=\dot{\boldsymbol{A}}^{(l) \mathrm{T}} \boldsymbol{\varPhi}^{(l+1)} \boldsymbol{W}^{(l) \mathrm{T}} \in \mathbb{R}^{\left|N_{L-1}\right| \times d^{\prime}}, \\ l=L-1, \cdots, 1 . \\ \boldsymbol{\varPhi}^{(l)}[i, j]=\left\{\begin{array}{l} 0, \quad(i, j) \in \varPsi_{-}^{(l)} ; \\ \hat{\boldsymbol{\varPhi}}^{(l)}[i, j], \quad(i, j) \in \varPsi_{+}^{(l)} ; \\ \frac{\boldsymbol{S}^{(l)}[i, j]}{\boldsymbol{S}^{(l)}[i, j]-\boldsymbol{R}^{(l)}[i, j]} \left[\hat{\boldsymbol{\varPhi}}^{(l)}[i, j]\right]_{+}- \\ \boldsymbol{\varOmega}^{(l)}[i, j]\left[\hat{\boldsymbol{\varPhi}}^{(l)}[i, j]\right]_{-}, \\ \quad(i, j) \in \varPsi^{(l)} ; \end{array}\right. \\ l=L-1, \cdots, 2 .\\ \boldsymbol{\varGamma}[i, j]=\max \left\{\Delta[i, j]-\left(\boldsymbol{\eta}_{i}+\rho\right), 0\right\} . \\ \Delta[i, j]=\left[\hat{\boldsymbol{\varPhi}}_{+}^{(1)}[i, j]\right]_{+}(1-\dot{\boldsymbol{X}}[i, j])+ \\ {\left[\hat{\boldsymbol{\varPhi}}^{(1)}[i, j]\right]_{-} \dot{\boldsymbol{X}}[i, j] .} \end{gathered} $

如果将$ \hat{\boldsymbol{\varPhi}}^{(l)}$和Φ^(l)看作相应节点的隐藏层表示，就可以将该对偶问题解释为GCN上的一个反向传播过程。尽管从形式上看这样一个对偶问题是非常复杂的，但事实上该优化问题只有Ω、η和ρ这3个变量。且这3个变量都只有简单的元素级限制，所有其他项都是确定可计算的，可以通过TensorFlow、Pytorch等自动差分框架来直接进行快速优化求解。进一步的，文[22]证明了对于任意Ω的可行解，可以找到η和ρ的闭式解；且通过实验说明了直接给Ω默认赋值为$ \frac{\boldsymbol{S}^{(l)}[i, j]}{\boldsymbol{S}^{(l)}[i, j]-\boldsymbol{R}^{(l)}[i, j]}$而不去优化，也可以获得很好的鲁棒性验证效果。这里本文直接采用该方法。

3.9 非鲁棒性验证

通过3.8节所述方法，可以近似验证一个GCL编码器的鲁棒性。但值得注意的是，即使式(8)解的极大值小于0，也不能说明该GCL编码器在及其扰动空间内是非鲁棒的。因为该极大值是式(5)解的下界，而式(5)的解又是式(3)解的下界。于是，还需要1个方法来验证其非鲁棒性。文[22]给出了找到扰动空间内最差扰动的方法，将v_t和v_k的嵌入表示分别记为g_θ^t和g_θ^k，将对特征经过最差扰动的v_t的嵌入表示记为$ \hat{\boldsymbol{g}}_{\theta}^{t}$。然后将它们代入(norm(g_θ^t)-norm(g_θ^k))^T$ \hat{\boldsymbol{g}}_{\theta}^{t}$，若值小于0，则说明g_θ在v_t及其扰动空间内是非鲁棒的。

4 实验 4.1 实验数据集

本文主要在Cora-ML ^[33]和CiteSeer ^[34]这2个图学习研究领域广泛使用的图数据集上进行实验。对于每个数据集中的每个节点，允许其1%的特征可以被扰动，即q=0.01d，d为输入特征维度。对于全局扰动，设置不同Q的来观察其结果。

4.2 评测模型

本文评测了2个经典的GCL模型。一个是GRACE^[9]模型，它通过均匀随机采样同时对边和节点特征进行扰动，来产生2个视图，并采用类似SimCLR的框架进行训练。2个视图中对应节点做为正例样本对，其余所有节点都是其负例样本。另一个是ARIEL^[29]模型，这是特定针对PGD攻击^[30]而改进的鲁棒GCL方法。它不仅对边和节点特征进行扰动产生2个视图G₁和G₂，还通过PGD攻击来产生1个对抗视图G_adv，分别对G₁和G₂、G₁和G_adv运用对比损失，从而训练出针对PGD攻击鲁棒的编码器。

4.3 实验设置

考虑到图对比学习隐藏层的特征维度往往比较大，会导致机器显存不足的问题，实验中略微减小了隐藏层特征维度。对于Cora数据集和CiteSeer数据集，2个模型的隐藏层特征维度均设置为64。其余设置均与文[9, 29]提供的代码相同。

注意图对比学习在训练过程中是不需要下游任务信息的。本文提出的图对比学习鲁棒性验证算法也仅仅需要使用节点的嵌入表征，采用第3章中的方法，就可以去评测图对比学习算法的鲁棒性。因此该方法是不依赖于下游任务的。

4.4 验证GRACE编码器的鲁棒性

使用本文提出的图对比学习鲁棒性验证算法对GRACE模型进行鲁棒性验证。

图 3为GRACE模型在Cora-ML数据集上的鲁棒性表现，蓝线和橙线分别表示验证鲁棒与验证非鲁棒节点的占比。两条曲线之间的纵轴差值是较小的(此为不能被验证为鲁棒或非鲁棒的节点的占比)，最大的差值约为30%，表明本文提出的方法可以较为有效地验证图对比学习算法的鲁棒性，也说明本文采取的一系列放松方式以及对非线性激活函数寻找的上界下界都是比较合理的。

从图 3可以看到，GRACE模型只在Q较小时会有较好的可验证鲁棒性，且其可验证鲁棒性随着Q的增大快速衰减，当Q=12时，有73.02%的节点被验证为鲁棒的，但当Q=15时，就只有59.73%的节点会被验证为是鲁棒的。这一现象在更加复杂的CiteSeer数据集上表现得更加明显。图 4展示了GRACE模型在CiteSeer上的鲁棒性表现。

从图 4可以看到，在CiteSeer数据集上，随着Q的增大，可验证鲁棒的节点占比迅速减小，而可验证非鲁棒的节点占比迅速增大。具体的，当扰动空间Q=15时，就只有24.91%的节点被验证为是鲁棒的，且有39.4%的节点被验证是非鲁棒的。这进一步证明了GCL对于输入的微小扰动是十分脆弱的。

4.5 验证ARIEL编码器的鲁棒性

为了解决神经网络面对攻击表现脆弱的问题，很多方法针对一种特定的攻击进行防御从而获得鲁棒性，然而难以得知这种鲁棒性是否是可以泛化到其他的攻击上。本节使用提出的图对比学习鲁棒性验证算法来检测一个GCL模型的鲁棒性是否可以泛化。采用ARIEL模型与GRACE模型进行对比。ARIEL模型可以看作GRACE模型的一个改进版本，它与GRACE模型主要区别有2点：ARIEL在每个训练过程都会采样1个子图，对该子图增广产生2个不同的视图；它还会对子图使用PGD攻击产生1个对抗视图。ARIEL在这3个子图上分别使用对比损失函数来训练模型。

通过对比实验比较GRACE模型和ARIEL模型分别在Cora-ML数据集以及CiteSeer模型上的鲁棒性表现。从图 5可以看出，在Cora-ML数据集上，ARIEL模型的可验证鲁棒性的节点占比会略高于GRACE模型，但并不能说明ARIEL模型的可验证鲁棒性比GRACE更好，因为它们的验证非鲁棒性的节点占比几乎一致。然而，从图 6可以看出，在CiteSeer数据集上，ARIEL模型的可验证鲁棒性是要显著比GRACE模型差的。这一现象证明：针对特定攻击设计的鲁棒性模型的鲁棒性往往不能泛化，甚至在面对另一种攻击算法时会表现出更加脆弱。

为了进一步说明说明是ARIEL中的哪一项改动使得其可验证的鲁棒性变差了，本文进一步通过消融实验，去掉ARIEL模型的2项改动，然后使用图对比学习鲁棒性验证算法对其进行分析。首先将ARIEL模型中采样子图的部分去除，而保留其使用PGD攻击生成对抗样本的部分，并将其与ARIEL模型在CiteSeer数据集上的可验证鲁棒性进行对比，结果如图 7所示。可以看到，二者并无明显区别，这说明采样子图并不会对模型的可验证鲁棒性产生过多影响。

接下来将ARIEL模型中使用PGD攻击生成对抗样本的部分去除，而保留其采样子图的部分，并将其与ARIEL模型在CiteSeer数据集上的可验证鲁棒性进行对比，结果如图 8所示。可以看到，当去掉使用PGD攻击生成对抗样本的步骤后，模型的可验证鲁棒性有着比较明显的提升，可以证明采用PGD攻击生成对抗样本的ARIEL模型虽然在面对PGD攻击时有着优越的鲁棒性能，但是这种做法带来的鲁棒性提升并不能泛化到其他攻击中。ARIEL模型的可验证鲁棒性变差意味着其在面对另外一种攻击时很可能会表现得更加脆弱。

4.6 参数实验

在本文提出的图对比学习鲁棒性验证算法中，考虑到负例样本空间过大问题时，采用了对负例样本采样的策略来近似。本节通过对采样的负例样本数量进行参数实验，来说明这一做法是合理的。对于Cora-ML和CiteSeer 2个数据集，将Q固定为12，然后对GRACE和ARIEL模型设置不同的K去验证其鲁棒性。

从图 9和10中可以看出，随着采样负例数量的增加，验证鲁棒节点占比会逐渐减少，同时验证非鲁棒节点的占比会逐渐增多。但可以看到，这种趋势在K＞20时已经很微小了，所以本文的图对比学习鲁棒性验证算法采用K=20作为采样负例样本数量是比较合理的，可以高效且准确地验证GCL的编码器的鲁棒性。

5 结论

本文提出了基于节点特征对抗性攻击的图对比学习鲁棒性验证算法。首先，定义了图对比学习中的鲁棒性问题，并将其建模为一个动态规划问题。然后，针对该动态规划问题求解中的困难，提出了负例样本采样、二元离散特征放松到连续域、非线性激活函数放松等解决方法，并通过对偶问题进行高效求解。该算法能在不依赖特定攻击算法、数据标签以及下游任务的情况下，验证GCL模型的鲁棒性。最后，通过实验证明了所提出方法的有效性；并通过对比实验和消融实验，验证了针对某种特定攻击设计的鲁棒性算法往往不能够在其他攻击上泛化其鲁棒性，进一步表明了本文提出的图对比学习鲁棒性验证算法的重要性。

该算法未考虑结构扰动下的鲁棒性，下一步将继续考虑结构扰动的情况，从而为设计一个在各种攻击上都有鲁棒性保证的GCL算法提供支持。