Scalable Fair Clustering

By Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner. 2019

232 citations recorded by the source corpus.

We study the fair variant of the classic $k$-median problem introduced by Chierichetti et al. [2017]. In the standard $k$-median problem, given an input pointset $P$, the goal is to find $k$ centers $C$ and assign each input point to one of the centers in $C$ such that the average distance of points to their cluster center is minimized. In the fair variant of $k$-median, the points are colored, and the goal is to minimize the same average distance objective while ensuring that all clusters have an "approximately equal" number of points of each color. Chierichetti et al. proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the $k$-median objective. In the second step, fairlets are merged into $k$ clusters by one of the existing $k$-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time. Our algorithm additionally allows for finer control over the balance of resulting clusters than the original work. We complement our theoretical bounds with empirical evaluation.

Subfields: AI Ethics, Fairness & Society, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In AI Ethics, Fairness & Society

In Algorithms & Complexity

Citations in the corpus

Does Gender Matter? Towards Fairness in Dialogue Systems (2019, neutral): “4411 and Hamilton, 2019) and clustering (Backurs et al., 2019; Chen et al., 2019).”
A Survey on Bias and Fairness in Machine Learning (2019, methodology): “Fair methods in domains similar to community detection are also proposed, such as graph embedding [21] and clustering [7, 30].”
Beyond Individual and Group Fairness (2020, background): “…fairness criteria and algorithms for ranking [Celis et al., 2018, Beutel et al., 2019, Narasimhan et al., 2019] and clustering problems [Chierichetti et al., 2017, Schmidt et al., 2018, Backurs et al., 2019] with requirement of a proportional representation of populations within each cluster.”
Man is to Person as Woman is to Location: Measuring Gender Bias in Named Entity Recognition (2019, background): “…learning (Moyer et al. 2018) to graph embedding (Bose and Hamilton 2019) to community detection (Mehrabi et al. 2019a) and clustering (Backurs et al. 2019), researchers have studied biases in these areas and tried to address them by pointing out the observed problems and proposing…”
Algorithmic Fairness (2020, background): “[8, 35] use the same notion of fair representation learning and applies it for fair clustering, and [122] applies it for fair dimensionality reduction (PCA).”
Fairness in Machine Learning: A Survey (2020, methodology): “We also note that currently, there is little runtime benchmarking of methods outside of clustering approaches (see [243, 14]).”
Fair Algorithms for Clustering (2019, methodology): “To match [25] and [12], we sub-sample bank and census to 1000 and 600 respectively, declared only one sensitive attribute for each (i.”
Rényi Fair Inference (2019, methodology): “(2017); Backurs et al. (2019); Rösner & Schmidt (2018); Bercea et al.”
Trustworthy Artificial Intelligence: A Review (2022, methodology): “Decrease F [10, 27, 33, 38, 97, 128, 172] F, P [63, 91, 169, 189] F, A [156]”
A Review on Fairness in Machine Learning (2022, methodology): “[9] use the same notion of fair representation learning and apply it for fair clustering, and Samadi et al.”
Fair Generative Modeling via Weak Supervision (2019, background): “There is also a body of work on fair clustering (Chierichetti et al., 2017; Backurs et al., 2019; Bera et al., 2019; Schmidt et al., 2018) which ensure that the clustering assignments are balanced with respect to some sensitive attribute.”