基于梯度选择的图卷积网络针对性通用对抗攻击①

曹海芳

(天津大学 数学学院,天津 300350)

图结构数据已广泛应用于许多现实世界的应用程序中,例如社交网络(Facebook和Twitter),生物网络(蛋白质或基因相互作用) 以及属性图(PubMed和Arxiv)等[1–3].节点分类任务是图结构数据上最重要的任务之一,即给定一个节点子集及其标签,预测其余节点的标签.对于节点分类任务,基于图的深度学习模型——图神经网络已实现了最先进的性能[4],而图卷积网络(GCN)作为一种特殊的图神经网络,在此任务上取得了更好的结果.

目前的研究更多的是将重点放在如何提高GCN的性能上,却很少有人关注GCN 模型的鲁棒性.但是,研究表明,GCN是极易受到对抗攻击的.例如,只须对图数据的拓扑结构或者节点的特征进行微小的修改就能使GCN 得到错误的分类结果[5].目前的攻击方法中,绝大多数是通过修改图数据的拓扑结构和节点属性来进行攻击的,然而,这样的攻击在现实场景中是不适用的.例如,在社交网络应用程序中,攻击者必须登录用户的帐户才能更改现有的连接和功能,而获得登录访问权限几乎是不可能的.相比之下,在实践中添加与用户相对应的伪节点(fake node)会容易得多.

TUA 就是一种通过添加伪节点进行攻击的针对性通用攻击方法.在针对GCN的所有攻击方法中,通用攻击方法是一种特殊的攻击方法,此方法要求GCN 将所有的受害节点都错误分类,而不是某个单独的节点[6–8].针对性通用攻击则要求GCN 将所有受害节点都错误地分到某一个指定的类别[9].本文则是基于TUA 算法,通过引入梯度选择的方法,使得本文方法在所有类别的实验中都取得了与TUA 方法相当甚至优于TUA 方法的结果,平均ASR 相对TUA 得到了1.7%的提升.

1 相关知识介绍

1.1 图卷积网络 (GCN)[4,10]

给定属性图G(A,X),其中A∈{0,1}N×N为邻接矩阵,X∈{0,1}N×d为特征矩阵,即图G有N个节点,且每个节点伴随一个d维的特征.令V={v1,v2,···,vN}为节点集,C={c1,c2,···ck}为类别集.节点分类任务的目标就是通过在含有节点标签的训练集上学习从而成功预测测试集节点的标签.GCN 首先通过聚合邻居节点的信息来得到节点的嵌入表示(第l层如下):

1.2 图对抗攻击

在过去的几年中,Zungner 等[6]和Dai 等[5]首先发现了GCN 容易受到对抗性攻击的特性.而根据攻击的不同阶段,GCN中的对抗攻击分为两种类型:投毒攻击(训练期间的攻击)和逃避攻击(测试期间的攻击).通常,投毒攻击的重点是通过干扰训练数据来降低GCN 模型的性能,而逃避攻击则通过修改属性或拓扑结构来构造对抗性样本,从而使GCN 模型的性能降低.另外,根据攻击的不同目的,对图结构化数据的对抗攻击可分为节点分类攻击,链接预测攻击和图分类攻击.节点分类攻击的目的是使某些节点被GCN 误分类.链接预测攻击的重点是减少节点之间的关联,从而导致GCN 提供错误的预测结果.图分类攻击则旨在增强指定图与目标分类之间的相关性,以使GCN 无法正确分类给定图样本.本文提出的GTUA 可以归为逃避攻击和节点分类攻击.

在对图结构数据的所有对抗攻击中,伪节点攻击是一种常见的攻击方法,通过将一组伪节点注入到图中来实现,从而可以避免对原始图进行拓扑或属性修改.例如,GreedyAttack和GreedyGAN 通过将伪造的节点直接添加到受害节点来进行目标节点攻击[11].Wang 等[12]引入近似快速梯度符号法,该方法在受害节点和其他节点之间添加了一个恶性节点,从而导致受害节点被错误分类.但是,大多数现有的伪节点攻击并非旨在进行普遍的对抗攻击.而在本文提出的GTUA中,伪节点充当受害节点的2 跳邻居.由于GCN的攻击过程,伪节点特征的影响通过攻击节点传递到受害节点,从而进行针对性通用对抗攻击.

2 基于梯度选择的图卷积网络针对性通用对抗攻击

