PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.08244v1cs.LGcs.AI

TL;DR

Graph unlearning can suffer catastrophic utility loss under mass deletion because graph dependencies make deleted samples unevenly difficult to forget. CUNO progressively orders deletions by estimated difficulty and applies distribution-level NPO while preserving retained behavior, consistently mitigating utility collapse at high deletion ratios.

  • Problem

    Graph unlearning must remove designated training data without retraining from scratch, but existing methods can substantially degrade retained-data utility as deletion ratios grow.

  • Method

    CUNO combines difficulty-ordered curriculum scheduling with distribution-level NPO and a retain objective for staged graph unlearning.

  • Results

    At 20% deletion, CUNO achieves up to 4 times higher model utility than existing methods and consistently mitigates catastrophic unlearning across high deletion rates.

  • Takeaways & Limitations

    Curriculum unlearning is most beneficial when the forget set spans a wide range of difficulty, a condition naturally satisfied under mass deletion.

  • Takeaways & Limitations

    Stage count and epoch allocation are chosen empirically and fixed, while self-adaptive scheduling does not consistently outperform the fixed baseline because message passing contaminates adaptive signals.

Abstract

from arXiv · show

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.

1 Introduction

Graph unlearning faces catastrophic utility loss as deletion ratios grow, especially because graph dependencies make deleted nodes unevenly consequential. CUNO addresses this with progressive curriculum scheduling and distribution-level NPO, improving utility preservation under mass deletion.

  • Motivation: Existing graph unlearning methods can substantially degrade retained-data utility, with the problem worsening as deletion ratios increase.Catastrophic unlearning is defined by utility loss growing faster than retraining loss.
  • Motivation: Beyond 5% deletion, existing methods’ average utility drops sharply while Retrain degrades more gracefully, although most prior evaluations stop at 5%.This leaves the high-ratio regime largely unexplored despite real-world deletion scenarios reaching 10–30% or more.
  • Motivation: Graph structural dependencies give nodes different roles and cause deletion effects to propagate through retained neighborhoods and multi-hop message passing.A leaf node and a high-degree hub can therefore impose substantially different collateral effects during unlearning.
  • CUNO: CUNO progressively removes the forget set using curriculum scheduling rather than deleting all samples at once.The framework orders deleted samples by estimated complexity to smooth optimization and reduce abrupt utility collapse.
  • CUNO: CUNO extends NPO to a distribution-level objective that provides more controlled forgetting for node-level mass deletion.The approach combines curriculum scheduling with NPO to improve utility preservation under large deletion ratios.
  • Results: At 20% deletion, CUNO achieves up to 4 times higher model utility than existing methods.Experiments across multiple datasets and GNN architectures show improved utility preservation at high deletion ratios.

2 Problem Formulation

The paper formulates graph unlearning as removing designated training samples’ influence while preserving retained-data utility. It defines mass deletion by deletion rate and characterizes catastrophic unlearning through utility loss relative to retraining.

  • Graph learning and unlearning: The supervised node-classification setting uses a graph G=(V,E,X), with labeled training nodes and a graph model producing class-distribution predictions.The model is trained by minimizing cross-entropy on labeled training nodes.
  • Graph learning and unlearning: An unlearning algorithm transforms a trained model using forget set S_d while preserving predictive utility on retain set S_r.The retain set is the training set excluding designated deleted samples.
  • Mass deletion and catastrophic unlearning: Mass deletion is defined by deletion rate γ=|S_d|/|S_tr|, while utility drop is ΔU(γ)=U(f_θtr)−U(f_θunl).These quantities measure deletion scale and the resulting utility loss.
  • Mass deletion and catastrophic unlearning: Catastrophic unlearning occurs when utility loss grows substantially faster than the inherent loss from retraining from scratch.The gap widens rapidly beyond γ=5%, after being modest at γ≤2%.

3 Method

