基于改进投影梯度下降算法的图卷积网络投毒攻击

金柯君，于洪涛，吴翼腾，李邵梅，操晓春

（1.中国人民解放军战略支援部队信息工程大学信息技术研究所，郑州 450000；2.中国科学院信息工程研究所信息安全国家重点实验室，北京 100093）

0 概述

图数据具有强大的表达能力，已经成为数据挖掘和机器学习领域的重要研究对象。图神经网络是专门针对图数据设计的端到端的深度学习模型［1］，它可以对语义属性数据和图数据统一表达建模，从图数据中提取特征以完成许多图分析任务，例如，节点分类［2-3］、链路预测［4-5］、社区检测［6-7］等。研究表明，图神经网络很容易受到对抗性攻击的安全威胁［8］，攻击者只要对图神经网络的结构或属性特征施加微小的扰动，则会导致图神经网络模型误判并影响其在具体任务中的表现。文献［9］研究图神经网络的对抗性攻击问题。之后，图神经网络的对抗性攻击方法的研究逐渐受到研究人员的关注［10-12］，成为人工智能安全领域的研究热点。

对抗性攻击根据攻击阶段不同分为污染测试数据的逃逸攻击和污染训练数据的投毒攻击［13-15］。投毒攻击分为数据投毒和对抗训练［16］两个阶段，为双层优化问题［17］。在实际应用中，图神经网络模型受到投毒攻击后，则更新训练参数，在参数更新过程中均会受到扰动的影响。模型的每一轮训练都在“中毒”数据的基础上，而攻击者的每一轮训练也是基于上一轮模型训练参数，这是一个循环嵌套的优化过程，即模型会对攻击者做出对抗性训练，以尽可能地降低受攻击后的性能损失。从攻击者角度出发，在优化攻击方法中考虑模型的对抗训练过程，以提高攻击效果。传统的连续优化方法难以直接应用于扰动的离散数据。文献［9］针对指定目标，采用贪婪算法对连边或节点特征逐个扰动以攻击单个节点。文献［18］针对非指定目标，提出基于投影梯度下降（Projection Gradient Descent，PGD）算法的投毒攻击Min-max。

本文提出基于改进投影梯度下降算法的投毒攻击方法PGattack。结合数据投毒与对抗训练两个阶段，在投毒攻击场景下，将模型训练参数看作可重新训练的变量，而不是固定的常量，在更新扰动矩阵时考虑模型的对抗训练过程，同时在模型对抗训练过程中研究扰动矩阵的作用。在此基础上，将图的连边情况松弛为一个取值［0，1］的连续变量，采用投影梯度下降算法对其进行扰动后再转化为二进制，并对离散图数据实施有效扰动。

1 基本概念与相关工作

1.1 图与图神经网络

图定义为G(V，E)，其中V={v1，v2，…，vN}表示节点 数|V|=N的节点集合，E={e1，e2，…，eM}表示连边集合，节点之间的相邻关系通过邻接矩阵A表示。在无权无向图中，A={0，1}N×N，AT=A。当节点vi和节点vj存在直接连边时，Ai，j≠0，否则Ai，j=0。在特征图中每个节点有n维的特征向量，节点特征可用矩阵X={0，1}N×n表示。节点分类任务［19］根据图G(V，E)和有标签节点的信息训练节点分类模型，并利用该模型正确预测无标签节点的类别。模型的表达如式（1）所示：

其中：A为邻接矩阵；X为输入特征向量；W为训练参数矩阵；为模型输出。

交叉熵损失函数如式（2）所示：

其中：Y为节点的标签。

图神经网络的学习过程如式（3）所示：

其中：W＊为图神经网络模型训练参数。

1.2 相关工作

1.2.1 投毒攻击

本文以图卷积网络（Graph Convolutional Network，GCN）作为研究对象，研究节点分类模型中非指定目标数据的投毒攻击。非指定目标攻击通过施加对抗性扰动以影响模型的整体性能，导致测试集的预测准确率整体下降［19］。投毒攻击是针对训练阶段的一种攻击方式。攻击者将投毒样本注入到训练数据集中，图卷积网络对“中毒”数据重新训练后，造成测试数据集的准确率降低［20］。文献［9，17］基于GCN 构建生成投毒攻击模型。根据上述定义，攻击方法可以统一概括为约束优化问题，如式（4）所示：

