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

Machine unlearning must remove requested data’s influence without repeatedly paying the cost of full retraining, and naïve shard partitioning can damage graph structure. GraphEraser uses balanced graph partitioning, shard models, and learned aggregation for GNN unlearning, achieving faster unlearning and higher reported F1 scores while retaining comparable utility. The framework is approximate because shard models are deterministically unlearned but graph partitioning is not.

  • Problem

    Machine unlearning for GNNs must remove requested data influence efficiently, while directly applying SISA can damage graph structural information and model utility.

  • Method

    GraphEraser partitions training graphs into balanced shards, trains shard models, and aggregates their predictions using learned importance scores.

  • Results

    GraphEraser reports 2.06× to 35.94× shorter unlearning time than retraining from scratch, up to 62.5% higher F1 than random partitioning, and up to 112% higher F1 than majority-vote aggregation.

  • Takeaways & Limitations

    GraphEraser provides a graph-specific unlearning framework with efficient retraining and model utility evaluated across five real-world graph datasets and four GNN models.

  • Takeaways & Limitations

    GraphEraser performs approximate unlearning because shard models are deterministic but graph partitioning is not.

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 machine unlearning for graph data, where retraining is costly and naïve SISA partitioning can damage structural information. It combines balanced graph partitioning with learned shard aggregation and improves unlearning efficiency and model utility in experiments.

  • Machine unlearning removes the influence of requested training data, while retraining from scratch can be computationally prohibitive on large datasets.
  • SISA partitions training data into disjoint shards and trains separate models, but directly applying this strategy to graphs can severely damage structural information.
  • GraphEraser proposes two balanced graph partition algorithms that preserve graph information while avoiding highly unbalanced shards.
  • GraphEraser adds a learning-based aggregation method that optimizes shard-model importance scores to improve global model utility.
  • 2.06× to 35.94× shorter average unlearning time is reported versus retraining from scratch, with comparable utility; F1 score is up to 62.5% higher than random partitioning.
  • Experiments use five real-world graph datasets and four state-of-the-art GNN models to evaluate unlearning efficiency and model utility.

2 Preliminaries

The preliminaries define attributed graphs and GNN message passing, motivate machine unlearning, and describe SISA as an efficient shard-based alternative to full retraining.

  • An attributed graph is represented by nodes V, adjacency matrix A, and feature matrix X; edges connect node pairs.
  • GNNs aggregate neighboring-node information to form embeddings used for tasks including node classification, link prediction, and graph classification.
  • This paper focuses on node classification, predicting a node’s label from its features and neighbors’ information through message passing.
  • Machine unlearning requires removing a revoked sample and its influence on the resulting model, whereas full retraining becomes costly for complex models and large datasets.
  • SISA trains separate models on disjoint data shards and retrains only the shard containing a deleted sample, reducing retraining time.

3 Graph Unlearning

Graph unlearning distinguishes node and edge requests and requires both efficient retraining and comparable prediction utility. GraphEraser addresses these requirements through balanced partitioning, shard training, and aggregation.

  • Node unlearning removes a node, its features, and incident edges from the training graph before obtaining the unlearned model.
  • Edge unlearning removes a requested edge while retaining the features of its two endpoint nodes.
  • The objectives are high unlearning efficiency and comparable model utility, with prediction accuracy ideally close to retraining from scratch.
  • Balanced shards make shard retraining times similar, while preserving structural properties supports prediction accuracy in node classification.
  • GraphEraser uses balanced graph partition, parallel shard-model training, and shard-model aggregation as its three framework phases.

4 Balanced Graph Partition