CUNO combines curriculum scheduling, which determines when samples are forgotten, with distribution-level NPO, which determines how forgetting is performed. Staged updates and retention loss are designed to smooth optimization and preserve utility under mass deletion.

  • Curriculum scheduling: CUNO orders deleted samples by estimated unlearning difficulty and progressively processes them in staged subsets.This converts one-shot unlearning into staged optimization based on a scalar complexity score.
  • Curriculum scheduling: Curriculum scheduling has four design dimensions: complexity metric, stage count, ordering, and overlap.These choices control difficulty estimation, granularity, processing direction, and transitions between stages.
  • Curriculum scheduling: Overlapping stages reduce stage drift because the theoretical bound scales with 1−ρ_ov.Shared samples expose the model to mixed difficulty levels during transitions.
  • Distribution-level NPO: Distribution-level NPO steers predictions away from a frozen reference across all classes rather than comparing a single response.It is designed for the full predictive distributions in multi-class node classification.
  • Empirical behavior: Across datasets and GNN models, CUNO consistently achieves lower utility drop across deletion rates.Figure 3 reports model utility and utility drop over rates from 1% through 50%.
  • Distribution-level NPO: NPO self-dampens forgetting gradients on samples that have already been forgotten, concentrating optimization on samples still requiring forgetting.The gradient contribution vanishes as forgetting succeeds.
  • Stage-wise update: Each stage combines the NPO forget objective with a retain objective weighted by λ to preserve utility on retained data.The full graph and full retain set are used at every stage.

4 Experiments

Experiments evaluate CUNO across graph datasets, GNN architectures, deletion rates, forgetting metrics, and ablations. CUNO preserves utility under mass deletion while combining curriculum scheduling with NPO to reduce utility degradation and improve calibrated forgetting.

  • Model Utility Preservation: At γ=20%, existing methods reach MU values of 0.20, 0.34, and 0.39, below the Retrain reference of 0.74.Their utility drops exceed ∆U=0.44, and degradation worsens at γ=50%.
  • Model Utility Preservation: CUNO preserves the highest model utility among approximate methods across deletion rates, achieving MU=0.56 and ∆U=0.19 at γ=20%.This retains 74% of the original utility, compared with 26% for GA and 45% for GIF.
  • Model Utility Preservation: At γ=50%, CUNO maintains MU=0.42 and ∆U=0.33, while the next-best method, INPO, reaches MU=0.37 and ∆U=0.38.The advantage over competing methods increases as deletion becomes more aggressive.
  • Forget Effect Analysis: CUNO achieves FE=0.81 at MU=0.56 under FE-Standard, whereas GA reaches FE=0.92 with MU=0.20.FE-Standard is confounded by neighborhood-driven label inference, so higher values alone do not establish better unlearning.
  • Forget Effect Analysis: CUNO reaches transformed FE-MIA=0.98 with MU=0.56, matching Retrain’s membership-privacy level while preserving the highest utility among non-Retrain methods.FE-MIA penalizes both over-erasing and under-erasing relative to Retrain.
  • Ablation Study: The full CUNO method has the lowest utility drop across ablations, with ∆U=0.18 at γ=20% versus 0.22 without curriculum and 0.47 without NPO.The results support complementary contributions from curriculum scheduling and NPO.
  • Hyperparameter Study: Across 9 scenarios, K=8 accounts for 18 of 45 top-five appearances, while M-GN and T-D each accumulate 6 top-five appearances.No single complexity metric dominates across all curriculum-stage counts.
  • Hyperparameter Study: Overlapping curriculum ranks first in 96 of 99 comparisons, while hard-to-easy ordering ranks first in 57 versus 42 for easy-to-hard.The no-curriculum baseline ranks last in 97 of 99 ordering comparisons.

5 Conclusion

The paper identifies catastrophic unlearning as a key challenge under mass deletion and proposes CUNO, combining progressive curriculum forgetting with distribution-level NPO. Theory and experiments support its effectiveness across deletion rates up to 50%, while future work targets broader graph settings and adaptive scheduling.

  • Conclusion: CUNO combines curriculum-based progressive forgetting with distribution-level NPO to mitigate catastrophic unlearning under mass deletion.The curriculum sequences deletions, while NPO focuses gradients on not-yet-forgotten samples.
  • Conclusion: Curriculum unlearning is theoretically most beneficial when the forget set spans a wide range of unlearning difficulty.The paper identifies this condition as naturally satisfied under mass deletion.
  • Conclusion: Experiments across multiple datasets and GNN architectures show that CUNO mitigates catastrophic unlearning across deletion rates up to 50%.The conclusion reports that CUNO substantially outperforms existing methods in this regime.
  • Future Work: Future directions include extending CUNO to heterogeneous and dynamic graphs and developing self-adaptive curriculum scheduling.These directions define the stated scope beyond the current study.

