mlsanityData to 7 Oct 2026

Fair Clustering Through Fairlets

arXiv 1802.05733 ↗First posted 15 Feb 2018cs.LG stat.MLcited by 176

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 40; 2022: 30; 2023: 34; 2024: 29; 2025: 21; 2026: 22.

176 papers.

Sort:

By area:

  1. 2021A survey on datasets for fairness-aware machine learningcited by 157
  2. 2022Fairness in Graph Mining: A Surveycited by 76
  3. 2022Fair and Optimal Classification via Post-Processingcited by 50
  4. 2021Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Informationcited by 33
  5. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  6. 2023Inductive Graph Unlearningcited by 30
  7. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  8. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  9. 2021A Sociotechnical View of Algorithmic Fairnesscited by 24
  10. 2023Efficient fair PCA for fair representation learningcited by 23
  11. 2021Fair Clustering Under a Bounded Costcited by 21
  12. 2022Fairness Amidst Non-IID Graph Data: A Literature Reviewcited by 20
38 more
  1. 2021Loss-Aversively Fair Classificationcited by 18
  2. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  3. 2021Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifoldcited by 18
  4. 2024Generative Dataset Distillation: Balancing Global Structure and Local Detailscited by 18
  5. 2021Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraintscited by 17
  6. 2021Modeling Techniques for Machine Learning Fairness: A Surveycited by 17
  7. 2022Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metriccited by 17
  8. 2022Scalable Spectral Clustering with Group Fairness Constraintscited by 16
  9. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  10. 2022Robust Fair Clustering: A Novel Fairness Attack and Defense Frameworkcited by 13
  11. 2023Proportional Fairness in Clustering: A Social Choice Perspectivecited by 12
  12. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  13. 2021Deep Fair Discriminative Clusteringcited by 10
  14. 2021A Stochastic Alternating Balance k-Means Algorithm for Fair Clusteringcited by 10
  15. 2021Fair Clustering Using Antidote Datacited by 10
  16. 2021Fairness-Aware Unsupervised Feature Selectioncited by 10
  17. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
  18. 2022Fairness-aware Model-agnostic Positive and Unlabeled Learningcited by 10
  19. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  20. 2021Fair-Capacitated Clusteringcited by 9
  21. 2022Group Meritocratic Fairness in Linear Contextual Banditscited by 9
  22. 2023Doubly Constrained Fair Clusteringcited by 9
  23. 2024A Survey on Deep Clustering: From the Prior Perspectivecited by 9
  24. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  25. 2022Individual Preference Stability for Clusteringcited by 8
  26. 2023Proportionally Representative Clusteringcited by 8
  27. 2023Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!cited by 8
  28. 2023On Measuring Fairness in Generative Modelscited by 8
  29. 2023Fair Wasserstein Coresetscited by 8
  30. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  31. 2023Adversarial Attacks on the Interpretation of Neuron Activation Maximizationcited by 7
  32. 2021Pairwise Fairness for Ordinal Regressioncited by 6
  33. 2022Improved Approximation for Fair Correlation Clusteringcited by 6
  34. 2023Near-Optimal Quantum Coreset Construction Algorithms for Clusteringcited by 6
  35. 2024Fair Submodular Covercited by 6
  36. 2021Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problemcited by 5
  37. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  38. 2021Fairness Degrading Adversarial Attacks Against Clustering Algorithmscited by 5

50 most cited of 176 All 176 (JSON)