基于子图采样的大规模图对抗性攻击方法

高昕 安冬冬 章晓峰

摘  要： 为提高对抗性攻击在大规模图上的攻击效率，提出了基于子图采样的对抗样本生成方法. 该方法通过引入PageRank、余弦相似度及K跳子图等技术，提取与目标节点高度相关的子图，在大规模图上缓解了计算梯度效率较低的问题，在降低被攻击模型准确性的同时提升了攻击的隐蔽性. 实验结果表明： 所提出的对抗性攻击方法与基于梯度攻击的GradArgmax算法相比，在Cora数据集上提升了30.7%的攻击性能，且在Reddit大规模数据上能够计算GradArgmax算法无法计算的攻击扰动.

关键词： 图神经网络； 对抗性攻击； 子图提取算法

中图分类号： TP 181    文献标志码： A    文章编号： 1000-5137（2024）02-0167-05

Subgraph sampling-based adversarial attack method for large-scale graphs

GAO Xin¹， AN Dongdong^1?， ZHANG Xiaofeng²

（1.College of Information， Mechanical and Electrical Engineering， Shanghai Normal University，Shanghai 201418， China； 2.Shanghai Newtouch Software Co.， Ltd.， Shanghai 200120， China）

Abstract： A subgraph sampling-based adversarial example generation method was proposed to enhance the efficiency of adversarial attacks on large-scale graphs. PageRank， cosine similarity， and K-hop subgraphs were employed to extract subgraphs highly relevant to the target node in this method， alleviating the issue of low gradient computation efficiency in large-scale graphs. The stealthiness of the attack was also increased while reducing the accuracy of the attacked model. Experimental results showed that attack performance was improved by 30.7% on the Cora dataset by this adversarial attack method compared to the GradArgmax algorithm， and attack perturbations on large-scale like Reddit dataset could be computed which the GradArgmax algorithm could not achieve.

Key words： graph neural network； adversarial attack； subgraph extraction algorithm

随着图神经网络在商品推荐^［1-3］、信用评估^［4］等现实领域的广泛应用，其安全性问题已经成为一个重要的关注点. 在这个背景下，对抗性攻击作为一种攻击手段，研究如何生成对抗性样例，以评估和提高模型的安全性变得至关重要. 图神经网络强大的图数据分析能力来源于其消息传递机制，这也为恶意攻击者提供了机会.攻击者可以通过构建微小的扰动至原图，导致模型输出错误的结果.

目前已有的研究中，DAI等^［5］提出GradArgmax方法，通过训练代理模型提取梯度信息，生成对抗扰动叠加至原图，从而实现攻击效果；XU等^［6］提出了project gradient descent（PGD）結构攻击，从一阶优化的角度进行梯度攻击；ZUGNER等^［7］提出Nettack方法，通过修改图结构或特征，最大化代理模型的损失函数.但是随着数据规模的不断增长，由于大多数攻击算法需要存储不必要的图信息，时间和内存成本上升较多，难以实现对更大规模的图进行攻击^［8］.

本文作者针对上述问题，提出了基于大规模图节点分类的对抗性攻击方法. 首先通过提取目标节点的K跳内节点，并利用PageRank、余弦相似度等方法提取其余高关联节点采样子图，减少攻击方法所存储的不必要的图信息；同时，利用线性图卷积网络（GCN）训练代理模型，提高梯度计算效率. 实验结果表明，该方法能够在降低时间和空间成本的同时，有效施加攻击，从而降低原模型的准确性.

1  模型定义和问题描述

定义待攻击图，其中，表示结构矩阵表示特征矩阵，每个节点拥有一个标签.对于半监督节点分类任务，利用所有已有标签节点信息，最小化模型损失函数以学习模型构建节点到标签的映射：

， （1）

其中，为图的节点集合；（·）为交叉熵损失函数；为分类器在节点上的预测分类；为实际节点分类.

对于攻击者，通过在满足攻击约束的条件下，设计结构攻击及特征攻击叠加至原图，得到攻击后的图，最大化分类错误

（2）

其中，.本研究以攻擊预算为约束条件，即攻击者仅能修改特定次数的结构矩阵或特征矩阵.

2  算法实现

2.1 训练代理模型

