FairProp: Fair Node Representation Learning via Differentiable Propagation Layers

Emmanouil Kariotakis; Aritra Konar

cs.LGOct 5, 2026

FairProp: Fair Node Representation Learning via Differentiable Propagation Layers

Authors: Emmanouil Kariotakis, Aritra Konar

Organizations: Department of Electrical Engineering (ESAT-STADIUS), KU Leuven, Belgium

Abstract

Graph neural networks (GNNs) are the standard tool for node representation learning and are increasingly used in high-stakes settings. Their message-passing backbone, however, can amplify topological bias, raising fairness concerns. We study group fairness at the level of downstream predictions for node classification, link prediction, and node regression, and bound the demographic parity gap for an arbitrary number of sensitive groups. Our node classification bound is provably no looser than the closest prior result. For link prediction, ours is the first bound on the parity gap of the deployed sigmoid-activated prediction rather than a pre-activation proxy, and for node regression we provide the first such bound. Across all three tasks, the analysis identifies two distinct sources of bias: the separation between group means and the within-group covariance of the final representations. Building on this insight, we embed fairness into propagation itself by augmenting the convex smoothing problem underlying APPNP with a convex group-mean constraint and a within-group covariance regularizer. Unfolding projected gradient descent on this problem yields FairProp, whose layers pair a propagation step with a closed-form projection and which provably converges linearly to the unique fair optimum. Experiments on three tasks show that FairProp, even with exact group-mean equalization alone, provides a strong inductive bias that achieves excellent fairness-utility trade-offs against strong baselines.

Figures & tables

Figure 1: FairProp Architecture

	Credit		Recidivism		Pokec-z		Pokec-n
	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$
APPNP	80.9 $\pm$ 0.2	3.5 $\pm$ 0.7	67.1 $\pm$ 0.2	18.4 $\pm$ 0.3 †	67.6 $\pm$ 0.6	5.2 $\pm$ 0.6	67.7 $\pm$ 0.6	6.6 $\pm$ 0.9
FairProp (proj)	80.8 $\pm$ 0.2	0.4 $\pm$ 0.3	66.8 $\pm$ 0.3	3.5 $\pm$ 0.4 †	67.2 $\pm$ 0.7	0.7 $\pm$ 0.3	67.3 $\pm$ 0.8	0.2 $\pm$ 0.2
FairGAT	79.4 $\pm$ 0.5	1.2 $\pm$ 0.3	67.8 $\pm$ 1.1	15.1 $\pm$ 0.5	69.4 $\pm$ 0.9	2.0 $\pm$ 1.2	68.6 $\pm$ 0.8	2.3 $\pm$ 3.0
FairVGNN	80.0 $\pm$ 0.3	0.8 $\pm$ 0.1	65.5 $\pm$ 2.3	19.5 $\pm$ 0.4	—	—	—	—
FMP	81.2 $\pm$ 0.1	3.5 $\pm$ 0.3	69.8 $\pm$ 0.3	19.1 $\pm$ 0.3	65.8 $\pm$ 0.4	3.9 $\pm$ 0.3	65.3 $\pm$ 0.5	1.7 $\pm$ 0.5

Table 1: Node classification results. Best and second best per column in bold and underlined , respectively, excluding APPNP. Dashed results indicate out-of-memory (OOM) or time-consuming experiments. All results are presented by

\times 100

. FairProp is always the best in terms of fairness and among the best in terms of accuracy.

	Cora		Citeseer		Pubmed
	AUC $\uparrow$	$\Delta^{\mathrm{LP}}_{\mathrm{DP}}$ $\downarrow$	AUC $\uparrow$	$\Delta^{\mathrm{LP}}_{\mathrm{DP}}$ $\downarrow$	AUC $\uparrow$	$\Delta^{\mathrm{LP}}_{\mathrm{DP}}$ $\downarrow$
