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

By João Mattos, Debolina Halder Lina, and Arlei Silva (Rice University)
Accepted at AAAI-26 (Oral)

Motivation

Link prediction is the task of predicting missing or future connections in a graph. This task drives key applications from social recommendations to knowledge graph completion.

But biased link predictions can reinforce structural inequalities. For example, under-connecting minorities in professional networks like LinkedIn, or creating “filter bubbles” in online communities.

Existing work defines fairness dyadically, comparing inter-group vs. intra-group edges under Demographic Parity (ΔDP).
However, our work shows that this dyadic framing masks hidden biases and is insensitive to ranking exposure and proportions, limiting its effectiveness.

Problem: The Dyadic Fairness Trap

1. Limited Expressive Power of GNNs

Standard Graph Neural Networks (GNNs) operate within the expressivity limits of the 1-Weisfeiler-Lehman test, producing similar embeddings for structurally symmetric nodes, even if they belong to different demographic groups.

Hence, fair node embeddings do not guarantee fair link predictions

Example: Two nodes with similar neighborhoods but different genders may still get indistinguishable embeddings, leading to biased edge predictions.

2. Hidden Bias Within Edge Groups

Demographic parity aggregates sensitive subgroups into broad categories (e.g., “intra” vs “inter” edges), hiding subgroup imbalances.
For instance, male–male links may dominate over female–female links, yet ΔDP will remain low.

Property 1 (Non-Dyadic Distribution-Preserving Fairness): requires the predicted edge-type distribution ($\hat{\pi }$) to match the original one ($\pi$):

3. Missing Ranking Awareness

ΔDP treats predictions as unordered, ignoring exposure bias — when certain groups dominate the top of a ranked list despite similar global proportions.
This limitation leads to unfair recommendation visibility.

To fix this, we formalize:

Property 2 (Rank-Aware Fairness): Fairness metrics must consider both proportions and positions of subgroup edges in the ranking.

Solution: Distribution-Preserving and Rank-Aware Fairness

We adapt ideas from fair information retrieval and introduce the Normalized Cumulative KL-Divergence (NDKL) metric:

NDKL penalizes deviations between the exposure of each group in the top-k ranks and their expected proportions.
It satisfies both key properties:

1. Non-Dyadic (Subgroup-Aware)
2. Rank-Aware (Exposure-Sensitive)

The MORAL Algorithm

We introduce MORAL (Multi-Output Ranking Aggregation for Link Fairness) — a lightweight, post-processing framework compatible with any link prediction model.

How MORAL Works

1. Decoupled Training:
   Train separate predictors for each sensitive-group edge type
   (e.g., male–male, female–female, male–female).

2. Fair Ranking Aggregation:
   During inference, MORAL greedily builds a ranked list that minimizes divergence from the desired exposure distribution π using group-specific scores.

Inputs

• Candidate sets ${\mathcal{C}}_j=\{(u,v,\text{score})\}$ for each group $j\in \{0,1,2\}$ (sorted by descending score)
• Target distribution $\mathit{\pi }=({\pi }_0,{\pi }_1,{\pi }_2)$
• Total output size $n$

Output

• Ranking list $\mathbf{R}$ of $n$ predicted edges with assigned group labels

def MORAL(n, p):
    """
    Greedy probabilistic approach to generate an array that maintains the 
    target distribution (p0, p1, p2, ...., pn) for any prefix length k.
    
    This code assumes a distribution of 3 link types.
    
    Args:
        n (int): Length of the array.
        p (tuple): Target proportions (p0, p1, p2, ..., pn).

    Returns:
        list: Generated array of length n with values in {0,1,2}.
    """
    target_counts = np.array([p_i * n for p_i in p])  # Expected counts for 0,1,2
    actual_counts = np.zeros(3)  # Current counts of 0s, 1s, 2s
    arr = []

    for i in range(n):
        # Compute probabilities to minimize deviation from target counts
        remaining = n - i
        probs = (target_counts - actual_counts) / remaining  # Adjusted probabilities
        
        # Avoid numerical errors
        probs = np.clip(probs, 0, 1)
        probs /= probs.sum()  # Normalize to sum to 1

        # Sample from adjusted probabilities
        choice = np.random.choice([0, 1, 2], p=probs)
        arr.append(choice)
        actual_counts[choice] += 1

    return arr

This ensures fairness without retraining the base model, and balances accuracy and exposure simultaneously.

One can input the top links of each pair type using a mask:

final_output = torch.zeros(size=(K,))
final_labels = torch.zeros(size=(K,))

output_array_positions = MORAL(K, pi.numpy())
for sens_value in range(3):
	mask = output_array_positions == sens_value
	sens_mask = sens == sens_value
	sens_val_outputs_sorted, idx = output[sens_mask].sort(descending=True)
	final_output[mask] = sens_val_outputs_sorted[:mask.sum()]

In this snippet, output contains the scores for each pair, and sens is an indicator variable, indicating the type of each pair in output.

Experiments

We evaluated on six real-world datasets:

Results Highlights

• RQ1 – Hidden Bias:
  ΔDP fails to detect subgroup imbalance; MORAL matches the original distribution closely.

• RQ2 – Ranking Awareness:
  Rankings with identical ΔDP can differ drastically in NDKL — demonstrating ΔDP’s blindness to exposure bias.

• RQ3 – Performance:
  MORAL achieves the lowest NDKL (best fairness) while maintaining strong accuracy.

Table 1. Fairness performance comparison of all approaches considered (k = 1000).
Lower NDKL and higher prec@1000 are better.
Best NDKL and prec@1000 values are in bold and underlined, respectively.

MORAL consistently outperforms existing baselines in the fairness–utility trade-off across all datasets.

Key Takeaways

• Dyadic Fairness is not enough for Link Prediction.
  It hides biases within and across subgroups.

• Fairness Must Be Rank-Aware and Distribution-Aware.
  Exposure matters: fairness lives at the top of the ranking.

• MORAL Provides a Simple Fix.
  Decoupled predictors + fair aggregation deliver robust and interpretable fairness improvements.

Broader Impact

MORAL offers a general blueprint for fairness in pair-wise prediction tasks, relevant to recommender systems, graph completion, and link discovery.
By addressing fairness beyond dyadic approaches, it challenges the community to rethink fairness in structured data and graph learning.

Resources

• 📄 Paper: AAAI-26 Proceedings – “Breaking the Dyadic Barrier”
• 💻 Code: github.com/joaopedromattos/MORAL
• 📊 BibTeX: (available in the repository)