Structural Bias Beyond Homophily: A Study of Fairness in Link Prediction
cs.LG, cs.SI
Submitted: 2026-02-12
Updated: 2026-05-29
License: http://creativecommons.org/licenses/by/4.0/
The gist: Graph link prediction (LP) plays a critical role in socially impactful applications such as job recommendation and friendship formation, making fairness a critical concern in this task.
Terminology
Abstract
Graph link prediction (LP) plays a critical role in socially impactful applications such as job recommendation and friendship formation, making fairness a critical concern in this task. While many fairness-aware methods manipulate graph structures to mitigate prediction disparities, the topological biases inherent to social graphs remain poorly understood and are consistently conflated with homophily alone. In this work, we study the relationship between structural biases and fairness outcomes in LP. To this end, we formalize a taxonomy of topological bias measures and introduce a graph generation method producing a diverse corpus of synthetic graphs with controlled structural properties. Using this corpus, we show empirically that fairness outcomes are strongly correlated with graph topology, and that current fairness-aware methods remain sensitive to structural biases beyond homophily. These findings highlight the need for structurally grounded evaluations in fair graph learning.
Sources
- FairEdit: Preserving Fairness in Graph Neural Networks through Greedy Graph Editing
- Structural Group Unfairness: Measurement and Mitigation by means of the Effective Resistance
- Graph Learning with Localized Neighborhood Fairness
- A Topology-aware Analysis of Graph Collaborative Filtering
- Pitfalls of Graph Neural Network Evaluation
- Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction
- Semi-Supervised Classification with Graph Convolutional Networks
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks