k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods

Lilian Marey; Tiphaine Viard; Charlotte Laclau

cs.LGMar 4, 2026

k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods

Authors: Lilian Marey, Tiphaine Viard, Charlotte Laclau

Organizations: LTCI, T´el´ecom Paris - Deezer Research · i3, T´el´ecom Paris · LTCI, T´el´ecom Paris

Abstract

Link prediction (LP) plays a central role in graph-based applications, particularly in social recommendation. However, real-world graphs often reflect structural biases, most notably homophily, the tendency of nodes with similar attributes to connect. While this property can improve predictive performance, it also risks reinforcing existing social disparities. In response, fairness-aware LP methods have emerged, often seeking to mitigate these effects by promoting inter-group connections, that is, links between nodes with differing sensitive attributes (e.g., gender), following the principle of dyadic fairness. However, dyadic fairness overlooks potential disparities within the sensitive groups themselves. To overcome this issue, we propose $k$ -hop fairness, a structural notion of fairness for LP, that assesses disparities conditioned on the distance between nodes in the graph. We formalize this notion through predictive fairness and structural bias metrics, and propose pre- and post-processing mitigation strategies. Experiments across standard LP benchmarks reveal: (1) a strong tendency of models to reproduce structural biases at different $k$ -hops; (2) interdependence between structural biases at different hops when rewiring graphs; and (3) that our post-processing method achieves favorable $k$ -hop performance-fairness trade-offs compared to existing fair LP baselines.

Figures & tables

Figure 1: In this example, nodes A and B are segregated within a cluster of blue nodes. While a dyadic view would produce likely inter-edges (typically between nodes with shared neighbors around node C),

k

-hop fairness allows specifying the order at which fairness is desired (here,

k=3

), enabling connections to the segregated part.

Panel of Figure 2 — Figure 2: Comparison between graph structural bias and classical LP models $k$ -hop fairness across meaningful hops.

Panel of Figure 3 — Figure 3: Influence of $NB^{(k)}$ minimization via edge addition on structural bias at other hops. All p-values reported were found to be below 0.01, indicating statistical significance. The evolution of biases over iterations is shown in Supplementary E.2. For some target $k$ , the optimization process did not identify edges that reduce bias, these cases were excluded from the analysis.

Panel of Figure 4 — Figure 4: AUC vs $NF^{(k)}$ plot for base and fairness-aware GNN-based baselines and for targeted $k$ values. Our post-processing results are shown through arrows from base models. The star marker denotes the hypothetical model achieving the best AUC and the best $NF^{(k)}$ across baselines. Only baselines with AUC $>0.55$ are displayed. The outcome of our post-processing approach on the base models are represented with an arrow. Figure (d) shows $\alpha$ effect in the post-processing method for SAGE predictions.

Appendix figures & tables22 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Sensitive star graph with

n=12

and

p=\frac{2}{3}

Figure 6: Toy graphs (a), (b), (c) (left to right) with constant assortativity. Node colors represent sensitive attributes and the dotted lines represent different edge prediction sets according to color.

Toy Graph	$a$	$NB^{(1)}$	$NB^{(2)}$	$NB^{(3)}$
(a)	$\sim\frac{1}{n}$	$\sim\frac{1}{n^{2}}$	$\sim\frac{1}{n}$	$0$
(b)	$\sim\frac{1}{n}$	$\sim\frac{1}{2}$	$\sim\frac{1}{n}$	$\sim 1$
(c)	$\sim\frac{1}{n}$	$\sim\frac{1}{4}$	$\sim\frac{1}{2}$	$\sim\frac{1}{2}$

Appendix

Table 1: Asymptotic assortativity and

NB^{(k)}

for

k\in\{1,2,3\}

when

n\rightarrow\infty

for the three presented toy graphs.

