基于局部影响分析模型的图神经网络对抗攻击

吴翼腾; 刘伟; 于洪涛; 操晓春

doi:10.11999/JEIT210448

基于局部影响分析模型的图神经网络对抗攻击

doi: 10.11999/JEIT210448

1.
信息工程大学郑州 450002
2.
中国科学院信息工程研究所信息安全国家重点实验室北京 100093

基金项目: 自然科学基金创新研究群体项目(61521003)，国家重点研发计划(2016QY03D0502)，郑州市协同创新重大专项基金(162/32410218)

详细信息

作者简介:
吴翼腾：男，1992年生，博士，工程师，研究方向为人工智能安全、对抗机器学习

刘伟：男，1992年生，硕士，工程师，研究方向为人工智能安全、自然语言理解

于洪涛：男，1970年生，博士，研究员，博士生导师，主要研究方向为人工智能与大数据

通讯作者:
于洪涛　yht_ndsc@126.com

中图分类号: TN915.08; TP18
计量
- 文章访问数: 573
- HTML全文浏览量: 300
- PDF下载量: 99
- 被引次数: 0
出版历程
- 收稿日期: 2021-05-25
- 修回日期: 2021-12-21
- 录用日期: 2022-01-12
- 网络出版日期: 2022-02-03
- 刊出日期: 2022-07-25

Adversarial Attacks on Graph Neural Network Based on Local Influence Analysis Model

1.
Information Engineering University, Zhengzhou 450002, China
2.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Funds: The Innovative Research Groups of the National Natural Science Foundation of China (61521003), The National Key R&D Project (2016QY03D0502), Zhengzhou City Collaborative Innovation Major Project (162/32410218)

摘要

摘要: 图神经网络(GNN)容易受到对抗攻击安全威胁。现有研究未注意到图神经网络对抗攻击与统计学经典分支统计诊断之间的联系。该文分析了二者理论本质的一致性，将统计诊断的重要成果局部影响分析模型引入图神经网络对抗攻击。首先建立局部影响分析模型，提出并证明针对图神经网络攻击的扰动筛选公式，得出该式的物理意义为扰动对模型训练参数影响的度量。其次为降低计算复杂度，根据扰动筛选公式的物理意义得出扰动筛选近似公式。最后引入投影梯度下降算法实施扰动筛选。实验结果表明，将局部影响分析模型引入图神经网络对抗攻击领域具有合理性；与现有攻击方法相比，所提方法具有有效性。
- 图神经网络 /
- 对抗攻击 /
- 统计诊断 /
- 局部影响分析 /
- 投影梯度下降
Abstract: Graph Neural Networks (GNNs) are vulnerable to adversarial attacks. Existing papers do not pay attention to the relationship between adversarial attacks and statistical diagnosis, a classical branch of statistics. In this paper, the consistency of the two theories is analyzed, and the local influence analysis model, an important achievement of statistical diagnosis, is introduced into adversarial attack on GNNs. Firstly, the local influence analysis model is established to derive the equation of perturbation selecting of attacks, and the physical meaning of this equation is a measurement of the influence of perturbation on model training parameters. Secondly, to reduce the computational complexity, according to the physical meaning of the perturbation selecting equation, the approximate equation is obtained. Finally, the projected gradient descent algorithm is introduced to implement disturbance selecting. Experimental results show that it is reasonable to introduce the local influence analysis model into the field of adversarial attacks on graph neural network; Compared with the existing attack methods, the proposed method is more effective.
- Graph Neural Network (GNN) /
- Adversarial attack /
- Statistical diagnosis /
- Local influence analysis /
- Projected gradient descent

HTML全文

图 1 不同扰动量的攻击效果对比

下载: 全尺寸图片幻灯片

表 1 基于局部影响分析模型的图神经网络对抗攻击算法

输入：邻接矩阵A，特征矩阵X，标签Y，攻击点数n，迭代次　　　　数iters；
输出：扰动列表disturb_list
(1) disturb_list = [ ];
(2) for i = 1:iters:
(3) 　根据disturb_list更新扰动矩阵$ {{\hat {\boldsymbol A}}}' $；
(4) 　根据式(14)和式(5)重训练图神经网络得参数$ {{\mathbf{W}}^*} $；
(5) 　根据式(12)计算攻击梯度$ {\nabla _{{{\hat {\boldsymbol A}}}}}{d^2} $；
(6) 　根据攻击梯度$ {\nabla _{{{\hat {\boldsymbol A}}}}}{d^2} $采用梯度下降算法更新扰动矩阵$ {{\hat {\boldsymbol A}}}' $；
(7) 　对$ {{\hat {\boldsymbol A}}}' $进行投影操作以控制扰动总量满足约束条件，disturb 　　　　list=$ {{\hat {\boldsymbol A}}}' - {\mathbf{A}} $；
(8) 　end for
(9) 把$ {{\hat {\boldsymbol A}}}' $还原为邻接矩阵$ {{\hat {\boldsymbol A}}} $；
(10) 返回disturb list=$ {{\hat {\boldsymbol A}}} - {\mathbf{A}} $。

