Simple Graph Unlearning on ER Networks — Implementation Notes

Why

The ER notebook is the control condition of the graph-unlearning series. Before asking whether
topology changes forgetting, we need one topology where there is almost no structure to blame:
Erdős–Rényi. This note records what the notebook implements, how it maps to the papers, and what
result would count as evidence.

The code itself is explained line by line in
CODE_GUIDE_ER.

Summary

Why graph unlearning is not i.i.d. unlearning

In ordinary machine unlearning a training sample is independent of the others. In a graph, nodes
and edges are coupled by message passing: deleting one node’s label does not delete its features,
its edges, or the influence it had on its neighbours’ representations. GraphEraser states this as
the reason SISA cannot be applied naively; the survey makes the same point when it lists the
correlated data and non-trivial partitioning as the graph-specific difficulties. GraphEraser’s
answer is to partition the graph into balanced shards so that most of a node’s neighbourhood stays
together.

Two request types exist:

  • Node unlearning: remove a node’s data (features, label, edges) from the model.
  • Edge unlearning: remove a relationship between two nodes.

Our ER notebook implements node-label unlearning: the node stays in the graph for message
passing, but its label is removed from the training set and the model must stop predicting it. This
is the simplest request and the one that matches the GNN classification setup.

Why ER is the control

ER has:

  • Poisson degree distribution (no hubs, no heavy tail),
  • clustering coefficient (low and degree-independent),
  • short average path length .

If unlearning difficulty is uniform across degree classes on ER, then any degree effect observed on
BA can be attributed to the heavy tail, and any clustering effect on WS to the triangles. The ER
notebook’s section 13 is exactly that check: it bins the forgotten nodes by degree and plots the
confidence drop per method.

What the notebook implements

Graph: , , expected degree .

Task: two-part 3-class node classification with 16-dimensional Gaussian probe features and
labels generated from the seed only, not from the graph:

  • 70% generalizable nodes: labels from a fixed random linear rule plus label noise.
  • 30% memorization nodes: random labels. Exact retraining cannot recover them from the
    remaining nodes.

The forget request targets 25% of the memorization-training nodes. Utility is measured on held-out
generalizable nodes. The task is deliberately learnable; it is not a benchmark.

Why no degree feature? Degree is part of the structure under test. If ER, BA and WS received
different feature matrices, a difference in forgetting could come from the features instead of the
adjacency. One shared feature matrix and one shared label vector make the graph the only variable.

Model: 2-layer GCN with a dense renormalised adjacency
, 64 hidden units, dropout 0.5, Adam, 200 epochs. PyTorch
only — no PyTorch Geometric.

Deletion request: 25% of the memorization-training nodes (41 of 166 at seed 42), sampled uniformly.

Methods:

  1. No unlearning — the original model; upper bound on leakage.
  2. Retrain — same architecture trained without the forgotten labels; the exact reference.
  3. GraphEraser — 5 balanced random shards, one GCN per shard on its induced subgraph, mean-logit
    aggregation; unlearning retrains only the shard(s) containing forgotten nodes. This is our
    simplified variant; 07_graph_partition_strategies.ipynb compares random sharding with LPA and
    Louvain (a BLPA-style balanced LPA, not the paper’s exact BLPA/BEKM).
  4. GNNDelete — freeze the trained GCN, insert a trainable residual operator after each layer on
    the forgotten nodes and their 1-hop neighbours; loss = uniform-target term on forgotten nodes +
    KL preservation term on all retained nodes. GNNDelete is not one of the PDFs in
    98 Background Papers/; this is a description of our implementation, following the public code
    (mims-harvard/GNNDelete, Cheng et al., ICLR 2023).
  5. NegGrad — gradient ascent on the cross-entropy of the forgotten nodes.

Metrics:

  • Forget accuracy — accuracy on the forgotten nodes. Lower is better; chance is 1/3.
  • Test accuracy — utility on held-out nodes.
  • MIA AUC (forget vs held-out memorization) — how distinguishable forgotten nodes are from
    unseen random-label nodes of the same type. 0.5 is ideal; higher means residual leakage.
  • MIA AUC (retain vs held-out memorization) — should stay above 0.5; the model is allowed to
    know retained training data.
  • Unlearning time — wall-clock cost of the removal operation.

The MIA is a population attack: per-node negative log-likelihood, thresholded, AUC. The
inexact-unlearning and LiRA notes predict that this overestimates privacy. It is a first-pass
metric, not a privacy claim.

