# Certified Graph Unlearning

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 34 of its 44 references that are in the map.
- First posted on arXiv 18 Jun 2022.

## Placed in

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

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [VectorNet: Encoding HD Maps and Agent Dynamics from Vectorized Representation](https://mlsanity.com/paper/2005.04259/) (2020)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [YFCC100M: The New Data in Multimedia Research](https://mlsanity.com/paper/1503.01817/) (2015)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction](https://mlsanity.com/paper/2111.00064/) (2021)
- [ETA Prediction with Graph Neural Networks in Google Maps](https://mlsanity.com/paper/2108.11482/) (2021)
- [Graph Attention Multi-Layer Perceptron](https://mlsanity.com/paper/2206.04355/) (2022)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training](https://mlsanity.com/paper/2104.09376/) (2021)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [Stability of Graph Scattering Transforms](https://mlsanity.com/paper/1906.04784/) (2019)

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

- [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)
- [Model Sparsity Can Simplify Machine Unlearning](https://mlsanity.com/paper/2304.04934/) (2023)
- [To Generate or Not? Safety-Driven Unlearned Diffusion Models Are Still Easy To Generate Unsafe Images ... For Now](https://mlsanity.com/paper/2310.11868/) (2023)
- [Simplicity Prevails: Rethinking Negative Preference Optimization for LLM Unlearning](https://mlsanity.com/paper/2410.07163/) (2024)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [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)
- [Unlearning Graph Classifiers with Limited Data Resources](https://mlsanity.com/paper/2211.03216/) (2022)
- [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)
- [Machine Unlearning of Federated Clusters](https://mlsanity.com/paper/2210.16424/) (2022)
- [A Probabilistic Perspective on Unlearning and Alignment for Large Language Models](https://mlsanity.com/paper/2410.03523/) (2024)
- [Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projection](https://mlsanity.com/paper/2302.08990/) (2023)
- [MultiDelete for Multimodal Machine Unlearning](https://mlsanity.com/paper/2311.12047/) (2023)
- [Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions](https://mlsanity.com/paper/2409.09778/) (2024)
- [Targeted Unlearning with Single Layer Unlearning Gradient](https://mlsanity.com/paper/2407.11867/) (2024)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [Distill to Delete: Unlearning in Graph Networks with Knowledge Distillation](https://mlsanity.com/paper/2309.16173/) (2023)
- [Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protection](https://mlsanity.com/paper/2307.06422/) (2023)
- [A Survey of Graph Unlearning](https://mlsanity.com/paper/2310.02164/) (2023)
- [Robust Machine Unlearning for Quantized Neural Networks via Adaptive Gradient Reweighting with Similar Labels](https://mlsanity.com/paper/2503.13917/) (2025)
- [Label Smoothing Improves Machine Unlearning](https://mlsanity.com/paper/2406.07698/) (2024)
- [GraphGuard: Detecting and Counteracting Training Data Misuse in Graph Neural Networks](https://mlsanity.com/paper/2312.07861/) (2023)
- [OpenGU: A Comprehensive Benchmark for Graph Unlearning](https://mlsanity.com/paper/2501.02728/) (2025)
- [Model Collapse Is Not a Bug but a Feature in Machine Unlearning for LLMs](https://mlsanity.com/paper/2507.04219/) (2025)
- [A Comprehensive Data-centric Overview of Federated Graph Learning](https://mlsanity.com/paper/2507.16541/) (2025)
- [Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgery](https://mlsanity.com/paper/2510.22124/) (2025)

## Abstract (arXiv)

Graph-structured data is ubiquitous in practice and often processed using graph neural networks (GNNs). With the adoption of recent laws ensuring the ``right to be forgotten'', the problem of graph data removal has become of significant importance. To address the problem, we introduce the first known framework for certified graph unlearning of GNNs. In contrast to standard machine unlearning, new analytical and heuristic unlearning challenges arise when dealing with complex graph data. First, three different types of unlearning requests need to be considered, including node feature, edge and node unlearning. Second, to establish provable performance guarantees, one needs to address challenges associated with feature mixing during propagation. The underlying analysis is illustrated on the example of simple graph convolutions (SGC) and their generalized PageRank (GPR) extensions, thereby laying the theoretical foundation for certified unlearning of GNNs. Our empirical studies on six benchmark datasets demonstrate excellent performance-complexity trade-offs when compared to complete retraining methods and approaches that do not leverage graph information. For example, when unlearning 20% of the nodes on the Cora dataset, our approach suffers only a 0.1% loss in test accuracy while offering a 4-fold speed-up compared to complete retraining. Our scheme also outperforms unlearning methods that do not leverage graph information with a 12% increase in test accuracy for a comparable time complexity.