下载: 导出CSV

表 2 数据集统计特性

数据集	节点数	连边数	特征维数	分类数
Polblogs	1222	16714	1490	2
Cora_ml	2810	7981	2879	7
Cora	2485	5069	1433	7
Citeseer	2110	3668	3703	6

下载: 导出CSV

表 3 本文方法与其他攻击方法的对比(%)

	方法	Polblogs	Cora_ml	Cora	Citeseer
k = 1	未扰动	94.70	86.51	85.09	74.70
	Random	94.62	86.51	85.12	74.15
	Mettack	92.15	85.33	84.43	74.83
	Min-max	92.56	85.36	83.66	74.11
	本文方法	91.37	84.87	83.55	73.12
k = 2	未扰动	95.65	88.02	87.24	74.72
	Random	95.62	88.11	87.20	74.48
	Mettack	94.06	80.52	80.94	73.02
	Min-max	95.05	87.65	86.49	75.11
	本文方法	92.91	75.53	78.75	68.12

下载: 导出CSV

表 4 投毒数据用于攻击其他图学习模型

	方法	Polblogs	Cora_ml	Cora	Citeseer
GCN	未扰动	94.57%	87.12%	85.20%	74.93%
	Random	94.34%	87.26%	85.13%	74.72%
	Mettack	92.45%	80.59%	81.02%	74.27%
	Min-max	92.77%	85.16%	84.83%	74.01%
	本文方法	91.22%	78.49%	79.71%	70.36%
DeepWalk	未扰动	92.23%	79.32%	74.29%	58.35%
	Random	92.19%	80.03%	74.44%	59.13%
	Mettack	91.06%	76.63%	72.27%	60.24%
	Min-max	92.15%	78.78%	73.75%	57.37%
	本文方法	90.36%	77.45%	71.47%	58.93%

下载: 导出CSV

参考文献(27)

