GUIC: Certified Graph Unlearning with Individual Fairness Guarantees

Abstract

Graph unlearning, motivated by emerging right to be forgotten regulations, seeks to remove the influence of specific subsets of data (e.g., noisy, poisoned, or privacy-sensitive data) from pre-trained graph learning models. While much attention has focused on the technical feasibility of unlearning, its implications for fairness remain largely unexamined. To address this critical gap, this paper introduces GUIC, the first framework that jointly ensures certified unlearning and individual fairness in graph-based models, introducing a novel perspective on responsible model updates in graph unlearning. Specifically, GUIC employs a principled distance-based rule to pinpoint individual biases arising from node removals and applies a computationally efficient certificate-driven update, preserving the local Lipschitz constraints crucial for individual fairness. Different from computationally expensive retraining or fairness-regularized optimization methods, GUIC provides a lightweight yet verifiable alternative with theoretical fairness guarantees. Experiments on multiple real-world datasets show that our method consistently surpasses existing approaches across key performance metrics.