PEANUT: Perturbations by Eigenvector Alignment for Attacking Graph Neural Networks Under Topology-Driven Message Passing

Bhavya Kohli; Biplab Sikdar

cs.LGMar 27, 2026

PEANUT: Perturbations by Eigenvector Alignment for Attacking Graph Neural Networks Under Topology-Driven Message Passing

Authors: Bhavya Kohli, Biplab Sikdar

Organizations: National University of Singapore, Singapore

Abstract

Message Passing Neural Networks (MPNNs) have achieved strong performance on tasks involving relational data. However, small perturbations to graph structure can significantly alter their outputs, raising concerns about their robustness in real-world deployment in security critical environments. In this work, we study a core vulnerability in MPNNs that explicitly consume graph topology via the adjacency matrix or Laplacian as part of their message passing mechanism. We show that this design choice exposes an extremely vulnerable attack surface, with significant effects even under minimal perturbation. Building on this observation, we propose PEA, a simple, gradient-free, black-box injection attack that requires only a single query to the target model, capitalizing on this vulnerability by constructing a perturbation aligned with a specific significant eigenvector to induce large output deviations. Unlike graph modification attacks, PEA operates under the realistic assumption that adversaries cannot alter the original graph and are limited to injecting new nodes at inference time. PEA requires no iterative optimization, parameter learning, or surrogate models---which require additional training and remain susceptible to differences in model priors and generalization capabilities---thereby avoiding significant computational overhead and the associated transferability challenges. We evaluate PEA on popular benchmark datasets across three graph learning tasks, showing consistent performance degradation under realistic attack constraints despite its simplicity. Our results reveal a fundamental security weakness in topology-driven message passing architectures and urge an implementation shift, as the worst effects of such attacks can be substantially mitigated through appropriate input filtering.

Figures & tables

Fig. 1 : PEA when used on a graph-level task. The attacker queries the model once to obtain the (clean) node-level embeddings, using them to create the perturbation

{\mathbf{S}}_{v}

using the eigenvector

{\mathbf{u}}_{1}

{\mathbf{Z}}{\mathbf{Z}}^{\top}

which induces a high

{\mathcal{L}}({\mathbf{S}}_{v})

Dataset	$r$	$n_{v}$	AGIA		TDGIA		ATDGIA		G2A2C		PEA		PEA (Acting on ${\mathbf{S}}$ )
Dataset	$r$	$n_{v}$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$
Cora	0.001	2	$0.00$ $\pm 0.00$	$0.00$ $\pm 0.00$	$0.00$ $\pm 0.00$	$0.00$ $\pm 0.00$	$0.10$ $\pm 0.12$	$0.09$ $\pm 0.13$	$0.21$ $\pm 0.05$	$0.20$ $\pm 0.06$	$0.07$ $\pm 0.09$	$0.06$ $\pm 0.10$	$59.20$ $\pm 0.29$	$80.10$ $\pm 0.32$
	0.01	27	$1.34$ $\pm 0.14$	$1.43$ $\pm 0.26$	$1.45$ $\pm 0.33$	$1.50$ $\pm 0.34$	$2.23$ $\pm 0.37$	$2.65$ $\pm 0.39$	$2.19$ $\pm 0.16$	$2.11$ $\pm 0.25$	$0.73$ $\pm 0.31$	$0.54$ $\pm 0.29$	$59.20$ $\pm 0.29$	$80.10$ $\pm 0.32$
	0.05	135	$16.77$ $\pm 0.74$	$17.25$ $\pm 0.63$	$16.03$ $\pm 1.01$	$16.74$ $\pm 1.19$	$28.30$ $\pm 0.89$	$30.69$ $\pm 0.89$	$9.78$ $\pm 0.30$	$9.68$ $\pm 0.37$	$41.58$ $\pm 3.75$	$47.60$ $\pm 5.05$	$59.20$ $\pm 0.29$	$80.10$ $\pm 0.32$
	0.1	270	$29.14$ $\pm 0.65$	$30.87$ $\pm 0.62$	$29.50$ $\pm 0.88$	$30.94$ $\pm 0.71$	$37.92$ $\pm 1.46$	$39.21$ $\pm 1.24$	$19.65$ $\pm 0.42$	$19.93$ $\pm 0.42$	$58.74$ $\pm 0.37$	$79.12$ $\pm 0.55$	$59.20$ $\pm 0.29$	$80.10$ $\pm 0.32$
