Research Progress of Adversarial Defenses on Graphs

doi:10.3778/j.issn.1673-9418.2105021

Abstract

Abstract:

Graph neural networks (GNN) have been successfully applied in complex tasks in many fields, but recent studies show that GNN is vulnerable to graph adversarial attacks, leading to severe performance degradation. The vulnerability of GNN affects all applications including node classification, link prediction and community detection. Graph adversarial attacks can be implemented efficiently, which brings serious security risks and privacy issues. Graph adversarial defense is dedicated to improving the robustness and generalization of GNN to resist adversarial attacks. Research progress of graph adversarial defense algorithm is reviewed. First, the work background and related concepts of graph adversarial defense are introduced, and the development process of graph adversarial defense is analyzed. Then, according to different defense strategies of the defense algorithm, the algorithms are divided into four categories, including attack detection, adversarial training, robustness certification and immu-nologic defense and the strategies of each type of defense algorithm are summarized. Furthermore, the principles and implementation of defense algorithm are analyzed, and typical algorithms are compared in terms of defense strategies, target task, advantages, disadvantages and experiments. Finally, through a comprehensive and systematic analysis of the existing graph adversarial defense algorithm, the problems and developing directions of the defense algorithm are summarized to provide help for further development of graph adversarial defense.

Key words: graph data, graph neural networks (GNN), graph adversarial defense

摘要：

图神经网络（GNN）在多个领域的复杂任务中已经得到成功的应用，但研究表明其易受到对抗攻击而导致性能严重下降，这种脆弱性影响了包含节点分类、链路预测和社团探测在内的所有应用。图对抗攻击已经可以高效地实施，这带来了严重的安全隐患和隐私问题，图对抗防御致力于提高GNN的鲁棒性和泛化能力以抵御对抗攻击。综述了图对抗防御算法研究进展，首先，介绍了图对抗防御的背景和相关概念，并对图对抗防御研究发展脉络进行梳理和分析。然后，根据防御算法的不同防御策略将算法分为四类，包括攻击检测、对抗训练、可认证鲁棒性以及免疫防御，对每类防御算法原理进行分析总结。在此基础上，分析了每种防御算法的原理和实现，并从防御策略、目标任务、优缺点和实验数据等方面对典型算法进行全面的比较。最后，通过对现有图对抗防御算法全面、系统的分析，对防御算法当前存在的问题及未来发展方向进行了总结和探讨，为图对抗防御进一步的发展提供帮助。

关键词: 图数据, 图神经网络（GNN）, 图对抗防御

LI Penghui, ZHAI Zhengli, FENG Shu. Research Progress of Adversarial Defenses on Graphs[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(12): 2292-2303.

李鹏辉, 翟正利, 冯舒. 图对抗防御研究进展[J]. 计算机科学与探索, 2021, 15(12): 2292-2303.

References

[1] ZHANG S, YAO L, SUN A X, et al. Deep learning based recommender system: a survey and new perspectives[J]. ACM Computing Surveys, 2019, 52(1): 1-38.
[2] XU B B, CEN K T, HUANG J J, et al. A survey on graph convolutional neural network[J]. Chinese Journal of Com-puters, 2020, 43(5): 755-780.
徐冰冰, 岑科廷, 黄俊杰, 等. 图卷积神经网络综述[J]. 计算机学报, 2020, 43(5): 755-780.
[3] WU Z H, PAN S R, CHEN F W, et al. A comprehensive survey on graph neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 32(1): 4-24.
[4] ZHANG L, QIAN F, ZHAO S, et al. Network representa-tion learning via variational auto-encoder[J]. Journal of Fron-tiers of Computer Science and Technology, 2019, 13(10): 1733-1744.
张蕾, 钱峰, 赵姝, 等. 利用变分自编码器进行网络表示学习[J]. 计算机科学与探索, 2019, 13(10): 1733-1744.
[5] DING Y, HUANG L, WANG C D. Link prediction based on generative adversarial networks[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(4): 554-562.
丁玥, 黄玲, 王昌栋. 基于生成式对抗网络的链路预测方法[J]. 计算机科学与探索, 2019, 13(4): 554-562.
[6] LEVIE R, MONTI F, BRESSON X, et al. CayleyNets: graph convolutional neural networks with complex rational spectral filters[J]. IEEE Transactions on Signal Processing, 2018, 67(1): 97-109.
[7] YING R, HE R N, CHEN K F, et al. Graph convolutional neural networks for web-scale recommender systems[C]//Proceedings of the 24th ACM SIGKDD International Con-ference on Knowledge Discovery & Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 974-983.
[8] XU H, MA Y, LIU H, et al. Adversarial attacks and de-fenses in images, graphs and text: a review[J]. International Journal of Automation and Computing, 2020, 17(2): 151-178.
[9] SUN L, DOU Y, YANG C, et al. Adversarial attack and defense on graph data: a survey[J]. arXiv:1812.10528, 2018.
[10] ZüGNER D, AKBARNEJAD A, GüNNEMANN S. Adver-sarial attacks on neural networks for graph data[C]//Procee-dings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2847-2856.
[11] ZüGNER D, GüNNEMANN S. Adversarial attacks on graph neural networks via meta learning[J]. arXiv:1902. 08412, 2019.
[12] DAI H, LI H, TIAN T, et al. Adversarial attack on graph structured data[J]. arXiv:1806.02371, 2018.
[13] CHEN J Y, CHEN L H, CHEN Y X, et al. GA-based Q-attack on community detection[J]. IEEE Transactions on Computational Social Systems, 2019, 6(3): 491-503.
[14] FANG M H, YANG G L, GONG N Z, et al. Poisoning attacks to graph-based recommender systems[C]//Proceed-ings of the 34th Annual Computer Security Applications Conference, San Juan, Dec 3-7, 2018. New York: ACM, 2018: 381-392.
[15] YU J, GAO M, RONG W, et al. Hybrid attacks on model-based social recommender systems[J]. Physica A: Statis-tical Mechanics and Its Applications, 2017, 483: 171-181.
[16] BREUER A, EILAT R, WEINSBERG U. Friend or faux: graph-based early detection of fake accounts on social net-works[C]//Proceedings of the Web Conference 2020, Taipei,China, Apr 20-24, 2020. New York: ACM, 2020: 1287-1297.
[17] ZHANG Y, KHAN S, COATES M. Comparing and detec-ting adversarial attacks for graph deep learning[C]//Procee-dings of the 2019 International Conference on Learning Representations, New Orleans, May 6-9, 2019: 228-235.
[18] HOU S, FAN Y, ZHANG Y, et al. αCyber: enhancing robustness of Android malware detection system against adversarial attacks on heterogeneous graph based model[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management, Beijing, Nov 3-7, 2019. New York: ACM, 2019: 609-618.
[19] IOANNIDIS V N, BERBERIDIS D, GIANNAKIS G B. GraphSAC: detecting anomalies in large-scale graphs[J]. arXiv:1910.09589, 2019.
[20] ZHANG S, YIN H, CHEN T, et al. GCN-based user represen-tation learning for unifying robust recommendation and fraudster detection[J]. arXiv:2005.10150, 2020.
[21] FENG F, HE X, TANG J, et al. Graph adversarial training: dynamically regularizing based on graph structure[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(6): 2493-2504.
[22] WANG X, LIU X, HSIEH C J. GraphDefense: towards robust graph convolutional networks[J]. arXiv:1911.04429, 2019.
[23] JIN H W, ZHANG X H. Latent adversarial training of graph convolution networks[C]//Proceedings of the 2019 Workshop on Learning and Reasoning with Graph-Structured Representations, Long Beach, Jun 9-15, 2019. Red Hook: Curran Associates, 2019: 2925-2932.
[24] ZüGNER D, GüNNEMANN S. Certifiable robustness and robust training for graph convolutional networks[C]//Pro-ceedings of the 25th ACM SIGKDD International Confe-rence on Knowledge Discovery & Data Mining, Ancho-rage, Aug 4-8, 2019. New York: ACM, 2019: 246-256.
[25] ZüGNER D, GüNNEMANN S. Certifiable robustness of graph convolutional networks under structure perturbations[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Virtual Event, Aug 23-27, 2020. New York: ACM, 2020: 1656-1665.
[26] BOJCHEVSKI A, GüNNEMANN S. Certifiable robust-ness to graph perturbations[J]. arXiv:1910.14356, 2019.
[27] ZHU D, ZHANG Z, CUI P, et al. Robust graph convolu-tional networks against adversarial attacks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, Aug 4-8, 2019. New York: ACM, 2019: 1399-1407.
[28] TANG X, LI Y, SUN Y, et al. Transferring robustness for graph neural network against poisoning attacks[C]//Procee-dings of the 13th International Conference on Web Search and Data Mining, Houston, Feb 3-7, 2020. New York: ACM, 2020: 600-608.
[29] ZHANG X, ZITNIK M. GNNGuard: defending graph neural networks against adversarial attacks[J]. arXiv:2006.08149, 2020.
[30] WANG S, CHEN Z, NI J, et al. Adversarial defense frame-work for graph neural network[J]. arXiv:1905.03679, 2019.
[31] HUANG G, LIU Z, VAN DER MAATEN L, et al. Densely connected convolutional networks[C]//Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, Jul 21-26, 2017. Piscataway: IEEE, 2017: 2261-2269.
[32] JIN M, CHANG H, ZHU W, et al. Power up! Robust graph convolutional network against evasion attacks based on graph powering[J]. arXiv:1905.10029, 2019.
[33] JIN W, MA Y, LIU X, et al. Graph structure learning for robust graph neural networks[J]. arXiv:2005.10203, 2020.
[34] PEZESHKPOUR P, TIAN Y F, SINGH S. Investigating robustness and interpretability of link prediction via adver-sarial modifications[J]. arXiv:1905.00563, 2019.
[35] WANG B H, ZHANG L, GONG N Z. SybilSCAR: Sybil detection in online social networks via local rule based pro-pagation[C]//Proceedings of the 2017 IEEE Conference on Computer Communications, Atlanta, May 1-4, 2017. Pisca-taway: IEEE, 2017: 1-9.
[36] DAI Q, LI Q, TANG J, et al. Adversarial network embed-ding[J]. arXiv:1711.07838, 2017.
[37] DAI Q Y, SHEN X, ZHANG L, et al. Adversarial training methods for network embedding[C]//Proceedings of the World Wide Web Conference, San Francisco, May 13-17, 2019. New York: ACM, 2019: 329-339.
[38] XU K, CHEN H, LIU S, et al. Topology attack and defense for graph neural networks: an optimization perspective[J]. arXiv:1906.04214, 2019.
[39] XU K D, LIU S J, CHEN P Y, et al. Towards an efficient and general framework of robust training for graph neural networks[C]//Proceedings of the 2020 IEEE International Conference on Acoustics, Speech and Signal Processing, Barcelona, May 4-8, 2020. Piscataway: IEEE, 2020: 8479-8483.
[40] CHEN J, WU Y, LIN X, et al. Can adversarial network attack be defended?[J]. arXiv:1903.05994, 2019.
[41] SUN K, LIN Z C, GUO H T, et al. Virtual adversarial training on graph convolutional networks in node classifica-tion[C]//LNCS 11857: Proceedings of the 2nd Chinese Con-ference on Pattern Recognition and Computer Vision, Xi’an, Nov 8-11, 2019. Cham: Springer, 2019: 431-443.
[42] DENG Z, DONG Y, ZHU J. Batch virtual adversarial training for graph convolutional networks[J]. arXiv:1902. 09192, 2019.
[43] ZHOU K, MICHALAK T P, VOROBEYCHIK Y. Adversa-rial robustness of similarity-based link prediction[C]//Pro-ceedings of the 2019 IEEE International Conference on Data Mining, Beijing, Nov 8-11, 2019. Piscataway: IEEE, 2019: 926-935.
[44] MINERVINI P, DEMEESTER T, ROCKT?SCHEL T, et al. Adversarial sets for regularising neural link predictors[J]. arXiv:1707.07596, 2017.
[45] LéCUYER M, ATLIDAKIS V, GEAMBASU R, et al. Certified robustness to adversarial examples with differen-tial privacy[C]//Proceedings of the 2019 IEEE Symposium on Security and Privacy, San Francisco, May 19-23, 2019. Piscataway: IEEE, 2019: 656-672.
[46] BOJCHEVSKI A, KLICPERA J, GüNNEMANN S. Efficient robustness certificates for discrete data: sparsity-aware randomized smoothing for graphs, images and more[J]. arXiv:2008.12952, 2020.
[47] JIA J Y, WANG B H, CAO X Y, et al. Certified robustness of community detection against adversarial structural per-turbation via randomized smoothing[C]//Proceedings of the Web Conference 2020, Taipei, China, Apr 20-24, 2020. New York: ACM, 2020: 2718-2724.
[48] WU H, WANG C, TYSHETSKIY Y, et al. Adversarial examples on graph data: deep insights into attack and defense[J]. arXiv:1903.01610, 2019.
[49] ENTEZARI N, AL-SAYOURI S A, DARVISHZADEH A, et al. All you need is low (rank) defending against adversa-rial attacks on graphs[C]//Proceedings of the 13th Interna-tional Conference on Web Search and Data Mining, Hou-ston, Feb 3-7, 2020. New York: ACM, 2020: 169-177.
[50] MILLER B A, ?AMURCU M, GOMEZ A J, et al. Impro-ving robustness to attacks against vertex classification[C]// Proceedings of the 15th International Workshop on Mining and Learning with Graphs, Anchorage, Aug 5, 2019. New York: ACM, 2019: 1-8.
[51] LUO D, CHENG W, YU W, et al. Learning to drop: robust graph neural network via topological denoising[C]//Pro-ceedings of the 14th ACM International Conference on Web Search and Data Mining, Jerusalem, Mar 8-12, 2021. New York: ACM, 2021: 779-787.
[52] GEISLER S, ZüGNER D, GüNNEMANN S. Reliable graph neural networks via robust aggregation[C]//Procee-dings of the 34th Annual Conference on Neural Infor-mation Processing Systems 2020, Dec 6-12, 2020: 1-13.
[53] PENG S, MINE T. A robust hierarchical graph convolu-tional network model for collaborative filtering[J]. arXiv:2004.14734, 2020.
[54] YU S Q, ZHAO M H, FU C B, et al. Target defense against link-prediction-based attacks via evolutionary perturbations[J]. IEEE Transactions on Knowledge and Data Enginee-ring, 2021, 33(2): 754-767.
[55] LIM M, ABDULLAH A, JHANJHI N Z, et al. Hidden link prediction in criminal networks using the deep reinforce-ment learning technique[J]. Computers, 2019, 8(1): 8.
[56] KENLAY H, THANOU D, DONG X W. On the stability of polynomial spectral graph filters[C]//Proceedings of the 2020 IEEE International Conference on Acoustics, Speech and Signal Processing, Barcelona, May 4-8, 2020. Piscata-way: IEEE, 2020: 5350-5354.
[57] TAO S C, SHEN H W, CAO Q, et al. Adversarial immuniza-tion for improving certifiable robustness on graphs[J]. arXiv: 2007.09647, 2020.
[58] LOGINS A, LI Y C, KARRAS P. On the robustness of cascade diffusion under node attacks[C]//Proceedings of the Web Conference 2020, Taipei, China, Apr 20-24, 2020. New York: ACM, 2020: 2711-2717.
[59] HE X L, JIA J Y, BACKES M, et al. Stealing links from graph neural networks[J]. arXiv:2005.02131, 2020.
[60] XIE Y Q, LI S, YANG C, et al. When do GNNs work: under-standing and improving neighborhood aggregation[C]//Pr-oceedings of the 29th International Joint Conference on Artificial Intelligence, Yokohama, Jul 7-15, 2020: 1303- 1309.
[61] LI Y Y, CHEN L. Unified robust training for graph neural networks against label noise[J]. arXiv:2103.03414, 2021.
[62] KHOSLA P, TETERWAK P, WANG C, et al. Supervised contrastive learning[J]. arXiv:2004.11362, 2020.
[63] TSIPRAS D, SANTURKAR S, ENGSTROM L, et al. Ro-bustness may be at odds with accuracy[J]. arXiv:1805. 12152, 2018.