B.2 Catastrophic Drop in Machine Unlearning

Approximate unlearning methods face a trade-off between forgetting target data and preserving retained utility, especially for large or influential deletions. Catastrophic unlearning motivates more stable objectives and exposes an underdeveloped role for curriculum scheduling in graph unlearning.

  • Large or influential deletion requests intensify the trade-off between forgetting quality and retained utility.
  • Catastrophic unlearning describes drastic degradation of general utility caused by aggressive forgetting objectives.
  • Negative preference optimization aims to move models away from undesired behavior while slowing utility collapse relative to standard gradient ascent.
  • Curriculum learning: Curriculum learning organizes samples or tasks into meaningful progressions, often from easier examples to harder ones.
  • Curriculum learning: Curriculum methods have expanded to graph learning but remain underdeveloped in machine and graph unlearning.

C Complexity Metrics for Curriculum Construction

CUNO estimates deletion difficulty using topology, model response, retain coupling, and task-boundary signals, then orders the forget set into curriculum stages. The design includes safeguards for sparse retain neighborhoods, computational-cost trade-offs, and a default gradient-norm metric motivated by model influence.

  • Topology-based metrics: Topology-based metrics estimate difficulty from structural position, offering model-agnostic, efficient, and interpretable proxies for removal disruption.Examples include degree, betweenness centrality, PageRank, clustering coefficient, and eigenvector centrality.
  • Model-response metrics: Model-response metrics capture memorization or parameter sensitivity that topology alone may miss.Prediction Confidence reflects predictive sharpness, while Gradient Norm measures a deleted sample’s influence on model parameters.
  • Retain-coupling metrics: Retain-coupling metrics estimate collateral impact on retained representations, connectivity, and multi-hop receptive fields.RC, MRC, and RBC respectively capture retained-neighbor alignment, influence spread, and retained-node connectivity disruption.
  • Task-boundary metrics: Task-boundary metrics identify deleted samples near decision boundaries, which are harder to remove without disturbing task-relevant structure.Class-Boundary Heterophily assigns higher difficulty to nodes closer to cross-class boundaries.
  • Practical considerations: Sparse retain neighborhoods trigger κ(v)=0, while preprocessing costs range from under 10ms for T-D and T-CC to under 10s for M-GN.The fallback reduces retain-coupling discrimination at high γ; M-GN is the default motivation despite its higher scoring cost.
  • Curriculum construction: CUNO computes a complexity score for each deleted sample, sorts the forget set, and partitions it into overlapping curriculum stages.The procedure supports easy-to-hard or hard-to-easy ordering and allocates a per-stage epoch budget.

E.1 The Dispersion–Drift Trade-off

The dispersion–drift analysis explains when curriculum unlearning improves optimization: partitioning reduces conflicting within-stage gradients, while overlap controls target drift between stages. The benefit is strongest when difficulty heterogeneity is reducible without excessive stage transitions.

  • Dispersion: Partitioning reduces average intra-stage gradient dispersion by the between-stage dispersion amount Dinter(θ).Lower dispersion improves alignment between individual forget gradients and the stage-mean update.
  • Drift: Curriculum convergence trades lower in-stage dispersion against a drift cost that remains bounded as the number of stages increases.The theorem requires η≤1/L and sufficient per-stage steps so α<1.
  • Dispersion: High within-stage dispersion limits per-sample progress because averaged updates can point poorly toward individual forget gradients.The analysis distinguishes gradient dispersion from stochastic sampling variance in full-batch optimization.
  • Drift: Overlap controls stage drift because shared samples cancel between adjacent objectives, leaving only their symmetric difference.The resulting drift scales with the non-overlapping portion of adjacent stages.
  • Conditions for benefit: Curriculum helps when partitioning meaningfully reduces heterogeneity and maximum stage drift remains small.These conditions connect metric quality, overlap, and stage design to the optimization advantage over one-shot unlearning.
  • Practical implications: The advantage grows with deletion ratio, overlapping partitions rank first in 96/99 comparisons, and utility gains plateau beyond K>8.The paper attributes these patterns to greater forget-set heterogeneity, reduced drift, and diminishing within-stage separation.
  • NPO: NPO self-dampens gradients on already-forgotten samples, unlike gradient ascent, whose forgetting signal does not automatically diminish.The NPO gradient remains uniformly bounded in the distribution-level formulation.

