mlsanityData to 7 Oct 2026

Certified Graph Unlearning

arXiv 2206.09140 ↗First posted 18 Jun 2022cs.LGcited by 46

On the map: LLM safety and security → Graph unlearning

Abstract (arXiv)

Graph-structured data is ubiquitous in practice and often processed using graph neural networks (GNNs). With the adoption of recent laws ensuring the ``right to be forgotten'', the problem of graph data removal has become of significant importance. To address the problem, we introduce the first known framework for certified graph unlearning of GNNs. In contrast to standard machine unlearning, new analytical and heuristic unlearning challenges arise when dealing with complex graph data. First, three different types of unlearning requests need to be considered, including node feature, edge and node unlearning. Second, to establish provable performance guarantees, one needs to address challenges associated with feature mixing during propagation. The underlying analysis is illustrated on the example of simple graph convolutions (SGC) and their generalized PageRank (GPR) extensions, thereby laying the theoretical foundation for certified unlearning of GNNs. Our empirical studies on six benchmark datasets demonstrate excellent performance-complexity trade-offs when compared to complete retraining methods and approaches that do not leverage graph information. For example, when unlearning 20% of the nodes on the Cora dataset, our approach suffers only a 0.1% loss in test accuracy while offering a 4-fold speed-up compared to complete retraining. Our scheme also outperforms unlearning methods that do not leverage graph information with a 12% increase in test accuracy for a comparable time complexity.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). Placed in Graph unlearning, one of 12 directions in LLM safety and security. Builds on 34 of its 44 references that are in the map. First posted on arXiv 18 Jun 2022.

Builds on

34 of 44 references.

Closest ancestors · 1

Same direction, newest first

  1. 2021Graph Unlearning27 Mar

Other references · 33

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  5. 2019Simplifying Graph Convolutional Networkscited by 1,470
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  7. 2019Machine Unlearningcited by 1,020
  8. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  9. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  10. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  11. 2015Image-based Recommendations on Styles and Substitutescited by 702
  12. 2019Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networkscited by 599
21 more
  1. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  2. 2020VectorNet: Encoding HD Maps and Agent Dynamics from Vectorized Representationcited by 528
  3. 2019Certified Data Removal from Machine Learning Modelscited by 512
  4. 2019Making AI Forget You: Data Deletion in Machine Learningcited by 447
  5. 2021Remember What You Want to Forget: Algorithms for Machine Unlearningcited by 360
  6. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  7. 2015YFCC100M: The New Data in Multimedia Researchcited by 234
  8. 2021Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Predictioncited by 137
  9. 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
  10. 2022Graph Attention Multi-Layer Perceptroncited by 82
  11. 2021New Benchmarks for Learning on Non-Homophilous Graphscited by 81
  12. 2021LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysiscited by 65
  13. 2021Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced trainingcited by 54
  14. 2022GAP: Differentially Private Graph Neural Networks with Aggregation Perturbationcited by 46
  15. 2021Node-Level Differentially Private Graph Neural Networkscited by 43
  16. 2019Optimizing Generalized PageRank Methods for Seed-Expansion Community Detectioncited by 35
  17. 2019Stability of Graph Scattering Transformscited by 34
  18. 2021Releasing Graph Neural Networks with Differential Privacy Guaranteescited by 32
  19. 2020Spatio-Temporal Graph Scattering Transformcited by 19
  20. 2020Residual Correlation in Graph Neural Network Regressioncited by 11
  21. 2020CopulaGNN: Towards Integrating Representational and Correlational Roles of Graphs in Graph Neural Networkscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 13; 2024: 14; 2025: 13; 2026: 3.

46 papers.

Sort:

