Balancing Fairness and Accuracy in Graph Learning via Fairness-Constrained Rewiring

Algorithmic fairness aims to ensure the safe and responsible use of machine learning tools in applications across domains. In graph learning, several “fair rewiring” approaches have been proposed that perturb edges in the input graph to mitigate feature and relational bias. However, these approaches can lead to a decrease in accuracy in downstream tasks. On the other hand, classical rewiring approaches improve accuracy by mitigating over-smoothing and over-squashing effects induced by the graph’s topology. In this work we show that those classical rewiring approaches reinforce existing topological biases and boost accuracy at the cost of fairness. We propose a novel fairness metric (topological bias) that allows for evaluating relational bias separately from feature bias. We then propose a fairness constraint that can be incorporated into classical rewiring techniques to mitigate topological bias. We show that the resulting fairness-constrained rewiring balances fairness and accuracy effectively in graph learning tasks.