acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph unlearning, machine unlearning, curriculum learning, negative preference optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_vujKOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies graph unlearning under large deletion ratios ("mass deletion"), where existing methods exhibit severe utility degradation. The authors propose CUNO, a curriculum-based graph unlearning framework that progressively partitions the forget set according to estimated unlearning difficulty and combines staged forgetting with a distribution-level NPO objective. Theoretical analysis characterizes a dispersion-drift tradeoff induced by curriculum partitioning and the self-damping behavior of the NPO objective, while experiments across three datasets, three GNN architectures, and deletion rates up to 50% demonstrate improved utility retention and closer behavior to the retraining baseline.

Critical strengths

The paper focuses on a practically important but underexplored regime of graph unlearning: high deletion ratios. The empirical evidence convincingly demonstrates that many existing methods suffer utility collapse under mass deletion, making the problem itself well motivated.

The proposed method is conceptually simple and empirically strong. Across multiple deletion rates, datasets, and GNN architectures, CUNO consistently improves utility retention and often remains closest to the retraining reference.

Critical weaknesses

The paper’s main empirical claims are stronger than what is established theoretically. The theoretical analysis characterizes optimization properties of curriculum partitioning and NPO, including gradient dispersion reduction, stage drift control, and self-damping gradients. However, the theory does not directly analyze graph unlearning quality, utility preservation, or calibration to retraining. As a result, the connection between the proven optimization benefits and the observed improvements in utility retention remains largely empirical.

Questions for authors
  1. The theoretical analysis focuses on optimization quantities such as gradient dispersion and stage drift. Can the authors clarify how these quantities are connected to the downstream metrics used in the experiments (MU, ΔU, FE-MIA)? Is there empirical evidence that reductions in dispersion or drift correlate with improved unlearning quality across methods and datasets?

  2. Proposition E.4 relies on a directional-alignment assumption between the curriculum metric and per-sample gradients. How critical is this assumption in practice? Do the authors have empirical evidence that the proposed default metric (gradient norm) is sufficiently aligned with this assumption across datasets and deletion regimes?

6 comments

We thank the reviewer for the thoughtful feedback. For readability and to stay within the character limit per reply, we address the comments in separate replies below, starting with W1 and Q1.

W1, Q1 — Theory and downstream metrics

  • How the optimization analysis supports claims about utility preservation and calibration to Retrain.
  • Whether lower gradient dispersion or stage drift correlates with better MU, ΔU and FE-MIA across methods and datasets.

Response

We thank the reviewer for raising the questions. Our main finding is that NPO and staging each reduce the measured distance to Retrain and utility loss. The theory gives a conditional basis for the optimization design; the evidence for downstream performance is empirical. We have made this distinction explicit in App. E.

Under the Lipschitz utility assumption in App. E,

ΔU≤LU∥θunl−θrtr∥+R(γ),\Delta U \le L_U\|\theta^{\mathrm{unl}}-\theta^{\mathrm{rtr}}\|+R(\gamma),

where R(γ)R(\gamma) is Retrain's measured utility drop. We would like to clarify that we use this as a conditional link, not a calibrated numerical bound. Theorem E.1 analyzes convergence to the final stage optimum, and Prop. E.3 relates changes in stage optima to overlap. These results motivate the scheduling design.

Empirical link to utility. We measured distances across nine dataset–GNN pairs, five seeds and five deletion rates (5%, 10%, 20%, 40% and 50%). Output distance is defined as the mean total variation between predictions on test nodes. The table reports the mean parameter distance, output distance and utility drop (ΔU\Delta U) across settings.

VariantParameter distanceOutput distanceΔU\Delta U
GA, one-shot10020.750.53
GA, staged6880.690.47
NPO, one-shot3480.420.24
NPO, staged (CUNO)3390.410.22

Under either schedule, replacing GA with NPO reduces both mean parameter distance and ΔU\Delta U by more than half. Staging improves both further under either objective. This supports combining staging with NPO. Prop. E.5 separately characterizes its class-wise gradient weighting and bounded logit gradient.

With four variants per setting, the mean Spearman correlation between parameter distance and ΔU\Delta U is 0.67. Across seven methods (the four variants above plus GIF, INPO and ETR), the mean correlations with ΔU\Delta U are 0.30 for parameter distance and 0.80 for output distance. Output distance measures behavioural closeness on the same test nodes used for utility. Calibration is evaluated separately using per-run transformed FE-MIA across deletion rates; closeness in utility alone does not establish calibration.

