Proportionally Fair Clustering

By Xingyu Chen, Brandon Fain, Charles Lyu, Kamesh Munagala. 2019

183 citations recorded by the source corpus.

We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering $n$ points with $k$ centers, we define fairness as proportionality to mean that any $n/k$ points are entitled to form their own cluster if there is another center that is closer in distance for all $n/k$ points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the $k$-means objective.

Subfields: Economics and Econometrics, 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 Economics and Econometrics

1. Aram Galstyan
2. Kristina Lerman
3. Fred Morstatter

In AI Ethics, Fairness & Society

1. Aram Galstyan
2. Fred Morstatter
3. Ninareh Mehrabi
4. Kristina Lerman
5. Nripsuta Ani Saxena

In Algorithms & Complexity

1. Deeparnab Chakrabarty
2. Suman Kalyan Bera
3. Fred Morstatter
4. Maryam Negahbani

Citations in the corpus

• A Survey on Bias and Fairness in Machine Learning (2019, methodology): “s using held-out node attributes (Step 2-supervised using other node attributes). Fair methods in domains similar to community detection are also proposed, such as graph embedding [21] and clustering [7, 30]. 5.2.6 Fair Causal Inference. Many researchers have used causal models and graphs to solve f”
• Fairness in Machine Learning: A Survey (2020, unknown): “Currently, unsupervised methods fall into three distinct areas: (1) fair clustering (e.g., References [7, 8, 15, 22, 23, 62, 67, 179, 248, 258, 269]); (2) investigating the presence and detection of discrimination in association rule mining (e.g., References [136, 230, 231]); and (3) transfer…”
• Algorithm fairness in artificial intelligence for medicine and healthcare (2023, unknown): “Similar to LAFTR is unsupervised fair clustering, which aims at learning attribute-invariant cluster assignments (which can also be done via adversarial learning for debiasing representations) 271,272 .”
• Fair Algorithms for Clustering (2019, background): “[24] define a notion of proportionally fair clustering where all possible groups of reasonably large size are entitled to choose a center for themselves.”