aiqbench analysis
The paper argues that graph neural network vulnerability to feature perturbations depends mainly on graph structure, with node degree as the key quantity, rather than only on the learned weights. Its SepAttack method is gradient-free, comes with analytical guarantees, and reports large speedups over Nettack and IG-Attack, but these results are on specific benchmarks and need independent replication. For ML practitioners, the more reusable idea is the separation of graph-dependent and weight-dependent components for both attacks and adversarial training.
A Separation Principle for Adversarial Attacks and Defense of Graph Neural Networks
arXiv:2610.38127v1 Announce Type: new Abstract: Adversarial attacks on graph neural networks (GNNs) have been studied as a model-centric optimization problem driven by gradients, learned policies, or meta-learning, with the graph treated as a passive substrate. This view overlooks a defining feature of GNNs: their predictions are produced by structured message passing along the graph, so their adversarial vulnerabilities are encoded as much in the geometry of the graph as in the learned weights. We develop a structure-driven framework for feature attacks in which the attack is derived from the spectral properties of the normalized adjacency operator. Its central result is a separation principle: under a natural relaxation of the attack objective, the optimal feature perturbation is rank one and factorizes into a graph-dependent component (degree-proportional spatial allocation, depending only on the graph) and a weight-dependent component (top singular vector of the composed weights, depending only on the weights). Node degree thus emerges as the fundamental graph quantity governing adversarial vulnerability to feature perturbations. The resulting attack, which we call SepAttack, requires no gradient computation, carries analytical guarantees, achieves competitive or superior performance against established baselines such as Nettack and IG-Attack with up to ${\sim}70\times$ speedup in the targeted setting, and transfers near-perfectly across architectures on continuous-feature graphs because its graph-dependent component is architecture-invariant by construction. We further derive a separation-principle adversarial training procedure (SepAT) directly from the closed-form worst-case attack and report robustness gains on binary-feature benchmarks.
Abstract:Adversarial attacks on graph neural networks (GNNs) have been studied as a model-centric optimization problem driven by gradients, learned policies, or meta-learning, with the graph treated as a passive substrate. This view overlooks a defining feature of GNNs: their predictions are produced by structured message passing along the graph, so their adversarial vulnerabilities are encoded as much in the geometry of the graph as in the learned weights. We develop a structure-driven framework for feature attacks in which the attack is derived from the spectral properties of the normalized adjacency operator. Its central result is a separation principle: under a natural relaxation of the attack objective, the optimal feature perturbation is rank one and factorizes into a graph-dependent component (degree-proportional spatial allocation, depending only on the graph) and a weight-dependent component (top singular vector of the composed weights, depending only on the weights). Node degree thus emerges as the fundamental graph quantity governing adversarial vulnerability to feature perturbations. The resulting attack, which we call SepAttack, requires no gradient computation, carries analytical guarantees, achieves competitive or superior performance against established baselines such as Nettack and IG-Attack with up to ${\sim}70\times$ speedup in the targeted setting, and transfers near-perfectly across architectures on continuous-feature graphs because its graph-dependent component is architecture-invariant by construction. We further derive a separation-principle adversarial training procedure (SepAT) directly from the closed-form worst-case attack and report robustness gains on binary-feature benchmarks.
Machine Learning (cs.LG)
arXiv:2610.38127 [cs.LG]
(or arXiv:2610.38127v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.38127 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 326 words
Related coverage
Provable Adversarial Detection: Prime Quantization meets Gromov--Wasserstein
arXiv · Oct 21, 2026
Mutually Adversarial Self-Training with Evolving Data for Unified Multimodal Models
arXiv · Sep 30, 2026
When Helping Hurts and How to Fix It: Multi-Agent Debate for Data Cleaning
arXiv · Jun 3, 2026
Quantum Query Complexity and Span Programs from Pre-Geometry
arXiv · Oct 6, 2026