Lethe: Link Inference Attacks For Evaluation of Edge Unlearning Methods

1 Introduction

• EU seeks to remove information associated with specific edges while preserving the rest of the graph, a difficult task because removed edges may remain inferable through other mechanisms.In a social network, the request could concern removing a past interaction while retaining the remaining graph structure.Source: §1 · pp. 1–2
• Existing EU evaluations lack standardized protocols, and prior benchmarks either focus on node unlearning or rely mainly on UMIA and accuracy metrics.Source: §1 · p. 2
• Existing evaluations use small, feature-rich graphs where edge removal can leave accuracy nearly unchanged and unlearning runtime comparable to retraining.The paper notes that accuracy can remain stable even when up to half of the edges are removed.Source: §1 · p. 2, Figure 1 · p. 2
• Lethe benchmarks 15 methods across 8 datasets and 5 architectures, using larger graphs, link-inference attacks, and WalkCentrality-based forget-set strategies.The benchmark is designed to focus on graph structure rather than feature-rich representations.Source: §1 · p. 2
• Lethe uses link-inference attacks to assess method efficacy and finds that centrality-based forget-set selection can expose systematic failures in defending against those attacks.Source: §1 · p. 3

2 Related Work

• Dedicated edge-unlearning methods include GNNDelete’s structural objectives, CEU’s certified updates, and Unlink to Unlearn’s inference-time masking [26].Source: §2 · p. 3
• Existing methods commonly evaluate on small, feature-rich datasets such as Cora and Citeseer, while Lethe benchmarks general-purpose machine-unlearning methods for edge removal alongside dedicated graph-unlearning methods.Source: §2 · p. 3
• The Jain et al. benchmark focuses on node unlearning, while OpenGU [13] covers both node and edge tasks but emphasizes membership inference rather than dedicated link-inference attacks.Source: §2 · p. 3
• Lethe standardizes link-inference evaluation and provides centrality-guided forget-set selection strategies for assessing edge-unlearning methods.Source: §2 · p. 3
• Link-inference attacks test whether forgotten edges can still be reconstructed, but incompatible threat models and implementations in prior work make cross-method comparison difficult.Source: §2 · p. 3

3 Limitations of Current Evaluations

• Cora, Citeseer, and Pubmed are small enough that retraining typically takes only 3 to 5 seconds, limiting the practical value of unlearning-time savings.Source: §3 · p. 4
• On Cora, Citeseer, and Pubmed, most general MU and GU methods run in time comparable to retraining, while Fine-tuning is slightly faster.Small runtime differences may reflect statistical noise or hardware and implementation factors rather than meaningful algorithmic efficiency.Source: §3 · p. 4
• Feature-rich datasets can support strong predictions from node features alone, reducing the relative importance of graph structure and the measured effect of removing edges.Source: §3 · p. 5
• Gold Model accuracy changes by at most 3% for most architectures and datasets at 5% and 20% forget-set sizes, making accuracy an insensitive proxy for EU effectiveness.GIN is more affected by edge removal than other architectures discussed.Source: §3 · p. 5, Table 1 · p. 5

4.1 Design of Lethe

• Lethe prioritizes graphs with more than 5K nodes and 100K edges, where retraining has meaningful computational cost.Although Cora, Citeseer, and Pubmed are supported, they are omitted from the results discussion.Source: §4.1 · p. 6
• Three link inference attacks assess whether forgotten edges remain inferable, complementing accuracy, which can be uninformative on feature-rich graphs.The attacks are UMIA, Link Stealing, and LinkTeller; Lethe reports ROC-AUC over forgotten and non-existing edge pairs.Source: §4.1 · p. 6
• Lethe evaluates 8 datasets and 15 methods with three link inference attacks under low- and high-centrality settings.The benchmark is built to satisfy scale, structural-informativeness, and task-difficulty desiderata.Source: §4.1 · pp. 5–6

4.2 Settings of Edge Unlearning: WalkCentrality

• WalkCentrality is a model-agnostic measure used to create two difficulty settings because edges differ in structural redundancy and message-passing footprint.Low-centrality removals are reported as localized and having a large impact, with experiments on Photos, Computers, and DBLP.Source: §4.2 · pp. 6–7, §4.1 · p. 6
• For sparse graphs, WalkCentrality can be computed in O(k · |E|), enabling edge ranking and selection of the 5% lowest- or highest-scoring edges.Precomputed powers of the normalized adjacency matrix reduce each edge’s score to a lookup and sum.Source: §4.2 · p. 6

5 Experimental Evaluation

• The evaluation uses cached Original and Gold Models as references and benchmarks nine general-purpose machine-unlearning methods alongside six graph-unlearning methods.The Gold Model represents retraining from scratch after removing forgotten edges; attack metrics assess whether those edges remain recoverable.Source: §5 · p. 7

5.1.1 New insights from Link Inference Attacks

