# Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 40 of its 51 references that are in the map.
- First posted on arXiv 17 Aug 2024.

## Placed in

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

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [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)
- [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)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics](https://mlsanity.com/paper/1908.02591/) (2019)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [DeepInf: Social Influence Prediction with Deep Learning](https://mlsanity.com/paper/1807.05560/) (2018)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited](https://mlsanity.com/paper/2202.03580/) (2022)
- [Membership Inference Attack on Graph Neural Networks](https://mlsanity.com/paper/2101.06570/) (2021)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Certified Graph Unlearning](https://mlsanity.com/paper/2206.09140/) (2022)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [Unlearning Graph Classifiers with Limited Data Resources](https://mlsanity.com/paper/2211.03216/) (2022)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)

## Built on by (most cited first, 14 of 14)

- [OpenGU: A Comprehensive Benchmark for Graph Unlearning](https://mlsanity.com/paper/2501.02728/) (2025)
- [Towards Reliable Forgetting: A Survey on Machine Unlearning Verification](https://mlsanity.com/paper/2506.15115/) (2025)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [SORSA: Singular Values and Orthonormal Regularized Singular Vectors Adaptation of Large Language Models](https://mlsanity.com/paper/2409.00055/) (2024)
- [Unlearning Inversion Attacks for Graph Neural Networks](https://mlsanity.com/paper/2506.00808/) (2025)
- [Adaptive Graph Unlearning](https://mlsanity.com/paper/2505.12614/) (2025)
- [Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2603.18570/) (2026)
- [Variance-Reduced (varepsilon,δ)-Unlearning using Forget Set Gradients](https://mlsanity.com/paper/2602.14938/) (2026)
- [TRU: Targeted Reverse Update for Efficient Multimodal Recommendation Unlearning](https://mlsanity.com/paper/2604.02183/) (2026)
- [Stable Multimodal Graph Unlearning via Feature-Dimension Aware Quantile Selection](https://mlsanity.com/paper/2605.03303/) (2026)
- [SoK: Unlearnability and Unlearning for Model Dememorization](https://mlsanity.com/paper/2605.11592/) (2026)
- [Closed-Form Node Classification with Exact Graph Unlearning](https://mlsanity.com/paper/2605.25662/) (2026)
- [CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion](https://mlsanity.com/paper/2609.08244/) (2026)
- [From Mathematical to Executable Certificates for Machine Unlearning](https://mlsanity.com/paper/2610.02268/) (2026)

## Abstract (arXiv)

Graph unlearning has emerged as a pivotal research area for ensuring privacy protection, given the widespread adoption of Graph Neural Networks (GNNs) in applications involving sensitive user data. Among existing studies, certified graph unlearning is distinguished by providing robust privacy guarantees. However, current certified graph unlearning methods are impractical for large-scale graphs because they necessitate the costly re-computation of graph propagation for each unlearning request. Although numerous scalable techniques have been developed to accelerate graph propagation for GNNs, their integration into certified graph unlearning remains uncertain as these scalable approaches introduce approximation errors into node embeddings. In contrast, certified graph unlearning demands bounded model error on exact node embeddings to maintain its certified guarantee. To address this challenge, we present ScaleGUN, the first approach to scale certified graph unlearning to billion-edge graphs. ScaleGUN integrates the approximate graph propagation technique into certified graph unlearning, offering certified guarantees for three unlearning scenarios: node feature, edge, and node unlearning. Extensive experiments on real-world datasets demonstrate the efficiency and unlearning efficacy of ScaleGUN. Remarkably, ScaleGUN accomplishes (ε,δ)=(1,10-4) certified unlearning on the billion-edge graph ogbn-papers100M in 20 seconds for a 5,000 random edge removal request -- of which only 5 seconds are required for updating the node embeddings -- compared to 1.91 hours for retraining and 1.89 hours for re-propagation. Our code is available at https://github.com/luyi256/ScaleGUN.