Citeseer	0.001	3	$0.00$ $\pm 0.00$	$0.00$ $\pm 0.00$	$0.00$ $\pm 0.00$	$0.00$ $\pm 0.00$	$0.00$ $\pm 0.00$	$0.01$ $\pm 0.01$	$0.20$ $\pm 0.06$	$0.28$ $\pm 0.10$	$0.01$ $\pm 0.03$	$0.02$ $\pm 0.05$	$31.67$ $\pm 4.84$	$42.42$ $\pm 6.19$

TABLE I : Results of PEA and the baselines on NC using the SGC architecture as the defending model. The decrease in accuracy and (macro) F1 score are reported for each method, with statistics computed over

10

runs for all methods except G2A2C, which is over

5

runs (

3

for Pubmed) due to very high execution times.

Dataset	$r$	$n_{v}$	Clean		RAND		DEG		BET		CENT		PEA
Dataset	$r$	$n_{v}$	Accuracy	F1	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$
Cora	0.001	2	$86.90$ $\pm 0.29$	$86.30$ $\pm 0.32$	$0.07$ $\pm 0.28$	$0.06$ $\pm 0.32$	$0.06$ $\pm 0.35$	$0.04$ $\pm 0.40$	$0.01$ $\pm 0.30$	$-0.00$ $\pm 0.34$	$0.01$ $\pm 0.28$	$0.00$ $\pm 0.31$	$0.07$ $\pm 0.32$	$0.06$ $\pm 0.35$
	0.01	27	$86.90$ $\pm 0.29$	$86.30$ $\pm 0.32$	$0.92$ $\pm 0.24$	$0.76$ $\pm 0.44$	$0.35$ $\pm 0.26$	$0.22$ $\pm 0.38$	$0.07$ $\pm 0.34$	$0.01$ $\pm 0.38$	$-0.06$ $\pm 0.28$	$-0.11$ $\pm 0.30$	$0.73$ $\pm 0.32$	$0.54$ $\pm 0.42$
	0.05	135	$86.90$ $\pm 0.29$	$86.30$ $\pm 0.32$	$33.32$ $\pm 2.77$	$36.68$ $\pm 3.21$	$10.63$ $\pm 2.23$	$10.72$ $\pm 2.27$	$1.03$ $\pm 0.26$	$0.74$ $\pm 0.35$	$-0.01$ $\pm 0.32$	$-0.05$ $\pm 0.38$	$41.58$ $\pm 3.74$	$47.60$ $\pm 5.04$
	0.1	270	$86.90$ $\pm 0.29$	$86.30$ $\pm 0.32$	$56.39$ $\pm 0.66$	$74.47$ $\pm 1.27$	$55.52$ $\pm 1.92$	$73.04$ $\pm 3.22$	$2.39$ $\pm 0.27$	$1.80$ $\pm 0.30$	$0.44$ $\pm 0.37$	$0.51$ $\pm 0.45$	$58.74$ $\pm 0.15$	$79.12$ $\pm 0.35$
Citeseer	0.001	3	$73.42$ $\pm 0.44$	$69.54$ $\pm 0.40$	$0.00$ $\pm 0.44$	$0.01$ $\pm 0.40$	$0.01$ $\pm 0.45$	$0.02$ $\pm 0.40$	$0.00$ $\pm 0.46$	$0.00$ $\pm 0.42$	$-0.02$ $\pm 0.44$	$-0.02$ $\pm 0.40$	$0.01$ $\pm 0.44$	$0.02$ $\pm 0.40$

