GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning

Ying Song; Balaji Palanisamy

cs.LGNov 14, 2025

GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning

Authors: Ying Song, Balaji Palanisamy

Organizations: University of Pittsburgh Pittsburgh, PA, USA

Abstract

Graph unlearning (GU) has emerged as a promising solution to comply with "the right to be forgotten" regulations by enabling the removal of sensitive information upon request. However, this solution is not foolproof. The involvement of multiple parties creates new attack surfaces, and residual traces of deleted data can persist within the unlearned graph neural networks (GNNs). These vulnerabilities can be exploited by attackers to recover the supposedly erased samples, undermining the intended functionality of GU. In this work, we propose GraphToxin, the first full graph reconstruction attack against GU. We show that GraphToxin can recover not only a deleted individual's information and personal links but also sensitive content of their neighbors, thereby posing substantially more detrimental threats than prior membership inference attacks (MIAs). Specifically, we introduce a novel curvature matching module to provide fine-grained guidance for full unlearned graph recovery. We further extend GraphToxin to multiple-node removal under both white-box and black-box settings, showcasing its practical feasibility and potential to cause considerable harm. We highlight the necessity of worst-case analysis and propose a systematic evaluation framework to assess attack performance under both random and worst-case node removal scenarios. Our extensive experiments demonstrate the effectiveness and flexibility of GraphToxin. Notably, current defense mechanisms are largely ineffective against this attack. Additionally, our findings reveal that existing GU verification standards based on MIAs can be misleading: they achieve membership-level protection, while the full unlearned graph remains recoverable through GraphToxin.

Figures & tables

Attack Type	Attacker’s Knowledge and Capabilities			Recovery Content		Attack Unlearning Case
Attack Type	Graph Data	Model Access	Graph Unlearning	Feature	Topology	Random	Worse
Attribute Inference Attack (N/A)	Partial/Shadow Graph	Grey/Black Box	$\varnothing$	Single/Partial	$\varnothing$	$\varnothing$	$\varnothing$
Link Stealing Attack [ 55 ]	Partial/Shadow Graph	Grey/Black Box	Partial Unlearned Graph	$\varnothing$	Single Edge	$\surd$	$\varnothing$
Graph Topology Reconstruction Attack (N/A)	Partial/Shadow Graph	Grey/Black Box	$\varnothing$	$\varnothing$	Partial/Full	$\varnothing$	$\varnothing$
Full Graph Reconstruction Attack (Ours)	Data-free	White/Black Box	#of Node&Edge and Labels	Full	Full	$\surd$	$\surd$

Table 1 : Attack Comparison .

\surd

represents “access” or “applicable”, and

\varnothing

denotes “not applicable” or “unknown”. N/A means currently unexplored in the field.

Figure 1 : An overview of GraphToxin. The white-box Gra- phToxin uses gradient difference for full unlearned graph recovery. The black-box GraphToxin first estimates gradie- nts and then exploits their difference for recovery.

Figure 2 : Example of the Ambiguity of Gradient Matching

Dataset	GU	Baseline	RNMSE( $\downarrow$ )		ED( $\downarrow$ )		PMGK( $\uparrow$ )		ATT. ACC( $\uparrow$ )		ATT. FID( $\uparrow$ )		PWD( $\downarrow$ )
Dataset	GU	Baseline	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst
Cora	Retrain	Rand.	6.59	3.61	78.76	72.45	84.35	68.35	6.79	9.18	6.31	7.48	82.79	80.23
		FewE	5.08	2.84	73.11	65.96	84.62	68.79	57.50	39.29	56.67	37.98	40.47	56.30
		GLG-GU	3.82	1.98	96.83	71.57	79.74	66.38	28.33	45.44	25.71	40.73	68.54	53.66
		Toxin	4.11	1.95	71.38	52.35	84.05	67.21	72.21	84.72	69.00	77.97	29.66	22.35
	MEGU	Rand.	6.59	3.61	78.76	72.45	84.19	68.64	6.79	9.18	6.31	7.48	82.79	80.23

Table 2 : The Performance of GraphToxin for Single-node Removal (Backbone: GCN) . Unit: 1e-2 . Arrow indicates the direction of better performance and the blue color denotes the superb ‘best’ results (in bold ).

Panel of Figure 3 — Figure 3 : Impact of the Full Unlearned Graph Size and Node Homophily

Figure 5 : Impact of Laplacian Coefficient

