CUNO: Curriculum-Based Graph Unlearning to Mitigate Utility Collapse at High Deletion Ratios

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. A shared limitation of these methods is that they apply the same forgetting operation to the entire forget set. This is particularly damaging in graph learning, where structural dependencies cause different nodes to play vastly different roles in the learned model. 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 substantially narrows the utility gap to the retraining reference across all deletion rates evaluated: at 20% deletion it retains 74% of the original model's utility compared to 26-53% for the compared approximate baselines, and preserves more than half the original utility even at 50% deletion, while staying closest to Retrain's membership-inference footprint among the compared methods. Our code is publicly available at https://anonymous.4open.science/r/cuno-D4FF.