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

AI summary

Overview

• Research area: Fairness in graph machine learning, specifically fair link prediction; intersections with fair ranking and information retrieval.
• Technical level: Intermediate. The paper assumes familiarity with graph neural networks, link prediction, and standard group-fairness metrics, but its central arguments are stated in plain terms and illustrated with toy examples.
• Scope: The paper formalizes why dyadic demographic parity is an inadequate fairness criterion for link prediction, proposes an exposure-based fairness metric (NDKL), and introduces a post-processing method called MORAL that improves fairness–utility trade-offs on six real-world graph datasets.

What This Paper Is About

Most prior fair link prediction work defines fairness in dyadic terms: it splits node pairs into intra-group pairs (both endpoints share a sensitive attribute) and inter-group pairs (endpoints differ) and enforces demographic parity between those two categories. The authors argue this two-category framing hides disparities that occur within the aggregated categories (for example, male–male links being systematically favored over female–female links), and that because demographic parity ignores ranking order it cannot detect exposure bias when only the top-ranked candidate links receive user attention. The paper's goal is to formalize these failure modes and provide both a better evaluation metric and a bias-mitigation method that any link predictor can be paired with.

Key Contributions

1. The authors expose the limitations of demographic parity as a fairness metric in link prediction, showing that it can mask subgroup bias (a phenomenon the paper connects to "fairness gerrymandering" and a "glass ceiling" effect) and that it is ranking-insensitive and permutation-invariant.
2. They propose using an exposure-based fairness metric, the Normalized Cumulative KL-Divergence (NDKL), which was previously applied in fair ranking, and show experimentally that existing fair link prediction approaches fail at achieving good accuracy–fairness trade-offs under it.
3. They introduce MORAL (Multi-Output Ranking Aggregation for Link fairness), a post-processing algorithm that decouples predictions by sensitive group and then greedily aggregates them into a single ranking whose group exposure approaches the original graph's distribution.
4. They formalize two desired properties for a link prediction fairness metric: Property 1 (Non-Dyadic Distribution-Preserving Fairness) and Property 2 (Rank awareness), and prove bounds on NDKL when the full ranking satisfies demographic parity.

Main Findings

