Is Graph Unlearning Ready for Practice? A Benchmark on Efficiency, Utility, and Forgetting
Authors: Samyak Jain
Ronak Kalvani
sainyam galhotra
Sayan Ranu
Venue: ICLR 2026 Poster (2026)
Keywords: graph unlearning
GNN
graph neural network
Primary area: datasets and benchmarks
TL;DR: Our benchmark shows that graph unlearning can rival retraining in select scenarios, but in most cases, it remains less reliable than retraining from scratch

Abstract: Graph Neural Networks (\textsc{Gnn}s) are increasingly being deployed in sensitive, user-centric applications where regulations such as the GDPR mandate the ability to remove data upon request. This has spurred interest in graph unlearning, the task of removing the influence of specific training data from a trained \textsc{Gnn}  without retraining from scratch. While several unlearning techniques have recently emerged, the field lacks a principled benchmark to assess whether these methods truly provide a practical alternative to retraining and, if so, how to choose among them for different workloads. In this work, we present the first systematic benchmark for \textsc{Gnn} unlearning, structured around three core desiderata: \emph{efficiency} (is unlearning faster than retraining?), \emph{utility} (does the unlearned model preserve predictive performance and align with the retrained gold standard?), and \emph{forgetting} (does the model genuinely eliminate the influence of removed data?). Through extensive experiments across diverse datasets and deletion scenarios, we deliver a unified assessment of existing approaches, surfacing their trade-offs and limitations. Crucially, our findings show that most unlearning techniques are not yet practical for large-scale graphs. At the same time, our benchmarking yields actionable guidelines on when unlearning can be a viable alternative to retraining and how to select among methods for different workloads, thereby charting a path for future research toward more practical, scalable, and trustworthy graph unlearning.

Published as a conference paper at ICLR 2026
Is GRAPH UNLEARNING READY FOR PRACTICE? A BENCHMARK ON EFFICIENCY, UTILITY, AND FORGET-
TING
Samyak Jain' Ronak K
Sainyam Galhotra 4.5 Sayan Ranu
"Department of Computer Science and Engineering
2 DDpaarmennt of Mathematics and Computing *Department Computer Science
3 Yardi School of Artificial Intelligence
Indian Institute of Technology Delhi, New Delhi, 110016. India CComell University
samyakjain17799gaal.. com, [mt62109520, sayanr aayanranu@cse) iitd.ac. acd. in, coduell.
ABSTRACT
Graph Neural Networks (GNNS) are increasingly being deployed in sensitive, user- centric applications where regulations such as the GDPR mandate the ability remove data upon request. This has spurred interest in graph unlearning, the task of removing the influence of specific training data from trained GNN without re- training from scratch. While several unlearning techniques have recently emerged, the field lacks principled benchmark to assess whether these methods truly pro- vide practical alternative to retraining and, if so, how to choose among them for different workloads. In this work, we present the first systematic benchmark for GNN unlearning, structured around three core desiderata: efficiency (is unlearn- ing faster than retraining?), utility (does the unlearned model preserve predictive performance and align with the retrained gold standard?), and forgetring (does the model genuinely eliminate the influence of removed data?). Through extensive experiments across diverse datasets and deletion scenarios, deliver unified assessment of existing approaches, surfacing their trade-offss and limitations. Cru- cially, our findings show that most unlearning techniques are not yet practical for large-scale graphs. At the same time, our benchmarking yields actionable guide- lines on when unlearning can viable alternative to retraining and how select among methods for different workloads, thereby charting path for future research toward more practical, scalable, and trustworthy graph unlearning.
INTRODUCTION
The ability to remove the influence of specific training data from machine learning models, com- monly referred to machine unlearning, is increasingly critical for real-world applications (Bour- toule et al., 2021] Cao and Yang, 2013). Requests for data deletion arise in practice due to evolving privacy regulations, such as the General Data Protection Regulation (GDPR) (Mantelero 2013), which grants individuals the "right to be forgotten" by requiring organizations to erase personal data upon request. Compliance with such regulations is not optional: organizations face substantial legal and financial penalties for failure to comply, making efficient unlearning a practical necessity.
A growing body of work has investigated algorithmic frameworks for GNN unlearning (Cheng al.,
2023 Li et al. 2024 Wu et al.) 2023 Dong et al. [2244] Pan et al. 2023 Chen et al.) [022 Wang al. 2023). Collectively, these works underscore the importance of graph unlearning and have established it as an active area of research.
Despite notable progress, the field still lacks a principled benchmarking framework capable of ad- dressing two fundamental questions: (I) Do existing GNN unlearning methods offer tangible advantage over retraining from scratch on the modified dataset? (2) If so, how can practitioners determine the most suitable unlearning algorithm for a given workload? Answering these questions remains clusive because current evaluations suffer from the following key gaps:
Evaluation ambiguity: Should unlearning aim to replicate the predictive performance of the gold standard (e.g.. AUC, Fl-score), the similarity of output logits, or the closeness of model parameters? Current works inconsistently adopt these metrics, leading to incomparable results and potentially misleading conclusions.
Denotes equal contribution.

---

Published as a conference paper at ICLR 2026
Efficiency retraining: For unlearning to be practically useful, it must be faster than retraining from scratch after data deletion. If an unlearning method takes longer than retraining, or exceeds GPU memory capacity, it becomes redundant regardless of its effectiveness. Yet, systematic effi- ciency comparisons against retraining on large datasets are frequently missing in existing studies.
Generalization and robustness: The difficulty of unlearning vary with graph structure (e.g.. ho- mophilous vs. heterophilous networks), deletion scenarios (e.g., random removals targeted deletions within specific communities), and GNN architectures. Yet, this diversity remains under- explored, leaving open questions about robustness and generalization. Moreover, many methods that provide "certified" unlearning rely on simplifying assumptions, such as restricting to linear GNNS (Guo al. 2023 Yi and Wei 2025). In practice, however, non-linear GNNS are far more common, and their behavior under unlearning is less understood.
To address the above gaps, our benchmarking study makes the following key contributions:
1. Comprehensive and diagnostic benchmarking framework. While prior unlearning papers evaluate some subset of utility, efficiency, and forgetting, our contribution lies in conducting the first holistic, multi-layeree diagnostic assessment of GNN unlearning. Concretely, we evaluate: (i) utility across three complementary axes axes-agett aggrrgate metries (accuracy, fidelity), per-instance outputs (logit-space deviations), and parameter-space proximity-revealinn discrepancies missed by prior single-metric evaluations; (ii) forgetting quality using a broader suite of privacy attacks, including membership inference Olatunji et al. (202I), unlearning inversion et al. (0026), and noisy-labeler attacks Sui et al. [2025); (ii) efficiency through both runtime and memory profiling, explicitly accounting for preprocessing overheads that prior work omits; and (iv) ro- bustness to realistic and adversarial deletion distributions (e.g.. degree-based. label-skewed), go- ing beyond the uniform-random setups that dominate existing evaluations. This expanded scope enables a more reliable understanding of when unlearning works, when it fails, and why.
Actionable insights and decision support. Our empirical analysis surfaces critical trade-offs across efficiency, utility, and forgetting, showing that while unlearning can sometimes approxi- mate retraining well, in many practical settings, retraining-from-scrttee remains the most com- pelling option. Our results call for re-orientation of research priorities: paradigms that em- phasize theoretical guarantees under narrow assumptions (e.g., projection or certification- based methods) offer limited practical value, while the most promising techniques must be extended with scalable, batchable implementations if they are to remain competitive with retraining.
3. Open-source implementation. We provide rich, open-source codebase covering multiple state-of-the- the- graph unlearning algorithms, ensuring reproducibility and enabling future work to build upon a common and fair experimental ground (https://gi com/ iidaaddeaaaa iitd/ UnnlearringgBBnchnarz3))
At this juncture, we note the existence of benchmarking effort on GNN unlearning (Fan et al., 2025). Our study differs in three fundamental ways. First, it goes beyond raw experimentation to provide actionable guidance: we distill empirical findings into simple principles that practitioners can use to decide when unlearning is viable and when retraining is the only realistic option. Second, unlike prior work, which measures efficacy only through aggregate metrics (e.g., AUC-ROC), we assess alignment at multiple levels spanning prediction fidelity, logit distributions, and weight space, and thereby capturing subtler divergences from retraining. Third, foreground efficiency relative to retraining as an indispensable criterion: an unlearning method slower than retraining offers little practical value, yet this baseline is overlooked. Finally, we move beyond the unrealistic assumption that deletions are uniformly random, and evaluate robustness to a wider array of disitributions.
PRELIMINARIES
Definition 2.1 (Graph). A graph is represented G = E)), where V is a finite of vertices (or nodes), E C V x V is set of edges, and X E R is a feature matrix, where each row X, E Rdd corresponds to the d-dimensional feature vector of node v E V.
We study graph unlearning in the context of the node classification.
Definition 2.2 (Node Classification with GNNS ). Given a graph G = (V,E let Vinin C V denote the set of training nodes with associated labels Ywain The learning task is to infer labels for the remaining nodes V Viaan under specified evaluation regime T E {transductive,, inductive). A GNN AGNY takes as input the dataset D = (Vimins E, X. Yrain) and outputs model parameters θ t denoted by fe, which maps nodes in V to label distributions.
AGxO (D). The trained predictor is
2

---

Published as a conference paper at ICLR 2026
Definition 2.3 (Graph Unlearning). Let G XV) be graph with training dataset D (Viain E, X, Muain). Consider a subset of training nodes AVerain S Verain that must be removed. The modified training dataset is then D' = (Virain AV E, N, Fwass)). ). where Vwasn are labels of nodes Virain VVtrain
Denote by O' + AGss (D") the parameters obtained by retraining a GNN from scratch on D'. A graph unlearning algorithm Ui takes as input the original parameters θ (trained on D) together with the removal set VVrrain and produces updated parameters Ô < U(,,, Aveass)). The objective of unlearning is twofold: (i) the unlearned model θ should be similar the gold model O' on the retained data, and (i) should forget the influence of the removed set AVerain-
Model similarity: No consensus exists on how to measure the similarity between the gold standard model O' and the unlearned model Ô. The similarity may be assessed at three different layers, each with its own advantages and limitations:
Parameter space similarity. Here, similarity is defined directly between the parameter sets O' and é, for instance, using norm-based distances such as &2 or cosine distance. If the parameters are close, then the intermediate activations at each GNN layer are also likely to be similar (See A.II, thereby providing a strong indication that the unlearned model closely matches the retrained one in terms of the functions these two models have learned.
Logit space similarity. The mapping from parameters to outputs is not one-to-one since two different parameterizations may produce similar predictions. Hence, an alternative view is to fo- on the distributions produced by the two predictors. For node e with feature X., for (x,) and fg (x,) define probability distributions over the label space. Distances between these dis- tributions can be quantified using measures such as KL-divergence, Jensen-Shannon divergence, Earth Mover's Distance (EMD), or lp distances.
Similarity in utility space. Different logit distributions may still produce similar outputs due to the discretization of the continuous logit space. Hence, the coarsest view compares task-level metrics such as training/validation loss, AUCROC, or F1-scores obtained by fee and fe-
Forgetting: Two models may exhibit high similarity and yet differ significantly in the amount of information they retain about removed nodes. Hence, forgetting must be assessed separately from utility. Just like model similarity, there is no single all-encompassing measure to quantify the extent of forgetting. We use the pronee strategy to evaluate forgetting: (i) membership information of removed nodes in the original training set, (ii) structural leakage caused by message passing, and (iii) confidence patterns correlated with the removed training signals. The technical details of how these aspects are assessed are discussed in
3 GNN UNLEARNING: THE CURRENT LANDSCAPE
Table [ characterizes existing techniques for GNN unlearning across multiple dimensions. Below, we unpack each dimension.
Unlearning Paradigm. Existing research on GNN unlearning spans several overlapping method- ological directions, each grounded in different principles for approximating retraining:
Learning-based approaches directly update or fine-tune model parameters to mimic the effect of removing training data. Examples include GNNDELETE (Cheng et al. (023) and MEGU (Li et al., 2024), which design efficient update rules or gradient-based corrections to balance unlearning effectiveness with predictive accuracy.
Influencce-unccioo and projection approaches analytically approximate the effect of remov- ing data. Influence-function methods such GIF (Wu et al., (023). IDEA (Dong et al.) 2024). ETR (Yang et al.] (2025) and GST (Pan et al. 2023) estimate how the loss landscape would change if sample were deleted and then adjust parameters accordingly. Projector (Cong and Mah- davi 2023) extends this idea by restricting updates to subspaces aligned with retraining dynamics, thereby offering guarantees of exact unlearning. However, PROJECTOR is tied to a narrowly de- fined, custom-built linear GNN and lacks the flexibility to operate on general GNN architectures.
Partition-based approaches (SISA-style) such as GRAPHERASER (Chen et al., 2022) and GUIDE (Wang et al. 2023) follow a shard-and shard-and-aggregaae and-aggregate paradigm: the graph is partitioned into smaller subgraphs (shards), and unlearning is applied only the affected shards before aggregat- ing results. While this design can be computationally efficient, is highly sensitive to partition quality and does not reflect real-world graphs that rarely shardable in natural way. Moreover,
3

---

Published as a conference paper at ICLR 2026
the guarantees of exactness provided by these methods hold only under the restrictive assumption that a separate GNN is trained per shard. If a single GNN is trained over the full graph, these guarantees break down.
Certified approaches. A distinct line of work, exemplified by Certified Graph Unlearning (Chien et al. 2022) and SCALEGUN (Yi and Wei 2025), provides formal guarantees on forgetting. How- ever, these methods restricted to very narrow setting. Specifically, they operate only on custom-designed linear GNNS because their celuuecee-functiin based updates rely on tractable gradients and Hessians, which remain low-rank and invertible only under linear message passing- This restriction prevents them from being applied to widely other non-linear GNNS, and renders non-convex optimizations inapplicable, as doing so would invalidate the theoretical guarantees. Additionally, these methods are limited to one-vs-rest (binary) classification: each class has an independent binary Hessian, whereas multiclass softmax couples parameters across classes, pro- ducing a dense Hessian that breaks the efficient update scheme. In effect, the pursuit of formal guarantees comes at the cost of practical flexibility and applicability to real-world GNN settings. Non linear methods like (Dong et al., 2024) inject noise (like gaussian noise) which lead to large error bounds on larger graphs where unlearning crucially needed as retraining from scratch is hard. This limits utility large graph.
Property. Columns 3-6 describe four important aspects of how unlearning is operationalized: Model Agnostic methods gener- alize across architectures and hence are more ver- satile. Continuous Train- ing indicates the ability to absorb new training data following a round of un- learning. Techniques that lack this capability are re- stricted to static snapshots only and hence are not de- ployment friendly. This limitation primarily arises when an unlearning algo- rithm adds additional neu- ral transformation lay- ETR
Table I: Comparison of graph unlearning methods across multiple di- mensions (GNNDELETE Gur et al. 2023). IDEA(Dong al. (002)) GST et al., 2023
et al., 2023), MEGU(Li et al. 2024
PROJECTOR Cong and Mahdavil (023). GRAPHERASER Chen et al.
2022). GUIDE
al. 2023), SCALEGUN (Yi and Weil 2025)
CGU (Chien et al. 2022), COGNAC (Koippaka et al. 2024). ETR (Yang et al. 2025)). This study covers peer-reviewed unlearning algorithms only. IF indicates Ieluence-Function
Technique
Paradigm
Properties
Model
Cont. Train.
Mode Post-hoc
Guarantee
GNNDELETE MEGU
Learning Leaming IF IF, vertified
X
Post-bat
X
GIF
X
Post-hoc
X
IDEA
Post-
X
GST
Post-hoc
X
PROJECTOR GRAPHERASER
Prujection
Train time
SISA
Train-time
GUIDE
SISA
Train-time
Cenified GU
Certified
Train-time
SCALEGUN COGNAC
Cortified
Train-time
Conrective
Post-hoe
IF. Learning
Post-hac
ers to the original GNN to unlearn. The Mode column denotes whether unlearning is applied post-
hoc (to a pre-trained model) or must be integrated into train-time procedures (e.g.. via partitioning or certification). This category also includes techniques that assume tailored GNN architecture for their unlearning method to work. Post-hoe methods are more flexible, while train-time methods provide stronger guarantees at the cost of higher training complexity. Finally, a subset of techniques provides guarantee of exactnexs or certificution. However, such guarantees invariably rely on restrictive assumptions as discussed.
4 BENCHMARKING FRAMEWORK
An effective unlearning algorithm must satisfy three fundamental constraints:
Efficiency. The algorithm should be computationally more efficient than retraining the model from scratch on the updated training data (the gold standard).
Model utility. The predictive performance of the unlearned model should remain comparable to that of the gold standard. This ensures that the removal of data does not lead to disproportionate degradation downstream tasks, making the model practically useful after unlearning-
Forgetting quality. An effective unlearning algorithm must ensure that the influence of the moved data is genuinely eliminated from the model. This requirement often mandated by legal frameworks such GDPR driven by user demands for data erasure.
We next outline the metries used assess the extent to which these constraints are satisfied.
4

