Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Problem Statement
Fairness in link prediction aims to reduce disparities in predicted link probabilities across groups. In social-network recommendations, link predictors determine visibility and connectivity, potentially inducing feedback loops that reinforce within-group connections and disadvantage minority groups. A critical issue arises when these models are trained on historical graph data, which can inherit and amplify existing structural biases.

While demographic parity ($\Delta$DP) is a common fairness metric in ranked link prediction, it aggregates links into coarse categories (same-group vs. cross-group). Mattos et al. (2025) argue that this dyadic view fails to detect exposure bias because it ignores the specific position of links within the ranking. Consequently, aggregate parity can hold even when specific subgroup-pair links (e.g., female-female links) are systematically ranked lower than others, obscuring within-group disparities.

Methodology
This study is a reproducibility and extension of Mattos et al. (2025). The authors formalize link prediction as a ranking problem where sensitive attributes define subgroup-pair types (e.g., $E_{0-0}, E_{1-1}, E_{0-1}$).

1. Metrics:

   • Demographic Parity ($\Delta$DP): Measures the difference in mean predicted scores between intra-group ($E_{intra}$) and inter-group ($E_{inter}$) links. It is permutation-invariant regarding ranking order.
   • Normalized Discounted KL-divergence (NDKL): A rank-aware, non-dyadic metric that treats all subgroup-pair types distinctly. It accumulates the Kullback-Leibler divergence between the predicted exposure distribution and a target distribution across ranking prefixes, weighted by a logarithmic decay factor to penalize deviations at higher ranks more heavily.
   • Utility: Measured via Precision@1000 and NDCG@1000.

2. MORAL (Multi-Output Ranking Aggregation for Link Fairness):
   A post-processing algorithm that re-ranks outputs from decoupled link predictors (one model trained per subgroup-pair type). MORAL employs a greedy KL-guided aggregation strategy: at each rank position, it selects the top remaining edge from each subgroup-pair pool that minimizes the KL-divergence between the updated exposure distribution and a target distribution $\pi$ (derived from the original graph).

3. Experimental Setup:

   • Datasets: Six social network datasets (Credit, Facebook, German, NBA, Pokec-n, Pokec-z) and two additional datasets (Global Airport Routes Network, Chameleon) for topology verification.
   • Reproduction: The authors reproduced the core setup using GCN encoders and dot-product decoders, correcting inconsistencies found in the original codebase regarding target distribution calculation and KL-aggregation.
   • Extensions:
     • Asymmetric Homophily Stress-Test: Synthetic graphs generated via the Directed Preferential Attachment with Homophily (DPAH) model to test performance under varying degrees of within-group connectivity.
     • Metric Robustness: Evaluation using Attention-Weighted Rank Fairness (AWRF) and NDCG to ensure results are not specific to the NDKL aggregation mechanism.
     • Categorical Attributes: Extension of the framework to sensitive attributes with cardinality $m > 2$.

Key Contributions

1. Reproduction and Correction: The study successfully reproduces the core claims of Mattos et al. (2025) while releasing a corrected, reproducible implementation. It identifies and fixes inconsistencies in the original code regarding target distribution computation and KL-divergence normalization.
2. Validation of Claims:
   • C1: Confirms that $\Delta$DP can indicate aggregate parity even when significant exposure disparities exist within specific subgroup pairs (e.g., within $E_{intra}$).
   • C2: Demonstrates that NDKL effectively detects these hidden disparities due to its rank-aware and non-dyadic nature.
   • C3: Shows that MORAL consistently mitigates exposure biases (low NDKL) while maintaining competitive utility (Precision/NDCG) across diverse datasets.
3. Robustness Analysis:
   • The study extends the original work by testing asymmetric homophily, showing that MORAL performs robustly, though exposure disparities are most pronounced at intermediate absolute homophily levels.
   • It validates the framework's generalizability to categorical sensitive attributes (up to $m=10$) and different graph topologies (Core-periphery, Heterophilic).
   • It confirms that fairness improvements are not merely an artifact of optimizing NDKL, as similar trends are observed with AWRF.

Results

• Fairness vs. Utility: MORAL achieves near-zero NDKL across all datasets, significantly outperforming baselines (FairAdj, FairWalk, DetConstSort). This reduction in exposure bias comes with minimal utility loss; MORAL maintains high Precision@1000, often matching or exceeding baselines.
• Metric Sensitivity: $\Delta$DP remains largely invariant to shifts in exposure allocation within groups, whereas NDKL and AWRF are highly sensitive to these shifts.
• Homophily: In synthetic settings, exposure-based metrics peak at intermediate absolute homophily ($\approx 0.6$), where within-group edges are frequent but rankings remain diverse. At high homophily, utility drops slightly as decoupled predictors receive weaker training signals.
• Categorical Attributes: As the number of subgroup-pair types ($T$) increases, NDKL and AWRF degrade monotonically, indicating that aligning exposure with the target distribution becomes progressively harder. However, utility remains high, suggesting top-ranked edges remain accurate even as lower ranks become less stable.
• Ablation: A comparison of pre-rerank vs. post-rerank scores shows that the greedy KL-aggregation step itself is responsible for a substantial reduction in exposure bias (66.9% reduction in NDKL, 92.6% in AWRF).

Significance and Claims
The paper concludes that dyadic demographic parity is insufficient for ranked link prediction because it can obscure subgroup-pair exposure disparities. The authors argue that when link prediction outputs are consumed as rankings, exposure should be the relevant currency of fairness.

The study supports the use of exposure-based, rank-aware metrics (like NDKL and AWRF) and the MORAL post-processing method as effective tools for debiasing ranked link predictions. It highlights a practical trade-off: while MORAL scales to higher-cardinality settings, the computational cost and difficulty of exposure alignment increase with the number of subgroup-pair types. The authors emphasize that preserving the original graph's distribution ($\pi$) is a design choice to prevent algorithmic amplification of bias, rather than a claim that the original distribution is inherently "fair."