参与:路、刘晓坤作者:Daniel Zügner、Amir Akbarnejad、Stephan Günnemann

KDD 2018 最佳论文:首个面向Facebook、arXiv网络图类的对抗攻击研究

8 月 19 日至 23 日,数据挖掘顶会 KDD 2018 在英国伦敦举行,昨日大会公布了最佳论文等奖项。最佳论文来自慕尼黑工业大学的研究者,他们提出了针对图深度学习模型的对抗攻击方法,是首个在属性图上的对抗攻击研究。研究者还提出了一种利用增量计算的高效算法 Nettack。此外,实验证明该攻击方法是可以迁移的。

图数据是很多高影响力应用的核心,比如社交和评级网络分析(Facebook、Amazon)、基因相互作用网络(BioGRID),以及互连文档集合(PubMed、Arxiv)。基于图数据的一个最常应用任务是节点分类:给出一个大的(属性)图和一些节点的类别标签,来预测其余节点的类别标签。例如,你可能想对生物相互作用图(biological interaction graph)中的蛋白质进行分类、预测电子商务网络中用户的类型 [13],或者把引文网络中的科研论文按主题分类 [20]。

尽管过去已经出现很多解决节点分类问题的经典方法 [8, 22],但是近年来人们对基于图的深度学习方法产生了极大兴趣 [5, 7, 26]。具体来说,图卷积网络 [20, 29] 方法在很多图学习任务(包括节点分类)上达到了优秀性能。

这些方法的能力超出了其非线性、层级本质,依赖于利用图关系信息来执行分类任务:它们不仅仅独立地考虑实例(节点及其特征),还利用实例之间的关系(边缘)。换言之,实例不是被分别处理的,这些方法处理的是某种形式的非独立同分布(i.i.d.)数据,在处理过程中利用所谓的网络效应(如同质性(homophily)[22])来支持分类。

但是,这些方法存在一个大问题:人们都知道用于分类学习任务的深度学习架构很容易被欺骗/攻击 [15, 31]。即使是添加轻微扰动因素的实例(即对抗扰动/样本)也可能导致结果不直观、不可信,也给想要利用这些缺陷的攻击者开了方便之门。目前基于图的深度学习方法的对抗扰动问题并未得到解决。这非常重要,尤其是对于使用基于图的学习的领域(如 web),对抗非常常见,虚假数据很容易侵入:比如垃圾邮件制造者向社交网络添加错误的信息;犯罪分子频繁操控在线评论和产品网站 [19]。

该论文试图解决这一问题,作者研究了此类操控是否可能。用于属性图的深度学习模型真的很容易被欺骗吗?其结果可信程度如何?

答案难以预料:一方面,关系效应(relational effect)可能改善鲁棒性,因为预测并未基于单独的实例,而是联合地基于不同的实例。另一方面,信息传播可能带来级联效应(cascading effect),即操纵一个实例会影响到其他实例。与现有的对抗攻击研究相比,本论文在很多方面都大不相同。

图 1:对图结构和节点特征的极小扰动导致目标误分类。

该论文提出一个对属性图进行对抗扰动的原则,旨在欺骗当前最优的图深度学习模型。具体来说,该研究主要针对基于图卷积网络(如 GCN [20] 和 Column Network(CLN)[29])的半监督分类模型,但提出的方法也有可能适用于无监督模型 DeepWalk [28]。研究者默认假设攻击者具备全部数据的知识,但只能操纵其中的一部分。该假设确保最糟糕情况下的可靠脆弱性分析。但是,即使仅了解部分数据,实验证明本研究中的攻击仍然有效。该论文的贡献如下:

  • 模型:该研究针对节点分类提出一个基于属性图的对抗攻击模型,引入了新的攻击类型,可明确区分攻击者和目标节点。这些攻击可以操纵图结构和节点特征,同时通过保持重要的数据特征(如度分布、特征共现)来确保改变不被发现。

  • 算法:该研究开发了一种高效算法 Nettack,基于线性化思路计算这些攻击。该方法实现了增量计算,并利用图的稀疏性进行快速执行。

  • 实验:实验证明该研究提出的模型仅对图进行稍微改动,即可恶化目标节点的分类结果。研究者进一步证明这些结果可迁移至其他模型、不同数据集,甚至在仅可以观察到部分数据时仍然有效。整体而言,这强调了应对图数据攻击的必要性。

