# IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 69 references that are in the map.
- First posted on arXiv 28 Jul 2024.

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

- [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)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [GMAN: A Graph Multi-Attention Network for Traffic Prediction](https://mlsanity.com/paper/1911.08415/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Session-based Recommendation with Graph Neural Networks](https://mlsanity.com/paper/1811.00855/) (2018)
- [Unrolling SGD: Understanding Factors Influencing Machine Unlearning](https://mlsanity.com/paper/2109.13398/) (2021)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakage](https://mlsanity.com/paper/2206.03426/) (2022)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Graph Transformation Policy Network for Chemical Reaction Prediction](https://mlsanity.com/paper/1812.09441/) (2018)
- [A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking](https://mlsanity.com/paper/2210.07494/) (2022)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Adapting Membership Inference Attacks to GNN for Graph Classification: Approaches and Implications](https://mlsanity.com/paper/2110.08760/) (2021)
- [Unlearning Graph Classifiers with Limited Data Resources](https://mlsanity.com/paper/2211.03216/) (2022)

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

- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Verification of Machine Unlearning is Fragile](https://mlsanity.com/paper/2408.00929/) (2024)
- [CEGA: A Cost-Effective Approach for Graph-Based Model Extraction and Acquisition](https://mlsanity.com/paper/2506.17709/) (2025)
- [OpenGU: A Comprehensive Benchmark for Graph Unlearning](https://mlsanity.com/paper/2501.02728/) (2025)
- [ATOM: A Framework of Detecting Query-Based Model Extraction Attacks for Graph Neural Networks](https://mlsanity.com/paper/2503.16693/) (2025)
- [Towards Reliable Forgetting: A Survey on Machine Unlearning Verification](https://mlsanity.com/paper/2506.15115/) (2025)
- [Forget Vectors at Play: Universal Input Perturbations Driving Machine Unlearning in Image Classification](https://mlsanity.com/paper/2412.16780/) (2024)
- [CREDIT: Certified Ownership Verification of Deep Neural Networks Against Model Extraction Attacks](https://mlsanity.com/paper/2602.20419/) (2026)
- [FROG: Fair Removal on Graphs](https://mlsanity.com/paper/2503.18197/) (2025)
- [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)
- [Efficient Knowledge Graph Unlearning with Zeroth-order Information](https://mlsanity.com/paper/2508.14013/) (2025)
- [Adaptive Graph Unlearning](https://mlsanity.com/paper/2505.12614/) (2025)
- [GDGU: A Gradient Difference-based Graph Unlearning Method for Cyberattack Localization in Electric Vehicle Charging Networks](https://mlsanity.com/paper/2606.19566/) (2026)
- [Unlearning Algorithmic Biases over Graphs](https://mlsanity.com/paper/2505.14945/) (2025)
- [Graph Unlearning via Embedding Reconstruction -- A Range-Null Space Decomposition Approach](https://mlsanity.com/paper/2508.02044/) (2025)
- [Factor Decorrelation Enhanced Data Removal from Deep Predictive Models](https://mlsanity.com/paper/2509.23443/) (2025)
- [Forget and Explain: Transparent Verification of GNN Unlearning](https://mlsanity.com/paper/2512.07450/) (2025)
- [A Robust Certified Machine Unlearning Method Under Distribution Shift](https://mlsanity.com/paper/2601.06967/) (2026)
- [Stable Multimodal Graph Unlearning via Feature-Dimension Aware Quantile Selection](https://mlsanity.com/paper/2605.03303/) (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)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have been increasingly deployed in a plethora of applications. However, the graph data used for training may contain sensitive personal information of the involved individuals. Once trained, GNNs typically encode such information in their learnable parameters. As a consequence, privacy leakage may happen when the trained GNNs are deployed and exposed to potential attackers. Facing such a threat, machine unlearning for GNNs has become an emerging technique that aims to remove certain personal information from a trained GNN. Among these techniques, certified unlearning stands out, as it provides a solid theoretical guarantee of the information removal effectiveness. Nevertheless, most of the existing certified unlearning methods for GNNs are only designed to handle node and edge unlearning requests. Meanwhile, these approaches are usually tailored for either a specific design of GNN or a specially designed training objective. These disadvantages significantly jeopardize their flexibility. In this paper, we propose a principled framework named IDEA to achieve flexible and certified unlearning for GNNs. Specifically, we first instantiate four types of unlearning requests on graphs, and then we propose an approximation approach to flexibly handle these unlearning requests over diverse GNNs. We further provide theoretical guarantee of the effectiveness for the proposed approach as a certification. Different from existing alternatives, IDEA is not designed for any specific GNNs or optimization objectives to perform certified unlearning, and thus can be easily generalized. Extensive experiments on real-world datasets demonstrate the superiority of IDEA in multiple key perspectives.