TABLE II : Results of PEA and the heuristic baselines on NC using the SGC architecture as the defending model. The decrease in accuracy and (macro) F1 score are reported for each method, with statistics computed over

10

runs.

Statistic $\backslash$ Dataset	Cora	Citeseer	Pubmed
Number of Classes	7	6	3
Number of Nodes	2708	3327	19717
Number of Edges	10556	9104	88648
Avg. Degree	4.90	3.74	5.50
${n_{v}}$ for $r=0.01$	27	33	197
${\bm{\Delta}}$ for $r=0.01$	132	124	1083

TABLE III : Dataset summary for the NC task.

Fig. 2 : Comparing PEA to the heuristic baselines across the three NC datasets, on the SGC .

Dataset	Layer	Mean Aggregation		Sum Aggregation
Dataset	Layer	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$
Cora	SAGE	3.09±0.65	3.04±0.64	49.26±7.81	68.47±8.14
Cora	GIN	4.70±0.89	5.42±1.12	51.74±3.79	72.28±3.69
Citeseer	SAGE	0.65±0.35	0.66±0.57	49.26±7.81	68.47±8.14
Citeseer	GIN	1.79±1.07	1.78±1.28	34.56±14.10	44.31±15.50
Pubmed	SAGE	0.79±0.22	0.82±0.26	44.94±1.16	64.75±1.91

TABLE IV : Ablation on SAGE and GIN , with a fixed

r=0.05

. Results on more values of

r

are reported in Appendix -F4 . The original pairing is SAGE and GIN with Mean and Sum aggregation respectively.

Fig. 3 : Base performance across different architectures (Left); Performance of different

\tilde{{\mathbf{X}}}

modes across layers for a fixed budget (Top-right); and Performance of PEA vs filter-based defense methods (Bottom-right).

Fig. 4 : Norm difference (

{\mathcal{L}}({\mathbf{S}}_{v})

) between PEA -W, PEA , and a randomly chosen

{\mathbf{S}}_{v}

, illustrating how the white-box version compares with the black-box approximation and randomly chosen perturbations, using SGC on the NC datasets.

Statistic $\backslash$ Dataset	FreeSolv	ESOL	Lipophilicity	ZINC	AQSOL	MUTAG	PROTEINS	ENZYMES	IMDB-BINARY	BBBP	BACE
Number of Graphs	641	1126	4200	12000	9833	188	1113	600	1000	2039	1513
Number of Classes	-	-	-	-	-	2	2	6	2	2	2
Avg. Number of Nodes	8.73	13.29	27.04	23.16	17.58	17.93	39.06	32.63	19.77	24.06	34.09
Avg. Number of Edges	25.51	40.63	86.04	72.99	53.38	57.52	184.69	156.91	212.84	75.97	107.81
Avg. Degree	2.83	2.98	3.18	3.14	2.98	3.19	4.73	4.86	9.89	3.13	3.17
Avg. ${\bm{\Delta}}$ for $r=0.05$	1.28	2.03	4.30	3.65	2.67	2.88	9.23	7.85	10.64	3.80	5.39

TABLE V : Dataset summary for the GR and GC tasks.

Fig. 5 : GIN Regression performance vs number of virtual nodes on the five regression datasets.

Fig. 6 : GCN Regression performance vs number of virtual nodes on the MoleculeNet datasets.

Panel of Figure 12 — Fig. 7 : GIN regression performance across the five datasets after perturbation with PEA and the four heuristic baselines (Top); and with PEA , PEA -D, Rand and Rand -D (Bottom), for the same budget (normalized for the discrete variants).

Dataset	Clean	PEA	RAND	DEG	BET	CENT
FreeSolv	1.113	2.145	2.277	2.345	1.724	2.356
ESOL	0.422	0.858	0.767	0.801	0.848	0.806
Lipophilicity	0.629	0.861	0.786	0.830	0.758	0.762
ZINC	0.729	1.751	1.610	1.614	1.455	1.594
AQSOL	1.545	8.243	9.681	11.505	8.031	9.243

