# Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning

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

## Key facts

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

## Placed in

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

## Builds on (most cited first, 14 of 14)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [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)
- [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)
- [Fast Machine Unlearning Without Retraining Through Selective Synaptic Dampening](https://mlsanity.com/paper/2308.07707/) (2023)
- [Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations](https://mlsanity.com/paper/2003.02960/) (2020)
- [Towards Effective and General Graph Unlearning via Mutual Evolution](https://mlsanity.com/paper/2401.11760/) (2024)
- [Characterizing the Influence of Graph Elements](https://mlsanity.com/paper/2210.07441/) (2022)
- [Generalized Data Weighting via Class-level Gradient Manipulation](https://mlsanity.com/paper/2111.00056/) (2021)

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

- [Unlearning Inversion Attacks for Graph Neural Networks](https://mlsanity.com/paper/2506.00808/) (2025)
- [Adaptive Graph Unlearning](https://mlsanity.com/paper/2505.12614/) (2025)
- [Re-understanding Graph Unlearning through Memorization](https://mlsanity.com/paper/2601.14694/) (2026)
- [Neural Corrective Machine Unranking](https://mlsanity.com/paper/2411.08562/) (2024)
- [CUFG: Curriculum Unlearning Guided by the Forgetting Gradient](https://mlsanity.com/paper/2509.14633/) (2025)
- [Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2603.18570/) (2026)
- [GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning](https://mlsanity.com/paper/2511.10936/) (2025)
- [FairGU: Fairness-aware Graph Unlearning in Social Networks](https://mlsanity.com/paper/2601.09469/) (2026)
- [The EpisTwin: A Knowledge Graph-Grounded Neuro-Symbolic Architecture for Personal AI](https://mlsanity.com/paper/2603.06290/) (2026)
- [Stable Multimodal Graph Unlearning via Feature-Dimension Aware Quantile Selection](https://mlsanity.com/paper/2605.03303/) (2026)
- [FedUP: One-Shot Federated Unlearning via Centroid-Guided Plug-in Filters](https://mlsanity.com/paper/2606.24113/) (2026)
- [CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion](https://mlsanity.com/paper/2609.08244/) (2026)

## Abstract (arXiv)

Graph unlearning, which aims to eliminate the influence of specific nodes, edges, or attributes from a trained Graph Neural Network (GNN), is essential in applications where privacy, bias, or data obsolescence is a concern. However, existing graph unlearning techniques often necessitate additional training on the remaining data, leading to significant computational costs, particularly with large-scale graphs. To address these challenges, we propose a two-stage training-free approach, Erase then Rectify (ETR), designed for efficient and scalable graph unlearning while preserving the model utility. Specifically, we first build a theoretical foundation showing that masking parameters critical for unlearned samples enables effective unlearning. Building on this insight, the Erase stage strategically edits model parameters to eliminate the impact of unlearned samples and their propagated influence on intercorrelated nodes. To further ensure the GNN's utility, the Rectify stage devises a gradient approximation method to estimate the model's gradient on the remaining dataset, which is then used to enhance model performance. Overall, ETR achieves graph unlearning without additional training or full training data access, significantly reducing computational overhead and preserving data privacy. Extensive experiments on seven public datasets demonstrate the consistent superiority of ETR in model utility, unlearning efficiency, and unlearning effectiveness, establishing it as a promising solution for real-world graph unlearning challenges.