图对抗攻击研究综述

142021，57（7）ComputerEngineeringandApplications计算机工程与应用图对抗攻击研究综述翟正利，辉，冯舒青岛理工大学信息与控制工程学院，山东青岛266525摘要：将深度学习用于图数据建模已经在包括节点分类、链路预测和图分类等在内的复杂任务中表现出优异的性能，但是图神经网络同样继承了深度神经网络模型容易在微小扰动下导致错误输出的脆弱性，引发了将图神经网络应用于金融、交通等安全关键领域的担忧。研究图对抗攻击的原理和实现，可以提高对图神经网络脆弱性和鲁棒性的理解，从而促进图神经网络更广泛的应用，图对抗攻击已经成为亟待深入研究的领域。介绍了图对抗攻击相关概念，将对抗攻击算法按照攻击策略分为拓扑攻击、特征攻击和混合攻击三类；进而，归纳每类算法的核心思想和策略，并比较典型攻击的具体实现方法及优缺点。通过分析现有研究成果，总结图对抗攻击存在的问题及其发展方向，为图对抗攻击领域进一步的研究和发展提供帮助。关键词：图数据；图神经网络；图对抗攻击；对抗样本文献标志码：A中图分类号：TP181doi：10.3778/.1002-8331.2012-0367ResearchOverviewofAdversarialAttacksonGraphsZHAIZhengli,LIPenghui,FENGShuSchoolofInformationandControlEngineering,QingdaoUniversityofTechnology,Qingdao,Shandong266520,ChinaAbstract：Deeplearningforgraphdatamodelinghasshownexcellentperformanceincomplextasks,includingnodeclassification,linkprediction,r,thesubtlepeuralnetworksalsoinheritthisvulnerability,ithasraisedconcernsforadaptinggraphneustigatingthemechanismandmethodofgraphadversarialattacks,itcanimprovetheunderstandingofvulnerabilityandrobustnessofgraphneuralnetworks,dvery,,accordingtoattackstrategies,adversarialattackalgorithmsareclassifiedintothreecategories,includingtopologyattack,er,eachcategoryissummarized,rmore,sometypicalattacksarecompared,includingspecificimplementationmethods,advantages,htheanalysisofthestateoftheart,theexistingproblemsanddevelopmentdirectionofgraphadversarialattacksaresummarized,ds：graphdata;graphneuralnetwork;graphadversarialattack;adversarialexample近年来，得益于计算机计算能力的提升，大量可用的数据集以及算法的创新，深度神经网络在图像识别[1]、语义分割[2]、自然语言处理[3]、推荐系统[4]等领域表现出卓越的性能。图作为一种表示对象及对象之间关系的数据结构，在现实世界中广泛存在，如交通网络、社交网络、通信网络等。图神经网络[5-7]将基于深度学习的方法应用于图数据上，通过聚合图中节点的邻域信息学习图基金项目：国家自然科学基金（61502262）。数据的结构信息和特征信息，在节点分类、链路预测、图嵌入等方面得到迅速发展。虽然深度神经网络具有出的性能，但是近来研究表明，在精心设计的微小扰动下，深度神经网络性能会严重下降[8-9]。例如在图像分类[10]和文本分类[11]场景下，只需修改少数像素或文字就可以改变大部分测试数据的预测结果。作为深度神经网络在图数据上的应用，图作者简介：翟正利（1972—），通信作者，男，博士（后），副教授，CCF会员，研究方向为深度学习、网络信息服务、Petri网理论与应用、智能信息处理等，E-mail：***********；辉（1995—），男，硕士研究生，研究方向为对抗攻击与防御、机器视觉；冯舒（1995—），女，硕士研究生，研究方向为深度学习、推荐系统。收稿日期：2020-12-21修回日期：2021-02-18文章编号：1002-8331（2021）07-0014-08