基于梯度选择的图卷积网络针对性通用对抗攻击(GTUA)的目标是使得每一个与攻击节点(从标签为目标类别的节点集中随机选择)连接的受害节点都得到与攻击节点相同的标签(如图1所示).主要由3 个步骤完成:添加伴随0 特征的伪节点;计算目标函数关于伪节点特征矩阵的梯度矩阵;按梯度矩阵元素大小进行梯度选择并确定扰动特征.下面分别详细介绍每一个步骤.

图1 攻击前后的受害节点分类结果

2.1 添加伴随0 特征的伪节点

在添加伪节点之前,先简单介绍几步预处理过程:对于给定的图G(A,X),首先选定一个类别co作为目标类别,随后在标签为co的节点集中随机选择NA个节点作为攻击节点VA={v1A,v1A,···,vNAA},同时为了简便起见,规定为每个攻击节点连接相同数量NF个伪节点.即,给定图G(A,X),目标类别co,攻击节点VA,每个攻击节点的伪节点数目NF,通过给每个攻击节点连接特

G′=(A′,X′)征为0的伪节点得到新图,其中,

其中,E∈{0,1}N×(NA·NF),P∈{0,1}(NA·NF)×(NA·NF),XF∈{0,1}(NA·NF)×d,且初始化为全0,本文的目的就是通过给伪节点添加某些特征,也就是XF的某些元素由0 改为1,从而使得下面的目标函数取得最大值.

2.2 计算目标函数关于伪节点特征矩阵的梯度矩阵

在此首先明确本文的目的是,对于给定的图G(A,X),目标类别co,攻击节点VA,希望每一个标签不是co的节点,当其与VA连接时,能够使得GCN为其得到co的标签,这也就是针对性通用攻击的含义.由此含义,首先给出一个随机选定的辅助节点集来帮助建立目标函数,其中NT表示辅助节点的数量,要求VT中的每一个节点都不属于标签co,因此有下面的目标函数:

其中,‖E‖0表示伪节点与攻击节点之间的连边的数量,‖XF‖0表示给伪节点添加的特征的数量,二者都受到参数 Δ的限制,因为扰动必须是微小的.其中,

式(5)是关于每一个辅助节点的目标函数部分,v∈VT,A′(v,A)表示辅助节点v与攻击节点VA连接之后的新的邻接矩阵,[f(·)]v,co和[f(·)]v,cv分别表示GCN 将节点v判定为目标类别和其当前类别的输出概率.而制定此目标函数的依据是:如果本文的攻击或者说扰动能够使得GCN 将这些非co的辅助节点在连接到VA后被分类到co,那么对于所有的非co的节点,当其与VA连接后,就会有很大的概率被分类为co,并且如果考虑一种极端情况:将所有非co节点作为辅助节点,那么就能更好地理解此目标函数.

前面确定了目标函数,那么如何计算扰动？在这里首先介绍基于梯度的方法.因为只考虑对XF进行扰动,因此只需要先计算目标函数关于XF的梯度:

2.3 按梯度矩阵元素大小进行梯度选择并确定扰动特征

以往的基于梯度的方法基本都是采用一种贪婪式的选择方法[13]:在每一次迭代中只改动一个元素,因此找到每一次迭代中的梯度矩阵中的最大元素作为修改的对象即可.TUA 也是采用这样一种方式,首先找到Grad中的最大元素Gradmax:

然后找到Gradmax在XF对应哪一个伪节点的哪一个特征,再找到它在X′中的对应位置,将该位置的元素由0 置为1,这样就完成了一次迭代,直到到达一定的阈值就结束扰动.需要提到的一点是:如果某一次迭代时最大梯度对应的位置已经是1,那么就寻找第二大的梯度位置,依次下去.

本文提出的GTUA 也是采用一种基于梯度的贪婪式方法,但是在这个过程中加上一个梯度选择的过程.具体做法就是在得到Grad之后,选出其中从大到小前k个元素:

然后分别计算将其在X′中对应位置的特征值由0 置为1 后的损失函数值:

其中,X1′,X2′,···,Xk′分别是对Grad1,Grad2,···,Gradk位置进行扰动后的新的特征矩阵.最后再选择其中得到最大损失函数值的特征修改作为这一次迭代的扰动:

加入这样一个梯度选择的过程,是出于以下思考:因为考虑A和X都是取值为0 或1的离散数据类型,因此在选择Grad中最大元素Gradmax对应的位置并由0 置为1的时候相当于是选择了长度1的步长,并且每一次迭代都是固定步长1.因此,就很可能出现一种情况,Grad中第二大元素Gradsec对应的位置由0 置为1 会得到更大的损失函数,如图2所示.