TABLE VI : Performance of PEA and the heuristic baselines on the GR datasets with

{n_{v}}=5

Datasets	Accuracy	Macro F1
MUTAG	$84.18$ $\pm 8.12$	$81.10$ $\pm 10.75$
PROTEINS	$75.11$ $\pm 2.43$	$73.67$ $\pm 2.32$
ENZYMES	$44.00$ $\pm 8.10$	$42.94$ $\pm 6.65$
IMDB-BINARY	$71.30$ $\pm 3.80$	$71.05$ $\pm 3.84$
BBBP	$87.49$ $\pm 1.49$	$81.24$ $\pm 3.43$
BACE	$78.26$ $\pm 3.26$	$77.93$ $\pm 3.39$

TABLE VII : Mean performance of the GIN on GC. Statistics are computed over 10-Fold cross validation splits.

Fig. 8 : GIN Classification accuracy vs number of virtual nodes on the six classification datasets. All reported numbers have been averaged over the 10-Fold CV.

Dataset	Metric	Budget	PEA	RAND	DEG	BET	CENT
PEMS-BAY	MAE (1.790)	0.050	0.282	0.174	0.334	0.073	0.283
		0.075	0.548	0.287	0.688	0.121	0.635
		0.100	0.833	0.456	1.122	0.187	1.050
	MAPE (4.136)	0.050	0.504	0.284	0.575	0.237	0.504
		0.075	1.042	0.496	1.165	0.363	1.138
		0.100	1.609	0.811	1.936	0.517	1.888

TABLE VIII : Performance on three metrics on the three traffic flow prediction datasets. The numbers below the metric name denote the clean performance, and the numbers for each method denote the respective increases (higher is better).

Dataset	$r$	${n_{v}}$	AGIA		TDGIA		ATDGIA		PEA
Dataset	$r$	${n_{v}}$	$\rm Accuracy_{\downarrow}$	$\rm F1_{\downarrow}$	$\rm Accuracy_{\downarrow}$	$\rm F1_{\downarrow}$	$\rm Accuracy_{\downarrow}$	$\rm F1_{\downarrow}$	$\rm Accuracy_{\downarrow}$	$\rm F1_{\downarrow}$
Cora	0.001	2	$0.04$ $\pm 0.11$	$0.03$ $\pm 0.08$	$0.07$ $\pm 0.15$	$0.05$ $\pm 0.10$	$0.07$ $\pm 0.15$	$0.07$ $\pm 0.15$	$0.07$ $\pm 0.17$	$0.04$ $\pm 0.17$
	0.01	27	$2.52$ $\pm 0.62$	$2.21$ $\pm 0.62$	$2.41$ $\pm 0.48$	$2.04$ $\pm 0.56$	$3.78$ $\pm 0.92$	$5.11$ $\pm 1.69$	$0.72$ $\pm 0.42$	$0.57$ $\pm 0.42$
	0.05	135	$8.96$ $\pm 1.18$	$10.24$ $\pm 1.58$	$9.81$ $\pm 1.55$	$11.05$ $\pm 1.89$	$12.78$ $\pm 2.25$	$13.55$ $\pm 2.24$	$36.12$ $\pm 1.94$	$45.34$ $\pm 3.18$
	0.1	270	$12.44$ $\pm 1.30$	$13.38$ $\pm 1.69$	$13.00$ $\pm 1.45$	$13.72$ $\pm 1.88$	$14.52$ $\pm 2.00$	$15.05$ $\pm 2.35$	$51.65$ $\pm 0.77$	$73.08$ $\pm 0.77$
