A Separation Principle for Adversarial Attacks and Defense of Graph Neural Networks

Farid Mafi; Saber Jafarpour; Mohammad Pirani

cs.LGOct 28, 2026

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

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.

Figures & tables

Cora
		Success Rate (%)
Method / Mode	Time	$\gamma\!=\!1$	$\gamma\!=\!2$	$\gamma\!=\!3$	$\gamma\!=\!4$	$\gamma\!=\!5$
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.

\gamma

: features perturbed per target. Bold: best per column within each dataset.

Dataset	Clean mis.	FGM	PGD-40	SepAttack
Texas	38.4	81.6 $\pm$ 22.3	82.7 $\pm$ 22.3	89.2 $\pm$ 0 2.7
Wisconsin	47.1	64.7 $\pm$ 12.8	65.9 $\pm$ 10.2	73.7 $\pm$ 0 2.6
Cornell	59.5	67.6 $\pm$ 0 2.7	65.4 $\pm$ 0 3.5	79.5 $\pm$ 0 6.5

Table 2: Heterophilous benchmarks. Misclassification rate (%) at full attack budget

\delta{=}10

on three WebKB heterophilous graphs ( Pei et al., 2020 ) . Mean

\pm

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,

\alpha{=}2\delta/T

, normalized step); FGM is the L2 variant. The normalized-adjacency spectral radius is

\lambda_{1}{\approx}2.23

on Wisconsin and

\lambda_{1}{\approx}2.30

on Texas/Cornell, vs.

\lambda_{1}{\approx}1.0

on the citation networks.

Figure 1: Cross-architecture transfer on continuous-feature graphs at

\delta=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

\mathbf{w}_{1}

is broadly shared. Binary-feature case (where

\mathbf{w}_{1}

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

\delta=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(\mathrm{err}(+\sqrt{\tilde{d}},\mathbf{w}_{1}),\,\mathrm{err}(-\sqrt{\tilde{d}},\mathbf{w}_{1}))

\delta=10

. Avg. gain : mean reduction in worst-case error across

\delta\in\{2,4,6,8,10\}

, in percentage points. SepAT uses the bilateral output-stability regularizer of Section 5 (

\alpha{=}0.25

\delta_{\max}{=}10

T_{w}{=}50

\lambda{=}5\times 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 (

|\mathcal{A}|{=}100

, attacker set drawn uniformly at random once per seed and matched across methods): the Proposition 1 heuristic

\mathrm{SepAttack}|\mathcal{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

\delta=10

(full access): accuracy (%) under each attack component, averaged over 5 seeds. Random :

u_{\text{rand}}\cdot w_{\text{rand}}^{T}

, both unit vectors drawn iid from

\mathcal{N}(0,I)

and renormalized (floor baseline). Graph-only :

u_{\text{best}}\cdot w_{\text{rand}}^{T}

(optimal spatial allocation, random weight direction). Weight-only :

u_{\text{rand}}\cdot\mathbf{w}_{1}^{T}

(random spatial allocation, optimal weight direction). Combined :

u_{\text{best}}\cdot\mathbf{w}_{1}^{T}

(Theorem 1 optimum with best-sign selection of

\pm\sqrt{\tilde{d}}/\|\sqrt{\tilde{d}}\|

). All variants share the same Frobenius budget

\|\Delta\mathbf{X}\|_{F}=\delta

. Random vectors are seeded per-seed ( seed+1000 for

w_{\text{rand}}

, seed+2000 for

u_{\text{rand}}

		Transfer ratio (%) to target architecture				Source
Dataset	Attack	GAT	SAGE	APPNP	JKNet	drop (pp)
Cora	SepAttack (our attack)	50% $\pm$ 9	27% $\pm$ 13	52% $\pm$ 15	73% $\pm$ 38	17.2 $\pm$ 2.8
	PGD-40	79% $\pm$ 5	75% $\pm$ 9	76% $\pm$ 7	92% $\pm$ 4	23.0 $\pm$ 2.0
	FGM	77% $\pm$ 6	70% $\pm$ 9	70% $\pm$ 6	91% $\pm$ 2	16.0 $\pm$ 1.4
CiteSeer	SepAttack	22% $\pm$ 12	31% $\pm$ 12	20% $\pm$ 10	43% $\pm$ 20	12.5 $\pm$ 2.5
	PGD-40	66% $\pm$ 6	77% $\pm$ 6	64% $\pm$ 3	88% $\pm$ 10	24.1 $\pm$ 1.7

Appendix

Table 6: Cross-architecture transfer on binary-feature citation networks at

\delta=10

, averaged over 5 seeds. Cells report transfer ratio

\pm

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.

Adversarial Attacks

Adversarial attacks exploit crafted inputs, poisoned data, or system interactions to manipulate AI predictions, behavior, privacy, or reliability.

See all 451 papers

GJDNet: Robust Graph Neural Networks via Joint Disentangled Learning Against Adversarial Attacks
Jun 1, 2026Canyixing Cui, Tao Wu, Xingping Xian +3Disentangled Representation Learning Graph Neural Networks
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
Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks
Sep 9, 2026Yaning Jia, Shenyang Deng, Yaoqing Yang +3Graph Neural Networks Adversarial Attacks
Department of Computer Science Dartmouth College Hanover, New Hampshire, USA
TopFeaRe: Locating Critical State of Adversarial Resilience for Graphs Regarding Topology-Feature Entanglement
Apr 15, 2026Xinxin Fan, Wenxiong Chen, Quanliang Jing +4Adversarial Robustness Adversarial Attacks
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

Jun 1, 2026J/K move · Enter open · S save

GJDNet: Robust Graph Neural Networks via Joint Disentangled Learning Against Adversarial Attacks

Canyixing Cui, Tao Wu, Xingping Xian, Xiao-Ke Xu+2

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

Disentangled Representation Learning Graph Neural Networks Adversarial Robustness Node Classification

Open paper AskPDF arXiv

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.

Abstract

Adversarial Attacks

Explore similar work

GJDNet: Robust Graph Neural Networks via Joint Disentangled Learning Against Adversarial Attacks

Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks

TopFeaRe: Locating Critical State of Adversarial Resilience for Graphs Regarding Topology-Feature Entanglement