---

Published as a conference paper at ICLR 2026
Table 2: Statistical overview of benchmark datasets.
Dataset
Nodes
Edges
Features
Classes
Type
Description
CORA
2,708
5,278
1,433
Homophily
Citation Network
CITESEER
3,327
4,732
3,703
Homophily
Citation Network
OGBN-Ariv
169,343
1,166,243
128
40
Homophily
Citation Network
PHOTO
7,487
119,043
745
Homophily
Co-purchasing Network
AMAZON-Rating
24,492
93,050
300
Heterophily
Rating Network
ROMAN-Empirr
22,662
32,927
300
18
Hcterophily
Article Syntax Network
Reddit
232,965
114,615,892
602
Homophily
Social Network
Efficiency. The efficiency of an unlearning algorithm is measured by its running time relative to retraining the gold-standard model. An algorithm deemed practical only if it offers tangible speedup over full retraining on the updated dataset.
Utility. Model utility assessed multiple levels:
Aggregate accuracy: The percentage of correctly classified nodes by model O i...
Acc
[[e((v) = ye]-
(1)
Viesa
DE Vae
Per-instance similarity: At the granularity of individual predictions, we evaluate:
Fidelity: The fraction of test nodes for which the unlearned model makes the same prediction as the gold-standard model O', Fidelity = Visa VEV
Σ (1)
= fer
Logit-level distance: The &2 distance between the predicted probability distributions (logits) of the unlearned and gold-standard models, averaged across all test nodes.
Fidelity and logit distance are important because two models can achieve nearly identical accuracy while making very different individual predictions. Thus, fidelity and logit distance capture per- instance agreement that aggregate metrics like accuracy alone may obscure.
Model-Ievel similarity. Finally, we compare the parameters of the unlearned model é and the gold-standard model é'. Similarity in the parameter space is measured via the Eg distance: Forgetting To quantify forgetting, adopt three complementary families of attacks, each probing a different form of residual influence from the removed set.
Membership Inference Attacks (MIA). These evaluate whether an adversary can determine if node belonged to the original training set. MIAs test basic privacy requirement, but capture only one dimension of forgetting and cannot detect structural or label-level leakage. For more details
on the mathematical formulation, please refer to App. A.2
Unlearning Inversion Attacks (UTA) (Zhang al., 2026). Inversion-based attacks attempt to reconstruct deleted edges from black-box access O These attacks detect structural leakage caused by message passing and confidence perturbations, which MIAs do not capture.
Noisy-Labeler Attacks (Sui et al. 2025). We additionally evaluate whether Ô acts "noisy la- beler." assigning removed nodes high-confidence predictions that reflect their original class mem- berships. This probes label leakage, complementing MIAs and structural leakage (UIA).
BENCHMARKING EVALUATION
As discussed in & [ our central question is when can we use an existing unlearning algorithm or should we simply retrain. Building the three pillars of efficiency, utility, and accurate forgetting of removed data, we study the following research questions (RQs):
RQ1. Utility. To what extent does an unlearned model approximate the distribution of model retrained from scratch, and under what cireumstances does this approximation break down?
RQ2. Efficiency. Do existing unlearning techniques actually offer computational savings (time
and memory) over retraining, or does retraining remain the practical baseline?
RQ3. Forgetting, Do existing unlearning algorithms successfully forget the deleted data?
RQ4. Large-scale unlearning. Can methods process multiple successive deletion requests with- out catastrophic loss in utility or efficiency?
RQ5. Robustness across workloads. How stable are unlearning methods when deletion requests come from non-random distributions (high degrees, label frequency, etc.)?
While primarily focus unlearning over node deletions, in App. A.3 and App. A.4 evaluate performance edge and feature unlearning.
also
5

---

Published as a conference paper at ICLR 2026
Table Accuracies for unlearning 10% nodes (higher is better). Best results are shaded.
Technique
CORA
CITESEER
PhотO
AMAZON-R.
ROMAN-F.
OGBN-ARXIY
GOLD (GCN)
0.88 #
0.73
0,93 =
0.43 0.01
0.41 0.00
0.60 0.01
Original Acc (GCN)
0.89 = 0.00
0.07
0.00
0.43 0.00
0,41 # 0.00
0.61 = 0.00
GOLD (PROSECTOR)
0,84 = 0.00
0.77
0.87 0.00
0.47 = 0.00
0,50 = 0.00
0.61 = 0.00
Original Acc (PROIECTOR)
0.84 + 0.00
0.70
0.87 = 0.00
0.47 = 0.00
0.50 0.00
0.61 = 0.00 0.00
MEGU
0.89 a 0.00
0.77 0.00
0.92 a 0.00
0.42 + 0.00
0.41 * 0.00
0.61 a 0.00
GIF
0.88 = 0.00
0.70
0.92 + 0.00
0.43 = 0.00
0.04
IDEA
0.87 + 0.00
0.77
0.93 = 0.00
0.41 = 0.00
0.48
0.56 0.00
PROJECTOR
0.84
0.00
0.87 0.00
0.00
0.61 0.00
GRAPHERASER
0.85 + 0.00
0.76
0.92 0.00
0.42 0.00
0.34 0.00
0.59 0.00
GNNDELETE
0.05
0.34 0.76
0.37 = 0.00
+
OOM
GST
OOM
OOM
OOM
OOM
OOM
OoM
GUIDE
0.84 # 0.00
0.05
0.85 + 0.00
0,23 0.01
0.26 0.01
OOM
COGNAC
0,84# 0.00
0.68= 0.05
0,92+ 0.01
0.45# 0.01
0.51
0.68+ 0.00
ETR
0.892 0.00
0.81= 0.05
0.93 0.01
0.41 0.01
0.30 0.00
0.582 0.00
5.1
EXPERIMENTAL SETUP
App. A.I outlines our hardware/software environment, hyperparameters, and codebase. Each exper- iment is repeated five times, and we report the mean and standard deviation. Dataset statisties are provided in Table 2 The Reddit dataset is used primarily to test scalability. By default, deletion workloads consist of nodes sampled uniformly at random unless noted otherwise. OOT indicates that algorithm failed to complete with 24 hours. OOM, the other hand, indicates exceeding the GPU memory bandwidth (A100, 40GB).
We benchmark all algorithms listed in Table I except the certification- based methods, namely SCALEGUN (Yi and Wei. 2025) and CGU (Chien et al. 2022) These two techniques are excluded from the main benchmarking they are limited to one- Vs.-all binary clas- sification and restricted to a specific class of linear GNNs. Nonetheless, for completeness, these two techniques are compared separately, and the results are presented in App. A.5
Benchmarked algorithms:
For all model-agnostic unlearning algorithms, unless otherwise specified, we use GCN as the default backbone. PROJECTOR is also restricted to linear GNNS, but unlike certification-bat it generalizes to multi-class classification. We therefore include PROJECTOR in our benchmarks for completeness, while emphasizing that its results should be interpreted with caution due to the architectural mismatch.
algorithms,
5.2 RQI. EVALUATING UTILITY
To address RQ1, we systematically compare the unlearning performance of existing techniques across multiple datasets by evaluating the changes in model behavior at four hierarchical levels of the information space: (i) prediction accuracy, (ii) output fidelity through similarity of prediction dis- tributions, (ii) representation-level differences in the logit space, and (iv) parameter-level changes. First, we analyze how the different techniques perform on these metrics at a fixed unlearning ratio. Next, we examine how varying the unlearning ratio affects their overall effectiveness.
Accuracy. In Table 3 we see that for homophilous datasets, such as CORA, CITESEER and PHOTO, the accuracy of GOLD is closely matched by MEGU, GIF, and IDEA. However, the relative per- formance ranking shifts when moving to heterophilous datasets such as AMAzON-Rating and RoMAN-Empire. Here, PROJECTOR has the highest accuracy, thanks to its eustomized linear GNN doing better than the GCN used by the rest of the algorithms. GST runs out of memory across all datasets. Hence, we omit this algorithm from further benchmarking.
Fidelity. Two models can achieve similar accuracy yet diverge in fidelity, meaning one is not truly aligned with the other. Table 4 reports the fidelity results. PROJECTOR achieves the highest fidelity overall, but this is relative to its own customized linear GNN, making the comparison with other methods less direct. The fact that PROJECTOR can exhibit lower accuracy yet superior fidelity highlights that accuracy alone is unreliable metric for assessing unlearning quality. Among GCN- based approaches, MEGU consistently achieves the strongest fidelity on average, underscoring its robustness across datasets.
Logit distance. Table(]]eeports pairwise & distances between the logits of unlearned models and the GOLD retrained models, providing a finer-grained view of distributional similarity. Unlike fidelity,

---

Published as a conference paper at ICLR 2026
Table 4: Fidelity at an unlearn ratio of 0.1 (higher is better). Projector achieves the highest fidelity
(highlighted in gold); however, it operates on a customized linear GNN specifically designed to enable 'exact' unlearning, making direct comparisons unfair. To provide fair reference, we also highlight in gray the best fidelity achieved by other methods when applied to the standard GCN.
Technique
CORA
CITESEER
PHOTO
AMAZON-R.
ROMAN-E.
Ogbn-arxiv
MEGU
0.95 1 0.00
0.85 0.01
0.99 0.00
0.84 = 0.03
0,86 1 0.00
0.91 = 0.01
GIP
0,93 : 0.01
0.82 0.01
0.97 0.00
0.87 =001
0.57 + 0.00
0.85
IDEA
0.92 + 0.00
0.83 1 0.01
0.95 : 0.00
0.82 = 0.01
0,53 + 0.00
0.76 0.00
PROJECTOR
0.99
1.00 0.00
0.99 0.00
0.00
0,98 0.00
GRAPHERASER
0,88 = 0.00
0.81 0.01
0,98 0.00
0.85 = 0.01
0.60 + 0.01
0.90 =00=00 0.01
GNNDELETE
0.79 1: 0.06
0.83 0.01
0.35 0.12
0.67 = 0.01
0.62 : 0.01
OOM
GUIDE
0.84 0.004
0.79 0.00
0.96 0.003
0.81 =
0.70 :: 0.02
OOM
Cognac
0,90 0.01
0.872 0.01
0.97:1 0.01
0.81 0.02
0.65 0.01
0.81 0.01
ETR
0.88= 0.01
0.82 0.01
0.96: 0.01
0.81 0.02
0.48 0.01
0.83 0.01
Table 5: Pairwise Logit L2 Distance (GOLD vs. Techniques) at an Unlearn Ratio of 0.1. Lower is
better. The color scheme is explained in Table 4 caption.
Technique
CORA
CITESEER
PHOTO
AMAZON-R. R.
ROMAN-E.
OGEN-ARXIV
MEGU
3.05 0.20
6.31
0.23
3.81 = 0.68
0.59 0 0.15
1.57 0.24
3.53 0.12
GIF
3.60 1600100 0.19
6,33
0,23
4,20 1 0.61
0.56 0.12
5.24 1 0.13
5,03 0.14
IDEA
18.03 + 0.80
10.06
1 0.44
22.79 + 1.88
4.69 = 0.19
22.62 = 0.64
45,79 + 0.63
PROJECTOR
0.09
0.00
0.08
0.00
0.27 0.01
0.17 1 0.00
0.42 0.01
0.41 1 0.00
GNNDELETE
5.91 031++0.22 0.26
7.36
0.19
8.57 + 0.46
1.10 + 0.06
2.64 0.16
OOM
Cognac
19.7=
27.49 0.28
0.89
0.63= 0.19
9.13+ 0.89
11.28 0.93
ETR
17.11 0.39
32.89: 0.25
5.9358:: 0.87
1.02= 0.19
5.38 0.89
7.63# 0.93
which is affected by the thresholding of logits into discrete predictions, logit distances capture dis- crepancies at the level of the entire output distribution. This makes them more sensitive diagnostic for alignment with GOLD. Note that this comparison is not meaningful for SISA-based approaches, since these techniques aggregate predictions across shards rather than using single model. As a result, we omit their logit-level evaluation.
Consistent with the fidelity results, PROJECTOR and MEGU achieves the closest alignments to gold. By contrast, IDEA exhibits substantial divergence in logit space, despite achieving reasonably strong fidelity in Table This discrepancy indicates that while IDEA often predicts the same labels as GOLD, it does so with very different confidence distributions.
Model-level distance. This analysis is only feasible for methods that preserve the original GNN architecture after unlearning- Approaches that alter the architecture, e.g., by introducing additional neural layers are not considered, since their parameters are no longer in the same space as the GOLD model. Likewise, sharding-basee based methods are also excluded because they train multiple models and aggregate their predictions, making a direct parameter-level comparison inconsistent with their design. These constraints leave us with MEGU, GIF, and IDEA.
Table reports the relative L2 distances in weight space. At an unlearning ratio of 0.1, the methods are virtually indistinguishable. As the workload increases 0.8, minor separations emerge. with MEGU showing a slight advantage. We further note that GIF and IDEA yield identical distances, since they share the same training pipeline, with differences arising only during inference.
Table 6: L2 distance between model parameters with GOLD at unlearn ratios 0.1 and 0.8. Lower is better.
Dataset
GOLD vs. GIF
GOLD vs IDEA
GOLD vs MEGU
Unleum ratio
0.1
0.8
0.1
0.8
0.1
0.8
Cora
1.27
681.97
1.27
681.97
1.27
681.38
Citeseer
1.07
439.44
1.07
439 .4
1.07
439.36
Photo
1.39
307.67
1.39
307.67
1.39
307.66
Amazon-Rating Ratings
1.39
500.69
1.39
500.69
1.39
500.72
Roman Empire
1.40
663.72
1.40
663.72
1.40
662.94
Ogbn-Arxiv
1.44
429.48
1.44
429.49
1.44
428.84
5.3
RQ2. EFFICIENCY
Time: Table 7 reports the running time of each technique. A notable finding is that MEGU, despite being the strongest performer in terms of fidelity, is slower than GOLD large datasets, and hence, making it impractical as an unlearning algorithm. GRAPHERASER and GUIDE are by far the slowest, as their shard-based preprocessing dominates the pipeline. By contrast, GIF and IDEA are generally faster than GOLD on most datasets. Worryingly, on Reddit, all algorithms except COGNAC and ETR fail to scale due to GPU memory saturation. ETR is the only method to outperform Gold on Reddit.
The hidden cost of PROJECTOR's Speed: We observe an interesting trend with PROJECTOR: is by far the fastest unlearning algorithm. Projector scales polynomially with feature dimensions,
7

---

Published as a conference paper at ICLR 2026
Table 7: Total unlearning time unlearning time (Table 22 + preprocessing time (Table 23 in sec- onds. Values in parentheses indicate the percentage of time spent in preprocessing. Cells highlighted in red exceed Gold's runtime. Cognac and Projector does not perform any pre pre-processing.
Datase
GOLD
MEGU
GIF
IDFA
GANDELRTE
GRAPHERASTR
GUIDE
PROJECTOR
COGNAC
ETR
CORA
0.65
(10%)
0.39 (31%)
0.38 (45%)
0.60 (23%%
22.93
77.86 (46%)
1.99
2.16
1665 (65%)
CITESEER
0.56
(965)
0.45 (1816)
0.45 (5256)
0.62 (231))
23.20 (44%)
81,35 (4558)
10.57
1.00
2:51 (3016)
PHotO
0.90
0.51 (100%)
0.37 (78%6)
(929)
0.87 (28%)
30,02 (4.5%
(731)
0.47
1.45
2.02 (4416)
AMAZON-R
1.70
2.50(10099)
0.34 (549)
0.47 (945)
1.24 (3588)
26. 70 (44R5)
782.20 (68%)
0.19
3.53
1.54 (49%)
ROMAN-E
1.77
2.28(10044)
0.6 (56%)
0.54 (469))
1.0 (32%)
27.1 (50%)
442.20 (75%)
0.32
123
2.68 (28%)
ARXIV
9.90
(004))
4.79 (60%)
5.31 (68%)
00M
(598))
00M
0.30
30.48
10.81 (19%)
Redai
96.73
00M
00M
00M
00M
00M
00M
197.45
54,36 (5316)
Table 8: Peak Allocated Memory (MB) in GPU.
Dusaset
GOLD
MEGU
GiF
GNNDELETE
GRAPHDEASER
PROJECTOR
GUIDE
COGNAC
ETR
COBA
39.11
162.85
38.67
85.78
60.05
98,08
1236.81
126.89
73.12
106
CITTESEER
70.16
158.58
155.12
1646.57
291.43
172.38
196
PHOTO
151.31
551.45
756.18
23
456
AMAZUN-RAIE RATENGS
146.74
309:37
594.8%
551.4]
1813,03
339,96
459.76
251.98
346
ROMAN-FMPIRE
07.34
278.09 09
407.87
405.20
680.50
100.34
250.30
172.1 I1
284
DGRN-ARXIV
1200.09
7040 49
8363.62
ODM
2125.08
265.58
00M
1907.
2406
REDDIT
2861
00M
00M
00M
00M
001
00M
00M
14464
1539
which is the dominant factor when feature dimension is larger than the number of nodes in the unlearn request (Cong and Mahdavi (203). Hence, it takes more time on cora and citeseer than ogbn-arxiv, much larger graph. However, this advantage comes with critical caveat; PROJECTOR operates on a customized linear GNN that is, on average, 100x slower to train than a standard GCN (see Table 15 Appendix). As result, the base model itself becomes challenging to train on large datasets. Since the GNN was mustom-made to make unlearning fast and exact, reporting unlearning time in isolation obscures these underlying limitations.
Memory:
Table X reports peak GPU memory usage. We find that all unlearning techniques ex- cept ETR consume more memory than GOLD. Only ETR and COGNAC are able to scale on Reddit since they support batching. Although batching is not fundamentally impossible on the remaining techniques, current implementations rely on design choices that make batching non-trivial, often leading to memory blowups large datasets. For instance, MEGU assumes an operator gate that consumes the entire graph and model outputs, making it difficult to redesign the training schema without incurring major changes in runtime and performance. GIF and IDEA rely full gradi- ent and Hessian-vector products; while approximate batching is theoretically possible, it would trade off accuracy and efficiency, and current implementations provide no stable alternatives. In GNNDELETE, its deleted-edge consistency condition, implemented by embedding all edges in the graph, breaks under batching and reindexing, making a tailored batching scheme essential. Finally, GRAPHERASER avoids batching by design through sharding, but its preprocessing overhead is so large that sharding itself dominates runtime, often exceeding the cost of retraining from scratch.
We also observe a trend in existing literature to underestimate the true cost of unlearning. Specifically, when an unlearning request arrives, the total response time not limited to updating model parameters on the residual graph. It also includes the preprocessing needed to construct the residual graph itself and to extract or organize the information required for the unlearning procedure. This preprocessing pipeline differs substantially between retraining and unlearning algorithms, and prior work has largely ignored these costs in reported runtimes. In MEGU, the reported times exclude the conversion of adjacency matrices GPU tensors and the selection of k-hop neighborhoods needed before optimization. GIF and IDEA similarly account only for fnfuuence-funetion updates, omitting the expensive steps of neighborhood identification and gradient retrieval. GNNDELETE ignores expensive preprocessing steps, including deleting edge masks, forming subgraphs, loss computation, backpropagation. and evaluations. GRAPHERASERR GUIDE separately reports partitioning, unlearning, and aggregation times, but in practice unlearning time for them should be defined as data removal from shards followed by subsequent retraining.
Runtime Measurement Gaps:
5.4 RQ3. FORGETTING
We use three complementary attack families: membership inference, inversion, and noisy-labeler at- tacks. Together, these attacks probe different facets of residual information, ranging from prediction- level leakage (MIA) to reconstruction of hidden representations (inversion) and label-dependent vulnerability (noisy-labele attacks).
We first observe from the MIA results (Fig. TT that most techniques achieve AUROC values close to 0.5, indicating that the adversary cannot reliably distinguish deleted from retained nodes. However,
8

---

Published as a conference paper at ICLR 2026
Average MIA AUROC
6:75
Average MIA AUROG G
9.70
4.70
G7
ECA
0/0
Projecor
10C4
GF
CUIDE
0,90
6:20
67A
Average MIA
S0.D
SOLD
6.13
0.37-
6,30
Cora Dataset
Photo Dataset
Roman-empire Dataset
(a) Cora
(b) Photo
(c) Roman-Empire
Figure 1: MIA Histograms. The results the remaining datasets are available in Fig.
Table 9: AUCROC on Inversion attack Zhang et al.
2026 An AUCROC close to 0.5 is better.
Method
CORA
CITESEER
AMAZON-R.
ROMAN-E.
OGEN-ARXIV
MEGU
0.53 0.01
0.54
0.53 = 0.01
0.51 0.00
0.00
GIP
0.53 + 0.02
0.54 + 0.01
0.53 + 0.01
0.51 + 0.00
0.51 +.00
0.50 + 0.00
IDEA
0.52 1: 0.01
0.54 1: 0.01
0.53 0:01
0.51 0:000
0.51 0.00
0.50 0.00
GNNDELETE
0.78 + 0.05
0.90
0.80 0.12
0.95
0.80+ 0.01
00M
PROJECTOR
0.60 + 0.02
0.57 + 0.00
0.53 + 0.01
0.60 +.001
0.52 0.00
0.56 + 0.00
GRAPHERASER
GUIDE
0.53 + 0.00
0.54 + 0.01
0.53
+ 0.01
0.51 0.00
0.51 + 0.00
0OM
COGNAC
0.54 0.00
0.58
1. 0.01
0.54
1: 0.01
0.51 0.000
0.52 0.521.000
0.50
ETR
0.54++0.0
0.53 + 0.01
0.33
0.01
0.51 0.00
0.51 0.00
0.50
PROJECTOR, GRAPHERASER, and GNNDELETE deviate noticeably from 0.5, revealing that these methods continue leak membership information despite unlearning.
The inversion attack results reported in Table 9 sharpen this conclusion. Methods such as MEGU, GIF, IDEA, TRAPHERASERR and GUIDE achieve AUROC values extremely close 0.5 across all datasets, suggesting that even an adversary with access to logits cannot reconstruct discriminative representations of the deleted nodes. In stark contrast, GNNDELETE exhibits severe vulnerability, with AUROC values ranging from 0.78 to 0.95, and PROJECTOR shows moderate but consistent degradation, further confirming that these approaches leave behind strong representational signa- tures of the forgotten nodes.
A similar pattern appears under the noisy- attack (Table 24 Nearly all methods maintain AUROC values indistinguishable from random guessing, but GNNDELETE again shows clear sus- ceptibility, particularly on larger graphs such as Amazon-Ratings The consistency of these failures across all three attack families indicates that certain structural characteristics in GNNDELETE (and, to lesser extent, PROJECTOR) prevent complete removal of the influence of deleted nodes.
5.5
RQ4: ROBUSTNESS TO LARGE-SCALE UNLFARNING
Fig. investigates RQ4 by examining how accuracy, fidelity and logit distance evolve with increas- ing unlearn ratios on the CORA dataset. In this setting, curves that remain close to the GOLD re- trained model would indicate faithful alignment between unlearning and retraining. Note that nodes are deleted only from the training set. Interestingly, gold accuracy drops to less than 0.2 when 80% of the nodes are removed but MEGU, GIF, and IDEA largely unaffected. Additionally, we notice that the fidelity of these techniques drops, and logit distance continuously increases with increas- ing unlearning ratio. Stability of accuracy and continuous degradation of fidelity and logit distance suggests the possibility of unfaithful forgetting under high deletion workloads.
5.6 RQ5: ROBUSTNESS TO WORKLOAD DISTRIBUTIONS
Node deletion: Table I0 reports fidelity under five strategies: (i) random
Table 10: Fidelity of different techniques under various node deletion strategies for the Cora dataset (Unlearn ratio 0.1). Higher fidelity indi- cates closer alignment with GOLD.
nodes, (ii) nodes from the most frequent label class, (iii) nodes with second most frequent label class, (iv) low-degree nodes, and (v) high-degree nodes. Two key patterns emerge. generally easier to handle.
Technique
Random
High Freq
2nd High Freq
Low Degree
High Degree
0.95
0.95
0.92
0.96
Geneel
0.79 = 0106
0.92
0.82
0.91
0.69
0.93
0.93
0.89
0.89
IDEA PROJECTOR
(1.2 = 01.00
0.91
0.88
0.90
0.89
0.99 0.00
0.97
0.92
0.90
GRAPH FRASER
0.38 0.00
0.90
0.74
0.91
0.87
Random deletions and those from the highest frequency classes Random deletions preserve the overall topology and label distribution. Deletions from the highest-frqquency class have limited impact, e.g., in Cora, this class is twice
9

---

Published as a conference paper at ICLR 2026
Accuracy vs Unlearn Ratio
Fidelity vs Unleam Ratio
Logit vs Unleam Ratio
Accuracy
Fidelity
to Min
Unlearn Ratio
Unlearn Ratio
Unleam Ratio
(a) Accuracy
(b) Fidelity
(c) Logit distance
Figure 2: Accuracy vs. Unlearn Ratio plot over all techniques.
as large as the second-highest, so its dominance persists even after removing 10% of its nodes. Deletions from low-degree classes, also dont cause much effect because they affect embeddings of very few nodes. In contrast, deleting high-degree nodes destabilizes message passing by removing structural hubs, producing widespread embedding changes. Similarly, removing nodes from the second-mox most frequent class is disruptive: these nodes are numerous enough to influence learning but not dominant enough to absorb the effect, so their removal shifts class distributions unpredictably. Overall, MEGU demonstrates the highest robustness to deletion distributions. These results also highlight that structured deletion requests reveal vulnerabilities hidden by random removals, highlighting the need to evaluate unlearning under targeted deletion scenarios.
GNN architecture: Tables 12 in the Appendix evaluate robustness across different GNN back- bones. MEGU delivers the most reliable performance across architectures. Overall, we do not observe a clear trend suggesting that any specific architecture is inherently harder to unlearn.
6 CONCLUDING INSIGHTS
Table II distills the key insights across the three pil- lars of efficiency and sclability, utility preservation, and faithful forgetting.
Table 11: Evaluation of graph unlearning
techniques against the three pillars: Effi ciency, Utility, and Forgetting. A v indi- cates the pillar is satisfied; a x indicates a violation. indicates partial satisfaction.
Efficiency and Scalability. Unlearning is most valu- able when retraining prohibitively expensive. Yet, all algorithms except COGNAC and ETR, fail pre- cisely in this regime (such as REDDIT). Several meth- ods incur substantial preprocessing overheads or rely on computationally intensive subgraph extraction and optimization steps, making them slower than retrain- ing. While MEGU, GIF, and IDEA offer faster unlearning times than retraining, their large memory footprints prohibit them from scaling to Reddit.
Technique
Efficiency
Utility
Forgetting
GUIDE
PROJECTOR
GNNDELETE
X
GNNERASER
Y
GIF
V
IDEA
V
MEGU
V
COGNAC
X
ETR
Utility Preservation. The utility of unlearned model is ideally measured relative to the retrain-froe from-sst "Gold" model. While accuracy re- mains the most commonly reported proxy, our expanded metrics, fidelity and logit distance, reveal deeper trends. Several methods, such as COGNAC and ETR, achieve competitive accuracy but devi- ate substantially in logit-space or parameter-space indicating that the underlying models differ from the Gold solution even when predictions appear similar. In contrast, methods such as MEGU, GIF, and IDEA exhibit consistently high fidelity and low logit divergence.
Forgetting Quality. Robustness to attacks is handled well by most methods except PROJECTOR, GNNDELFTE, and GRAPHERASER. COGNAC shows hints of topological information leakage in inversion attacks.
Decision-Making Guidance. The ideal method is one that has a / on each of the pillars in Ta- ble 11 However, no such method exists currently. On small and medium graphs, MEGU, GIF, and IDEA remain the most dependable choices, providing strong accuracy, alignment with GOLD, and robust forgetting. On large graphs where retraining expensive, ETR currently offers the best compromise: it scales, surpasses retraining in efficiency on the largest dataset, and exhibits solid forgetting performance, albeit with reduced geometric fidelity.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
We acknowledge the Yardi School of AI, IIT Delhi for supporting this research. This work was par- tially supported by the CSE Research Acceleration Fund of IIT Delhi. Samyak Jain acknowledges CSE dept IIT Delhi for sponsoring his travel to ICLR26. Sainyam Galhotra's work was supported by ARO grant 1911NF-25-1-0255 findings, and conclusions recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsors.
BSF grant 2024101, and a grant from Infosys. Any opinions,
REPRODUCIBILITY
To ensure full reproducibility of our experiments, we provide the following:
Code and Documentation. Our complete codebase publicly available through GitHub repos- itory https://github. included, which documents installation, usage instructions, and experiment configurations. Each technique is integrated from its publicly released implementation, with general configurations and hyperparameters made accessible through command line arguments. Default values for all hyper- parameters are included in the code, and all scripts are fully commented and seeded for consistent reproducibility.
Bew.eiinnnneennhhrrt.. A detailed README file is
Datasets. We conduct experiments on widely used benchmark datasets: Cora, Citeseer, OGBN- Arxiv, Photo, Amazon-Ratings Roman-Empai and Reddit (see Table 2). All datasets are pub- licly available through standard repositories such as PoTcr Geometric and OGB. Dataset statistics provided in the main paper for clarity.
Hyperparameters. All hyperparameters (e.g., learning rate, weight decay, number of epochs, learning budgets) are specified in the codebase via an argument parser. For each baseline technique, follow the configurations recommended in the respective papers, ensuring fairness and consis- tency.
We provide enviromment configuration files (e.g., requirements txt and conda yaml) that specify all dependencies. Our experiments were run on the following system setup:
Environment.
CPU: 96 logical cores
RAM: 512 GB
GPU: NVIDIA A100-PCIe-40GB
Operating System: Ubuntu 20.04.4 LTS
TyTorc Version: 1.13.1+cul17
CUDA Version: 11.7
PyTorc Geometric Version: 2.3.1
REFERENCES
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 202/ IEEE symposium security and privacy (SP), pages 141-159. IEEE, 2021.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pages 463-480. IEEE, 2015.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang Graph unlearning. In Proceedings of the 2022 ACM SIGSAC conference on computer and com- munications security, pages 499-513, 2022.
11

---

Published as a conference paper at ICLR 2026
Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, and Marinka Zitnik. GNNDelete: A gen- eral strategy for unlearning in graph neural networks. In The Eleventh International Conference on Learning Representations, 2023. URL httpss://pperreiieee www.ee..eeeeteeeeeeeeeeeeeeeeeee aott:/oorummdddXXOOttiiii
Eli Chien, Chao Pan, and Olgica Milenkovic. Certified graph unlearning, In NeurIPS GLFrontiers Workshop, 2022.
Weilin Cong and Mehrdad Mahdavi. Efficiently forgetting what you have learned in graph represen- tation learning via projection. In International Conference on Artificial Intelligence and Statistics, pages 6674 PMLR, 2023.
Yushun Dong. Binchi Zhang, Zhenyu Lei, Na Zou, and Jundong Li. Idea: A flexible framework of certified unlearning for graph neural networks. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 621-630. 2024.
Bowen Fan, Yuming Ai, Xunkai Li, Zhilin Guo, Rong-Hua Li, and Guoren Wang. Opengu: A comprehensive benchmark for graph unlearning. arXiv preprint (eXiv:2501.02228 2025.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens van der Maaten, Certified data removal from machine learning models, 2023. https://: www. htabs//9991.1.. 03030
Varshita Kolipaka, Akshit Sinha, Debangan Mishra, Sumit Kumar, Arvindh Arun, Shashwat Goel, and Ponnurangam Kumaraguru. A cognae shot to forget bad memories: Corrective unlearning in gnns. arXiv preprint arXi::2412.0077 2024.
Xunkai Li, Yulin Zhao, Zhengyu Wu, Wentao Zhang. Rong-Hua Li, and Guoren Wang. Towards effective and general graph unlearning via mutual evolution. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 38, pages 13682-13690, 2024.
Alessandro Mantelero. The eu proposal for a general data protection regulation and the roots of the 'right to be forgotten'. Computer Law & Security Review, 29(3):229-23,, 2013.
Iyiola E Olatunji, Wolfgang Nejdl, and Megha Khosla. Membership inference attack on graph neural networks. In 2021 Third IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA), pages 11-20. IEEE, 2021.
Chao Pan, Eli Chien, and Olgica Milenkovic. Unlearning graph classifiers with limited data sources. In Proceedings of the ACM Web Conference 2023, pages 716-726, 2023.
Levi Rauchwerger, Stefanie Jegelka, and Ron Levie. Generalization, expressivity, and universality of graph neural networks on attributed graphs In ICLR, 2025.
Zhihao Sui, Liang Hu, Jian Cao, Dora D. Liu, Usman Naseem, Zhongyuan Lai, and Qi Zhang. Re- calling the forgotten class memberships: Unlearned models can be noisy labelers to leak privacy. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), 2025.
Cheng-Long Wang, Mengdi Huai, and Di Wang. Inductive graph unlearning. In 32nd USENIX
Security Symposium (USENIX Security 23), pages 3205-3222, 2023.
Jiancan WU, Yi Yang. Yuchun Qian, Yongduo Sui, Xiang Wang, and Xiangnan He. Gift A general graph unlearning strategy via influence function. In Proceedings of the ACM Web Conference 2023, pages 651-661, 2023.
Zhe-Rui Yang. Jindong Han, Chang-Dong Wang, and Hao Liu. Erase then rectify: trriiiing-fre free pa- rameter editing approach for cost-effective graph unlearning. In Proceedings of the Thirty-iinth AAAI Conference on Artificial Intelligence and Thirty-Sevent Conference on Innovative Appli- cations of Artificial Intelligence and Fifieenth Symposium on Educational Advances in Artificial Intelligence, 2025.
Lu Yi and Zhewei Wei. Scalable and certifiable graph unlearning: Overcoming the approximation error barrier. In ICLR, 2025.
Jiahao Zhang, Yilong Wang, Zhiwei Zhang, Xiaorui Liu, and Suhang Wang. Unlearning inversion attacks for graph neural networks. In Proceedings of the 19th ACM International Conference on Web Search and Data Mining (WSDM), 2026.
12

---

Published as a conference paper at ICLR 2026
A APPENDIX
Lemma A.1 (Similarity of Activations Under Similar Parameters). Let fe be a passage-passing GNN with parameters θ, using standard aggregation functions (mean/sum/maxx and activation functions (RELU, sigmoid, or tanh). If e' denotes the parameters of the gold model and @ the parameters of an unlearned model, then the intermediate activations satisfy
| 10 (0') (b)] < Le
for some layer-dependent Lipschitz constant Lę 0. Thus, the parameters close, the activa- tions at every layer are also close.
Proof. Rauchwerger et al. (2025) show that message parggggassiingggggg GNN layers are Lipschitz continuous.
Let Lg denote the Lipschitz constant of layer l. For a generic MPNN layer of the form
h (e+1) o We (G uEN()))))
the Lipschitz constant satisfies
L LAGe Well.
where LAgG Lipschitz constant the aggregator (LAGG = 1 for mean/max, and LAgG S dmax for sum aggregation). Since common activations such ReLU, tanh, and sigmoid are at most 1-Lipschitz, they do not enlarge the bound.
Because the composition of Lipschitz functions is Lipschitz, the entire L-layer GNN satisfies
-h
II Le 1|0' - +1|.
Thus, if the parameters of the Gold model @' and the unlearned model Ô close, then their intermediate activations at every layer are also guaranteed to be close, up to the (typically small) product of per-layer Lipschitz constants
A.1 EXPERIMENTAL SETUP
For the baseline algorithms, we use the code available at OpenGU Fan et al. (2025). Our code- base and an integrated framework to evaluate all baselines is released at https: /tttps://githutt h/gggttubbc.o com/ Lida-iiaa/bnleerrnnn..eeeee Benchmark
A.1.1 HARDWARE CONFIGURATION
All experiments were conducted on high performacce computing system with the following spec- ifications:
CPU: 96 logical cores
RAM: 512 GB
GPU: NVIDIA A100-PCIE-40GB
1.2
SOFTWARE CONFIGURATION
The software environment for our experiments was configured as follows:
Operating System: Linux (Ubuntu 20.04.4 LTS (GNU/Linux 5.4.0- 1..00-124-geerr x86_64))
Tororch Version: 1.1.1+ccl17
CUDA Version: 11.7
Py Torch Geometric Version: 2.3.1
"oodem GNNs shallow, with T. < 3, the Lipschitz product does explode in practice.
13

---

Published as a conference paper at ICLR 2026
Table 12: Test accuracies (# std) of different unlearning methods across datasets and base models. "OOM" denotes out-of-memon Best values are highlighted among unl unlearning methods only.
Dataset
Base Model
Original
GOLD
MEGU
GNN Delete
GIF
IDEA
GruphEraser
GST
0.00
0.00
0.76
0.57
Cora
GAT
0.59 + 0.00
0.88 + 0.00
0.88 + 0.01
0.78 + 0.02
0.84 + 0.01
0.84 + 0.01
0.85 + 0.01
OOM
GIN
0.58 0.00
0.88 0.01
0.87 0.00
0.71 4: 0.055
0.52
0.01
0.52 0.01
0.83 0.00
OOM
GCx
0.77 1 0.00
0.73
0.01
0.77 0.00
0.76 1: 0.01
0.76 1 0.00
0.77 1: 0.00
0.77 1: 0.01
OOM
Citeseer
GAT
0.75 + 0.00
0.74 0.01
0.74 + 0.01
0.72 + 0.01
0.72 + 0.01
0.72 0.01
0.73 + 0.01
OOM
0.00
0.01
0.01
0.02
0.75
GCN
0,92 1: 0.00
0.93 0.00
0.92 0.00
0.34 1: 0.11
0.92 0.00
0.93 1 0.00
0.92 1: 0.00
OOM
Photo
GAT
1.93+:0.00
0.00
0:002
+
0.90
0.73
OOM
GIN
0.78 0.00
0.76 0.08
0.78 0.00
0.14 4: 0.05
0.75 0.00
0.76 +: 0.00
0.89 + 0.00
OOM
GCN
0.43 0.00
0.43
0.42 0.00
0.37 1: 0.00
0.43 1: 0.00
0.41 0.00
0.44
OOM
Amazon-KR R.
GAT
0,46 0.00
0,46 0.00
0,45 0.00
0338 1: 0.00
0.40 0.01
0.41 1: 0.01
0.41 1 0.00
OOM
GIN
01.55 0.00
0.00 0.43
0.42 + 0.01
0.38 + 0.01
0.43 + 0.00
0.43 + 0.00
0.41 + 0.01
OOM
GCN
0.00
0.00
0.00
0.44
0.48
0.41
Roman-E. E.
GAT
0.52 1 0.00
0.49 0.00
0.41 0.02
0.34 1: 0.00
0.41 1: 0.00
0.41 1 0.00
0.28 1: 0.00
OOM
GIN
0.45 0.00
0.00
0.00
0.33 0.00
0.43 +
0.43
0.36
0OM
A.1.3 HYPERPARAMETERS
For all the algorithms, have used their default unlearning arguments and hyperparameters. We use the same basclinn GCN for all techniques and consistent seeds to across techniques to reduce bias and ensure fairness. More details of the parameters for each algo can be seen in our codebase.
A.2 FORGETTING VIA MEMBERSHIP INFERENCE ATTACKS
MIAs test whether an unlearned model can still leak information about the deleted nodes' training membership. In the standard formulation, attack model is trained to distinguish members (training samples) from non-members (test samples) using the posterior distributions (class probabilities) of target model as input.
We adapt this methodology to the unlearning setting by designing a shadow attack model based on the change in posteriors before and after unlearning. Specifically, for each node we compute the & norm between its posterior probability vector produced by the original model and the corresponding vector after unlearning. Intuitively, member nodes (those originally in the training set and later targeted for unlearning) should undergo larger shifts in their posteriors than non-member nodes. We then label deleted training nodes positive instances (members) and an equal number of test nodes as negative instances (non-members). Using these labels and the posterior-change scores, we compute the AUROC. AUROC quantifies the attack's discriminative power: values close 0.5 indicate random guessing and thus strong protection, while higher values imply that the unlearned model still leaks membership information and has not fully forgotten.
Average AUROC
Average MIA AUROC
370
Prgede: GlMieekts
GF
230
Pigedar
I0CA
GF
370
Figedar
I36A
GUIDE
845
3:00
MEmU
Coonec
Menu
310
AOLD
455
BOLD
ETH
BOLD
ETh
455
810
140
Citeseer Dataset
Amazon-ratings Dataset
OGBN-arxiv Dataset
(a) Citesecr
(b) Amazon-ratings
(c) Ogbn-arxiv
Figure 3: MIA Histograms to evaluate forgetting.
14

---

Published as a conference paper at ICLR 2026
Table 13: Fidelity results across datasets, base models, and unlearning methods. PROJECTOR is ommitted since it cannot handle generic GNNs.
Dataset
Base Model
MEGU
GIF
IDEA
GNN Delete
GraphEraser
GST
GCN
0.95 1 0.00
0.93 1 0.01
0.92 1 0.00
0.79 1 0.06
0.88 1 0.00
OOM
Cora
GAT
0.93 1 0.01
0.87 + 0.01
0.87
0.00
0.81 1 0.02
0.90 0.01
OOM
GIN
0.95 + 0.01
0.86 = 0.01
0.86 0.00
0.75 + 0.06
0.89 0.02
OOM
GCN
0.85 = 0.01
0.82 0.01
0.83 0.01
0.83 + 0.01
0.81 0.01
OOM
Citeseer
GAT
0.89 + 0.01
0.84 0.01
0.83 0.00
0.88 + 0.01
0.88 0.01
0OM
GIN
0.89 + 0.01
0.81 + 0.01
0.81 0.00
0.81 + 0.02
0.82 0.01
0OM
GCN
0.99 0.00
0.97
0.95
0.35 + 0.12
0.00
OOM
Photo
GAT
0.84 0.07
0.84 0.08
0.008
0.13
0.77
OOM
GIN
0.75 0.05
0.72 0.05
0.06
0.12 0.08
0.79
OOM
GCN
0.84 + 0.03
0.87 + 0.01
0.82 + 0.01
0.67 + 0.01
0.83 0.01
OOM
Amazon-R. R.
GAT
0.79 + 0.03
0.62 + 0.01
0.64 + 0.01
0.59 +: 0.03
0.71 0.03
OOM
GIN
0.76 1 0.04
0.72 0.02
0.72 0.02
0.66 0.04
0.77 0.02
OOM
GCN
0.86 + 0.00
0.57 + 0.00
0.53 0.00
0.62 0.00
0.60 0.60 0.01
OOM
Roman-E.
GAT
0.68 + 0.03
0.44 0.00
0.44
0.001
0.49 0.01
OOM
GIN
0.83 + 0.01
0.53 + 0.00
0.53 +.00
0.55 + 0.00
0.65 = 0.00
00M
Table 14: Logit distance results across datasets, base models, and unlearming methods (lower is better). PROJECTOR and GRAPHERASER are omitted since PROJECTOR does not handle heneric GNNs and GRAPHÉRASER uses sharding.
Dataset
Base Model
MEGU
GIF
IDEA
GNN Delete
GST
GCN
3.05 0.20
3.60 0.19
18.03 1 0.80
5.91 +: 0.26
OOM
Cora
GAT
10.86 1: 2.01
10.74 1.49
10.68 1.49
12.05 +:: 1.39
OOM
GIN
3.86 = 0.28
6.38 0.23
6.38 + 0.23
7.36 = 0.28
OOM
GCN
6.31 0.23
6.33 0.23
10.06 0.44
7.36 + 0.19
OOM
Citeseer
GAT
12.74 + 2.35
15.52 3.60
15.45 3.65
13.10 + 3.10
OOM
GIN
5.32 + 0.65
7.23 + 0.91
7.23 + 0.91
8.07 + 0.95
0OM
GCN
3.81
4.20 0.61
22.79 1.88
8.57 1:
0OM
Photo
GAT
23.90 + 20.07
23.39
20.34
23.35 + 20.34
23.32 + 20.46
0OM
GIN
34.75 + 2.96
25.62 + 3.53
25.54 + 3.61
64.22 + 24.42
00M
GCN
0.59 0.15
0.56 0.12
+ 0.19
1.10
0OM
Amazon-R.
GAT
1.32 = 0.34
1.70 0.07
1.69 + 0.07
OOM
GIN
1.61 + 0.48
1.83 + 0.36
1.84 + 0.36
2.04 - 0.46
0OM
GCN
1.57 0.24
5.24 0.13
22.62 + 0.64
2.64 + 0.16
0OM
Roman-E
GAT
6.91 + 0.95
19.42 + 0.60
19.36 1 0.62
7.11 + 0.52
OOM
GIN
2.42 1 0.10
5.97 + 0.09
5.97 + 0.09
3.93 + 0.08
OOM
Table 15: Accuracies and training times achieved by the Original model and GOLD model Pro- jector and vanilla GCN.
Dataset
Original Acc.
GOLD Acc.
GCN Training Time
Pro.GNN Training Time
Cora
0.8392 + 0.0000
0.8362 + 0.0043
0.4822 + 0.3140
33.3136 +: 2.4494
Citeseer
0.7639 1 0.0000
0.7654 0.0016
0.4765 1 0.3378
53,8463 =: 32.8146
Photo
0.8693 0.0000
0.8701
0.0017
0.5703 + 0.3294
220.2981 10.2529
Amazon-ratings
0.4741 + 0.0000
0.4723
0.0023
1.0025 1 0.3326
288.1078 405.8160
Roman-empire
0.4947 + 0.0000
0.4969
0.0023
0.9746 + 0.3257
90.0904 +
OGBN arixv
0.6126 + 0.0000
0.6124 0.0009
10.2016 + 0.4677
11856.62 + 1018.27
A.3 EDGE UNLEARNING
we report accuracy, fidelity, and logit-level L2 distance relative to the gold stan- dard under the setting where 10% edges deleted uniformly random. The results exhibit trends
In Tables 16 18
15

---

Published as a conference paper at ICLR 2026
consistent with the node-deletion setting: MEGU continues to deliver stable and competitive perfor- mance, typically achieving the best results or performing very close to the top method.
Table 16: Accuracies for edge-deletion experiment (higher is better). Best results are shaded.
Technique
CORA
CITESEER
Рhoтo
AMAZON-R.
ROMAN-E.
Original
0.88 + 0,00
0.76 = 0.00
0.92 + 0.01
0,43 + 0.00
0,41 = 0.00
GOLD
0.88 0.00
0.73 + 0.00
0.92 0.01
0.43 + 0.01
0.41 + 0.00
MEGU
0.88 0.00
0.76 + 0.00
0.91 0.00
0.42 + 0.00
0.40 + 0.00
GIF
0.89 0.00
0.76 + 0.02
0.92 0.02
0.43 0.02
0.37 + 0.00
IDEA
0.88 + 0.00
0.76 + 0.01
0.92 0.00
0.00
0.46 0.00
GNNDELETE
0.62 0.07
0.70
0.26
0.00
0.19
GRAPHERASER
0.88 + 0.00
0.76 0.01
0.92 0.02
0.00
GUIDE
0.83 0.00
0.75 = 0.00
0.90
0.00
0.37 = 0.00
COGNAC
0.83 0.01
0.68 + 0.01
0.91 0.01
0.45 + 0.01
0.48 + 0.01
Table 17: Fidelity scores for edge-deletion experiment (higher is better). Best results are shaded.
Technique
CORA
CITESEER
РHOтO
AMAZON-R.
ROMAN-F.
MEGU
0.96 + 0.01
0.86 + 0.01
0.97 + 0.01
0.88 + 0.02
0.82 + 0.01
GIF
0,95 + 0.01
0.85 + 0.01
0.98 = 0.00
0.92 0.01
0.73 + 0,00
IDEA
0.94 0.01
0.86 + 0.01
0.96 = 0.00
0.85 + 0.00
0.69 + 0.01
GNNDELETE
0.64 + 0.08
0.77 + 0.03
0.27 + 0.06
0.64 + 0.01
0.00 1 0.00
GRAPHERASER
0.95 0.01
0.84 0.01
0.99 0.00
0.92 0.00
0.87 1 0.01
GUIDE
0.84 + 0.01
0.79 + 0.00
0.96 = 0.00
0.81 + 0.00
0.69 = 0.02
COGNAC
0.92 0.00
0.87 0.00
0.97 0.01
0.75 0.004
0.64 + 0.004
Table 18: L2 distance for edge-deletion experiment (lower is better). Best values are shaded.
Technique
CoRA
CITESEER
Рhото
AMAZON-R. R.
ROMAN-E. E.
MEGU
2.89 + 0.20
6.23 = 0.21
4.64 + 0.81
0.53 = 0.07
1.51 + 0.15
GIF
2.94 + 0.19
6.21 + 0.22
3.86 + 0.67
0.36 = 0.10
2.17 0.13
IDEA
17.88 + 0.83
10.01 + 0.51
21.99 0.94
4.65 0.19
- 0.62
GNNDELETE
7.08 + 0.18
7.84 + 0.16
8.98 + 0.33
1.04 = 0.02
3.35 + 0.07
COGNAC
16.35 = 1.02
21.86 + 0.07
6.08 + 0.41
0.75 + 0.005
5.74 +
A.4 FEATURE UNLEARNING
Following the standard feature-unlearning protocol Li et al. (2024). we sample 10% of the nodes uniformly random and mask out their features. The corresponding results are reported in Ta- bles 19 21 The overall patterns remain consistent with earlier observations: MEGU continues to deliver the most robust performance across all metrics.
A.5 PERFORMANCE OF LINEAR GNNs
Certified Unlearning. We evaluate the two certified graph-unlearing algorithms, CGU and SCALEGUN, using the official implementations released by their authors. Both methods offer formal guarantees of exact forgetting, but these guarantees hold only under highly restrictive assumptions: (i) the underlying GNN must be a custom linear message-passing architecture, and (ii) the predic- tion task must be binary node classification. As result, neither method supports multi-class node classification natively. For SCALEGUN, multi-class datasets must be decomposed into a one-vs-rest collection of binary tasks; CGU imposes similar constraints due to the structure of its certified up- date rule. Consequently, the metrics produced by these algorithms are not directly comparable to those of unlearning methods that operate in the full multi-class setting.
16

---

Published as a conference paper at ICLR 2026
Table 19: Accuracies for the feature-deletion experiment (higher is better). Best results are shaded.
Technique
CORA
CITESEER
PHOтO
AMAZON-R.
ROMAN-E.
Original
0.89 = 0.00
0.77 0.00
0.92 0.00
0.44 0.00
0.41 0.00
GOLDD
0.89 + 0.01
0.73 + 0.00
0.92 + 0.00
0.43 + 0.00
0.40 + 0.00
MEGU
0.89 0.00
0.77 0.00
0.92 0.00
0.43
0.41 0.00
GIF
0.89
0.77
0.93
0.44
0.42
IDEA
0.88 0.00
0.07
0.00
0.42
0.49
GNNDELETE
0.76 0.03
0.35 0.06
0.00
0.31 0.00
GRAPHERASER
0.89 0.01
0.01
0.93 = 0.01
0.44 0.01
0,42 - 0.00
GUIDE
0.84 + 0.01
0.75
0.91 0.00
0.42 0.00
0.38 0.01
Table 20: Fidelity scores for feature-deletion experiment (higher is better). Best results are shaded.
Technique
CORA
CITESEER
РhoтO
AMAZON-R.
ROMAN-E. E.
MEGU
0.96 = 0.00
0.85
0.98 = 0.00
0.87 0.03
0.86 = 0.00
GIF
0.95 0.01
0.85
0.98 # 0.01
0.89 = 0.01
0.80 0.01
IDEA
0.94 + 0.00
0.00
0.95 0.00
0.83 0.01
0.71 + 0.01
GNNDELETE
0.81 0.03
0.06 0.02
0.08
0.55 0.02
GRAPHERASER
0.95 0.01
0.00
0.98
0.89
0.80 0.01
GUIDE
0.84
0.79
0.96 - 0.00
0.82 - 0.01
0.69 + 0.02
Empirically, both CGU and SCALEGUN exhibit competitive accuracy and high fidelity on ho- mophilous datasets such CORA, CITESEER, PHOΤO,, and OGBN-ARXIV, with their unlearned performance remaining close to the Gold (retrain-from-scratch)) model. However, their behavior diverges sharply heterophilous datasets. SCALEGUN suffers substantial drops in accuracy and fidelity on AMAZON- -AAINNG and ROMAN-EMPIRE indicating brittle performance outside of the linear, homophilous regime for which is designed. In contrast, CGU remains comparatively stable across these datasets, showing no analogous collapse in utility.
Overall, evaluation highlights common limitation of certified graph-unlearning algorithms: although theoretically appealing, they currently apply only to narrow classes of linear binary GNNS and do not yet offer practical, general-purpose solution for real-world multi-class graph learning. Their results should therefore be interpreted as establishing a theoretical baseline, rather than as direct competitors to unlearning methods that operate on expressive, modern GNN architectures.
A.6 DISCLAIMER
We note that LLM was used to polish the writing. The LLM output was not used is but was proofread for both grammatical and semantic correctness by the authors before being used in our manuscript.
17

---

Published as a conference paper at ICLR 2026
Table 21: L2 distance for feature-deletion experiment (lower is better). Best results are shaded.
Technique
CORA
CITESEER
Рното
AMAZON-R.
ROMAN-E.
MEGU
3.49 + 0.29
7.16 + 0.23
4.62 = 0.99
0.48 + 0.05
1.57 + 0.24
GIF
3.81 0.25
7.39 0.22
4.89 0.92
0.47 = 0.07
2.03 + 0.22
IDEA
16.85 + 0.85
10.49 0.48
20.89 = 2.34
4.60 0.22
17.22 0.68
0.68
GNNDELETE
6.27 + 0.27
8.15 0.19
9.96 = 0.38
1.12 = 0.06
2.70 + 0.18
Table 22: Unlearning times (in seconds) for each unlearning method across datasets. We ignore Cognac and Projector in this table since they do not have a pre-processing step. Their full un unlearning times have already been reported in Table
Dataset
GOLD
MEGU
GIv
IDEA
GNNDELFTE
GRAPHERASER
GUIDE
ETR
4.16
CITESEER
0.39 0:01
0.01
0001
0.37 0.01
0.23 0.03
0.48 0.01
12.93 1.33
11.36 0.66:0.66 0.65
1.76 0.03
PHOTO
0.50
0.00
15.58
5.61
252.35
1.14 0.04
AMAZON-R
0.73 0:04
0.00
0.00
0.03
0.81 +
16.07
1.98
219.71
0.91 0.09
ROMAN-E
0.67 = 0:03
0.00 = 0.00
0.28 + 0.02
0.29 + 0.01
0.73 + 0.07
13.07 + 4.33
110.97 + 4.35
1.94 0.08
1.71
Table 23: Unlearning preprocessing times (in seconds) for each unlearning method across datasets. ignore Cognac and Projector this table since they do not have a preprocessing step.
Dataset
GOLD
MEGU
GIv
IDRA
GRAPHERASEEL GNV
GUIDE
ETR
CORA
0.27 0.06
0.61 =: 0.07
0.12 = 0.05
0.17
0.08
0.14
0..09
10:47 2 1.38
35.73
0.74 1: 0.02
CITESEER
0.27 1. 0.06
0.62 2 0.09
0.08 4: 0.05
0.25 2: 0.07
0.14 0.00
10:27 2: 6.47
36,60 1: 3.10
0.75 4: 0.00
0.00
0.06
666.65
AMAZON-R
0.97 0.21
2.50 +: 0.27
0.40 0.11
0.44 0.07
0.43 0.14
12.63
5.96
532.46
+: 3.23
0.90 0.09
ROMAN-E
0.15
2:28 + 0.25
0.30 = 0.04
0:25 + 0.05
0.36 0.01
13.56 + 7:33
331.23 25.86
0.74 174---00
1.89
Table 24: AUROC following Noisy-Labeler attack Sui al.
2025
(Closer to 0.50 is better.)
Method
CORA
CITESEER
РHото
AMAZON-R.
ROMAN-E.
OGBN-ARXIV
MEGU
0.50
0.31 + 0.02
0.50 + 0.01
0.50
0.50 0.01
GIF
0.00
0.02
0.50 0.01
0.51
0.01
0.50
0.50
0.00
0.02
0.50 0.01
0.50 - 0.01
0.00
0.50
GNNDELETE
0.58
0.61 0.09
0.81 + 0.02
0.52
PROJECTOR
0.50 0.03
0.51
0.50
0.00
0.50
0.50 0.00
GRAPHERASER
0.49-0.01
0.02
0.50
0.00
0.50
0.50
GUIDE
1.00
0.01
0.50
0.00
0.50
OOM
COGNAC
0.51 0.00
0.00
0.50
0.00
0.00
0.50 0.01
0.51 0.01
0.00
0.50 +.00 0.01
0.00
0.0
0.50 +
Table 25: SCALEGUN unlearning results. Note: SCALEGUN supports only binary classification; for multi-class datasets, uses one-vs-rest reduction. Hence, results not directly comparable with other unlearning algorithms.
Dataset
Orig. Acc
Gold Ace
Unlearned Acc
Fidelity
Logit Dist.
CORA
81.7
82.2
81.5
92.6
0.51
CITESEER
75,9
75,48
74.7
93.8
0.602
РHОTO
50.9
50.7
50.7
99.0
0.12
32.2
31.7
20.6
5.8
0.03
ROMAN-EMPIRE
42.7
42.6
15.3
5.6
0.54
40.64
40.69
40.67
99.0
0.192
18

---

Published as a conference paper at ICLR 2026
Table 26: CGU unlearning results. Note: CGU supports only binary classification; for multi-class datasets, uses os-rest reduction. Hence, results are directly comparable with other un- learning algorithms.
Dataset
Orig. Ace
Gold Acc
Unlearnt Acc
Fidelity
Logit Dist.
CORA
87.4
87.6
87.4
99.0
0.12
CITESEER
75.9
75.9
75.1
97.1
0.144
PHOTOS
61.9
62.2
62.2
99.8
0.20
AMAZON-RATINGS
35.0
34.7
35.2
96.3
0.05
ROMAN-EMPIRE
28.4
28.3
28.4
97.1
0.06
OGBN-ARXIV
47.8
47.9
47.9
99.9
0.02
19


Reviews:
[{"review_id": "MYx4SpC5Yp", "reviewer": "Reviewer_hfMm", "summary": "This paper introduces a systematic benchmark for graph unlearning, organized around three desiderata: efficiency, utility, and forgetting. It evaluates multiple families of unlearning methods across diverse datasets and deletion scenarios, comparing them against a retrained “gold” model. The study reports that while current techniques can sometimes approximate retraining, most are not yet practical for large graphs, and it offers actionable guidance for when to prefer unlearning vs. retraining, plus an open-source implementation.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tClear, multi-level evaluation framework: The work formalizes efficiency/utility/forgetting pillars and defines metrics including fidelity and logit distance beyond accuracy, improving diagnostic resolution. This enhances experimental rigor and comparability. Forgetting measured via MIAs tailored to unlearning, aligning with privacy goals. This matters for trustworthiness.\n2.\tBroad empirical coverage with actionable insights: This paper applies seven datasets spanning homophily/heterophily and scale, which supports generality claims. \n3.\tEffective supplementary material: The appendix provides details and support the main body findings.", "weaknesses": "1.\tLimited inclusion of certified methods in main comparisons: Certified approaches are discussed but excluded from benchmarking due to constraints (Sec. 5.1), reducing completeness of the “landscape” under the proposed metrics.\n2.\tRuntime accounting and preprocessing costs: Although the paper critiques under-reporting, its own measurements still aggregate components differently across methods; explicit timing breakdowns (graph construction, neighbourhood extraction, IF computations, etc.) are not standardized. Some claims (e.g., batching incompatibility specifics) are argued qualitatively without per-method ablations quantifying what batching would save or lose.\n3.\tLack of theoretical evidence: The paper does not propose or establish any new theoretical results. It would be beneficial to include theoretical foundations or analyses to support the discussion of existing unlearning algorithms.\n4.\tPrivacy metrics: It is advisable to incorporate privacy metrics into the framework, as privacy is a primary motivation for unlearning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1gLm4i4h2o", "reviewer": "Reviewer_hgen", "summary": "This paper presents a systematic benchmark for Graph Neural Network (GNN) unlearning methods, evaluating existing approaches across three core desiderata: efficiency relative to retraining from scratch, utility preservation across parameter/logit/performance spaces, and forgetting quality via membership inference attacks. Through extensive experiments on seven datasets (Cora, Citeseer, Photo, Amazon-Ratings, Roman-Empire, OGBN-Arxiv, and Reddit), the authors evaluate eight unlearning algorithms and find that most techniques fail to scale to large graphs due to memory constraints and lack batching-aware implementations. The benchmark reveals that while methods like MEGU achieve strong utility preservation, they often fail the efficiency criterion by being slower than retraining, and that certified unlearning approaches are restricted to impractical linear GNN architectures. The paper concludes that retraining from scratch remains the most viable option for large-scale graphs, calling for fundamental redesigns of unlearning algorithms to support batching.", "questions": "1. Could the authors justify why the current evaluation is sufficient to assess GDPR compliance?\n\n2. How would the conclusions in Table 10 and Section 6 change if these methods failed under stronger attack scenarios?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Comprehensive multi-level evaluation framework**. The paper introduces a rigorous assessment methodology that evaluates unlearning quality at four hierarchical levels (parameter space via L2 distance, logit space via distributional divergence, per-instance fidelity, and aggregate accuracy metrics), which is substantially more thorough than prior work that relied solely on aggregate performance metrics. This multi-level analysis successfully reveals subtle discrepancies, such as IDEA achieving reasonable fidelity (0.92 on Cora in Table 4) while exhibiting large logit divergence (18.03 on Cora in Table 5), demonstrating that aggregate metrics alone are insufficient for assessing unlearning quality.\n\n2. **Critical practical insights with actionable guidance**. The paper goes beyond empirical results to provide concrete decision-making guidelines (Table 10) by systematically comparing all methods against three essential pillars and revealing critical overlooked issues. Specifically, the work exposes widespread runtime under-reporting in existing literature (Section 5.3 discusses how MEGU excludes adjacency matrix conversion, GIF/IDEA omit neighborhood identification, and GNNDELETE ignores edge mask preprocessing), and demonstrates that most methods fail on large-scale graphs where unlearning is most needed (all methods OOM on Reddit except GOLD as shown in Tables 7-8), highlighting a fundamental gap between theoretical unlearning research and practical deployment requirements.\n\n3. **Insightful analysis of theoretical versus practical guarantees**. The paper provides valuable critical examination of certified unlearning methods (Section 3, lines 160-171), clearly articulating why approaches like PROJECTOR, CGU, and SCALEGUN have limited practical applicability despite theoretical exactness guarantees. Specifically, it explains that these methods are \"restricted to a very narrow setting\" requiring custom linear GNNs, binary classification for CGU/SCALEGUN, and assumptions of tractable low-rank Hessians that \"break the efficient update scheme\" for non-linear architectures.", "weaknesses": "1. **Limited forgetting evaluation and missing adversarial analysis**. The forgetting assessment relies solely on a simple membership inference attack measuring L2 distance between pre- and post-unlearning posteriors (Appendix A.2), which may not detect sophisticated privacy leaks\n\n2. **Incomplete coverage of recent methods and missing evaluation against state-of-the-art attacks**. While the paper claims to provide \"the first comprehensive evaluation of GNN unlearning\" (page 2, line 67), it omits several recent and promising approaches that address the scalability and efficiency concerns raised in the paper. Notably, Zhang's \"Graph unlearning with efficient partial retraining\" (WWW 2024) [1] and Yang et al.'s \"Erase then Rectify: A Training-Free Parameter Editing Approach\" (AAAI 2025) [2] may also require evaluation in this benchmark. Furthermore, the forgetting evaluation in Section 5.4 and Appendix A.2 uses only basic membership inference attacks, ignoring recent attack methods such as the unlearning inversion attacks by Zhang et al. [3] and the noisy labeler attacks by Sui et al. [4] that specifically target unlearned models and can leak class membership information. Without evaluating against these recent baselines and attacks, the benchmark's claim to provide comprehensive guidance (as stated in the contributions on page 2, lines 72-78) is weakened, particularly since these newer methods may offer better efficiency-utility tradeoffs and the newer attacks may reveal vulnerabilities missed by the simple L2-based MIA employed in the current evaluation.\n\n\n### References\n[1] Jiahao Zhang. “Graph unlearning with efficient partial retraining”. WWW 2024.\n\n[2] Zhe-Rui Yang, Jindong Han, Chang-Dong Wang, Hao Liu. “Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning”. AAAI 2025.\n\n[3] Jiahao Zhang, Yilong Wang, Zhiwei Zhang, Xiaorui Liu, Suhang Wang. “Unlearning Inversion Attacks for Graph Neural Networks”. WSDM 2026. \n\n[4] Zhihao Sui, Liang Hu, Jian Cao, Dora D. Liu, Usman Naseem, Zhongyuan Lai, Qi Zhang. “Recalling The Forgotten Class Memberships: Unlearned Models Can Be Noisy Labelers to Leak Privacy”. IJCAI, 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wiCmLEvQXT", "reviewer": "Reviewer_JbxA", "summary": "The paper introduces a systematic review of recent graph unlearning techniques, and benchmarks them in line with the usual three properties used to evaluate graph unlearning: utility, forgetting, and efficiency. The authors evaluate a wide array of unlearning methods on the task of random node unlearning. They include an ablation with more targeted unlearning. In particular, they introduce new metrics to measure the utility of a model, where they also look at the fidelity, L2 distance, and parameter difference between the original and unlearnt model. Overall, I feel the work is timely, but the contributions are limited and narrow. I will discuss this further in weaknesses.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper does well to create a comprehensive unlearning benchmark\n- The paper is a pleasure to read, and is well-written.\n- The paper goes beyond the metrics, and discusses hidden training costs (which I appreciate a lot), as well as OOM issues which most graph unlearning methods suffer from as scale increases—contrary to their claims.\n- I really appreciate the strong concluding section with limitations and insights for practical deployment", "weaknesses": "1. Key contribution 1 (Unified benchmarking framework), is not exactly a contribution. If you look at any graph unlearning paper released in the past couple years, they all measure efficiency, utility and forgetting. This is certainly not the first comprehensive evaluation, and frankly I think is a bare minimum for any paper introducing a new method [1][2]. Therefore, I fail to see why this should be a core contribution.\n\n2. All main experiments are performed on 1 setting: randomised node unlearning. I feel this is very limiting, and cannot in general inform broad claims about unlearning methods. Edge unlearning or feature unlearning are not even mentioned, even though most of the mentioned algorithms focus on all of them. Since the paper positions itself as a benchmark paper, I feel this is a reasonable ask. [3] is mentioned as a competing benchmark in the paper, and performs these tasks and more.\n\n3. The reason for exclusion of [1] in the study is that \"it operates on the paradigm of corrective unlearning instead of privacy preservation\". I find this unsatisfactory for a number of reasons. Firstly, the experimental setting is randomised node unlearning, which by itself has nothing to do with privacy, and is used as a proxy to evaluate unlearning on a set of nodes that were asked to be deleted. From what I can see in [1], the actual procedure of unlearning is identical to other unlearning methods. Second, many of the other methods included here are included in [1] for a comparison, so why is the converse not possible?\n\n4. Continuing from point 3, I feel [1] has a very reasonable and practical evaluation of unlearning, which is certainly better than random unlearning. Since this is a benchmark paper, would it not make sense to include various settings of attacks? A lot of unlearning papers mention that they can operate on adversarial attacks as well (see [2]), even if their main area is privacy. This is an addition to point 2. I feel the paper can benefit from including more experimental settings from both [1] and [2].\n\n5. One point of technical novelty in the paper is the introduction of multiple levels of measuring *utility*. I agree for the need of the fidelity metric, and find that to be a nice contribution, however, I feel the other introduced metrics, the logit distance and the model-level distance, are redundant and don't offer much. I would ask the authors for a clarification on my understanding of these metrics.\n\n    - (1) Won't a similar fidelity score imply a similar logit distance? Since the output class of the predictions is directly dependent on the logits? \n    - (2) The paper says \"If the parameters are close, then the intermediate activations at each GNN layer are also likely to be similar\". I am not sure I can naively believe this. and would prefer some theoretical or empirical backing of this. \n    - (3) I would like to ask how these metrics make a difference in the decision making guidance (since utility is mentioned as a whole there), and if they don't, what is the contribution exactly, and why are they needed?\n\n6. I feel there should be more of a discussion on the actual \"unlearning\" part (forgetting). The paper discusses at length about the impact on their introduced metrics, but they are for model utility. I feel forgetting is more of an under-explored area and MIA is not the best indicator for forgetting performance. I would like the paper to have a longer discussion on forgetting. Specifically, the paper defines \"The objective of unlearning is that the unlearned model Θ˜ be similar to Θ′, which is the gold standard\", and this is true for both utility and forgetting metrics. However, discussion of forgetting is limited. \n\n7. Can the authors clarify what they mean by deletion for retrain-from-scratch, specifically for RQ4? Are the nodes removed from the training set, or are they removed from the graph altogether? Both these settings can drastically change the outcome of the experiments, and warrants a careful discussion for both cases. \n\nOverall, I feel the paper does not adequately answer any of the introduced gaps in the introduction. Evaluation ambiguity remains, Efficiency vs. retraining was the reason inexact machine unlearning methods were introduced, and I don't believe the experimental breadth is sufficient for warranting an analysis of generalisation. Thus, I am leaning towards a rejection.\n\n[1] [Cognac](https://arxiv.org/pdf/2412.00789)\n\n[2] [Megu](https://arxiv.org/pdf/2401.11760)\n\n[3] [Open-GU](https://arxiv.org/pdf/2501.02728)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wGaccaC7jv", "reviewer": "Reviewer_MdZs", "summary": "This paper presents a benchmark for Graph Neural Network (GNN) unlearning methods, evaluating them based on Efficiency (vs. retraining), Utility (multi-level alignment with retrained models), and Forgetting (MIA resistance). It assesses various existing unlearning techniques across diverse datasets and deletion scenarios. This concludes that most methods suffer from scalability issues (memory, lack of batching), making retraining often preferable for large graphs, and provides guidelines for selecting methods when unlearning is viable. Codebase is also provided.", "questions": "1. I would definitely like to see Cognac [1] being evaluated to retain my rating. From what I understand, it can easily be adapted to work and evaluated in this setting, even if they don't evaluate it in this setting in their paper. It might not be the state-of-the-art in this setting, but it is SOTA in a harder setting, so it still needs to be evaluated for completeness.\n2. The MIA results in Figure 1 show PROJECTOR and GRAPHERASER performing poorly. Given that these methods are designed with stronger (sometimes exact) unlearning notions in mind, this seems counterintuitive. Do you have hypotheses as to why they failed the MIA test used? Does it relate to their specific architectures or the assumptions underlying the MIA?\n3. You highlight the lack of batching support as a major scalability bottleneck. Based on the algorithmic principles of methods like MEGU, GIF, or GNNDelete, what are the core technical challenges in developing batch-compatible versions? Are certain paradigms inherently harder to batch than others, or is it just a matter of implementation?\n4. Table 10 provides a useful summary. For MEGU, efficiency is marked 'X' due to being slower than GOLD on large graphs. However, it performs well on utility/forgetting. Could there be scenarios (frequent small deletions on medium graphs) where MEGU's overhead is acceptable given its strong utility? The guidance seems slightly harsh as it's binary (retrain vs. use X).\n5. How sensitive are the efficiency results (Table 7) to implementation details? Could optimized implementations significantly change the ranking or make more methods competitive with retraining?\n6. Sidenote: I'm also not sure if the paper violates margin constraints. It seems awfully dense and cluttered.\n\n---\n\n*[1] Kolipaka, Varshita, Akshit, Sinha, Debangan, Mishra, Sumit, Kumar, Arvindh, Arun, Shashwat, Goel, Ponnurangam, Kumaraguru. \"A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks.\" Proceedings of the 42nd International Conference on Machine Learning (ICML).*", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. **Comprehensive Evaluation:** Establishes a benchmark (efficiency, multi-level utility, forgetting, robustness) that (in my opinion, having worked in this field) advances evaluation standards in GNN unlearning.\n2. **Practical Relevance:** Directly compares against retraining, assesses scalability on large graphs, and considers hidden computational costs, providing a reality check on practical viability.\n3. **Clear Insights & Guidance:** Systematically reveals limitations (especially scalability/batching) of current methods and provides clear, evidence-based recommendations summarized effectively (Table 10).\n4. **Clarity and Reproducibility:** Very well-written and organized, making comparisons accessible. Also provides an open-source codebase implementing multiple methods within its framework.", "weaknesses": "1. **Limited Scope of \"Forgetting\":** Relies solely on one type of MIA based on posterior shifts. Forgetting is a complex concept, and exploring other attack types (ex., attribute inference, link re-inference) or information-theoretic measures could provide a more complete picture. The MIA results (Figures 1, 3) show subtle differences, making strong conclusions about relative forgetting quality difficult for methods near the 0.5 AUROC baseline.\n2. **Focus on Node Classification:** Primarily evaluates unlearning for node classification. Performance trade-offs might differ for other tasks like link prediction or graph classification.\n3. **Implementation vs. Algorithm:** The scalability critique focuses heavily on current *implementations* lacking batching. While reflecting the practical state, it doesn't definitively rule out that some *algorithms* could be made scalable with more engineering effort. A deeper discussion of algorithmic amenability to batching would be valuable.\n4. **Novelty:** As a benchmarking paper, its novelty lies in the depth and width of its framework and insights rather than proposing new methods. So while highly valuable, I would prefer to have covered all the setups in the same framework for it to be complete.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)