Fair Clustering

Fair clustering aims to partition data into groups while mitigating biases stemming from sensitive attributes like race or gender, ensuring equitable representation across clusters. Current research focuses on developing algorithms that incorporate fairness constraints into established clustering methods like k-means and spectral clustering, often employing integer programming, exponential tilting, or matrix factorization techniques to achieve this. These advancements address concerns about algorithmic bias in various applications, from resource allocation to personalized federated learning, promoting more equitable outcomes and advancing the understanding of fairness in unsupervised machine learning. The field is also actively exploring different fairness metrics and their trade-offs with clustering quality, as well as the robustness of fair clustering algorithms to adversarial attacks.

Papers

October 19, 2024

A Semidefinite Relaxation Approach for Fair Graph Clustering
Sina Baharlouei, Sadra Sabouri
Network Analysis Fair Clustering Semidefinite Relaxation Clustering Quality

October 16, 2024

Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights
Ameet Gadekar, Aristides Gionis, Suhas Thejaswi
Practical Algorithm Fair Clustering Facility Location Problem Median Problem Complexity Analysis Better Approximation K$ Clustering Data Summarization

September 4, 2024

Fair Minimum Representation Clustering via Integer Programming
Connor Lawless, Oktay Gunluk
K Mean Integer Programming Fair Clustering Optimal Clustering Median Problem

July 27, 2024

Enhancing Group Fairness in Federated Learning through Personalization
Yifan Yang, Ali Payani, Parinaz Naghizadeh
Personalized Federated Learning Group Fairness Fairness Accuracy Fair Clustering

June 24, 2024

Efficient k-means with Individual Fairness via Exponential Tilting
Shengkun Zhu, Jinshan Zeng, Yuan Sun, Sheng Wang, Xiaodong Li, Zhiyong Peng
Resource Allocation Fairness Metric Tilting Angle Individual Fairness Fair Clustering

June 22, 2024

Fair Clustering: Critique, Caveats, and Future Directions
John Dickerson, Seyed A. Esmaeili, Jamie Morgenstern, Claire Jie Zhang
Future Direction Common Pitfall Fairness Notion Fair Clustering Lower Critique Accuracy

June 2, 2024

Robust Fair Clustering with Group Membership Uncertainty Sets
Sharmila Duppala, Juan Luque, John P. Dickerson, Seyed A. Esmaeili
Robustness Guarantee Fair Clustering Uncertainty Set Population Level Clustering Quality

May 22, 2024

Semantic Equitable Clustering: A Simple, Fast and Effective Strategy for Vision Transformer
Qihang Fan, Huaibo Huang, Mingrui Chen, Ran He
Vision Transformer Semantic Segmentation Vision Model Global Attention Fair Clustering Simple Strategy Token Clustering

May 16, 2024

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
Sayan Bandyapadhyay, Eden Chlamtáč, Yury Makarychev, Ali Vakilian
Polynomial Time Fairness Constraint Fair Clustering Polynomial Time Approximation

March 24, 2024

From Discrete to Continuous: Deep Fair Clustering With Transferable Representations
Xiang Zhang
Group Fairness Discrete Environment Continuous Speech Transferable Representation Fair Clustering Fairness Objective Clustering Friendly Representation

February 16, 2024

Towards Cohesion-Fairness Harmony: Contrastive Regularization in Individual Fair Graph Clustering
Siamak Ghodsi, Seyed Amjad Seyedi, Eirini Ntoutsi
Group Fairness Fair Clustering Contrastive Regularization Fairness Regularization

February 9, 2024

A Scalable Algorithm for Individually Fair K-means Clustering
MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi
Data Clustering Local Search Fair Clustering Scalable Algorithm K$ Clustering

December 14, 2023

Fair Clustering: A Causal Perspective
Fritz Bayer, Drago Plecko, Niko Beerenwinkel, Jack Kuipers
Fairness Notion Fair Clustering Causal Fairness

November 23, 2023

A Unified Framework for Fair Spectral Clustering With Effective Graph Learning
Xiang Zhang, Qiao Wang
Unified Framework Spectral Clustering Graph Structure Learning Fair Clustering Group Fairness Constraint

November 21, 2023

Fair Polylog-Approximate Low-Cost Hierarchical Clustering
Marina Knittel, Max Springer, John Dickerson, MohammadTaghi Hajiaghayi
Fair Machine Learning Hierarchical Clustering Fair Clustering Logarithmic Barrier

September 2, 2023

Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$
Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, Julian Wargalla
Clustering Algorithm Fair Clustering Median Problem K$ Center

July 22, 2023

Spectral Normalized-Cut Graph Partitioning with Fairness Constraints
Jia Li, Yanhao Wang, Arpit Merchant
Fairness Constraint Fair Clustering Spectral Algorithm Normalized Cut Disjoint Cluster

June 11, 2023

Approximation Algorithms for Fair Range Clustering
Sèdjro S. Hotegni, Sepideh Mahabadi, Ali Vakilian
Approximation Algorithm Fair Clustering Optimal Clustering Constant Factor Approximation

May 31, 2023

Doubly Constrained Fair Clustering
John Dickerson, Seyed A. Esmaeili, Jamie Morgenstern, Claire Jie Zhang
Group Fairness Fairness Notion Fair Clustering

May 27, 2023

Fair Clustering via Hierarchical Fair-Dirichlet Process
Abhisek Chakraborty, Anirban Bhattacharya, Debdeep Pati
Procedural Fairness Unsupervised Learning Algorithmic Fairness Objective Function Fair Clustering Hierarchical Dirichlet Process