论文:Adversarial Attacks on Neural Networks for Graph Data

论文链接:https://arxiv.org/pdf/1805.07984.pdf

摘要:应用到图的深度学习模型已经在节点分类任务上实现了强大的性能。尽管此类模型数量激增,但目前仍未有研究涉及它们在对抗攻击下的鲁棒性。而在它们可能被应用的领域(例如网页),对抗攻击是很常见的。图深度学习模型会轻易地被欺骗吗?在这篇论文中,我们介绍了首个在属性图上的对抗攻击研究,具体而言,我们聚焦于图卷积模型。除了测试时的攻击以外,我们还解决了更具挑战性的投毒/诱发型(poisoning/causative)攻击,其中我们聚焦于机器学习模型的训练阶段。

我们生成了针对节点特征和图结构的对抗扰动,因此考虑了实例之间的依赖关系。此外,我们通过保留重要的数据特征来确保扰动不易被察觉。为了应对潜在的离散领域,我们提出了一种利用增量计算的高效算法 Nettack。我们的实验研究表明即使仅添加了很少的扰动,节点分类的准确率也会显著下降。另外,我们的攻击方法是可迁移的:学习到的攻击可以泛化到其它当前最佳的节点分类模型和无监督方法上,并且类似地,即使仅给定了关于图的有限知识,该方法也能成功实现攻击。

图 2:随着扰动数量的增长,平均代理损失(surrogate loss)的变化曲线。由我们模型的不同变体在 Cora 数据集上得到,数值越大越好。

图 3 展示了在有或没有我们的约束下,得到的图的检验统计量 Λ。如图可知,我们强加的约束会对攻击产生影响;假如没有强加约束,损坏的图的幂律分布将变得和原始图更加不相似。类似地,表 2 展示了特征扰动的结果。

图 3(左):检验统计量 Λ 的变化(度分布)。图 4(右)梯度 vs. 实际损失。

表 2:Cora 上每个类别中的特征扰动 top-10。

图 6a 评估了两个攻击类型的 Nettack 性能:逃逸攻击(evasion attack),基于原始图的模型参数(这里用的是 GCN [20])保持不变;投毒攻击(poisoning attack),模型在攻击之后进行重新训练(平均 10 次运行)。

图 6b 和 6c 显示,Nettack 产生的性能恶化效果可迁移至不同(半监督)图卷积方法:GCN [20] and CLN [29]。最明显的是,即使是无监督模型 DeepWalk [28] 也受到我们的扰动的极大影响(图 6d)。

图 6:使用不同攻击算法在 Cora 数据上的结果。Clean 表示原始数据。分值越低表示结果越好。

图 7 分析了攻击仅具备有限知识时的结果:给出目标节点 v_0,我们仅为模型提供相比 Cora 图其尺寸更大的图的子图。

图 7:具备有限数据知识的攻击。

表 3 总结了该方法在不同数据集和分类模型上的结果。这里,我们报告了被正确分类的部分目标节点。我们对代理模型(surrogate model)的对抗扰动可在我们评估的这些数据集上迁移至这三种模型。毫不奇怪,influencer 攻击比直接攻击导致的性能下降更加明显。

表 3:结果一览。数值越小表示结果越好。

理论获奖论文KDD 2018对抗样本
2
相关数据
深度学习技术

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

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

参数技术

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

神经网络技术

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

数据挖掘技术

数据挖掘(英语:data mining)是一个跨学科的计算机科学分支 它是用人工智能、机器学习、统计学和数据库的交叉方法在相對較大型的数据集中发现模式的计算过程。 数据挖掘过程的总体目标是从一个数据集中提取信息,并将其转换成可理解的结构,以进一步使用。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

分类问题技术

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

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