  Fair machine learning aims to mitigate the biases of model predictions
against certain subpopulations regarding sensitive attributes such as race and
gender. Among the many existing fairness notions, counterfactual fairness
measures the model fairness from a causal perspective by comparing the
predictions of each individual from the original data and the counterfactuals.
In counterfactuals, the sensitive attribute values of this individual had been
modified. Recently, a few works extend counterfactual fairness to graph data,
but most of them neglect the following facts that can lead to biases: 1) the
sensitive attributes of each node's neighbors may causally affect the
prediction w.r.t. this node; 2) the sensitive attributes may causally affect
other features and the graph structure. To tackle these issues, in this paper,
we propose a novel fairness notion - graph counterfactual fairness, which
considers the biases led by the above facts. To learn node representations
towards graph counterfactual fairness, we propose a novel framework based on
counterfactual data augmentation. In this framework, we generate
counterfactuals corresponding to perturbations on each node's and their
neighbors' sensitive attributes. Then we enforce fairness by minimizing the
discrepancy between the representations learned from the original graph and the
counterfactuals for each node. Experiments on both synthetic and real-world
graphs show that our framework outperforms the state-of-the-art baselines in
graph counterfactual fairness, and also achieves comparable prediction
performance.