Metric	Polblogs	Facebook	Pokec	Citeseer	Synthetic
# Nodes	1,222	1,034	2,779	3,264	950
# Edges	16,714	26,749	22,650	4,536	9,496
% Sensitive nodes	48	15	34	33	32 / 16
Density	0.022	0.050	0.006	0.001	0.021
$NB^{(1)}$ Compute Time (s)	0.088	0.053	0.797	1.149	0.071
$NB^{(2)}$ Compute Time (s)	0.130	0.085	0.872	1.148	0.093

Appendix

Table 2: Compute time (in seconds) for different

NB^{(k)}

across datasets and for

k

in meaningful hop set

\mathcal{K}

, with recursive method. Compute time are averaged over 10 iterations.

Figure 7: Comparison between graph structural bias and classical LP models

k

-hop fairness across meaningful hops for Synthetic dataset.

Figure 8: Influence of $NB^{(k)}$ minimization via edge addition on structural bias at other hops for Synthetic dataset.

Panel of Figure 9 — Figure 9: Evolution of structural bias across edge addition rewiring for several values of targeted $k$ for Polblogs , Facebook and Synthetic datasets. Bias values are normalized (divided by original value) to increase readability.

Panel of Figure 10 — Figure 10: Evolution of structural bias across edge addition rewiring for several values of targeted $k$ for Pokec dataset. Bias values are normalized (divided by original value) to increase readability.

Panel of Figure 11 — Figure 11: Evolution of structural bias across edge addition rewiring for several values of targeted $k$ for Citeseer dataset. Bias values are normalized (divided by original value) to increase readability.

Dataset	$k$	$\Delta NF^{(k)}$	$\Delta AUC$	$\Delta DP$	$\Delta EO$
Polblogs	$1$	-0.46 ± 0.01	0.00 ± 0.00	-0.00 ± 0.00	-0.00 ± 0.00
	$2$	-0.25 ± 0.01	-0.28 ± 0.01	-0.07 ± 0.03	0.31 ± 0.04
	$4$	-0.17 ± 0.01	-0.00 ± 0.00	0.05 ± 0.00	0.00 ± 0.00
Facebook	$1$	-0.07 ± 0.00	0.00 ± 0.00	0.00 ± 0.00	-0.00 ± 0.00
	$2$	-0.03 ± 0.00	-0.00 ± 0.00	0.02 ± 0.00	0.04 ± 0.00
	$6$	-0.01 ± 0.01	0.00 ± 0.00	0.00 ± 0.00	-0.00 ± 0.00

Appendix

Table 3: Effects of our post-processing method on dyadic fairness metrics DP, EO, performance AUC and targeted

k

-hop metrics on GCN base model (average ± standard deviation).

Panel of Figure 12 — Figure 12: AUC vs $NF^{(k)}$ plot for base and fairness-aware baselines and for targeted $k$ values. Our post-processing results are shown through arrows from base models. The star marker denotes the hypothetical model achieving the best AUC and the best $NF^{(k)}$ across baselines. Only baselines with AUC $>0.55$ are displayed.

Panel of Figure 13 — Figure 13: $\alpha$ effect on $NF^{(k)}$ and $AUC$ in the post-processing method for SAGE predictions (log-scale for x-axis).

Panel of Figure 14 — Figure 14: AUC vs $NF^{(k)}$ plot for base and fairness-aware baselines and for targeted $k$ values. Our post-processing results are shown through arrows from base models. The star marker denotes the hypothetical model achieving the best AUC and the best $NF^{(k)}$ across baselines. Only baselines with AUC $>0.55$ are displayed.

Panel of Figure 15 — Figure 15: $\alpha$ effect on $NF^{(k)}$ and $AUC$ in the post-processing method for SAGE predictions (log-scale for x-axis).

Panel of Figure 16 — Figure 16: AUC vs $NF^{(k)}$ plot for base and fairness-aware baselines and for targeted $k$ values. Our post-processing results are shown through arrows from base models. The star marker denotes the hypothetical model achieving the best AUC and the best $NF^{(k)}$ across baselines. Only baselines with AUC $>0.55$ are displayed.

