图神经网络的对抗标签翻转攻击与防御

2021 年 3 月 28 日 专知

论文解读者 ：北邮 GAMMA Lab 博士生张梦玫

题目：Adversarial Label-Flipping Attack and Defense for Graph Neural Networks

会议： ICDM 2020

论文代码：

https://github.com/MengmeiZ/LafAK

随着GNN的广泛应用，其对于对抗攻击的鲁棒性越来越受到人们的关注。然而，现有的工作忽略了对抗标签翻转攻击，其中攻击者可以通过操纵少量的训练标签毒害模型训练。探索GNN对标签翻转攻击的鲁棒性是非常关键的，特别是当标签从外部来源收集并且容易注入错误标签时(例如推荐系统)。在这项工作中我们介绍了第一个对抗标签翻转攻击GNN的研究，并提出了一种有效的攻击模型LafAK，LafAK利用GCN的近似闭合解和不可微目标的连续代理，通过基于梯度的优化器高效地产生攻击。此外，我们还指出了GNNs易受标签翻转攻击的一个关键原因是对翻转节点的过拟合。基于此，我们提出了一个防御框架，该框架引入了一个基于社区分类的自监督任务作为正则化来避免过拟合。我们在四个真实的数据集上展示了我们提出的攻击模型和防御模型的有效性。

1 引言

GNN已经被大量工作证明对于对抗攻击不鲁棒[1]，尤其是毒害攻击，即攻击者试图通过操纵训练数据来误导模型的训练、破坏模型的性能。这些工作指出了GNNs易受拓扑攻击和特征攻击，然而，现有的工作忽略了一种特定类型的中毒攻击，即对抗标签翻转攻击(攻击者可以恶意反转少量训练标签)。对抗的标签反转不同于随机标签噪声，可以针对性地利用算法的漏洞，显著降低模型的整体性能。因此我们要回答一个 问题: GNN也容易被对抗性标签翻转攻击破坏吗?一方面，由于GNN中的消息传播常局限于local的邻居，因此GNN可能会鲁棒，另一方面，作为深度学习模型，它们很容易对错误的标签进行过度拟合。

回答这个问题非常重要，尤其是当标签是从外部来源收集时，如图1中的Polblogs网络，博客是节点（#1490），引用关系是边，博客所属党派是标签（#40），其中党派标签多为用户自动上传的。对于Polblogs，我们假设只能翻转四个标签(如图1有双轮廓的节点从蓝色翻转到黄色)，GNN在对抗翻转后的标签上再训练后，测试acc会显著下降(约29 %)，而随机翻转仅平均下降约2.51%。显然，GNN容易被我们的对抗翻转攻击影响，这可能会阻碍它们在各个领域的适用性。因此，系统地研究和进一步提高GNN对标签翻转攻击的鲁棒性是非常必要的。

图1. 对抗标签翻转攻击的例子

要回答这个问题，就要决定翻转哪些标签作为对抗攻击，这本质上是一个离散性的NP-hard整数规划问题。为了避免组合搜索，最近的方法[2,3]建议使用基于梯度的优化器来搜索最优攻击。但这种想法不能直接应用于我们的问题，因为有两个挑战:

(1)挑战1：攻击的(外层)优化涉及求解GNNs的(内层)优化，这本质上是一种双层优化，通常难以求解。现有的工作试图绕过这个问题，例如假设GNN的参数是静态的，或者间接优化双层优化问题，即将问题转化为min-max问题。此处我们通过线性化GNN和替换分类损失，提出了GNN的近似闭合解，直接将复杂的双层优化转化为单层优化问题。

(2)挑战2：优化目标包含特殊的不可微组件(如离散的acc指标和翻转操作)，使我们无法直接应用梯度。此处我们专门为这些不可微的组件设计了连续代理，使得模型可以利用基于梯度的优化器高效地生成攻击。

此外, 为了提高GNN对于对抗标签翻转攻击的鲁棒性, 我们经研究发现其脆弱的一个关键原因是过拟合了翻转标签。为了缓解这一问题, 我们提出了一个基于自监督的防御框架, 它以社区分类任务作为辅助任务，引入社区级别的信号以惩罚过拟合翻转标签的GNN。

2 攻击方法

LafAK的优化目标：希望找到最优的翻转向量来扰动训练标签（即），使得基于这些标签训练得到的GCN参数的分类精度能够最大程度下降，即：

