CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion
Chenhan Zhang, Ali Braytee, Madhushi Bandara, Xin Hao, Paul J. Kennedy, Massimo Piccardi, Raymond Owen
cs.LG · cs.AI
Quick verdict
Curriculum + distribution-level NPO fight catastrophic graph unlearning up to 50% deletion; results convincing, but datasets small and curriculum gain modest.
Summary
This NeurIPS submission studies graph unlearning under 'mass deletion' (removal of up to 50% of training nodes), where existing approximate methods lose most utility — a failure the authors call catastrophic unlearning. CUNO attacks it with two components: curriculum scheduling, which orders forget nodes by an estimated unlearning-difficulty score (default: per-sample task-loss gradient norm) and removes them in K=8 overlapping hard-to-easy stages; and a distribution-level negative preference optimization (NPO) objective computed over full temperature-scaled predictive distributions, paired with a retain loss and a frozen reference model. Theory in Appendix E frames curriculum unlearning as a dispersion-drift trade-off and proves NPO's gradient is self-dampening where gradient ascent's is not. Experiments on Cora, CiteSeer, and PubMed with GCN/GAT/GraphSAGE across seven deletion rates and five seeds show CUNO retaining 74% of original utility at 20% deletion versus 26-53% for GA, GIF, INPO, and ETR, and about 55% at 50%, with MIA-based forgetting calibrated to Retrain. Ablations attribute collapse prevention primarily to NPO (utility drop 0.22 vs 0.18 at 20%); the curriculum adds a smaller, consistent gain. Limitations: only three small citation graphs despite the mass-deletion motivation; no significance testing for small ablation margins; one arithmetic inconsistency in Section 4.2 (76% vs ~67% gap closure); directional alignment verified for only 2 of 11 difficulty metrics.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 2
● low 3
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Existing approximate graph unlearning methods suffer catastrophic utility collapse beyond ~5% deletion, a regime most prior work never evaluates (Figure 1).
- Ordering the forget set by estimated difficulty into overlapping stages and applying a distribution-level NPO objective preserves utility: 74% of original at 20% deletion versus 26-53% for GA/GIF/INPO/ETR, and more than half at 50% deletion.
- Curriculum unlearning is theoretically a dispersion-drift trade-off (Theorem E.1, Propositions E.3-E.4), and NPO's self-dampening gradient (Proposition E.5) removes the collapse mechanism of gradient ascent under mass deletion.
- NPO is the primary driver of collapse prevention; curriculum scheduling contributes a smaller but consistent additional gain (Section 4.4 ablations).
Strengths
Well-motivated, quantified problem framing
Figure 1 (right) documents that most prior methods (INPO, UTU, GNNDelete at 0.1-5%; FedLU, ETR at 5%) never evaluate beyond 5% deletion; Section 2 defines catastrophic unlearning operationally as growth of the gap between unlearning utility drop and retraining's inherent loss, and the 1-50% regime is a genuine gap.
Dual-axis forgetting evaluation with honest metric critique
Section 4.3 explicitly flags FE-Standard as homophily-confounded (Retrain itself only 0.11-0.47), anchors calibrated FE-MIA at Retrain, and reads GA's high FE (0.92 at MU 0.20) as utility-driven inflation and INPO's raw 0.69 as under-erasure — a level of metric self-critique rare in this literature.
Theory that predicts its own empirical patterns
Systematic design-space study
Complete, seeded experimental grid
Weaknesses
Experimental scale mismatches the mass-deletion motivation
The curriculum's incremental value is thin and statistically untested
Arithmetic inconsistency in Section 4.2
Theory-practice gaps
Baseline coverage and cost reporting
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion — Preliminary Review
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is catastrophic unlearning in graph neural networks?
It is the sharp drop in a GNN's accuracy on retained data when approximate unlearning removes a large fraction of training nodes at once — far larger than the loss from retraining from scratch on the remaining data. The CUNO paper shows that beyond about 5% deletion, existing methods' utility collapses: at 20% deletion they retain only 26-53% of original accuracy, versus 74% for CUNO.
How does CUNO unlearn nodes from a graph model?
CUNO scores every node slated for deletion by estimated unlearning difficulty (default: the norm of its task-loss gradient), splits them into eight difficulty-ordered overlapping stages processed from hardest to easiest, and at each stage minimizes a distribution-level negative preference optimization (NPO) loss over full predictive distributions plus a supervised loss on retained nodes, using a frozen copy of the original model as the reference.
Does CUNO actually delete nodes or edges from the graph?
No. CUNO performs label-level, parameter-level unlearning: the graph's topology and features stay intact, and only the model parameters change so the forget set's influence is removed. Physically removing nodes or edges is explicitly out of scope (Appendix H).
Is CUNO's code and data available?
Yes. The paper links an anonymized code repository (anonymous.4open.science/r/cuno-D4FF) and uses standard public benchmarks (Cora, CiteSeer, PubMed); hyperparameters, seeds, and hardware (two NVIDIA A40 GPUs) are listed in Appendix F.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Sampled excerpt: three [...sampling gap...] regions skip the tail of Section 4 / Section 4.5 narrative, Appendix C (metric formulas), the head of Algorithm 1, and Appendix G.1-G.2; judgments on those parts rest on visible cross-references and figure captions only.
- Appendix F.3 is cut off mid-sentence after the MU definition; the precise FE-MIA attack construction is only partially visible.
- Metadata gives the seventh author as 'Raymond Owen' while the extracted byline reads 'Raymond O'Kennedy'; this is verified only as a text discrepancy.
- Numbers quoted from figures (e.g., Figure 13b's 10^-3-scale deviations, win counts in Figures 14-15) come from extracted figure text and could not be checked against rendered plots.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.