Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity

Link prediction is a fundamental task in network analysis with widespread applications, from social recommendation to knowledge graph completion. Fairness in this setting is critical, as biased predictions can propagate or exacerbate societal inequalities. Prior work adopts a dyadic perspective, enforcing fairness through demographic parity between intra-group and inter-group link predictions. However, this dyadic framing can obscure underlying disparities across subgroups, allowing systemic biases to go undetected. Moreover, we argue that demographic parity does not meet desired properties for fairness assessment in ranking-based tasks such as link prediction. We formalize the limitations of existing fairness evaluations and borrow a framework inspired by information retrieval that enables a more expressive assessment, addressing these limitations. Additionally, we propose a lightweight post-processing method combined with decoupled link predictors that effectively mitigates bias and achieves state-of-the-art fairness–utility trade-offs.