Generating adversarial examples with graph neural networks

Florian Jaeckle, M. Pawan Kumar

Abstract

Recent years have witnessed the deployment of adversarial attacks to evaluate the robustness of Neural Networks. Past work in this field has relied on traditional optimization algorithms that ignore the specific internal structure of the target network. We present AdvGNN, a novel adversarial attack framework that uses Graph Neural Networks (GNNs) to learn the most efficient way to "break" a target neural network. By mimicking the target's architecture, AdvGNN finds adversarial perturbations significantly faster than state-of-the-art optimization methods like PGD and C&W, while demonstrating an impressive ability to generalize to unseen network architectures.

Introduction

Neural networks are notoriously fragile; tiny, imperceptible changes to an input, known as adversarial examples, can cause them to fail spectacularly. To build more robust models, researchers require strong "attacks" to test them. Currently, attacks fall into two categories: optimization-based methods (e.g., PGD), which are effective but slow because they ignore the specific internal structure of the network, and generative-based methods, which are fast but often fail on "hard" cases because they don't iterate or adapt to specific inputs. AdvGNN bridges this gap by creating an attacker that is both learned and iterative, using the target network's own structure as a roadmap.

Methodology

The core innovation of AdvGNN is treating the target network as a graph rather than a black box.

  • Isomorphic Architecture: The GNN is built as a mirror image of the target network. Every neuron in the target becomes a node in the GNN, and every weight becomes an edge.
  • Feature Engineering: Each node in the GNN is initialized with features describing its current state, including its gradient, upper/lower activation bounds, and information from standard robustness relaxations.
  • Forward-Backward Message Passing: To find an attack direction, the GNN performs passes where nodes exchange information with their neighbors, allowing it to "understand" how a change in one layer affects the rest of the network.
  • Learned Update Rule: Unlike standard PGD, which moves strictly in the direction of the gradient, AdvGNN learns a sophisticated "direction of movement" that maximizes adversarial loss more efficiently.
  • Training with a Horizon: The GNN is trained using a loss function with a decay factor, encouraging the model to find an adversarial example in as few steps as possible.

Experimental Setup and Datasets

The framework was evaluated using the CIFAR-10 dataset. To address the limitations of standard benchmarks—which are often either too easy or impossible—the authors introduced a new "Challenging Dataset" consisting of three models: Base, Wide, and Deep. They used expensive binary searches to find the exact minimum perturbation needed for each image, ensuring every test case is solvable but requires high efficiency to succeed within a time limit.

Attack success rate on 'Easy Properties' for the Base model, demonstrating rapid convergence for simpler cases.

Key Results

AdvGNN demonstrates significant performance gains over traditional optimization methods:

  • Massive Speedups: On the "Base" model, AdvGNN reduced the average time to find an adversarial example by over 65% compared to PGD and MI-FGSM+.
  • Higher Success Rates: Under a strict 100-second timeout, AdvGNN solved significantly more cases. On the Base model, AdvGNN timed out on only 9.4% of cases, while PGD timed out on 83%.
  • Robust Generalization: When attacking the "Wide" model (which it was never trained on), AdvGNN remained the most efficient method, outperforming the best baseline by 20% in speed.
Performance comparison of AdvGNN against baselines across Base, Wide, and Deep models over a 100-second computation window.

Discussion and Future Work

AdvGNN's success stems from using structure as an inductive bias. By making the GNN isomorphic to the target network, the model doesn't have to learn how a neural network works from scratch. While AdvGNN generalizes well to wider networks, attacking significantly deeper networks required approximately 15 minutes of fine-tuning to maintain peak performance.

Currently, the method requires white-box access to the target network's weights and architecture. Future research could explore using AdvGNN to accelerate adversarial training or integrating it into formal verification tools to prove network safety more rapidly.

Summary updated

Abstract

Recent years have witnessed the deployment of adversarial attacks to evaluate the robustness of Neural Networks. Past work in this field has relied on traditional optimization algorithms that ignor...
BibTeX
@inproceedings{jaeckle2021generating,
  author = {Florian Jaeckle and M. Pawan Kumar},
  title = {{Generating adversarial examples with graph neural networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=PphREvhddGP},
}
Figure