其中，是一个无向图, 是图的邻接矩阵，是图的特征矩阵，此处考虑二分类标签 , 带标签节点个数为 , 无标签节点个数为。翻转向量 , 为Hadamard 积, 代表翻转标签，最大翻转次数被一个很小的翻转比例限制，以保证攻击的不可感知性。不难看出，基于0-1测试误差的外层优化包含了GCN的训练（基于loss ）作为约束，其中被约束为给定下的最优GCN参数，这是一个典型的双层优化问题。首先，在优化中每次迭代更新都需要重训GCN，这种时间开销是难以忍受的。其次，和都是离散的，阻碍了基于梯度的优化方法的应用。为此我们提出相应的解决方案如下。

线性化GCN：为了得到GCN的近似封闭形式，同时保持图卷积的功能，我们通过在下式中对GCN进行线性化来简化GCN。

替换内层分类loss得到闭合解：给定线性化版本，GCN被简化为一个简单的特征传播步骤(即 )，和一个标准的逻辑回归分类，即使在小样本设置下其也没有统计上有效的闭合解。而线性回归模型有闭合解，即最小二乘（OLS）。因此，我们将GCN简化为线性回归，通过将(内部)分类损失替换为回归损失(即平方损失)，得到GCN的近似封闭形式(命名为GCN (appr)):

将双层优化转化为单层优化：得到GCN (appr)的最优参数后，代入到最初的LafAK优化目标，即可得到

不可微的连续代理：对于不可微的，一个标准解是将替换为连续测试损失。与相比，基于的攻击目标的目标是最大限度地降低分类的整体置信度，而不是测试精度。为了更好地保持功能，我们首先将Heaviside阶跃函数(即 )替换为光滑的近似函数，且的值越大，光滑函数越接近阶跃函数。接下来，给定反转

\delta \odot \mathbf{y}_L

，我们可以进一步得到测试节点的近似预测：

