GUIC: Certified Graph Unlearning with Individual Fairness Guarantees
Wang, Zichong Liu, Tongliang Zhang, Wenbin
Wang, Zichong
Liu, Tongliang
Zhang, Wenbin
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
License
Language
Collections
Research Projects
Organizational Units
Journal Issue
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.
Citation
Z. Wang, T. Liu, W. Zhang, "GUIC: Certified Graph Unlearning with Individual Fairness Guarantees," 2026, pp. 35820-35828.
Source
Proceedings of the AAAI Conference on Artificial Intelligence
Conference
Fortieth AAAI Conference on Artificial Intelligence
Keywords
46 Information and Computing Sciences, 4611 Machine Learning
Subjects
Source
Fortieth AAAI Conference on Artificial Intelligence
Publisher
Association for the Advancement of Artificial Intelligence