Lethe: Link Inference Attacks For Evaluation of Edge Unlearning Methods

AI summary

Overview

Research area: Graph machine learning and privacy — specifically Graph Unlearning (GU) and its subproblem, Edge Unlearning (EU), evaluated through link inference attacks.

Technical level: Intermediate to Advanced. Readers should be comfortable with Graph Neural Networks, message passing, and standard unlearning terminology, though the paper's central argument (that existing evaluations are uninformative) is stated plainly enough for newcomers.

Scope: This paper diagnoses two systematic flaws in how Edge Unlearning methods are evaluated — negligible runtime gains and accuracy metrics that barely move — and introduces Lethe, a benchmark of 15 methods, 8 datasets, and 5 architectures that replaces proxy accuracy with three link inference attacks and a centrality-based forget-set selection scheme called WalkCentrality.

What This Paper Is About

Edge Unlearning methods promise to remove a specific edge (for example, a connection between two users in a social network) from a trained Graph Neural Network without retraining from scratch. The paper shows that the standard way of testing these methods is broken: on small, feature-rich datasets like Cora and Citeseer, unlearning often takes as long as retraining, and deleting edges barely changes test accuracy, so accuracy cannot tell a good method from a bad one. The authors build a benchmark that measures whether an adversary can still detect that the forgotten edge was once there, rather than asking whether the model's accuracy stayed the same.

Key Contributions

1. An empirical diagnosis of two evaluation failures. The paper demonstrates that (a) on Cora, Citeseer, and Pubmed, most unlearning methods run in time comparable to retraining, with marginal gains typically below one second, and (b) retraining from scratch on a graph with up to half the edges removed still yields stable accuracy on most datasets (Δ ≤ 5%), making accuracy an uninformative signal for edge unlearning.

2. Lethe, the first dedicated Edge Unlearning benchmark. It spans 15 methods (9 general-purpose machine unlearning methods extended to graphs, plus 6 graph-specific methods), 8 datasets, and 5 model architectures, with an emphasis on large graphs satisfying the stated desideratum of more than 5K nodes and more than 100K edges.

3. A shift from accuracy to link inference attacks. The benchmark adapts three attacks — UMIA, Link Stealing (LS), and LinkTeller (LT) — where an adversary must classify a candidate edge as a forgotten edge versus a non-existing edge, with ROC-AUC reported and 0.5 treated as the ideal (random guessing).

4. WalkCentrality and two difficulty settings. A model-agnostic edge centrality measure derived from the normalized adjacency matrix is used to build "low centrality" and "high centrality" forget sets of 5% of edges each, exposing qualitatively different unlearning behaviour.

Main Findings

• Accuracy is essentially uninformative. Across benchmark datasets, the spread in test accuracy among non-collapsing methods is at most 11 percentage points on Photos with GCN and under 1.5 pp on DBLP with GCN, with the vast majority of methods clustering within ±2 pp of the Original model.

• E-UMIA is uniformly blind in the edge setting. Across all methods and datasets it produces AUC ≈ 0.48–0.53 with no method-discriminating signal. The sole exception is GNNDelete on DBLP (UMIA = 0.633), which the authors attribute to model collapse rather than genuine unlearning.

• Link Stealing is the most informative attack. On three of five datasets, LS produces a spread of at least 20 pp across methods, with a consistent ranking structure; on high-centrality settings the spread reaches 20–30 pp. On Photos, Computers, Flickr, and ogbn-arxiv, the standard deviation of LS across methods is 6–18× larger than E-UMIA (7.2×, 17.9×, 6.0×, 7.9× respectively) and 3–12× larger than LT, with all eight F-tests rejecting equal variance at p < 10⁻³.

• Statistical confirmation that accuracy does not move. One-sample t-tests on deviation from Identity yield p = 0.17 on AmazonComputers, p = 0.38 on DBLP, and p = 0.07 on ogbn-arxiv. On AmazonPhotos and Flickr the test is significant (p < 0.05), but the mean deviation is only −2.2 pp and −2.8 pp, driven by methods that sacrifice accuracy without reducing LS.

• Low-centrality edges stay exposed. On low-centrality forget sets, every method achieves LT AUC ≈ 0.75–0.85 except on Flickr. On high-centrality edges, LT drops to a range of 0.38–0.64. Every paired dumbbell spans roughly 0.35 AUC units. A Wilcoxon signed-rank test gives W = 9591, the theoretical maximum, because every low-centrality LT value exceeds its high-centrality counterpart (p < 10⁻²³), while the same test on accuracy gives W = 3568 (p = 0.14).

• Certified methods carry a double restriction. CEU, CGU, and ScaleGUN require a linear SGC architecture, which underperforms GCN by 3.6 pp on AmazonPhotos, 4.2 pp on AmazonComputers, and 1.2 pp on Flickr. At a 5% forget set their runtime exceeds that of retraining on all but the smallest datasets.

