Reconstruct Then Rectify: Information-Conserving Node Interaction Estimation for Graph Unlearning

Graph unlearning aims to remove the influence of specified nodes or edges from a trained graph neural network (GNN). We study efficient approximate node unlearning, whose target is to reproduce the behavior of retraining without claiming a certified deletion guarantee. Existing approaches can require partial retraining, full-parameter re-estimation, or accurate influence approximation. We propose Reconstruct Then Rectify (RTR), a post-hoc framework that leaves the base GNN parameters fixed. RTR first learns initial node-interaction estimates through information-conserving reconstruction and then refines them using a range–null-space decomposition under a linear inverse constraint. The refined interactions are subtracted from retained-node embeddings. Under the stated linear-inverse assumptions, the rectification preserves the constraint and does not increase the squared $L_2$ estimation error. Experiments on multiple datasets and four GNN backbones show substantial runtime reductions while maintaining utility close to retraining; we further evaluate poisoned-node removal and resistance to MIA.