• Dyadic fairness aggregates away real bias. The paper defines intra-pairs as $E_{s\text{-}s} \cup E_{s'\text{-}s'}$ and inter-pairs as $E_{s'\text{-}s}$, and shows with a toy example that two different top-10 rankings can achieve the same optimal demographic parity while one overrepresents $E_{s\text{-}s}$ relative to $E_{s'\text{-}s'}$. The metric $\Delta_{\text{max}}$ likewise fails to penalize subgroup-level disparities when the groupings ignore pairwise composition.
• Fair node embeddings do not translate into fair link predictions. Because most GNNs operate within the expressivity limits of the 1-WL test, they tend to produce similar embeddings for nodes in symmetric neighborhoods containing different sensitive groups, undermining training objectives that need to distinguish edge groups to achieve parity.
• Ranking order matters and demographic parity cannot see it. In the Section 5.2 experiment, the authors fix the proportions of each pair type at the values needed for optimal demographic parity, then consider the best and worst permutations in terms of NDKL, assuming all ranked pairs are positive so that prec@k = 100%. Despite the exposure difference between the best and worst rankings, demographic parity is unchanged.
• NDKL has provable bounds. Theorem 1 states that, when the full ranking satisfies demographic parity, $0 \leq \text{NDKL} \leq \max_{i \in {0,1,2}} \log \frac{1}{\pi_i}$ for a target distribution over 3 sensitive groups. The authors report that observed NDKL scores in controlled manipulation experiments consistently fall within these bounds.
• Existing baselines fail under the new metric. On the top-100 distributions in Figure 3, MORAL gets closest to the target distribution, while other methods overestimate one pair type at the expense of another despite low demographic parity values.
• MORAL achieves the fairest rankings. In Table 2 (k = 1000), MORAL obtains the best NDKL on all six datasets: 0.04 ± 0.00 (Facebook), 0.01 ± 0.00 (Credit), 0.03 ± 0.00 (German), 0.02 ± 0.00 (NBA), 0.03 ± 0.00 (Pokec-n), 0.04 ± 0.00 (Pokec-z). Its corresponding prec@1000 values are 0.95, 1.00, 0.96, 0.80, 0.98, and 0.98.
• Baselines are often less fair and sometimes infeasible. For example, UGE reaches NDKL 0.80 ± 0.07 on Credit, GraphAIR reaches 0.67 ± 0.22 on Credit and 0.26 ± 0.25 on Pokec-z, and DetConstSort reaches 0.23 ± 0.00 on Pokec-z while obtaining prec@1000 of 0.00 on Facebook and 0.00 on Credit. EDITS, FairEGM, FairLP, and FairAdj report OOM (out-of-memory) results on Pokec-n and Pokec-z; FairLP and FairAdj also report OOM on Credit.
• Both graph families are hard. The authors report that both periphery and community graph types are challenging for all methods, and highlight the largest fairness improvements from MORAL on Credit, German, and NBA.

Methodology in Plain English

The authors start by defining the graph notation, the three sensitive-attribute pair types ($E_{s\text{-}s}$, $E_{s'\text{-}s}$, $E_{s'\text{-}s'}$), and the standard demographic parity gap $\Delta_{DP}$ between intra- and inter-group predictions. They then reason about three separate gaps in existing practice: node-level fairness assumptions that break down due to limited GNN expressivity, subgroup bias hidden by dyadic aggregation, and ranking blindness. From these, they derive two properties a good metric should have — treating every sensitive-attribute pairing as a distinct subgroup while matching the original graph's edge-type distribution, and being sensitive to the proportion and rank of each pair type with position-weighted penalties. They select NDKL as a metric that satisfies both.

For the mitigation method, MORAL trains three separate link predictors, one for each sensitive group interaction ($f_{s\text{-}s}$, $f_{s\text{-}s'}$, $f_{s'\text{-}s'}$), each on only the edges of that type. At inference, a greedy algorithm builds the final ranking one position at a time: at each step it tentatively considers the top-scoring remaining candidate from each group, computes which choice would minimize the KL divergence between the running group exposure distribution and the target distribution $\pi$, and appends that edge. The paper reports a per-epoch gradient cost of $\frac{|E_{train}|}{|S| \cdot \binom{|S|}{2} \cdot b}$.

Experiments use PyTorch Geometric and PyGDebias, NVIDIA A40 GPUs, fixed random seeds, three runs per experiment, 70/10/20% train/validation/test random edge splits with the sensitive attribute distribution preserved across splits, and the Adam optimizer with learning rate 0.0003. All approaches use a GCN encoder with a dot-product decoder, and baselines follow their original hyperparameter recommendations. Evaluation uses NDKL for fairness and prec@k for utility.

Why This Matters

Impact on research: The paper reframes fair link prediction as a group-aware ranking problem rather than a binary classification problem, and argues that a widely used metric ($\Delta_{DP}$) can register as fair while hiding subgroup disparities. It formalizes the gap between node-level fairness and pairwise fairness, connecting it to the 1-WL expressivity limit of standard GNNs.

Real-world applications (as described in the paper):

• Social and professional network recommendations, where the paper cites models suggesting white women receive 33% fewer job leads on average (McDonald et al. 2009), and where closed networking circles provide more job leads and higher-status connections.
• Friendship and social interaction networks, where the majority of links occur only within the same communities, creating filter bubbles.
• Credit scoring networks, where nodes are individuals and edges are credit relationships, with age as the sensitive attribute.
• Credit approval networks, where edges link similar individuals and gender is the sensitive attribute.

Industry relevance: Because MORAL is a post-processing method paired with decoupled link predictors, it can be attached to any existing link prediction model and outputs group assignments per rank position, making it compatible with any fairness metric satisfying the paper's two properties. This model-agnostic property matters for deployed recommendation and ranking systems where the underlying predictor is fixed and retraining is costly.

Future Directions

• Extending the framework beyond binary sensitive attributes: the paper explicitly notes that its analysis is also valid for categorical and/or multiple sensitive attributes, but the experiments only cover binary attributes, leaving multi-attribute evaluation as an open question.
• Testing the approach with other encoders, including GNNs and SGNNs beyond the GCN used here, since the authors state they expect similar trends but do not report those experiments.
• Determining how the approach scales beyond the six datasets studied, given that several baselines report OOM on Pokec-n and Pokec-z and the paper does not report results from those configurations.
• Exploring alternative metrics in place of NDKL, since the paper notes that other metrics could be used provided they quantify divergence across multiple groups and incorporate exposure weighting in ranked outputs.
• Comparing against a broader set of ranking fairness methods, as the related work section in the provided content is truncated mid-sentence.

Target Audience

Researchers and practitioners working on fair graph machine learning, fair link prediction, and fair ranking, particularly those who need to evaluate recommendation or connection-suggestion systems where only top-ranked items receive attention. It also suits applied machine learning engineers looking for a model-agnostic post-processing approach that can be layered on top of an existing link prediction model, and readers who want a critique of demographic parity as a fairness criterion in pairwise prediction tasks.

Authors’ 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 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.