Fast and effective algorithms for fair clustering at scale

Problem
This paper addresses the gap in fair clustering algorithms that effectively balance clustering quality and fairness, particularly in large-scale datasets. Existing methods either lack control over the cost-fairness trade-off or do not scale well, leading to suboptimal solutions in fairness-sensitive applications. The authors present a preprint work that aims to provide a scalable solution while ensuring that protected groups are adequately represented in each cluster.

Method
The authors propose a general framework for fair clustering that allows for precise control over the trade-off between clustering cost (defined as the sum of squared Euclidean distances from objects to their cluster centers) and fairness. They introduce three heuristics based on this framework:

1. Quality-Focused Heuristic: Prioritizes solution quality and allows for the incorporation of additional constraints.
2. Scalability-Focused Heuristic: Enhances scalability while maintaining high solution quality.
3. Maximum Scalability Heuristic: Optimized for speed, capable of producing solutions for datasets with millions of objects in seconds.

The heuristics leverage efficient algorithms to ensure that the clustering process remains computationally feasible even as dataset sizes increase. The authors provide a detailed description of the algorithms, including their computational complexity and the specific adjustments made to traditional clustering methods to accommodate fairness constraints.

Results
The proposed heuristics were evaluated against existing fair clustering methods on benchmark datasets. The results indicate significant improvements in both clustering quality and fairness metrics. For instance, the maximum scalability heuristic demonstrated the ability to process datasets with over a million objects, achieving clustering costs that were 30% lower than the best-performing baseline while maintaining fairness levels within user-defined thresholds. The authors report that their methods consistently outperform state-of-the-art approaches across various metrics, including silhouette scores and fairness indices.

Limitations
The authors acknowledge several limitations in their work. First, while the heuristics are designed for scalability, they may still face challenges with extremely high-dimensional data, which could affect clustering performance. Additionally, the trade-off between cost and fairness is inherently problem-specific, and the heuristics may require fine-tuning for optimal performance in different contexts. The authors also note that their framework does not address the potential biases in the initial data, which could influence the fairness outcomes.

Why it matters
This work has significant implications for the deployment of clustering algorithms in fairness-sensitive domains, such as hiring practices, loan approvals, and educational admissions. By providing scalable and effective solutions for fair clustering, the authors enable practitioners to implement fairer decision-making processes that ensure equitable representation of protected groups. The framework and heuristics can serve as a foundation for future research in fair machine learning, particularly in developing more sophisticated algorithms that can handle larger datasets while maintaining fairness.

Authors: Claudio Mantuano, Manuel Kammermann, Philipp Baumann
Source: arXiv:2605.13759
URL: https://arxiv.org/abs/2605.13759v1