Source-linked AI summary
Adversarial Attack on Graph Structured Data
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, Le Song
TL;DR
Graph neural network robustness is underexplored even though modifying graph relationships can create serious risks. The paper develops attacks matched to different levels of classifier access and evaluates them on graph- and node-classification tasks, finding that GNNs are vulnerable and that attacks can help diagnose classifiers.
Problem
Graph neural network robustness has received limited attention compared with adversarial attacks on images and text, despite risks from modifying graph relationships.
Method
The paper proposes RL-S2V for label-only black-box attacks and provides gradient-, genetic-, and sampling-based methods for settings with different classifier access.
Results
The experiments show that a family of GNNs is vulnerable to adversarial attacks in both graph-level and node-level classification tasks.
Takeaways & Limitations
Adversarial attack samples can be used to inspect or diagnose learned graph classifiers, while the paper also discusses defenses against such attacks.
Takeaways & Limitations
The attack settings are bounded by classifier access, ranging from full information to prediction labels or queries on only some samples.
Abstract
from arXiv · showhide
Deep learning on graph structures has shown exciting results in various applications. However, few attentions have been paid to the robustness of such models, in contrast to numerous research work for image or text adversarial attack and defense. In this paper, we focus on the adversarial attacks that fool the model by modifying the combinatorial structure of data. We first propose a reinforcement learning based attack method that learns the generalizable attack policy, while only requiring prediction labels from the target classifier. Also, variants of genetic algorithms and gradient methods are presented in the scenario where prediction confidence or gradients are available. We use both synthetic and real-world data to show that, a family of Graph Neural Network models are vulnerable to these attacks, in both graph-level and node-level classification tasks. We also show such attacks can be used to diagnose the learned classifiers.
1. Introduction
The paper addresses the underexplored robustness of graph neural networks by attacking their discrete combinatorial structures. It introduces attacks under different classifier-access settings and evaluates vulnerability in graph-based applications.
- Motivation: Graph structure supports important applications, but weak interpretability and robustness create risks in financial and security settings.Graph-sensitive models can use relationship patterns for prediction while exposing models to manipulation.
- Motivation: Graph attacks remain underexplored compared with adversarial attacks on images and text, despite potentially severe consequences from cheap structural manipulation.The paper motivates this gap with fraud scenarios involving altered social or transaction relationships.
- Evaluation: The experiments target graph neural networks in node- and graph-classification tasks and examine their vulnerability to structural adversarial examples.The paper also reports using attacks to inspect learned classifiers and discusses defense methods.
- Approach: The paper proposes RL-S2V, which sequentially adds or drops edges using only prediction feedback and a hierarchical Q-function to make quadratic actions tractable.The learned policy can also propose attacks for new instances without access to the classifier.
- Attack settings: The study considers white-box, practical black-box, and restricted black-box attacks, with practical black-box access split by confidence availability.Prediction labels alone define PBA-D, while prediction confidence defines PBA-C; WBA exposes gradients and other classifier information.
2. Background
The background defines inductive graph classification and transductive node classification, then describes GNN representations built through neighborhood propagation and graph-level pooling.
- Graph data: Graph data are modeled as graphs Gi = (Vi, Ei), with optional node or edge features and, in this paper, primarily undirected structure.The dataset notation associates graph instances with target labels or target nodes depending on the task.
- Inductive Graph Classification: Inductive graph classification assigns each graph a label and evaluates test graphs unseen during training.The classifier maps graph instances to categories and is optimized using cross-entropy by default.
- Transductive Node Classification: Transductive node classification assigns labels to target nodes within one observed graph, while test-node labels remain unobserved during training.The classifier maps nodes in the shared graph G0 to categories.
- Graph Neural Networks: GNNs iteratively compute node representations from neighborhood information, using a fixed propagation depth or convergence-based updates.The initial node embedding is set to zero, and the resulting node embeddings can be aggregated by global pooling for graph-level prediction.
3. Graph adversarial attack
The paper formulates graph adversarial attacks as constrained edge modifications and develops reinforcement-learning and alternative attack methods for different classifier-access settings. RL-S2V learns a transferable Q-function for sequential edge attacks, while gradient and genetic methods support settings with richer information but face scalability or access constraints.
- 3. Graph adversarial attack: The attacker modifies a graph by adding or deleting edges while preserving classification semantics or limiting changes to a local neighborhood.The small-modification constraint permits at most m edge changes within a b-hop neighborhood when explicit semantics are unavailable.
- 3.1. Attacking as hierarchical reinforcement learning: The attack procedure is modeled as a finite-horizon MDP whose state is the partially modified graph, action is an edge operation, and reward arrives primarily at termination.Q-learning is used because the problem is discrete and finite-horizon; confidence-based attacks can use the target loss as reward.
- 3.1. Attacking as hierarchical reinforcement learning: Hierarchical action decomposition reduces each edge choice from O(|V|^2) possibilities to O(|V|) complexity by selecting the two endpoints sequentially.The decomposition retains the original optimality structure while representing an edge action through two endpoint decisions.
- 3.1.1. PARAMETERIZATION OF Q∗: RL-S2V parameterizes a shared Q-function that generalizes across the MDPs induced by different dataset samples and supports black-box attack and transfer.The method learns one Q-function rather than a separate function for each sample-specific MDP.
- 3.2.2. GRADIENT BASED WHITE BOX ATTACK: GradArgmax obtains edge-level gradients through binary adjacency coefficients and greedily adds or deletes the edges with the most attack-relevant gradient values.Because it evaluates all node pairs, the white-box method costs at least O(|V|^2) before gradient back-propagation and does not scale without approximation.
- 3.2. Other attacking methods: GeneticAlg evolves candidate graph modifications through population-based operations and uses the target loss as fitness, but is restricted to prediction-confidence access.Its fitness evaluation requires executing the target model, with computation cost O(|V|+|E|).
4. Experiment
Experiments evaluate graph-structure attacks against graph- and node-classification models under several access settings, using synthetic and real-world datasets. The attacks reduce classifier performance, transfer to unseen graphs, expose model sensitivities, and provide modest robustness gains through random edge dropping.
- Experimental setup: The experiments evaluate attack methods on synthetic graph classification and real-world node classification tasks, including structure2vec and GCN targets.Graph-level experiments use synthetic data; node-level experiments use Citeseer, Cora, Pubmed, and Finance datasets.
- Graph-level attack: In practical black-box graph classification, GeneticAlg and RL-S2V reduce structure2vec accuracy to 40% ∼60%.The target model initially achieves very high accuracy on distinguishing the number of connected components.
- Graph-level attack: RL-S2V transfers its learned attack policy to unseen graph-classification samples without access to the target model.The result suggests that the target classifier makes some form of consistent mistakes.
- Node-level attack: Deleting a single edge produces attack rates of about 10% on small node-classification graphs and 4% on Finance.With two-edge modifications, classifier accuracy falls to 60% or lower, although larger changes may violate small-modification constraints.
- Node-level attack: GradArgmax performs better for node-level than graph-level attacks because gradients with respect to the adjacency matrix are not averaged.RL-S2V also learns an attack policy that generalizes to unseen node-classification samples in the restrict black-box setting.
- Inspection of adversarial samples: Visualization reveals graph-level sensitivity to modifications spanning four hops and node-level cases where GCN is over-sensitive or makes a reasonable prediction.The graph-level target is structure2vec with K =4, while the node-level target is GCN with K =2.
- Defense against attacks: Random edge dropping during training decreases attack rates by about 1% while leaving target-model accuracy similar.The authors describe the improvement as modest but evidence of effectiveness for this cheap adversarial-training method.
5. Related work
Prior adversarial-attack research has focused on continuous and discrete spaces, including gradient-based white-box attacks and substitute models for limited-access settings.
- Recent adversarial attacks target deep learning models in continuous and discrete spaces.
- White-box methods use target-model gradients, including box-constrained L-BFGS, Fast Gradient Sign, and DeepFool.
- When the target model is inaccessible, substitute models can support adversarial attacks.
6. Conclusion
The paper studies adversarial attacks on graph-structured data, proposes three methods for different access settings, and evaluates GNN vulnerability and diagnostic use.
- The paper proposes RL-S2V, GradArgmax, and GeneticAlg for three different adversarial-attack settings.
- Experiments show that a family of GNN models is vulnerable to graph-structure attacks.
- Attack-sample visualization can help inspect the target classifier.
- The paper discusses defense methods through experiments and identifies more effective defense algorithms as future work.