Panel of Figure 17 — Figure 17: $\alpha$ effect on $NF^{(k)}$ and $AUC$ in the post-processing method for SAGE predictions (log-scale for x-axis).

Panel of Figure 18 — Figure 18: AUC vs $NF^{(k)}$ plot for base and fairness-aware baselines and for targeted $k$ values. Our post-processing results are shown through arrows from base models. The star marker denotes the hypothetical model achieving the best AUC and the best $NF^{(k)}$ across baselines. Only baselines with AUC $>0.55$ are displayed.

Panel of Figure 19 — Figure 19: $\alpha$ effect on $NF^{(k)}$ and $AUC$ in the post-processing method for SAGE predictions (log-scale for x-axis).

Panel of Figure 20 — Figure 20: AUC vs $NF^{(k)}$ plot for base and fairness-aware baselines and for targeted $k$ values. Our post-processing results are shown through arrows from base models. The star marker denotes the hypothetical model achieving the best AUC and the best $NF^{(k)}$ across baselines. Only baselines with AUC $>0.55$ are displayed.

Panel of Figure 21 — Figure 21: $\alpha$ effect on $NF^{(k)}$ and $AUC$ in the post-processing method for SAGE predictions (log-scale for x-axis).

Dataset	Model	$NF^{(1)}$	$NF^{(2)}$	$NF^{(3)}$	$NF^{(4)}$	$NF^{(5)}$	$NF^{(6)}$	DP	EO	AUC
Polblogs	N2V	0.62 ± 0.01	0.35 ± 0.01	0.07 ± 0.01	0.05 ± 0.01	0.07 ± 0.04	0.08 ± 0.06	0.35 ± 0.02	0.26 ± 0.02	0.76 ± 0.01
	GCN	0.56 ± 0.01	0.29 ± 0.01	0.12 ± 0.01	0.22 ± 0.01	0.12 ± 0.06	0.12 ± 0.08	0.20 ± 0.02	0.09 ± 0.03	0.89 ± 0.00
	SAGE	0.55 ± 0.02	0.29 ± 0.03	0.11 ± 0.03	0.19 ± 0.02	0.12 ± 0.05	0.06 ± 0.04	0.18 ± 0.05	0.06 ± 0.04	0.84 ± 0.01
	CrossWalk	0.52 ± 0.01	0.29 ± 0.01	0.07 ± 0.01	0.18 ± 0.01	0.06 ± 0.01	0.12 ± 0.05	0.13 ± 0.01	0.11 ± 0.01	0.68 ± 0.01
	DeBayes	0.56 ± 0.00	0.41 ± 0.00	0.11 ± 0.00	0.04 ± 0.01	0.07 ± 0.06	0.10 ± 0.11	0.42 ± 0.01	0.33 ± 0.01	0.73 ± 0.00
	EDITS	0.77 ± 0.01	0.47 ± 0.00	0.30 ± 0.00	0.39 ± 0.00	0.09 ± 0.00	0.16 ± 0.01	0.06 ± 0.00	0.01 ± 0.01	0.66 ± 0.01

Appendix

Table 4: Comparison of model performance on Polblogs , Facebook , and Pokec datasets, highlighting best scores. For our methods, we report only the post-processing variant applied to the LP model yielding the best results. Presented scores are averaged over 10 iterations with different train/test split random seeds, standard deviation being displayed next to averaged values.

