Lethe: Link Inference Attacks For Evaluation of Edge Unlearning Methods

Andrea D'Angelo; Francesco Gullo; Davide Mottin; Sayan Ranu; Giovanni Stilo

cs.LGOct 15, 2026

Lethe: Link Inference Attacks For Evaluation of Edge Unlearning Methods

Authors: Andrea D'Angelo, Francesco Gullo, Davide Mottin, Sayan Ranu, Giovanni Stilo

Organizations: University of Aarhus Aarhus, Denmark · University of L’Aquila L’Aquila, Italy · Indian Institute of Technology Delhi Delhi, India · Luiss Guido Carli University Rome, Italy

Abstract

Graph Unlearning (GU) aims to remove the influence of specific training data from a Graph Neural Network without retraining anew. While most methods address removal of nodes and features, Edge Unlearning (EU), aiming at forgetting edges, has recently attracted dedicated attention as a standalone problem due to the hardness of completely removing the impact of an edge in the model. Despite this, no dedicated benchmark for EU exists besides isolated evaluations on feature-rich datasets such as Cora and Citeseer where GNNs exploit node features rather than graph structure. As such, we show two systematic limitations in existing evaluations: dedicated EU methods can be slower than retraining anew, and accuracy metrics are uninformative due to the negligible impact of edge removal. To address this gap, we introduce Lethe, the first comprehensive benchmark for Edge Unlearning, featuring 15 methods and 8 datasets. Our benchmark emphasizes large graphs, introduces evaluation tasks of varying difficulty, and proposes empirical measures based on link inference attacks rather than proxy accuracy metrics. We provide a comprehensive empirical analysis, demonstrate the shortcomings of current evaluations, and release Lethe as a reproducible, extensible benchmark.

Figures & tables

Figure 1: Main benchmark findings. (a) Inefficiency: Some methods take longer than retraining the model from scratch (Gold Model) or exhibit negligible runtime advantage; (b) Uninformative measures: No significant drop in accuracy after removing up to 50% of edges.

Figure 2: Runtime (sec.) of GU methods on Cora, Citeseer and Pubmed across 5 different GNN architectures. Note that CGU and ScaleGUN only work on linear models (i.e., SGC). The red line represents the Gold Model: anything above implies that it takes more time than retraining the model from scratch.

Dataset	Architecture	Original	Gold Model (5%)		Gold Model (20%)		Gold Model (50%)
Dataset	Architecture	Original	Acc	$\Delta$	Acc	$\Delta$	Acc	$\Delta$
Computers	GCN	79.7	81.1	+1.3	81.6	+1.9	75.2	-4.5
	GIN	42.7	43.8	+1.1	25.0	-17.6	36.6	-6.1
	GAT	81.8	81.4	-0.4	80.9	-0.9	79.1	-2.7
	GraphSAGE	84.0	83.9	-0.1	83.4	-0.5	81.1	-2.9
	SGCCGU	75.6	74.4	-1.2	74.6	-1.1	73.5	-2.2

Table 1: Gold Model test accuracy (%) across architectures and datasets at 5%, 20%, and 50% forget-set size. Original shows the accuracy of the unmodified model (upper bound).

\Delta

is the accuracy change relative to Original.

Dataset	Domain	$\|V\|$	$\|E\|$	Avg. deg	Density	Features	Classes	$\Delta_{20\%}$
Cora	Citation	2.7K	10.6K	7.8	0.29%	1433	7	$-3.1$
Citeseer	Citation	3.3K	9.2K	5.5	0.17%	3703	6	$-1.5$
Pubmed	Citation	19.7K	44.3K	4.5	0.02%	500	3	$+0.3$
Computers	Co-purchase	13.8K	492K	35.8	0.52%	767	10	$+0.5$
Photos	Co-purchase	7.6K	238K	31.1	0.81%	745	8	$-2.2$
DBLP	Citation	17.7K	106K	6.0	0.07%	1639	4	$+0.1$

Table 2: Datasets included in Lethe and their key properties. Avg. deg : average node degree. Density : edge density.

\Delta_{20\%}

: accuracy change Gold

-

Identity (pp) at

k{=}20\%

