Fair Clustering Through Fairlets

By Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii. 2018

538 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability, 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 Artificial Intelligence

In Statistics and Probability

In AI Ethics, Fairness & Society

In Algorithms & Complexity

Citations in the corpus

Beyond Individual and Group Fairness (2020, background): “…studying 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…”
Proportionally Fair Clustering (2019, background): “In (Chierichetti et al., 2017) and subsequent generalizations (Rösner & Schmidt, 2018; Bera et al.”
Scalable Fair Clustering (2019, methodology): “In order to compute the ﬁnal clustering, however, they resort to a variant of the algorithm of Chierichetti et al. (2017), or another algorithm with a running time exponential in k .”
Empirical Risk Minimization under Fairness Constraints (2018, background): “mpirically effective and performs favorably against state-of-the-art approaches. 1 Introduction In recent years there has been a lot of interest on algorithmic fairness in machine learning see, e.g., [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] and references therein. The central question is how to e”
Algorithmic Fairness (2020, neutral): “[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 and Transparency of Machine Learning for Trustworthy Cloud Services (2018, background): “Recently, novel techniques exist which can deal with representation issues directly in the training phase [24], [25].”
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering (2018, methodology): “[12].”
What About Applied Fairness? (2018, background): “…let alone nascent deﬁnitions in sub-areas like recommender systems (Burke et al., 2018; Ekstrand et al., 2018), regression (Calders et al., 2013; Berk et al., 2017), and clustering (Chierichetti et al., 2017) or those that may have been de-ﬁned in neighboring ﬁelds like economics (Baumol, 1982).”
On the cost of essentially fair clusterings (2018, methodology): “We follow [14] and call these atomic microclusters fairlets .”
Fairer machine learning in the real world: Mitigating discrimination without collecting sensitive data (2017, background): “Unsupervised learning is particularly challenging to evaluate fairness upon, given that groups discovered are latent, although there has been some recent work beginning to explore this space (Chierichetti et al., 2017).”
Fairness in Machine Learning (2020, methodology): “Pre-Processing methods consist in transforming the training data to remove undesired biases [16, 21, 24, 28, 47, 51, 52, 53, 61, 64, 65, 66, 67, 86, 90, 91, 92, 112, 114, 116, 118, 121, 122, 127, 126, 164, 174, 188, 190, 191, 193].”
Convex Formulations for Fair Principal Component Analysis (2018, methodology): “Chierichetti et al. (2017) directly perform fair clustering by approximating an NP-hard preprocessing step; however, this approach only applies to speciﬁc clustering techniques whereas the approach we develop can be used with arbitrary a r X i v : 1802 .”
Privacy preserving clustering with constraints (2018, methodology): “The fair k -center problem was introduced in [13].”
Rényi Fair Inference (2019, background): “This notion of fairness is closely related to minimum balance introduced by Chierichetti et al. (2017).”
Fairness in representation: quantifying stereotyping as a representational harm (2019, methodology): “In the context of unsupervised learning, recent work on fair clustering[12, 31, 3] and PCA[30, 28] seeks to generate a modiﬁed representation of the input points so that the new representation (clustering or reduced dimension) satisﬁes a notion of “balance” with respect to groups.”
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.”
Fair Algorithms for Clustering (2019, methodology): “The DI doctrine is indeed a law [1,22] in the United States, and consequently many works on algorithmic fairness [13, 14, 18, 23, 37, 43] have focused on this.”
A Review on Fairness in Machine Learning (2022, background): “Chierichetti et al. [46] and Backurs et al. [9] use the same notion of fair representation learning and apply it for fair clustering, and Samadi et al. [180] apply it for fair dimensionality reduction (PCA).”