GraphEraser — Graph Unlearning (Chen et al.)
Why
The partition-based graph-unlearning method implemented in the ER notebook. It is the direct
adaptation of SISA to graphs, and its central warning — random sharding destroys graph structure —
is the reason partition choice is a topology question.
Summary
Bibliographic. Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, Yang
Zhang. Graph Unlearning. ACM CCS 2022 (arXiv:2103.14991v2, 16 Sep 2022). 22 pages. Code:
https://github.com/MinChen00/Graph-Unlearning.
Problem
Retraining a GNN from scratch per deletion request is too expensive. SISA (sharding + slicing +
aggregation) is the standard efficient-retraining framework, but it was designed for i.i.d. data.
Applying SISA to graphs has two problems:
- Graph structure is lost. Random node sharding cuts edges; each shard model sees a mutilated
neighbourhood, and accuracy drops. - Shards are unbalanced. Classic community detection (e.g. LPA) produces shards with wildly
different sizes (on Cora, the largest shard had 113 nodes and the smallest 2), so the largest
shard dominates the retraining time and the 1/K speedup disappears.
Framework
GraphEraser has three phases:
- Balanced graph partition — split the training graph into disjoint shards, each with at
most nodes ( by default). - Shard model training — train one GNN per shard on its induced subgraph; shards can be
trained in parallel. - Shard model aggregation — at inference, send the node and its neighbourhood to all shard
models and combine their predictions.
On a node-unlearning request, the node is removed from its shard and only that shard model is
retrained. Edge requests are evaluated in Appendix H and reach the same conclusions as node
unlearning. The aggregation may also need relearning if the deleted node was used to train the
aggregator; the paper uses a small random subset (10% of the training nodes) to relearn and reports
comparable utility, and notes that relearning is unnecessary when the deleted nodes were not used
to train the aggregator.
Partition methods
- BLPA (Balanced Label Propagation Algorithm). Start from a random balanced assignment, then
repeatedly move nodes to neighbouring shards, prioritising moves by the number of neighbours in
the destination, subject to the capacity . This keeps communities together while enforcing
balance. - BEKM (Balanced Embedding K-Means). Compute node embeddings, run balanced k-means (capacity
per cluster) with centroids and up to iterations; embedding dimension 32. - Both are compared against Random sharding and Scratch (full retrain).
Aggregation
- Mean and majority vote are the baselines.
- LBAggr (learning-based aggregation): learn an importance score per shard
model, with , by minimising the prediction loss on a set of validation nodes.
Gradient descent is followed by a projection that maps negative scores back to 0 and renormalises.
The paper reports LBAggr is up to 93% higher F1 than mean aggregation and 112% higher F1
than majority vote.
Experimental setup
- Datasets: Cora (2,708 nodes / 5,429 edges / 7 classes / 1,433 features), Citeseer
(3,327 / 4,732 / 6 / 3,703), Pubmed (19,717 / 44,338 / 3 / 500), CS (18,333 / 163,788 / 15 /
6,805), Physics (34,493 / 495,924 / 5 / 8,415). - Split: 80% of nodes for training, 20% for utility evaluation; partitioning is applied only to
the training graph. - Shard counts: k = 20, 20, 50, 30, 100 for Cora, Citeseer, Pubmed, CS, Physics; .
- GNNs: SAGE, GCN, GAT, GIN, two layers each, 100 epochs, Adam with lr 0.01 and weight decay
0.001, PyTorch Geometric. - Metrics: unlearning efficiency = average time over 100 independent node/edge requests;
model utility = micro-F1.
Results
- 2.06× (small dataset) to 35.94× (large dataset) unlearning time improvement over retraining.
- Up to 62.5% higher F1 than random partitioning (GraphEraser-BLPA / BEKM vs Random).
- LBAggr up to 93% / 112% higher F1 than mean / majority vote.
- Edge unlearning results are deferred to the appendix to avoid repetition; the conclusions are the
same.
Limitations
- The shard models are deterministically unlearned, but the partition was computed on the full
graph including the deleted node and is not recomputed. The paper states this explicitly
(Section 4.3, “Guarantee of Unlearning”): the partition is not deterministically unlearned, so
GraphEraser is an approximate method. - Partition quality depends on the graph having community structure; on a homogeneous graph (ER) the
balanced random partition is close to optimal. - The paper studies node classification on static graphs, not generative models.
Thesis hook
- The ER notebook’s GraphEraser implementation follows this pipeline exactly: balanced random
partition, one GCN per shard on its induced subgraph, mean-logit aggregation, retrain the affected
shard.04_ba_network_unlearning.ipynband05_ws_network_unlearning.ipynbrevisit the partition
question, and07_graph_partition_strategies.ipynbcompares random vs LPA vs Louvain. - The 1/K cost and the edge-cut trade-off are the two quantities the thesis can measure
across ER/BA/WS. The ER notebook’s section 10 plots the theoretical 1/K curve against the edge cut. - The paper’s warning that SISA-style random partitioning damages structural information predicts
that GraphEraser’s advantage should be largest on WS (high clustering) and BA (hubs), smallest on
ER. That is a testable topology hypothesis. - The partition approximation is the concrete failure mode: the shard assignment was chosen using
the deleted node’s edges, so a trace may remain in which shard the node was in. That is
measurable, in principle, with an MIA.
Open questions
- Is the 1/K speedup actually achieved on ER/BA/WS at n = 1000, or does aggregation/relearning cost
dominate? - Does LBAggr help on synthetic graphs with weak community structure, or is mean aggregation enough?
- How should graph diffusion unlearning be sharded — by graph record (SISA over records) rather than
by node? That is a different axis from GraphEraser’s node sharding.