高昕 安冬冬 章晓峰
摘 要： 为提高对抗性攻击在大规模图上的攻击效率，提出了基于子图采样的对抗样本生成方法. 该方法通过引入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 Xin1， AN Dongdong1?， ZHANG Xiaofeng2
（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.
猜你喜欢 对抗性子图集上 技能主导类隔网对抗性项群运动训练特征和实战技巧研究——以网球为例四川工商学院学术新视野(2021年1期)2021-07-22Cookie-Cutter集上的Gibbs测度数学年刊A辑(中文版)(2020年2期)2020-07-25链完备偏序集上广义向量均衡问题解映射的保序性数学物理学报(2019年6期)2020-01-13缺乏阳刚的男孩子要多参加对抗性运动家庭医学(下半月)(2019年8期)2019-09-25临界完全图Ramsey数同济大学学报（自然科学版）(2019年2期)2019-04-02关于羽毛球教学中多球训练的探讨东方教育(2018年19期)2018-08-23复扇形指标集上的分布混沌数学物理学报(2017年5期)2017-11-23技战能主导类格斗对抗性项群的竞技特点与训练要求中国体育教练员(2017年2期)2017-07-31基于频繁子图挖掘的数据服务Mashup推荐电子科技大学学报(2016年2期)2016-08-31不含2K1+K2和C4作为导出子图的图的色数华东师范大学学报（自然科学版）(2014年1期)2014-04-16
