A Random Walk Based Black-Box Adversarial Attack against Graph Neural Network

doi:10.3969/j.issn.1671-1122.2024.10.011

Abstract

Abstract:

Graph neural networks have achieved remarkable success on many graph analysis tasks. However, recent studies have unveiled their susceptibility to adversarial attacks.The existing research on black box attacks often requires attackers to know all the training data of the target model, and is not applicable in scenarios where attackers have difficulty obtaining feature representations of graph neural network nodes.This paper proposed a more strict black-box attack model, where the attacker only possessed knowledge of the graph structure and labels of select nodes, but remained unaware of node feature representations. Under this attack model, this paper proposed a black-box adversarial attack method against graph neural networks. The approach approximated the influence of each node on the model output and identified optimal perturbations with greedy strategy. Experiments show that though less information is available, the attack success rate of this algorithm is close to that of the state-of-the-art algorithms, while achieving a higher attack speed. In addition, the attack method in this article also has migration and anti-defense capabilities.

Key words: artificial intelligence security, graph neural network, adversarial attacks

CLC Number:

TP309

LU Xiaofeng, CHENG Tianze, LONG Chengnian. A Random Walk Based Black-Box Adversarial Attack against Graph Neural Network[J]. Netinfo Security, 2024, 24(10): 1570-1577.

Figures/Tables 7

References 19

[1]	YING Zhitao, HE Ruining, CHEN Kaifeng, et al. Graph Convolutional Neural Networks for Web-Scale Recommender Systems[C]// ACM. Proceedings of the 24th ACM SIGKDD Cnternational Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018: 974-983.
[2]	LI Cheng, MA Jiaqi, GUO Qiaozhu, et al. Deepcas: An End-to-End Predictor of Information Cascades[C]// ACM. Proceedings of the 26th International Conference on World Wide Web. New York: ACM, 2017: 577-586.
[3]	WEBER M, DOMENICONI G, CHEN Jie, et al. Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics[EB/OL]. (2019-07-31)[2024-04-10]. https://arxiv.org/pdf/1908.02591.
[4]	ZUGNER D, AKBARNEJAD A, GUNNEMANN S. Adversarial Attacks on Neural Networks for Graph Data[C]// ACM. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018: 2847-2856.
[5]	SUN Lichao, DOU Yingtong, YANG C, et al. Adversarial Attack and Defense on Graph Data: A Survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(8): 7693-7711.
[6]	MAHMOOD K, MAHMOOD R, RATHBUN E, et al. Back in Black: A Comparative Evaluation of Recent State-of-the-Art Black-Box Attacks[J]. IEEE Access, 2021, 10: 998-1019.
[7]	ZUGNER D, GUNNEMANN S. Adversarial Attacks on Graph Neural Networks via Meta Learning[EB/OL]. (2024-01-28)[2024-04-10]. https://arxiv.org/pdf/1902.08412.
[8]	DAI Hanjun, LI Hui, TIAN T, et al. Adversarial Attack on Graph Structured Data[C]// IEEE. International Conference on Machine Learning. New York: IEEE, 2018: 1115-1124.
[9]	MA Yao, WANG Suhang, DERR T, et al. Attacking Graph Convolutional Networks via Rewiring[EB/OL]. (2019-09-28)[2024-04-10]. https://arxiv.org/pdf/1906.03750.
[10]	CHANG Heng, RONG Yu, XU Tingyang, et al. A Restricted Black-Box Adversarial Framework towards Attacking Graph Embedding Models[C]// AAAI. Proceedings of the AAAI Conference on Artificial Intelligence. Menlo Park: AAAI, 2020, 34(4): 3389-3396.
[11]	MA Jiaqi, DING Shuangrui, MEI Qiaozhu. Towards More Practical Adversarial Attacks on Graph Neural Networks[J]. Advances in Neural Information Processing Systems, 2020, 33: 4756-4766.
[12]	KIPF T N, WELLING M. Semi-Supervised Classification with Graph Convolutional Networks[EB/OL]. (2017-02-22)[2024-04-10]. https://arxiv.org/pdf/1609.02907.
[13]	GASTEIGER J, BOJCHEVSKI A, GUNNEMANN S. Predict then Propagate: Graph Neural Networks Meet Personalized Pagerank[EB/OL]. (2022-04-05)[2024-04-10]. https://arxiv.org/pdf/1810.05997.
[14]	LOVASZ L. Random Walks on Graphs[J]. Combinatorics, Paul Erdos is Eighty, 1993, 2(1): 4-11.
[15]	WANIEK M, MICHALAK T P, WOOLDRIDGE M J, et al. Hiding Individuals and Communities in a Social Network[J]. Nature Human Behaviour, 2018, 2(2): 139-147.
[16]	CHEN Jinyin, WU Yangyang. Fast Gradient Attack on Network Embedding[EB/OL]. (2018-09-15)[2024-04-10]. https://arxiv.org/pdf/1809.02797.
[17]	WU Huijun, WANG Chen, TYSHETSKIY Y, et al. Adversarial Examples on Graph Data: Deep Insights into Attack and Defense[EB/OL]. (2019-05-22)[2024-04-10]. https://arxiv.org/pdf/1903.01610.
[18]	ENTEZARI N, Al-SAYOURI S A, DARVISHZADEH A, et al. All You Need is Low (Rank) Defending against Adversarial Attacks on Graphs[C]// ACM. Proceedings of the 13th International Conference on Web Search and Data Mining. New York: ACM, 2020: 169-177.
[19]	ZHU Dingyuan, ZHANG Ziwei, CUI Peng, et al. Robust Graph Convolutional Networks against Adversarial Attacks[C]// ACM. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2019: 1399-1407.

数据集	Nodes	Edges	Features	Classes	Degrees
Citeseer	2110	3668	3703	6	1.74
Cora	2485	5069	1433	7	2.04
Cora-ML	2810	7981	2879	7	2.84

数据集	GCN	Jaccard	SVD	RGCN
CiteSeer	71.80%	72.33%	67.77%	70.82%
Cora	83.20%	82.25%	69.20%	82.92%
Cora-ML	85.14%	84.79%	77.54%	85.05%

数据集	攻击	GCN	Jaccard	SVD	RGCN
CiteSeer	Myattack	88%	84%	6%	96%
	Nettack	88%	85%	10%	95%
	DICE	42%	20%	48%	28%
Cora	Myattack	86%	58%	18%	94%
	Nettack	92%	78%	24%	90%
	DICE	26%	12%	40%	20%
Cora-ML	Myattack	84%	80%	10%	88%
	Nettack	90%	44%	16%	58%
	DICE	22%	18%	42%	16%