analiza aiqbench
GraphToxin exposes a critical vulnerability in graph unlearning mechanisms, demonstrating that residual traces in Graph Neural Networks can be reconstructed to recover deleted data and sensitive neighbor information. This research underscores the insufficiency of current membership inference verification standards for ensuring true "right to be forgotten" compliance in privacy-sensitive applications. The findings necessitate robust worst-case analysis and new defense strategies to prevent full graph reconstruction attacks in multi-party AI systems.
GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning
arXiv:2511.10936v3 Announce Type: replace-cross Abstract: 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.
Abstract: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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR)
arXiv:2511.10936 [cs.LG]
(or arXiv:2511.10936v3 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2511.10936 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 336 cuvinte
Subiecte conexe
Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction
arXiv · 1 sept. 2026
Spatial Entropy based Partitioning for Spatiotemporal Graph Unlearning
arXiv · 1 sept. 2026
No single pane of glass: Anatomy of an Azure permission takeover
Sysdig Blog · 14 iul. 2026
How do neural networks regress cubic polynomials? Apparently, they use a trick invented in Milan 500 years ago
LessWrong · 22 iul. 2026