ELEGANT: Certified Defense on the Fairness of Graph Neural Networks
Yushun Dong Binchi Zhang Hanghang Tong Jundong Li
Graph Neural Networks (GNNs) have emerged as a prominent graph learning model
in various graph-based tasks over the years. Nevertheless, due to the
vulnerabilities of GNNs, it has been empirically proved that malicious
attackers could easily corrupt the fairness level of their predictions by
adding perturbations to the input graph data. In this paper, we take crucial
steps to study a novel problem of certifiable defense on the fairness level of
GNNs. Specifically, we propose a principled framework named ELEGANT and present
a detailed theoretical certification analysis for the fairness of GNNs. ELEGANT
takes any GNNs as its backbone, and the fairness level of such a backbone is
theoretically impossible to be corrupted under certain perturbation budgets for
attackers. Notably, ELEGANT does not have any assumption over the GNN structure
or parameters, and does not require re-training the GNNs to realize
certification. Hence it can serve as a plug-and-play framework for any
optimized GNNs ready to be deployed. We verify the satisfactory effectiveness
of ELEGANT in practice through extensive experiments on real-world datasets
across different backbones of GNNs, where ELEGANT is also demonstrated to be
beneficial for GNN debiasing. Open-source code can be found at
https://github.com/yushundong/ELEGANT.