Dispersion and drift diagnostics. We compare Hard-to-Easy (H2E), Easy-to-Hard (E2H), random ordering and shuffled κ\kappa within each dataset–GNN–seed–deletion-rate setting. This diagnostic compares schedules, rather than all seven methods. For the initial diagnostic, we compute per-node task-loss (cross-entropy) gradients in evaluation mode at the trained model θtr\theta_{\mathrm{tr}}. The dispersion ratio is the mean per-stage dispersion divided by that of the whole forget set. It is 0.61 for H2E versus 0.87 for random ordering, with H2E yielding lower dispersion in 81% of settings. Our default difficulty score is based on task-loss gradient norms. This diagnostic examines within-stage variation in task-loss gradients. We use total parameter movement between stage endpoints as a proxy for the theoretical drift between stage optima.

We then examine whether these two diagnostics are associated with final utility and forgetting scores. For each setting, we compute Spearman correlations across the four schedules and report their averages below.

DiagnosticMean within-setting Spearman with ΔU\Delta UWith transformed FE-MIA
Initial dispersion ratio−0.04+0.09
Stage-endpoint movement+0.02+0.09

While lower dispersion or stage movement does not consistently correspond to better final scores across the four schedules, these diagnostics help us understand how grouping affects the optimization process. The distance-to-Retrain analysis provides a separate empirical link to utility.

Revision. We have clarified the assumptions and scope of the theory in App. E and revised the abstract and corresponding claims in Sections 1 (Introduction), 3.1 (Curriculum Scheduling) and 3.2 (Distribution-Level NPO) accordingly. We have added empirical analyses in Apps. G.7–G.9 to examine gradient dispersion, stage movement and distance to Retrain in relation to downstream performance.

Q2 — Directional-alignment assumption

  • How critical the directional-alignment assumption in Proposition E.4 is to the theoretical results.
  • Whether the default gradient-norm score satisfies this assumption across datasets and deletion rates.

Response

We thank the reviewer for the question. A5 is needed for Prop. E.4, while Theorem E.1 and Props. E.3 and E.5 do not rely on it. Our diagnostics show positive rank alignment for the default score, but the uniform condition in A5 is more demanding.

At the trained model, we compute each forget node's task-loss gradient and choose the mean forget-gradient direction as uu. Across nine dataset–GNN pairs, five seeds and five deletion rates (5%, 10%, 20%, 40% and 50%), we measure the correlation between the score and its gradient projection onto uu, and the fraction of node pairs whose rankings agree.

ScoreMean rank correlationConcordant pairs
Random ranking (expected)0.0050%
Degree0.0652%
Gradient norm, as used0.3061%
Gradient norm, evaluation mode0.6075%

The default score has positive correlation in 83% of configurations. Mean correlation is 0.38 on Cora, 0.32 on CiteSeer and 0.22 on PubMed, and ranges from 0.37 at 5% deletion to 0.26 at 50%. Evaluation mode gives stronger alignment than the default implementation with dropout active; this row is a diagnostic, not a change to the evaluated method.

For the tested mean-gradient direction, the positive minimum-slope condition across all pairs holds in 1.8% of configurations. Thus, average rank alignment should be distinguished from the uniform requirement in A5. The lower initial dispersion observed in 81% of settings provides a separate empirical motivation for the grouping, rather than a test of whether A5 is necessary.

Revision. We have clarified the role of A5 and the conditional scope of Prop. E.4, and added alignment diagnostics in App. E.1. Section 3.1 and App. H have been updated accordingly.

Many thanks for the detailed rebuttal. My main concerns have been partially resolved:

  1. the theoretically motivated quantities show little consistent association with downstream performance.
  2. A5 condition required by Proposition E.4 holds in only 1.8% of the tested configurations, limiting its practical relevance. The rebuttal has improved my assessment, but these concerns remain. I would maintain my current rating, while viewing the paper as borderline between weak reject and weak accept.
Reviewer_jikzOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies label-level graph unlearning under high deletion ratios, where approximate unlearning can substantially degrade retained predictive utility. Under a fixed-graph setting, CUNO orders forget samples by estimated unlearning difficulty and processes them through overlapping curriculum stages. Each stage combines a distribution-level negative preference optimization objective with supervised learning on retained labels. The paper analyzes the interaction between within-stage gradient dispersion and stage-transition drift, and evaluates the method on three citation datasets and three GNN architectures, with deletion ratios up to 50%. Experiments report improved utility relative to the compared approximate unlearning methods, alongside retraining-calibrated membership-inference evaluation and component ablations.