forget set.

	Photos				Computers				DBLP				Flickr				ogbn-arxiv
Method	Acc	UMIA	LT	LS	Acc	UMIA	LT	LS	Acc	UMIA	LT	LS	Acc	UMIA	LT	LS	Acc	UMIA	LT	LS
Original	90.8	0.526	0.480	0.639	79.9	0.500	0.564	0.525	82.5	0.505	0.392	0.733	49.0	0.510	0.391	0.746	53.1	0.505	0.636	0.833
GoldModel	90.3	0.524	0.490	0.635	81.6	0.505	0.569	$0.587$	83.1	0.501	0.366	0.729	48.3	0.511	0.369	$0.765$	53.3	0.508	0.628	0.833
Finetuning	88.8	0.507	0.493	0.714	79.1	0.491	0.557	0.554	82.6	0.497	0.381	0.733	38.5	0.499	0.364	0.750	52.3	0.505	0.619	0.829
NegGrad	80.6	0.515	0.475	0.597	76.3	0.512	0.558	0.661	82.5	0.503	0.391	0.732	45.1	0.519	0.375	0.741	52.7	0.504	0.628	0.829
AdvNegGrad	89.3	0.525	0.492	0.716	69.1	0.512	0.550	0.807	82.6	0.495	0.376	0.731	44.3	0.517	0.366	0.741	51.4	0.503	0.621	0.816

Table 3: Accuracy and link inference attacks across all methods. Upper block: GCN architecture. Lower block: SGC architecture. Acc: test accuracy (% ;

\uparrow

better). UMIA: E-UMIA AUC (

\approx

0.5 = indistinguishable from random). LT: LinkTeller AUC. LS: Link Stealing AUC. Shaded rows are reference baselines. § GNNDelete collapses model performance, as found in Jain et al. (2026) .

Figure 3: (a) LinkTeller AUC and (b) Test accuracy mean and std across all methods on each dataset when unlearning low centrality (orange) and high centrality (blue) edges.

Figure 4: Runtime of certified EU methods relative to the Gold Model (retraining from scratch) at

5\%

forget-set size across all benchmark datasets. All bars above the dashed line indicate methods slower than retraining.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	$\|V\|$	$\|E\|$	1%	5%	10%	20%	50%
Cora	2,708	5,278	58.0 $\pm$ 2.3	85.0 $\pm$ 0.5	90.7 $\pm$ 0.6	94.2 $\pm$ 0.3	97.6 $\pm$ 0.4
Citeseer	3,327	4,552	26.3 $\pm$ 1.3	53.1 $\pm$ 0.9	65.1 $\pm$ 0.4	75.9 $\pm$ 0.3	88.5 $\pm$ 0.2
Pubmed	19,717	44,324	76.2 $\pm$ 1.4	94.5 $\pm$ 0.3	97.8 $\pm$ 0.2	99.3 $\pm$ 0.1	$\approx$ 100 $\pm$ 0.0

Appendix

Table 4: Fraction of nodes (%) affected by 2-hop neighbourhood expansion when removing a random subset of edges. Values averaged over 5 random forget-set samples. Bold entries exceed 80%.

Dataset	$\rho$ (WalkCentrality, loss increase)
Photos	-0.989
Computers	-0.993
DBLP	-0.989

Appendix

Table 5: Spearman correlation between WalkCentrality and the increase in training loss after edge removal.

Dataset	Low WalkCentrality	High WalkCentrality	Ratio
Photos	0.309	0.060	5.2 $\times$
Computers	0.274	0.042	6.7 $\times$
DBLP	0.289	0.056	5.3 $\times$

Appendix

Table 6: Endpoint displacement after edge removal for low- and high-WalkCentrality edges.

Method	None	25%	50%
Identity	0.518	0.641	0.639
Gold Model	0.547	0.673	0.672
Finetuning	0.522	0.636	0.634
NegGrad	0.564	0.681	0.678
Adv.NegGrad	0.554	0.685	0.682
UNSIR	0.776	0.861	0.863

Appendix

Table 7: LinkStealing ablation on attacker’s access.

