Source-linked AI summary
Adversarial Attacks on Neural Networks for Graph Data
Daniel Zügner, Amir Akbarnejad, Stephan Günnemann
TL;DR
The paper addresses the lack of evidence on whether graph deep-learning models resist adversarial attacks, a question important in adversarial domains. It develops attacks on attributed-graph features and structure, including poisoning attacks, using Nettack while preserving selected data characteristics. Experiments show that few perturbations significantly reduce classification performance, with transfer across models and success under partial knowledge.
Problem
The robustness of deep learning models for graphs to adversarial perturbations had not been studied, despite adversaries being common in graph-based domains.
Method
The paper attacks attributed graphs by modifying node features and structure for test-time and poisoning settings, using Nettack with preserved degree and feature-co-occurrence characteristics.
Results
Classification performance is consistently reduced by few perturbations, with attacks transferring across established models and succeeding when only partial graph knowledge is available.
Takeaways & Limitations
Adversarial attacks pose a demonstrated vulnerability for graph-based node classification and motivate further study of robust graph-learning models.
Takeaways & Limitations
The paper focuses on node classification and leaves robustification and tasks beyond node classification for future work.
Abstract
from arXiv · showhide
Deep learning models for graphs have achieved strong performance for the task of node classification. Despite their proliferation, currently there is no study of their robustness to adversarial attacks. Yet, in domains where they are likely to be used, e.g. the web, adversaries are common. Can deep learning models for graphs be easily fooled? In this work, we introduce the first study of adversarial attacks on attributed graphs, specifically focusing on models exploiting ideas of graph convolutions. In addition to attacks at test time, we tackle the more challenging class of poisoning/causative attacks, which focus on the training phase of a machine learning model. We generate adversarial perturbations targeting the node's features and the graph structure, thus, taking the dependencies between instances in account. Moreover, we ensure that the perturbations remain unnoticeable by preserving important data characteristics. To cope with the underlying discrete domain we propose an efficient algorithm Nettack exploiting incremental computations. Our experimental study shows that accuracy of node classification significantly drops even when performing only few perturbations. Even more, our attacks are transferable: the learned attacks generalize to other state-of-the-art node classification models and unsupervised approaches, and likewise are successful even when only limited knowledge about the graph is given.
1 INTRODUCTION
Graph neural networks use relational information for node classification, but their adversarial robustness had not been studied despite realistic opportunities for graph manipulation. The paper introduces attacks on node features and graph structure, including poisoning attacks, and reports substantial degradation from few, transferable perturbations.
- Graph node classification supports applications involving social, biological, commercial, and document networks.
- Graph convolutional models exploit edges and network effects such as homophily rather than treating nodes as independent instances.
- Adversarial perturbations in graph learning had not been studied, despite attackers being able to inject false or manipulated data in domains such as the web.
- Graph attacks can alter node features or structure and can distinguish manipulable attacker nodes from nodes targeted for misclassification.
- Nettack preserves degree distributions and feature co-occurrences while using linearization and incremental computations for efficient discrete attacks.
- Classification performance is consistently reduced with few changes, including under poisoning attacks, transfer to other models, and partial graph knowledge.
2 PRELIMINARIES
The paper studies semi-supervised, transductive node classification on one attributed graph with binary node features and graph-convolution layers. Predictions are coupled through neighboring nodes, while labels are available for only a subset.
- The input is a single attributed graph G=(A,X), with binary adjacency structure and binary node features.
- Node classification learns a function mapping every node to one class using labels from a subset of nodes.
- The setting is transductive because predictions concern known test nodes within the same graph used during training.
- Graph convolution layers recursively combine neighboring representations through the normalized adjacency matrix, coupling all instances.
- The model uses node features as the first-layer input and learns parameters semi-supervisedly by minimizing cross-entropy on labeled nodes.
3 RELATED WORK
Prior adversarial-learning research largely assumed independent instances and focused more on evasion than poisoning attacks. Graph-specific adversarial analysis remained sparse, while discrete graph data also challenged gradient-based perturbation methods.
- Deep Learning for Graphs: Deep learning for graphs includes node-embedding methods and graph-specific architectures; this paper focuses on the latter and tests transfer to node embeddings.
- Adversarial Attacks: Earlier adversarial examples research showed sensitivity to small perturbations and transferability across models, but assumed independent data instances.
- Attack Taxonomy: Poisoning attacks modify training data and are harder than evasion attacks because subsequent model learning must also be considered.
- Generating Adversarial Perturbations: Gradient-guided perturbation methods are suboptimal for discrete data because gradients are undefined.
- Scope: Robustification methods are outside this paper’s scope and are not discussed.
- Adversarial Attacks when Learning with Graphs: Existing graph-learning studies were almost nonexistent and generally examined injected noise or robustness rather than principled attack generation.
4 ATTACK MODEL
The attack model seeks small, targeted changes to node features or graph structure that alter a target node’s classification while preserving characteristics that make perturbations difficult to notice.
- The objective is to perturb G^(0)=(A^(0),X^(0)) into G′=(A′,X′) so classification performance drops through structure or feature attacks.
- Target vs. Attackers: Attacks target a node v_0, whose prediction can be changed by manipulating other attacker nodes because graph data are non-i.i.d.
- Target vs. Attackers: An influencer attack leaves v_0 unchanged and alters it indirectly, whereas a direct attack uses A={v_0}.
- A modification budget Δ limits the number of permitted graph changes.
- The bi-level formulation optimizes a perturbed graph using parameters retrained on that graph; an evasion variant keeps parameters learned from the original graph fixed.
- Unnoticeable Perturbations: Unnoticeability is enforced by preserving graph degree distributions and feature co-occurrence patterns rather than relying only on Δ.
- Unnoticeable Perturbations: The degree constraint compares original and perturbed degree distributions using a likelihood-ratio test for power-law distributions.
- Unnoticeable Perturbations: Feature additions are accepted when a one-step random walk from the node’s original features reaches the added feature with sufficiently high probability.
5 GENERATING ADVERSARIAL GRAPHS
Nettack makes discrete graph attacks tractable by attacking a linearized surrogate model and greedily selecting high-scoring, constraint-compliant feature or edge changes with incremental updates.
- Because discrete bi-level optimization is difficult, the method attacks a surrogate model first and then trains the final model on the attacked graph.
- Surrogate Model: Linearizing graph convolutions reduces the model to a form whose log-probabilities are represented by ẐA^2XW.
- Surrogate Model: The surrogate loss maximizes the log-probability difference between the strongest competing class and the original class c_old for target v_0.
- Approximate Solution: Nettack greedily evaluates allowable edge and feature changes, selects the change with the highest score, updates the graph, and repeats until the budget Δ is exceeded.
- Structural Attacks: For structural attacks, the two-hop receptive field makes most entries irrelevant and enables sparse incremental updates instead of recomputing from scratch.
- Feature Attacks: Feature attacks exploit linearity in X, selecting allowable entries with the largest gradient magnitude and computing each feature score in constant time.
- Constraint Checking: Constraint sets for allowable changes can be precomputed, while degree-distribution validity requires dynamic incremental updates because degrees change after each edge perturbation.
6 EXPERIMENTS
Experiments show that Nettack can substantially damage node classification with few, constrained perturbations, including poisoning settings, while attacks transfer across models and remain effective with partial graph knowledge.
- Attacks on the surrogate model: Structure perturbations change surrogate loss more strongly than feature-only perturbations.The experiments compare Nettack with variants manipulating only features or only graph structure.
- Attacks on the surrogate model: Direct attacks require fewer perturbations than influencer attacks, although both remain feasible under the proposed constraints.The constraints preserve graph and feature characteristics while still allowing successful, less noticeable attacks.
- Attacks on the surrogate model: Attacking features and structure simultaneously is powerful, and the constraints produce more realistic perturbations without hindering the attack.Unconstrained attacks can create conspicuous degree distributions or unlikely feature changes.
- Attacks on the surrogate model: Nettack scales linearly with the number of graph-structure perturbations and influencer nodes considered.The reported runtime uses sequential candidate-edge processing, which the authors note can be parallelized.
- Transferability of attacks: Direct attacks remain highly effective in poisoning settings, where the model is retrained after perturbation; influencer attacks are harder but still work.The poisoning results motivate reporting poisoning experiments in subsequent comparisons.
- Transferability of attacks: Nettack perturbations transfer to GCN, CLN, and DeepWalk across evaluated datasets, outperforming Rnd and FGSM in the direct-attack setting.DeepWalk receives structural attacks because it handles unattributed graphs; all reported comparisons use poisoning attacks.
- Transferability of attacks: FGSM performs worse than Nettack because gradients poorly approximate loss changes in the discrete graph domain.The authors emphasize Nettack’s ability to compute loss changes precisely and efficiently.
- Transferability of attacks: With only 10% of the graph observed, direct attacks can still significantly attack the model, while influencer attacks require 75% of the graph size to succeed.Full graph knowledge requires the fewest perturbations, but the experiment indicates it is not necessary.
7 CONCLUSION
The work establishes adversarial attacks on attributed graphs for node classification and finds that these attacks remain effective under constrained knowledge and limited influencers. It also identifies robustness and tasks beyond node classification as directions for further study.
- The study introduces adversarial attacks on attributed graphs targeting node features and graph structure for graph-convolutional node classification.The approach includes direct and influencer attacks in a discrete relational domain.
- Preserving the graph’s degree distribution and feature co-occurrences keeps perturbations unnoticeable while enabling efficient discrete-domain attacks.
- Poisoning attacks successfully reduce classification performance even with partial graph knowledge or attacks restricted to a few influencers.
- The attacks generalize to other node classification models.
- Future work targets more robust graph-learning models and tasks beyond node classification.