Machine Unlearning — Survey (Nguyen et al.)
Why
The vocabulary paper: it fixes the definitions (exact vs approximate), the request types (item,
feature, class, task, stream), the algorithm families, and the evaluation metrics that the rest of
the thesis will use.
Summary
Bibliographic. Thanh Tam Nguyen, Thanh Trung Huynh, Zhao Ren, Phi Le Nguyen, Alan Wee-Chung
Liew, Hongzhi Yin, Quoc Viet Hung Nguyen. A Survey of Machine Unlearning. arXiv:2209.02299v6,
17 Sep 2024. 24 pages. Sections cited below are from the PDF.
Definitions
- Exact unlearning (Definition 1/2): the unlearned model distribution must equal the
retrained-model distribution,
.
The equality can be read in weight space or in output space; the output-space version is
sometimes called weak unlearning. Retraining trivially satisfies the definition and is treated
as the gold standard, but it is too expensive for large models and does not batch requests well. - Approximate unlearning (-certified removal): the two distributions only have to be
close,
,
with an relaxation for the failure probability. This is the same shape as
differential privacy. The survey notes the tension: DP implies approximate unlearning because a
DP model never memorises the data, but a strongly DP model also does not learn from the data. - Indistinguishability metrics used to compare the two models: weight distance, KL /
Jensen–Shannon divergence, activation distance, and membership inference. The survey notes the
practical problem with weight distance: retraining is itself stochastic, so two models trained on
the same data can differ.
Request scenarios (Section 2)
- Item removal — delete individual training samples; the common case.
- Feature removal — delete a feature or attribute across many samples (e.g. gender in hiring
data). Influence-function and disentangled-representation methods are discussed. - Class removal — delete an entire class without samples of that class.
- Task removal — delete a task from a multi-task / lifelong model.
- Stream removal — a sequence of requests over time; adaptive requests depend on the
intermediate unlearned model, non-adaptive ones do not.
Restricted-access settings (Section 4)
- Zero-glance: the forget set is not available at unlearning time; only retained data
can be used. - Zero-shot: the training data is not accessible at all; the objective becomes
. In the classification variant the algorithm
receives the forget-class labels , i.e. . - Few-shot: a small subset is available.
Algorithm families (Section 5)
- Model-agnostic
- Differential privacy: set the privacy budget to zero for the deleted sample.
- Certified removal: Newton update / influence-function correction with a bound; falls back to
retraining if the bound is too large. - Statistical query learning: recompute the statistics over the remaining data; exact for
adaptive queries, but does not scale to deep networks. - Decremental learning: remove support vectors / clusters without full retraining.
- Knowledge adaptation (distillation): transfer knowledge from the original model to a student
trained on retained data. - Parameter sampling: sample weights from a distribution conditioned on the retained data.
- Model-intrinsic
- Softmax classifiers, linear models, tree-based models, Bayesian models, and DNN-specific
methods (Fisher information, masked/selective forgetting, neuron pruning).
- Softmax classifiers, linear models, tree-based models, Bayesian models, and DNN-specific
- Data-driven
- Data partition (SISA): shard the training set, train one model per shard, slice each shard
into checkpoints, aggregate predictions. A deletion retrains only the affected shard from the
nearest checkpoint. This is the direct ancestor of GraphEraser. - Data augmentation: error-maximizing noise for the forget class, error-minimizing noise for
protection, mnemonic codes. - Data influence: influence functions and stored training history; subtract the update
attributable to the deleted sample.
- Data partition (SISA): shard the training set, train one model per shard, slice each shard
Evaluation metrics (Section 6.3)
- Accuracy on the forget set, retain set, and test set.
- Completeness: did the unlearning actually remove the influence, measured with attacks or
relearning. - Unlearn time: wall-clock cost relative to retraining.
- Distance: weight, activation, KL/JS, layer-wise distance between unlearned and retrained
models. - Relearn time: if the model recovers the forgotten data in a few steps, it did not forget.
- Membership inference: attack the unlearned model; the forget set should look like unseen
data. - ZRF (Zero Retrain Forgetting): compare the forget-set output distribution against a random
(unskilled) model, avoiding the need for a retrained reference.
Graph unlearning (Section 7.3)
The survey treats graph data as a distinct hard case for two stated reasons: samples are correlated
and partitioning is non-trivial, and requests can target nodes or edges. Its resource table lists
GraphEraser, GNNDelete, GraphEditor, GUIDE, FedLU, and related methods, and it notes that unlearning
must remove influence from both model weights and neighbouring representations.
Resources
The paper’s Table 4 lists reference implementations, including MinChen00/Graph-Unlearning
(GraphEraser) and mims-harvard/GNNDelete, which are the two implementations used in the graph
notebooks. Table 5 lists datasets; Cora and OGB are the graph entries.
Stated gaps
The survey’s conclusion is that the field lacks common frameworks, benchmarks, and consistent
evaluation; theoretical guarantees exist mostly for convex / linear settings; verification of
unlearning is still open. These are the gaps the thesis can speak to in the graph-diffusion
setting.
Thesis hook
- Gives the exact/approximate language for the thesis: the ER notebook’s retrain run is the
exact reference; GraphEraser, GNNDelete, and NegGrad are approximate. - Gives the metric vocabulary: forget accuracy, retain accuracy, unlearn time, MIA. The ER notebook
implements a subset and should eventually add relearning and a stronger MIA. - Confirms that graph unlearning is a recognised sub-problem with node/edge requests and
non-i.i.d. data, which is exactly why ER/BA/WS matter. - The SISA → GraphEraser lineage is the justification for the shard-based method in
03_er_network_unlearning.ipynb.
Open questions
- Which definition should the thesis claim: exact, -certified, or empirical
indistinguishability? A diffusion model cannot be retrained per request at thesis scale, so the
claim will be empirical. - Which metrics from Section 6.3 are feasible for graph diffusion? Relearn time and ZRF look
cheaper than full retraining. - The survey is model-agnostic; it does not say how to evaluate unlearning of a generative graph
model. That gap is the thesis.
Notes in this survey
- Inexact unlearning and U-MIA (Hayes et al.) — why the usual MIA overestimates privacy.
- Knowledge unlearning via gradient ascent (Jang et al.) — the NegGrad baseline.
- SISS (Alberti et al.) — data unlearning for diffusion.
- ReTrack (Shi et al.) — trajectory redirection.
- Extracting training data (Carlini et al.) — the memorisation threat.
- LiRA (Carlini et al.) — per-example MIA.
- GDPR Article 17 — the legal driver.
- GraphEraser (Chen et al.) — partition-based graph unlearning.
- Simple graph unlearning on ER — implementation notes for the ER notebook.