# Fair Clustering Through Fairlets

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

## Key facts

- Cited by 176 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2018.

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

- [A survey on datasets for fairness-aware machine learning](https://mlsanity.com/paper/2110.00530/) (2021)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Fair and Optimal Classification via Post-Processing](https://mlsanity.com/paper/2211.01528/) (2022)
- [Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information](https://mlsanity.com/paper/2102.08410/) (2021)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Efficient fair PCA for fair representation learning](https://mlsanity.com/paper/2302.13319/) (2023)
- [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)
- [Loss-Aversively Fair Classification](https://mlsanity.com/paper/2105.04273/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifold](https://mlsanity.com/paper/2109.11196/) (2021)
- [Generative Dataset Distillation: Balancing Global Structure and Local Details](https://mlsanity.com/paper/2404.17732/) (2024)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Modeling Techniques for Machine Learning Fairness: A Survey](https://mlsanity.com/paper/2111.03015/) (2021)
- [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)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Robust Fair Clustering: A Novel Fairness Attack and Defense Framework](https://mlsanity.com/paper/2210.01953/) (2022)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (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)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Fairness-aware Model-agnostic Positive and Unlabeled Learning](https://mlsanity.com/paper/2206.09346/) (2022)

## Abstract (arXiv)

We study the question of fair clustering under the em disparate impact doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the k-center and the k-median objectives, and show that even with two protected classes the problem is challenging, as the optimum solution can violate common conventions---for instance a point may no longer be assigned to its nearest cluster center! En route we introduce the concept of fairlets, which are minimal sets that satisfy fair representation while approximately preserving the clustering objective. We show that any fair clustering problem can be decomposed into first finding good fairlets, and then using existing machinery for traditional clustering algorithms. While finding good fairlets can be NP-hard, we proceed to obtain efficient approximation algorithms based on minimum cost flow. We empirically quantify the value of fair clustering on real-world datasets with sensitive attributes.