Critical strengths

The paper provides a clearly formulated approach with consistent empirical benefits under high deletion ratios.

The formulation clearly separates curriculum scheduling from the stage-wise forgetting objective, making the method and its design choices straightforward to follow. Experiments across three datasets and three GNN architectures demonstrate improved utility preservation over the compared approximate unlearning baselines, including at high deletion ratios. The ablations also show that curriculum scheduling provides additional benefits beyond the NPO objective alone. These results support the practical value of the proposed combination for mitigating utility degradation in the evaluated label-level unlearning setting.

Critical weaknesses

W1. The methodological novelty requires more complete comparison with prior curriculum-based unlearning methods.

Two closely related works deserve explicit discussion. CUFG (Miao et al., 2025) introduces difficulty-based progressive unlearning to improve optimization stability and mitigate model collapse, including experiments with 50% random forgetting. CAU (Yang et al., 2025) schedules unlearning samples using gradient- and embedding-based difficulty measures while balancing forgetting and retention. Although these works address different application domains, they provide relevant precedents for CUNO’s central scheduling idea. Neither appears to be discussed in the submitted paper.

CUNO combines a distribution-level NPO objective, hard-to-easy scheduling, and overlapping stages. These are meaningful design choices, but their methodological distinction from existing curriculum-based unlearning frameworks needs sharper explanation. In particular, the paper should clarify what new scheduling principle is introduced and how its interaction with the forgetting objective advances beyond applying difficulty-based progressive unlearning to GNNs.

Comparisons against GA, GIF, INPO, and ETR establish benefits over the selected baselines, but do not directly establish the additional value over existing curriculum-based approaches. Matched comparisons using compatible adaptations of prior scheduling strategies, under the same label-level unlearning protocol, forgetting objective, and optimization budget, would make the novelty and empirical contribution more convincing.

Miao, J., Hu, L., Zhang, Q., Yuan, L. Z., & Naseem, U. (2025). CUFG: Curriculum unlearning guided by the forgetting gradient [Preprint]. arXiv. arXiv:2509.14633.

Yang, L., Ren, Z., Zhao, Z., Ren, P., Chen, Z., Li, X., Wang, S., Yin, D., & Xin, X. (2025). Curriculum approximate unlearning for session-based recommendation [Preprint]. arXiv. arXiv:2508.15263v1.

W2. The necessity of the graph-specific scheduling rationale is not sufficiently isolated.

The default difficulty measure is the per-sample task-loss gradient norm, which is broadly applicable beyond graphs. Although gradients computed through a GNN implicitly incorporate graph dependencies, it remains unclear whether this score captures the collateral effects of forgetting on retained neighbors beyond generic sample difficulty. The proposed topology-based and retain-coupling metrics are useful, but their comparison does not directly establish this relationship.

The scheduling experiments compare easy-to-hard, hard-to-easy, and no-curriculum optimization, but do not include a random-order staged baseline with matched stage count, overlap, and optimization budget. Consequently, the results do not fully distinguish the benefit of difficulty-aware ordering from the benefit of staged optimization itself. This control is particularly relevant to assessing the contribution of the proposed scheduler.

The experiments use uniformly sampled forget labels on three homophilous citation graphs. This setting does not directly isolate the structural mechanisms motivating the method, such as differences between forgetting hubs, peripheral nodes, and boundary nodes. Controlled comparisons across these structural roles, with matched deletion size and class composition, would strengthen the evidence that graph dependencies specifically justify the proposed scheduling choices.

Questions for authors

What evidence connects the difficulty scores to the impact of forgetting on retained neighbors? Do the existing analyses show that the preferred scheduling strategy changes with the structural roles of the forget nodes?

Does difficulty-aware ordering outperform random-order staged unlearning when the stage count, overlap, forgetting objective, and optimization budget are matched? Such evidence would help establish whether the gains depend on the proposed ordering.

5 comments

We thank the reviewer for the thoughtful feedback. For readability and to stay within the character limit per reply, we address the comments in separate replies below, starting with W1.

W1 — Comparison with CUFG and CAU

  • How CUNO differs from prior curriculum-based unlearning methods, particularly CUFG and CAU.
  • Matched comparisons with compatible prior scheduling strategies under the same protocol, objective and budget.

Response

We thank the reviewer for drawing our attention to these closely related works. We would like to clarify that CUFG studies image-classification unlearning, while CAU focuses on session-based recommendation. These concurrent works also study curriculum-based unlearning, whereas CUNO addresses label unlearning in GNNs. CUFG uses confidence-based, easy-to-hard scheduling with a gradient corrector. CAU uses gradient- or embedding-based difficulty with hard or soft sampling.

