  Graph neural networks (GNNs) have achieved remarkable performance on
graph-structured data. However, GNNs may inherit prejudice from the training
data and make discriminatory predictions based on sensitive attributes, such as
gender and race. Recently, there has been an increasing interest in ensuring
fairness on GNNs, but all of them are under the assumption that the training
and testing data are under the same distribution, i.e., training data and
testing data are from the same graph. Will graph fairness performance decrease
under distribution shifts? How does distribution shifts affect graph fairness
learning? All these open questions are largely unexplored from a theoretical
perspective. To answer these questions, we first theoretically identify the
factors that determine bias on a graph. Subsequently, we explore the factors
influencing fairness on testing graphs, with a noteworthy factor being the
representation distances of certain groups between the training and testing
graph. Motivated by our theoretical analysis, we propose our framework
FatraGNN. Specifically, to guarantee fairness performance on unknown testing
graphs, we propose a graph generator to produce numerous graphs with
significant bias and under different distributions. Then we minimize the
representation distances for each certain group between the training graph and
generated graphs. This empowers our model to achieve high classification and
fairness performance even on generated graphs with significant bias, thereby
effectively handling unknown testing graphs. Experiments on real-world and
semi-synthetic datasets demonstrate the effectiveness of our model in terms of
both accuracy and fairness.