APPNP	0.908 $\pm$ 0.007	0.031 $\pm$ 0.004	0.885 $\pm$ 0.009	0.014 $\pm$ 0.001	0.957 $\pm$ 0.002	0.081 $\pm$ 0.002
FairProp (proj)	0.897 $\pm$ 0.009	0.003 $\pm$ 0.001	0.875 $\pm$ 0.009	0.002 $\pm$ 0.000	0.942 $\pm$ 0.003	0.003 $\pm$ 0.001
EDITS	0.905 $\pm$ 0.008	0.009 $\pm$ 0.002	0.879 $\pm$ 0.007	0.008 $\pm$ 0.001	0.966 $\pm$ 0.001	0.028 $\pm$ 0.005
FairGAT	0.915 $\pm$ 0.006	0.050 $\pm$ 0.017	0.919 $\pm$ 0.007	0.027 $\pm$ 0.016	0.845 $\pm$ 0.017	0.066 $\pm$ 0.034
FairAdj	0.915 $\pm$ 0.006	0.019 $\pm$ 0.001	0.888 $\pm$ 0.006	0.013 $\pm$ 0.001	0.969 $\pm$ 0.001	0.050 $\pm$ 0.001

Table 2: Link prediction results. Best and second best per column in bold and underlined , respectively, excluding APPNP. FairProp yields the best utility-fairness trade-off, with near 0

\Delta^{\mathrm{LP}}_{\mathrm{DP}}

	GermanCredit		Pokec-z		Pokec-n
	MAE $\downarrow$	$\Delta_{\mathrm{MG}}$ $\downarrow$	MAE $\downarrow$	$\Delta_{\mathrm{MG}}$ $\downarrow$	MAE $\downarrow$	$\Delta_{\mathrm{MG}}$ $\downarrow$
APPNP	0.404 $\pm$ 0.035	0.089 $\pm$ 0.015	0.199 $\pm$ 0.001	0.091 $\pm$ 0.001 †	0.199 $\pm$ 0.001	0.152 $\pm$ 0.001 †
FairProp (proj)	0.481 $\pm$ 0.027	0.000 $\pm$ 0.000	0.200 $\pm$ 0.001	0.000 $\pm$ 0.000 †	0.199 $\pm$ 0.001	0.000 $\pm$ 0.000 †
FairGAT	0.442 $\pm$ 0.012	0.017 $\pm$ 0.012	0.652 $\pm$ 0.052	0.061 $\pm$ 0.007	0.654 $\pm$ 0.042	0.094 $\pm$ 0.008
EDITS	0.414 $\pm$ 0.013	0.024 $\pm$ 0.019	0.587 $\pm$ 0.004	0.006 $\pm$ 0.002	0.586 $\pm$ 0.005	0.020 $\pm$ 0.001
FairVGNN	0.407 $\pm$ 0.024	0.049 $\pm$ 0.021	—	—	—	—

Table 3: Node regression results. Best and second best per column in bold and underlined , respectively, excluding APPNP. FairProp is almost always the best in terms of both MAE and fairness.

Figure 2: The effect of variance regularization in link prediction.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Illustrative example showing that mean matching is not enough, and that variance can still result in discrimination of sensitive attributes.

Figure 4: Left: APPNP output

{\mathbf{y}}^{*}

with mean gap

\delta

. Middle: the Euclidean projection shifts each group uniformly, equalizing the means but preserving within-group spread. Right: FairProp shifts node

i

proportionally to

({\mathbf{Q}}^{-1}{\mathbf{a}})_{i}

, equalizing the means while also reducing within-group spread. Brackets: minority mean

\pm 2

