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 inherent structure of the problem and data, or generative methods that rely purely on learning and often fail to generate adversarial examples where they are hard to find. To alleviate these deficiencies, we propose a novel attack based on a graph neural network (GNN) that takes advantage of the strengths of both approaches; we call it AdvGNN. Our GNN architecture closely resembles the network we wish to attack. During inference, we perform forward-backward passes through the GNN layers to guide an iterative procedure towards adversarial examples. During training, its parameters are estimated via a loss function that encourages the efficient computation of adversarial examples over a time horizon. We show that our method beats state-of-the-art adversarial attacks, including PGD-attack, MI-FGSM, and Carlini and Wagner attack, reducing the time required to generate adversarial examples with small perturbation norms by over 65%. Moreover, AdvGNN achieves good generalization performance on unseen networks. Finally, we provide a new challenging dataset specifically designed to allow for a more illustrative comparison of adversarial attacks.

Introduction

Since the discovery that Neural Networks (NNs) are vulnerable to "adversarial examples"—inputs with tiny, imperceptible perturbations that trigger misclassification—researchers have been in an arms race to develop stronger attacks and better defenses.

Existing attacks generally fall into two camps:

  1. Optimization-based attacks (e.g., PGD, C&W): These treat the network as a mathematical function and use iterative steps (like gradient descent) to find perturbations. They are highly effective but slow and "structure-agnostic," meaning they do not exploit the specific internal architecture of the network.
  2. Generative/Learning-based attacks: These train a second model to "guess" the perturbation. They are fast but often fail to find "hard" adversarial examples because they lack the refinement of iterative optimization.

AdvGNN addresses this gap by creating an attack that is both fast and precise, "learning" how to navigate the specific internal structure of the target network.

Methodology: AdvGNN

AdvGNN treats the target neural network as a graph, leveraging its topology to guide the attack process.

  • Isomorphic Architecture: The AdvGNN architecture is built to be isomorphic to the target network—every neuron in the target model becomes a node in the GNN, and every weight becomes an edge. This allows the GNN to "understand" how changes in early layers propagate to the final output.
  • Rich Node Features: AdvGNN nodes are initialized with features including the current gradient, intermediate activation bounds (derived from interval bound propagation), and information from Lagrangian relaxations of the loss function.
  • Learned Ascent Directions: During an attack, the GNN performs internal forward and backward passes to propose a "direction of movement" that is more informed than a simple gradient step.
  • Horizon-based Training: The GNN is trained using a loss function with a decay factor, encouraging it to find successful adversarial perturbations in as few iterations as possible.

Experimental Evaluation

The method was evaluated using CIFAR-10 and a new challenging dataset specifically designed for this study. This dataset includes three model types—Base, Wide, and Deep—where adversarial examples are mathematically guaranteed to exist but are extremely difficult to find. The researchers also tested AdvGNN against adversarially trained models hardened using Madry’s robust training method.

Key Results

AdvGNN consistently outperformed state-of-the-art baselines (PGD, MI-FGSM+, and C&W) across all tested models.

Performance of AdvGNN vs. baselines on the challenging dataset across Base, Wide, and Deep models.

As shown in the results for the challenging dataset, AdvGNN achieves a significantly higher success rate within a shorter computation time. On the "Base" model, AdvGNN found adversarial examples in an average of 13.5 seconds, compared to 87.4 seconds for PGD. In scenarios where PGD timed out on 83% of properties, AdvGNN only timed out on 9.4%.

Performance of AdvGNN vs. baselines on 'Easy Properties' across Base, Wide, and Deep models.

Even on "Easy Properties," AdvGNN reaches a near 100% success rate almost instantly, demonstrating its efficiency across varying difficulty levels. Overall, the method reduced the time required to find adversarial examples with small perturbation norms by over 65%.

Discussion and Conclusion

A key insight of this work is that the internal structure of a target network provides a valuable signal for generating attacks. By mirroring this topology, AdvGNN can exploit ReLU-based architectures effectively. Furthermore, the model demonstrates impressive generalization: an AdvGNN trained on a small "Base" model can effectively attack a "Wide" model it has never seen before.

While the computation of complex node features adds some overhead, the performance gains are substantial. Future work includes using AdvGNN to generate harder examples for adversarial training and integrating it into formal verification frameworks to accelerate safety proofs.

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 ignore the inherent structure of the problem and data, or generative methods that rely purely on learning and often fail to generate adversarial examples where they are hard to find. To alleviate these deficiencies, we propose a novel attack based on a graph neural network (GNN) that takes advantage of the strengths of both approaches; we call it AdvGNN. Our GNN architecture closely resembles the network we wish to attack. During inference, we perform forward-backward passes through the GNN layers to guide an iterative procedure towards adversarial examples. During training, its parameters are estimated via a loss function that encourages the efficient computation of adversarial examples over a time horizon. We show that our method beats state-of-the-art adversarial attacks, including PGD-attack, MI-FGSM, and Carlini and Wagner attack, reducing the time required to generate adversarial examples with small perturbation norms by over 65\%. Moreover, AdvGNN achieves good generalization performance on unseen networks. Finally, we provide a new challenging dataset specifically designed to allow for a more illustrative comparison of adversarial attacks.
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