• Link Stealing provides the clearest method discrimination: its spread reaches at least 20 pp on three of five datasets, while accuracy is largely uninformative.Across four datasets, Link Stealing’s standard deviation is 6–18× E-UMIA’s; the supplied Table 3 caption identifies attack and accuracy metrics across methods and architectures.Source: §5.1.1 · p. 8, Table 3 · p. 8

5.1.2 Impact of centrality-based sampling

• Low-centrality forget sets remain highly exposed to LinkTeller on four of five datasets, while accuracy remains largely unchanged across centrality settings.The paired LinkTeller comparison reports W = 9591 and p < 10^-23; accuracy yields W = 3568 and p = 0.14.Source: §5.1.2 · p. 9, Figure 3 · p. 9

5.1.3 Applicability of certified methods in practice

• Certified methods do not consistently reduce attack success; on Photos, CGU and ScaleGUN worsen Link Stealing relative to Identity by 8.3 pp and 6.6 pp, respectively.The guarantee bounds parameter-space closeness to the Gold Model, not the attack-relevant geometry captured by LinkTeller and Link Stealing.Source: §5.1.3 · p. 10
• Certified methods require linear architectures such as SGC and, at a 5% forget set, are impractical by runtime on all but the smallest datasets.Their formal guarantees do not translate into consistent reduction of adversary success on link inference attacks.Source: §5.1.3 · p. 10, Figure 4 · p. 10

6 Conclusion

• Lethe combines WalkCentrality-based forget-set strategies, link inference attacks, and general-purpose machine-unlearning methods adapted to graphs in a modular EU benchmark.The benchmark is designed to support extensions with additional baselines, datasets, and measures.Source: §6 · p. 10
• The benchmark’s evaluations show that accuracy and UMIA attacks are uninformative for EU, while dedicated link inference attacks reveal limitations across methods.Lethe also finds that centrality-based forget-set selection can lead to systematic failures in defending against link inference attacks.Source: §6 · p. 10
• Lethe tests state-of-the-art link inference attacks but cannot cover all existing attacks or downstream GNN tasks, motivating an up-to-date, extensible benchmark.The code is modular and can be extended to other datasets, models, tasks, and negative-set constructions.Source: §6 · p. 10

Broader Impact

• Lethe aims to help researchers identify and correct EU weaknesses before deployment, while its public link inference attacks are inherently dual-use.The authors caution that low attack AUC means only that a specific adversary under the defined threat model cannot recover forgotten edges; benchmark datasets contain no personally identifiable information.Source: Broader Impact · p. 13

Released artifact and data access

• The released artifact includes benchmark code, configuration files, model and unlearning implementations, and link-inference attacks; datasets are publicly available and not redistributed.The data was preprocessed for compatibility with the framework architecture.Source: Released artifact and data access · p. 13

A Task and Attacks

• Edge unlearning seeks an updated model that approximates the gold model trained from scratch on the retain graph while leaking no information about the forgotten edges.The retain graph removes the edge forget set from the original graph, and the gold model is trained on that retain graph without exposure to those edges.Source: A Task and Attacks · p. 14

A.1 Link Inference Attacks

• The link-inference evaluation gives an adversary access to the unlearned model and retain graph, compares forgotten edges with balanced random non-edges, and uses attacks including UMIA and LinkTeller.The threat model withholds the original graph and forget set; UMIA uses losses for infected nodes, while LinkTeller measures feature influence on another node’s output.Source: §A.1 · pp. 14–15

A.2 Infected nodes study

• Removing 1% of edges affects 58–76% of nodes within two hops, while removing 5% affects more than 85%.These figures describe the fraction of nodes affected by two-hop neighborhood expansion; Table 4 reports averages over five random forget-set samples.Source: §A.2 · p. 15, Table 4 · p. 15

B WalkCentrality experiments

• The reported strong negative correlation indicates that higher-WalkCentrality edges are more completely absorbed by the rest of the graph after removal.The experiment correlates WalkCentrality with the increase in training loss after removing corresponding edges; Table 5 presents the correlation scores.Source: B WalkCentrality experiments · p. 15, Table 5 · p. 16
• The endpoint-displacement experiment measures how far the removed edge’s endpoints’ hidden representations move and reports the median across edges in each forget set.The passage characterizes low-centrality removals as localized and large; Table 6 covers endpoint displacement for low- and high-WalkCentrality edges.Source: B WalkCentrality experiments · p. 16, Table 6 · p. 16
• LinkTeller reaches 0.73–0.85 in the low-WalkCentrality setting and 0.38–0.64 in the high-WalkCentrality setting, consistent with its endpoint-influence measure.The authors connect the results: higher-WalkCentrality edges are more redundant, so their removal displaces endpoints less.Source: B WalkCentrality experiments · p. 16

C.1 Ablation on the attacker’s accessible information