CUNO combines overlapping stages with a frozen-reference, distribution-level NPO objective for label unlearning in GNNs. Overlap supports gradual stage transitions, while NPO applies likelihood-ratio weights to individual class-gradient contributions. Each stage retains the full graph for message passing. This combination, rather than difficulty ordering alone, is our main contribution.

Matched adaptations. We adapted the prior schedules to our label-level NPO protocol with a 48-step budget. CUFG uses its disjoint confidence-based schedule. For CAU, we adapt its soft-sampling strategy, using progressive sampling with stage-wise score updates. These are schedule adaptations, not comparisons with the full original methods.

Entries average nine dataset–GNN pairs and deletion rates from 5% to 50% within each seed, then report mean ± std over five seeds.

ScheduleMUFETransformed FE-MIA
CUFG0.549 ±\pm 0.0130.677 ±\pm 0.0290.824 ±\pm 0.043
CAU0.547 ±\pm 0.0120.778 ±\pm 0.0250.865 ±\pm 0.031
CUNO0.539 ±\pm 0.0150.796 ±\pm 0.0260.866 ±\pm 0.028

Among the schedules reported here, CUNO achieves the highest mean FE (0.796) while maintaining comparable utility. Compared with the adapted CUFG schedule, CUNO improves FE by 0.119 and transformed FE-MIA by 0.042, with a 0.010 reduction in MU. Compared with the adapted CAU schedule, CUNO has higher mean FE (0.796 versus 0.778), nearly identical transformed FE-MIA (0.866 versus 0.865), and slightly lower MU (0.539 versus 0.547). These results highlight CUNO’s balance between forgetting and retained utility under the same NPO objective and update budget. The random-order control in our reply to Q2 further isolates the contribution of difficulty ordering.

Revision. We have added a discussion of CUFG and CAU as concurrent work in App. B.3 and clarified their differences from CUNO.

W2, Q1 — Graph structure and difficulty scores

  • Whether the difficulty scores capture the impact of forgetting on retained neighbours beyond generic sample difficulty.
  • Whether the preferred ordering changes for hub, peripheral and boundary forget nodes.

Response

We thank the reviewer for raising this question about the graph-specific rationale. We conducted a node-level probe and controlled structural-role experiments.

Does the score reflect damage to retained neighbours? We start from the trained model and apply 16 small task-loss gradient-ascent steps to one forget node, without a retain loss. This is a sensitivity probe, not a full CUNO run. We measure prediction KL changes on neighbours and the positive increase in retained-node loss. Across 165 configurations with at least eight forget nodes, the highest-ranked quarter accounts for:

RankingNeighbour damagePositive retained-loss increase
Random (expected)25%25%
Degree49%44%
Gradient norm (default)62%54%
Low prediction confidence85%72%

The gradient score identifies nodes associated with greater collateral damage, while low prediction confidence provides an even stronger signal. The gradient score also captures 62% of the positive neighbour-excess damage after subtracting the KL change outside the neighbourhood. Together, these results show that model-aware scores can help identify nodes associated with greater collateral effects. Further investigation could explore how gradient-based scores relate to graph-specific effects beyond general sample difficulty.

Does the preferred ordering change with structural role? We select hubs, peripheral nodes and boundary nodes within each class, matching deletion size and class composition. The results suggest that structural role alone does not clearly determine the preferred ordering in the settings tested. One possible explanation is that structural roles describe coarse topological properties, whereas gradient-based difficulty reflects the model’s sensitivity to individual nodes, including their features, prediction errors and neighbourhood dependencies. Nodes within the same structural role may therefore differ in difficulty, motivating a model-aware assessment of ordering rather than a fixed preference based on structural role.

Revision. We have added the retained-loss probe results to App. G.7 to provide empirical support for the default difficulty score.

W2, Q2 — Difficulty ordering versus random staging

  • Whether difficulty-aware ordering outperforms random-order staged unlearning.
  • Separating the effect of ordering from staging with matched stage count, overlap, objective and budget.

Response

We thank the reviewer for highlighting this important control. To test whether ordering adds value beyond staged optimization, we compare one-shot NPO with four staged schedules. The staged schedules use the same stage construction, overlap, objective and update budget; only the ranking changes.

We evaluate three datasets, three GNNs, five seeds and five deletion rates, using gradient norm as the difficulty score. The table reports ΔU\Delta U (lower is better): we average the nine dataset–GNN pairs within each seed, then report mean ±\pm std across seeds.

