- 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
-
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?
-
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
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 . 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 , and the fraction of node pairs whose rankings agree.
| Score | Mean rank correlation | Concordant pairs |
|---|---|---|
| Random ranking (expected) | 0.00 | 50% |
| Degree | 0.06 | 52% |
| Gradient norm, as used | 0.30 | 61% |
| Gradient norm, evaluation mode | 0.60 | 75% |
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:
- the theoretically motivated quantities show little consistent association with downstream performance.
- 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.
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
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(γ),
where R(γ) 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) across settings.
Under either schedule, replacing GA with NPO reduces both mean parameter distance and Δ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 is 0.67. Across seven methods (the four variants above plus GIF, INPO and ETR), the mean correlations with Δ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 κ 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. 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.
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.