引言
此为原创文章，未经许可，禁止转载
这篇博文主要介绍的对图神经网络进行攻击，即：通过对某些节点的特征进行扰动、或者对图结构进行扰动使得图神经网络对于特定节点分类任务失效(分类错误)，研究图神经网络的对抗攻击是有必要的，因为这会帮助我们构建更加鲁棒的图神经网络模型。博文的主要内容来源于 KDD 2018 Best Paper：Adversarial Attacks on Neural Networks for Graph Data
基本记号
这篇文章的主要记号仍然沿用了图神经网路的惯例，图卷积层表示为
\[H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)\]其中 $\tilde{A}=A+I_N$ 表示加了自环(self-loop)后的邻接矩阵，\(\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}\)，$H$是节点的embedding矩阵，$H^{(0)}=X$即为节点的初始embedding，$W$是一个可训练的权重向量。使用这样的记号，单隐层GCN模型可以表示为
\[Z=f_{\theta}(A, X)=\operatorname{softmax}\left(\hat{A} \sigma\left(\hat{A} X W^{(1)}\right) W^{(2)}\right)\]其中$\hat{A}=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$，输出$Z_{vc}$表示将节点$v$分类到类别$c$的概率。$\theta$表示所有参数的集合，即\(\theta=\left\{W^{(1)}, W^{(2)}\right\}\)。参数$\theta$通过交叉熵优化：
\[L(\theta ; A, X)=-\sum_{v \in \mathcal{V}_{L}} \ln Z_{v, c_{v}} \quad, \quad Z=f_{\theta}(A, X)\]其中$\mathcal{V}_L$表示有标签的节点集合。$c_v$表示节点$v$的类别，训练完成之后，$Z$表示每个节点的类别概率。
攻击模型
攻击模型的目标是通过对图$G^{(0)}=\left(A^{(0)}, X^{(0)}\right)$进行细微的扰动，得到图$G^{\prime}=\left(A^{\prime}, X^{\prime}\right)$，使得在图$G’$是上进行的节点分类性能下降。对于邻接矩阵$A^{(0)}$的变动称为结构攻击，对于特征矩阵$X^{(0)}$的扰动称为特征攻击。
定义：目标节点和攻击者节点
具体而言，我们的目的是对特定的目标节点$v_0\in\mathcal{V}$进行攻击，即改变$v_0$的预测类别，因为图数据边的原因，节点和节点之间是相互关联的，因此我们不一定要通过直接改变目标节点$v_0$的特征使得神经网络对其分类错误，我们也可以通过改变目标节点周围的邻居，我们称这些邻居为攻击者节点$\mathcal{A} \subseteq \mathcal{V}$。攻击者节点必须满足以下性质：
\[X_{u i}^{\prime} \neq X_{u i}^{(0)} \Rightarrow u \in \mathcal{A} \quad, \quad A_{u v}^{\prime} \neq A_{u v}^{(0)} \Rightarrow u \in \mathcal{A} \vee v \in \mathcal{A}\]第一个式子表示所有特征有变动的节点都属于攻击者节点，第二个式子表示如果两个节点之间的连边有变动，那么他们都是攻击者节点。
如果目标节点$v_0\notin\mathcal{A}$，我们称这种攻击为间接攻击，因为我们不是通过直接扰动$v_0$的特征或者关联的边来改变对其的预测分类的。如果目标节点$v_0\in\mathcal{A}$，我们称这种攻击为直接攻击。
限制：尽可能小得改变图
对于攻击者来说，他需要尽可能少得改变图数据(节点特征和边信息)以保证攻击不被轻易发现，下式设定了一个对于图进行攻击的次数限制$\Delta$：
\[\sum_{u} \sum_{i}\left|X_{u i}^{(0)}-X_{u i}^{\prime}\right|+\sum_{u<v}\left|A_{u v}^{(0)}-A_{u v}^{\prime}\right| \leq \Delta\]这个式子表示所有特征被扰动和邻边被扰动的节点的总数不能超过某一个阈值$\Delta$。记所有满足这个限制的图$G’$集合为$\mathcal{P}^{G^0}_{\Delta,\mathcal{A}}$，那么图上的攻击就可以转化为一个优化问题：
给定图$G^{(0)}=\left(A^{(0)}, X^{(0)}\right)$，一个目标节点$v_0$，攻击节点集合$\mathcal{A}$。假设$c_{old}$表示$v_0$在图$G^{(0)}$上的分类结果(或者真实标签)，攻击问题的优化定义为：
\[\begin{array}{c}{\arg \max _{\left(A^{\prime}, X^{\prime}\right) \in \mathcal{P}_{\Delta, \mathcal{A}}^{G 0}} \max _{c \neq c_{o l d}} \ln Z_{v_{0}, c}^{*}-\ln Z_{v_{0}, c_{o l d}}^{*}} \\ {\text {subject to } Z^{*}=f_{\theta^{*}}\left(A^{\prime}, X^{\prime}\right) \text { with } \theta^{*}=\arg \min _{\theta} L\left(\theta ; A^{\prime}, X^{\prime}\right)}\end{array}\]这个优化问题的意思是：给定所有符合条件(攻击的次数足够少)的攻击后的图$G’=(A’, X’)\in\mathcal{P}_{\Delta, \mathcal{A}}^{G^0}$，找到能够使得目标节点的预测值和被攻击之前的正确值之间差距最大的图结构$G’=(A’, X’)$。注意到在上式中，我们用到了$\theta^{*}$，即每个攻击后的图结构都是在数据集上进行重新训练以得到最优的参数。因此这实际上是一个二层优化问题(bi-level optimization problem)。
(5)式是一个大致衡量图变动的指标，在一些复杂的情况下，具体的$\Delta$值很难设定，为了使图变动不容易被发现，我们需要更加精细的指标来衡量图的变动情况。
结构扰动限制
图结构最重要的特征是度分布，在真实的网络中，度分布常常以power-law的形式出现，即图中节点的度和具有该度的节点数量服从$p(x) \propto x^{-\alpha}$的分布，作者希望改变结构后的图$G’$仍然能服从相似的度分布，即原图的度分布和改变后$\alpha$大致相当，$\alpha$可由下式近似计算
\[\alpha_{G} \approx 1+\left|\mathcal{D}_{G}\right| \cdot\left[\sum_{d_{i} \in \mathcal{D}_{G}} \log \frac{d_{i}}{d_{\min }-\frac{1}{2}}\right]^{-1}\]式中$d_{min}$是一个阈值，所有低于这个阈值的节点不参与计算，$d_v^G$表示节点$v$的度，\(\mathcal{D}_G=\left\{d_v^G\vert v\in\mathcal{V}, d_v^G\ge d_{min}\right\}\)表示关于度的multiset。通过这个式子，我们能估计出原图\(\alpha_{G^{(0)}}\)和改变后的图\(\alpha_{G'}\)，同样，我们也能够估计出组合这两个图的\(\alpha_{comb}\)，其中\(\mathcal{D}_{comb}=\mathcal{D}_{G^{(0)}} \cup \mathcal{D}_{G^{\prime}}\)。
给定$\alpha_x$，$\mathcal{D}_x$的log-likelihood可以通过下式评估：
\[l\left(\mathcal{D}_{x}\right)=\left|\mathcal{D}_{x}\right| \cdot \log \alpha_{x}+\left|\mathcal{D}_{x}\right| \cdot \alpha_{x} \cdot \log d_{\min }+\left(\alpha_{x}+1\right) \sum_{d_{i} \in \mathcal{D}_{x}} \log d_{i}\]使用这些log-likelihood，我们能够通过假设检验的方式评估是否两个图\(\mathcal{D}_{G^{(0)}}\)和\(\mathcal{D}_{G^\prime}\)来自于同样的power-law分布，建立两个对立的假设
\[l\left(H_{0}\right)=l\left(\mathcal{D}_{c o m b}\right) \quad \text { and } \quad l\left(H_{1}\right)=l\left(\mathcal{D}_{G^{(0)}}\right)+l\left(\mathcal{D}_{G^{\prime}}\right)\]最终的测试统计量可以写成这样的形式：
\[\Lambda\left(G^{(0)}, G^{\prime}\right)=-2 \cdot l\left(H_{0}\right)+2 \cdot l\left(H_{1}\right)\]当图的规模非常大的时候，这个统计量服从自由度为1的$\chi^2$分布(卡方分布)。最终，我们只接受扰动后的图$G^{\prime}=\left(A^{\prime}, X^{\prime}\right)$，使得度分布满足
\[\Lambda\left(G^{(0)}, G^{\prime}\right)<\tau \approx 0.004\]特征扰动限制
为了对特征的扰动进行更加精细得刻画，我们构建了一个基于特征共现图$C=(\mathcal{F}, E)$的概率随机游走模型，即$\mathcal{F}$是特征的集合，$E \subseteq \mathcal{F} \times \mathcal{F}$类似于一个邻接矩阵，元素$E_{ij}$表示特征$i$和特征$j$共现过。将特征$i$加入到节点$u$的特征集中需要满足下面的条件：
\[p\left(i | S_{u}\right)=\frac{1}{\left|S_{u}\right|} \sum_{j \in S_{u}} 1 / d_{j} \cdot E_{i j}>\sigma\]这个式子的意思是，节点$u$的特征集合的所有特征出发，在图上进行一步随机游走，要是有足够大的概率能够到达特征$i$，那么我们认为添加特征$i$到节点$u$的特征集合中是不易被发现的，本文选择了最大的可到达概率的一般，即\(\sigma=0.5 \cdot \frac{1}{\left\vert S_{u}\right\vert} \sum_{j \in S_{u}} 1 / d_{j}\)。
采样相同的统计测试原理，我们只接受扰动后的图$G^{\prime}=\left(A^{\prime}, X^{\prime}\right)$，使得特征值满足：
\[\forall u \in \mathcal{V} : \forall i \in \mathcal{F} : X_{u i}^{\prime}=1 \Rightarrow i \in S_{u} \vee p\left(i | S_{u}\right)>\sigma\]即，对原图每个节点添加的特征要满足共现概率足够大的要求。
小结
综上，我们从\(\mathcal{P}_{\Delta, \mathcal{A}}^{G^0}\)选出满足式(11)和式(13)的子集\(\hat{\mathcal{P}}_{\Delta, \mathcal{A}}^{G^0}\)来保证对图的扰动不容易被发现。
生成对抗图
直接求解(6)(11)(13)是比较困难的，因此作者在论文中提出了一个代理模型，通过对代理模型进行攻击得到一个被攻击的图模型，然后这个图模型被用来接着训练最终的模型。
为了得到一个易于处理但是依然能够保留图卷积操作的代理模型，作者对图卷积层进行了简化，移除了非线性激活函数：
\[Z^{\prime}=\operatorname{softmax}\left(\hat{A} \hat{A} X W^{(1)} W^{(2)}\right)=\operatorname{softmax}\left(\hat{A}^{2} X W\right)\]其中$W^{(1)}$和$W^{(2)}$都是可学习的神经网络权重，因此它们被一个$W\in\mathbb{R}^{N\times K}$所替代。
由于模型的目标是使得目标节点$v_0$的log-probabilities变化量最大，softmax可以直接忽略掉，因为softmax是单调函数。也就是可以把log-probabilities简化为$\hat{A}^2XW$，给定一个在没有任何扰动的数据集上训练好的代理模型，得到模型参数$W$，代理损失被定义为：
\[\mathcal{L}_{S}\left(A, X ; W, v_{0}\right)=\max _{c \neq c_{o l d}}\left[\hat{A}^{2} X W\right]_{v_{0} c}-\left[\hat{A}^{2} X W\right]_{v_{0} c_{o l d}}\]$\hat{A}^2XW$输出是一个$N\times K$的矩阵，表示每个节点被预测到每个类上的class probability。上面的式子表示在输出$v_0$的所有class probability中，找到使得class probability最大的一个，且这个类别和节点的真实类别不能相同。
攻击目标就变成了：
\[{\arg\max} _{\left(A^{\prime}, X^{\prime}\right) \in \mathcal{P}_{\Delta, \mathcal{A}}^{G 0}} \mathcal{L}_{S}\left(A^{\prime}, X^{\prime} ; W, v_{0}\right)\]也就是对所有扰动后的图，选出一个，使得所有目标节点被误分类的可能性最高。
当然，这个被选出的扰动后的图还要满足扰动不易被发现的条件，即满足式(11)(13)，联合优化式(11)(13)是困难的，因此作者提出了一个贪心的近似策略。首先定义两个得分函数，用来衡量对结构扰动和对特征扰动的代理模型的损失。
\[\begin{aligned} s_{\text {struct}}\left(e ; G, v_{0}\right) & :=\mathcal{L}_{s}\left(A^{\prime}, X ; W, v_{0}\right) \\ s_{f e a t}\left(f ; G, v_{0}\right) & :=\mathcal{L}_{s}\left(A, X^{\prime} ; W, v_{0}\right) \end{aligned}\]其中 $A^{\prime} :=A \pm e\left(\text { i.e. } a_{u v}^{\prime}=a_{v u}^{\prime}=1-a_{u v}\right)$ 且 $X^\prime := X \pm f(i.e. x^\prime_{ui}=1-x_{ui})$分别表示对结构和对特征的扰动。$A^\prime$是$A$添加或者删除一个边得到的，而$X^\prime$是$X$添加或者删除一个特征得到的。整个攻击过程可以归结为：给定一个当前状态$G^{(t)}$，在满足不易被发现的条件下，生成所有可能的结构扰动$C_{struct}$，在它们之中选择一个使得log-probablities 改变量最大，也就是$s_{struct}$最大。然后在这个基础之上，生成所有可能的特征扰动$C_{feat}$， 在它们之中选择一个使得log-probablities该变量最大，也就是$s_{feat}$最大，记作状态$G^{t+1}$，重复这两个步骤一直更新，知道超过不易被发现的度量$\Delta$。如下：
这个算法能够work的前提是$s_{struct}$和$s_{feat}$的计算要足够高效，因此作者在论文中花了一些篇幅介绍如何高效得计算这些数值，在此不再赘述。