# Guarantees for Spectral Clustering with Fairness Constraints

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

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2019.

## Built on by (most cited first, 30 of 72)

- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [FairGRAPE: Fairness-aware GRAdient Pruning mEthod for Face Attribute Classification](https://mlsanity.com/paper/2207.10888/) (2022)
- [RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network](https://mlsanity.com/paper/2202.13547/) (2022)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [Fairness Amidst Non-IID Graph Data: A Literature Review](https://mlsanity.com/paper/2202.07170/) (2022)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metric](https://mlsanity.com/paper/2209.12396/) (2022)
- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [Robust Fair Clustering: A Novel Fairness Attack and Defense Framework](https://mlsanity.com/paper/2210.01953/) (2022)
- [FairGen: Towards Fair Graph Generation](https://mlsanity.com/paper/2303.17743/) (2023)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Deep Fair Discriminative Clustering](https://mlsanity.com/paper/2105.14146/) (2021)
- [A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering](https://mlsanity.com/paper/2105.14172/) (2021)
- [Fair Clustering Using Antidote Data](https://mlsanity.com/paper/2106.00600/) (2021)
- [Fairness-Aware Unsupervised Feature Selection](https://mlsanity.com/paper/2106.02216/) (2021)
- [Graph Learning with Localized Neighborhood Fairness](https://mlsanity.com/paper/2212.12040/) (2022)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Pairwise Fairness for Ordinal Regression](https://mlsanity.com/paper/2105.03153/) (2021)
- [FAL-CUR: Fair Active Learning using Uncertainty and Representativeness on Fair Clustering](https://mlsanity.com/paper/2209.12756/) (2022)
- [Fairness-aware Multi-view Clustering](https://mlsanity.com/paper/2302.05788/) (2023)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Fairness Degrading Adversarial Attacks Against Clustering Algorithms](https://mlsanity.com/paper/2110.12020/) (2021)
- [Emergent specialization from participation dynamics and multi-learner retraining](https://mlsanity.com/paper/2206.02667/) (2022)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Fairness-Aware Estimation of Graphical Models](https://mlsanity.com/paper/2408.17396/) (2024)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)

## Abstract (arXiv)

Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where h groups have strong inter-group connectivity, but also exhibit a "natural" clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.