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

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.

• Publication year

  2026

• Venue

  Unknown venue

• Publication date

  2026-03-04

• Fields of study

  Computer Science

• Identifiers
  arXiv 2603.03867
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• TopoFair: Linking Topological Bias to Fairness in Link Prediction Benchmarks

  2026cited by this paper
• Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity

  2025cited by this paper
• Link Prediction Without Learning

  2024cited by this paper
• Structural Group Unfairness: Measurement and Mitigation by Means of the Effective Resistance

  2023cited by this paper
• Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction

  2023cited by this paper
• Fairness-Aware Graph Neural Networks: A Survey

  2023cited by this paper
• Learning Fair Graph Representations via Automated Data Augmentations

  2023cited by this paper
• FairLP: Towards Fair Link Prediction on Social Network Graphs

  2022cited by this paper
• Graph Learning with Localized Neighborhood Fairness

  2022cited by this paper
• FairMILE: Towards an Efficient Framework for Fair Graph Representation Learning

  2022cited by this paper
• A Survey on Fairness for Machine Learning on Graphs

  2022cited by this paper
• On Dyadic Fairness: Exploring and Mitigating Bias in Graph Connections

  2021cited by this paper
• A clarification of the nuances in the fairness metrics landscape

  2021cited by this paper
• Unbiased Graph Embedding with Biased Graph Observations

  2021cited by this paper
• EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks

  2021influential reference
• CrossWalk: Fairness-enhanced Node Representation Learning

  2021cited by this paper
• Bursting the Filter Bubble: Fairness-Aware Network Link Prediction

  2020cited by this paper
• DeBayes: a Bayesian method for debiasing network embeddings

  2020cited by this paper
• On the Information Unfairness of Social Networks

  2020cited by this paper
• All of the Fairness for Edge Prediction with Optimal Transport

  2020cited by this paper
• Modeling echo chambers and polarization dynamics in social networks

  2019cited by this paper
• Fairwalk: Towards Fair Graph Embedding

  2019cited by this paper
• Inductive Representation Learning on Large Graphs

  2017cited by this paper
• Equality of Opportunity in Supervised Learning

  2016cited by this paper
• Semi-Supervised Classification with Graph Convolutional Networks

  2016cited by this paper
• node2vec: Scalable Feature Learning for Networks

  2016cited by this paper
• Homophily and the Glass Ceiling Effect in Social Networks

  2015cited by this paper
• {SNAP Datasets}: {Stanford} Large Network Dataset Collection

  2014cited by this paper
• CiteSeer x : A Scholarly Big Dataset

  2014cited by this paper
• Certifying and Removing Disparate Impact

  2014cited by this paper
• Learning Fair Representations

  2013cited by this paper
• The Filter Bubble: What the Internet Is Hiding from You

  2012cited by this paper
• Fairness through awareness

  2011cited by this paper
• The political blogosphere and the 2004 U.S. election: divided they blog

  2005cited by this paper
• Assortative mixing in networks.

  2002cited by this paper
• Algebraic Graph Theory

  2001influential reference
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper

• No citing papers are available for this paper.