# CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in LLM preference optimization methods, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 43 of its 58 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Placed in

- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)
- LLM safety and security / [Graph unlearning](https://mlsanity.com/safety/graph-unlearning/)

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

- [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)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Negative Preference Optimization: From Catastrophic Collapse to Effective Unlearning](https://mlsanity.com/paper/2404.05868/) (2024)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Teacher-Student Curriculum Learning](https://mlsanity.com/paper/1707.00183/) (2017)
- [Competence-based Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1903.09848/) (2019)
- [Simplicity Prevails: Rethinking Negative Preference Optimization for LLM Unlearning](https://mlsanity.com/paper/2410.07163/) (2024)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [What makes unlearning hard and what to do about it](https://mlsanity.com/paper/2406.01257/) (2024)
- [Calibration in Deep Learning: A Survey of the State-of-the-Art](https://mlsanity.com/paper/2308.01222/) (2023)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [A Closer Look at Machine Unlearning for Large Language Models](https://mlsanity.com/paper/2410.08109/) (2024)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Heterogeneous Federated Knowledge Graph Embedding Learning and Unlearning](https://mlsanity.com/paper/2302.02069/) (2023)
- [Machine Unlearning: A Comprehensive Survey](https://mlsanity.com/paper/2405.07406/) (2024)
- [Machine Unlearning: Taxonomy, Metrics, Applications, Challenges, and Prospects](https://mlsanity.com/paper/2403.08254/) (2024)
- [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)
- [CLNode: Curriculum Learning for Node Classification](https://mlsanity.com/paper/2206.07258/) (2022)
- [IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2407.19398/) (2024)
- [Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projection](https://mlsanity.com/paper/2302.08990/) (2023)
- [Learning Like Humans: Advancing LLM Reasoning Capabilities via Adaptive Difficulty Curriculum Learning and Expert-Guided Self-Reformulation](https://mlsanity.com/paper/2505.08364/) (2025)
- [MentorGNN: Deriving Curriculum for Pre-Training GNNs](https://mlsanity.com/paper/2208.09905/) (2022)
- [Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy](https://mlsanity.com/paper/2410.09591/) (2024)
- [Adversarial Machine Unlearning](https://mlsanity.com/paper/2406.07687/) (2024)

## Abstract (arXiv)

Graph unlearning removes the influence of designated training data from a trained graph model without retraining from scratch. However, existing methods suffer a sharp drop in model utility under large deletion ratios (mass deletion), a phenomenon we refer to as catastrophic unlearning. We find that a key cause is the uniform treatment of all deleted samples, which is particularly damaging in graph learning: structural dependencies cause different nodes to play vastly different roles in the learned model, yet existing methods apply the same forgetting operation to the entire forget set. Based on this insight, we propose CUNO, a curriculum-based graph unlearning framework that removes the forget set progressively, ordering samples by their estimated unlearning difficulty across multiple stages. CUNO further employs a distribution-level negative preference optimization (NPO) objective at each curriculum stage that steers the model away from its original behavior on the current forget subset while preserving retained performance. Our theoretical analysis shows that the curriculum design is most beneficial when the forget set spans a wide range of unlearning difficulty, a condition naturally satisfied under mass deletion. Comprehensive experiments confirm that CUNO consistently mitigates catastrophic unlearning: at 20% deletion, it retains 74% of the original utility compared to 26-53% for existing methods, and maintains more than half the original utility even at 50% deletion. Our code is publicly available at https://anonymous.4open.science/r/cuno-D4FF.