# Towards Effective and General Graph Unlearning via Mutual Evolution

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

## Key facts

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

## Placed in

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

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

- [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)
- [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)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [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)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (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)
- [Graph Neural Networks in Network Neuroscience](https://mlsanity.com/paper/2106.03535/) (2021)
- [Line Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2010.10046/) (2020)
- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Graph Neural Networks: Taxonomy, Advances and Trends](https://mlsanity.com/paper/2012.08752/) (2020)
- [Distance-Weighted Graph Neural Networks on FPGAs for Real-Time Particle Reconstruction in High Energy Physics](https://mlsanity.com/paper/2008.03601/) (2020)
- [Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection](https://mlsanity.com/paper/2212.12488/) (2022)
- [Unravelling the Performance of Physics-informed Graph Neural Networks for Dynamical Systems](https://mlsanity.com/paper/2211.05520/) (2022)
- [Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projection](https://mlsanity.com/paper/2302.08990/) (2023)

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

- [Machine Unlearning: A Comprehensive Survey](https://mlsanity.com/paper/2405.07406/) (2024)
- [On Effects of Steering Latent Representation for Large Language Model Unlearning](https://mlsanity.com/paper/2408.06223/) (2024)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning](https://mlsanity.com/paper/2409.16684/) (2024)
- [OpenGU: A Comprehensive Benchmark for Graph Unlearning](https://mlsanity.com/paper/2501.02728/) (2025)
- [A Comprehensive Data-centric Overview of Federated Graph Learning](https://mlsanity.com/paper/2507.16541/) (2025)
- [Forget Vectors at Play: Universal Input Perturbations Driving Machine Unlearning in Image Classification](https://mlsanity.com/paper/2412.16780/) (2024)
- [Graph Memory Learning: Imitating Lifelong Remembering and Forgetting of Brain Networks](https://mlsanity.com/paper/2407.19183/) (2024)
- [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)
- [Enabling Group Fairness in Graph Unlearning via Bi-level Debiasing](https://mlsanity.com/paper/2505.09702/) (2025)
- [Graph Unlearning Meets Influence-aware Negative Preference Optimization](https://mlsanity.com/paper/2510.19479/) (2025)
- [A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2412.00789/) (2024)
- [Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach](https://mlsanity.com/paper/2501.11823/) (2025)
- [Adaptive Graph Unlearning](https://mlsanity.com/paper/2505.12614/) (2025)
- [Re-understanding Graph Unlearning through Memorization](https://mlsanity.com/paper/2601.14694/) (2026)
- [Node-level Contrastive Unlearning on Graph Neural Networks](https://mlsanity.com/paper/2503.02959/) (2025)
- [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)
- [TCGU: Data-centric Graph Unlearning based on Transferable Condensation](https://mlsanity.com/paper/2410.06480/) (2024)
- [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)
- [Federated Graph Unlearning](https://mlsanity.com/paper/2508.02485/) (2025)
- [Learning to Fast Unrank in Collaborative Filtering Recommendation](https://mlsanity.com/paper/2511.06803/) (2025)
- [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)
- [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)

With the rapid advancement of AI applications, the growing needs for data privacy and model robustness have highlighted the importance of machine unlearning, especially in thriving graph-based scenarios. However, most existing graph unlearning strategies primarily rely on well-designed architectures or manual process, rendering them less user-friendly and posing challenges in terms of deployment efficiency. Furthermore, striking a balance between unlearning performance and framework generalization is also a pivotal concern. To address the above issues, we propose underlineMutual underlineEvolution underlineGraph underlineUnlearning (MEGU), a new mutual evolution paradigm that simultaneously evolves the predictive and unlearning capacities of graph unlearning. By incorporating aforementioned two components, MEGU ensures complementary optimization in a unified training framework that aligns with the prediction and unlearning requirements. Extensive experiments on 9 graph benchmark datasets demonstrate the superior performance of MEGU in addressing unlearning requirements at the feature, node, and edge levels. Specifically, MEGU achieves average performance improvements of 2.7%, 2.5%, and 3.2% across these three levels of unlearning tasks when compared to state-of-the-art baselines. Furthermore, MEGU exhibits satisfactory training efficiency, reducing time and space overhead by an average of 159.8x and 9.6x, respectively, in comparison to retraining GNN from scratch.