PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Unlearning

Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, Yang Zhang

arXiv:2103.14991v2cs.LGcs.AIcs.CRstat.ML

TL;DR

Removing requested training data from graph models requires balancing unlearning efficiency and model utility. GraphEraser uses balanced graph shards and learned aggregation; experiments report 2.06× to 35.94× shorter unlearning time than retraining, with comparable utility.

  • Problem

    Graph unlearning must address removal requests while balancing unlearning efficiency and model utility.

    Source: §3.1 · p. 3

  • Method

    GraphEraser partitions graphs into balanced shards, trains a model per shard, and uses learning-based aggregation.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    2.06× (smallest dataset) to 35.94× (largest dataset) shorter average unlearning time than retraining from scratch, with comparable utility; F1 is up to 62.5% higher than random partitioning.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Other balanced graph partition methods can be plugged into GraphEraser, with partition choice depending on the GNN structure.

    Source: §4.3 · p. 6

    GraphEraser performs approximate rather than exact unlearning because its graph clustering step is not deterministic.

    Source: §4.3 · p. 6

Abstract

from arXiv · show

Machine unlearning is a process of removing the impact of some training data from the machine learning (ML) models upon receiving removal requests. While straightforward and legitimate, retraining the ML model from scratch incurs a high computational overhead. To address this issue, a number of approximate algorithms have been proposed in the domain of image and text data, among which SISA is the state-of-the-art solution. It randomly partitions the training set into multiple shards and trains a constituent model for each shard. However, directly applying SISA to the graph data can severely damage the graph structural information, and thereby the resulting ML model utility. In this paper, we propose GraphEraser, a novel machine unlearning framework tailored to graph data. Its contributions include two novel graph partition algorithms and a learning-based aggregation method. We conduct extensive experiments on five real-world graph datasets to illustrate the unlearning efficiency and model utility of GraphEraser. It achieves 2.06$\times$ (small dataset) to 35.94$\times$ (large dataset) unlearning time improvement. On the other hand, GraphEraser achieves up to $62.5\%$ higher F1 score and our proposed learning-based aggregation method achieves up to $112\%$ higher F1 score.\footnote{Our code is available at \url{https://github.com/MinChen00/Graph-Unlearning}.}

1 Introduction

GraphEraser addresses the challenge of unlearning from GNNs: retraining from scratch is costly, while SISA-style random node partitioning can damage graph structure and model utility. It combines graph-aware balanced partitioning with learned shard aggregation to support efficient unlearning while preserving utility.

1 Introduction

  • SISA [5] partitions training data into disjoint shards and retrains only the affected shard, but its random partitioning can damage graph structure needed for representative GNNs.GNNs aggregate neighboring-node feature information, making graph structure important to model utility.Source: §1 · p. 1
  • Its two graph partition strategies preserve structure through community detection or jointly use graph structure and node features by clustering their embedding vectors into shards.The embedding-based strategy transforms node features and graph structure into vectors before clustering.Source: §1 · pp. 1–2
  • A unified balancing principle and two balanced partition algorithms address shard-size imbalance, while learned shard-importance scores improve the global prediction over uniform contribution.Unbalanced shards can concentrate revoked samples in the largest shard and make retraining slow; shard models do not contribute uniformly to the final prediction.Source: §1 · p. 2
  • GraphEraser cuts average unlearning time by up to 2.06× on the smallest dataset and 35.94× on the largest versus retraining from scratch, with comparable model utility.It achieves up to 62.5% higher F1 score than random partitioning; learned aggregation achieves up to 93% higher F1 score than mean aggregation and 112% higher F1 score than majority-vote aggregation.Source: §1 · p. 2
  • GraphEraser is presented as the first GNN machine-unlearning approach, defining node and edge unlearning requests and a general pipeline for graph unlearning.Machine unlearning aims to eliminate the impact of data whose owner requests deletion; deterministic unlearning removes the sample and retrains from scratch, which can be computationally prohibitive on large datasets.Source: §1 · pp. 1–2
  • The evaluation spans five real-world graph datasets and four state-of-the-art GNN models to assess unlearning efficiency and model utility.Source: §1 · p. 2

2 Preliminaries

The preliminaries define attributed graphs and explain how GNNs aggregate neighborhood information for node classification. They also introduce machine unlearning and SISA’s shard-based approach, which retrains only the shard containing a deleted sample.

2.1 Graph Neural Networks

  • An attributed graph is represented as G = ⟨V, A, X⟩, with nodes V, binary adjacency matrix A, and node-feature matrix X; an edge between u and v is denoted e_u,v.The feature dimension is d_X and the number of nodes is n = |V|.Source: §2.1 · p. 2
  • GNNs aggregate neighboring nodes’ information into embeddings, and this paper focuses on predicting a node’s label from its features and neighborhood information.The paper uses message passing to train the GNN.Source: §2.1 · p. 2

2.2 Machine Unlearning

  • Unlearning requires deleting a revoked sample and eliminating its influence on the model; retraining from scratch is effective but can be prohibitively costly for complex models and large datasets.Approximation approaches [20] aim to reduce that overhead.Source: §2.2 · pp. 2–3
  • GraphEraser partitions a training graph into disjoint shards, trains shard models in parallel, learns model importance scores for aggregation, and retrains the affected shard after a deletion request.For prediction, the node is sent to every shard model and their posteriors are aggregated using the learned scores.Source: Figure 1 · p. 3
  • SISA divides training data into disjoint shards, trains a model per shard, aggregates their predictions, and retrains only the affected shard after a deletion request.This avoids retraining the entire model from scratch.Source: §2.2 · p. 3

3 Graph Unlearning

Graph unlearning removes either a node and its incident links or a single edge, while seeking fast retraining and prediction accuracy close to retraining from scratch. GraphEraser addresses graph-specific partitioning challenges through balanced shards, shard models, and prediction aggregation.

3.1 Problem Definition

  • Node unlearning removes a node’s features and incident links; edge unlearning removes one edge while retaining both endpoint nodes’ features.The target unlearned model is trained on the resulting graph after the requested node data or edge is removed.Source: §3.1 · p. 3
  • Randomly applying SISA can damage graph structure, whereas community detection can yield unbalanced shards [19] [42]; graph unlearning therefore seeks balanced shards and structural preservation.Similar shard sizes help keep retraining time similar across shards, while preserving structural properties supports prediction accuracy in node classification.Source: §3.1 · pp. 3–4

3.2 GraphEraser Framework

  • GraphEraser partitions the graph into disjoint balanced shards, trains same-architecture shard models (in parallel if desired), then aggregates their predictions at inference.At inference, each shard model receives the target node’s features, its neighbors’ features, and the graph structure among them.Source: §3.2 · p. 4

4 Balanced Graph Partition

GraphEraser contrasts random, structure-aware, and joint feature-and-structure graph partitioning, then introduces capacity-limited algorithms to balance the structure-aware shards. The section also discusses the approximate nature of its unlearning and the authors’ interpretation of data deletion from a preprocessed graph.

4 Balanced Graph Partition

  • GraphEraser considers node features alone via random node-ID shards, structure alone, or both through embedding clustering; it treats random partitioning as a baseline and balances the latter two strategies.Directly applying community detection or embedding clustering can produce highly unbalanced shards, motivating a general balancing principle.Source: §4 · p. 4

4.1 Community Detection Method

  • BLPA uses LPA community labels, then prioritizes node-to-shard reassignment by neighbor count subject to a maximum shard size, repeating until convergence or iteration T.Its stated computational complexity is O(n·dave), where n is the number of nodes and dave is the training graph’s average node degree.Source: §4.1 · pp. 4–5

4.2 Embedding Clustering Method

  • BEKM applies k-means to pretrained GNN node embeddings and prioritizes closer embedding-centroid pairs for shard assignment, subject to the maximum shard size.Its stated computational complexity is O(k · n), for k shards and n nodes.Source: §4.2 · p. 6

4.3 Discussion

  • GraphEraser deterministically unlearns shard models but not graph partitioning, so it performs approximate unlearning; the authors argue revoked data can be deleted from the preprocessed graph without repartitioning.They report empirically quantifying possible information leakage and frame the legal discussion as their understanding of the right to be forgotten.Source: §4.3 · p. 6

5 Learning-based Aggregation

GraphEraser learns shard importance scores for aggregation, then combines partitioning, shard training, score learning, and targeted retraining into an unlearning workflow.

5 Learning-based Aggregation

  • MajAggr uses majority voting, as in, whereas MeanAggr averages shard posterior vectors and predicts the label with the highest aggregated posterior.Source: §5 · pp. 6–7
  • LBAggr learns an importance score for each shard model because shards can contribute differently to predictions, using cross-entropy loss, regularization, and scores constrained to sum to 1.The loss is defined using training-graph node features and neighborhoods, true labels, and shard-model predictions.Source: §5 · p. 7
  • To optimize shard weights, GraphEraser maps negative scores to 0 and uses softmax normalization because direct score normalization made loss unstable across epochs.The mapping follows projected gradient descent [2].Source: §5 · p. 7
  • When revoked nodes were used to train LBAggr, GraphEraser relearns the weights; using a random 10% of training nodes achieved comparable utility to using all nodes.This relearning time counts toward unlearning time, and weights need not be relearned if revoked nodes were not used to train LBAggr.Source: §5 · p. 7

5.1 Putting Things Together: GraphEraser

  • GraphEraser partitions G0 with Algorithm 1 for GCNs and Algorithm 2 otherwise, trains shard models, learns their weights from sampled nodes, and retrains only the corresponding shard after revocation.Source: §5.1 · p. 7

6 Evaluation

Across five public graph datasets and four GNN models, the evaluation examines GraphEraser’s unlearning efficiency and utility, LBAggr, balanced partitioning, and unlearning power.

6.1 Experimental Setup

  • The experiments use five public graph datasets, four two-layer GNNs, and Micro F1 to measure model utility.The datasets comprise three citation graphs and two coauthor graphs; the evaluation also measures unlearning efficiency.Source: §6.1 · p. 8

6.2 Evaluation of Unlearning Efficiency

  • Shard-based methods improve node-unlearning time over Scratch by 4.16× (Cora), 3.08× (Citeseer), 5.40× (Pubmed), 19.25× (CS), and 35.9× (Physics).GraphEraser-BLPA and GraphEraser-BEKM have similar unlearning times to Random. Partitioning is a one-time cost, and prediction costs are mostly below 0.01 second.Source: Figure 4 · p. 9, §6.2 · p. 9

6.3 Evaluation of Model Utility

  • On Cora with GCN, GraphEraser-BLPA scores 0.676 F1 versus Random’s 0.509, while Random is comparable on Pubmed, CS, and Physics.The paper recommends choosing by the role of graph structure: Random when MLP and GNN F1 scores are close, otherwise GraphEraser; for GCN, it favors BLPA over BEKM. BEKM also scores 0.801 versus Scratch’s 0.787 on Cora with GIN.Source: §6.3 · pp. 9–10, Table 4 · p. 10

6.4 Effectiveness of LBAggr

  • On Cora with BLPA and GCN, LBAggr achieves 0.357 higher F1 than MajAggr, and generally improves F1 over MeanAggr and MajAggr in most cases.MajAggr loses information about runner-up classes when shard posteriors assign high confidence to multiple classes; using 10% or 1,000 training nodes gives utility comparable to using all nodes.Source: Table 4 · p. 10, §6.4 · pp. 10–11, Table 6 · p. 11

6.5 Comparison with Existing Balanced Graph Partition Solutions

  • GraphEraser-BEKM and BEKM-Hungarian achieve similar utility, but BEKM-Hungarian’s O(n^3) complexity is much higher than GraphEraser-BEKM’s O(k ·n) and does not scale to large graphs.For GCN, GraphEraser-BLPA and BLPA-LP outperform METIS in utility; BLPA is more efficient than BLPA-LP at comparable utility. GraphEraser supports other balanced partition methods that meet its requirements.Source: §6.5 · pp. 11–12, Table 8 · p. 12, Table 7 · p. 12

6.6 Unlearning Power of GraphEraser

  • Membership-inference attack AUCs for GraphEraser and deterministic unlearning are both close to 0.5, indicating little extra information leakage from GraphEraser.The comparison measures attack AUC for GraphEraser’s fixed-partition unlearning against deterministic unlearning that repartitions and retrains from scratch.Source: Table 9 · p. 12, §6.6 · p. 12

7 Discussion

The discussion frames GraphEraser as supporting regulatory deletion and practical service maintenance while noting its adaptive-unlearning limitation and shard-maintenance tradeoffs. It also describes how to handle inserted nodes.

Guarantee to the right to be forgotten

  • GraphEraser meets the right-to-be-forgotten requirement when the model is trained without the revoked sample, though membership inference remains possible and defenses can be added [10].The authors describe those attacks as orthogonal to the work’s primary goal of complying with legitimate regulations.Source: §7 · p. 13

Compatibility with Commercial Graph Services

  • After one-time graph partitioning, GraphEraser uses the existing shard-training pipeline and handles removal requests by retraining only the shard model containing deleted samples.The paper says this lowers maintenance effort relative to existing services.Source: §7 · p. 13

Additional Cost of Maintaining Massive Shards

  • Shard-based methods add prediction time and storage costs, but the paper reports prediction overhead is much less than global-model retraining time and argues computation costs exceed storage costs.At the time of writing, storage costs were $0.026/GB per month on Google Cloud, $0.023/GB per month on Amazon Web Services, and $0.018/GB per month on Azure; cheapest GPU rentals started at $0.35/hour, $0.526/hour, and $0.90/hour, respectively.Source: §7 · p. 13

Adaptive Machine Unlearning

  • GraphEraser satisfies (α,β,γ)-unlearning in the non-adaptive setting but not the adaptive setting, following results for distributed unlearning methods such as SISA [24].The definition requires an unlearning algorithm’s output to be similar to retraining from scratch.Source: §7 · p. 13

Handling Different Scenarios

  • For node insertions, GraphEraser can place the node in the shard containing the most of its neighbors and retrain that shard’s model.The paper refers readers to Appendix I for handling removal requests arising independently from a specific community.Source: §7 · p. 13

8 Related Work

Related work distinguishes exact and approximate machine unlearning, then surveys balanced graph partitioning methods that trade off structural information, scalability, and node features.

Machine Unlearning

  • Deterministic unlearning fully removes revoked samples but makes retraining costly, while Cao et al. offer efficient summation-based removal only for models expressible in that form.Approximate unlearning instead seeks a close output distribution to training without the revoked sample.Source: §8 · p. 13
  • (ε, δ)-approximate unlearning [18] is related to differential privacy, but group DP requires more noise for multiple deletions and can reduce model utility.The cited definition bounds the probability of outputs from training without a revoked sample by the approximate unlearning output probability plus δ.Source: §8 · p. 13
  • Prior approximate methods cover k-means [18], linear and logistic regression [23], and convex models [36], with update efficiency or error depending on the method.Izzo et al. reduce per-deletion runtime from quadratic to linear in dimension; Neel et al. [36] provide constant update runtime for a fixed accuracy target.Source: §8 · p. 13
  • Because GNNs are highly non-convex, GraphEraser’s compliance with (ε, δ)-approximate unlearning is difficult to prove theoretically, so the paper empirically assesses leakage via membership inference.The cited related-work discussion says most prior studies address linear or convex models.Source: §8 · pp. 13–14

Balanced Graph Partitioning

  • Balanced graph partitioning methods fall into structural-only strategies, including balanced community detection and direct graph optimization, or feature-and-structure strategies using embeddings and balanced clustering.Balanced label propagation (BLPA-LP) formulates label propagation as a linear program to enforce community-size constraints.Source: §8 · p. 14
  • Direct partitioning optimizes graph cuts or modularity [37]; spectral methods do not scale well, while multilevel methods [2] include METIS, reported as state-of-the-art [3].Multilevel methods contract edges, partition the smaller graph, then unfold it with local improvement.Source: §8 · p. 14
  • Embedding-based balanced clustering includes BEKM-Hungarian and a linear-regression method, whose soft balance constraint cannot precisely control cluster size.BEKM-Hungarian casts node reassignment as a matching problem approximately solved by the Hungarian algorithm.Source: §8 · p. 14

9 Conclusion … C Convergence Analysis

GraphEraser provides a graph-specific GNN unlearning framework with balanced graph partitioning and learned aggregation; the appendices describe GNN operations, illustrate shard imbalance, and evaluate partition-algorithm convergence.

9 Conclusion

  • GraphEraser introduces a GNN unlearning pipeline for node and edge requests, balanced graph partition algorithms that preserve structure, and learning-based aggregation, evaluated on five datasets and four GNN models.The paper reports that these components deliver high unlearning efficiency and model utility.Source: §9 · p. 14

A Details of Graph Neural Networks

  • After ℓ message-passing steps, a node embedding incorporates information from its ℓ-hop neighbors through aggregation and update operations.Each node receives messages from its neighbors, aggregates them into an intermediate embedding, and updates its embedding.Source: A Details of Graph Neural Networks · p. 18
  • GIN sums neighbor embeddings, SAGE averages them, GCN uses symmetric normalization, and GAT weights them by learned attention scores.These are presented as four widely used aggregation operations.Source: A Details of Graph Neural Networks · p. 18
  • GNNs can update embeddings by linear combination, concatenation, or interpolation, and node-classification models stack message-passing modules with a softmax layer.The paper notes that linear updates can cause over-smoothing, while concatenation and interpolation are alternatives; the model outputs class-posterior probabilities for each node.Source: A Details of Graph Neural Networks · p. 18

B Visualization of Classical LPA

C Convergence Analysis

  • Within 30 iterations, the ratio of nodes moving between shards approaches zero for BLPA and BEKM on all five datasets, motivating T = 30 in the experiments.Convergence is defined as no nodes changing shards between consecutive iterations.Source: Figure 6 · p. 18, C Convergence Analysis · p. 19

D Correlation between Importance Scores and Shard Properties · E Role of Graph Structure

LBAggr assigns greater importance to more accurate shard models and favors one shard among those trained on similar graphs, while GraphEraser’s utility advantage over Random generally grows as graph structure becomes more important.

D Correlation between Importance Scores and Shard Properties

  • The shard-importance investigation examines how shard properties relate to importance scores assigned by LBAggr.The experiment is intended to support evidence of LBAggr’s effectiveness reported in Section 6.4.Source: D Correlation between Importance… · p. 19
  • More accurate shard models generally receive higher importance scores, guiding LBAggr to select shards with stronger prediction capability.Figure 7 shows this correlation for GAT with GraphEraser-BLPA and GraphEraser-BEKM on Cora.Source: Figure 7 · p. 19, D Correlation between Importance… · p. 19

E Role of Graph Structure

  • When graph structure is more important, GraphEraser’s utility improvement over Random is greater in most cases, despite some outliers.The trend is assessed using Pearson correlation scores across the Figure 9 subfigures.Source: E Role of Graph Structure · p. 19
  • The graph-structure experiment compares GraphEraser with Random on Cora and Citeseer after deleting training-graph edges at rates from 0% to 90% in 10% increments.The edge-deletion ratio models the significance of graph structure; utility improvement is the measured performance gap.Source: E Role of Graph Structure · p. 19

D Correlation between Importance Scores and Shard Properties

  • Among shards with similar graph embeddings, LBAggr typically assigns a higher score to one and a lower score to another, reducing redundant information.The shard embeddings are means of node embeddings from a pretrained GNN, projected into two dimensions with t-SNE.Source: Figure 8 · p. 19, D Correlation between Importance… · p. 19
  • Figure 8 plots Cora shard embeddings, with circle size proportional to shard importance score.Each circle represents the mean node embedding of a shard.Source: Figure 8 · p. 19

F Robustness of GraphEraser

GraphEraser generally maintains model utility under node unlearning, with little F1-score decline below a 10% deletion ratio in most settings. Uniform versus non-uniform deletion distributions do not significantly change its robustness, though larger deletions can reduce utility.

F Robustness of GraphEraser

  • The experiments compare random deletion across all shards with deletion restricted to the half of shards having larger sizes.These define the uniform and non-uniform unlearning-request distributions, respectively.Source: F Robustness of GraphEraser · p. 19
  • Uniform and non-uniform deletion distributions do not significantly affect GraphEraser’s robustness to node deletion.The section concludes that GraphEraser is robust to deletion of a large number of nodes, despite utility degradation in some higher-deletion cases.Source: F Robustness of GraphEraser · p. 19
  • For most settings, F1 scores do not drop significantly below 10% node deletion; for Pubmed GCN, 50% deletion reduces utility from 0.72 to 0.56.The authors note that deleting 50% of nodes is unlikely in practice.Source: F Robustness of GraphEraser · p. 19, Figure 10 · p. 20

G Ablation Study

The ablation study finds that increasing the shard count improves unlearning efficiency while slightly reducing F1, whereas the shard-size balance parameter δ has only a slight impact on utility. The authors recommend choosing the shard count based on graph size and setting δ to its lower bound for efficiency.

Number of Shards k

  • Increasing the number of shards reduces average unlearning time but slightly lowers F1 across four GNNs, with GCN showing the largest utility drop.On Physics, shard counts from 2 to 100 were tested; the authors suspect GCN is more affected because partitioning reduces the node-degree information used for normalization.Source: G Ablation Study · pp. 20–21, Figure 11 · p. 21

Maximum Number of Nodes in Each Shard δ

  • Across five datasets, δ has only a slight impact on utility, so the authors set it to ⌈n/k⌉, the balanced-shard lower bound, for best efficiency.The experiments vary δ from ⌈n/k⌉ to n using a scaling parameter γ from 0 to 1; at these bounds, BLPA and BEKM reduce to standard LPA and original k-means, respectively.Source: Figure 12 · p. 21, G Ablation Study · p. 21

H Additional Experimental Results on Edge Unlearning · I Community-Dependent Removal · Requests

The additional experiments report edge-unlearning efficiency and utility results similar to node unlearning, and show that community-dependent removal can be handled with limited shard retraining without significant utility loss.

H Additional Experimental Results on Edge Unlearning

Requests

  • GraphEraser can handle requests targeting specific community types because its shard-size-constrained partitioning tends to place nodes from the same community in the same shards.The method is described as a shard-size-constraint version of community detection algorithms.Source: Requests · p. 21
  • For community-dependent requests, only a few shard models need to be retrained..Source: Requests · p. 21
  • Deleting nodes from a single community detected by vanilla LPA does not significantly affect GraphEraser’s model utility.The robustness test gradually deleted the selected community’s nodes, with Figure 14 showing utility against the ratio of unlearned nodes.Source: Requests · p. 21, Figure 14 · p. 22

H Additional Experimental Results on Edge Unlearning

Related papers

Loading 2103.14991v2…