Access to $G^{\prime}$	Photos	Flickr
0%	26 pp ( $p{=}3\times 10^{-9}$ )	2 pp ( $p{=}0.4$ )
25%	23 pp ( $p{=}2\times 10^{-8}$ )	6 pp ( $p{=}3\times 10^{-3}$ )
50%	24 pp ( $p{=}2\times 10^{-8}$ )	11 pp ( $p{=}1\times 10^{-5}$ )
100%	24 pp ( $p{=}1\times 10^{-8}$ )	14 pp ( $p{=}2\times 10^{-6}$ )

Appendix

Table 8: F-tests on LinkStealing attacker’s access ablation

Metric	Low Centrality	High Centrality	Community
Accuracy (test)	0.8802	0.8873	0.8699
Accuracy (forget)	0.8901	0.8964	0.8548
E-UMIA	0.5162	0.5128	0.4981

Appendix

Table 9: Metrics on the community-built forget set on DBLP.

Method	Low Centrality	High Centrality	Community
Original	0.7480	0.4535	0.6786
GoldModel	0.7486	0.4589	0.6773
Finetuning	0.7481	0.4717	0.6756
NegGrad	0.7788	0.4487	0.6701
AdvNegGrad	0.7491	0.4600	0.6697
UNSIR	0.7572	0.4626	0.6715

Appendix

Table 10: Link Teller values for the community-built forget set on DBLP.

Metric	Low Centrality	High Centrality	Temporal Window
Accuracy (test)	0.5168	0.5151	0.5138
Accuracy (forget)	0.5276	0.5262	0.5220
E-UMIA	0.5051	0.5040	0.5020

Appendix

Table 11: Performance across different node groups and temporal windows.

Method	Low Centrality	High Centrality	Temporal Window
Original	0.7906	0.6357	0.7179
GoldModel	0.7707	0.6284	0.7185
Finetuning	0.7677	0.6191	0.7183
NegGrad	0.7665	0.6275	0.7150
AdvNegGrad	0.7622	0.6211	0.7205
UNSIR	0.7681	0.6264	0.7154

Appendix

Table 12: Performance across different node groups and temporal windows for each method.

	Photos				DBLP
Method	Low		High		Low		High
	LP AUC	LT	LP AUC	LT	LP AUC	LT	LP AUC	LT
Original	0.960	0.947	0.956	0.929	0.856	0.757	0.849	0.719
Gold Model	0.955	0.949	0.813	0.932	0.859	0.741	0.851	0.674
Finetuning	0.944	0.959	0.929	0.922	0.855	0.736	0.847	0.724
NegGrad	0.947	0.957	0.937	0.922	0.855	0.736	0.848	0.724

Appendix

Table 13: Link prediction performance on Photos and DBLP across low- and high-centrality forget sets. LP = Link Prediction. LT = Link Teller. Low = Low WalkCentrality set. High = High WalkCentrality set.

Attack	Forget Set	Photos	DBLP
Link Stealing	Low Centrality	0.950	0.860
Link Stealing	High Centrality	0.888	0.812
LinkTeller	Low Centrality	0.954	0.741
LinkTeller	High Centrality	0.926	0.713

Appendix

Table 14: Mean LS and LT values for Link prediction.

Method	Family	Graph-native	Certified	Needs retain set	Needs forget set
Original ( $M^{*}$ )	Reference	—	—	✗	✗
Retrain / Gold ( $M_{G}$ )	Reference	—	Exact	✓	✗
Fine-Tuning	Training	✗	✗	✓	✗
NegGrad	Gradient ascent	✗	✗	✗	✓
AdvancedNegGrad (NegGrad+)	Gradient ascent + descent	✗	✗	✓	✓
UNSIR	Noise / impair–repair	✗	✗	✓	✓

Appendix

Table 15: Overview of the unlearning methods considered in this work. “Graph-native” denotes methods that were originally proposed for and evaluated on graph neural networks (GNNs).

Figure 5: Per-method LinkTeller AUC (left) and test accuracy (right) for all five datasets under GCN, for low-centrality (orange diamonds) and high-centrality (blue circles) forget sets. The dashed line marks the random-chance AUC baseline of 0.5. GNNDelete is included for completeness but excluded from statistical analysis.

