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).
  • 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.

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