[1]	白铂, 刘玉婷, 马驰骋, 等. 图神经网络[J]. 中国科学:数学, 2020, 50(3): 367–384. doi: 10.1360/N012019-00133 BAI Bo, LIU Yuting, MA Chicheng, et al. Graph neural network[J]. Scientia Sinica:Mathematica, 2020, 50(3): 367–384. doi: 10.1360/N012019-00133
[2]	康世泽, 吉立新, 张建朋. 一种基于图注意力网络的异质信息网络表示学习框架[J]. 电子与信息学报, 2021, 43(4): 915–922. doi: 10.11999/JEIT200034 KANG Shize, JI Lixin, and ZHANG Jianpeng. Heterogeneous information network representation learning framework based on graph attention network[J]. Journal of Electronics &Information Technology, 2021, 43(4): 915–922. doi: 10.11999/JEIT200034
[3]	徐冰冰, 岑科廷, 黄俊杰, 等. 图卷积神经网络综述[J]. 计算机学报, 2020, 43(5): 755–780. doi: 10.11897/SP.J.1016.2020.00755 XU Bingbing, CEN Keting, HUANG Junjie, et al. A survey on graph convolutional neural network[J]. Chinese Journal of Computers, 2020, 43(5): 755–780. doi: 10.11897/SP.J.1016.2020.00755
[4]	XU Han, MA Yao, LIU Haochen, et al. Adversarial attacks and defenses in images, graphs and text: A review[J]. International Journal of Automation and Computing, 2020, 17(2): 151–178. doi: 10.1007/s11633-019-1211-x
[5]	ZÜGNER D, AKBARNEJAD A, and GÜNNEMANN S. Adversarial attacks on neural networks for graph data[C]. The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, United Kingdom, 2018: 2847–2856.
[6]	MA Jiaqi, DING Shuangrui, and MEI Qiaozhu. Towards more practical adversarial attacks on graph neural networks[C]. The 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada, 2020.
[7]	LI Jia, ZHANG Honglei, HAN Zhichao, et al. Adversarial attack on community detection by hiding individuals[C]. The Web Conference 2020, Taipei, China, 2020: 917–927.
[8]	BOJCHEVSKI A and GÜNNEMANN S. Adversarial attacks on node embeddings via graph poisoning[C]. The 36th International Conference on Machine Learning, Long Beach, USA, 2019: 695–704.
[9]	COOK R D. Detection of influential observation in linear regression[J]. Technometrics, 1977, 19(1): 15–18. doi: 10.1080/00401706.1977.10489493
[10]	COOK R D. Influential observations in linear regression[J]. Journal of the American Statistical Association, 1979, 74(365): 169–174. doi: 10.1080/01621459.1979.10481634
[11]	韦博成, 鲁国斌, 史建清. 统计诊断引论[M]. 南京: 东南大学出版社, 1991: 442–488. WEI Bocheng, LU Guobin, and SHI Jianqing. Introduction to Statistical Diagnosis[M]. Nanjing: Southeast University Press, 1991: 442–488.
[12]	韦博成, 林金官, 解锋昌. 统计诊断[M]. 北京: 高等教育出版社, 2009: 101–118. WEI Bocheng, LIN Jinguan, and XIE Fengchang. Statistical Diagnosis[M]. Beijing: Higher Education Press, 2009: 101–118.
[13]	YUAN Xiaoyong, HE Pan, ZHU Qile, et al. Adversarial examples: Attacks and defenses for deep learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30(9): 2805–2824. doi: 10.1109/TNNLS.2018.2886017
[14]	闫佳, 闫佳, 聂楚江, 等. 基于遗传算法的恶意代码对抗样本生成方法[J]. 电子与信息学报, 2020, 42(9): 2126–2133. doi: 10.11999/JEIT191059 YAN Jia, YAN Jia, NIE Chujiang, et al. Method for generating malicious code adversarial samples based on genetic algorithm[J]. Journal of Electronics &Information Technology, 2020, 42(9): 2126–2133. doi: 10.11999/JEIT191059
[15]	ZÜGNER D and GÜNNEMANN S. Adversarial attacks on graph neural networks via meta learning[C]. The 7th International Conference on Learning Representations, New Orleans, USA, 2019.
[16]	WU Yiteng, LIU Wei, HU Xinbang, et al. Parameter discrepancy hypothesis: Adversarial attack for graph data[J]. Information Sciences, 2021, 577: 234–244. doi: 10.1016/j.ins.2021.06.086
[17]	COOK R D and WEISBERG S. Residuals and Influence in Regression[M]. New York: Chapman and Hall, 1982: 1–20.
[18]	XU Kaidi, CHEN Hongge, LIU Sijia, et al. Topology attack and defense for graph neural networks: An optimization perspective[C]. The Twenty-Eighth International Joint Conference on Artificial Intelligence, Macao, China, 2019: 3961–3967.
[19]	LI Qimai, WU Xiaoming, LIU Han, et al. Label efficient semi-supervised learning via graph filtering[C]. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Long Beach, USA, 2019: 9582–9591.
[20]	NT H and MAEHARA T. Revisiting graph neural networks: All we have is low-pass filters[J]. arXiv: 1905.09550, 2019.
[21]	WU F, ZHANG Tianyi, DE SOUZA JR A H, et al. Simplifying graph convolutional networks[J]. arXiv: 1902.07153, 2019.
[22]	费宇, 陈飞, 喻达磊, 等. 线性和广义线性混合模型及其统计诊断[M]. 北京: 科学出版社, 2013: 51–82. FEI Yu, CHEN Fei, YU Dalei, et al. Linear and Generalized Linear Mixed Models and Their Statistical Diagnosis[M]. Beijing: Science Press, 2013: 51–82.
[23]	SEN P, NAMATA G, BILGIC M, et al. Collective classification in network data[J]. AI Magazine, 2008, 29(3): 93–106. doi: 10.1609/aimag.v29i3.2157
[24]	MCCALLUM A K, NIGAM K, RENNIE J, et al. Automating the construction of internet portals with machine learning[J]. Information Retrieval, 2000, 3(2): 127–163. doi: 10.1023/A:1009953814988
[25]	ADAMIC L A and GLANCE N. The political blogosphere and the 2004 U. S. election: Divided they blog[C]. The 3rd International Workshop on Link Discovery, Chicago, USA, 2005: 36–43.
[26]	KIPF T N and WELLING M. Semi-supervised classification with graph convolutional networks[C]. The 5th International Conference on Learning Representations, Toulon, France, 2017.
[27]	PEROZZI B, AL-RFOU R, and SKIENA S. Deepwalk: Online learning of social representations[C]. The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2014: 701–710.