Scheduleγ=5%\gamma=5\%γ=10%\gamma=10\%γ=20%\gamma=20\%γ=40%\gamma=40\%γ=50%\gamma=50\%
One-shot NPO0.128 ±\pm 0.0150.153 ±\pm 0.0180.214 ±\pm 0.0280.309 ±\pm 0.0180.367 ±\pm 0.024
Staged NPO, random ordering0.117 ±\pm 0.0130.145 ±\pm 0.0190.194 ±\pm 0.0360.282 ±\pm 0.0150.349 ±\pm 0.035
Staged NPO, shuffled κ\kappa0.120 ±\pm 0.0050.135 ±\pm 0.0240.185 ±\pm 0.0310.261 ±\pm 0.0300.341 ±\pm 0.035
Staged NPO, difficulty ordering, Hard-to-Easy (H2E)0.118 ±\pm 0.0130.134 ±\pm 0.0230.187 ±\pm 0.0240.268 ±\pm 0.0130.339 ±\pm 0.025
Staged NPO, difficulty ordering, Easy-to-Hard (E2H)0.109 ±\pm 0.0200.137 ±\pm 0.0180.185 ±\pm 0.0290.259 ±\pm 0.0250.329 ±\pm 0.039

The matched controls show additional numerical gains from ordering: E2H has lower mean ΔU\Delta U than random staging at all five rates, and H2E at four. At 20–50%, H2E also has smaller across-seed standard deviations than both randomized controls. The full H2E schedule improves over one-shot NPO at every tested rate.

Averaged across rates, the gain from one-shot NPO to random staging is slightly larger than the further gain from random staging to E2H. Shuffled κ\kappa remains competitive, and some dataset–GNN combinations perform similarly. These results support ordering as a complementary contribution whose benefit varies with the setting. Understanding these dataset- and GNN-dependent effects remains a valuable research direction.

Comparison scope. Our original H2E preference comes from rankings across 11 complexity metrics and nine dataset–GNN pairs. This table fixes the metric to gradient norm and reports mean ΔU\Delta U, favoring E2H over H2E at four of five rates. Different metric coverage and aggregation can favor different directions.

Complementary evidence on the score. The node-level probe discussed above in W2, Q1 examines how the score relates to collateral damage. A separate grouping diagnostic uses per-node cross-entropy gradients in evaluation mode at θtr\theta_{\mathrm{tr}}: mean within-stage dispersion divided by whole-forget-set dispersion is 0.61 for H2E and 0.87 for random ordering, with H2E lower in 81% of settings. This supports the grouping design without establishing a causal link to final utility gains.

Revision. We have clarified the contributions of staging and ordering in Section 4.5 and added the matched controls and diagnostics to App. G.7.

Reviewer_txeGOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies label-level graph unlearning on a fixed graph under mass deletion, where up to 50% of training labels must be forgotten — a regime prior work, evaluated mostly at ≤5%, largely bypasses, and where existing methods suffer a sharp utility drop termed catastrophic unlearning. It proposes CUNO, which (i) partitions the forget set into K curriculum stages ordered by an unlearning-difficulty score (default per-sample gradient norm, hard-to-easy, with overlapping stages) and (ii) forgets each stage with a distribution-level negative preference optimisation (NPO) objective plus a retain loss. Theoretical analysis frames curriculum as a dispersion–drift trade-off and NPO as bounded and self-dampening, unlike gradient ascent. Experiments on Cora, CiteSeer and PubMed with GCN, GAT and GraphSAGE (5 seeds) against GA, GIF, INPO, ETR and Retrain show CUNO preserves the highest model utility among approximate methods at all deletion rates (e.g., MU 0.56 vs. 0.20–0.39 for baselines at 20% deletion; 0.42 vs. Retrain 0.69 at 50%) and matches Retrain's membership-inference level most closely at 20% deletion, with ablations for curriculum, NPO and hyperparameters.

Critical strengths
  • Important, underexplored mass-deletion regime. Prior graph unlearning is evaluated mostly at ≤5% deletion; by extending to 50% and documenting catastrophic unlearning, the paper exposes a failure mode that is invisible at conventional rates and defines the operating point where a new method is actually needed.
  • Large, consistent empirical gain with extensive validation. CUNO preserves the highest utility among approximate methods across 3 datasets, 3 GNN architectures, 7 deletion rates and 5 seeds (e.g., MU 0.56 vs. 0.20–0.39 for baselines at 20% deletion), with component and hyperparameter ablations — so the benefit does not appear to be an artefact of a single dataset, architecture, or deletion rate.
