Graph Adversarial Immunization for Certifiable Robustness
Despite achieving great success, graph neural networks (GNNs) are vulnerable to adversarial attacks. Existing defenses focus on developing adversarial training or model modification. In this paper, we propose and formulate graph adversarial immunization, i.e., vaccinating part of graph structure to improve certifiable robustness of graph against any admissible adversarial attack. We first propose edge-level immunization to vaccinate node pairs. Unfortunately, such edge-level immunization cannot defend against emerging node injection attacks, since it only immunizes existing node pairs. To this end, we further propose node-level immunization. To avoid computationally intensive combinatorial optimization associated with adversarial immunization, we develop AdvImmune-Edge and AdvImmune-Node algorithms to effectively obtain the immune node pairs or nodes. Extensive experiments demonstrate the superiority of AdvImmune methods. In particular, AdvImmune-Node remarkably improves the ratio of robust nodes by 79%, 294%, and 100%, after immunizing only 5% of nodes. Furthermore, AdvImmune methods show excellent defensive performance against various attacks, outperforming state-of-the-art defenses. To the best of our knowledge, this is the first attempt to improve certifiable robustness from graph data perspective without losing performance on clean graphs, providing new insights into graph adversarial learning.
Code (1)
Tasks
Adversarial AttackCombinatorial OptimizationSimilar Papers 제목 키워드 기반
Adversarial Immunization for Certifiable Robustness on Graphs
Despite achieving strong performance in semi-supervised node classification task, graph neural networks (GNNs) are vulnerable to adversarial attacks, similar to other deep learning models. Existing researches focus on de…
Adversarial AttackBilevel OptimizationCombinatorial OptimizationNode ClassificationCertifiably Robust Graph Contrastive Learning
Graph Contrastive Learning (GCL) has emerged as a popular unsupervised graph representation learning method. However, it has been shown that GCL is vulnerable to adversarial attacks on both the graph structure and node a…
Contrastive LearningGraph Representation LearningRepresentation LearningCertifiable Robustness to Graph Perturbations
Despite the exploding interest in graph neural networks there has been little effort to verify and improve their robustness. This is even more alarming given recent findings showing that they are extremely vulnerable to …
Certifiable Robustness and Robust Training for Graph Convolutional Networks
Recent works show that Graph Neural Networks (GNNs) are highly non-robust with respect to adversarial attacks on both the graph structure and the node attributes, making their outcomes unreliable. We propose the first me…
Node ClassificationTowards Certifiable Adversarial Sample Detection
Convolutional Neural Networks (CNNs) are deployed in more and more classification systems, but adversarial samples can be maliciously crafted to trick them, and are becoming a real threat. There have been various proposa…
Adversarial Robustness