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

arXiv: https://arxiv.org/abs/2603.03867 · HTML: https://mlsanity.com/paper/2603.03867/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 4 Mar 2026.

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [A Clarification of the Nuances in the Fairness Metrics Landscape](https://mlsanity.com/paper/2106.00467/) (2021)
- [EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks](https://mlsanity.com/paper/2108.05233/) (2021)
- [DeBayes: a Bayesian Method for Debiasing Network Embeddings](https://mlsanity.com/paper/2002.11442/) (2020)
- [All of the Fairness for Edge Prediction with Optimal Transport](https://mlsanity.com/paper/2010.16326/) (2020)
- [CrossWalk: Fairness-enhanced Node Representation Learning](https://mlsanity.com/paper/2105.02725/) (2021)
- [Unbiased Graph Embedding with Biased Graph Observations](https://mlsanity.com/paper/2110.13957/) (2021)
- [Fairness-Aware Graph Neural Networks: A Survey](https://mlsanity.com/paper/2307.03929/) (2023)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [Modeling echo chambers and polarization dynamics in social networks](https://mlsanity.com/paper/1906.12325/) (2019)
- [Graph Learning with Localized Neighborhood Fairness](https://mlsanity.com/paper/2212.12040/) (2022)
- [Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction](https://mlsanity.com/paper/2309.17417/) (2023)
- [FairMILE: Towards an Efficient Framework for Fair Graph Representation Learning](https://mlsanity.com/paper/2211.09925/) (2022)
- [Structural Group Unfairness: Measurement and Mitigation by means of the Effective Resistance](https://mlsanity.com/paper/2305.03223/) (2023)
- [Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity](https://mlsanity.com/paper/2511.06568/) (2025)
- [Structural Bias Beyond Homophily: A Study of Fairness in Link Prediction](https://mlsanity.com/paper/2602.11802/) (2026)

## Abstract (arXiv)

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.