Taylor Wu作者

KDD 2018最佳论文解读 | 图神经网络对抗攻击

本篇文章介绍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实至名归!


极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

入门深度学习对抗样本
5
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

半监督学习技术

半监督学习属于无监督学习(没有任何标记的训练数据)和监督学习(完全标记的训练数据)之间。许多机器学习研究人员发现,将未标记数据与少量标记数据结合使用可以显着提高学习准确性。对于学习问题的标记数据的获取通常需要熟练的人类代理(例如转录音频片段)或物理实验(例如,确定蛋白质的3D结构或确定在特定位置处是否存在油)。因此与标签处理相关的成本可能使得完全标注的训练集不可行,而获取未标记的数据相对便宜。在这种情况下,半监督学习可能具有很大的实用价值。半监督学习对机器学习也是理论上的兴趣,也是人类学习的典范。

激活函数技术

在 计算网络中, 一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。 一种函数(例如 ReLU 或 S 型函数),用于对上一层的所有输入求加权和,然后生成一个输出值(通常为非线性值),并将其传递给下一层。

交叉熵技术

交叉熵(Cross Entropy)是Loss函数的一种(也称为损失函数或代价函数),用于描述模型预测值与真实值的差距大小

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

概率分布技术

概率分布(probability distribution)或简称分布,是概率论的一个概念。广义地,它指称随机变量的概率性质--当我们说概率空间中的两个随机变量具有同样的分布(或同分布)时,我们是无法用概率来区别它们的。

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

直推式学习技术

在逻辑学、统计推理和监督学习中,转换或转换推理是从观察到的具体(训练)案例到具体(测试)案例的推理。 这与常见的案例-一般规则-案例的归纳推理有所不同

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

分类问题技术

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

对抗样本技术

对抗样本是一类被设计来混淆机器学习器的样本,它们看上去与真实样本的几乎相同(无法用肉眼分辨),但其中噪声的加入却会导致机器学习模型做出错误的分类判断。

推荐文章
暂无评论
暂无评论~