# Fair clustering via equitable group representations

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2020.

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

- [A survey on datasets for fairness-aware machine learning](https://mlsanity.com/paper/2110.00530/) (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 New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering](https://mlsanity.com/paper/2105.14172/) (2021)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [FedCCL: Federated Dual-Clustered Feature Contrast Under Domain Heterogeneity](https://mlsanity.com/paper/2404.09259/) (2024)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Minimax Group Fairness in Strategic Classification](https://mlsanity.com/paper/2410.02513/) (2024)
- [Modification-Fair Cluster Editing](https://mlsanity.com/paper/2112.03183/) (2021)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Fair Labeled Clustering](https://mlsanity.com/paper/2205.14358/) (2022)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Fairness Through Counterfactual Utilities](https://mlsanity.com/paper/2108.05315/) (2021)
- [Increasing Fairness in Predictions Using Bias Parity Score Based Loss Function Regularization](https://mlsanity.com/paper/2111.03638/) (2021)
- [Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolina](https://mlsanity.com/paper/2205.14867/) (2022)
- [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022)
- [Bias Mitigation Methods for Binary Classification Decision-Making Systems: Survey and Recommendations](https://mlsanity.com/paper/2305.20020/) (2023)

## Abstract (arXiv)

What does it mean for a clustering to be fair? One popular approach seeks to ensure that each cluster contains groups in (roughly) the same proportion in which they exist in the population. The normative principle at play is balance: any cluster might act as a representative of the data, and thus should reflect its diversity. But clustering also captures a different form of representativeness. A core principle in most clustering problems is that a cluster center should be representative of the cluster it represents, by being "close" to the points associated with it. This is so that we can effectively replace the points by their cluster centers without significant loss in fidelity, and indeed is a common "use case" for clustering. For such a clustering to be fair, the centers should "represent" different groups equally well. We call such a clustering a group-representative clustering. In this paper, we study the structure and computation of group-representative clusterings. We show that this notion naturally parallels the development of fairness notions in classification, with direct analogs of ideas like demographic parity and equal opportunity. We demonstrate how these notions are distinct from and cannot be captured by balance-based notions of fairness. We present approximation algorithms for group representative k-median clustering and couple this with an empirical evaluation on various real-world data sets.