On Structural Explanation of Bias in Graph Neural Networks
Graph Neural Networks (GNNs) have shown satisfying performance in various
graph analytical problems. Hence, they have become the \emph{de facto} solution
in a variety of decision-making scenarios. However, GNNs could yield biased
results against certain demographic subgroups. Some recent works have
empirically shown that the biased structure of the input network is a
significant source of bias for GNNs. Nevertheless, no studies have
systematically scrutinized which part of the input network structure leads to
biased predictions for any given node. The low transparency on how the
structure of the input network influences the bias in GNN outcome largely
limits the safe adoption of GNNs in various decision-critical scenarios. In
this paper, we study a novel research problem of structural explanation of bias
in GNNs. Specifically, we propose a novel post-hoc explanation framework to
identify two edge sets that can maximally account for the exhibited bias and
maximally contribute to the fairness level of the GNN prediction for any given
node, respectively. Such explanations not only provide a comprehensive
understanding of bias/fairness of GNN predictions but also have practical
significance in building an effective yet fair GNN model. Extensive experiments
on real-world datasets validate the effectiveness of the proposed framework
towards delivering effective structural explanations for the bias of GNNs.
Open-source code can be found at https://github.com/yushundong/REFEREE.