Dataset	Model	$NF^{(1)}$	$NF^{(2)}$	$NF^{(3)}$	$NF^{(4)}$	$NF^{(5)}$	$NF^{(6)}$	DP	EO	AUC
Citeseer	N2V	0.50 ± 0.01	0.39 ± 0.01	0.28 ± 0.02	0.18 ± 0.02	0.10 ± 0.02	0.05 ± 0.01	0.17 ± 0.03	0.08 ± 0.05	0.74 ± 0.02
	GCN	0.50 ± 0.01	0.35 ± 0.01	0.24 ± 0.00	0.19 ± 0.00	0.14 ± 0.00	0.10 ± 0.00	0.05 ± 0.01	0.04 ± 0.03	0.63 ± 0.01
	SAGE	0.52 ± 0.01	0.38 ± 0.01	0.25 ± 0.01	0.19 ± 0.00	0.15 ± 0.00	0.10 ± 0.00	0.06 ± 0.01	0.05 ± 0.02	0.60 ± 0.02
	CrossWalk	0.30 ± 0.00	0.26 ± 0.00	0.22 ± 0.00	0.18 ± 0.00	0.14 ± 0.00	0.10 ± 0.00	0.00 ± 0.00	0.00 ± 0.00	0.52 ± 0.02
	DeBayes	0.49 ± 0.01	0.40 ± 0.01	0.32 ± 0.01	0.24 ± 0.01	0.17 ± 0.02	0.11 ± 0.01	0.19 ± 0.02	0.13 ± 0.04	0.79 ± 0.01
	EDITS	0.31 ± 0.00	0.27 ± 0.00	0.23 ± 0.00	0.19 ± 0.00	0.15 ± 0.00	0.10 ± 0.00	0.00 ± 0.00	0.01 ± 0.01	0.49 ± 0.01

Appendix

Table 5: Comparison of model performance on Citeseer , and Synthetic datasets, highlighting best scores. For our methods, we report only the post-processing variant applied to the LP model yielding the best results. Presented scores are averaged over 10 iterations with different train/test split random seeds, standard deviation being displayed next to averaged values.

Link Prediction

Link prediction estimates missing or future relationships in graphs, from social ties and knowledge-graph facts to biological interactions.

See all 46 papers

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study
Aug 10, 2026Valentijn Oldenburg, Floris de Kam, Stef de Wildt +1Learning to Rank Link Prediction
University of Amsterdam
FairProp: Fair Node Representation Learning via Differentiable Propagation Layers
Oct 5, 2026Emmanouil Kariotakis, Aritra KonarGraph Neural Networks Graph Representation Learning
Department of Electrical Engineering (ESAT-STADIUS), KU Leuven, Belgium
Investigating the Effect of k-NN Preprocessing on Developing Graph Neural Networks: A Fairness-Based Perspective
Sep 27, 2026Nikolaos Zafeiropoulos, Emmanouil Mavrikos, George E. TsekourasGraph Neural Networks Algorithmic Fairness
Department of Cultural Technology and Communication University of the Aegean Mytilene, Greece

Aug 10, 2026J/K move · Enter open · S save

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Valentijn Oldenburg, Floris de Kam, Stef de Wildt, Jarno Nilson Balk

University of Amsterdam

Learning to Rank Link Prediction Algorithmic Fairness Group Fairness

Open paper AskPDF arXiv

In fair ranked link prediction, demographic parity (

Δ_\mathrm{DP}

) is a common fairness metric. Yet, Mattos et al. (2025) argue that it fails to detect exposure bias because it ignores where links appear in the ranking. In this study, we reproduce this claim by showing that

Δ_\mathrm{DP}

can indicate aggregate parity even when some subgroup-pair links are systematically ranked lower than others. The proposed rank-aware Normalized Discounted KL-divergence (NDKL), however, does detect such disparities. We also reproduce the effectiveness of MORAL, a post-processing method that improves exposure-based fairness while maintaining competitive utility. Beyond reproduction, we assess robustness using synthetic homophily settings, categorical sensitive attributes, and additional fairness and utility metrics, including subgroup-pair-adapted Attention-Weighted Rank Fairness (AWRF). Overall, our results show that exposure-based metrics uncover biases hidden by

Δ_\mathrm{DP}

and that MORAL reduces these biases with minimal utility loss across diverse settings and datasets. We release a corrected, reproducible implementation at https://github.com/Floris93100/reproducing-MORAL.

Abstract

Link Prediction

Explore similar work

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

FairProp: Fair Node Representation Learning via Differentiable Propagation Layers

Investigating the Effect of k-NN Preprocessing on Developing Graph Neural Networks: A Fairness-Based Perspective