std (

\gamma=0.1

\lambda=0

Figure 5: The simulated graph. Outlined minority nodes have edges to the majority; the remaining minority nodes have almost none.

Dataset	Task	Nodes	Edges	Features	Sensitive attr.	Target / Classes
Node Classification (NC)
Credit	NC	30,000	150,000	22	Age ( $>25$ )	2 classes
Recidivism	NC	6,172	30,860	7	Race	2 classes
Pokec-z	NC	67,796	617,958	276	Gender	2 classes
Pokec-n	NC	66,569	517,047	265	Gender	2 classes
Link Prediction (LP)

Appendix

Table 4: Datasets used in the experiments. Edges are counted without multiplicity (undirected). For node regression (NR) the Target column lists the predicted continuous quantity; for link prediction (LP) node classes are not used as a task label but are listed for reference.

Panel of Figure 6 — Figure 6: Showing the effect of relaxing the mean-gap $\delta$ by using the slab projection, on different tasks and datasets.

	Credit		Recidivism		Pokec-z		Pokec-n
	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$	Acc $\uparrow$	$\Delta^{\mathrm{NC}}_{\mathrm{DP}}$ $\downarrow$
APPNP	80.9 $\pm$ 0.2	3.5 $\pm$ 0.7	67.1 $\pm$ 0.2	18.4 $\pm$ 0.3 †	67.6 $\pm$ 0.6	5.2 $\pm$ 0.6	67.7 $\pm$ 0.6	6.6 $\pm$ 0.9
FairProp (proj)	80.8 $\pm$ 0.2	0.4 $\pm$ 0.3	66.8 $\pm$ 0.3	3.5 $\pm$ 0.4 †	67.2 $\pm$ 0.7	0.7 $\pm$ 0.3	67.3 $\pm$ 0.8	0.2 $\pm$ 0.2
FairGNN	79.9 $\pm$ 1.1	2.9 $\pm$ 1.9	54.0 $\pm$ 10.0	10.8 $\pm$ 7.6	53.9 $\pm$ 3.9	5.0 $\pm$ 3.3	52.8 $\pm$ 2.7	4.4 $\pm$ 4.8
NIFTY	80.2 $\pm$ 0.3	10.1 $\pm$ 0.4	68.1 $\pm$ 1.0	19.8 $\pm$ 0.5	65.5 $\pm$ 1.7	11.5 $\pm$ 3.1	64.7 $\pm$ 1.1	4.7 $\pm$ 3.2
RawlsGCN	79.6 $\pm$ 0.7	1.7 $\pm$ 0.7	67.9 $\pm$ 0.9	18.7 $\pm$ 1.1	57.1 $\pm$ 6.4	2.5 $\pm$ 4.5	54.5 $\pm$ 6.6	2.6 $\pm$ 4.7

Appendix

Table 5: Node classification results. Best and second best per column in bold and underlined , respectively, excluding the unfair baseline. Dashed results indicate out-of-memory (OOM) or time-consuming experiments. All results are presented by

\times 100

	Cora		Citeseer		Pubmed
	AUC $\uparrow$	$\Delta^{\mathrm{LP}}_{\mathrm{DP}}$ $\downarrow$	AUC $\uparrow$	$\Delta^{\mathrm{LP}}_{\mathrm{DP}}$ $\downarrow$	AUC $\uparrow$	$\Delta^{\mathrm{LP}}_{\mathrm{DP}}$ $\downarrow$
APPNP	0.908 $\pm$ 0.007	0.031 $\pm$ 0.004	0.885 $\pm$ 0.009	0.014 $\pm$ 0.001	0.957 $\pm$ 0.002	0.081 $\pm$ 0.002
FairProp (proj)	0.897 $\pm$ 0.009	0.003 $\pm$ 0.001	0.875 $\pm$ 0.009	0.002 $\pm$ 0.000	0.942 $\pm$ 0.003	0.003 $\pm$ 0.001
FairGNN	0.683 $\pm$ 0.070	0.008 $\pm$ 0.006	0.808 $\pm$ 0.041	0.019 $\pm$ 0.009	0.873 $\pm$ 0.065	0.007 $\pm$ 0.008
EDITS	0.905 $\pm$ 0.008	0.009 $\pm$ 0.002	0.879 $\pm$ 0.007	0.008 $\pm$ 0.001	0.966 $\pm$ 0.001	0.028 $\pm$ 0.005
FairEdit	0.799 $\pm$ 0.049	0.015 $\pm$ 0.010	0.808 $\pm$ 0.032	0.012 $\pm$ 0.004	0.914 $\pm$ 0.025	0.004 $\pm$ 0.004

Appendix

Table 6: Link prediction results. Best and second best per column in bold and underlined , respectively, excluding the unfair baseline.

	GermanCredit		Pokec-z		Pokec-n
	MAE $\downarrow$	$\Delta_{\mathrm{MG}}$ $\downarrow$	MAE $\downarrow$	$\Delta_{\mathrm{MG}}$ $\downarrow$	MAE $\downarrow$	$\Delta_{\mathrm{MG}}$ $\downarrow$
APPNP	0.404 $\pm$ 0.035	0.089 $\pm$ 0.015	0.199 $\pm$ 0.001	0.091 $\pm$ 0.001 †	0.199 $\pm$ 0.001	0.152 $\pm$ 0.001 †
FairProp (proj)	0.481 $\pm$ 0.027	0.000 $\pm$ 0.000	0.200 $\pm$ 0.001	0.000 $\pm$ 0.000 †	0.199 $\pm$ 0.001	0.000 $\pm$ 0.000 †
FairGNN	0.415 $\pm$ 0.016	0.070 $\pm$ 0.024	0.600 $\pm$ 0.021	0.100 $\pm$ 0.011	1.826 $\pm$ 5.353	0.453 $\pm$ 1.322
FairGAT	0.442 $\pm$ 0.012	0.017 $\pm$ 0.012	0.652 $\pm$ 0.052	0.061 $\pm$ 0.007	0.654 $\pm$ 0.042	0.094 $\pm$ 0.008
EDITS	0.414 $\pm$ 0.013	0.024 $\pm$ 0.019	0.587 $\pm$ 0.004	0.006 $\pm$ 0.002	0.586 $\pm$ 0.005	0.020 $\pm$ 0.001

Appendix

Table 7: Node regression results. Best and second best per column in bold and underlined , respectively, excluding the unfair baseline.

Figure 7: Runtime Results. OOT stands for Out-of-Time and OOM for Out-of-Memory.

Figure 8: Utility-fairness trade-off on node classification. Each point shows mean accuracy (higher is better) against

\Delta^{\text{NC}}_{\text{DP}}

(lower is better) over 20 runs. Top-left is optimal.

Figure 9: Utility-fairness trade-off on link prediction. Each point shows mean AUC (higher is better) against

\Delta^{\text{LP}}_{\text{DP}}

(lower is better) over 20 runs. Top-left is optimal.

Figure 10: Comparison of our bound on the soft prediction gap against that of FairGAT ( Kose and Shen, 2024a ) .

Explore similar work

Grad2Fair: A Gradient-driven Approach for Graph Fairness without Demographics
Jul 16, 2026Yuchang Zhu, Zezhong Xie, Huizhe Zhang +4Graph Neural Networks Algorithmic Fairness
School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510007, China · Institute of Artificial Intelligence, Xiamen University, Xiamen 361005, China · School of Software Engineering, Sun Yat-sen University, Zhuhai 519082, China
Causally Fair Node Classification on Non-IID Graph Data
May 3, 2025Yucong Dai, Lu Zhang, Yaowei Hu +2Structural Causal Models Graph Representation Learning
Clemson University · University of Arkansas · Walmart Inc.
Deep Fair Learning: Task-Aware Fair Representations via Joint Distance-Covariance Regularization
Apr 8, 2025Enze Shi, Yiqun Xiao, Linglong Kong +1Representation Learning Algorithmic Fairness
Department of Mathematical and Statistical Science, University of Alberta.

Jul 16, 2026, cs.LGJ/K move · Enter open · S save

Grad2Fair: A Gradient-driven Approach for Graph Fairness without Demographics

Yuchang Zhu, Zezhong Xie, Huizhe Zhang, Huazhen Zhong+3

School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510007, China · Institute of Artificial Intelligence, Xiamen University, Xiamen 361005, China · School of Software Engineering, Sun Yat-sen University, Zhuhai 519082, China

Graph Neural Networks Algorithmic Fairness Group Fairness

Open paper AskPDF arXiv

Graph neural networks (GNNs) frequently encounter group fairness issues, often yielding biased predictions against specific demographic groups defined by sensitive attributes such as gender or race. While this challenge has motivated extensive research, most existing solutions rely on the strong assumption that demographics are fully available. To bypass this strict requirement, a few recent studies have attempted to use predicted demographics as proxies to enforce fairness constraints. However, predicted demographics may be inaccurate, resulting in the failure to improve fairness. In this work, we investigate the problem of graph fairness without demographic information and avoid the utilization of predicted demographics. Motivated by our observation that the gradient distributions of misclassified nodes implicitly encode demographic information, we first propose GradDist, a gradient-based metric that quantifies bias by measuring the distance between local modes within these distributions. To mitigate this bias, we propose Gradient-to-Fairness (Grad2Fair), a gradient-guided approach for group fairness without demographics. Due to the potential demographics in gradients, Grad2Fair directly leverages gradients to debias and eliminates demographic prediction, thereby enabling stable fairness performance. Experiments on several real-world datasets demonstrate the effectiveness of Grad2Fair, as evidenced by superior performance over baselines in most cases. Our code is available at https://github.com/ZzoomD/Grad2Fair.

Abstract

Explore similar work

Grad2Fair: A Gradient-driven Approach for Graph Fairness without Demographics

Causally Fair Node Classification on Non-IID Graph Data

Deep Fair Learning: Task-Aware Fair Representations via Joint Distance-Covariance Regularization