F.1 Dataset Statistics

The evaluated datasets have high edge homophily, allowing retained-set information to continue reaching forget nodes through message passing and making unlearning difficult. Cora additionally has the highest reported average local clustering coefficient, indicating tightly interconnected neighborhoods.

  • All three datasets have high edge homophily, with h≥0.74, so retained-set signal can leak into forget nodes through message passing.
  • Cora has the highest average local clustering coefficient, C=0.241, indicating tightly interconnected local neighborhoods.

F.2 Supplementary Implementation details.

The supplementary implementation evaluates CUNO across diverse datasets, architectures, deletion rates, and random seeds using shared training and unlearning controls. It fixes core CUNO settings and aligns baseline configurations to support fair comparisons.

  • Model training: All GNNs use 200 Adam epochs, learning rate 10^-2, weight decay 5×10^-4, hidden dimension 64, two message-passing layers, and dropout 0.5.The best validation checkpoint is shared by all methods.
  • Unlearning budget: Unlearning methods receive the same T = 50-epoch budget and learning rate 10^-1, while training-free ETR and GIF use closed-form procedures.CUNO divides the 50 epochs across effective curriculum stages.
  • Forget-set construction: The forget set uniformly samples training nodes without class or topological stratification, including both hubs and peripheral leaves.Validation and test nodes are excluded, and all methods share the same seeded partition and pretrained checkpoint.
  • CUNO configuration: CUNO uses K = 8 overlapping stages with ρ = 0.2, hard-to-easy ordering, gradient-norm complexity, β = 0.1, λ = 0.5, and τ = 1.0.Its preference reference is a frozen deep copy of the pretrained checkpoint.
  • Baseline configuration: Baseline hyperparameters follow their original implementations, with shared parameter categories aligned to eliminate confounders.GIF and ETR remain outside the epoch-budget framework because they are training-free.
  • Experimental setup: Experiments cover three datasets, three GNN architectures, seven deletion rates, two task types, and five random seeds.This design spans diverse graph structures, model families, forget-set sizes, and tasks.

F.3 Evaluation Metrics

The evaluation separates forgetting from retained-model utility using test-set generalization and two forget-effect measures. FE-Standard is treated as confounded by graph-based label inference, whereas FE-MIA more directly probes parameter-level memory.

  • Model Utility: Model Utility is evaluated on held-out test nodes, where higher MU indicates better preservation of predictive capability after deletion.Using Stest avoids overestimation that can arise when evaluating on training retain nodes.
  • Utility drop: Utility drop is ∆U = U0 − MU(θu), with positive values indicating loss relative to the original model and ∆U = 0 indicating matched or higher utility.Lower values are better.
  • Forget Effect: FE-Standard = 1 − Acc(Sd; θu), measuring one minus unlearned-model accuracy on forget nodes.Its interpretation is limited because retained-graph neighborhoods can still support label inference.
  • Forget Effect: On Cora, CiteSeer, and PubMed, Retrain obtains FE-Standard values of 0.38, 0.47, and 0.11, respectively, reflecting dataset-dependent structural predictability.These values primarily reflect neighborhood-driven inference rather than unlearning success.
  • FE-MIA: FE-MIA uses a shadow classifier trained on the original model to test whether forget-set examples still appear as training members.The same attack is applied unchanged across all unlearning methods.
  • FE-MIA: Retrain is the ideal behavioral reference, so its FE-MIAraw is approximately 0.83–0.94 rather than chance-level 0.5.The value reflects the shadow classifier’s false-positive rate on non-members.

G.1 Computational efficiency.

