A Separation Principle for Adversarial Attacks and Defense of Graph Neural Networks
Authors: Farid Mafi, Saber Jafarpour, Mohammad Pirani
Organizations: University of Waterloo, Waterloo, ON, Canada · University of Colorado Boulder, Boulder, CO, USA · University of Ottawa, Ottawa, ON, Canada
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 ∼70× 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.
Figures & tables
Success Rate (%)
Method / Mode
Time
γ=1
γ=2
γ=3
γ=4
γ=5
Cora
SepAttack (our attack) / Direct
5 ms
13.0
17.5
20.0
22.0
23.0
SepAttack / Influence
6 ms
9.5
13.0
16.0
18.5
19.0
Nettack / Direct
352 ms
8.0
15.0
17.5
18.5
19.5
Nettack / Influence
407 ms
6.0
10.0
12.0
16.0
16.5
Table 1: Targeted feature attack comparison: overall success rate (%) on the preselected target set (40 correctly-classified test nodes per dataset), averaged over 5 seeds. γ : features perturbed per target. Bold: best per column within each dataset.
Dataset
Clean mis.
FGM
PGD-40
SepAttack
Texas
38.4
81.6 ± 22.3
82.7 ± 22.3
89.2 ± 0 2.7
Wisconsin
47.1
64.7 ± 12.8
65.9 ± 10.2
73.7 ± 0 2.6
Cornell
59.5
67.6 ± 0 2.7
65.4 ± 0 3.5
79.5 ± 0 6.5
Table 2: Heterophilous benchmarks. Misclassification rate (%) at full attack budget δ=10 on three WebKB heterophilous graphs ( Pei et al., 2020 ) . Mean ± std over 5 seeds; standard 60/20/20 split (index 0) ( Zhu et al., 2020 ; Chien et al., 2021 ) (different from the 10/10/80 Nettack protocol of Section 6 ). PGD-40 follows the Madry ( Madry et al., 2018 ) L2 convention (5 random restarts, α=2δ/T , normalized step); FGM is the L2 variant. The normalized-adjacency spectral radius is λ1≈2.23 on Wisconsin and λ1≈2.30 on Texas/Cornell, vs. λ1≈1.0 on the citation networks.
Figure 1: Cross-architecture transfer on continuous-feature graphs at δ=10 , 5 seeds. Bars: transfer ratio (%) = accuracy drop on target / drop on source GCN; dashed line = perfect transfer. GCN source omitted (trivially 100% ). Source drops (pp) used as denominators: Cora-ML: SepAttack=57.4, PGD=76.2, FGM=50.0; PubMed: SepAttack=43.7, PGD=64.1, FGM=47.8. All three attacks transfer within 6 pp of perfect efficiency, confirming the principle’s architecture-invariance prediction when w1 is broadly shared. Binary-feature case (where w1 is not shared): Table 6 .
Dataset
Clean (no def.)
Clean (SepAT)
Worst-case (no def.)
Worst-case (SepAT)
Avg. gain
Cora
82.7
82.2
16.0
41.3
+23.4 pp
CiteSeer
69.9
68.2
15.4
33.2
+15.1 pp
PubMed
78.1
75.9
40.6
42.6
+1.6 pp
Table 3: SepAT (separation-principle adversarial training): worst-case accuracy (%) under best-sign SepAttack at δ=10 . Clean (no def.) : test accuracy of the standard GCN without attack; Clean (SepAT) : test accuracy of the SepAT-regularized GCN without attack; Worst-case : 100−max(err(+d~,w1),err(−d~,w1)) at δ=10 . Avg. gain : mean reduction in worst-case error across δ∈{2,4,6,8,10} , in percentage points. SepAT uses the bilateral output-stability regularizer of Section 5 ( α=0.25 , δmax=10 , Tw=50 , λ=5×10−4 ); Planetoid split Kipf (2016) , 2-layer GCN with 16 hidden units; see Appendix E.2 .
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Method
Year
Strategy
Knowledge
Perturbation
Stage
Theoretical Basis
Nettack
2018
Gradient
Grey-box
Struct+Feat
Both
Surrogate scoring
FGA
2018
Gradient
White-box
Structure
Evasion
FGSM adaptation
RL-S2V
2018
RL
Black-box
Structure
Both
Learned policy
PGD Attack
2019
Gradient
White-box
Structure
Both
Continuous relaxation
Metattack
2019
Meta-learning
Grey-box
Structure
Poisoning
Meta-gradients
TDGIA
2021
Optimization
Grey-box
Injection
Evasion
Smooth optimization
Appendix
Table 4: Comparison of adversarial attack methods on GNNs for node classification (Time Ascending). Full references in Section 2 .
Figure 2: SepAttack on the nonlinear ReLU-GCN, 5 seeds. (a) Full access: SepAttack (black) achieves the highest misclassification rate on Cora, CiteSeer, and Cora-ML at every budget; on PubMed, Unif-Unif overtakes at the largest budget. (b) Restricted access ( ∣A∣=100 , attacker set drawn uniformly at random once per seed and matched across methods): the Proposition 1 heuristic SepAttack∣A dominates feasible-set peers. Dashed grey: clean misclassification.
Dataset
Features
Clean
Random
Graph-only
Weight-only
Combined
Cora
binary
82.6
82.6
82.6
81.1
65.4
CiteSeer
binary
74.6
74.6
74.6
72.2
62.1
Cora-ML
continuous
85.5
85.4
85.4
74.3
28.1
PubMed
continuous
86.1
86.1
86.0
75.0
42.4
Appendix
Table 5: Separation-principle ablation at δ=10 (full access): accuracy (%) under each attack component, averaged over 5 seeds. Random : urand⋅wrandT , both unit vectors drawn iid from N(0,I) and renormalized (floor baseline). Graph-only : ubest⋅wrandT (optimal spatial allocation, random weight direction). Weight-only : urand⋅w1T (random spatial allocation, optimal weight direction). Combined : ubest⋅w1T (Theorem 1 optimum with best-sign selection of ±d~/∥d~∥ ). All variants share the same Frobenius budget ∥ΔX∥F=δ . Random vectors are seeded per-seed ( seed+1000 for wrand , seed+2000 for urand ).
Transfer ratio (%) to target architecture
Source
Dataset
Attack
GAT
SAGE
APPNP
JKNet
drop (pp)
Cora
SepAttack (our attack)
50% ± 9
27% ± 13
52% ± 15
73% ± 38
17.2 ± 2.8
PGD-40
79% ± 5
75% ± 9
76% ± 7
92% ± 4
23.0 ± 2.0
FGM
77% ± 6
70% ± 9
70% ± 6
91% ± 2
16.0 ± 1.4
CiteSeer
SepAttack
22% ± 12
31% ± 12
20% ± 10
43% ± 20
12.5 ± 2.5
PGD-40
66% ± 6
77% ± 6
64% ± 3
88% ± 10
24.1 ± 1.7
Appendix
Table 6: Cross-architecture transfer on binary-feature citation networks at δ=10 , averaged over 5 seeds. Cells report transfer ratio ± std (accuracy drop on target / drop on source GCN, %). Last column: accuracy drop on the source GCN itself (pp), the denominator used for the ratios.
Graph Neural Networks (GNNs) are vulnerable to adversarial attacks, which inherently invert connectivity patterns by introducing disassortative edges in assortative graphs and assortative edges in disassortative graphs. This structural inversion creates structure-feature mismatches that disrupt neighborhood aggregation across different graph types. However, we find that existing defenses are limited, as they either treat neighborhoods as monolithic under fixed assortativity assumptions or rely on standard softmax classifiers that fail to account for perturbation-induced representation shifts. To further exploit this observation, we adopt a robustness perspective that jointly disentangles node representations and decision spaces, isolating perturbation effects while enforcing well-separated decision regions. Based on this principle, we propose Graph Joint Disentanglement Network (GJDNet), a unified framework for robust node classification across diverse graph assortativity regimes. GJDNet enhances robustness at both representation and decision levels: it employs feature-driven soft structural disentanglement with skewness-aware neighbor filtering to suppress perturbation-induced structure-feature mismatches, and introduces a Spherical Decision Boundary (SDB) to promote intra-class compactness and inter-class separation in the embedding space, thereby stabilizing decision boundaries under perturbations. Theoretical analysis provides insights into the effectiveness of the proposed disentangled representation and decision mechanisms, while extensive experiments demonstrate that GJDNet consistently achieves strong robustness across graphs with different connectivity regimes.
Canyixing Cui, Tao Wu, Xingping Xian +3
School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, China · School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications, Chongqing, China · Computational Communication Research Center, Beijing Normal University, Zhuhai, China +2
Graph Neural Networks (GNNs) have achieved remarkable success across diverse applications, yet they remain highly vulnerable to adversarial attacks that maliciously perturb graph structure. Existing defenses often lack rigorous theoretical grounding, rely on attack-specific heuristics, or require costly retraining procedures such as adversarial training. To address these limitations, we propose Kernel-Complexity Edge Sanitization (KCES), a training-free and model-agnostic framework for defending against structural attacks. KCES is built upon Graph Kernel Complexity (GKC), a principled metric derived from the graph Gram matrix that appears in a generalization upper bound on the GNN test error. From this bound, we define an edge-specific KC score that quantifies each edge's structural influence via its induced change in GKC. KCES then identifies and prunes high-KC edges, which are empirically enriched with adversarial perturbations under structural attacks, to mitigate their harmful impact. Computationally efficient and scalable, KCES operates as a lightweight preprocessing step without retraining and can be seamlessly integrated with existing defenses. Extensive experiments demonstrate that KCES consistently outperforms representative robust baselines across diverse attack settings and scales effectively to large graphs. Supported by theoretical analysis and extensive empirical validation, KCES provides a principled and efficient framework for securing GNNs. Our code is available at https://github.com/karpning/KCScore.
Yaning Jia, Shenyang Deng, Yaoqing Yang +3
Department of Computer Science Dartmouth College Hanover, New Hampshire, USA
Graph adversarial attacks are usually produced from the two perspectives of topology/structure and node feature, both of them represent the paramount characteristics learned by today's deep learning models. Although some defense countermeasures are proposed at present, they fails to disclose the intrinsic reasons why these two aspects necessitate and how they are adequately fused to co-learn the graph representation. Towards this question, we in this paper propose an adversarial defense approach through locating the graph's critical state of adversarial resilience, resorting to the equilibrium-point theory in the discipline of complex dynamic system (CDS). In brief, our work has three novelties: i) Adversarial-Attack Modeling, i.e. map a graph regime into CDS, and use the oscillation of dynamic system to model the behavior of adversarial perturbation; ii) 2D Topology-Feature-Entangled Function Design for Perturbed Graph, i.e. project graph topology and node feature as two characteristic spaces, and define two-dimensional entangled perturbation functions to represent the dynamic variance under adversarial attacks; and iii) Location of Critical State of Adversarial Resilience, i.e. utilize the equilibrium-point theory to locate the graph's critical state of attack resilience resorting to the perturbation-reflected 2D function. Finally, multi-facet experiments on five commonly-used realistic datasets validate the effectiveness of our proposed approach, and the results show our approach can significantly outperform the state-of-the-art baselines under four representative graph adversarial attacks.
Xinxin Fan, Wenxiong Chen, Quanliang Jing +4
State Key Laboratory of AI Safety, Institute of Computing Technology, Chinese Academy of Sciences · University of Chinese Academy of Sciences · Dalian University of Technology +1