Critical weaknesses
  • Curriculum contribution not isolated. No random-ordering / shuffled-κ control is provided, and the ablation shows NPO accounts for most of the gain (ΔU 0.55 → 0.22 without curriculum, vs. 0.18 with it at 20% deletion), while easy-to-hard and hard-to-easy perform similarly. This is consequential because the paper's central claim — that difficulty-ordered forgetting drives the improvement — may instead be explained by staged optimisation and the NPO objective alone.
  • Narrow, label-only evaluation vs. broad graph-unlearning claims. All nodes, edges and features remain in the fixed graph, forget sets are sampled uniformly at random, and evaluation covers only three small homophilous citation graphs. This is consequential because it leaves untested the structural, correlated and larger-scale deletions that motivate the work in Sec. 1, so generality beyond this setting is unclear.
Questions for authors
  1. [Additional experiment — could change my assessment] With identical K, overlap, total budget and NPO loss, what are MU/ΔU for (a) random ordering and (b) shuffled κ, across deletion rates? If either matches CUNO, how should the difficulty-ordering claim be interpreted?
  2. [Additional experiment — could change my assessment] Does the gain hold under structured deletion, e.g., when the forget set is a community, class, or participant cluster rather than uniformly sampled, as motivated in Sec. 1?
  3. [Additional results — could change my assessment] Please report raw and transformed FE-MIA (mean ± std) at all deletion rates, not only 20% in Fig. 4. Does CUNO's calibration to Retrain hold at 40–50%?
  4. [Clarification] Please reconcile K=4 (Sec. 4.1, App. F.2) with K=8 described as the default in App. E.1, and clarify how the overlapping stages are counted in the budget: with ρ_ov=0.5, do overlapped samples receive more forget updates than non-overlapped samples under the equal-epoch budget?
5 comments

We thank the reviewer for the thoughtful feedback. For readability and to stay within the character limit per reply, we address the comments in separate replies below, starting with W1 and Q1.

W1, Q1 — Contribution of difficulty ordering

  • Whether the gains come from difficulty ordering or from staged optimization and NPO alone.
  • MU/ΔU for random ordering and shuffled κ across deletion rates, with matched stage count, overlap, objective and budget.

Response

We thank the reviewer for highlighting the need to separate ordering from staging. We compare one-shot NPO with four staged variants that share the stage construction, overlap, objective and update budget, differing only in ranking.

We evaluate three datasets, three GNNs, five seeds and five deletion rates. The table reports ΔU\Delta U (lower is better): we average the nine dataset–GNN pairs within each seed, then report mean ±\pm std across seeds.

Scheduleγ=5%\gamma=5\%γ=10%\gamma=10\%γ=20%\gamma=20\%γ=40%\gamma=40\%γ=50%\gamma=50\%
One-shot NPO0.128 ±\pm 0.0150.153 ±\pm 0.0180.214 ±\pm 0.0280.309 ±\pm 0.0180.367 ±\pm 0.024
Staged NPO, random ordering0.117 ±\pm 0.0130.145 ±\pm 0.0190.194 ±\pm 0.0360.282 ±\pm 0.0150.349 ±\pm 0.035
Staged NPO, shuffled κ\kappa0.120 ±\pm 0.0050.135 ±\pm 0.0240.185 ±\pm 0.0310.261 ±\pm 0.0300.341 ±\pm 0.035
Staged NPO, difficulty ordering, Hard-to-Easy (H2E)0.118 ±\pm 0.0130.134 ±\pm 0.0230.187 ±\pm 0.0240.268 ±\pm 0.0130.339 ±\pm 0.025
Staged NPO, difficulty ordering, Easy-to-Hard (E2H)0.109 ±\pm 0.0200.137 ±\pm 0.0180.185 ±\pm 0.0290.259 ±\pm 0.0250.329 ±\pm 0.039

Difficulty ordering provides additional numerical gains over random staging: E2H has lower mean ΔU\Delta U at all five rates, and H2E at four. At 20–50%, H2E also has smaller across-seed standard deviations than both randomized controls. Averaged across rates, the gain from one-shot NPO to random staging is slightly larger than the further gain from random staging to E2H. Shuffled κ\kappa remains competitive, and some dataset–GNN combinations perform similarly. Understanding when ordering helps and which direction works best remains a valuable research direction.

