Fair Graph Learning Needs Expressiveness: Rethinking Fairness from the Spectral Perspective
TL;DR
It is formally proved that GNN architectures lacking spectral expressiveness impose strict constraints on the representation space, so that harmful linear correlations between sensitive attributes and target prediction logits are preserved whenever a low-expressive backbone is paired with a debiasing operator acting within that backbone's representation space.
Abstract
Graph Neural Networks (GNNs) have achieved remarkable success, yet they are susceptible to encoding and amplifying societal biases. Current research in fair graph learning predominantly focuses on developing specialized debiasing techniques through input data preprocessing, training optimization, or model architecture modifications under the assumption that the GNN backbone is an interchangeable component capable of independently generating a debiased representation space. This paper revisits this prevalent paradigm by demonstrating that the expressiveness of backbone GNNs critically influences fairness outcomes. Through spectral-domain theoretical analysis, we establish the link between GNN expressiveness and the elimination of linear statistical bias. We formally prove that GNN architectures lacking spectral expressiveness impose strict constraints on the representation space, so that harmful linear correlations between sensitive attributes and target prediction logits are preserved whenever a low-expressive backbone is paired with a debiasing operator acting within that backbone's representation space. Universal spectral expressiveness is therefore a necessary condition for eliminating linear prediction-sensitive correlation in this family of methods, although it is not sufficient on its own. Driven by this finding, we propose a fair graph learning framework that pairs a universally expressive GNN backbone, utilizing powerful graph-wise filtering and node-wise signal transformation, with a lightweight linear decorrelation module operating in the logit space. Comprehensive evaluations on six real-world datasets show that FairFormer attains a strong accuracy–fairness trade-off and ranks as the best or near-best fairness method on most benchmarks. On Bail and Pokec_n, however, a linear decorrelation module alone does not dominate every baseline on every fairness metric. Our results are consistent with the necessity of spectral expressiveness for linear decorrelation of prediction and sensitive attributes, establishing expressiveness as a key design axis for trustworthy GNN design. Code is available at https://github.com/qslim/expressive-fair-learning.
