# Socially Fair Center-based and Linear Subspace Clustering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 22 Aug 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/2008.05171/) (2020)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Faster Algorithms for the Constrained k-means Problem](https://mlsanity.com/paper/1504.02564/) (2015)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Representing Sentences as Low-Rank Subspaces](https://mlsanity.com/paper/1704.05358/) (2017)
- [Geometry of Polysemy](https://mlsanity.com/paper/1610.07569/) (2016)

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

- [Fair Active Ranking from Pairwise Preferences](https://mlsanity.com/paper/2402.03252/) (2024)

## Abstract (arXiv)

Center-based clustering (e.g., k-means, k-medians) and clustering using linear subspaces are two most popular techniques to partition real-world data into smaller clusters. However, when the data consists of sensitive demographic groups, significantly different clustering cost per point for different sensitive groups can lead to fairness-related harms (e.g., different quality-of-service). The goal of socially fair clustering is to minimize the maximum cost of clustering per point over all groups. In this work, we propose a unified framework to solve socially fair center-based clustering and linear subspace clustering, and give practical, efficient approximation algorithms for these problems. We do extensive experiments to show that on multiple benchmark datasets our algorithms either closely match or outperform state-of-the-art baselines.