图2 不同梯度下loss 与步长的关系

3 实验分析

3.1 数据集和评价指标

本文在3 个常用的属性图数据集上进行实验:Cora (2 708 节点,5 429 边,1 433 特征,7 类别),Citeseer (3 312 节点,4 732 边,3 703 特征,6 类别)和PubMed (19 717 节点,44 338 边,500 特征,3 类别)[14–16].此外,根据Kipf&Welling的设置,在3 个相应的数据集上训练GCN 模型.最后用平均攻击成功率(ASR)作为模型性能的评价标准,ASR 越高,表明模型的攻击效果越好.

3.2 实验设置

首先按照TUA的方法加快微扰计算.因为大多数基于梯度的攻击都存在时间和内存成本高的问题,为了解决这个问题,Li 等[16]提出了一种有效加速攻击的框架,该攻击框架攻击由目标节点的k跳邻居组成的较小子图(k取决于GCN 层数),从而可以避免不必要的图信息存储和计算[17].因为本文是基于Kipf&Welling的设置来训练GCN,也就是一个2 层的GCN,因此只需要关注以目标节点为中心,以其一阶邻居和二阶邻居组成的子图即可.根据TUA的实验发现,当NF,NT固定时,随着NA的取值大于3 之后,ASR 几乎不再随着NA的增大而增大;同样的,固定NA,NT的取值时,当NF大于2 之后,ASR 也不再随NF的增大而增大;固定NA,NF时,当NT达到20 后,随着NT的增大,ASR几乎不再增大.但是,无论其中哪一个参数增大,对计算与存储的消耗都会成倍的增加.同时,对GTUA 进行了相关参数的实验,发现与TUA 有着相似的规律.因此在后续的实验中,规定参数设置NA=3,NF=2,NT=20.

3.3 实验结果与分析

本文进行两组实验,第一组实验用来查看在梯度选择过程中选择不同数量的梯度值NG对ASR 带来的影响,这里本文考虑NG∈{1,2,3,4,5,6},实验结果如图3所示.由图3可知,当加入了梯度选择的步骤之后,多数情况下ASR 值都是高于原始ASR 值的,且在这里的实验中发现NG取5的时候能在多数情况下得到最大的ASR 值,因此后面的实验就选定NG=5.

图3 选择不同数量的梯度对ASR的影响

第二组实验选择一个恰当的NG值,将本文方法GTUA 与TUA的ASR 值进行对比来验证GTUA的有效性.由实验一的结果,本文选择NG=5.结果如表1所示,可以很清楚地看到GTUA 在多数情况下优于TUA,在少量情况下取得与TUA 同样的结果,而取得相同结果的原因是每一次迭代都在梯度最大值处的扰动能得到最大的损失函数值,表1的最后一行也表明GTUA 与TUA 相比,平均ASR 提高了1.7%.

表1 GTUA 与TUA的性能比较(ASR)

表2展示了GTUA 与TUA的一次训练加测试的耗时对比,可以发现:因为GTUA 梯度选择的过程需要计算NG次损失函数,因此耗时要远大于TUA,且通过实验发现,随着图的节点与边的增多,两者之间的耗时差距越来越大,因此GTUA 比较适用于小图,而对于大图,时间成本略高.但是,由于GTUA 选择梯度的过程,从而导致它并不依赖于损失函数对特征矩阵的最大梯度,而TUA 则严重依赖于上述最大梯度,所以一些微小的改动并不会对GTUA 模型的结果造成影响,却会大大影响到TUA的结果,所以GTUA 相比TUA 有更好的鲁棒性.

表2 GTUA 与TUA 算法的效率比较(单位:s)

0.58 0.584 2 0.5125 0.53 3 1.0 1.0 4 0.895 0.915 5 0.555 0.5615 1 0.9855 0.9855 1 0.869 0.869 2 0.829 0.8335 0 PubMed平均值/ 0.8017 0.8193

4 结论与展望

本文提出了一种基于梯度的图卷积网络针对性通用对抗攻击GTUA,实验结果表明,与当前流行的方法TUA 相比,GTUA 最差能够达到与其一样的结果,但在多数情况下优于TUA,由此可以看出梯度选择的过程确实提升了扰动的质量.另外,本文也留下了一个后续的研究方向:对于离散数据类型上的基于梯度的方法,都可以尝试加入梯度选择的过程,由本文的结果可以大胆地预测,其在很大程度上可能会带来效果上的提升.