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:

  1. Graph structure is lost. Random node sharding cuts edges; each shard model sees a mutilated
    neighbourhood, and accuracy drops.
  2. 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:

  1. Balanced graph partition — split the training graph into disjoint shards, each with at
    most nodes ( by default).
  2. Shard model training — train one GNN per shard on its induced subgraph; shards can be
    trained in parallel.
  3. 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.ipynb and 05_ws_network_unlearning.ipynb revisit the partition
    question, and 07_graph_partition_strategies.ipynb compares 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.