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

Computer Science > Machine Learning arXiv:2603.03867 (cs) [Submitted on 4 Mar 2026] Title:k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods Authors:Lilian Marey, Tiphaine Viard, Charlotte Laclau View a PDF of the paper titled k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods, by Lilian Marey and 2 other authors View PDF HTML (experimental) 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 ...