# Fair Labeled Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 28 May 2022.

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

- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [Approximation algorithms for stochastic clustering](https://mlsanity.com/paper/1809.02271/) (2018)
- [Whither Fair Clustering?](https://mlsanity.com/paper/2007.07838/) (2020)

## Built on by (most cited first, 2 of 2)

- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024)

## Abstract (arXiv)

Numerous algorithms have been produced for the fundamental problem of clustering under many different notions of fairness. Perhaps the most common family of notions currently studied is group fairness, in which proportional group representation is ensured in every cluster. We extend this direction by considering the downstream application of clustering and how group fairness should be ensured for such a setting. Specifically, we consider a common setting in which a decision-maker runs a clustering algorithm, inspects the center of each cluster, and decides an appropriate outcome (label) for its corresponding cluster. In hiring for example, there could be two outcomes, positive (hire) or negative (reject), and each cluster would be assigned one of these two outcomes. To ensure group fairness in such a setting, we would desire proportional group representation in every label but not necessarily in every cluster as is done in group fair clustering. We provide algorithms for such problems and show that in contrast to their NP-hard counterparts in group fair clustering, they permit efficient solutions. We also consider a well-motivated alternative setting where the decision-maker is free to assign labels to the clusters regardless of the centers' positions in the metric space. We show that this setting exhibits interesting transitions from computationally hard to easy according to additional constraints on the problem. Moreover, when the constraint parameters take on natural values we show a randomized algorithm for this setting that always achieves an optimal clustering and satisfies the fairness constraints in expectation. Finally, we run experiments on real world datasets that validate the effectiveness of our algorithms.