其中：为加入扰动后图卷积网络的 邻接矩阵；‖ · ‖0为矩阵中非0 元素的个数；δ为扰动预算，即允许扰动的最大数。投毒攻击以降低训练值的损失函数Latk为目标，当Latk越小时，攻击效果越好。本文令Latk=-Ltrain。投毒攻击允许对参数进行重新训练，从式（4）可以看出，投毒攻击属于双层优化问题。

1.2.2 基于投影梯度下降算法的投毒攻击方法

文献［18］提出利用投影梯度下降算法对图数据实施攻击的方法，该方法能有效处理离散图数据，并提出一阶攻击生成框架的2 种攻击场景：1）逃逸攻击，攻击一个预定义的图神经网络；2）投毒攻击，攻击一个可再训练的图神经网络。

针对第1 种攻击场景，文献［18］采用投影梯度下降算法对邻接矩阵A^ 进行扰动，攻击模型的表示如式（5）所示：

针对第2 种可再训练模型参数的场景，文献［18］对模型参数W进行优化。GCN 模型以扰动损失大的方向作为优化目标，GCN 攻击模型则以扰动损失减小的方向作为优化目标。攻击生成问题转变成最小最大化的问题，如式（6）所示：

外部最小化原始数据的损失利用投影梯度下降算法解决，内部最大化生成对抗数据的损失由普通梯度下降算法进行优化。

投影梯度下降算法可以对离散图数据进行有效的扰动，具有较优的攻击效果。但是在投毒攻击的场景下，式（6）将模型参数看成与扰动无关的变量，而非扰动的函数，忽略了两者之间的联系。

2 基于改进投影梯度下降算法的投毒攻击方法

2.1 攻击模型

本文基于改进投影梯度下降算法，使用一个两层GCN 构建投毒攻击模型，将特征矩阵看作常数，仅对图的邻接矩阵进行扰动，构建一个扰动矩阵S并对邻接矩阵A实施扰动。当Si，j=Sj，i=1 时，表示节点vi和节点vj之间的连边被扰动，即删除或添加；当Si，j=Sj，i=0 时，表示节点vi和节点vj之间的连边未 被扰动。扰动矩阵S对邻接矩阵A的扰动过程如式（7）所示：

其中：为扰动后的邻接矩阵；为A的补矩阵，补矩阵可以表示2 个节点之间是否存在边；当(-A)i，j=1 时，节点vi和节点vj之间不存在连边，攻击者可以添加连边；当(-A)i，j=-1 时，节点vi和节点vj之间存在连边，攻击者可以将其删除；1 为元素全1 的矩阵；◦为矩阵中逐元素乘积。δ为扰动预算，本文攻击方法寻求一个扰动矩阵S导致GCN 模型性能下降，在有限δ内对节点进行错误分类，对应式（2）中的损失函数最小。本文攻击方法可以概括为以下约束优化问题：

本文将GCN 模型训练参数W＊（S）看作扰动矩阵S的函数，而不是独立于扰动之外的变量，这是在投毒攻击场景下实施有效攻击的关键。在参数W＊（S）训练过程中需要考虑扰动矩阵S的影响。在本文每轮GCN 模型参数W＊（S）的训练过程中都基于扰动矩阵S，投毒攻击过程主要分为3 个步骤：1）构建扰动矩阵S，根据上一轮的GCN 模型参数W＊（S），采用投影梯度下降算法对S进行训练，并对邻接矩阵A实施扰动；2）模型根据扰动后的邻接矩阵A^(S)训练GCN 模型参数W＊（S）；3）重复前2 个步骤直至满足迭代总次数。

本文方法将数据投毒和对抗训练这2 个阶段相结合，在GCN 模型的对抗训练过程中考虑了扰动矩阵的影响，在更新扰动矩阵时考虑了GCN 模型对抗训练的影响。根据式（8），本文将投毒攻击分为数据投毒阶段和对抗训练阶段。

