# Promoting Fairness in Link Prediction with Graph Enhancement

arXiv: https://arxiv.org/abs/2409.08658 · HTML: https://mlsanity.com/paper/2409.08658/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 70 references that are in the map.
- First posted on arXiv 13 Sep 2024.

## Builds on (most cited first, 30 of 44)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Data-centric Artificial Intelligence: A Survey](https://mlsanity.com/paper/2303.10158/) (2023)
- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Fair Mixup: Fairness via Interpolation](https://mlsanity.com/paper/2103.06503/) (2021)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Graph-MLP: Node Classification without Message Passing in Graph](https://mlsanity.com/paper/2106.04051/) (2021)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Satisfying Real-world Goals with Dataset Constraints](https://mlsanity.com/paper/1606.07558/) (2016)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [Learning Fair Node Representations with Graph Counterfactual Fairness](https://mlsanity.com/paper/2201.03662/) (2022)

## Built on by (most cited first, 6 of 6)

- [LUNE: Efficient LLM Unlearning via LoRA Fine-Tuning with Negative Examples](https://mlsanity.com/paper/2512.07375/) (2025)
- [Enabling Group Fairness in Graph Unlearning via Bi-level Debiasing](https://mlsanity.com/paper/2505.09702/) (2025)
- [Recover-to-Forget: Gradient Reconstruction from LoRA for Efficient LLM Unlearning](https://mlsanity.com/paper/2512.07374/) (2025)
- [Information Loss and Disparate Effects in Network Embeddings](https://mlsanity.com/paper/2509.12396/) (2025)
- [Estimating Fair Graphs from Graph-Stationary Data](https://mlsanity.com/paper/2510.07536/) (2025)
- [Mitigating Bias in Graph Hyperdimensional Computing](https://mlsanity.com/paper/2512.07433/) (2025)

## Abstract (arXiv)

Link prediction is a crucial task in network analysis, but it has been shown to be prone to biased predictions, particularly when links are unfairly predicted between nodes from different sensitive groups. In this paper, we study the fair link prediction problem, which aims to ensure that the predicted link probability is independent of the sensitive attributes of the connected nodes. Existing methods typically incorporate debiasing techniques within graph embeddings to mitigate this issue. However, training on large real-world graphs is already challenging, and adding fairness constraints can further complicate the process. To overcome this challenge, we propose FairLink, a method that learns a fairness-enhanced graph to bypass the need for debiasing during the link predictor's training. FairLink maintains link prediction accuracy by ensuring that the enhanced graph follows a training trajectory similar to that of the original input graph. Meanwhile, it enhances fairness by minimizing the absolute difference in link probabilities between node pairs within the same sensitive group and those between node pairs from different sensitive groups. Our extensive experiments on multiple large-scale graphs demonstrate that FairLink not only promotes fairness but also often achieves link prediction accuracy comparable to baseline methods. Most importantly, the enhanced graph exhibits strong generalizability across different GNN architectures.