翟正利，等：图对抗攻击研究综述神经网络也同样继承了深度神经网络的脆弱性[12]，如图1所示，在图中添加或删除少量边将导致模型产生错误分类，随着图神经网络在实际生产环境的部署应用[13]，这种脆弱性引起了学术界和工业界的诸多担忧[14]，例如在安全至关重要的金融系统中，攻击者可能通过建立与高信用客户的连接，达到绕过检测系统并获得更高的信用值的目的。[：][：][：][：][：]+[：][：][：]测预模型预测−型模类别A类别B类别C待预测节点[：]节点特征图1微小扰动导致节点的错误分类随着人们对于图模型安全性的关注，图对抗攻击的研究不断取得新的进展，但与针对传统深度神经网络的攻击相比，针对图神经网络的对抗攻击存在以下挑战：1）与图像等具有连续特征的欧式空间数据不同，图数据的结构信息和特征信息是离散的，因此设计有效的攻击算法更具挑战性；（2）由于图数据在现实世界的广泛存在，使得图数据具有多种类别，同时，现实世界的图可以包含数以千万计的节点，如社交网络等，图数据的多样性和大规模性对算法的时间和空间复杂度提出了更高的要求；（3）在图像中，可以使用特定的距离函数来衡量人眼无法察觉的扰动的大小，而在图数据中，不仅难以定性扰动是否可察觉，而且定量的评估标准也亟待分析研究。随着对图对抗攻击研究的深入，攻击理论和模型已经得到了迅速的发展，推动图对抗攻击的研究，有助于提高对图神经网络的更深层次的理解，提高模型的鲁棒性与可解释性，以促进其更广泛的应用。本文对现有图对抗攻击研究进行全面、系统的介绍，对不同攻击算法的建模方法进行比较和总结，根据攻击算法的不同攻击策略进行分类，并总结了图对抗攻击领域面临的挑战以及发展方向。1定义与符号设图G=(A,E)，其中V={v1,v2,…,vn}表示图中n个节点的集合，E表示图中m条边的集合，E中每个元素eij=(vi,vj)表示从节点vi到节点vj的边；使用邻接矩阵A∈Rn×n表示图中节点间的连接，当eij∈E时Aij=1，2021，57（7）15否则Aij=0；使用X∈Rn×d表示图G上节点的特征矩阵，其中Xi∈Rd表示图中第i个节点的d维特征。未添加扰动的图称为原始图或干净图，而添加了扰动ε后的图称为扰动图或对抗样本G′，扰动ε的上限称为扰动预算Δ，使用fθ*表示攻击者训练得到的结构和性能与被攻击模型相似的代理模型，表1列示了本文常用符号及含义。表1符号及说明符号说明符号说明G=(V,E)节点集合为V，边集合为E的图X节点特征矩阵n图中节点的数量fθ参数为θ的神经网络模型m图中边的数量fθ*参数为θ*的代理模型eij节点vi到vj的边L损失函数扰动后的对象，其中(∙)可以为图、邻接矩Nk(vvi的k阶邻居i)节点集合(⋅)′阵或节点特征矩阵，如A′表示扰动后的邻接矩阵deg(vi)节点vi的度ε扰动量A邻接矩阵Δ扰动预算2图对抗攻击概述根据攻击者对目标模型的了解，将攻击分为白盒攻击和黑盒攻击，白盒攻击是指攻击者完全了解模型信息的情况下进行的攻击，黑盒攻击则是指攻击者部分了解甚至完全不了解目标模型情况下进行的攻击；根据攻击发生的不同阶段，可以将攻击分为逃逸攻击和投毒攻击，其中逃逸攻击发生在模型测试阶段，而投毒攻击发生在模型训练阶段[15]；根据攻击的目标，可以将攻击分为定向攻击和非定向攻击，定向攻击指攻击后模型输出攻击预设值，非定向攻击指攻击后模型输出任意错误值；根据攻击方式可以将攻击分为拓扑攻击和特征攻击，拓扑攻击通过修改图结构进行攻击，特征攻击通过修改节点特征进行攻击[12]。总结现有图对抗攻击算法，使用以下定义描述图对抗攻击：定义1（图对抗攻击）图对抗攻击是指通过在图G上添加微小扰动ε，得到对抗样本G′，使模型性能大幅度下降：max∑L(fθ′(G′ii),θ′=argθmin∑L(fθ(G（1）jj),yj)其中，y表示模型预测值或标签，fθ′表示攻击模型，当G=G时表示逃逸攻击，当G=G′时表示投毒攻击。给定扰动预算Δ，使用函数D衡量扰动图和原始图之间的差异，对于图中扰动量ε通过以下约束保证扰动难以（

162021，57（7）ComputerEngineeringandApplications计算机工程与应用被察觉：D(G′,G)=A′-A0+X′-X0=ε≤Δva表示目标节点，G′t表示t时刻的扰动图。（2）奖励函数r：由于攻击者的目的是使目标节点va被错误分类，因此在修改图的过程中奖励函数值始终为0，即r(st,at)=0,∀t=1,2,…,m′-1，仅在终止时才获得奖励：ì1,fθ(G′,va)≠yr((G′,va))=í（3）-1,f(G,v)=y′θaî终止状态：当修改边的数量达到m′时，算法终止。3攻击算法为了便于后续介绍，本文将图对抗攻击算法分为拓扑攻击、特征攻击以及兼具拓扑攻击和特征攻击方式的混合攻击三类进行介绍，表2对比了典型攻击算法。3.1拓扑攻击拓扑攻击也称为结构攻击，在实际的攻击操作中，与RL-S2V[16]类似，ReWatt[18]同样将攻击过程建模为MDP，但ReWatt采用重连边作为动作at，具体而言，给定节点三元组(v0,v1,v2)，删除v0和v1之间边的同时添加连接v0和v2的新边，保证图中节点和边的总数不发生改变，此外，ReWatt使用不同的奖励函数：ì1,fθ(st)≠fθ(s1)r(st,at)=íînr,fθ(st)=fθ(s1)nr=-1=-1Kpm攻击者可以通过在图中添加、删除节点间的边以达到降低模型性能的目的。RL-S2V[16]严格限制了攻击者对目标模型的了解，在此种黑盒攻击设定下攻击者不仅不了解模型，同时还假设攻击者无法访问训练数据的标签信息，仅能依靠被攻击模型的输出作为反馈来修改图结构。基于上述假设，RL-S2V将Q-learning[17]引入攻击模型中，把攻击过程建模为马尔可夫决策过程（MarkovDecisionProcess，MDP）。动作at：在图中添加或删除边，同时采用分层操作降低执行此动作的时间复杂度。状态st：使用元组(G′t,va)表示t时刻的状态，其中表2模型GF-Attack[28]RL-S2V[16]ADW2、ADW3[27]（4）（5）其中，K表示预定义的重连边的操作次数，通过修改百分比p∈(0,1)可以灵活改变攻击预算，与RL-S2V仅在MDP终止时获得奖励不同，ReWatt在攻击成功时奖励正数得分，而在每次采取动作时得到负数奖励，算法在典型攻击算法比较优点缺点需要访问模型的图滤波器生成的扰动图的转移能力较弱需要完全了解目标模型及训练数据集，访问受限时攻击性能下降元梯度的计算和存储都比较昂贵计算量较大；攻击的转移能力较差算法具有较大的计算量需要大量计算资源用于求解梯度迭代计算梯度信息导致大量计算；易陷入局部最优解时间复杂度较高；未考虑非重叠社区对于计算资源和内存资源的需求较高生成的扰动图容易被防御生成的扰动样本性能和代理模型有关；需要访问训练数据集IG-FGSM攻击性能较差；IG-JSMA需要计算大量梯度信息难以同时满足不可察觉性和高攻击能力；Greedy-GAN训练复杂算法较复杂，难以扩展到复杂图数据上针对安卓恶意软件检测系统，难以扩展至其他任务攻击方法修改目标模型图滤波器基于强化学习增加或删除边利用特征值扰动理论和随机游走修改边基于元学习将输入图结构作为超参数进行训练基于强化学习进行重连边通过删除有限边最大限度减少目标链路的相似度基于投影梯度下降算法修改图结构基于GCN梯度生成对抗样本基于遗传算法进行重连边利用图自编码器的梯度信息进行迭代梯度攻击基于GCN梯度添加或删除边基于GCN梯度和贪婪策略迭代生成对抗样本生成的对抗样本可用于攻击其他模型；攻击扰动量很小；扰动的计算效率较高仅需访问模型输出，实用性较高计算效率高；生成对抗样本可用于攻击节点分类、链路预测等多种下游任务较小扰动即可使模型性能大幅下降；具有可转移性不会影响图中边的数量，扰动更加难以察觉算法的效果优于CTR和OTC；严格保证扰动的不可察觉性攻击可以在不同节点嵌入模型中转移只需进行少量的重连边就可以进行高效的攻击；攻击具有可转移性通过少量的重连边就可以绕开社团探测算法；生成的对抗样本具有较强的攻击性能生成扰动不易被察觉；具有很强的可转移性扰动少量的边即可导致模型性能显著下降攻击具有很强的转移能力，可以显著降低模型性能可进行增量计算；IG-JSMA攻击性能优于Nettack攻击可以扩展到大规模图上；Greedy-GAN可以生成具有较高真实度的虚节点干净图与扰动图间具有相似的图属性可用于异构图攻击；攻击对真实系统能够造成威胁Metattack[32]ReWatt[18]Greedy-Katz，LocalACT[36]Opt-attack[24]FGA[22]Q-Attack[19]IGA[23]PGD，min-max[25]Nettack[12]IG-FGSM，IG-JSMA[45]基于积分梯度修改边或特征在图中插入恶意构造的伪节点基于强化学习在图中注入伪节点针对异构图数据的节点注入GreedyAttack，Greedy-GAN[43]NIPA[46]HG-Attack[50]

翟正利，等：图对抗攻击研究综述重连边次数达到K次或成功修改了图分类模型的输出标签时终止。Q-Attack[19]是基于遗传算法攻击社团探测模型的方法，采用与ReWatt相同的重连边[18]攻击策略作为基因编码，攻击的次数作为每个染体的长度，并且基于模块度Q作为适应度函数fit的设计基础：fit=e-Q（6）Q=deg(41msT(Avij-i)⋅deg(vj)2m)s（7）其中，s是列向量，每个元素si表示节点vi的社团标签，式表明模块度越低的个体其适应度越高。EPA[20]为了节省存储空间将重连边的边编号作为基因编码，染体在交叉过程中的长度是可变的，同时在突变过程中结合图的拓扑特征进行搜索，以快速获得近似最优解，其适应度函数由衰减函数和攻击效果评估函数构成。同样基于遗传算法的EDA[21]用于攻击图嵌入模型，与Q-Attack[19]相同，将重连边作为基因，适应度函数为：fit=1-D(G,G′)|V|（8）其中，D(G,G′)用于衡量扰动图和原始图之间的欧式距离，EDA的目标是最大化嵌入空间中节点对间的欧式距离。给定图G，FGA[22]计算目标节点的损失函数值对每对节点的梯度信息，之后修改梯度绝对值最大的节点对间的边，当修改边的数量到达扰动预算时，将修改后的图作为对抗样本。IGA[23]利用图自动编码器的梯度信息，进行迭代梯度攻击以破坏链路预测模型，同时针对不同的实际环境可以对攻击模型进行不同限制。Sun等[24]将投影梯度下降（ProjectedGradientDescent，PGD）引入图对抗攻击中，对无监督节点嵌入算法进行投毒攻击，并在下游链路预测任务中证明了攻击的有效性。Xu等[25]将PGD用于攻击节点分类模型，使用对称矩阵S={0,1}n×n来表征图中的边是否被修改，当且仅当Sij=Sji=1时才修改节点vi和vj之间的连接，因此可以通过搜索最佳扰动矩阵S得到对抗样本，并且针对投毒攻击和逃逸攻击，分别提出了PGD拓扑攻击和min-max拓扑攻击。虽然同样利用梯度信息进行攻击，但Chen等[26]认为多数直接利用模型梯度信息的攻击算法[12，22-23，25]易陷入局部最优解，因此结合动量法提出了MGA模型，使迭代过程更加稳定。不同于利用模型梯度信息设计的攻击算法，Bojchevski等[27]利用特征值扰动理论评估了基于随机游走的节点嵌入模型的脆弱性，通过在攻击预算内添加或删除边来降低节点嵌入的质量，针对下游节点分类和链路预测任务分别采用Aclass和Alink算法进行攻击；GF-Attack[28]使用图信号处理方法描述图嵌入，通过攻击模型的图滤波器修改边，同时利用特征矩阵获得对抗样本，并在下游2021，57（7）17的节点分类任务中较RL-S2V和Aclass具有更好的攻击性能；Wang等[29]从基于协作分类的图分类模型出发，提出了利用LinLBP生成对抗样本的攻击方法，并且实验证明了此攻击可以转移到基于图神经网络的图分类模型中。受图像上通用攻击[30]的启发，Zang等[31]认为图中存在部分“锚节点”，通过修改“锚节点”与目标节点的边使目标节点被错误分类，而且这些“锚节点”可以通用于攻击任何目标节点。与传统深度算法将元学习用于模型超参数优化相反，Zügner等[32]提出的Metattack将输入图数据作为超参数进行优化以进行黑盒设定下的投毒攻击：∇mateG=∇GLatk(fθ*(G))（9）元梯度∇mateG表示微小扰动下模型训练后的损失Latk的变化。θ*是通过T次迭代获得的模型参数：θt+1=θt-α∇θtLtrain(fθt(G))（10）其中α表示学习率，Ltrain表示训练损失。根据训练过程将元梯度展开可以得到：∇mateG=∇fLatk(fθ*(G))∙[∇Gfθ*(G)+∇θ*fθ*(G)⋅∇Gθ*]（11）为了缓解元梯度计算和存储的高代价，可以利用一阶近似和启发式算法简化元梯度的计算，得到元梯度∇mateG后，采用贪婪策略选择添加或移除边。在针对社交网络的攻击中，CD-Attack[33]首先利用图神经网络和归一化割设计社团探测代理模型，然后设计满足离散约束的图生成网络，最后利用策略梯度法获得对抗样本，CD-Attack还要求同时从局部相似度和全局相似度来保证扰动的不可察觉性。为了在社交网络中逃避基于相似度的链路预测算法的检测，DICE[34]同时删除和添加节点间的连接，而基于启发式的OTC和CTR算法则分别通过添加连接和删除连接来隐藏社交关系[35]，并通过实验证明了：删除与现有朋友的连接CTR）相比添加与新朋友的连接（OTC）能提供更好的掩饰性，Zhou等[36]通过删除边来最小化目标链接的相似性，达到隐藏链接的目的。TGA[37]是针对动态图链路预测的第一个攻击算法，其利用不同时刻的深度动态图嵌入的梯度信息进行重连边，使目标链路无法被预测。与TGA不同，Fan等[38]提出的动态图链路预测攻击属于黑盒设定下的逃逸攻击，采用基于强化学习的算法，其基本策略和ReWatt[18]类似，而奖励函数用式表示：rsìht-ht+1,errt+1t(t,at)=í>errtî-n′,errt+1≤errt（12）其中，函数h衡量扰动下的链路预测性能，errt表示时刻t错误预测的链路数，n′表示动态图序列中扰动图的数量。当模型在状态st+1的性能比状态st差时，获得正奖励。（

182021，57（7）ComputerEngineeringandApplications计算机工程与应用3.2特征攻击相较于拓扑攻击和混合攻击，仅通过修改图中节点的特征进行特征攻击的模型较少，但是特征攻击并不会改变图中节点数，也并不修改节点间的边，因此可以保持图中重要的拓扑特征。基于标签传播算法的思想，Liu等[39]提出针对基于图的半监督学习模型的投毒攻击的一般框架，并且基于梯度下降设计不同的算法用于回归和分类任务。文献[40]考虑了图卷积神经网络（GraphConvolu-tionalNetwork，GCN）聚合邻居信息的特性，通过扰动目标节点vi的k(k≥2)阶邻居进行攻击，定义投毒效率来查扰动节点：ϕkvi(vj)=1(η)|ϕ(k-1)(η)（13）η∈anc∑(vvii,vj)|N1其中，anc(vi,vj)表示以目标节点vi为根节点的邻居树中vj的祖先节点集，ϕ1vi(η)=1。在候选节点集中选择投毒效率最高的节点构造特征扰动。3.3混合攻击混合攻击可以综合利用拓扑攻击与特征攻击的攻击操作，更进一步攻击者可以伪造新节点注入图中，并添加伪造节点与原始图中节点之间的边。针对图数据的早期攻击[41]通过在原始图中注入节点和边攻击图聚类算法。Nettack[12]是第一个在属性图上进行对抗攻击的黑盒攻击模型，在节点分类任务中，给定目标节点vi，Nettack的目标是通过代理模型，修改图G寻对抗样本G′，使得ymaxlnZ*v*≠yolda,y-lnZva,yold（14）其中，Z表示模型输出的分类概率，yold和y分别是基于图G和对抗样本G′得到的va的类别，算法的目标是将va的预测类别yold变为y，并使得两者的对数概率距离最大化。为了保证扰动的不可察觉性，Nettack除了保证攻击满足等式外，同时需要保留图的数据特征。Entezari等[42]进一步研究了Nettack[12]扰动，表明其攻击修改了图的高阶谱，并提出了构建低秩矩阵扰动原始图的LowBlow攻击方法。Wang等[43]利用贪婪算法在图中注入虚假节点以降低GCN性能，同时为了保证虚假节点的特征足够逼真，利用生成对抗网络（GenerativeAdversarialNetwork，GAN）思想提出了Greedy-GAN算法，添加鉴别器使生成节点特征与原始图中节点特征相似。基于梯度的攻击在图像对抗攻击中应用广泛，典型算法包括利用损失函数梯度的FGSM（FastGradientSignMethod）[44]和模型输出梯度的JSMA（Jacobian-basedSaliencyMapApproach）[15]，Wu等[45]在此基础上利用积分梯度（IntegratedGradients，IG）解决了图神经网络的离散输入问题，通过式计算IG得分（以拓扑攻击为例，特征攻击可以通过简单修改获得），对于定向攻击，优化目标是最大化F的值，而非定向攻击则修改具有高IG得分的节点特征或边。ìïk×(A-0))ï(Am∂F(ïij-0)×∑mij∂Aij×m1,IG(F(G))[i,j]≈ïífordeletingk=1edgesïïm∂F(k×(1-A（15）ij))ï(1-Aij)×∑m×1,ïk=1∂Aijmîfordeletingedges当F=L时，称攻击为IG-FGSM，当F=fθ时，称攻击为IG-JSMA。NIPA[46]是另一种基于强化学习的攻击模型，但与RL-S2V[16]修改原始图中节点之间的边作为动作at构建MDP的方式不同，NIPA将at定义为虚假节点注入或在虚假节点与原始图中节点之间添加边，奖励函数设计为：rt(st,at)=ìí1,At+1>Atî-1,At+1≤At（16）其中At表示时刻t测试集中节点标签与模型预测标签不同的节点数占测试集中所有节点的比例。NIPA攻击方法得到的扰动图与原始图在包括基尼系数和分布熵在内的多种属性上都是相似的。GTA[47]是首个针对图神经网络的后门攻击模型，使所有含有触发器的输入被木马模型fθ′错误分类。GTA将攻击中的触发器gt定义为子图，并且针对不同图定制不同触发器。通过给定图G与触发器gt混合得到扰动样本G′，攻击的目标为：ìíh(fθ′(G′))=ytîh(fθ′(G))=h(fθo(G))（17）其中，fθo表示预训练的图神经网络，h表示微调后的分类器，将带有触发器的对抗样本错误分类到指定类别yt，同时确保原始图在原始模型和木马模型中具有相同的分类结果。Zhang等[48]对图数据上的后门攻击进行了更深入的研究，提出了用于描述后门攻击的具体参数，并使用随机子图作为触发器以逃避检测系统。针对图神经网络的不同实际应用，Zhang等[49]评估了知识图谱嵌入（KnowledgeGraphEmbedding，KGE）模型的脆弱性，通过添加或删除KGE训练集中特定的知识实体进行投毒攻击，从而改变目标事实的合理性；HG-Attack[50]是针对恶意软件检测系统的攻击算法，通过注入恶意应用程序，使恶意软件绕过检测系统被分类为正常应用程序；不同于构造虚假用户注入数据集攻击推荐系统[51]，CopyAttack[52]通过复制源推荐系统的用户资料，利用强化学习选择和修改用户资料，得到可用于注入目标推荐系统的用户资料；Fang等[51]证明了即使在

翟正利，等：图对抗攻击研究综述部署了检测虚假用户的推荐系统中，大部分虚假用户仍然能够绕过检测。4图对抗攻击面临的挑战虽然图对抗攻击已经取得诸多进展，但在以下方面仍存在挑战。（1）应用的多样性：随着对攻击算法原理与实现研究的深入，对于链路预测等任务的对抗攻击开始逐步推进，但是目前多数攻击模型都集中于节点分类任务，针对图分类、推荐系统、社团探测等任务的攻击模型仍缺乏全面深入的研究，表3总结了攻击算法在各种学习任务中的应用。表3攻击算法的应用任务相关论文RL-S2V[16]，Nettack[12]，Aclass[27]，Wu等[45]，Metat-节点分类tack[32]，LowBlow[42]，GreedyAttack[43]，GUA[31]，POISONPROBE[40]，NIPA[46]，Xu等[25]节点嵌入Bojchevski等[27]，Opt-attack[24]，GUA[31]链路预测Alink[27]，Waniek等[35]，Zhou等[36]，Zhang等[49]，IGA[23]，TGA[37]，Fan等[38]社团探测CD-ATTACK[33]，Q-Attack[19]，DICE[34]，EPA[20]推荐系统CopyAttack[52]，Fang等[51]图嵌入GF-Attack[28]，FGA[22]，GTA[47]，MGA[26]，EDA[21]图分类RL-S2V[16]，Wang等[29]，ReWatt[18]，Zhang等[48]，Chen等[41]恶意软件检测HG-Attack[50]（2）攻击的可扩展性：图对抗攻击领域的可扩展性是指算法在不同规模和不同类型的图上的适用性，具有高扩展性的算法通过较少改动甚至无需改动就可以应用于大规模或其他不同类型的图，时间复杂度是衡量攻击算法可扩展性的重要方面，表4展示了典型算法的时间复杂度，部分文献设计了针对大规模图的攻击[29，43]；针对动态图的攻击上也出现了行之有效的算法[37-38]，但目前多数攻击算法都是针对静态图进行设计的。将攻击扩展到大规模图，动态图和异构图是仍是具有挑战性的任务。表4典型攻击算法的时间复杂度模型时间复杂度说明RL-S2V[16](O((n+m)Nettack[12]OΔ|∙Va|∙n|N2(vi)|+d)A)DW[27]2、ADW3O(mn+cnlogn)Va表示被攻击节点Metattack[32]O(n2)集，vi,vj∈Va，c表Greedy-Katz，LocalACT[36]O(|N1(vi)⋂N1(vj)|)示候选采样的边的数量GreedyAttack，Greedy-GAN[43]O(n|Va|+|V2a|)（3）攻击的可转移性：可扩展性主要针对数据集的规模和类型，而可转移性[12，19-24]是指针对一种模型设计2021，57（7）19的对抗样本也可用于攻击其他模型，可转移性是多数黑盒算法设计的依据，利用可转移性设计代理模型，得到的对抗样本使其他模型性能遭到破坏，但是训练代理模型要求拥有被攻击模型的训练集，如何在少样本甚至零样本情况下获得对抗样本是一个重要的研究方向。（4）攻击的通用性：指将针对一个目标上进行的扰动操作，应用于其他目标也具有相同或类似的攻击效果，图像领域的通用攻击已经取得了重要进展[30]，而对图数据通用性攻击的研究才刚刚起步[31]。能否对所有攻击目标设计通用的扰动操作、降低扰动设计的代价，是亟待研究的问题。（5）攻击的可行性：在现实系统中，攻击模型往往面临着更多复杂的限制，而攻击的可行性取决于攻击模型架构设置的合理性，主要包括：①攻击算法假定的对被攻击模型及数据集的了解；②攻击在真实环境中是否可行。多数黑盒算法[12，32-33，46]假定攻击者可以利用原始图数据集训练代理模型生成扰动图，实际生产环境中，图神经网络的训练数据集并不会公开；即使在严格受限的黑盒攻击设定下（攻击者仅能获取被攻击模型的输出）[16，27-28]，频繁查询模型的输出结果，也将引起防御机制的察觉，对攻击算法的限制条件越多，其相应的危害也越大；另一方面，白盒攻击[37，45]的设定虽然在真实环境中并不合理，但是分析目标模型在最坏情况下的脆弱性，有助于提到对图神经网络的理解。同时在真实系统中，并不能保证扰动的有效性和隐蔽性，例如在社交网络中，并不能轻易获得与陌生人间连接的许可[35]；在推荐系统中，插入过多虚假节点可能会因破坏原始图属性[52]引起检测系统的警觉。（6）扰动的度量标准：在图像数据中可以通过人眼观察定性扰动是否可察觉、通过距离函数定量衡量扰动量大小，但在图数据中由于节点间的关联性，难以确定扰动是否足够隐蔽，同时实际的扰动操作具有不同的难度，例如在图中修改现有节点与注入虚假节点难度差距较大。现有算法针对不同场景提出不同的度量标准，缺乏对扰动隐蔽性和扰动难度的系统研究。5结束语尽管图神经网络在多种任务中都有着出的表现，但与其他深度学习模型一样易受到微小扰动的损害，导致模型性能的严重下降，引发安全和隐私问题。本文通过对图对抗攻击算法进行全面、系统的归类分析，总结不同算法的实现、应用及其优缺点，并分析了当前图对抗攻击领域面临的挑战，未来的图对抗攻击研究包含以下方面：（1）在更广泛的学习任务和图数据类型中研究图对抗攻击的有效性和适用性，设计可以用于多种任务和图

202021，57（7）ComputerEngineeringandApplications计算机工程与应用数据类型的攻击模型，产生与特定任务无关的对抗样本以进行更广泛的攻击；分析包括异构图、动态图等在内的复杂图数据类型的特征，并设计行之有效的攻击算法。（2）提高算法的效率，目前多数攻击模型产生对抗样本过程中，需要存储大量梯度信息和图数据的中间状态，因此会耗费大量计算和存储资源，但现实世界的图数据往往是大规模和动态的，因此设计算法必须考虑计算复杂度。（3）提高模型的实用性，算法的实用性不仅要求算法的有效性和高效性，同时针对实际攻击而言，攻击者往往受到更多的限制，包括模型与数据集的限制，因此在复杂受限的现实环境中进行攻击需要更深入的研究，同时攻击算法应当在更广泛的数据集上进行验证。（4）构建统一的图对抗攻击算法的综合评价体系，纵观现有图对抗攻击，对于扰动量的度量以及模型效果的评价存在不同标准，需要更加通用的指标来度量不可察觉性，完善的指标能够更加全面地衡量算法的优劣，提高扰动样本的可解释性。参考文献：[1]HEK，ZHANGX，RENS，siduallearningforimagerecognition[C]//ProceedingsoftheIEEECon-ferenceonComputerVisionandPatternRecognition，2016：770-778.[2]GARCIA-GARCIAA，ORTS-ESCOLANOS，OPREAS，yondeeplearningtechniquesforimageandvideosemanticsegmentation[J].AppliedSoftCom-puting，2018，70：41-65.[3]涂文博，袁贞明，俞凯.无池化层卷积神经网络的中文分词方法[J].计算机工程与应用，2020，56（2）：120-126.[4]ZHANGS，YAOL，SUNA，arningbasedrecommendersystem：Asurveyandnewperspectives[J].ACMComputingSurveys（CSUR），2019，52（1）：1-38.[5]WUZH，PANS，CHENFW，ehensivesurveyongraphneuralnetworks[J].IEEETransactionsonNeuralNetworksandLearningSystems，2021，32（1）：4-24.[6]白铂，刘玉婷，马驰骋，等.图神经网络[J].中国科学（数学），2020，50（3）：367-384.[7]SCARSELLIF，GORIM，TSOIAC，phneuralnetworkmodel[J].IEEETransactionsonNeuralNetworks，2008，20（1）：61-80.[8]叶启松，戴旭初.攻击分类器的对抗样本生成技术的现状分析[J].计算机工程与应用，2020，56（5）：34-42.[9]XUH，MAY，LIUH，arialattacksanddefensesinimages，graphsandtext：Areview[J].Interna-tionalJournalofAutomationandComputing，2020，17（2）：151-178.[10]AKHTARN，ofadversarialattacksondeeplearningincomputervision：Asurvey[J].IEEEAccess，2018，6：14410-14430.[11]仝鑫，王罗娜，王润正，等.面向中文文本分类的词级对抗样本生成方法[J].信息网络安全，2020，20（9）：12-16.[12]ZÜGNERD，AKBARNEJADA，GÜarialattacksonneuralnetworksforgraphdata[C]//Proceedingsofthe24thACMSIGKDDInternationalConferenceonKnowledgeDiscovery&DataMining，2018：2847-2856.[13]GUOH，TANGR，YEY，-basedpushserviceplatform[C]//ProceedingsofInternationalConferenceonDatabaseSystemsforAdvancedApplications，2017：636-648.[14]JINW，LIY，XUH，arialattacksanddefensesongraphs：Areviewandempiricalstudy[J].arXiv：2003.00653，2020.[15]PAPERNOTN，MCDANIELP，JHAS，itationsofdeeplearninginadversarialsettings[C]//Proceedingsof2016IEEEEuropeanSymposiumonSecurityandPrivacy（EuroS&P），2016：372-387.[16]DAIH，LIH，TIANT，arialattackongraphstructureddata[J].arXiv：1806.02371，2018.[17]ARULKUMARANK，DEISENROTHMP，BRUNDAGEM，inforcementlearning：Abriefsurvey[J].IEEESignalProcessingMagazine，2017，34（6）：26-38.[18]MAY，WANGS，DERRT，inggraphcon-volutionalnetworksviarewiring[J].arXiv：1906.03750，2019.[19]CHENJ，CHENL，CHENY，-basedQ-attackoncommunitydetection[J].IEEETransactionsonCom-putationalSocialSystems，2019，6（3）：491-503.[20]CHENJ，CHENY，CHENL，caleevolutionaryperturbationattackoncommunitydetection[J].arXiv：1910.09741，2019.[21]YUS，ZHENGJ，CHENJ，rvisedeuclideandistanceattackonnetworkembedding[C]//Proceedingsof2020IEEEFifthInternationalConferenceonDataScienceinCyberspace（DSC），2020：71-77.[22]CHENJ，WUY，XUX，adientattackonnetworkembedding[J].arXiv：1809.02797，2018.[23]CHENJ，SHIZ，WUY，edictionadversarialattack[J].arXiv：1810.01110，2018.[24]SUNM，TANGJ，LIH，isoningattackagainstunsupervisednodeembeddingmethods[J].arXiv：1810.12881，2018.[25]XUK，CHENH，LIUS，gyattackanddefenseforgraphneuralnetworks：Anoptimizationperspective[J].arXiv：1906.04214，2019.[26]CHENJ，CHENY，ZHENGH，：Momentum

翟正利，等：图对抗攻击研究综述gradientattackonnetwork[J].arXiv：2002.11320，2020.[27]BOJCHEVSKIA，GÜarialattacksonnodeembeddingsviagraphpoisoning[C]//ProceedingsofInternationalConferenceonMachineLearning，2019：695-704.[28]CHANGH，RONGY，XUT，ictedblack-boxadversarialframeworktowardsattackinggraphembed-dingmodels[C]//ProceedingsofInternationalConferenceonAAAI，2020：3389-3396.[29]WANGB，inggraph-basedclassificationviamanipulatingthegraphstructure[C]//Proceedingsofthe2019ACMSIGSACConferenceonComputerandCommunicationsSecurity，2019：2023-2040.[30]MOOSAVI-DEZFOOLISM，FAWZIA，FAWZIO，saladversarialperturbations[C]//ProceedingsoftheIEEEConferenceonComputerVisionandPatternRecognition，2017：1765-1773.[31]ZANGX，XIEY，CHENJ，niversaladver-sarialattacks：Afewbadactorsruingraphlearningmodels[J].arXiv：2002.04784，2020.[32]ZÜGNERD，GÜarialattacksongraphneuralnetworksviametalearning[J].arXiv：1902.08412，2019.[33]LIJ，ZHANGH，HANZ，arialattackoncommunitydetectionbyhidingindividuals[C]//ProceedingsoftheWebConference，2020：917-927.[34]WANIEKM，MICHALAKTP，WOOLDRIDGEMJ，individualsandcommunitiesinasocialnetwork[J].NatureHumanBehaviour，2018，2（2）：139-147.[35]WANIEKM，ZHOUK，VOROBEYCHIKY，toleranceoflinkpredictionalgorithms：Howtohideyourrelationsinasocialnetwork[J].arXiv：1809.00152，2018.[36]ZHOUK，MICHALAKTP，RAHWANT，ingsimilarity-basedlinkpredictioninsocialnetworks[J].arXiv：1809.08368，2018.[37]CHENJ，ZHANGJ，CHENZ，-awaregradientattackondynamicnetworklinkprediction[J].arXiv：1911.10561，2019.[38]FANH，WANGB，ZHOUP，rcementlearning-basedblack-boxevasionattackstolinkpredictionindynamicgraphs[J].arXiv：2009.00163，2020.[39]LIUX，SIS，ZHUX，edframeworkfordatapoisoningattacktograph-basedsemi-supervisedlearning[J].arXiv：1910.14147，2019.2021，57（7）21[40]ctadversarialattacksviapoisoningneighborsforgraphconvolutionalnetworks[C]//Pro-ceedingsof2019IEEEInternationalConferenceonBigData（BigData），2019：1395-1400.[41]CHENY，NADJIY，KOUNTOURASA，calattacksagainstgraph-basedclustering[C]//Proceedingsofthe2017ACMSIGSACConferenceonComputerandCommunicationsSecurity，2017：1125-1142.[42]ENTEZARIN，AL-SAYOURISA，DARVISHZADEHA，needislow（Rank）defendingagainstadversarialattacksongraphs[C]//Proceedingsofthe13thInternationalConferenceonWebSearchandDataMining，2020：169-177.[43]WANGX，EATONJ，HSIEHCJ，graphconvolutionalnetworksbyaddingfakenodes[J].arXiv：1810.10751，2018.[44]GOODFELLOWIJ，SHLENSJ，ningandharnessingadversarialexamples[J].arXiv：1412.6572，2014.[45]WUH，WANGC，TYSHETSKIYY，arialexamplesongraphdata：Deepinsightsintoattackanddefense[J].arXiv：1903.01610，2019.[46]SUNY，WANGS，TANGX，jectionattacksongraphsviareinforcementlearning[J].arXiv：1909.06543，2019.[47]XIZ，PANGR，JIS，ackdoor[J].arXiv：2006.11890，2020.[48]ZHANGZ，JIAJ，WANGB，orattackstographneuralnetworks[J].arXiv：2006.11165，2020.[49]ZHANGH，ZHENGT，GAOJ，isoningattackagainstknowledgegraphembedding[J].arXiv：1904.12052，2019.[50]HOUS，FANY，ZHANGY，etal.αCyber：EnhancingrobustnessofAndroidmalwaredetectionsystemagainstadversarialattacksonheterogeneousgraphbasedmodel[C]//Proceedingsofthe28thACMInternationalConferenceonInformationandKnowledgeManagement，2019：609-618.[51]FANGM，YANGG，GONGNZ，ingattackstograph-basedrecommendersystems[C]//Proceedingsofthe34thAnnualComputerSecurityApplicationsCon-ference，2018：381-392.[52]FANW，DERRT，ZHAOX，ingblack-boxrecommendationsviacopyingcross-domainuserprofiles[J].arXiv：2005.08147，2020.