GraphEraser balances graph shards while preserving structural information, using community detection or embedding clustering and explicit size constraints. Its discussion also frames the framework as approximate because partitioning is not deterministic.

  • Partition Strategies: Graph partitioning considers node features alone, graph structure alone, or both through node embeddings.Random partitioning is treated as a baseline; the latter two strategies target comparable model utility by preserving graph information.
  • Balanced Partition Principle: Directly applying community detection or clustering can create highly unbalanced shards, reducing the efficiency benefit of unlearning.The imbalance follows from structural properties of real-world graphs and can concentrate revoked samples in a large shard.
  • BLPA: BLPA uses community detection with label propagation, moving nodes toward destination shards with many neighbors while enforcing a maximum shard size δ.It initializes random shards, builds and sorts reassignment profiles, then accepts moves whose destination shard remains within δ.
  • BLPA: O(n·dave) is BLPA’s computational complexity, where n is the node count and dave is the training graph’s average node degree.The complexity depends on the size of the reassignment profile, whose tuples correspond to node neighbors.
  • Discussion: BLPA’s convergence is assessed empirically rather than proved theoretically, with moved-node ratios approaching zero within 30 iterations on five datasets.The experiments therefore set the maximum iteration count T to 30.
  • BEKM: BEKM clusters pretrained-GNN node embeddings using distances to centroids while limiting each shard to at most δ embeddings.The embeddings incorporate both node features and graph structure; direct k-means can otherwise produce substantially different shard sizes.
  • Discussion: GraphEraser permits alternative balanced graph partition methods, but its graph partitioning is nondeterministic, making the overall unlearning approximate.The authors empirically quantify information leakage and report that GraphEraser does not leak much extra information.

5 Learning-based Aggregation

GraphEraser aggregates shard-model predictions either by voting, posterior averaging, or learned importance scores. Its workflow partitions the graph, trains shard models, learns aggregation scores, and uses the resulting models for prediction.

  • Existing Aggregation Strategies: Majority voting selects the label predicted most often across shard models, while posterior averaging predicts the highest aggregated posterior.These strategies are called MajAggr and MeanAggr, respectively.
  • Learning-based Aggregation: LBAggr learns an importance score for each shard model because shard models can contribute differently to the final prediction.The scores are learned using a loss function rather than assigning every shard equal importance.
  • Learning-based Aggregation: The aggregation objective uses node features, neighborhoods, true labels, shard-model outputs, importance scores, cross-entropy loss, and regularization.The importance scores are constrained to sum to 1, and the regularization term is used to reduce overfitting.
  • Optimization: Projected gradient descent maps negative importance scores to zero, while softmax normalization stabilizes score normalization across iterations.The authors report that normalizing by the current score sum produced highly unstable loss across epochs.
  • Overall Workflow: GraphEraser’s workflow selects a partition algorithm based on GNN type, trains shard models, and learns importance scores from randomly sampled training nodes.For GCNs it invokes Algorithm 1; otherwise it invokes Algorithm 2, then uses the shard models and scores to predict new samples.

6 Evaluation

