Single Node Injection Attack against Graph Neural Networks

Abstract

Node injection attack on Graph Neural Networks (GNNs) is an emerging and practical attack scenario that the attacker injects malicious nodes rather than modifying original nodes or edges to affect the performance of GNNs. However, existing node injection attacks ignore extremely limited scenarios, namely the injected nodes might be excessive such that they may be perceptible to the target GNN. In this paper, we focus on an extremely limited scenario of single node injection evasion attack, i.e., the attacker is only allowed to inject one single node during the test phase to hurt GNN's performance. The discreteness of network structure and the coupling effect between network structure and node features bring great challenges to this extremely limited scenario. We first propose an optimization-based method to explore the performance upper bound of single node injection evasion attack. Experimental results show that 100%, 98.60%, and 94.98% nodes on three public datasets are successfully attacked even when only injecting one node with one edge, confirming the feasibility of single node injection evasion attack. However, such an optimization-based method needs to be re-optimized for each attack, which is computationally unbearable. To solve the dilemma, we further propose a Generalizable Node Injection Attack model, namely G-NIA, to improve the attack efficiency while ensuring the attack performance. Experiments are conducted across three well-known GNNs. Our proposed G-NIA significantly outperforms state-of-the-art baselines and is 500 times faster than the optimization-based method when inferring.

arXiv commentAccepted by the CIKM 2021; Code: https://github.com/TaoShuchang/G-NIA

References in corpus (16)

• Inductive Representation Learning on Large Graphs
• One pixel attack for fooling deep neural networks
• struc2vec: Learning Node Representations from Structural Identity
• Adversarial Attacks on Neural Networks for Graph Data
• DeepInf: Social Influence Prediction with Deep Learning
• AM-GCN: Adaptive Multi-channel Graph Convolutional Networks
• Adversarial Attacks on Graph Neural Networks via Meta Learning
• Adversarial Attack and Defense on Graph Data: A Survey
• Adversarial Attacks on Node Embeddings via Graph Poisoning
• Certifiable Robustness and Robust Training for Graph Convolutional Networks
• Graph Wavelet Neural Network
• A Survey of Adversarial Learning on Graphs
• Certifiable Robustness to Graph Perturbations
• Adversarial Immunization for Certifiable Robustness on Graphs
• Exploring Adversarial Examples: Patterns of One-Pixel Attacks
• Scalable Attack on Graph Data by Injecting Vicious Nodes

Cited by in corpus (9)

• Adversarial Attack and Defense on Graph Data: A Survey
• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• Unnoticeable Backdoor Attacks on Graph Neural Networks
• Node Injection for Class-specific Network Poisoning
• Cluster Attack: Query-based Adversarial Attacks on Graphs with Graph-Dependent Priors
• Node Injection Attack Based on Label Propagation Against Graph Neural Network
• Fast Inference of Removal-Based Node Influence
• Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation
• LiSA: Leveraging Link Recommender to Attack Graph Neural Networks via Subgraph Injection