阅读更多，欢迎关注公众号：论文收割机（paper_reader）
原文链接：综述：图数据上的对抗攻击与防御
Sun, Lichao, Ji Wang, Philip S. Yu, and Bo Li. "Adversarial Attack and Defense on Graph Data: A Survey." arXiv preprint arXiv:1812.10528 (2018).
最新论文列表（持续更新）
引言
我们去年在公众号中第一时间介绍了KDD 2018（Best Paper）[1] 和 ICML 2018 [2] 中两篇关于在图数据（Graph Data）上攻击和防御的论文。可以预见的是，在图数据上面的对抗攻击将成为近两年数据挖掘和机器学习研究的热点话题。
今天，我们将结合一篇最近在Arxiv上发表的图数据对抗攻击综述(文首引用)，来对目前发表的文章做一个总结和概括，希望读者能对这个问题有一个比较宏观的理解。（点击文末阅读原文获取综述链接）
背景
在机器学习领域，对抗样本和对抗训练的概念通过2014年Ian Goodfellow提出的对抗生成网络被大家熟知。早期的对抗训练方法主要是应用在图像，语音和文本数据。因为这些数据是连续的，对抗的样本和噪音比较容易产生。并且，对抗生成网络在一些视觉和文本任务中比原来方法有了显著地进步。
最近两年，随着深度学习的思想被应用到图数据中，对于图的研究从原来的传统模型逐渐转移到了表示学习（representation learning）上面。大家发现，其实图数据在工业和学术界中非常常见，任何的关系数据都可以用图来建模，最常见的应用便是推荐系统和知识图谱。更有人指出，图数据是人工智能的基石。
把对抗思想应用到图数据是一个自然的过程，而且其在具体应用场景中也有广泛的案例，例如在在线社交网络中，水军账户通过关注正常账户，发布日常内容，来降低自己在社交网络的中可疑度，从而避免被检测到而封号。
2018年的KDD [1] 和 ICML [2] 两篇文章掀开了图数据对抗攻击与防御研究的大幕。到2019年四月，已经有将近五篇的后续研究文章出现在Arxiv和ICLR中，在最近公布结果的IJCAI，KDD和 ICML中，相信能看到更多关于这个话题的论文。
下面，我将介绍如何定义图数据上的对抗攻击，攻击的约束，攻击的目标，攻击方法以及防御方法。
图1：图数据对抗攻击基本流程 [1]
定义及约束
图数据对抗攻击的定义是：给定一个图（节点和边），通过修改这个图，使得这种修改在不被察觉到情况下，能够降低算法（例如节点分类和链接预测）在图数据上面的表现。
和优化问题相似，攻击方的目标是在一定约束的条件下最大可能地干扰算法的表现。在KDD 2018 [1]的文章中，作者将图被修改之后带来的变化定义为perturbations（扰动），即攻击者对图数据的攻击后的扰动必须满足与一些约束。例如，我们加边或者减边不能太多条，要保持图的基本结构等等，这是对抗攻击实现的前提。
具体来说有两种类型的扰动：
维持结构的扰动（Structure-preserving Perturbation）：加减节点和边会改变一些图的结构属性，例如度分布，节点中心性。其本质都是对边（Link）的改变。所以新产生的对抗样本要保持这些结构属性的变化在一定范围内。目前大部分文章都是这种类型的攻击；
维持属性的扰动（Attribute-preserving Perturbation）：第二种扰动是通过修改节点属性特征来实现，所以攻击者要保证这些属性不能发生明显变化，我们可以通过衡量节点（边）特征向量的相似度来维持特征的稳定性。去年KDD [1] 的文章就攻击了节点的属性特征。
攻击方法和类别
从计算机安全研究角度来说，对抗攻击不是一个新的话题，因为对抗攻击本来就是计算机安全研究的一个传统研究方向和研究手段。在对图数据攻击方法进行分类时，我们利用计算机安全研究的术语，将其分为投毒（poisoning）攻击和逃脱（evasion）攻击：
投毒攻击（Poisoning Attack）：新产生的对抗样本将被用于新算法的训练，形象地来说，攻击者对算法的训练集进行投毒，从而影响训练好的算法在未被污染的测试集上面的表现；
逃脱攻击（Evasion Attack）：新产生的对抗样本只存在测试集中，算法将在未被污染的训练集上训练。攻击者的目标是让对抗样本影响原来训练好的算法在测试集的表现。
根据图数据的特点，我们还可以图数据对抗攻击任务分为三类：
节点相关的任务（Node-related Task）：对节点分类任务还有对节点嵌入（node embedding）的攻击都属于节点层面的攻击，其目的是让分类器分错，降低其精确率或者召回率。因为节点分类是目前图数据的主要任务，因此大部分图数据对抗攻击论文都有研究到节点分类任务；
链接相关的任务（Link-related Task）：链接预测（Link Prediction）是图数据上面的另一个主要任务，推荐系统，知识图谱，社交网络都用到它。对于链接层面的攻击，主要目的让算法预测到错的链接目标；
全图相关的任务（Graph-related Task）：全图相关的任务主要是对整个图的分类，常见于对生物结构的分类任务。一般是学习图整体结构的低维嵌入，然后进行分类。这方面的对抗攻击研究还比较少，可参考[3]。
还是借鉴计算机安全研究的方法，我们可以根据攻击者掌握的信息，对攻击方法进行另一个维度的分类：
白盒攻击（White Box Attack）：攻击者掌握对方系统的所有信息，包括使用何种方法，算法输出结果，计算中的梯度等等。这种场景是指当攻击者完全攻入目标系统的时候；
灰盒攻击（Grey Box Attack）：攻击只掌握一部分信息便可以发动攻击，这种攻击比白盒攻击更具有危害，因为攻击者不需要完全攻破目标系统就可以发动攻击。在研究中，我们可以针对具体任务和场景，对灰盒攻击再进一步细分类别；
黑盒攻击（Black Box Attack）：攻击者只能查询到有限的攻击结果，对目标系统的机制完全不了解。这种攻击难度最大，对与防御方的危害也最大。
根据攻击者的目标，我们又可以将攻击分为:
可用性攻击（Availability Attack）：攻击者的目标是降低整个系统的表现，例如整体的精确度，召回率等等；
完整性攻击（Integrity Attack）：攻击者的目标是降低对于特定热任务或者对象的表现，对整体表现不要求。例如，在好友推荐任务（链路预测）中，攻击者可以让算法无法预测到特定两个人之间的好友关系。
图2：对链接预测任务的攻击流程示意图 [9]
总结与展望
通过上面的介绍，我们对图数据上的的对抗攻击有了基本认识。目前的工作中，[2] 通过强化学习研究图神经网络的对抗攻击，[1] 研究了传统模型和深度模型在图数据上的对抗攻击，而且是第一篇研究属性图（Attribute Graph）的文章。[4] 从对抗攻击的方法研究了图数据上聚类算法的安全性。[5，6] 研究了链接预测任务上的对抗攻击。我们可以看到，之前大部分研究都是基于深度模型，最近在Arxiv上面，[7] 提出了传统图模型上的对抗攻击，并将其用一个优化问题定义。
在今年的ICLR中，去年KDD Best Paper的作者，又有一篇图对抗攻击的文章被接收，是今年ICLR唯一接收的图对抗攻击的文章 [8]。这篇文章使用元学习（meta learning）的方法，对节点分类任务的训练过程进行攻击。该文章表示，新的攻击方法在极小的扰动下便可以大大降低图卷积网络（GCN）的表现。
在今年ICLR没有接收的文章中，还有利用对抗生成网络（GAN）生成相近的特征空间，从而产生对抗样本；也有对节点嵌入进行攻击的文章。具体大家可以在文首的综述原文中查看。
在已有的大部分研究中，对于扰动以及约束的定义基本上基于概念和模型，缺乏可解释性以及与实际应用的联系。而且大部分攻击模型只采用一种约束条件，由此产生的对抗样本很容易被另外一个新的指标检测到。而且在现有工作中，大部分指提出了攻击方法，很少有研究防御方法。
对于未来的研究，可以更多的探究更具实际价值的攻击方法和防御方法。根据上面到各种攻击方法和种类，有很多的方面还没有被探究。在一些属性图例如异质信息网络（Heterogeneous Information Network）研究也有待探索。正如上段提到的，考虑多种约束的攻击与防御也是一个很好的研究方向。目前针对传统图模型算法例如随机游走（Random Walk），信度传播（Belief Propagation）的对抗攻击还很少，这也是一个未来的研究方向。
在今年IJCAI，KDD 和 ICML 的接收论文公布后，本公众号还会献上最新的关于图数据对抗攻击与防御研究的解读，敬请期待。
Reference
[1] Zügner, Daniel, Amir Akbarnejad, and Stephan Günnemann. "Adversarial attacks on neural networks for graph data." In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-2856. ACM, 2018.
[2] Dai, Hanjun, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. "Adversarial Attack on Graph Structured Data." In International Conference on Machine Learning, pp. 1123-1132. 2018.
[3] Duvenaud, David K., Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. "Convolutional networks on graphs for learning molecular fingerprints." In Advances in neural information processing systems, pp. 2224-2232. 2015.
[4] Chen, Yizheng, Yacin Nadji, Athanasios Kountouras, Fabian Monrose, Roberto Perdisci, Manos Antonakakis, and Nikolaos Vasiloglou. "Practical attacks against graph-based clustering." In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1125-1142. ACM, 2017.
[5] Jinyin Chen, Ziqiang Shi, Yangyang Wu, Xuanheng Xu, and Haibin Zheng. Link prediction adversarial attack. arXiv preprint arXiv:1810.01110, 2018.
[6] Sun, Mingjie, Jian Tang, Huichen Li, Bo Li, Chaowei Xiao, bldlz, and 坚定的小白菜. "Data poisoning attack against unsupervised node embedding methods." arXiv preprint arXiv:1810.12881 (2018).
[7] Wang, Binghui, and Neil Zhenqiang Gong. "Attacking Graph-based Classification via Manipulating the Graph Structure." arXiv preprint arXiv:1903.00553 (2019).
[8] Zügner, Daniel, and Stephan Günnemann. "Adversarial Attacks on Graph Neural Networks via Meta Learning" arXiv preprint arXiv:1902.08412 (2019).
[9] Sun, Mingjie, Jian Tang, Huichen Li, Bo Li, Chaowei Xiao, bldlz, and 坚定的小白菜. "Data poisoning attack against unsupervised node embedding methods." arXiv preprint arXiv:1810.12881 (2018).