GraphEraser is evaluated across five graph datasets and four GNN models for unlearning efficiency, model utility, aggregation, partitioning, and information leakage. Results show substantial efficiency gains, dataset- and model-dependent utility differences, and trade-offs among partition and aggregation strategies.

  • Unlearning Efficiency: GraphEraser’s shard-based methods improve unlearning efficiency more on larger datasets, with reported improvements of 4.16× on Cora, 3.08× on Citeseer, 5.40× on Pubmed, 19.25× on CS, and 35.9× on Physics.The comparison is against the Scratch method, and the pattern is consistent across the four GNN models.
  • Unlearning Efficiency: Less than 30s of relearning time is required for LBAggr on most datasets, making it negligible compared with retraining shard models.LBAggr learns importance scores from only a small portion of training-graph nodes.
  • Model Utility: Graph structure affects utility: GraphEraser methods outperform Random on Cora and Citeseer, while Random is comparable on Pubmed, CS, and Physics.The authors relate this difference to how much graph structural information contributes to the target GNN’s utility.
  • Model Utility: When the MLP–GNN F1 gap is small, Random can provide comparable utility with easier implementation; otherwise, GraphEraser-BLPA or GraphEraser-BEKM is preferred.This guideline is based on the observed relationship between graph-structure contribution and shard-based unlearning behavior.
  • Partitioning: GraphEraser-BLPA is recommended for GCN, whereas GraphEraser-BEKM is recommended for other listed GNN architectures; BEKM-Hungarian has O(n^3) complexity versus GraphEraser-BEKM’s O(k ·n).For GCN, community-detection methods preserve local structure and node degree; BEKM-Hungarian is reported as not scalable to large graphs.
  • Aggregation: GCN benefits most from LBAggr, while GIN benefits least; BLPA benefits most because LBAggr restores global structural information through shard importance scores.BLPA captures local structure but loses some global structure, which LBAggr helps represent during aggregation.
  • Aggregation: Using 10% of nodes or a fixed 1,000 nodes to learn LBAggr importance scores achieves comparable utility to using all nodes.The authors suggest using the minimum of 10% and 1,000 nodes, with the same conclusion reported for BLPA.
  • Unlearning Power: GraphEraser’s leakage is evaluated by comparing membership-inference attack performance when partitions are retained versus when the graph is repartitioned and retrained from scratch.The retained-partition procedure deletes revoked nodes and retrains affected shard models, while the comparison retrains newly partitioned shard models.

7 Discussion

GraphEraser addresses practical unlearning constraints by supporting node insertion and discussing privacy and deployment considerations. Its right-to-be-forgotten guarantee is framed around training without the revoked sample, while stronger defenses remain add-ons.

  • The right-to-be-forgotten requirement is considered satisfied when the model is trained without the revoked sample, even though membership inference may remain possible.
  • Defense mechanisms against potential membership-inference attacks can be deployed as add-ons to GraphEraser.
  • After graph partitioning is defined, it can remain fixed, while shard-model training follows the same process as existing commercial graph-learning services.
  • GraphEraser handles node insertion by assigning a new node to the shard containing the largest number of its neighbors, then retraining that shard.

8 Related Work

Prior machine-unlearning work spans deterministic retraining and approximate methods, but theoretical approximate guarantees have largely focused on simpler model classes. Related graph-partitioning research addresses balance through constrained community detection, graph objectives, or balanced embedding clustering.

  • Machine Unlearning: Deterministic unlearning removes revoked samples and retrains the global model from scratch, whereas approximate unlearning seeks lower computational cost.
  • Machine Unlearning: (ε, δ)-approximate unlearning requires the unlearned model’s output distribution to remain close to that of a model trained without the revoked sample.
  • Machine Unlearning: Differential privacy is not directly adopted for group deletions because group-level noise can reduce model utility.
  • Machine Unlearning: Most prior theoretically grounded approximate-unlearning studies address linear or convex models, while GNNs are highly non-convex and require empirical leakage evaluation here.
  • Balanced Graph Partitioning: Balanced graph partitioning modifies community detection, optimizes graph criteria, or clusters node embeddings with balanced assignments.

9 Conclusion

The paper concludes by presenting GraphEraser as a GNN unlearning framework built on graph-aware shard partitioning and aggregation. Its surrounding GNN discussion describes message passing, aggregation, updating, and empirical shard behavior relevant to model utility and efficiency.

  • Conclusion: GraphEraser supports node and edge unlearning through a general GNN machine-unlearning pipeline.
  • Conclusion: Its approach combines balanced graph partition algorithms with learning-based aggregation to preserve structural information and improve model utility.
  • GNN Background: GNN message passing aggregates neighbor information and updates each node embedding through paired aggregation and updating operations.
  • GNN Background: GIN sums neighbor embeddings, SAGE averages them, GCN uses symmetric normalization, and GAT weights neighbors by attention scores.
  • GNN Background: Linear-combination updates can suffer over-smoothing, while concatenation and interpolation retain information from the current node embedding.
  • GNN Background: A GNN model stacks message-passing layers with a softmax layer and maps node features and adjacency information to posterior predictions.
  • Empirical Observations: Classical LPA produces visibly unequal shard sizes on Cora, with marked large and small shards.
  • Empirical Observations: Convergence experiments evaluate BLPA and BEKM by tracking the ratio of nodes moving between shards across iterations.