2.1.1 数据投毒阶段

在此阶段，攻击者对数据进行投毒并训练，以优化自身攻击方法。从式（8）可知，扰动矩阵S是一个对角线元素为0 的对称矩阵，S中含有N（N-1）/2 个独立的扰动变量。这些扰动变量之和应不超过扰动总数δ，S中的元素s∈｛0，1｝。在数据投毒阶段中，将S凸松弛成连续的S*，S*中的元素s*∈［0，1］。S*每个元素都是0～1 之间的连续值，是一个不断被优化的矩阵。S对邻接矩阵A的扰动数不能超过最大扰动数δ，不能简单地根据梯度下降算法对S*中的元素s*进行梯度更新，而需采用投影梯度下降算法。该算法是解决简单约束的连续优化算法，其基本思想是先使用梯度下降算法更新参数，再投影以保证更新的参数在可行域即约束条件之中。该过程如式（9）所示：

其中：t为梯度下降算法的迭代次数；ηt为第t轮更新S*的学习率；Wt-1(S)为第t-1 轮扰动后GCN 模型的训练参数。S*在更新过程中需要考虑到约束条件‖S*‖0≤2δ，在约束条件的范围内求解一个最接近S*的向量并记作Sp，如式（10）所示：

其中：Φ表示满足条件‖S*‖0≤2δ的约束空间。式（10）是S*(t)在约束空间Φ上的投影算子，将S*(t)投射到Φ连续空间中。此时，经过投影梯度下降算法得到的Sp并不能直接作为扰动矩阵使用，使用二项分布随机抽样［21］得到二值化的S，如式（11）所示：

再由式（7）得到扰动后的邻接矩阵。至此，本文完成了对数据的一轮“投毒”。

2.1.2 对抗训练阶段

在此阶段，GCN 模型对攻击者投毒后的数据做出反应并展开对抗训练。在攻击者对GCN 进行一轮扰动之后，GCN 模型根据扰动后的邻接矩阵^(S)对训练参数W（S）进行对抗训练，使得模型的损失函数Ltrain最小。GCN 模型参数W（S）采用梯度下降算法训练，过程如式（12）所示：

其中：α为GCN 模型训练参数W（S）更新的学习率。式（12）表示训练参数W（S）为扰动矩阵S的函数，通过对扰动矩阵S求梯度以最小化损失函数，如式（13）所示：

2.2 算法架构

根据上述理论，基于改进投影梯度下降算法的投毒攻击方法（PGattack）主要分为5 个步骤：1）根据上一轮的扰动矩阵S求得扰动后的邻接矩阵；2）图卷积网络进行正向训练，获得GCN 模型训练参数；3）求攻击梯度矩阵并根据投影梯度下降算法更新扰动矩阵Sp；4）将矩阵Sp二值化得到扰动矩阵S；5）根据扰动矩阵S对邻接矩阵进行扰动，重复步骤1～步骤4，直至满足迭代总次数iters 停止。

本文攻击算法的伪代码如算法1 所示。

算法1基于改进投影梯度下降的图卷积网络投毒攻击算法

本文提出的PGattack 攻击方法架构如图1 所示，该方法综合考虑投毒攻击的双层优化问题，实现数据投毒与GCN 模型对抗训练2 个过程的结合。

图1 PGattack 攻击方法架构Fig.1 Framework of PGattack attack method

3 实验验证

为分析本文攻击方法的主要影响因素并评估其攻击效果，本文实验采用型号为TITAN Xp 的GPU显卡，运行环境为ubuntu 16.04 系统，cuda10.0、Python3.7 以及Pytorch1.2.0。采用图深度学习常用的Citeseer［22］、Cora［22］、Cora_ml［23］和Polblogs［24］数据集，表1 所示为这些数据集的统计特征。数据集随机划分为标记节点和未标记节点，其中标记节点全部用于训练（10%）。在未标记的节点中，一部分用于测试（80%），另一部分用于验证（10%）。本文将数据集随机划分10 次，并记录10 次实验结果的平均值。

表1 数据集统计特征Table 1 Statistical characteristics of datasets

