{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:35:45Z","timestamp":1780054545097,"version":"3.54.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP200101374"],"award-info":[{"award-number":["DP200101374"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Priv. Secur."],"published-print":{"date-parts":[[2023,11,30]]},"abstract":"<jats:p>Recent studies indicate that Graph Neural Networks (GNNs) are vulnerable to adversarial attacks. Particularly, adversarially perturbing the graph structure, e.g., flipping edges, can lead to salient degeneration of GNNs\u2019 accuracy. In general, efficiency and stealthiness are two significant metrics to evaluate an attack method in practical use. However, most prevailing graph structure-based attack methods are query intensive, which impacts their practical use. Furthermore, while the stealthiness of perturbations has been discussed in previous studies, the majority of them focus on the attack scenario targeting a single node. To fill the research gap, we present a global attack method against GNNs, Saturation adversarial Attack with Meta-gradient, in this article. We first propose an enhanced meta-learning-based optimization method to obtain useful gradient information concerning graph structural perturbations. Then, leveraging the notion of saturation attack, we devise an effective algorithm to determine the perturbations based on the derived meta-gradients. Meanwhile, to ensure stealthiness, we introduce a similarity constraint to suppress the number of perturbed edges. Thorough experiments demonstrate that our method can effectively depreciate the accuracy of GNNs with a small number of queries. While achieving a higher misclassification rate, we also show that the perturbations developed by our method are not noticeable.<\/jats:p>","DOI":"10.1145\/3611307","type":"journal-article","created":{"date-parts":[[2023,7,28]],"date-time":"2023-07-28T03:53:20Z","timestamp":1690516400000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["SAM: Query-efficient Adversarial Attacks against Graph Neural Networks"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2352-0485","authenticated-orcid":false,"given":"Chenhan","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0004-1801","authenticated-orcid":false,"given":"Shiyao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6392-6711","authenticated-orcid":false,"given":"James J. Q.","family":"Yu","sequence":"additional","affiliation":[{"name":"University of York, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4485-6743","authenticated-orcid":false,"given":"Shui","family":"Yu","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"695","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Bojchevski Aleksandar","year":"2019","unstructured":"Aleksandar Bojchevski and Stephan G\u00fcnnemann. 2019. Adversarial attacks on node embeddings via graph poisoning. In Proceedings of the International Conference on Machine Learning. 695\u2013704."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_3_2_4_2","first-page":"1277","volume-title":"Proceedings of the IEEE Symposium on Security and Privacy (SP\u201920)","author":"Chen Jianbo","year":"2020","unstructured":"Jianbo Chen, Michael I. Jordan, and Martin J. Wainwright. 2020. Hopskipjumpattack: A query-efficient decision-based attack. In Proceedings of the IEEE Symposium on Security and Privacy (SP\u201920). 1277\u20131294."},{"key":"e_1_3_2_5_2","first-page":"1115","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Dai Hanjun","year":"2018","unstructured":"Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. 2018. Adversarial attack on graph structured data. In Proceedings of the International Conference on Machine Learning. 1115\u20131124."},{"issue":"2","key":"e_1_3_2_6_2","first-page":"971","article-title":"Tracking network dynamics: A survey using graph distances","volume":"12","author":"Donnat Claire","year":"2018","unstructured":"Claire Donnat and Susan Holmes. 2018. Tracking network dynamics: A survey using graph distances. Ann. Appl. Stat. 12, 2 (2018), 971\u20131012.","journal-title":"Ann. Appl. Stat."},{"key":"e_1_3_2_7_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Du Jiawei","year":"2019","unstructured":"Jiawei Du, Hu Zhang, Joey Tianyi Zhou, Yi Yang, and Jiashi Feng. 2019. Query-efficient meta attack to deep neural networks. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_8_2","article-title":"Robustness of graph neural networks at scale","volume":"34","author":"Geisler Simon","year":"2021","unstructured":"Simon Geisler, Tobias Schmidt, Hakan \u015eirin, Daniel Z\u00fcgner, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2021. Robustness of graph neural networks at scale. Adv. Neural Inf. Process. Syst. 34 (2021).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_2_9_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Goodfellow Ian J.","year":"2015","unstructured":"Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining and harnessing adversarial examples. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_10_2","article-title":"Inductive representation learning on large graphs","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Proceedings of the International Conference on Neural Information Processing Systems (2017).","journal-title":"Proceedings of the International Conference on Neural Information Processing Systems"},{"key":"e_1_3_2_11_2","first-page":"2669","volume-title":"Proceedings of the 30th USENIX Security Symposium (USENIX Security\u201921)","author":"He Xinlei","year":"2021","unstructured":"Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. 2021. Stealing links from graph neural networks. In Proceedings of the 30th USENIX Security Symposium (USENIX Security\u201921). 2669\u20132686."},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/3394486.3403049","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining","author":"Jin Wei","year":"2020","unstructured":"Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. 2020. Graph structure learning for robust graph neural networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 66\u201374."},{"key":"e_1_3_2_13_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Kipf Thomas N.","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_14_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Kurakin Alexey","year":"2017","unstructured":"Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. 2017. Adversarial machine learning at scale. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_15_2","first-page":"896","volume-title":"Proceedings of the Workshop on Challenges in Representation Learning (ICML\u201913)","volume":"3","author":"Lee Dong-Hyun","year":"2013","unstructured":"Dong-Hyun Lee. 2013. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Proceedings of the Workshop on Challenges in Representation Learning (ICML\u201913), Vol. 3. 896."},{"key":"e_1_3_2_16_2","article-title":"Adversarial attack on large scale graph","author":"Li Jintang","year":"2021","unstructured":"Jintang Li, Tao Xie, Chen Liang, Fenfang Xie, Xiangnan He, and Zibin Zheng. 2021. Adversarial attack on large scale graph. IEEE Trans. Knowl. Data Eng. (2021).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.282"},{"key":"e_1_3_2_18_2","first-page":"108","volume-title":"Proceedings of the ACM SIGSAC Conference on Computer and Communications Security","author":"Mu Jiaming","year":"2021","unstructured":"Jiaming Mu, Binghui Wang, Qi Li, Kun Sun, Mingwei Xu, and Zhuotao Liu. 2021. A hard label black-box adversarial attack against graph neural networks. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 108\u2013125."},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/3128572.3140451","volume-title":"Proceedings of the ACM Workshop on Artificial Intelligence and Security","author":"Mu\u00f1oz-Gonz\u00e1lez Luis","year":"2017","unstructured":"Luis Mu\u00f1oz-Gonz\u00e1lez, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C. Lupu, and Fabio Roli. 2017. Towards poisoning of deep learning algorithms with back-gradient optimization. In Proceedings of the ACM Workshop on Artificial Intelligence and Security. 27\u201338."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.94.052315"},{"key":"e_1_3_2_21_2","article-title":"On first-order meta-learning algorithms","author":"Nichol Alex","year":"2018","unstructured":"Alex Nichol, Joshua Achiam, and John Schulman. 2018. On first-order meta-learning algorithms. arXiv:1803.02999. Retrieved from https:\/\/arxiv.org\/abs\/1803.02999","journal-title":"arXiv:1803.02999"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2020.2975048"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v29i3.2157"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3201243"},{"key":"e_1_3_2_25_2","volume-title":"Proceedings of the 2nd International Conference on Learning Representations (ICLR\u201914)","author":"Szegedy Christian","year":"2014","unstructured":"Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In Proceedings of the 2nd International Conference on Learning Representations (ICLR\u201914)."},{"key":"e_1_3_2_26_2","first-page":"1395","volume-title":"Proceedings of the IEEE International Conference on Big Data (Big Data\u201919)","author":"Takahashi Tsubasa","year":"2019","unstructured":"Tsubasa Takahashi. 2019. Indirect adversarial attacks via poisoning neighbors for graph convolutional networks. In Proceedings of the IEEE International Conference on Big Data (Big Data\u201919). 1395\u20131400."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371851"},{"key":"e_1_3_2_28_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Veli\u010dkovi\u0107 Petar","year":"2018","unstructured":"Petar Veli\u010dkovi\u0107, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph attention networks. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_29_2","first-page":"2023","volume-title":"Proceedings of the ACM SIGSAC Conference on Computer and Communications Security","author":"Wang Binghui","year":"2019","unstructured":"Binghui Wang and Neil Zhenqiang Gong. 2019. Attacking graph-based classification via manipulating the graph structure. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 2023\u20132040."},{"key":"e_1_3_2_30_2","article-title":"Evasion attacks to graph neural networks via influence function","author":"Wang Binghui","year":"2020","unstructured":"Binghui Wang, Tianxiang Zhou, Minhua Lin, Pan Zhou, Ang Li, Meng Pang, Cai Fu, Hai Li, and Yiran Chen. 2020. Evasion attacks to graph neural networks via influence function. arXiv:2009.00203. Retrieved from https:\/\/arxiv.org\/abs\/2009.00203","journal-title":"arXiv:2009.00203"},{"key":"e_1_3_2_31_2","first-page":"239","volume-title":"Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks","author":"Wang Haopei","year":"2015","unstructured":"Haopei Wang, Lei Xu, and Guofei Gu. 2015. Floodguard: A dos attack prevention extension in software-defined networks. In Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks. 239\u2013250."},{"key":"e_1_3_2_32_2","first-page":"5401","volume-title":"Proceedings of the IEEE International Conference on Big Data (Big Data\u201919)","author":"Wang Shen","year":"2019","unstructured":"Shen Wang and S. Yu Philip. 2019. Heterogeneous graph matching networks: Application to unknown malware detection. In Proceedings of the IEEE International Conference on Big Data (Big Data\u201919). 5401\u20135408."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41562-017-0290-3"},{"key":"e_1_3_2_34_2","first-page":"4838","volume-title":"Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Wu Bingzhe","year":"2022","unstructured":"Bingzhe Wu, Yatao Bian, Hengtong Zhang, Jintang Li, Junchi Yu, Liang Chen, Chaochao Chen, and Junzhou Huang. 2022. Trustworthy graph learning: Reliability, explainability, and privacy protection. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 4838\u20134839."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAI.2021.3076021"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/550"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV48922.2021.00765"},{"key":"e_1_3_2_39_2","first-page":"3328","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Zang Xiao","year":"2021","unstructured":"Xiao Zang, Yi Xie, Jie Chen, and Bo Yuan. 2021. Graph universal adversarial attacks: A few bad actors ruin graph learning models. In Proceedings of the International Joint Conference on Artificial Intelligence. 3328\u20133334."},{"key":"e_1_3_2_40_2","article-title":"Trustworthy graph neural networks: Aspects, methods and trends","author":"Zhang He","year":"2022","unstructured":"He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. 2022. Trustworthy graph neural networks: Aspects, methods and trends. arXiv:2205.07424. Retrieved from https:\/\/arxiv.org\/abs\/2205.07424","journal-title":"arXiv:2205.07424"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/3450569.3463560","volume-title":"Proceedings of the ACM Symposium on Access Control Models and Technologies","author":"Zhang Zaixi","year":"2021","unstructured":"Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. 2021. Backdoor attacks to graph neural networks. In Proceedings of the ACM Symposium on Access Control Models and Technologies. 15\u201326."},{"key":"e_1_3_2_42_2","first-page":"3749","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Zhang Zaixi","year":"2021","unstructured":"Zaixi Zhang, Qi Liu, Zhenya Huang, Hao Wang, Chengqiang Lu, Chuanren Liu, and Enhong Chen. 2021. GraphMI: Extracting private graph data from graph neural networks. In Proceedings of the International Joint Conference on Artificial Intelligence. 3749\u20133755."},{"key":"e_1_3_2_43_2","first-page":"2847","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining","author":"Z\u00fcgner Daniel","year":"2018","unstructured":"Daniel Z\u00fcgner, Amir Akbarnejad, and Stephan G\u00fcnnemann. 2018. Adversarial attacks on neural networks for graph data. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2847\u20132856."},{"key":"e_1_3_2_44_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Z\u00fcgner Daniel","year":"2018","unstructured":"Daniel Z\u00fcgner and Stephan G\u00fcnnemann. 2018. Adversarial attacks on graph neural networks via meta learning. In Proceedings of the International Conference on Learning Representations."}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3611307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:54Z","timestamp":1750287054000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,11,30]]}},"alternative-id":["10.1145\/3611307"],"URL":"https:\/\/doi.org\/10.1145\/3611307","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"value":"2471-2566","type":"print"},{"value":"2471-2574","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]},"assertion":[{"value":"2022-11-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}