GUAP论文阅读思考笔记
Published:
前置定义
本文使用GCN作为攻击模型，给定的图表示为\(G=(A,X)\)，其中\(A\in\mathbb{R}^{n\times n}\)和\(X\in\mathbb{R}^{n\times d}\)分别是图的邻接矩阵和特征矩阵。一个两层的GCN的计算过程可以表示为
\[Z:=f(A,X)=softmax(\hat{A}\cdot RuLU(\hat{A}XW^{(0)})\cdot W^{(1)})\]训练的目标是最小化所有节点标签的交叉熵损失之和
\[L=-\sum_{i\in V_L}\sum_{k=1}^K 1\{Y_i=k\}\ln Z_{ik}\]GUAP-通过对抗补丁的图通用攻击
通过\(G_{new}=(A_{new}, X_{new})\)表示加了\(m\)个补丁节点的新图。方便起见将补丁节点后缀表示在原来的邻接矩阵和特征矩阵中，即 \(A_{new}=\left[\begin{array}{c} A & C \\ C^T & B \end{array}\right], X_{new}=\left[\begin{array}{c} X \\ X_{pathch} \end{array}\right]\)
其中\(C\)代表原节点和补丁节点之间的关联关系，\(B\)代表补丁节点内部的关联关系。\(X_{patch}\)表示补丁节点的特征。所以整个方法需要讨论的就是节点的生成方法，包括节点联系和节点特征。
节点生成
在特征生成上独立处理每一维特征，拟合一个正态分布并从中随机采样。并在最后进行二值化，将值小于\(0.5\)的归零。如果训练集中节点某一维的特征包含\(1\)的概率是\(p\)，包含\(0\)的概率是\(1-p\)，那么拟和的正态分布的均值和方差是\(p\)和\(1-p\)，新的样本以\(\frac{1}{2}[1-\operatorname{erf}(\frac{1/2-p}{\sqrt{2p(1-p)}})]\)的概率采样\(1\)。
边训练
边训练的目标是改变目标节点的预测结果，同时保留其他节点的信息，数学形式上可以表示为
\[\left\{\begin{aligned} \hat{l}(A'_{new}, X_{new},i)\neq \hat{l}(A,X,i),& & \\ \hat{l}(A'_{new}, X_{new},i)\neq \hat{l}(A,X,i),& &\forall j\neq i \end{aligned}\right.\]使用一个攻击矩阵\(P\)完成攻击训练，其中的元素\(P_{ij}\)代表节点\(i\)和\(j\)之间的关联关系是否被反转，新的邻接矩阵可以被表示为
\[A'_{new}:=attack(A_{new}, i)=(\mathbb{1}-P)\circ A_{new}+P\circ(\mathbb{1}_0-A_{new})\]其中\(\circ\)代表元素乘，\(\mathbb{1}\)表示全1矩阵，\(\mathbb{1}_0\)表示除对角元素为0的全1矩阵。
在训练中也需要将攻击图转换为补丁图，这样的unattack操作可以通过攻击矩阵翻转回去
\[A_{new}=unattack(A'_{new}, i)=attack(A'_{new}, i)\]外侧循环：GUAP
GUAP算法流程如图所示
在外侧循环中，GUAP对于每个训练集中节点计算\(A'_{new}\)然后检查预测结果是否发生变化，如果没有的话就使用一个内部的IGP循环来生成一个扰动，并使用扰动更新\(A'_{new}\)，并将其转换回\(A_{new}\)。后续那一堆操作是因为扰动可能会逐渐将新邻接矩阵修改到极大，所以使用L2映射和clip操作来防止邻接矩阵爆炸。L2映射将单独应用于每个补丁节点，以便到此类节点的边向量具有 L2范数半径。我们还将\(B\)的对角元素设置为0，以防止自循环。 最终攻击成功率为
\(ASR(V_L):=\frac{1}{\vert V_L\vert}\sum_{i=1}^{\vert V_L\vert}1{\hat{l}(A'_{new},X_{new},i)\neq\hat{l}(A,X,i)}\)
内侧循环：IGP
IGP流程如图所示
IGP（迭代图扰动）为当前的攻击矩阵计算一个扰动。对于攻击的第一个目标（改变目标节点的预测结果），策略是将预测结果推向另一个类别的决策边界。对于第二个目标（尽可能保持其他节点的预测结果），策略是为其他节点推进一个较小的损失。
\[L'_{new}:=-\sum_{j\in V_l\setminus i}\sum_{k=1}^K1\{Y_j=k\}\ln f(A'_{new}, X_{new})_{jk}\]能够将节点\(i\)推向最近的其他类别\(k\)的决策边界的对于第\(i\)行的最小扰动可以计算为
\[k=\arg\min_{c\neq pred}\frac{\Delta f_c}{\Vert w_c\Vert_2},v=\frac{\vert\Delta f_k\vert}{\Vert w_c\Vert_2^2}\Delta w_k\]其中\(\Delta f_c=f(A_{new},X_{new})_{i,c}-f(A_{new},X_{new})_{i,pred}\)，\(\Delta w_c=\nabla f(A_{new},X_{new})_{i,c}-\nabla f(A_{new},X_{new})_{i,pred}\)。此处的梯度是针对\(A_{new}\)的第\(i\)行（和第\(i\)列）计算的。将最开始的n个元素置0，因为原始图结构应当保持不变。
使用一个overshoot来将节点i推向决策边界的另一侧。从\(E'_{new}\)开始的第二部分是为了达成第二个目标，降低在其他节点的预测损失。在计算梯度时将第\(i\)行和第\(i\)列置0，因为目标节点不应该保存。