本文实验对GCN 模型的连边进行扰动，将扰动连边数与连边总数的比值称作扰动比例。GCN 模型在不同数据集上未受到干扰时的分类准确率对比如表2 所示。

表2 图卷积网络模型未受到干扰的分类准确率对比Table 2 Classification accuracy comparison of graph convolutional network model without disturbance

3.1 参数设置

本文攻击方法的性能与参数设置相关，攻击过程主要由数据投毒与对抗训练2 个阶段组成，训练轮数与学习率直接影响攻击效果。为尽可能提高攻击性能，本文在以上4 个数据集上进行实验，并根据实验数据设置相应参数。

3.1.1 训练轮数设置

在扰动比例为5%的情况下，本文方法的数据投毒阶段的训练轮数从10 次增至200 次，分别记录分类准确率。文献［18］将数据投毒阶段投影梯度下降的学习率设置为iters/，t为当前迭代轮数，iters 为训练总轮数，对抗训练的学习率设为0.01，对抗训练轮数设为100。在Citeseer、Cora、Cora_ml 和Polblogs数据集上，不同训练轮数下GCN 模型被PGattack 攻击后的分类准确率如表3 和图2 所示。

表3 在不同训练轮数下图卷积网络模型被PGattack攻击后的分类准确率Table 3 Classification accuracy of graph convolutional network model by PGattack attack in different training rounds

图2 图卷积网络模型被本文方法攻击后的分类准确率Fig.2 Classification accuracy of graph convolutional network model by the proposed method attack

从图2 可以看出，当训练轮数超过50 之后，GCN模型的分类准确率在一定范围内波动，呈现收敛趋势；同理，对GCN 模型对抗训练阶段的轮数进行对比实验，得出类似结果。后续实验将2 个阶段的训练轮数均设置为50。

3.1.2 对抗训练学习率设置

本文方法由数据投毒与对抗训练2 部分组成，本文实验选取扰动比例为5%，首先根据实验经验和粗粒度测试，将学习率从0.01 增至0.10，分别记录GCN 模型的分类准确率。在Citeseer、Cora、Cora_ml和Polblogs 数据集上，不同学习率下GCN 模型受PGattack 攻击后的分类准确率如表4 所示。综合表4数据，为取得更优的攻击性能，本文将学习率设为0.02。

表4 在不同学习率下图卷积网络模型被PGattack攻击后的分类准确率Table 4 Classification accuracy of graph convolutional network model by PGattack attack in different learning rates

3.2 攻击效果实验

本文根据训练模型对比分类准确率，以评估攻击效果，分类准确率下降幅度越大，说明GCN 模型的性能下降越明显，则攻击方法的效果越好。本文在Citeseer、Cora、Cora_ml 和Polblogs 数据 集上进行实验，训练轮数为50 轮，对抗训练学习率为0.02，将扰动比例从1%增至10%，分别记录GCN 模型在不同扰动比例下的分类准确率。随着扰动比例的增加，GCN 模型分类准确率背离初始准确率并逐步递减。在Citeseer、Cora、Cora_ml 和Polblogs 数据集上，在不同的扰动比例下本文攻击方法对GCN 模型进行扰动后的分类准确率如表5 和图3 所示。扰动比例越大（即扰动的连边数越多），GCN 模型的分类准确率越小，与预期相符，验证了攻击效果。

表5 在不同扰动比例下图卷积网络模型被PGattack攻击后的分类准确率Table 5 Classification accuracy of graph convolutional network model by PGattack attack in different disturbance ratios

图3 图卷积网络模型被本文方法攻击后的分类准确率Fig.3 Classification accuracy of graph convolutional network model by the proposed method attack

3.3 与其他攻击方法对比

本节将基于改进投影梯度下降算法的攻击方法PGattack 与基准方法的攻击性能与复杂度进行对比。基准方法包括以下4 个：1）随机攻击方法Random［19］，从训练集中随机选择增加连边或删除；2）删除同类连接异类［25］DICE 攻击方法，根据“从同类节点中删除连边，在不同类节点间增加连边”规则，利用启发式算法删除部分连边，随后通过添加连边恢复其影响力［24］；3）Min-max 攻击方法［18］，将攻击生成问题变成最小最大化的问题，最小化攻击的损失由投影梯度下降算法解决，最大化模型生成对抗数据的损失由梯度上升算法来解决；4）Metattack 攻击方法［26］，使用元学习中的元梯度方法解决投毒攻击的双层优化问题，通过计算元梯度以指导攻击行为，采用贪婪算法对邻接矩阵遍历扰动以实现攻击。

