acceptodds
Under review as a conference paper at ICLR 2027

ReCoGU: Retention-Aware Coarsening for Graph Unlearning

Abstract

Graph unlearning seeks to remove the influence of requested data while preserving utility on retained data. Reducing the training graph can lower retraining costs, but the resulting changes in features, structure, and supervision weights can introduce additional utility loss relative to full retraining on the retained graph. We propose ReCoGU, Retention-Aware Coarsening for Graph Unlearning, which constructs label-pure training units, merges adjacent small units with the same label, and represents each unit with retained-member mean features and binary inter-unit connections. ReCoGU stores feature sums, unit sizes, and inter-unit edge counts, updates only affected statistics for each request, and retrains from scratch on the updated coarse graph with square-root unit-size loss weights. We define collateral utility loss (CUL) as the difference between the average classification losses of ReCoGU and full retraining on the same retained training graph. For finite GNN outputs, aligned labels, and a Lipschitz loss, we derive a bound separating prediction distortion at the two trained parameter sets, supervision-weight correction, and surrogate optimization error. Across five datasets and three GNN backbones, ReCoGU has the lowest unlearning time in 10 of 15 settings and the second-lowest in the remaining five. Compared with baselines other than Retrain, ReCoGU achieves the highest Micro-F1 in 14 of the 15 settings. Its unlearning time ranges from 0.036 to 4.964 seconds, compared with 2.865 to 384.069 seconds for full retraining. On Cora and Physics, prediction distortion is positively associated with CUL (Spearman and ), and ablations show that mean features and inter-unit connections both reduce CUL.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph unlearning, Graph coarsening, Utility preservation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_WVFZOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ReCoGU, a graph unlearning framework that reduces retraining costs through retention-aware graph coarsening. It constructs label-pure training units, maintains locally updatable graph statistics, and retrains GNNs on the updated coarsened graph. The paper further introduces collateral utility loss (CUL) and derives a theoretical bound relating prediction distortion to retained-data utility. Experiments across five datasets and three GNN backbones demonstrate promising efficiency and classification performance.

Critical strengths
  1. The paper addresses the important trade-off between unlearning efficiency and retained-data utility. The use of locally updated coarsened graphs provides a practical approach to reducing retraining costs.

  2. The introduction of CUL and its decomposition into prediction distortion, supervision-weight correction, and optimization error provides a useful perspective for analyzing the effects of graph coarsening.

Critical weaknesses
  1. What is the fundamental technical novelty of ReCoGU beyond combining existing coarsening, local statistics updates, and weighted retraining? The paper should more clearly identify the limitations of previous coarsening-based unlearning methods and explain why the proposed components are necessary. More targeted comparisons and ablations would help distinguish the proposed contributions from existing approaches.

  2. Does the fixed partition truly eliminate the influence of deleted nodes?

A central design choice is to construct the initial label-pure partition using the original training graph and reuse it after unlearning requests. However, the initial partition depends on node features, labels, and graph structure, including information from nodes that may subsequently be deleted.

Although the proposed local updates remove deleted nodes from feature sums and edge statistics, their influence may remain indirectly through the fixed partition and surviving node assignments.

How can the authors ensure that the deleted nodes no longer influence the resulting model through the original partition? Could the authors compare the current approach against constructing a new partition directly from the retained graph? This distinction is important for establishing the validity of the proposed unlearning procedure.

  1. Insufficient justification for square-root unit-size weighting.

The method assigns each coarsened unit a loss weight proportional to the square root of its size. However, the theoretical analysis does not establish why this weighting is preferable to uniform weighting or weighting proportional to the original number of nodes.

Why is square-root weighting chosen, and how important is it to the reported performance? Could the authors provide comparisons with alternative weighting strategies and analyze how they affect CUL, classification accuracy, and class imbalance?

Questions for authors

See weakness

2 comments

Once again, we sincerely thank you for your valuable comments and requested experiments. We hope that our responses have adequately addressed all of your concerns. We would be happy to address any further questions or provide additional carification regarding the novelty and contributions of our work.

Thanks for the response. I still think the paper does not clearly explain the difference between graph unlearning and graph continual learning, and it does not present a specific challenge in the graph unlearning problem. moreover, as the paper described in the Introduction: "combining label-pure training units, structurally merging units that share the same label, performing local updates on retained statistics, and applying a square-root weighting scheme based on unit size” seems overly focused on engineering details. Still, the paper should at least have one paragraph of related work. I think this is an unfinished paper, but has its potential. I will keep myscore slightly lower the borderline

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

