FairProp: Fair Node Representation Learning via Differentiable Propagation Layers

Abstract

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.

Why FairProp?

Parity Bounds for Three Tasks

We bound the demographic parity gap of the deployed prediction for node classification, link prediction and node regression, for any number of groups. The bounds reveal two sources of bias: the gap between group means and the spread within each group.

Fairness During Propagation

Each FairProp layer is an APPNP propagation step followed by a closed-form projection that equalizes the group means. The layers converge linearly to the unique fair optimum, and the projection costs $O(nd)$.

What It Means in Practice

Three real decisions from the benchmarks, sentencing risk, citation suggestions and credit scoring, explained without equations, with the measured results before and after.

Strong Empirical Results

Against 18 fairness-aware baselines, FairProp gives the lowest parity gap on all four classification benchmarks, link-prediction gaps of at most 0.003, and exactly zero mean gap in regression.

What Goes Wrong, and What FairProp Changes

Many AI systems learn from networks: people linked to similar people, papers linked to the papers they cite. In such networks, like connects with like. A standard graph model shares information between neighbours, so a person's predicted outcome starts to depend on which group their neighbours belong to. FairProp adds one step each time neighbours share information: it moves each group's average back to the same place. Below are three real datasets from the paper, with the measured results before and after.

Every number comes from the paper's tables, averaged over 20 runs. The squares are those numbers rescaled to 1,000 people or pairs.

Criminal justiceClassify a person

Who is predicted to re-offend?

A risk tool predicts whether each of 6,172 defendants will commit another crime. Defendants are linked when their criminal records look alike. The two groups are Black and white defendants. Links run largely within each group, so a standard model's predictions end up tracking race.

How differently are Black and white defendants treated?

extra people flaggedeach square is one person out of 1,000

Predictions that turn out correct

Recidivism dataset · node classification · demographic parity gap 18.4 → 3.5 points (Table 1)

Research toolsSuggest a link

Which papers should you read next?

A literature tool suggests which of 19,717 medical papers should cite each other. The two groups are papers on Type 1 diabetes and papers on Type 2 or experimental diabetes, and most citations stay inside a group. A standard model learns that habit and keeps suggesting same-group papers, so readers rarely see the other group's work. Friend suggestions on social networks create echo chambers the same way.

How strongly does the model favour same-group suggestions?

extra same-group linkseach square is one pair out of 1,000

Real citation ranked above a random non-citation

Pubmed dataset · link prediction · groups from topic class parity, a proxy attribute · dyadic parity gap 0.081 → 0.003 (Table 2)

LendingEstimate a number

What credit score does each applicant get?

A bank estimates a credit score for each of 1,000 loan applicants. Applicants are linked when their financial profiles are similar, and similar profiles often share a gender. The two groups are male and female applicants. A standard model's scores drift apart by gender as a result.

How far apart are the average scores of male and female applicants?

Typical error of a predicted score

German Credit dataset · node regression · mean parity gap 0.089 → 0.000 (Table 3)

Two Sources of Bias, Three Tasks

We bound the parity gap of each task's deployed prediction using two properties of the final embeddings: $\delta$, the largest distance between group means, and $\mathbf{C}_k$, the covariance within each group $k$. The bounds hold for any number of sensitive groups.

mean-gap termwithin-group variance term

Node classification Prop. 2

Softmax readout $\sigma(\mathbf{W}\mathbf{h} + \mathbf{b})$, $L$-Lipschitz

$$\Delta_{\mathrm{DP}} \le L\Big(\class{t-delta}{\|\mathbf{W}\|_2\,\delta} + \class{t-var}{2\max_k \sqrt{\mathrm{tr}(\mathbf{W}\mathbf{C}_k\mathbf{W}^\top)}}\Big)$$

The nonlinearity adds a variance term.

No looser than the FairGAT bound whenever the graph has at least as many nodes as classes. On the four benchmarks it is 10–21× tighter (Fig. 10).

Link prediction Prop. 5

Sigmoid of a bilinear score $\sigma(\mathbf{h}_u^\top \boldsymbol{\Sigma} \mathbf{h}_v)$

$$\Delta_{\mathrm{DP}}^{\mathrm{LP}} \le LQ\|\boldsymbol{\Sigma}\|_2\Big(\class{t-delta}{2\delta} + \class{t-var}{\textstyle\sum_k (2\alpha_k + w_k)\sqrt{\mathrm{tr}\,\mathbf{C}_k}}\Big)$$

The nonlinearity adds a variance term.

Bounds the sigmoid probability that is actually deployed and evaluated, where earlier results bounded the pre-activation score.

Node regression Prop. 6

Linear readout $\hat{y} = \mathbf{W}\mathbf{h} + \mathbf{b}$, mean parity gap $\Delta_{\mathrm{MG}}$

$$\Delta_{\mathrm{MG}} \le \class{t-delta}{\|\mathbf{W}\|_2\,\delta}$$

One term. Removing the mean gap removes the whole bound.

The first parity bound for node regression. FairProp's mean gap is 0.000 on all three datasets in Table 3.

Equal means are not the end of the story

Both groups share the same mean, so $\delta = 0$. When one group is more spread out, a ring-shaped boundary still tells them apart, and a nonlinear readout can pick that up (Fig. 3).

Spread ratio, minority ÷ majority 2.5×

–

accuracy of the best circular boundary at recovering the group (50% is chance)