离散变量的连续代理：我们利用相互独立的伯努利随机变量建模 (即反转第i个节点的概率为），因此我们能够优化连续的伯努利参数了。具体我们可以利用重参数技巧来从中采样出离散的。至此LafAK的优化目标就变为了：

最后，我们利用SGD来迭代优化，优化结束后参考[2]中的策略决定最终的攻击，即如果是概率中最大的元素之一，则 -th标签将被翻转。这种策略背后的直觉类似于 greedy策略[2]。

3 防御方法

为了提高GCNs对标签翻转攻击的鲁棒性，我们通过分析GCNs在攻击下的学习过程，探究GCNs易受标签翻转攻击的原因。在图2中，我们分别绘制了clean/attack场景下的训练/验证精度。我们可以看到，与干净场景相比，有攻击的训练精度几乎没有变化，而训练精度和验证精度之间的差距明显增大。这通常表明GCN对翻转节点进行过拟合，并记忆其固有的错误信息，导致泛化性能较差。因此为了防止GCNs过拟合翻转标签是关键所在，此处我们假设社区结构可以作为高级信号正则节点分类任务。为了验证这一想法，我们将使用现有方法学习到的社区标签与GCN分类输出进行比较，如图3，我们可以看到，节点的团体标签与节点分类标签部分一致。因此，我们提出了一个基于自监督的防御框架, 它以社区分类任务作为辅助任务，引入社区级别的信号以惩罚过拟合翻转标签的GNN。

图2：clean/attack场景下的训练/验证精度

图3：社区标签 vs GCN输出

获取自监督标签：遵循常见的套路，我们首先通过现有的图嵌入方法如Deepwalk和ARGA将节点嵌入到低维空间中。然后使用标准的聚类算法(如K-means)将节点聚类到 (或更多)不同的组中，然后使用聚类赋值作为伪社区标签。

自监督辅助任务：我们使用保持社区结构的自监督任务作为GCNs训练的正则。具体地，我们将 -th层的隐藏特征矩阵作为 -way softmax分布的输入输出，然后利用社区标签构造辅助任务：

其中

, 是自监督任务的训练节点集合。低层参数将会被原始任务和辅助任务共享, 而高层参数和不共享，只要对翻转节点中的误导信号进行过拟合，共享层就会受到社区级信息的惩罚。我们在培训期间的总损失可表示为：

4 攻击实验

数据集：我们在以下四个常用数据集上进行实验：

对比方法：我们将我们的LafAK模型与以下基线进行比较:(1)随机翻转攻击( )，随机翻转相同数量节点的标签。(2)基于度的翻转攻击( )，翻转度最高的节点。(3)针对标签传播的标签翻转攻击( LPattack) []，这是最先进的基于图的半监督学习攻击模型。此外，为了进一步检验LafAK的每个部分的有效性，我们还考虑了两个变量:(1) :它利用标签传播闭合解计算未标记数据的预测,而不是我们的GCN近似闭合解。(2) :采用连续均方误差(MSE)代替0-1误差。

LafAK攻击效果实验：整体的攻击实验如下表所示，我们的模型LafAK显著降低了GCN在所有数据下的结果，这证明了GCN对标签翻转攻击的不鲁棒性。同时，LafAK比其他标签翻转攻击获得了更好的攻击效果，我们认为这是因为其他方法不能精确地近似标签对GCN模型的影响造成的。考虑模型的两个变量和，可以看出LafAK的性能优于和。结果表明，模型中GCN的近似闭合解和连续代理是合理有效的。

LafAK攻击的迁移性实验：如下图所示，基于GCN闭合解找到的攻击，可以成功迁移到GIN和GAT上，导致GIN和GAT模型效果的显著下降。

LafAK不同标签率下的攻击效果 ：如下图所示，标签率越高，整体ACC越高。但是不同标签率下，acc的下降趋势是比较一致的。

有限攻击知识：考虑更真实的攻击场景，即攻击者不知道unlabeled nodes的标签，此处采用GCN的预测结果来替代真实标签，发现攻击结果变化幅度很小，这凸显了LafAK的实用性。

5 防御实验

对比方法：(1) RGCN:一个鲁棒的GCN模型，针对对抗的拓扑/特征攻击。它采用高斯分布作为节点的隐藏表示，并使用基于方差的注意机制来弥补对抗性攻击的传播。(2) Sanitation:一个常见的防御技术对抗标签翻转攻击。它使用基于KNN的方法识别可能有标签损坏的训练点，然后删除/重新标记它们。这些基线都是用他们论文中建议的参数初始化的，我们也对这些参数进行了进一步的调整以获得最优的性能。

防御主实验：结果如下表所示，我们的模型显著提高了GCN模型在所有指标上的鲁棒性，这表明GCN可以极大地受益于保持社区的自我监督任务，减轻了翻转节点中对错误信息的过拟合。项目现有的方法RGCN和Sanitation不能防御我们的攻击。原因有:(1)RGCN主要针对的是特性/拓扑攻击，而不是标签翻转攻击。(2) Sanitization依赖大量的训练数据对翻转节点进行重标记，在半监督学习中可能失败。此外，与GCN相比，我们的模型在Pubmed数据集上的改进相对较小。这可能与Pubmed固有的群落结构较差有关。它暗示了社区结构对于提高鲁棒性的有效性。

防御泛化性：此外，为了证明我们提出的防御框架对其他GCN模型是通用的，我们还将我们的防御框架推广到RGCN、GAT和GIN，得到dRGCN、dGAT和dGIN。我们用固定翻转比率来评估其稳健性。结果如下图所示。我们可以看到，我们的防御框架可以成功地推广到现有的GCNs，提高了GCNs对标签翻转攻击的鲁棒性。

6 参考文献

[1]L. Sun, Y. Dou, C. Yang, J. Wang, P. S. Yu, and B. Li, “Adversarial attackand defense on graph data: A survey,”arXiv preprint arXiv:1812.10528,2018.

[2]X. Liu, S. Si, J. Zhu, Y. Li, and C. Hsieh, “A unified frameworkfor data poisoning attack to graph-based semi-supervised learning,” NeurIPS2019.

[3]K. Xu, H. Chen, S. Liu, P. Chen, T. Weng, M. Hong, and X. Lin, “Topology attack and defense for graph neural networks: An optimizationperspective,” IJCAI 2019.

本期责任编辑：杨成

本期编辑：刘佳玮

北邮 GAMMA Lab 公众号

主编：石川

责任编辑：王啸、杨成

编辑：刘佳玮

副编辑：郝燕如，纪厚业

专知便捷查看