本篇文章介绍KDD2018的最佳论文—图神经网络对抗攻击，该论文针对图节点分类任务进行对抗攻击。
论文题目：
Adversarial Attacks on Neural Networks for Graph Data
论文地址：
http://cn.arxiv.org/pdf/1805.07984
源码地址：
https://www.kdd.in.tum.de/nettack
摘要
深度学习在图的很多任务上已经实现了很好的效果，比如节点分类，图分类等。但是目前对于图的对抗攻击基本是空白的，图的深度学习模型是否容易受到被对抗样本“迷惑”呢？本篇论文，作者首次研究了对基于属性图的GCN进行了对抗攻击研究，由于GCN很多都是直推式学习（trian阶段使用test数据），论文不仅讨论了测试攻击也讨论了poisoning攻击（训练之前攻击）。
机遇与挑战
由于是对属性图进行操作，对抗扰动可以以两种方式进行：改变节点特征或者改变图的结构。对图中节点之间互相依赖的机构的扰动是之前没有研究过的，但是这确是一个现实世界中非常可能发生的情况：例如，一个人可以在社交网络中添加或者删除某个好友。
当前研究仅限于对一个特定节点进行扰动以使其产生错误的预测。但是图的关联效应却赋予我们更强大的潜力：通过改变一个节点，我们可能干扰其他节点的预测结果。并且这在现实世界中是一个很可能实现的，想像一个黑客谁劫持了一些帐户，然后他操纵这些帐户，以干扰对那些他没有控制一个帐户的预测，这个甚至是造成更加恐怖的影响，下图是一个示意图。
挑战
不像图像这种由连续特征组成的数据，图的结构和以及大部分情况下的节点特征都是离散的，所以基于梯度构造干扰的方法不适用，那么怎么设计有效的算法来在离散空间找到对抗样本呢？
对抗样本一个要求是对于人类的不可分辨性，例如图像，我们可以通过限制每个像素变化很小的值使得人类无法分辨图像的变化。对于大规模的Graph来说，可视化适不适合人肉观察的（会看到错综复杂的点和线），那么怎么定义这种“不可分辨性”呢？
最后，对于图节点任务，一般是直推式学习——训练期间使用train data和test data。这意味着常用的evasion攻击（模型的参数在train data上优化，并假设固定）是不符合实际的，我们需要考虑poisoning攻击（模型是在对抗样本上训练和测试的）。
攻击模型
图节点分类任务
这里简单的介绍图卷积，详细内容可以参考我的这篇综述Graph Neural Network Review
令 
表示属性图，其中
表示邻接矩阵，
表示节点特征矩阵，节点集合用
表示。图节点分类问题描述为，给定一个带有标签的子集
，标签集合为
，节点分类的目标是学习一个函数：
，这是一个半监督学习任务。
图卷积公式为：
节点分类在最后一层进行，公式如下：
其目标函数为有标签节点的交叉熵损失：
其中
表示节点
的标签。
问题定义
令
表示原始图，对原始进行微扰变为
，其中对于
的微扰叫做结构攻击，对
的微扰叫做特征攻击。
Target vs. Attackers. 我们的目标是攻击一个特定的节点
，使得其预测发生变化。由于图是一个非i.i.d.数据，对
的预测不仅和自身的有关，还和图中其他节点有关（尤其是其邻域节点）。因此考虑将节点分类target节点和attacker节点，target节点即为目标节点，attacker节点即为我们可以操纵的节点（在其上施加扰动），attacker集
如下：
如果
，则成为直接攻击（direct attack）；如果
，则成为影响攻击（influencer attack）
图节点分类对抗攻击问题定义为：
其中
表示所有扰动样本组成的空间。这个公式可以这样理解，对于所有扰动样本，找出使得在其上训练得到的分类器
对于目标节点
的分类错误率最高的样本，该样本即为对抗样本。
扰动样本
如何定义图上的扰动是不可分辨的？对于图来说有两种扰动，一种是结构扰动，一种是特征扰动，分别定义。
结构扰动：对于图结构来说，一个很好地描述是使用其节点度的分布。因为现实生活中很多网络都是无标度网络，其度分布是一个幂律分布
。那么可以定义结构扰动不可分辨为：扰动前后，图节点度满足同一个分布。对于图来说
可以是如下公式进行近似：
如果
和
都是
的采样，我们就可以认为这两个图是不可分辨的。我们可以通过log-likehood分数
来衡量一个数据集是否是一个概率分布的采样。论文中采用log-likehood分数差来衡量结构扰动的差距：
当
时，我们认为结构干扰是不可分辨的。
特征扰动：对于节点特征来说，如果两个特征从未共同出现过（特征都为1），而扰动使得他们共现了，那对我们来说应该是比较容易观察到的；相反，如果两个特征经常一起出现，而某个节点特征中他们没有共现，扰动以后他们共现了，这对我们来说是不容易分辨的。举个例子，一篇关于深度学习的文章很可能同时出现“深度学习”和“神经网络”，如果某个深度学习文章这两个单词没有共同出现，而我们只需要稍微修改就可以使得他们共现，并且不会使得文章很突兀；相反如果我们想加入“氢氧化钠”这种词汇，会使得文章很突兀。
数学上可以这样描述，定义
表示
中特征的共现关系，其中
表示所有特征组成的集合，
表示特征共现概率矩阵。令
表示节点
所有不为0的特征序号，对于节，考虑一个扰动：添加一个特征
，如果满足以下条件，我们认为该特征扰动是不可分辨的：
公式(8)理解为特征间共现概率的加权平均，
越大表示该特征越平凡，即该特征与很多特征都共现，那如果添加的特征和它共现了意义也不大。
扰动的绝对大小：对于扰动的绝对大小也得进行限制：
那么对于一个扰动，如果满足以上三个条件，我们认为是不可分辨的，即
需满足上述三个条件。
生成对抗样本
生成对抗样本的思路为：对一个代理模型按照如上所述进行攻击，并且对结构扰动和特征扰动进行近似解耦，以此方式可以使用序列优化的方法生成对抗样本，论文后面实验这种对抗样本可以迁移到其他的模型。
论文中使用的代理模型为，激活函数为恒等函数的两层GCN网络：
其中softmax可以去掉，因为我们的目标是比较对目标节点
的预测的变化。给定以训练好的代理模型（
固定）的损失函数如下：
我们的目标是
为了方便优化，将结构扰动和特征扰动分开：
其中
分别表示增加/移除一个边或特征，
.算法如下：
论文主体部分就这么多了，后面有一些证明与优化，再接着是实验，本文不再介绍，感兴趣的同学去看论文即可。
总结
深度学习一大诟病就是更加容易受到对抗样本的攻击，随着深度学习在图上的应用，图的对抗攻击研究会越来越深入，本篇论文是图对抗攻击的开山之作，确实有很多值得学习的建模思想，KDD2018 Best Paper实至名归！
