A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks

Abstract Graph Neural Networks (GNNs) are increasingly being used for a variety of ML applications on graph data. Because graph data does not follow the independently and identically distributed (i.i.d.) assumption, adversarial manipulations or incorrect data can propagate to other data points through message passing, which deteriorates the model's performance. To allow model developers to remove the adverse effects of manipulated entities from a trained GNN, we study the recently formulated problem of Corrective Unlearning. We find that current graph unlearning methods fail to unlearn the effect of manipulations even when the whole manipulated set is known. We introduce a new graph unlearning method, Cognac, which can unlearn the effect of the manipulation set even when only 5% of it is identified. It recovers most of the performance of a strong oracle with fully corrected training data, even beating retraining from scratch without the deletion set, and is 8x more efficient while also scaling to large datasets. We hope our work assists GNN developers in mitigating harmful effects caused by issues in real-world data, post-training. Beyond introducing a novel method, this work advances scientific methodology in GNN unlearning. We first use adversarial evaluation for graph unlearning methods beyond privacy applications, showing that metrics must genuinely reflect unlearning efficacy in corrective settings. Our extensive baselining includes methods from other domains like image unlearning for the first time in GNN unlearning, revealing that non-graph-specific approaches can surprisingly outperform graph-specific SOTA. Furthermore, our rigorous ablations challenge prevalent assumptions in GNN unlearning literature; for example, we show that common practices like node unlinking are not universally beneficial. xii Chapter 1