Comparison scope: The original H2E preference comes from rankings across 11 complexity metrics and nine dataset–GNN pairs. This table fixes the metric to gradient norm and reports mean ΔU\Delta U, with E2H performing better than H2E at four of five rates. The different metric coverage and aggregation can favor different directions.

Additional evidence supporting difficulty scoring. We conducted two analyses using the default per-node task-loss gradient norm κ\kappa:

  • Identifying potentially disruptive nodes. We apply task-loss gradient ascent to one forget node at a time and measure the positive retained-loss increase. The highest-κ\kappa quarter accounts for 54% of the total increase, versus an expected 25% for random selection (p<10−15p<10^{-15}, Wilcoxon test across 165 configurations).
  • Reducing within-stage task-loss gradient dispersion. Using per-node cross-entropy gradients in evaluation mode at θtr\theta_{\mathrm{tr}}, the mean within-stage dispersion divided by whole-forget-set dispersion is 0.61 for H2E and 0.87 for random ordering. H2E gives lower dispersion in 81% of settings.

These diagnostics support the scheduling design without establishing a causal link to final utility gains.

Revision. We have clarified the contributions of staging and ordering in Section 4.5 and added the matched controls and diagnostics to App. G.7.

W2, Q2 — Structured deletion and scope

  • Whether the gains hold for community-, class- or participant-based forget sets rather than uniform sampling.
  • Whether fixed-graph label unlearning on small citation graphs supports the broader claims about graph unlearning.

Response

We thank the reviewer for raising the issue of structured deletion. Particularly, we tested community- and class-based deletion with the same hyperparameters as uniform deletion.

We add communities (detected by seeded Louvain) or classes in random order until reaching ⌊γ∣Vtrain∣⌋\lfloor\gamma|\mathcal V_{\mathrm{train}}|\rfloor labels. We subsample the final group to match the deletion budget. Below are the 20% and 50% results. Entries average nine dataset–GNN pairs within each seed, then report mean ±\pm std over five seeds.

MethodCommunity, 20%Community, 50%Class, 20%Class, 50%
Retrain0.729 ± 0.0080.655 ± 0.0110.692 ± 0.0310.476 ± 0.048
GA0.223 ± 0.0230.218 ± 0.0370.266 ± 0.0420.205 ± 0.054
GIF0.297 ± 0.0690.235 ± 0.0100.219 ± 0.0570.270 ± 0.009
INPO0.362 ± 0.0350.373 ± 0.0610.288 ± 0.0720.354 ± 0.029
ETR0.431 ± 0.0550.372 ± 0.0370.466 ± 0.0850.393 ± 0.048
CUNO0.583 ± 0.0210.412 ± 0.0320.589 ± 0.0300.388 ± 0.035

CUNO has the highest average MU among the compared approximate methods at 5–40% deletion. At 20%, it exceeds the strongest approximate baseline by 0.152 MU under community deletion and 0.123 under class deletion. At 50%, it leads under community deletion and is close to ETR under class deletion (0.388 versus 0.393). These results support utility preservation under correlated label deletion. These datasets have no participant IDs, so we cannot test participant-level deletion directly.

Evaluation with larger forget sets. To assess requests involving more training labels, we also tested CoauthorCS, which contains 18,333 nodes and 10,999 training labels, with 549–5,499 labels forgotten. Across three GNNs and five seeds, CUNO has the highest average MU and transformed FE-MIA among the valid approximate baselines at each tested rate. At 50%, its MU is 0.595 ± 0.004, versus 0.552 ± 0.018 for the next-best baseline, INPO. Its transformed FE-MIA is 0.623 ± 0.008, versus 0.350 ± 0.021 for INPO. This improves on the baselines but still leaves a substantial gap to Retrain. GIF produced invalid outputs under the shared configuration and is excluded.

Clarifying the unlearning setting. Both the main experiments in the paper and the additional community-based, class-based and CoauthorCS experiments evaluate label unlearning on a fixed graph, where nodes, edges and features remain unchanged.

Revision. We have added the structured-deletion protocol and results to App. G.10 and the CoauthorCS results to App. G.11. The Introduction and App. H clarify the scope of label unlearning on a fixed graph.

Q3 — FE-MIA at all deletion rates

  • Raw and transformed FE-MIA (mean ± std) at all deletion rates.
  • Whether calibration to Retrain holds at 40–50% deletion.

Response

We thank the reviewer for pointing out the need to report forgetting results at all deletion rates. We agree that evaluating forgetting at high deletion rates is essential to support the mass-deletion claim. We report raw and transformed FE-MIA at all seven deletion rates below.

