# GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 49 of its 64 references that are in the map.
- First posted on arXiv 14 Nov 2025.

## Placed in

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

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

- [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)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Model Cards for Model Reporting](https://mlsanity.com/paper/1810.03993/) (2018)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [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)
- [Inverting Gradients -- How easy is it to break privacy in federated learning?](https://mlsanity.com/paper/2003.14053/) (2020)
- [See through Gradients: Image Batch Recovery via GradInversion](https://mlsanity.com/paper/2104.07586/) (2021)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [When Machine Unlearning Jeopardizes Privacy](https://mlsanity.com/paper/2005.02205/) (2020)
- [Fishr: Invariant Gradient Variances for Out-of-Distribution Generalization](https://mlsanity.com/paper/2109.02934/) (2021)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach](https://mlsanity.com/paper/1806.01316/) (2018)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [Membership Inference Attack on Graph Neural Networks](https://mlsanity.com/paper/2101.06570/) (2021)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [GraKeL: A Graph Kernel Library in Python](https://mlsanity.com/paper/1806.02193/) (2018)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [Learn What You Want to Unlearn: Unlearning Inversion Attacks against Machine Unlearning](https://mlsanity.com/paper/2404.03233/) (2024)
- [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)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [A Survey on Gradient Inversion: Attacks, Defenses and Future Directions](https://mlsanity.com/paper/2206.07284/) (2022)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Towards Effective and General Graph Unlearning via Mutual Evolution](https://mlsanity.com/paper/2401.11760/) (2024)
- [Reconstructing Training Data from Model Gradient, Provably](https://mlsanity.com/paper/2212.03714/) (2022)

## Abstract (arXiv)

Graph unlearning (GU) has emerged as a promising solution to comply with "the right to be forgotten" regulations by enabling the removal of sensitive information upon request. However, this solution is not foolproof. The involvement of multiple parties creates new attack surfaces, and residual traces of deleted data can persist within the unlearned graph neural networks (GNNs). These vulnerabilities can be exploited by attackers to recover the supposedly erased samples, undermining the intended functionality of GU. In this work, we propose GraphToxin, the first full graph reconstruction attack against GU. We show that GraphToxin can recover not only a deleted individual's information and personal links but also sensitive content of their neighbors, thereby posing substantially more detrimental threats than prior membership inference attacks (MIAs). Specifically, we introduce a novel curvature matching module to provide fine-grained guidance for full unlearned graph recovery. We further extend GraphToxin to multiple-node removal under both white-box and black-box settings, showcasing its practical feasibility and potential to cause considerable harm. We highlight the necessity of worst-case analysis and propose a systematic evaluation framework to assess attack performance under both random and worst-case node removal scenarios. Our extensive experiments demonstrate the effectiveness and flexibility of GraphToxin. Notably, current defense mechanisms are largely ineffective against this attack. Additionally, our findings reveal that existing GU verification standards based on MIAs can be misleading: they achieve membership-level protection, while the full unlearned graph remains recoverable through GraphToxin.