FairProp handles the mean term exactly with the projection. For the variance term it adds an optional regularizer $\lambda\,\mathrm{tr}(\mathbf{H}^\top\mathbf{M}\mathbf{H})$ inside the propagation objective. In practice the projection alone already gives the headline numbers.

The FairProp Layer

Let $\mathbf{H}^{(0)} = g_\theta(\mathbf{X})$ be the output of an MLP on the node features and $\mathbf{S} = \mathbf{D}^{-1/2}(\mathbf{A}+\mathbf{I})\mathbf{D}^{-1/2}$, with Laplacian $\mathbf{L}_S = \mathbf{I} - \mathbf{S}$. APPNP's propagation layers are gradient steps on the strongly convex feature-smoothing problem

\min_{\mathbf{H}} \; f(\mathbf{H}) := \tfrac{1}{2}\gamma\,\|\mathbf{H}-\mathbf{H}^{(0)}\|_F^2 + \tfrac{1}{2}(1-\gamma)\,\mathrm{tr}(\mathbf{H}^\top \mathbf{L}_S \mathbf{H}).

FairProp adds a convex constraint that equalizes the group means and an optional within-group variance penalty $\lambda\,\mathrm{tr}(\mathbf{H}^\top\mathbf{M}\mathbf{H})$, then unrolls projected gradient descent. Each layer is the familiar APPNP update followed by a closed-form projection $\mathbf{P}$:

\mathbf{H}^{(t+1)} = \mathbf{P}\big[(1-\gamma)\,\mathbf{S}\mathbf{H}^{(t)} + \gamma\,\mathbf{H}^{(0)} - 2\lambda\,\mathbf{M}\mathbf{H}^{(t)}\big], \qquad (\mathbf{P}\mathbf{H})_v = \mathbf{h}_v + \bar{\mathbf{h}} - \bar{\mathbf{h}}_{S_k} \;\; \forall v \in S_k.

Every node embedding is shifted by the difference between the global mean and its own group's mean, so all group means coincide after each layer.

Figure 1. The fairness lives entirely in the propagation block, so any readout downstream inherits it. With $\lambda = 0$ the layer has no extra parameters.

Exact and Cheap

The projection is linear and symmetric, so the backward pass is the same operation. It costs $O(nd)$, less than a single propagation step.

Provably Convergent

The layers converge linearly to the unique optimum of the constrained problem (Prop. 7). At APPNP's step size this holds for any $\lambda < \lambda^* = \gamma\, n_{\min}/2$.

Project Every Layer, Not Once

A single final projection moves every node in a group by the same amount, so the minority absorbs most of the shift (Remark 16). Projecting at every step gives the smoothest representation with equal means, and the correction diffuses through the graph (Theorem 14).

A Tunable Tolerance

Replacing the exact constraint with a slab of width $\delta$ gives a ReLU-like layer. Up to about $\delta = 10^{-2}$ results barely move; on GermanCredit regression, relaxing recovers MAE from 0.481 to 0.448 (App. G.3).

Watch a Fair Layer at Work

A small graph with a minority of 40 nodes and a majority of 240, as in Figs. 4 and 5 of the appendix. A few minority nodes are bridges with many edges into the majority; the rest barely touch it. Each node starts with a one-dimensional score and the layers propagate it. A toy decision rule then approves every node whose score clears a threshold.

Same-group edges 90%

Teleport $\gamma$ 0.10

Layers $T$ 10

FAIRPROP ONLY

Tolerance $\delta$ 0

Variance weight $\lambda/\lambda^*$ 0

Node scores after layer 10

dashed line: approval threshold τ

Who gets moved

dot size: shift relative to plain APPNP

minoritymajoritybridge node

after layer 10

Group-mean gap $\delta$–

Spread, ±1σ min. / maj.–

Approval rate min. / maj.–

Parity gap $\Delta_{\mathrm{DP}}$–

Avg. shift, minority bridge / core–

Compare Project once with FairPropBoth close the mean gap exactly. Projecting once moves every minority node by the same amount, so the minority keeps its wide spread and approval rates still differ. FairProp's shifts follow the graph: core nodes move further than bridge nodes, and the minority spread shrinks.

Raise the share of same-group edgesUnder APPNP the gap between group means grows, because propagation keeps each group's signal circulating inside the group. This is the topology bias FairProp removes.

Open the tolerance $\delta$The projection becomes a slab: the gap settles at exactly $\delta$. Like a ReLU, the layer leaves features inside the slab untouched and only pulls violating ones back to its edge.

This is a toy simulation with one feature and no training, written to show the mechanism. Its numbers are not results from the paper.

Empirical Results

Node classification

5–33× smaller gap

Lowest demographic parity gap on all four benchmarks (tied with FairSAD on Credit), at most 0.4 points of accuracy below APPNP.

Link prediction

≤ 0.003 parity gap

7–27× below APPNP while keeping over 98% of its AUC on Cora, Citeseer and Pubmed.

Node regression

0.000 mean gap

Exactly zero on every dataset, as the linear-readout bound predicts. MAE matches APPNP on both Pokec graphs.

We compare against 18 fairness-aware baselines. Pick a task and dataset: points toward the top left are better on both axes, and the arrow shows what adding the projection does to APPNP. All numbers are means over 20 runs, from Tables 5 to 7.

BibTeX

@article{kariotakis2026fairprop,
  title={FairProp: Fair Node Representation Learning via Differentiable Propagation Layers},
  author={Kariotakis, Emmanouil and Konar, Aritra},
  journal={arXiv preprint arXiv:2610.06484},
  year={2026}
}

TL;DR