Citeseer	0.001	3	$0.15$ $\pm 0.15$	$0.11$ $\pm 0.11$	$0.15$ $\pm 0.15$	$0.11$ $\pm 0.11$	$0.18$ $\pm 0.15$	$0.17$ $\pm 0.13$	$0.00$ $\pm 0.07$	$-0.00$ $\pm 0.06$

TABLE IX : Results of PEA and the baselines on Node c-lassification using the GCN architecture as the defending model. The accuracy and (macro) F1 score on the clean datasets are reported first, followed by their respective decrease for each method.

Fig. 9 : GIN Classification F1 vs number of virtual nodes on the six classification datasets. All reported numbers have been averaged over the 10-Fold CV.

Fig. 10 : GIN Regression performance (RMSE and MAE) for PEA , PEA -D, Rand and Rand -D for the same budget (normalized for the discrete variants), across the five regression datasets.

Defense $\rightarrow$	Jaccard (0.01)		Jaccard (0.05)
$r$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$
Clean	86.08±0.47	85.35±0.63	83.49±0.47	82.45±0.58
0.001	0.00±0.06	0.00±0.05	0.00±0.06	0.00±0.06
0.01	0.07±0.36	0.00±0.42	0.00±0.23	0.00±0.24
0.05	7.06±1.70	6.46±1.68	0.37±0.31	0.27±0.38
0.1	37.78±4.42	44.42±6.13	3.70±1.12	3.39±0.98

TABLE X : Clean accuracy and macro F1 scores followed by their respective decreases for the Jaccard graph defense method on the Cora dataset, using the SGC architecture.

Defense $\rightarrow$	SVD (20)		SVD (200)
$r$	Accuracy $\downarrow$	F1 $\downarrow$	Accuracy $\downarrow$	F1 $\downarrow$
Clean	75.76±0.49	74.22±0.75	83.71±0.45	83.02±0.52
0.001	1.81±0.56	2.27±0.69	1.60±0.78	1.24±0.79
0.01	11.73±1.69	14.31±1.20	5.00±0.78	4.28±0.80
0.05	34.88±4.14	45.98±5.63	35.27±4.19	42.27±5.25
0.1	46.98±0.90	65.73±1.42	54.91±0.55	74.56±1.03

TABLE XI : Clean accuracy and macro F1 scores followed by their respective decreases for the SVD graph defense method on the Cora dataset, using the SGC architecture.

Layer	Aggregation	Metric	$r$
Layer	Aggregation	Metric	0.001	0.01	0.05	0.1
SAGE	Mean	Accuracy $\downarrow$	0.04±0.09	0.10±0.25	3.09±0.65	7.73±1.35
	Mean	F1 $\downarrow$	0.06±0.09	0.14±0.27	3.04±0.64	7.64±1.23
	Sum	Accuracy $\downarrow$	0.02±0.16	4.31±1.88	49.26±7.81	54.25±5.67
	Sum	F1 $\downarrow$	-0.02±0.20	4.64±3.02	68.47±8.14	74.61±6.67
GIN	Sum	Accuracy $\downarrow$	0.03±0.23	12.39±8.18	51.74±3.79	54.62±4.50

TABLE XII : SAGE / GIN ablation on the Cora dataset

Layer	Aggregation	Metric	$r$
Layer	Aggregation	Metric	0.001	0.01	0.05	0.1
SAGE	Mean	Accuracy $\downarrow$	0.01±0.08	0.09±0.20	0.65±0.35	1.88±0.43
	Mean	F1 $\downarrow$	0.00±0.12	0.14±0.24	0.66±0.57	2.13±0.66
	Sum	Accuracy $\downarrow$	-0.04±0.18	1.67±2.16	34.56±14.10	43.26±12.41
	Sum	F1 $\downarrow$	0.06±0.23	2.41±2.36	44.31±15.50	53.31±13.18
GIN	Sum	Accuracy $\downarrow$	0.20±0.29	22.30±9.79	41.21±10.76	46.83±8.23

TABLE XIII : SAGE / GIN ablation on the Citeseer dataset

