# Graph Unlearning

arXiv: https://arxiv.org/abs/2103.14991 · HTML: https://mlsanity.com/paper/2103.14991/

## Key facts

- Cited by 138 papers in the map (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 58 of its 103 references that are in the map.
- First posted on arXiv 27 Mar 2021.

## Placed in

- LLM safety and security / [Graph unlearning](https://mlsanity.com/safety/graph-unlearning/)

## Builds on (most cited first, 30 of 58)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain](https://mlsanity.com/paper/1708.06733/) (2017)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Exploiting Unintended Feature Leakage in Collaborative Learning](https://mlsanity.com/paper/1805.04049/) (2018)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [ML-Leaks: Model and Data Independent Membership Inference Attacks and Defenses on Machine Learning Models](https://mlsanity.com/paper/1806.01246/) (2018)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Knockoff Nets: Stealing Functionality of Black-Box Models](https://mlsanity.com/paper/1812.02766/) (2018)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [The Secret Revealer: Generative Model-Inversion Attacks Against Deep Neural Networks](https://mlsanity.com/paper/1911.07135/) (2019)

## Built on by (most cited first, 30 of 138)

- [SalUn: Empowering Machine Unlearning via Gradient-based Weight Saliency in Both Image Classification and Generation](https://mlsanity.com/paper/2310.12508/) (2023)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Rethinking Machine Unlearning for Large Language Models](https://mlsanity.com/paper/2402.08787/) (2024)
- [Model Sparsity Can Simplify Machine Unlearning](https://mlsanity.com/paper/2304.04934/) (2023)
- [The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining](https://mlsanity.com/paper/2203.07320/) (2022)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Machine Unlearning: Solutions and Challenges](https://mlsanity.com/paper/2308.07061/) (2023)
- [OpenGraph: Towards Open Graph Foundation Models](https://mlsanity.com/paper/2403.01121/) (2024)
- [Backdoor Defense with Machine Unlearning](https://mlsanity.com/paper/2201.09538/) (2022)
- [A Survey on Federated Unlearning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/2310.20448/) (2023)
- [Position: LLM Unlearning Benchmarks are Weak Measures of Progress](https://mlsanity.com/paper/2410.02879/) (2024)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [AnyGraph: Graph Foundation Model in the Wild](https://mlsanity.com/paper/2408.10700/) (2024)
- [Scissorhands: Scrub Data Influence via Connection Sensitivity in Networks](https://mlsanity.com/paper/2401.06187/) (2024)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [Learn What You Want to Unlearn: Unlearning Inversion Attacks against Machine Unlearning](https://mlsanity.com/paper/2404.03233/) (2024)
- [Certified Graph Unlearning](https://mlsanity.com/paper/2206.09140/) (2022)
- [Challenging Forgets: Unveiling the Worst-Case Forget Sets in Machine Unlearning](https://mlsanity.com/paper/2403.07362/) (2024)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Machine Unlearning: A Comprehensive Survey](https://mlsanity.com/paper/2405.07406/) (2024)
- [Deep Regression Unlearning](https://mlsanity.com/paper/2210.08196/) (2022)
- [Unlearning Graph Classifiers with Limited Data Resources](https://mlsanity.com/paper/2211.03216/) (2022)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Making Recommender Systems Forget: Learning and Unlearning for Erasable Recommendation](https://mlsanity.com/paper/2203.11491/) (2022)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [SAFE: Machine Unlearning With Shard Graphs](https://mlsanity.com/paper/2304.13169/) (2023)
- [WAGLE: Strategic Weight Attribution for Effective and Modular Unlearning in Large Language Models](https://mlsanity.com/paper/2410.17509/) (2024)
- [Watermarking Graph Neural Networks based on Backdoor Attacks](https://mlsanity.com/paper/2110.11024/) (2021)

## Abstract (arXiv)

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× (small dataset) to 35.94× (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.footnoteOur code is available at urlhttps://github.com/MinChen00/Graph-Unlearning.