Noise	RNMSE( $\downarrow$ )		ED( $\downarrow$ )		PMGK( $\uparrow$ )		ACC( $\uparrow$ )		FID( $\uparrow$ )		PWD( $\downarrow$ )
Noise	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst
$0\%$	4.11	1.95	71.38	52.35	84.05	67.21	72.21	84.72	69.00	77.97	29.66	22.35
$5\%$	4.26	2.21	71.51	51.54	84.27	68.00	72.93	81.15	70.31	77.09	30.07	21.09
$10\%$	4.61	2.01	65.22	44.09	84.52	65.57	77.12	85.76	73.18	78.37	25.63	19.80
$15\%$	4.02	1.86	60.57	44.81	81.88	66.14	76.36	82.73	72.91	74.70	25.87	23.40
$20\%$	3.23	1.65	55.43	45.88	81.28	66.57	81.43	76.13	76.19	69.11	20.10	26.04

Table 3 : The Performance of GraphToxin under Label Noise (Dataset: Cora; Backbone: GCN; GU: Retraining)

Figure 6 : 1-hop and Higher-order Ripple Effects

Figure 7 : Impact of Layers in Ripple Effects

Defense	Type	RNMSE( $\downarrow$ )		ED( $\downarrow$ )		PMGK( $\uparrow$ )		ACC( $\uparrow$ )		FID( $\uparrow$ )		PWD( $\downarrow$ )
Defense	Type	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst
DP	$\sigma\textit{=}0.006$	4.94	2.63	65.79	54.16	84.80	65.81	77.13	90.92	66.17	80.98	41.64	36.40
	$\sigma\textit{=}0.007$	5.88	3.02	67.95	61.79	82.39	65.44	86.72	89.87	57.06	73.69	44.84	45.15
	$\sigma\textit{=}0.008$	5.86	3.22	73.16	67.57	82.10	66.76	75.22	80.22	45.38	54.76	45.61	47.19
	$\sigma\textit{=}0.009$	5.44	3.33	81.01	77.56	81.17	67.02	50.13	65.97	31.45	47.03	55.31	52.44
	$\sigma\textit{=}0.01$	5.15	3.30	89.03	82.55	82.63	65.68	34.38	52.80	47.03	36.95	54.12	49.95

Table 4 : The Performance of Node-DP and Gradient Compression in Defending GraphToxin (Dataset: Cora)

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Datasets	Nodes	Edges	Features	Labels	Avg. Deg.	Homo.(%)
Cora	2,708	10,556	1,433	7	3.90	82.52
PubMed	19,717	88,648	500	3	4.50	79.24
Photo	7,650	238,162	745	8	31.13	83.65

Appendix

Table 5 : Detailed Graph Statistics

Dataset	GNN	Original		Retraining				MEGU				ETR
		ACC	AUC	Random		Worst		Random		Worst		Random		Worst
		ACC	AUC	ACC	AUC	ACC	AUC	ACC	AUC	ACC	AUC	ACC	AUC	ACC	AUC
Cora	GCN	80.20	96.70	80.05	96.68	79.99	96.67	80.06	96.66	80.52	96.69	80.57	96.76	80.69	96.77
	SAGE	81.10	96.61	80.99	96.66	80.77	96.64	80.04	96.54	79.94	96.52	80.80	96.56	80.86	96.57
	SGC	81.10	96.12	80.42	96.24	80.24	96.19	80.64	96.06	80.49	96.06	81.10	96.15	81.10	96.17
PubMed	GCN	77.40	90.44	77.78	90.53	77.93	90.40	77.12	90.28	76.68	90.32	77.53	90.45	77.75	90.46

Appendix

Table 6 : The Performance of the Original and Unlearned GNNs for Single-node Removal .

Dataset	GU	Baseline	RNMSE( $\downarrow$ )		ED( $\downarrow$ )		PMGK( $\uparrow$ )		ATT. ACC( $\uparrow$ )		ATT. FID( $\uparrow$ )		PWD( $\downarrow$ )
Dataset	GU	Baseline	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst
PubMed	Retrain	Rand.	79.58	28.85	68.92	70.95	91.62	68.36	67.46	29.76	74.07	48.19	107.87	2.59
		FewE	77.73	27.99	65.14	61.47	92.30	71.30	67.46	77.19	74.08	67.20	0.02	10.61
		GLG-GU	45.74	10.04	68.59	90.81	90.47	64.55	68.39	38.67	77.78	30.99	20.89	61.74
		Toxin	53.44	13.36	74.17	63.16	90.66	70.68	85.58	88.18	78.17	69.14	18.65	12.24
	MEGU	Rand.	79.58	28.85	68.92	70.95	92.06	70.05	67.46	29.76	74.07	48.19	107.87	2.59

Appendix

Table 7 : The Performance of GraphToxin for Single-node Removal (Backbone: GCN) . Cont.

