# Unlearning Graph Classifiers with Limited Data Resources

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 37 of its 62 references that are in the map.
- First posted on arXiv 6 Nov 2022.

## Placed in

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

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [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)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Generalizing from a Few Examples: A Survey on Few-Shot Learning](https://mlsanity.com/paper/1904.05046/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Few-Shot Learning with Graph Neural Networks](https://mlsanity.com/paper/1711.04043/) (2017)
- [Graph Neural Networks with convolutional ARMA filters](https://mlsanity.com/paper/1901.01343/) (2019)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks](https://mlsanity.com/paper/2003.08414/) (2020)
- [Algorithms that Remember: Model Inversion Attacks and Data Protection Law](https://mlsanity.com/paper/1807.04644/) (2018)
- [Semi-Supervised Graph Classification: A Hierarchical Graph Perspective](https://mlsanity.com/paper/1904.05003/) (2019)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Geometric Scattering for Graph Data Analysis](https://mlsanity.com/paper/1810.03068/) (2018)
- [Knowledge-aware Coupled Graph Neural Network for Social Recommendation](https://mlsanity.com/paper/2110.03987/) (2021)
- [Graph Convolutional Neural Networks via Scattering](https://mlsanity.com/paper/1804.00099/) (2018)
- [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)

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

- [Machine Unlearning: Solutions and Challenges](https://mlsanity.com/paper/2308.07061/) (2023)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [Machine Unlearning in Generative AI: A Survey](https://mlsanity.com/paper/2407.20516/) (2024)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Breaking the Trilemma of Privacy, Utility, Efficiency via Controllable Machine Unlearning](https://mlsanity.com/paper/2310.18574/) (2023)
- [IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2407.19398/) (2024)
- [Verification of Machine Unlearning is Fragile](https://mlsanity.com/paper/2408.00929/) (2024)
- [Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation](https://mlsanity.com/paper/2405.14407/) (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)
- [DUCK: Distance-based Unlearning via Centroid Kinematics](https://mlsanity.com/paper/2312.02052/) (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)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Machine Unlearning for Recommendation Systems: An Insight](https://mlsanity.com/paper/2401.10942/) (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)
- [UPCORE: Utility-Preserving Coreset Selection for Balanced Unlearning](https://mlsanity.com/paper/2502.15082/) (2025)
- [TAPE: Tailored Posterior Difference for Auditing of Machine Unlearning](https://mlsanity.com/paper/2502.19770/) (2025)
- [SafeMo: Linguistically Grounded Unlearning for Trustworthy Text-to-Motion Generation](https://mlsanity.com/paper/2601.00590/) (2026)
- [Unlearning Inversion Attacks for Graph Neural Networks](https://mlsanity.com/paper/2506.00808/) (2025)
- [Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approach](https://mlsanity.com/paper/2411.03663/) (2024)
- [Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach](https://mlsanity.com/paper/2501.11823/) (2025)
- [Node-level Contrastive Unlearning on Graph Neural Networks](https://mlsanity.com/paper/2503.02959/) (2025)
- [Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2603.18570/) (2026)
- [GDGU: A Gradient Difference-based Graph Unlearning Method for Cyberattack Localization in Electric Vehicle Charging Networks](https://mlsanity.com/paper/2606.19566/) (2026)
- [Graph Transductive Defense: a Two-Stage Defense for Graph Membership Inference Attacks](https://mlsanity.com/paper/2406.07917/) (2024)
- [Targeted Therapy in Data Removal: Object Unlearning Based on Scene Graphs](https://mlsanity.com/paper/2412.00067/) (2024)
- [Unlearning Algorithmic Biases over Graphs](https://mlsanity.com/paper/2505.14945/) (2025)
- [Unlearning of Knowledge Graph Embedding via Preference Optimization](https://mlsanity.com/paper/2507.20566/) (2025)

## Abstract (arXiv)

As the demand for user privacy grows, controlled data removal (machine unlearning) is becoming an important feature of machine learning models for data-sensitive Web applications such as social networks and recommender systems. Nevertheless, at this point it is still largely unknown how to perform efficient machine unlearning of graph neural networks (GNNs); this is especially the case when the number of training samples is small, in which case unlearning can seriously compromise the performance of the model. To address this issue, we initiate the study of unlearning the Graph Scattering Transform (GST), a mathematical framework that is efficient, provably stable under feature or graph topology perturbations, and offers graph classification performance comparable to that of GNNs. Our main contribution is the first known nonlinear approximate graph unlearning method based on GSTs. Our second contribution is a theoretical analysis of the computational complexity of the proposed unlearning mechanism, which is hard to replicate for deep neural networks. Our third contribution are extensive simulation results which show that, compared to complete retraining of GNNs after each removal request, the new GST-based approach offers, on average, a 10.38x speed-up and leads to a 2.6% increase in test accuracy during unlearning of 90 out of 100 training graphs from the IMDB dataset (10% training ratio). Our implementation is available online at https://doi.org/10.5281/zenodo.7613150.