By area:

  1. 2023SalUn: Empowering Machine Unlearning via Gradient-based Weight Saliency in Both Image Classification and Generationcited by 376
  2. 2022A Survey of Machine Unlearningcited by 298
  3. 2023Model Sparsity Can Simplify Machine Unlearningcited by 206
  4. 2023To Generate or Not? Safety-Driven Unlearned Diffusion Models Are Still Easy To Generate Unsafe Images ... For Nowcited by 204
  5. 2024Simplicity Prevails: Rethinking Negative Preference Optimization for LLM Unlearningcited by 160
  6. 2023GIF: A General Graph Unlearning Strategy via Influence Functioncited by 59
  7. 2023Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomycited by 44
  8. 2024Challenging Forgets: Unveiling the Worst-Case Forget Sets in Machine Unlearningcited by 44
  9. 2023GNNDelete: A General Strategy for Unlearning in Graph Neural Networkscited by 43
  10. 2024Machine Unlearning: A Comprehensive Surveycited by 33
  11. 2022Unlearning Graph Classifiers with Limited Data Resourcescited by 31
  12. 2023SAFE: Machine Unlearning With Shard Graphscited by 28
34 more
  1. 2024WAGLE: Strategic Weight Attribution for Effective and Modular Unlearning in Large Language Modelscited by 25
  2. 2022Machine Unlearning of Federated Clusterscited by 21
  3. 2024A Probabilistic Perspective on Unlearning and Alignment for Large Language Modelscited by 21
  4. 2023Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projectioncited by 20
  5. 2023MultiDelete for Multimodal Machine Unlearningcited by 20
  6. 2024Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functionscited by 17
  7. 2024Targeted Unlearning with Single Layer Unlearning Gradientcited by 16
  8. 2023Distill to Delete: Unlearning in Graph Networks with Knowledge Distillationcited by 13
  9. 2024Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barriercited by 13
  10. 2023Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protectioncited by 12
  11. 2023A Survey of Graph Unlearningcited by 12
  12. 2025Robust Machine Unlearning for Quantized Neural Networks via Adaptive Gradient Reweighting with Similar Labelscited by 12
  13. 2023GraphGuard: Detecting and Counteracting Training Data Misuse in Graph Neural Networkscited by 8
  14. 2024Label Smoothing Improves Machine Unlearningcited by 8
  15. 2025OpenGU: A Comprehensive Benchmark for Graph Unlearningcited by 8
  16. 2025Model Collapse Is Not a Bug but a Feature in Machine Unlearning for LLMscited by 7
  17. 2025A Comprehensive Data-centric Overview of Federated Graph Learningcited by 7
  18. 2025Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgerycited by 5
  19. 2024Graph Memory Learning: Imitating Lifelong Remembering and Forgetting of Brain Networkscited by 4
  20. 2025Unlearning Inversion Attacks for Graph Neural Networkscited by 4
  21. 2024Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approachcited by 3
  22. 2025Human Motion Unlearningcited by 3
  23. 2026Forget by Uncertainty: Orthogonal Entropy Unlearning for Quantized Neural Networkscited by 2
  24. 2026Mitigating Privacy Risk via Forget Set-Free Unlearningcited by 2
  25. 2024GraphMU: Repairing Robustness of Graph Neural Networks via Machine Unlearningcited by 1
  26. 2024Accurate Forgetting for All-in-One Image Restoration Modelcited by 1
  27. 2025Face Identity Unlearning for Retrieval via Embedding Dispersioncited by 1
  28. 2024Graph Transductive Defense: a Two-Stage Defense for Graph Membership Inference Attackscited by 0
  29. 2025Unlearning Algorithmic Biases over Graphscited by 0
  30. 2025Graph Unlearning via Embedding Reconstruction -- A Range-Null Space Decomposition Approachcited by 0
  31. 2025Beyond Uniform Deletion: A Data Value-Weighted Framework for Certified Machine Unlearningcited by 0
  32. 2025GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearningcited by 0
  33. 2025Descend or Rewind? Stochastic Gradient Descent Unlearningcited by 0
  34. 2026A Robust Certified Machine Unlearning Method Under Distribution Shiftcited by 0