构建代理模型用于后续梯度计算. 多种图神经网络模型都可被用作代理模型，如GCN、图注意力（GAT）网络. 但是，传统的GCN模型通常由于效率较低，难以用于对大规模图神经网络的训练. 因此，使用线性神经网络模型（SGC）作为代理模型. SGC使用线性变换，不使用ReLU函数作为激活函数，一个2层SGC可以被表示为

， （3）

其中，表示压缩后的权重矩阵.通过训练参数构建代理模型，用于后续的攻击.

2.2 子图提取

采用子图提取技术来降低计算成本. 设计若干提取器，提取关联性较高的节点，得到最终的子图.对于子图的计算，在减少计算规模的同时，减少了攻擊算法存储的不必要的参数，以提升攻击效率.

2.2.1 K跳子图提取器

浅层邻域对于图神经网络来说足以学习到有效的节点表示，通过提取一个K跳子图来避免过度的计算量.K跳子图定义如下：

（4）

其中，表示节点到节点的最短距离；表示K跳子图的跳数；表示与节点距离小于的所有节点集合；表示与节点距离小于的所有节点的连边集合，最终得到K跳子图.

2.2.2 Personalized PageRank提取器

节点通常与之高度相关的节点相连，与相关性较低的节点的连接往往不隐蔽. 因此，为了增强隐蔽性，有必要将攻击限制在高度相关的节点上. PageRank算法通常用于计算节点之间的重要性，通过使用改进的Personalized PageRank算法，计算特定节点到其余节点的相关性. Personalized PageRank 可被描述为：

（5）

其中，是重启概率，控制随机游走的每一步中选择回到初始节点的概率為单位矩阵；为节点数量；为归一化矩阵.

2.2.3 余弦相似度提取器

在多数场景中，若两个节点的特征高度相似，则可被看作高度相关的节点，通过计算余弦相似度来表示两个节点的相似性：

. （6）

2.2.4 目标节点相关分数

首先计算各个节点与目标节点的相关分数

， （7）

其中，，表示提取器类型c表示提取器的权重；表示节点在提取器下的分数，得到：

（8）

设置超参数作为子图提取的阈值，若， 则将节点添加至子图：

. （9）

将上述子图与K跳子图进行合并：

，（10）

2.3 梯度計算

通过提取子图和训练代理模型，可以计算梯度，选择扰动进行攻击. 计算目标节点在子图上的损失函数梯度

（11）

其中，表示损失函数相对于邻接矩阵的偏导数表示最终提取的子图的梯度.

为了保证扰动的隐蔽性，需要避免攻击效果作用于低相关性的节点，首先对相关分数进行归一化，作为梯度的系数：

（12）

其中，表示各个节点与目标节点的相关分数.

最后，通过选择最大梯度，遵照以下规则进行扰动：

（13）

3  实验及结果分析

3.1 实验设置

在4个开源数据集上评估方法的性能：Citeseer，Cora，Pubmed以及Reddit. 前三个数据集为文献引用数据集，节点为文献，连边表示节点间存在引用；Reddit为社区论坛数据集，节点表示不同实体，如用户、帖子等，连边为用户间的交互、帖子与用户的关系等. 其中，Citeseer和Cora作为小规模数据集，用于评估方法的可行性；Pubmed和Reddit作为大规模数据集，用于评估方法在大规模数据集上的效率. 数据随机选择30%的节点作为训练集，70%作为测试集.

使用常见的GCN^［9］，GAT^［10］，GraphSage^［11］作为实验的目标模型，通过评估攻击算法在目标模型上的攻击前、攻击后的准确率，验证攻击算法的有效性.

将方法与以下2种方法进行比对：

随机攻击（RA）：随机地添加或删除连边；

GradArgmax：通过代理模型提取梯度信息，在所有已存在的边中，删除梯度最大的边.

对于节点分类任务，在受到攻击后，目标模型会降低分类的准确率. 因此，使用分类准确性来评估模型攻击的有效性.

3.2 模型性能分析

