arXiv preprint ·
A Separation Principle for Adversarial Attacks and Defense of Graph Neural Networks
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Jailbreak Connectivity: Towards Diverse, Transferable, and Universal Multimodal Large Language Model Jailbreak
PhysicsNeMo-Mesh: GPU-Native Meshes and Simulation Cases for Physics AI
Nemotron 3.5 Super and Lightning: Open, Efficient Mixture-of-Experts Hybrid Mamba-Transformer Models for Agentic AI
Tactus: Tactile & Pose Sensing Glove for Natural Dexterity Data Collection
Evaluating Causal Reasoning in LLMs: A Case Study in the Challenges of Procedural Generation
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.