Dataset	GNN	Baseline	NRMSE( $\downarrow$ )		ED( $\downarrow$ )		PMGK( $\uparrow$ )		ATT. ACC( $\uparrow$ )		ATT. FID( $\uparrow$ )		PWD( $\downarrow$ )
Dataset	GNN	Baseline	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst
Cora	GCN	Rand.	6.59	3.61	78.76	72.45	84.35	68.35	6.79	9.18	6.31	7.48	82.79	80.23
		FewE	5.08	2.84	73.11	65.96	84.62	68.79	57.50	39.29	56.67	37.98	40.47	56.30
		GLG-GU	3.82	1.98	96.83	71.57	79.74	66.38	28.33	45.44	25.71	40.73	68.54	53.66
		Toxin	4.11	1.95	71.38	52.35	84.05	67.21	72.21	84.72	69.00	77.97	29.66	22.35
	SAGE	Rand.	6.59	3.61	65.84	63.10	81.13	66.78	6.79	9.18	5.60	6.66	89.97	91.17

Appendix

Table 8 : GraphToxin for Single-node Removal with Different GNN Backbones (GU: Retraining) .

Panel of Figure 10 — Figure 10 : Impact of the Full Unlearned Graph Size and Node Homophily

Rem. Num	Retraining(ACC/AUC)		Baseline	NRMSE( $\downarrow$ )		ED( $\downarrow$ )		PMGK( $\uparrow$ )		ACC( $\uparrow$ )		FID( $\uparrow$ )		PWD( $\downarrow$ )
Rem. Num	Random	Worst	Baseline	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst
5	80.22/96.64	80.30/96.66	Rand.	2.34	1.71	73.16	73.52	68.01	62.14	27.88	9.94	23.80	8.68	67.08	77.68
			FewE	2.13	1.65	61.95	62.41	70.47	60.59	28.75	20.02	28.78	20.15	66.79	72.13
			GLG-GU	0.91	0.70	53.86	52.17	69.55	62.78	68.27	68.07	59.00	61.92	40.57	38.44
			Toxin	1.66	1.03	56.27	54.59	70.45	64.82	60.03	70.40	52.06	63.98	47.24	39.08
10	79.98/96.50	80.44/96.49	Rand.	1.69	1.42	72.50	73.56	58.88	63.76	24.84	17.72	22.04	16.00	66.75	72.57

Appendix

Table 9 : GraphToxin for Multiple Node Removals Based on Retraining (Backbone: GCN, Dataset: Cora) .

Type	Retraining(ACC/AUC)		Baseline	NRMSE( $\downarrow$ )		ED( $\downarrow$ )		PMGK( $\uparrow$ )		ACC( $\uparrow$ )		FID( $\uparrow$ )		PWD( $\downarrow$ )
Type	Random	Worst	Baseline	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst	Random	Worst
Single	79.66/96.10	79.63/96.09	Rand.	11.51	6.29	127.87	120.86	81.09	67.11	12.20	13.85	13.51	14.40	16.19	14.64
			FewE	5.68	3.10	115.91	96.78	82.98	67.97	49.40	65.56	47.62	58.30	11.27	9.25
			GLG-GU	3.74	2.13	143.00	149.78	84.04	67.40	0.36	2.77	1.43	1.14	18.99	18.98
			Toxin	4.76	2.49	87.37	80.08	81.56	68.30	72.74	82.07	70.95	73.64	8.28	6.97
Multiple	79.86/96.09	79.78/96.10	Rand.	2.34	1.71	126.49	135.71	65.10	57.04	27.88	9.94	21.81	7.57	14.91	17.83

Appendix

Table 10 : Black-box GraphToxin for A Single and Multiple Node Removals Based on Retraining (Dataset: Cora) .

Figure 11 : Impact of Deletion Size in Ripple Effects

Explore similar work

Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense
Jun 6, 2026Zhanke Zhou, Bo Han, Xuan Li +3Graph Neural Networks Text-Attributed Graph
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 Federated Unlearning for Privacy Preservation
May 4, 2026Ruotong Ma, Wentao Yu, Qizhou Wang +2Federated Graph Learning Federated Learning
Shanghai Jiao Tong University · Nanjing University of Science and Technology · Hong Kong Baptist University China
MUGEN: Generating Unlearnable Graph Examples for Multiple Learning Tasks
Sep 1, 2026Ziyan Liu, Chengshuai Zhao, Huan LiuUnlearnable Examples Graph Representation Learning
Harrisburg University of Science and Technology Harrisburg, Pennsylvania, USA · Arizona State University Tempe, Arizona, USA

Jun 6, 2026, cs.LGJ/K move · Enter open · S save

Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense

Zhanke Zhou, Bo Han, Xuan Li, Jiangchao Yao+2

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 Text-Attributed Graph LLM Defense Mechanisms Inverse Problem

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense

Graph Federated Unlearning for Privacy Preservation

MUGEN: Generating Unlearnable Graph Examples for Multiple Learning Tasks