The transformed score is 1−∣FEMIAmethod−FEMIARetrain∣1-|\mathrm{FE}_{\mathrm{MIA}}^{\mathrm{method}}-\mathrm{FE}_{\mathrm{MIA}}^{\mathrm{Retrain}}|. We compute it for each matched run before averaging. Entries average nine dataset–GNN pairs within each seed and report mean ±\pm std over five seeds.

Raw FE-MIA (Retrain is the reference):

γ\gamma (%)RetrainGAGIFINPOETRCUNO
110.767 ±\pm 0.1901.000 ±\pm 0.0000.633 ±\pm 0.2740.433 ±\pm 0.1491.000 ±\pm 0.0000.033 ±\pm 0.075
220.844 ±\pm 0.0911.000 ±\pm 0.0000.622 ±\pm 0.1070.611 ±\pm 0.0681.000 ±\pm 0.0000.011 ±\pm 0.025
550.887 ±\pm 0.0460.986 ±\pm 0.0080.803 ±\pm 0.0610.626 ±\pm 0.0481.000 ±\pm 0.0000.853 ±\pm 0.044
10100.853 ±\pm 0.0600.985 ±\pm 0.0090.823 ±\pm 0.0240.637 ±\pm 0.0181.000 ±\pm 0.0000.877 ±\pm 0.030
20200.901 ±\pm 0.0180.972 ±\pm 0.0100.884 ±\pm 0.0140.693 ±\pm 0.0311.000 ±\pm 0.0000.885 ±\pm 0.021
40400.918 ±\pm 0.0240.960 ±\pm 0.0120.887 ±\pm 0.0060.748 ±\pm 0.0131.000 ±\pm 0.0000.921 ±\pm 0.011
50500.940 ±\pm 0.0120.951 ±\pm 0.0040.883 ±\pm 0.0090.765 ±\pm 0.0151.000 ±\pm 0.0000.922 ±\pm 0.012

Transformed FE-MIA (1 means the same attack score as Retrain):

γ\gamma (%)GAGIFINPOETRCUNO
110.767 ±\pm 0.1900.667 ±\pm 0.1670.533 ±\pm 0.1390.767 ±\pm 0.1900.267 ±\pm 0.190
220.844 ±\pm 0.0910.533 ±\pm 0.1080.567 ±\pm 0.1070.844 ±\pm 0.0910.167 ±\pm 0.104
550.880 ±\pm 0.0400.803 ±\pm 0.0590.597 ±\pm 0.0980.887 ±\pm 0.0460.811 ±\pm 0.077
10100.865 ±\pm 0.0580.828 ±\pm 0.0390.614 ±\pm 0.0780.853 ±\pm 0.0600.841 ±\pm 0.063
20200.917 ±\pm 0.0160.884 ±\pm 0.0130.697 ±\pm 0.0440.901 ±\pm 0.0180.866 ±\pm 0.012
40400.927 ±\pm 0.0130.920 ±\pm 0.0110.735 ±\pm 0.0280.918 ±\pm 0.0240.903 ±\pm 0.007
50500.933 ±\pm 0.0090.898 ±\pm 0.0050.750 ±\pm 0.0180.940 ±\pm 0.0120.905 ±\pm 0.016

At 40% and 50% deletion, CUNO achieves mean transformed FE-MIA scores of 0.903 and 0.905, corresponding to mean absolute gaps from Retrain of 0.097 and 0.095. These results show approximate alignment with Retrain on FE-MIA at high deletion rates. CUNO retains mean MU of 0.489 and 0.421 at these two rates. Across 5–50%, no compared approximate method achieves both higher mean MU and higher mean transformed FE-MIA than CUNO. Its advantage therefore lies in the balance between retained utility and alignment with Retrain on FE-MIA.

Q4 — Default K and overlapping updates

  • The inconsistency between the default K=4 and K=8 stated in different sections.
  • How overlap affects per-sample updates and the fairness of the optimization budget.

Response

We thank the reviewer for identifying the inconsistent stage count and raising the question of sample exposure. Both details matter for reproducibility and a fair comparison. The default setting is K=4K=4.

How stages are counted in the update budget. The nominal 50-step budget is divided among the non-empty stages produced by the partition procedure.

Do overlapping samples receive more updates? Yes. Samples shared by two stages receive twice as many forget updates as samples appearing in only one stage. Thus, a common nominal budget does not imply equal per-sample exposure.

Revision. We have corrected the default stage setting in App. E.1 and clarified the update budget and sample exposure in App. F.2.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.