Search papers, labs, and topics across Lattice.
This paper introduces $k$-hop fairness, a novel structural fairness notion for link prediction that considers disparities based on the distance ($k$-hops) between nodes in a graph, addressing limitations of dyadic fairness which only considers direct connections. The authors formalize this concept with predictive fairness and structural bias metrics, and propose both pre- and post-processing mitigation strategies to address the identified biases. Experiments on standard link prediction benchmarks demonstrate the prevalence of structural biases at varying $k$-hops and show that the proposed post-processing method achieves better performance-fairness trade-offs compared to existing methods.
Link prediction models amplify structural biases beyond immediate connections, but a new $k$-hop fairness approach can mitigate these disparities with favorable performance trade-offs.
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.
