ML Security PapersPEANUT: Perturbations by Eigenvalue Alignment for Attacking GNNs Under Topology-Driven Message Passing
Published on arXiv
2603.26136
Input Manipulation Attack
OWASP ML Top 10 — ML01
Key Finding
Demonstrates significant GNN performance degradation through virtual node injection with zero features, highlighting the critical role of topology-driven connectivity in graph adversarial attacks
PEANUT
Novel technique introduced
Graph Neural Networks (GNNs) have achieved remarkable performance on tasks involving relational data. However, small perturbations to the graph structure can significantly alter GNN outputs, raising concerns about their robustness in real-world deployments. In this work, we explore the core vulnerability of GNNs which explicitly consume graph topology in the form of the adjacency matrix or Laplacian as a means for message passing, and propose PEANUT, a simple, gradient-free, restricted black-box attack that injects virtual nodes to capitalize on this vulnerability. PEANUT is a injection based attack, which is widely considered to be more practical and realistic scenario than graph modification attacks, where the attacker is able to modify the original graph structure directly. Our method works at the inference phase, making it an evasion attack, and is applicable almost immediately, since it does not involve lengthy iterative optimizations or parameter learning, which add computational and time overhead, or training surrogate models, which are susceptible to failure due to differences in model priors and generalization capabilities. PEANUT also does not require any features on the injected node and consequently demonstrates that GNN performance can be significantly deteriorated even with injected nodes with zeros for features, highlighting the significance of effectively designed connectivity in such attacks. Extensive experiments on real-world datasets across three graph tasks demonstrate the effectiveness of our attack despite its simplicity.
Key Contributions
- Gradient-free, black-box node injection attack requiring no node features (zero-feature injection)
- Eigenvalue alignment strategy exploiting GNNs' explicit use of adjacency/Laplacian matrices for message passing
- Evasion attack applicable at inference without iterative optimization or surrogate model training
🛡️ Threat Analysis
PEANUT is an evasion attack that manipulates GNN outputs at inference time by injecting virtual nodes with strategically crafted connectivity patterns. This is a structural adversarial attack causing misclassification through graph topology perturbation rather than feature perturbation, but fundamentally targets the same goal as traditional adversarial examples: causing incorrect model outputs through carefully crafted inputs.