• Certified guarantees do not translate into attack resistance. CGU and ScaleGUN worsen LS relative to Identity on Photos by 8.3 pp and 6.6 pp respectively; CGU also worsens it on DBLP (+1.3 pp). Their gains on Flickr (−24.6 pp and −26.4 pp) come at the cost of CGU collapsing to 5.3% test accuracy there. All three certified methods increase LT on ogbn-arxiv (CEU +3.3 pp, CGU +6.6 pp, ScaleGUN +5.5 pp), meaning the unlearned model is more susceptible to influence-based inference than the untouched original.

• GNNDelete collapses the model in the edge setting. It falls to 34.6% accuracy on Photos, 37.9% on Computers, and 22.6% on ogbn-arxiv, consistent with findings reported for node unlearning.

Methodology in Plain English

The authors start by auditing how the field currently tests edge unlearning. They train a "Gold Model" — the reference produced by retraining from scratch on the graph with the edges already removed — and compare both runtime and accuracy against unlearning methods across five architectures. This audit reveals that on popular small datasets the runtime advantage is negligible, and that deleting edges barely perturbs predictions because node features carry most of the signal.

From this they derive three requirements for a fair benchmark: graphs must be large enough that retraining is genuinely expensive; datasets must reward structural information rather than relying on feature richness; and the forget set must vary in difficulty rather than being sampled uniformly at random.

For the difficulty dimension they define WalkCentrality from the symmetrically normalized adjacency matrix. Intuitively, a low-centrality edge sits in a sparse region and participates in few message-passing paths, so its removal leaves a localized, unmasked trace. A high-centrality edge lies on many paths, so its signal is diffused and partly redundant. The score for an edge sums, over all ways of splitting a k-step walk around that edge, the signal flowing into one endpoint and out of the other, and can be computed for all edges in O(k·|E|) by precomputing a few matrix-vector products.

Rather than measuring accuracy, the benchmark trains an adversary that sees the unlearned model and the retain graph and must decide whether a candidate edge was forgotten or never existed. An AUC near 0.5 means the edge leaves no detectable footprint; higher values mean privacy leakage. Experiments run on a Linux cluster with Intel Xeon Gold 6140M CPUs, 880 GB of RAM, and an NVIDIA A100 GPU, training all architectures for 100 epochs with Adam, early stopping at patience 10, and a minimum improvement threshold of 0.01, with Original and Gold Models cached across settings.

Why This Matters

Impact on research. The paper argues that a substantial body of published edge unlearning results rests on a metric that cannot discriminate between methods. By showing that a random-looking AUC of 0.5 is the correct target and that accuracy sits flat regardless of forget-set difficulty, it reframes what "successful unlearning" should mean for graphs. It also complements the node-focused benchmark of Jain et al. (2026) and argues that MIA-based protocols such as those in OpenGU (Fan et al., 2026) are often the least informative in a graph context.

Real-world applications:

• Social networks, where a user requests removal of a past interaction or connection and the model holder must eliminate that edge's influence while preserving the rest of the graph.
• Medical record systems built on relational data, where a specific patient relationship must be forgotten.
• Regulatory compliance under the GDPR right to be forgotten, where an organisation must demonstrably prove data has been removed rather than merely showing unchanged accuracy.
• Any deployed GNN over co-purchase, citation, or other relational data where an adversary could probe the model to reconstruct a supposedly deleted relationship.

Industry relevance. Practitioners deciding whether to adopt an unlearning method now have evidence that cheaper-than-retraining claims often do not hold at scale, and that formally certified methods only apply to weaker linear architectures and can be slower than retraining at realistic forget-set sizes.

Future Directions

• Extending the attacker suite. The authors state they tested state-of-the-art link inference attacks but could not cover all existing attacks, and explicitly call for the community to expand the evaluation as attacks improve over time.
• Broadening tasks and datasets. The paper notes it could not cover all downstream tasks for GNNs and positions Lethe as a modular framework, documented in Appendix E, that is easily extended to other datasets, models, and tasks.
• Making certified methods practical. The gap between parameter-space certification and attack-relevant geometry — where certified methods sometimes increase LT above the untouched model — invites guarantees that bound susceptibility to inference rather than only distance to the Gold Model.
• Designing defences for low-centrality edges. Since low-centrality forget sets remain exposed to LinkTeller for every method on four of five datasets, no existing strategy addresses the localized, non-redundant footprint that makes these edges detectable.

Target Audience

Researchers and graduate students working on graph neural networks, machine unlearning, or privacy-preserving machine learning who need a rigorous protocol for evaluating edge removal. It is also valuable to practitioners who must justify unlearning claims under data-protection requirements, and to benchmark designers interested in how centrality-guided difficulty settings expose weaknesses that random sampling hides.

Authors’ 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.