• The LinkStealing ablation varies attacker access from the unlearned model alone to 25%, 50%, or all of the retained graph.It is tested on Photos and Flickr across unlearning methods using GCN.Source: §C.1 · p. 16
• For LinkStealing, attacker success rises with access, but it separates methods significantly with any structural access, unlike accuracy and E-UMIA.The conclusion holds with reduced access, although attack effectiveness falls substantially without structural information.Source: §C.1 · p. 16

C.2 Other forget set selection strategies

• The alternative forget sets select same-class edges for community-based removal or the oldest arXiv citation edges until 5% are removed.The experiments use GCN, a 5% forget set, and all unlearning methods.Source: §C.2 · p. 17
• Community- and time-based forget sets fall between low- and high-centrality LinkTeller values, while accuracy and UMIA remain uninformative.The time-based gap is narrower than on other datasets; community-based results exclude collapsing GNNDelete.Source: §C.2 · p. 17

C.3 Results on Link Prediction

• For link prediction, the study uses a GCN encoder and an MLP decoder; the original model reaches AUC 0.960 on Photos and 0.856 on DBLP.The experiments compare low- and high-centrality forget sets and evaluate both link inference attacks.Source: §C.3 · p. 18
• Pooled link-prediction comparisons are significant for Link Stealing (p = 3 × 10−5) and LinkTeller (p = 1 × 10−3), though the gap is smaller than for node classification.Source: §C.3 · p. 18
• On link prediction, low-centrality forget sets are more exposed to link inference than high-centrality sets across methods, datasets, and both attacks.All paired comparisons agree in direction.Source: §C.3 · p. 18
• GNNDelete also collapses under link prediction, losing 12–52 AUC points relative to the original model across datasets and settings.This is consistent with the node-classification experiments and with.Source: §C.3 · p. 18

• The Original model is the pre-unlearning reference, while the Gold model retrains from scratch after removing the forget set.Source: D Methods · p. 19
• Fine-Tuning, gradient-ascent NegGrad variants, UNSIR, distillation methods, Fisher-based scrubbing, SSD, and SalUn provide general-purpose unlearning approaches.Their mechanisms include retain-data adaptation, impair–repair, knowledge distillation, parameter dampening, and saliency-guided random-label training.Source: D Methods · p. 19
• GNNDelete inserts a trainable layer-wise deletion operator while freezing original weights, targeting deleted-edge consistency and preserved influence on neighboring nodes.Source: D Methods · p. 19
• CGU and CEU use influence-function approximations to update the GNN without full retraining and provide (ε, δ)-style certified guarantees under their assumptions.Source: D Methods · p. 20
• IDEA approximates individual training-instance effects with an instance-level certified guarantee, while ScaleGUN adds approximate propagation for scalability.UnlinkToUnlearn instead removes forget-set edges from the input graph and reruns inference with the original, unchanged weights.Source: D Methods · p. 20

E Running Experiments with Lethe

• Each JSONC configuration specifies data partitions and forget-set selection, a GNN predictor, unlearners, and evaluation metrics including runtime and link-inference attacks.The evaluator serializes results to JSON; the benchmark configurations cover dataset, architecture, and centrality-setting combinations.Source: E Running Experiments with Lethe · pp. 20–21

E.1 Extending Lethe

• Lethe resolves components from configuration files, so adding datasets, architectures, unlearning methods, or attacks requires no changes to the framework core.Custom datasets and methods use the documented PyG data interface and GraphUnlearner or GraphMeasure base classes.Source: §E.1 · pp. 21–22

F Complementary Results

• Across datasets and methods, low-centrality forget sets yield higher LinkTeller AUC, while high-centrality sets push most methods toward the 0.5 random baseline; test accuracy is nearly identical.Figure 5 presents LinkTeller AUC and test accuracy under both settings for all five benchmark datasets.Source: F Complementary Results · p. 22

F.1 Complementary Architecture Trends

• The complementary results show that Lethe’s main qualitative conclusions persist beyond GCN to GIN, GAT, and GRAPHSAGE.Figure 6 aggregates the complementary architecture results.Source: §F.1 · p. 22, Figure 6 · p. 24
• Runtime comparisons across GCN, GIN, and SGC show that UNSIR and SalUn are the two non-certified methods that fail to scale.Tables 16, 17, and 18 report runtime comparisons for GCN, GIN, and SGC, respectively.Source: §F.1 · p. 22, Table 17 · p. 24, Table 18 · p. 24
• LinkTeller remains architecture-agnostic: it is extremely high for low-centrality forget sets, while high-centrality results collapse to a much lower range across GIN, GAT, and GRAPHSAGE.GRAPHSAGE and GAT retain higher hard-setting accuracy overall, whereas GIN shows a broader spread and stronger dependence on graph structure.Source: §F.1 · p. 22, Figure 6 · p. 24

NeurIPS Paper Checklist

• The checklist answers “Yes” to declaring LLM usage and says a dedicated appendix section specifies its use in preparing the work.The checklist guidance says [N/A] applies when LLMs are not an important, original, or non-standard component of core method development.Source: NeurIPS Paper Checklist · p. 31