Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity
João Mattos, Debolina Halder Lina, Arlei Silva · 2025
Read Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity by João Mattos, Debolina Halder Lina, Arlei Silva (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06568.txt.
Introduction
João Mattos, Debolina Halder Lina, and Arlei Silva argue that the standard fairness test for link prediction can hide the bias it claims to catch. Link prediction guesses which connections a network will form, feeding social recommendations and knowledge graph completion. The usual fairness rule balances predictions between within-group and across-group pairs, a dyadic view of demographic parity.
That framing can average away disparities hitting particular subgroups, and parity itself fits ranking tasks poorly. The authors formalize those limits and propose a richer evaluation framework. A light post-processing step with separate predictors for different link types then cuts bias while keeping accuracy, reaching leading fairness-utility trade-offs in their experiments.
Catalog record
| CREATOR | João Mattos, Debolina Halder Lina, Arlei Silva |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06568
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity João Mattos, Debolina Halder Lina, Arlei Silva Abstract Link prediction is a fundamental task in graph machine learning with applications ranging from social recommendation to knowledge graph completion. Fairness in this setting is critical, as biased predictions can exacerbate societal inequalities. Prior work adopts a dyadic definition of fairness, enforcing fairness through demographic parity between intra-group and inter-group link predictions. However, we show that this dyadic framing can obscure underlying disparities across subgroups, allowing systemic biases to go undetected. Moreover, we argue that demographic parity does not meet the desired properties for fairness assessment in ranking-based tasks such as link prediction. We formalize the limitations of existing fairness evaluations and propose a framework that enables a more expressive assessment. 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. 1 1 1 This paper has been accepted for publication at the AAAI Conference on Artificial Intelligence (AAAI 2026). Code — https://github.com/joaopedromattos/MORAL 1 Introduction Link prediction is the task of discovering potential missing or future links in a network. There is extensive literature on link prediction models ( 34 ; 59 ; 40 ; 62 ; 5 ) , which demonstrates the relevance of this task and the variety of domains where it can be applied, ranging from social networks to knowledge graphs. Among these domains, many types of networks are prone to biases in their structure and features ( 9 ; 46 ; 24 ) , requiring the adoption of fair machine learning methods to mitigate bias in model predictions ( 30 ; 32 ; 8 ; 48 ; 49 ) . Our work is focused on the fair link prediction problem and, more specifically, on the evaluation and design of link prediction models under fairness considerations. As a motivational example, consider the recommendation problem in social networks, where links represent social interactions. On a professional network, such as LinkedIn, biased connection recommendations can lead to persistent employment disparities between groups. Closed male networking circles provide more job leads and higher status connections than female/minority ones ( 3 ) , resulting in white women receiving 33% fewer job leads on average, according to some models ( 39 ) . In addition, bias in friendship can lead to long-term accumulation ( 20 ; 22 ) , with the large majority of links occurring only within the same communities, creating filter bubbles ( 6 ; 2 ) . The graph representation learning literature has focused on fair node representations ( 60 ; 61 ; 35 ; 1 ; 29 ) , and building upon these works, the current notion of fairness adopted by fair link prediction methods is dyadic ( 30 ; 8 ; 32 ; 36 ) . The main assumption behind dyadic fairness is to categorize groups according to a protected attribute of interest and obtain equalized positive outcomes across these groups. In the social network example, two communities can be identified (e.g., men and women), and we can define fairness as links between men and women (inter) having the same probability of occurring as links within these groups (intra). To mitigate the disparity between these probabilities, fair link prediction algorithms adopt different strategies, evaluated through group fairness statistical metrics ( 14 ; 28 ; 37 ) . However, we show that fair node embeddings do not translate to fair link prediction. The limited expressive power of Graph Neural Networks (GNNs), outputs indistinguishable node representations in symmetric neighborhoods containing different sensitive groups. This prevents the adoption of fair node embeddings in training objectives that distinguish between edge groups to achieve parity. In addition, the dyadic fairness applied by previous fair link prediction methods (e.g., intra vs. inter) is unable to capture biases that occur within sensitive groups of node pairs, which is known as fairness gerrymandering ( 25 ) . In the social network example, male-male connections might be systematically more likely than female-female connections, and the dyadic fairness evaluation metrics considered (in particular, demographic parity) are insensitive to this phenomenon, thereby masking underlying biases. The consequence of this limitation is a ”glass ceiling” effect ( 46 ) , in which an under-representation of a subgroup of pairs goes undetected. A third limitation of existing work on fair graph machine learning (including link prediction) is evaluating fairness as a subset selection problem, instead of based on ranking ( 21 ; 26 ; 45 ; 33 ) . We claim that by not considering the ranking of candidate links, a link prediction method can be prone to exposure bias . In this fashion, one key property of a fair link prediction algorithm should be to ensure equality of probabilities and exposure, preventing one group from dominating the top positions of the ranking. Our work is the first attempt at formalizing and demonstrating empirically the above limitations in the context of fair link prediction. To address these limitations, we propose using an exposure-based fairness evaluation metric previously applied in information retrieval ( 13 ) . Our experiments show that several existing approaches ( 41 ; 10 ; 35 ; 42 ; 53 ) fail at achieving a good tradeoff between accuracy and fairness under this evaluation metric. This motivates the design of a new post-processing algorithm that can be combined with any existing link prediction model to generate fair outcomes based on the new metric, outperforming existing alternatives. We summarize the contributions of this work as follows: (1) we expose the limitations of demographic parity as a fairness metric in the context of link prediction; (2) we propose using an exposure-based fairness metric that overcomes the limitations of demographic parity and show that existing approaches for fair link prediction are ineffective under the new metric; and (3) we introduce MORAL , a post-processing algorithm that can de-bias the outputs of any link prediction model and achieves good accuracy vs. fairness tradeoffs under the new evaluation metric. 2 Preliminaries Let a graph G=(V,E,S) , v\in V is the set of nodes, (u,v)\in E the set of existing edges in the graph, and S\in\{0,1\}^{n} is the vector of sensitive attributes, where s_{v} indicates the sensitive attribute of node v . In this work, we consider binary sensitive attributes for simplicity and the availability of datasets, but our analysis is also valid for categorical and/or multiple sensitive attributes. The binary sensitive attribute S produces three subgroups of node pairs, which for the remainder of the paper we denote as E_{s\text{-}{s^{\prime}}}=\{(u,v)\in V\times V\mid s_{u}=1,s_{v}=0\} , E_{s\text{-}s}=\{(u,v)\in V\times V\mid s_{u}=1,s_{v}=1\} , and E_{s^{\prime}\text{-}s^{\prime}}=\{(u,v)\in V\times V\mid s_{u}=0,s_{v}=0\} , for simplicity. We consider a link prediction classifier a score function f(\cdot,\cdot) that maps a given input pair (u,v) to a score \hat{Y}\in[0,1] . We denote the scores of all candidate pairs as R\in[0,1]^{|C|} , where C is the set of candidate pairs. Definition 1 (Demographic Parity - \Delta_{DP} ) . Let \hat{Y} be the prediction of a binary classifier. Demographic parity is defined as: |P(\hat{Y}\mid(u,v)\in E_{\text{intra}})-P(\hat{Y}\mid(u,v)\in E_{\text{inter}})|. In this scenario, we can define the objective of fair link prediction with an output R as \min_{R}\lambda\mathscr{L}_{A}(R) , where \mathscr{L}_{A} is an accuracy loss (usually Binary Cross Entropy),