表1为各对抗性攻击算法作用于目标模型后，模型在小规模数据集上的分类准确率. 可以看出，在小规模数据集上，相较随机攻击算法和GradArgmax算法，本方法表现更好，说明通过子图采样后，算法能够更有效地选择攻击对象，使目标模型更容易产生误分类的情况. 图1展示了各攻击方法在Citeseer和Cora数据集上的攻击有效性，可以发现本方法的攻击有效性优于其余两种攻击方法.

表2为各对抗性攻击算法作用于目标模型后，模型在大规模数据集上的分类准确率. 可以看出，本方法能有效地施加攻击. 同时，在Reddit数据集上，本方法在实现攻击的同时，能够大幅降低目标模型的准确率.

4  结语

本文作者提出了大规模图节点分类任务上的对抗性攻击算法. 该算法在使用梯度攻击的基础上，引入了子图采样的方法，通过提取与目标节点高度相关的节点，在降低算法计算规模的同时，能够更有效地施加扰动. 实验表明，所提出的算法能够对大规模图进行高效的攻击.

参考文献：

［1］ YIN H Z， SUN Y Z， XU G D， et al. Trustworthy recommendation and search： introduction to the special issue part 1 ［J］. ACM Transactions on Information Systems， 2023，41（3）：51.

［2］ NIU X C， LI B F， LI C L， et al. A dual heterogeneous graph attention network to improve long-tail performance for shop search in e-commerce ［C］// The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Virtual Event： ACM， 2020：3405-3415.

［3］ ZHAO K， ZHENG Y K， ZHUANG T， et al. Joint learning of e-commerce search and recommendation with a unified graph neural network ［C］// The Fifteenth ACM International Conference on Web Search and Data Mining. Virtual Event： ACM， 2022：1461-1469.

［4］ LIU Z Q， CHEN C C， YANG X X， et al. Heterogeneous graph neural networks for malicious account detection ［C］// The 27th ACM International Conference on Information and Knowledge Management. Torino： ACM， 2018：2077-2085.

［5］ DAI H J， LI H， TIAN T， et al. Adversarial attack on graph structured data ［C］// Proceedings of the 35th International Conference on Machine Learning. Stockholm： ACM， 2018：1123-1132.

［6］ XU K D， CHEN H G， LIU S J， et al. Topology attack and defense for graph neural networks： an optimization perspective ［C］// Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Macao： ACM， 2019：3961-3967.

［7］ Z?GNER D， AKBARNEJAD A， G?NNEMANN S. Adversarial attacks on neural networks for graph data ［C］//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Macao： ACM， 2019：6246-6250.

［8］ LI J T， XIE T， CHEN L， et al. Adversarial attack on large scale graph ［J］. IEEE Transactions Knowledge Data Engineering， 2023，35（1）：82-95.

［9］ KIPF T N， WELLING M. Semi-supervised classification with graph convolutional networks ［J/OL］. arXiv，2016 ［2023-10-10］. https：// arxiv.org/abs/1609.02907.

［10］ VELICKOVIC P， CUCURULL G， CASANOVA A， et al. Graph attention networks ［C］// 6th International Conference on Learning Representations.Vancouver：ICLR， 2018：1-12.

［11］ HAMILTON W L， YING R， LESKOVEC J. Inductive representation learning on large graphs ［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Long Beach： ACM， 2017：1025-1035.

（責任编辑：包震宇，顾浩然）

DOI： 10.3969/J.ISSN.1000-5137.2024.02.004

收稿日期： 2023-12-15

基金项目： 国家自然科学基金青年基金（62302308），上海市青年科技英才扬帆计划（21YF1432900）

作者简介： 高昕（1998—）， 男， 硕士研究生， 主要从事对抗图网络方面的研究. E-mail： 1000513347@smail.shnu.edu.cn

* 通信作者： 安冬冬（1990—）， 女， 讲师， 主要从事形式化验证方面的研究. E-mail：andongdong@shnu.edu.cn

引用格式： 高昕， 安冬冬， 章晓峰. 基于子图采样的大规模图对抗性攻击方法 ［J］. 上海师范大学学报 （自然科学版中英文）， 2024，53（2）：167?171.

Citation format： GAO X， AN D D， ZHANG X F. Subgraph sampling-based adversarial attack method for large-scale graphs ［J］. Journal of Shanghai Normal University （Natural Sciences）， 2024，53（2）：167?171.