ReCoGU: Retention-Aware Coarsening for Graph Unlearning

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 $\rho =0.904$ and $0.629$), and ablations show that mean features and inter-unit connections both reduce CUL.