# A Semidefinite Relaxation Approach for Fair Graph Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 19 Oct 2024.

## Builds on (most cited first, 13 of 13)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [On the Apparent Conflict Between Individual and Group Fairness](https://mlsanity.com/paper/1912.06883/) (2019)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [On Formalizing Fairness in Prediction with Machine Learning](https://mlsanity.com/paper/1710.03184/) (2017)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [A Stochastic Optimization Framework for Fair Risk Minimization](https://mlsanity.com/paper/2102.12586/) (2021)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Enforcing Group Fairness in Algorithmic Decision Making: Utility Maximization Under Sufficiency](https://mlsanity.com/paper/2206.02237/) (2022)
- [Minimum adjusted Rand index for two clusterings of a given size](https://mlsanity.com/paper/2002.03677/) (2020)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Effect of a Process Mining based Pre-processing Step in Prediction of the Critical Health Outcomes](https://mlsanity.com/paper/2407.02821/) (2024)
- [Towards Cohesion-Fairness Harmony: Contrastive Regularization in Individual Fair Graph Clustering](https://mlsanity.com/paper/2402.10756/) (2024)

## Abstract (arXiv)

Fair graph clustering is crucial for ensuring equitable representation and treatment of diverse communities in network analysis. Traditional methods often ignore disparities among social, economic, and demographic groups, perpetuating biased outcomes and reinforcing inequalities. This study introduces fair graph clustering within the framework of the disparate impact doctrine, treating it as a joint optimization problem integrating clustering quality and fairness constraints. Given the NP-hard nature of this problem, we employ a semidefinite relaxation approach to approximate the underlying optimization problem. For up to medium-sized graphs, we utilize a singular value decomposition-based algorithm, while for larger graphs, we propose a novel algorithm based on the alternative direction method of multipliers. Unlike existing methods, our formulation allows for tuning the trade-off between clustering quality and fairness. Experimental results on graphs generated from the standard stochastic block model demonstrate the superiority of our approach in achieving an optimal accuracy-fairness trade-off compared to state-of-the-art methods.