3.3.1 攻击性能分析

本文在Citeseer、Cora、Cora_ml 和Polblogs数据集上，对GCN 模型中1%～5%的连边数进行攻击，训练轮数为50，对抗训练学习率为0.02，记录攻击后的分类准确率。不同方法攻击后图卷积网络模型的分类准确率如表6 和图4 所示。其中，图4 的Clean 表示模型在攻击前的准确率。

图4 图卷积网络模型的分类准确率Fig.4 Classification accuracy of graph convolutional network model

表6 图卷积网络模型被不同方法攻击后的分类准确率Table 6 Classification accuracy of graph convolutional network model after attacks by different methods

从表6 可以看出，当扰动比例为5%以下时，相比Random、DICE、Min-max 攻击方法，本文PGattack方法具有更好的攻击效果，GCN 模型的分类准确率下降辐度更大。

本文方法与传统投影梯度下降攻击方法Min-max相比，扰动筛选算法均采用投影梯度下降算法。而Min-max 方法将训练后的参数视为固定常数，在此基础上使用投影梯度下降算法进行扰动；PGattack方法将参数视为扰动的函数而非独立变量，在梯度攻击过程中考虑模型的对抗训练阶段以优化攻击算法。实验结果验证了PGattack 方法的有效性，即在攻击中考虑模型的对抗训练过程以提升攻击效果。

本文方法与Metattack 相比，当扰动比例为3%以下时，PGattack 的攻击效果优于Metattack；当扰动比例为4%以上时，PGattack 的攻击效果与Metattack 相比较差。Metattack 采用贪婪算法实施攻击，随着扰动比例的增大，攻击效果逐渐提升。当扰动数据量较大时，贪婪算法对离散数据扰动的准确性更高，但是需要逐一对元素实施扰动，计算复杂度较高。

3.3.2 复杂度分析

随机增删连边的Random 和基于简单的规则增删连边的DICE 攻击方法均不需要对模型进行训练，计算复杂度较低。Min-max 先求解训练参数W，再将W视为常量，使用投影梯度下降算法实施扰动，未考虑模型的对抗训练过程，复杂度中等，但是高于DICE 和Random。PGattack 将训练参数W视为与扰动相关的变量，在采用投影梯度下降算法实施扰动时考虑模型的对抗训练过程，计算复杂度大于Min-max。Metattack 攻击方法先求解元梯度，之后采用贪婪算法对连边逐个扰动，计算复杂度随扰动比例增加呈线性增长。

在4 个数据集上不同攻击方法的时间开销对比如表7 所示。

表7 不同攻击方法的时间开销对比Table 7 Time costs comparison among different attack methods

从表7 可以看出，除Metattack 以外，其他4 种攻击方法的耗时排序：PGattack>Min-max>DICE>Random。Metattack 随着扰动连边数增多，耗时呈线性增长趋势。实验结果与理论分析一致。Metattack攻击方法在扰动比例较大时，尽管具有更好的攻击效果，但时间开销较大。本文所提的PGattack 方法能够兼顾攻击性能与复杂度，具有更好的实用性。

4 结束语

本文提出基于改进投影梯度下降算法的投毒攻击方法，将模型训练参数看作扰动的函数，采用投影梯度下降算法对图的连边进行扰动，同时考虑模型的对抗训练过程。实验结果表明，当扰动比例为5%时，相比Random、DICE、Min-max 攻击方法，本文攻击方法能够有效降低图卷积网络模型的的分类准确率，在攻击性能与时间开销方面实现最佳平衡。后续将在图神经网络的链路预测、图分类、社区发现等任务中构建投毒攻击模型，分析图神经网络的脆弱机理，以提高本文方法的可扩展性。