Layer	Aggregation	Metric	$r$
Layer	Aggregation	Metric	0.001	0.01	0.05	0.1
SAGE	Mean	Accuracy $\downarrow$	-0.05±0.05	-0.29±0.13	0.79±0.22	2.02±0.41
	Mean	F1 $\downarrow$	-0.05±0.05	-0.31±0.13	0.82±0.26	2.22±0.61
	Sum	Accuracy $\downarrow$	0.15±0.18	28.68±8.91	44.94±1.16	45.27±0.30
	Sum	F1 $\downarrow$	0.31±0.21	44.32±9.31	64.75±1.91	65.35±0.38
GIN	Sum	Accuracy $\downarrow$	0.90±1.17	30.38±11.05	40.04±9.28	40.45±8.72

TABLE XIV : SAGE / GIN ablation on the Pubmed dataset

Dataset	Layer (Clean Acc)	$\tilde{{\mathbf{X}}}$ Mode	Accuracy Decrease (in %)
Dataset	Layer (Clean Acc)	$\tilde{{\mathbf{X}}}$ Mode	PEA	RAND	DEG	BET	CENT
Cora	SGC [0.2em]( $86.95$ $\pm 0.27$ )	zeros	$41.58$ $\pm 3.74$	$33.32$ $\pm 2.77$	$10.63$ $\pm 2.23$	$1.03$ $\pm 0.26$	$-0.01$ $\pm 0.32$
		avg	$46.34$ $\pm 4.00$	$37.28$ $\pm 2.99$	$16.89$ $\pm 3.13$	$1.52$ $\pm 0.32$	$0.04$ $\pm 0.33$
		randsamp	$45.66$ $\pm 2.32$	$36.97$ $\pm 1.97$	$16.59$ $\pm 1.79$	$1.60$ $\pm 0.26$	$0.03$ $\pm 0.38$
		rand	$58.86$ $\pm 0.35$	$54.94$ $\pm 2.42$	$50.81$ $\pm 3.69$	$6.61$ $\pm 0.75$	$2.92$ $\pm 0.84$
		randn	$41.21$ $\pm 4.13$	$33.06$ $\pm 2.94$	$10.34$ $\pm 2.24$	$1.09$ $\pm 0.20$	$-0.03$ $\pm 0.20$

TABLE XV : Performance of different ways of choosing

\tilde{{\mathbf{X}}}

across different MPNN architectures for the Cora and Citeseer datasets, with a fixed budget of

r=0.05

. For a given

\tilde{{\mathbf{X}}}

, the maximum decrease across all methods is underlined.

Panel of Figure 26 — Fig. 11 : Performance of PEA and the heuristic baselines on all three NC datasets over different perturbation budgets $r$

Explore similar work

Jun 4, 2026

PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysis

Whilst the vulnerability of graph neural networks (GNNs) to adversarial attacks poses a critical threat to graph representation learning, the understanding of the robust generalization behavior remains a fundamental challenge in the adversarial setting. Recently, PAC-Bayesian margin-based generalization analysis substantially advances this line of research by providing a flexible and data-dependent analytical framework. However, existing robust analyses often rely on isotropic Gaussian posteriors and control weight perturbations in the full parameter space, which limits the ability to capture heterogeneous parameter sensitivity yet hinges on hidden-width-dependent complexity terms, resulting in not-tight-enough generalization bounds. In this paper, we extend a recently proposed sensitivity-aware PAC-Bayesian framework from deep neural networks to message passing GNNs (MPGNNs) and derive a tighter robust generalization bound in the adversarial setting. Specifically, we first quantify how sensitive the perturbations across different parameter blocks are to the network outputs by deriving the output Jacobians with respect to the weight parameters. Exploiting the fact that these Jacobian matrices have rank at most

K

K

-class graph classification, we then construct Jacobian-aligned sensitivity matrices and use anisotropic Gaussian posteriors with optimized covariances to upper bound the KL divergence in a tight way. Notably, by refining the spectral-norm dependence on the learned weights and reducing the leading dimension factor from hidden-width-dependent terms to the number of classes

