mlsanityData to 7 Oct 2026

GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning

arXiv 2511.10936 ↗First posted 14 Nov 2025cs.LG cs.AI cs.CRcited by 0

On the map: LLM safety and security → Graph unlearning

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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

49 of 64 references.

Closest ancestors · 7

Same direction, newest first

  1. 2024Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning25 Sep
  2. 2024Towards Effective and General Graph Unlearning via Mutual Evolution22 Jan
  3. 2023A Survey of Graph Unlearning23 Aug
  4. 2023Inductive Graph Unlearning6 Apr
  5. 2023GIF: A General Graph Unlearning Strategy via Influence Function6 Apr
  6. 2022Certified Graph Unlearning18 Jun
  7. 2021Graph Unlearning27 Mar

Other references · 42

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2019Simplifying Graph Convolutional Networkscited by 1,470
  4. 2018Model Cards for Model Reportingcited by 1,068
  5. 2019Deep Leakage from Gradientscited by 1,004
  6. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  7. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  8. 2020Inverting Gradients -- How easy is it to break privacy in federated learning?cited by 707
  9. 2021See through Gradients: Image Batch Recovery via GradInversioncited by 320
  10. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
  11. 2021Fishr: Invariant Gradient Variances for Out-of-Distribution Generalizationcited by 186
  12. 2020When Machine Unlearning Jeopardizes Privacycited by 181
30 more
  1. 2016How to learn a graph from smooth signalscited by 146
  2. 2020Stealing Links from Graph Neural Networkscited by 114
  3. 2018Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approachcited by 89
  4. 2020Quantifying Privacy Leakage in Graph Embeddingcited by 82
  5. 2021Membership Inference Attack on Graph Neural Networkscited by 81
  6. 2021LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysiscited by 65
  7. 2018GraKeL: A Graph Kernel Library in Pythoncited by 54
  8. 2021GraphMI: Extracting Private Graph Data from Graph Neural Networkscited by 50
  9. 2022GAP: Differentially Private Graph Neural Networks with Aggregation Perturbationcited by 46
  10. 2021Node-Level Differentially Private Graph Neural Networkscited by 43
  11. 2024Learn What You Want to Unlearn: Unlearning Inversion Attacks against Machine Unlearningcited by 43
  12. 2022A Survey on Gradient Inversion: Attacks, Defenses and Future Directionscited by 39
  13. 2022Reconstructing Training Data from Model Gradient, Provablycited by 27
  14. 2022Model Inversion Attacks against Graph Neural Networkscited by 26
  15. 2022NAS-Bench-Graph: Benchmarking Graph Neural Architecture Searchcited by 25
  16. 2024Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerablecited by 24
  17. 2022Private Graph Extraction via Feature Explanationscited by 16
  18. 2022Characterizing the Influence of Graph Elementscited by 16
  19. 2023Preserving Node-level Privacy in Graph Neural Networkscited by 11
  20. 2022DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacycited by 10
  21. 2023Does Black-box Attribute Inference Attacks on Graph Neural Networks Constitute Privacy Risk?cited by 7
  22. 2019The General Data Protection Regulation: Requirements, Architectures, and Constraintscited by 5
  23. 2025GRAIN: Exact Graph Reconstruction from Gradientscited by 5
  24. 2025Boosting Gradient Leakage Attacks: Data Reconstruction in Realistic FL Settingscited by 5
  25. 2024Gradient Inversion Attack on Graph Neural Networkscited by 4
  26. 2025Unlearning Inversion Attacks for Graph Neural Networkscited by 4
  27. 2024Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approachcited by 3
  28. 2024Fast Inference of Removal-Based Node Influencecited by 2
  29. 2024AFGI: Towards Accurate and Fast-convergent Gradient Inversion Attack in Federated Learningcited by 2
  30. 2024LinkThief: Combining Generalized Structure Knowledge with Node Similarity for Link Stealing Attack against GNNcited by 2

Built on by

Not cited yet.