This paper studies graph unlearning problem, aiming to preserve utility of retained data after removing the requested nodes. Specifically, the authors explore label-pure clusters to form units, then locally update the affected unit. Finally, retrain a GNN from scratch. Experimental results support the effectiveness of the proposed method.

Critical strengths

None.

Critical weaknesses
  1. The first step is to get a lable-pure partition. This imposes two requirements on graph. First, there needs a great many of labels, so that we can get clear partition. This is unusual in graph setting, where we concern more on semi-supervised learning. Second, most of neighbor nodes belong to the same class, but the real case is neighbors usually have different labels. In this case, such partition may output many small-size units, decreasing coarsening ratio. I also notice that in such partition, the authors repeatedly compute shortest-path distance, which is a time-consuming operation.

  2. In experiments, retraining the graph after removing request nodes should have the highest performance, since it does not lose any information. But in table 1, retraining is not the best configuration.

Questions for authors

Please refere to the weaknesses.

1 comment

Once again, we sincerely thank you for your valuable comments and requested experiments. We hope that our responses have adequately addressed all of your concerns. We would be happy to address any further questions or provide additional carification regarding the novelty and contributions of our work.

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

Paper Summary

The paper proposes ReCoGU, a graph-unlearning method that compresses the training graph into label-pure units represented by supernodes. For a deletion request, it updates the affected units’ feature and edge statistics, then retrains a GNN from scratch on the updated compressed graph using square-root unit-size loss weights. The authors define collateral utility loss (CUL) relative to full retraining on the retained graph and derive a bound involving prediction distortion, supervision-weight correction, and optimization error. They evaluate ReCoGU on five datasets and three GNN backbones, measuring classification utility, unlearning time, membership-inference AUC, and CUL. The reported results indicate that ReCoGU often improves utility over other unlearning baselines and reduces retraining time compared with full retraining.

Critical strengths

Critical Strengths

  1. The coarsening procedure supports efficient updates after deletion. ReCoGU stores feature sums, unit sizes, and inter-unit edge counts, allowing it to update the compressed graph without rebuilding all of its statistics from the retained nodes. This gives a clear mechanism for reducing the cost of subsequent training.

  2. The paper analyzes the utility gap against full retraining and evaluates the method broadly. Its CUL bound separates prediction distortion, supervision-weight correction, and optimization error. Experiments across five datasets and three GNN backbones provide useful evidence about utility and runtime, even though they do not establish that the compressed training procedure is equivalent to training on the original retained graph.

Critical weaknesses

Critical Weaknesses

  1. ReCoGU changes the training procedure, which limits its applicability. The method replaces groups of original nodes with label-pure supernodes, averages their features, and reduces inter-unit connectivity to binary edges. This may work for the evaluated node-classification GNNs, but it can discard information needed by models or tasks that depend on individual nodes, edge weights, or detailed local structure. The paper does not sufficiently characterize when training on this compressed graph remains suitable or reliable.

  2. The CUL analysis does not establish that the compressed procedure reliably approximates full retraining. The bound depends on prediction distortion and weight-correction terms that are measured after training, so it is primarily a diagnostic rather than a guarantee that the method will have low utility loss in advance. The experiments show favorable results on selected datasets, but do not establish that the approximation remains reliable across broader graph structures, model families, or tasks. This limits the strength of the paper’s general claims.

Questions for authors

Questions For Authors

  1. Clarification: What is the reference training procedure for ReCoGU’s unlearning guarantee? Since the units are constructed using the original graph and labels, are they held fixed after deletion? If so, can deleted nodes continue to influence the model indirectly through the retained unit assignments?

  2. Evidence affecting the recommendation: How closely does training on the compressed graph approximate full retraining on the original retained graph across different graph structures and GNN architectures? Can the authors report comparisons that isolate the effects of mean-feature pooling, binary inter-unit edges, and square-root loss weighting?

  3. Clarification: What assumptions are needed for the CUL bound to be informative before training? Since its prediction-distortion terms are measured using trained models, how can the bound guide whether a particular graph or task will have a small utility gap?

1 comment

Once again, we sincerely thank you for your valuable comments and requested experiments. We hope that our responses have adequately addressed all of your concerns. We would be happy to address any further questions or provide additional carification regarding the novelty and contributions of our work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.