TKDE'21 | 面向大规模图数据的对抗攻击

作者：Jintang Li, Tao Xie, Liang Chen, Fenfang Xie, Xiangnan He, Zibin Zheng
单位：中山大学&中国科学技术大学
论文链接：https://arxiv.org/abs/2009.03488
代码链接：https://github.com/EdisonLeeeee/SGAttack
DeepRobust代码链接：https://github.com/DSE-MSU/DeepRobust

今天分享的是中大图学习团队在图对抗攻防领域的一篇文章：Adversarial Attack on Large Scale Graph，已被TKDE期刊收录。

1前言

最近的一些研究表明，图神经网络模型在面对恶意攻击时往往显得很脆弱，从而很容易被误导。虽然现有的一些攻击方法如利用梯度信息等的策略拥有比较优异的攻击效果，但是这些方法具有较大的时间和空间复杂度，所以并不能被利用到较大规模的图数据集上。作者认为这主要是因为这些方法往往需要利用完整的图来进行训练，导致时空复杂度会随着数据的规模而不断增大。基于此，作者提出了Simplified Gradient-based Attack (SGA) 攻击策略。SGA只需要考虑基于目标节点的 阶子图来进行梯度的计算，从而极大地降低了在大数据集上时间和空间的消耗。此外，针对攻击隐蔽性问题，作者基于同度性(Assortativity)指标，提出了Degree Assortativity Change (DAC) 来衡量不同攻击的隐蔽性。

图数据上的对抗攻击场景示例。通过修改目标节点周围少量边的连接，从而导致图神经网络误分类目标节点

2研究背景

在图攻击领域中存在着两个挑战。

• 可扩展性：现有的图攻击方法由于需要储存和计算不必要的图信息，所需的时间和空间复杂度较高，往往不能很好地扩展到大数据集上。
• 攻击扰动的衡量：区别于连续形式的图像数据，非欧结构的图数据是一个离散结构，所以我们并不能使用 正则或者 正则来衡量扰动大小，因此如何衡量攻击扰动的隐蔽性也是一个亟待解决的问题。

本文考虑基于图结构的投毒目标攻击（Poisoning targeted attack），即关注训练阶段且针对特定节点的攻击，攻击方式仅限于修改图结构（不包括对节点特征的攻击）。

3本文方法

本文的主要贡献主要有两部分：（1）快速有效的图攻击框架SGA；（2）攻击隐蔽性的度量指标DAC。

3.1SGA框架

SGA算法介绍

SGA框架基于以往采用替代模型进行攻击的思路，主要有以下几个步骤：

• 训练替代模型：类似NETTACK，作者首先训练了一个基于 层SGC（相对于GCN，SGC去掉了中间层的激活函数）的替代模型
• 提取 阶子图：以当前攻击的目标结点为中心，提取 阶子图的边作为备选修改边，并使用稀疏矩阵存储
• 快速梯度计算：接着，计算 阶子图中边的梯度，但由于备选边集合中仅包含子图内相连接的边，所以往往只能进行删边操作；因此需要引入“不存在的潜在边”作为备选集合的补充。因此，作者基于“Disconnect Internally, Connect Externally”的方法引入了预测可能性排名第二的类别的所有节点（第一的类别为真实类别）。最终，整个子图包含 阶内的相邻节点以及预测类别为第二高可能性的所有节点。
• 迭代梯度上升攻击：以这些节点为候选点，子图内的边及部分潜在可能连接的边作为候选边集，执行迭代式地梯度攻击，即每次选择梯度绝对值最大的合法边执行对应的加边/减边操作。

SGA框架攻击示意图

SGA算法执行流程

时间/空间复杂度比较

其中 Nettack是采用稀疏矩阵存储，然后根据贪心算法迭代计算每条边修改的影响来进行攻击，虽然空间复杂度在大图上可以接受，但是时间复杂度过高；GradArgmax则是传统的基于梯度的算法，将图存储为密集邻接矩阵计算每条边的梯度，不仅空间复杂度高并且时间复杂度也不低。本文提出的SGA攻击算法，由于仅需要目标结点的 阶子图进行计算，因此兼具时间和空间复杂度上的高效。

3.2攻击隐蔽性度量DAC

本篇文章的另一个贡献是提出攻击隐蔽性度量指标同度性变化(Degree Assortativity Change, DAC)。

同度性系数degree assortativity coefficient：即不同度数的节点之间相互连的倾向，如果同度性系数比较高，则代表高度节点倾向于与高度节点相连，反之则倾向于与低度节点相连。同度性系数基于皮尔森系数定义，描述了一个网络中各个节点的连接倾向程度。

作者基于同度性系数定义了DAC指标，具体为：

其中 为原图的同度性系数， 为攻击目标节点后生成的扰动图的同度性系数。当攻击隐蔽性越高，攻击前后网络的DAC指标变化的越小。

4实验结果

4.1数据集介绍

除了传统的几个引文网络数据集外，考虑了23w+节点的Reddit数据集

数据集信息

4.2主要实验

首先作者比较了攻击效率，包括运行时间和空间消耗，所提方法具有运行时间段、运行内存消耗少、攻击隐蔽性强等有点。

4个数据集上与对比算法在时间，空间以及DAC变化指标下的对比

三种攻击方法在三个数据集上，进行两种不同攻击时的相对运行时间

接着是比较攻击效果，所提方法在各个数据集上均取得了较好的表现，并且能够扩展至大数据集场景：

2个小数据集上对不同GNN模型准确度的影响

2个较大数据集上的实验结果

5总结

本文针对图对抗攻防场景，提出了一种基于 阶子图的攻击方法，能够快速有效地对图神经网络进行攻击；此外，作者还提出了一种衡量攻击影响程度的度量指标，可用于对攻击隐蔽性进行评价。