Fair Link Prediction with Overlapping Groups
Authors:
Preprint
- 18 December 2023
- preprint
- Published by Springer Nature in Research Square
Abstract
In this paper, we consider the problem of ensuring fairness in graph data, more specifically the implementation of fair link prediction. In the context of link prediction in graphs, the fairness notions of demographic parity and equalized odds tries to ensure equal average linking probability and true positive rates across different demographic groups consisting of various node pairs. In this paper, we propose novel algorithms to implement these fairness notions while taking overlapping and intersectional groups into account that arise in the case of multiple sensitive attributes, unlike most of the existing methods which only consider a single sensitive attribute. Assuming that the link prediction model generates a prediction score for each node pair to form an edge, we formulate a convex optimization problem that minimizes the squared Euclidean distance between the original prediction scores and transformed scores, subject to the fairness constraints. The transformed scores are then utilized for fair link prediction. We refer to our overall framework as Fair Link Prediction for Graphs (FairLPG) and demonstrate our method's effectiveness on real-world datasets and graph neural network based link predictions models. It outperforms or performs competitively with existing methods both in terms of fairness and prediction accuracy. To the best of our knowledge, this work is the first to handle the case of intersectional sensitive groups in the graph setting.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Fairness amidst non‐IID graph data: A literature reviewAI Magazine, 2025
- Fairness in Graph Mining: A SurveyIEEE Transactions on Knowledge and Data Engineering, 2023
- Towards Intersectionality in Machine Learning: Including More Identities, Handling Underrepresentation, and Performing Evaluation2022
- FairDrop: Biased Edge Dropout for Enhancing Fairness in Graph Representation LearningIEEE Transactions on Artificial Intelligence, 2021
- A Survey on Bias and Fairness in Machine LearningACM Computing Surveys, 2021
- Matching code and law: achieving algorithmic fairness with optimal transportData Mining and Knowledge Discovery, 2019
- Sources of Segregation in Social Networks: A Novel Approach Using FacebookAmerican Sociological Review, 2017
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Birds of a Feather: Homophily in Social NetworksAnnual Review of Sociology, 2001
- An extension of Karmarkar's projective algorithm for convex quadratic programmingMathematical Programming, 1989