CUNO provides a favorable quality–efficiency trade-off: it preserves strong forgetting and utility while adding little runtime over plain gradient ascent and costing less than full retraining. Its utility advantage is especially visible across dataset and model configurations.

  • Runtime: CUNO adds only marginal overhead over gradient ascent while running at less than half the cost of Retrain.Retrain uses full 200-epoch retraining and is generally impractical for large graphs.
  • Runtime: ETR and GIF are fastest overall, but their speed comes with substantially lower unlearning quality.They are one-off, training-free methods rather than iterative procedures.
  • Overall comparison: CUNO matches or surpasses all baselines on FE and MU while remaining practical in runtime.This makes it the best quality–efficiency trade-off among the evaluated methods.
  • Dataset comparisons: At γ = 20% on Cora, CUNO reaches MU 0.60 versus GA’s 0.15, or 4.0× higher utility.On CiteSeer, CUNO reaches MU 0.45, with ETR next at 0.42.
  • Metric interpretation: Retrain’s low FE-Standard is attributed to neighborhood aggregation that preserves label predictability for excluded nodes.This is presented as a graph-structure artifact rather than retraining failure.
  • Dataset comparisons: On Cora and CiteSeer, CUNO reaches MU 0.60 and 0.45, while the next-best non-retrain methods reach 0.34 and 0.42.The scatter plots show separation primarily along the MU axis.

G.4 Ablation Study (Supp.)

Ablations show that curriculum scheduling and NPO each contribute to stable utility preservation, while overlapping stages and higher stage counts are robust design choices. Dataset identity affects utility more than the specific complexity metric.

  • Curriculum scheduling: At γ = 1%, CUNO has ∆U = 0.00 versus 0.07 without curriculum; at γ = 20%, the values are 0.18 versus 0.22.At γ = 50%, the corresponding values are 0.34 and 0.37.
  • Ordering: Hard-to-easy ordering increasingly outperforms easy-to-hard at higher deletion rates, winning 7/9 scenarios at γ = 40%.The two strategies are nearly identical when γ ≤ 5%.
  • Forget objective: At γ = 20%, CUNO outperforms CUNO-KL with MU 0.57 versus 0.45 and ∆U 0.18 versus 0.30.The same NPO advantage appears without curriculum: MU 0.54 versus 0.40 and ∆U 0.22 versus 0.36.
  • Cross-configuration consistency: CUNO performs best in the majority of dataset–GNN configurations, indicating stability beyond a single topology or architecture.Per-configuration results span all nine dataset–GNN combinations.
  • Stage count and metric sensitivity: Increasing K consistently improves MU across all 11 metrics, with every metric reaching higher MU at K = 8.Dataset identity is the dominant variation source, with a mean MU range of 0.117 across datasets.
  • Curriculum mode: Overlapping curriculum yields up to ∆MU = 0.15 at γ = 2% and wins 9/9 scenarios there.Its advantage narrows at moderate deletion rates and remains the more robust default overall.

H Limitation and Future Directions

CUNO mitigates catastrophic utility collapse under mass deletion, but the paper identifies unresolved limits in adaptive scheduling, theory coverage, and generalization beyond parameter-level node unlearning.

  • Self-adaptive curriculum scheduling: Self-adaptive curriculum rules did not consistently outperform fixed scheduling because message passing contaminates forget-set loss and confidence signals with retained information.The number of stages and epoch allocation are currently chosen empirically; developing robust adaptation signals remains open.
  • Theoretical characterization of complexity metrics: The theory gives explicit complexity-correlation bounds for only two metrics, while nine others lack tight analytical characterizations.A complete theoretical characterization of the remaining metrics is left for future work.
  • Extension to broader graph learning settings: CUNO removes training-data influence at the parameter level while retaining graph topology and features, so physical structural node deletion is outside scope.The paper distinguishes parameter-level unlearning from removing nodes and their incident edges.
  • Extension to broader graph learning settings: Extending CUNO to link prediction, heterogeneous graphs, and dynamic graphs remains future work because these settings require new curriculum orderings for structural and temporal dependencies.Edges and subgraphs lack a direct centrality ordering, while dynamic graphs require temporal dependency-aware curricula.
Loading 2609.08244v1…