K

, our analysis yields much tighter robust generalization guarantees for MPGNNs, thereby guiding their designs to enhance adversarial robustness.

Ziling Liang, Xinping Yi, Qingsong Wen +1

School of Information Science and Engineering, Southeast University, Nanjing 210096, China · Squirrel Ai Learning, Bellevue, WA, 98004 USA

PAC-Bayesian Generalization Bounds Adversarial Robustness Message Passing Neural Networks

Ask PDF

Aug 11, 2026

Defending against Model Extraction for GNNs with Model Reprogramming

Graph Neural Networks (GNNs) serve as the backbone for high-stakes applications in Machine-Learning-as-a-Service (MLaaS). Still, their black-box deployment exposes them to Model Extraction (ME) attacks, in which adversaries steal intellectual property by querying APIs. Existing defenses suffer from a critical ''Euclidean bias'': they transfer image-based strategies (e.g., random noise) to graphs, ignoring the complex topological dependencies between nodes, which often results in severe utility degradation. Passive methods like watermarking also fail to prevent theft in real time. To bridge this gap, we propose GraphRP (Graph Reprogramming Protection), a proactive defense framework that repurposes Model Reprogramming for security. Unlike static perturbations, GraphRP introduces a Structure-Aware Gating Mechanism driven by learnable topological prototypes. This creates a dynamic ''structural firewall'' that selectively modulates the model's decision boundary: it preserves fidelity for benign queries residing on the training manifold, while maximizing the Fisher Information along the perturbation direction for adversarial queries. Under standard assumptions (bounded loss, optimal attacker, and local second-order approximation), we prove a lower bound on the attacker's estimation error that increases with the structural sensitivity of the reprogramming noise. Extensive experiments on both hard-label and soft-label ME attacks demonstrate that GraphRP significantly degrades attack effectiveness while preserving benign utility.

Yan Wen, Zhenyi Wang, Heng Huang

University of Maryland, College Park Department of Computer Science College Park, MD, USA · University of Central Florida Department of Computer Science and Institute of Artificial Intelligence Orlando, FL, USA

Graph Neural Networks Model Extraction Attacks

Ask PDF

Jun 6, 2026

Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense

Graph neural networks (GNNs) are widely deployed on relational data, yet they can leak sensitive or proprietary information about the training graph adjacency, e.g., social ties, transactions, and interactions. This work studies graph reconstruction attacks (GRA), a form of model inversion that reconstructs the training adjacency from a trained GNN, given different levels of attacker-side information. We first provide a systematic characterization of when and why adjacency becomes recoverable through features, labels, embeddings, and predictions, with leakage modulated by graph homophily, heterophily, and the model's inductive bias. Motivated by these findings, we view GNN inference through a Markov chain approximation lens, treating the layered forward computation as a chain of topology-dependent representations. Building on this view, we develop complementary attack and defense methods. On the attack side, we propose MC-GRA (+), which reconstructs the adjacency by optimizing a surrogate adjacency whose GNN-induced representations align with those of the target model at each layer. On the defense side, we propose MC-GPB (+), which suppresses adjacency-dependent information throughout the representation chain while aiming to preserve classification accuracy under a privacy-utility trade-off. Experiments across homophilic/heterophilic graph benchmarks and GNNs show that our attacks improve reconstruction fidelity over prior methods, while our defenses reduce reconstruction success with only minor accuracy loss.

Zhanke Zhou, Bo Han, Xuan Li +3

TMLR Group, Department of Computer Science, Hong Kong Baptist University, Kowloon Tong · Cooperative Medianet Innovation Center, Shanghai Jiao Tong University, Shanghai, China · Department of Computer Science, Stanford University, Stanford, CA 94305, USA +1

Graph Neural Networks Privacy-Preserving ML

Ask PDF