D Correlation between Importance Scores and Shard Properties

The analysis examines whether shard importance scores reflect predictive accuracy and graph properties. It relates importance to shard F1 scores and uses shard embeddings and edge-deletion experiments to study structural effects.

  • The importance-score analysis tests whether shard properties influence the learned aggregation weights.
  • LBAggr generally assigns higher importance scores to shard models with more accurate predictions.
  • Shard embeddings are formed by averaging pretrained node embeddings and projected into two dimensions with t-SNE for structural analysis.
  • Figure 7 uses shard-model F1 score on the x-axis and shard importance score on the y-axis to show their correlation for GAT models.
  • The edge-deletion experiment compares GraphEraser with Random on Cora and Citeseer as the fraction of deleted training-graph edges varies.

F Robustness of GraphEraser

GraphEraser remains robust under varying node-removal patterns and ratios, with substantial utility degradation appearing mainly at very high deletion rates. The provided experiments also examine how graph-structure importance relates to its utility improvement over random partitioning.

  • Node-removal ratio: GraphEraser’s F1 scores generally do not drop significantly when fewer than 10% of nodes are unlearned.This holds across the evaluated settings in Figure 10.
  • Node-removal ratio: At 50% node deletion, GCN on Pubmed drops from 0.72 to 0.56 in one reported setting.The paper notes that deleting 50% of nodes is unlikely in practice.
  • Request distribution: Uniform and non-uniform deletion distributions do not significantly differ in their effects on robustness.Non-uniform requests delete nodes only from half of the larger shards.
  • Structure sensitivity: Figure 9 relates the ratio of edge deletion, used as an indicator of graph-structure importance, to GraphEraser’s utility improvement over Random.
  • Experimental setup: Figure 10 evaluates model utility under uniform and non-uniform unlearning requests across three datasets.

G Ablation Study

The ablation study shows a trade-off between shard count, efficiency, and utility, while the shard-size parameter δ has little effect on utility. The experiments motivate selecting shard count according to graph size and using balanced shards for efficiency.

  • Number of Shards k: Increasing the number of shards decreases average unlearning time but slightly decreases F1 scores across four GNN models on Physics.GCN experiences the largest utility drop, and the paper recommends selecting shard count based on training-graph size.
  • Maximum Number of Nodes in Each Shard δ: The maximum nodes per shard δ controls partition balance, ranging from balanced shards at ⌈n/k⌉ to unconstrained shard sizes at n.At these bounds, the methods reduce to standard LPA or original k-means variants.
  • Maximum Number of Nodes in Each Shard δ: δ has only a slight impact on model utility across GraphEraser-BLPA and GraphEraser-BEKM on five datasets.The study varies δ through a scaling parameter γ from 0 to 1.
  • Maximum Number of Nodes in Each Shard δ: The experiments set δ = ⌈n/k⌉ for all datasets because this choice provides the best efficiency.

H Additional Experimental Results on Edge Unlearning

Additional experiments show that GraphEraser extends to edge unlearning with conclusions similar to node unlearning. It also remains robust when requests concentrate within a single community, where only a few shard models need retraining.

  • Edge Unlearning: Edge-unlearning experiments evaluate both efficiency and model utility, reaching conclusions similar to those for node unlearning.Figure 13 and Table 10 report the corresponding results.
  • Community-dependent Requests: Community-dependent requests can require retraining only a few shard models because nodes from specific communities tend to share shards.GraphEraser supports this setting through shard-size-constrained community partitioning.
  • Community-dependent Requests: Deleting nodes from a single vanilla-LPA community does not significantly affect GraphEraser’s model utility.The experiment progressively deletes nodes associated with one selected community.
Loading 2103.14991v2…