Controlled structure-only design

The thesis asks whether unlearning difficulty depends on graph shape (ER vs BA vs WS). That
question is only answerable if shape is the only thing that changes. The notebooks now enforce four
controls:

  • Same size and mean degree. ; ER , BA , WS all give
    .
  • Same task. Features and labels are generated from the seed alone; no degree feature. The
    task is 70% generalizable nodes plus 30% random-label memorization nodes.
  • Same splits and request. Masks and the forget subset (25% of memorization-training nodes)
    use the seed alone, so the exact same node IDs are forgotten in all three notebooks.
  • Same model and methods. Two-layer GCN, Adam, same epochs; retrain, GraphEraser, GNNDelete,
    NegGrad.

06_comparison_er_ba_ws.ipynb builds the task once per seed and passes it to all topologies, then
reports normalized forgetting = (baseline forget accuracy − method forget accuracy) /
(baseline forget accuracy − chance). This adjusts for different baseline difficulty. It also logs
structural descriptors and correlates them with forgetting, with the caveat that family and
descriptor are confounded; the within-family experiments are the causal tests.

Against the proposal’s hypotheses:

  • H1, ER easiest: no hubs, no triangles, little structure to retain.
  • H2, BA hubs: a few high-degree nodes carry disproportionate signal; forgetting a hub should
    cost more. The hub-biased request tests this within BA.
  • H3, WS clustering: redundant triangles keep a forgotten label recoverable; the rewiring
    sweep tests this within WS.

Proxy caveat. The thesis unlearns one graph record from a structure-only DiGress model. This
notebook unlearns node labels from a GCN. The direction of the structural effect transfers, not the
magnitude.

What the result would mean

  • Retrain is the reference; the gap between retrain and an approximate method is the price of
    approximation.
  • GraphEraser should approach retrain at roughly 1/K of the retraining cost for a small request.
    With ~41 memorization nodes forgotten across 5 shards, every shard is likely affected, so the
    realised cost approaches a full retrain. The notebook prints the number of retrained shards and
    the measured time, which is the honest comparison.
  • GNNDelete should keep test accuracy high (KL term) while its forget accuracy may stay above
    chance (the operator is local and the frozen encoder still carries the label signal).
  • NegGrad should reduce forget accuracy but may also hurt test accuracy; it has no preservation
    term.
  • Degree should not modulate the confidence drop on ER. A flat degree profile is the control that
    makes the BA hub experiment interpretable.

Status

The notebook was executed in Colab (run2) and in a local CPU venv: 18/18 code cells, 0 errors.
Results are in notebooks/03_graph_unlearning/03_er_network_unlearning_run2.ipynb. The earlier
_run.ipynb used the old smooth-label task and is obsolete.

Run 2, seed 42, 41 forgotten memorization nodes:

MethodForget accTest accMIA forgetTime (s)
No unlearning0.4630.5480.5200
Retrain0.3660.5560.4252.51
GraphEraser0.3660.5850.4371.31
GNNDelete0.3410.5190.4873.19
NegGrad0.2200.3630.4110.89

Chance is 0.333. Retrain and GraphEraser reach chance within sampling noise; GraphEraser keeps the
best utility. NegGrad over-forgets and breaks utility. MIA is noisy with 41 forgotten vs 65
reference nodes; treat it as secondary.

Thesis hook

  • ER gives the null result that the rest of the thesis is measured against: if forgetting is
    uniform here, topology effects elsewhere are real.
  • The four methods form the baseline set for BA/WS and for the diffusion stage; the same metrics
    (forget accuracy, retain accuracy, MIA, time) carry over.
  • The 1/K vs edge-cut trade-off is a concrete, measurable quantity that links GraphEraser’s
    engineering to graph structure.
  • The population-MIA caveat is the first methodological improvement to make: upgrade to a
    per-example attack before claiming privacy.

Open questions

  • What deletion ratio is realistic? The current request forgets 25% of the memorization-training
    nodes (41 of 166). The GraphEraser paper studies larger request sets.
  • Should the forget set be uniformly random, degree-stratified, or hub-biased on each topology?
    Random is the fair cross-topology control; hub-biased is the realistic BA worst case.
  • How many seeds are needed before the method differences are meaningful? The comparison notebook
    uses 3; a thesis result probably needs 5–10.
  • Does node-label unlearning capture “delete one stored graph” for the diffusion stage, or does the
    thesis need record-level unlearning (one graph = one record) with a different sharding axis?