FairProp: Fair Node Representation Learning via Differentiable Propagation Layers

Graph neural networks (GNNs) are the standard for node representation learning and are increasingly deployed in high-stakes domains. However, the message-passing backbone of GNNs can amplify topological bias, raising concerns about the fairness of their predictions. We study group fairness at the level of downstream predictions, spanning node classification, link prediction, and node regression, and derive bounds on the demographic parity gap for any number of sensitive groups. For node classification, our bound is provably no looser than the closest prior bound; for link prediction, we are the first to bound the parity gap of the deployed, sigmoid-activated prediction rather than a pre-activation proxy; and for node regression, we establish the first such bound. Common to all three tasks, our analysis reveals two distinct sources of bias: the separation between group means and the within-group covariance of the final representations. Guided by this analysis, we embed fairness directly into the propagation mechanism by augmenting the convex feature-smoothing problem solved by APPNP with a convex constraint on the group-mean gap and a within-group covariance regularizer. Unfolding projected gradient descent on this problem yields FairProp, whose layers consist of a propagation step followed by a closed-form projection, and which provably converges linearly to the unique fair optimum. Across three tasks, we empirically demonstrate that FairProp, even with exact group-mean equalization, provides a strong inductive bias that attains excellent fairness-utility trade-offs relative to prevailing baselines on benchmark datasets.