Figure 6: Aggregated complementary results for GIN , GAT , and GraphSAGE .

Method	DBLP	Photos	Computers	Flickr	ogbn-arxiv
Gold Model – GCN	9.1	12.4	17.1	14.0	45.6
Finetuning	0.8	7.9	8.9	2.2	9.5
NegGrad	0.8	7.2	8.9	3.8	9.6
AdvNegGrad	0.9	6.9	9.0	3.7	9.9
SCRUB	0.9	6.5	9.2	1.8	10.1
BadTeaching	0.9	7.1	9.1	3.8	12.3

Appendix

Table 16: RunTime comparison on GCN architecture.

Method	DBLP	Photos	Computers	Flickr	ogbn-arxiv
Gold Model – GIN	7.2	13.9	23.6	31.1	100
Finetuning	1.1	6.5	8.0	37.6	11.7
NegGrad	1.1	7.0	8.2	39.3	20.4
AdvNegGrad	1.5	6.6	9.0	39.0	23.9
SCRUB	2.3	6.6	9.7	46.6	20.6
BadTeaching	2.0	7.8	9.5	48.3	23.6

Appendix

Table 17: RunTime comparison on GIN architecture.

Method	DBLP	Photos	Computers	Flickr	ogbn-arxiv
Gold Model – SGC	18.4	19.7	35.5	56.3	38.5
Finetuning	2.1	3.9	11.8	17.9	11.5
NegGrad	2.2	4.4	9.6	19.0	11.8
AdvNegGrad	2.3	4.3	9.9	17.3	12.1
SCRUB	2.3	4.2	9.2	18.7	12.5
BadTeaching	2.5	4.5	9.8	18.6	15.0

Appendix

Table 18: Runtime comparison on SGC architecture.

Graph Unlearning

See all 11 papers

Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks
Mar 19, 2026Jiahao Zhang, Yilong Wang, Suhang WangGraph Unlearning Adversarial Attacks
The Pennsylvania State University University Park, PA, USA
GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning
Nov 14, 2025Ying Song, Balaji PalanisamyGraph Neural Networks Graph Unlearning
University of Pittsburgh Pittsburgh, PA, USA
Closed-Form Node Classification with Exact Graph Unlearning
May 25, 2026Aditya Gaur, Charu SharmaGraph Representation Learning Privacy-Preserving ML
Machine Learning Lab · IIIT Hyderabad

Mar 19, 2026J/K move · Enter open · S save

Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks

Jiahao Zhang, Yilong Wang, Suhang Wang

The Pennsylvania State University University Park, PA, USA

Graph Unlearning Adversarial Attacks Graph Neural Networks Machine Unlearning

Open paper AskPDF arXiv

Graph neural networks (GNNs) are widely used for learning from graph-structured data in domains such as social networks, recommender systems, and financial platforms. To comply with privacy regulations like the GDPR, CCPA, and PIPEDA, approximate graph unlearning, which aims to remove the influence of specific data points from trained models without full retraining, has become an increasingly important component of trustworthy graph learning. However, approximate unlearning often incurs subtle performance degradation, which may incur negative and unintended side effects. In this work, we show that such degradations can be amplified into adversarial attacks. We introduce the notion of unlearning corruption attacks, where an adversary injects carefully chosen nodes into the training graph and later requests their deletion. Because deletion requests are legally mandated and cannot be denied, this attack surface is both unavoidable and stealthy: the model performs normally during training, but accuracy collapses only after unlearning is applied. Technically, we formulate this attack as a bi-level optimization problem: to overcome the challenges of black-box unlearning and label scarcity, we approximate the unlearning process via gradient-based updates and employ a surrogate model to generate pseudo-labels for the optimization. Extensive experiments across benchmarks and unlearning algorithms demonstrate that small, carefully designed unlearning requests can induce significant accuracy degradation, raising urgent concerns about the robustness of GNN unlearning under real-world regulatory demands. The source code will be released upon paper acceptance.

Abstract

Graph Unlearning

Explore similar work

Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks

GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning

Closed-Form Node Classification with Exact Graph Unlearning