Forget Gradient Surgery: A Characterization of Projected Gradient Descent for Graph Edge Unlearning

Abstract

Preprint of the paper 'Forget Gradient Surgery: A Characterization of Projected Gradient Descent for Graph Edge Unlearning' (submitted to TMLR). Machine unlearning for graph neural networks is complicated by message passing: deleting an edge from the adjacency matrix does not erase what the parameters learned from it, and naive gradient ascent on the forgotten edges degrades performance on the rest of the graph. We study Forget Gradient Surgery (FGS), an approximate edge-unlearning method that combines a forget direction defined as the gradient of the forgotten-edge link logits under the post-deletion adjacency, an orthogonal projection against a deterministic retain anchor, and a data-driven stopping rule. Evaluated against retrain-from-scratch on Cora, CiteSeer, and PubMed (n = 10 seeds each) across deletion fractions 1%-20%, with link-inference attack AUC as the forgetting metric and held-out link AUC as utility, we find a Pareto frontier rather than a single winner: the KS-stopped variant is 2.3-2.7x faster than retraining and not significantly different from retrain on PubMed (attack gap +0.002, p = 0.40) and Cora (attack gap +0.008, p = 0.19), but under-forgets on CiteSeer (attack gap +0.037) and collapses at 20% deletion on Cora (utility -0.055). An attack-calibrated stopping variant closes the CiteSeer gap (paired improvement +0.028, p < 0.001) at the cost of up to 2x retraining time. A matched no-projection ablation shows the projection causally preserves utility (Cora -0.048, p < 0.001, dz = -2.51) while naive ascent destroys it.