Fast and effective algorithms for fair clustering at scale

• URL: http://arxiv.org/abs/2605.13759v1
• Date: Wed, 13 May 2026 16:40:07 GMT
• Title: Fast and effective algorithms for fair clustering at scale
• Abstract summary: We address a fair clustering problem in which objects belong to protected groups.<n>The objective is to minimize the clustering cost, defined as the sum of squared Euclidean distances between the objects and the centers of their clusters.<n>We propose a general framework for fair clustering that provides precise control over the cost-fairness trade-off and introduce threes based on it.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering is an unsupervised machine learning task that consists of identifying groups of similar objects. It has numerous applications and is increasingly used in fairness-sensitive domains where objects represent individuals, such as customers, employees, or students. We address a fair clustering problem in which objects belong to protected groups. The problem consists of partitioning the objects into a predefined number of clusters while attaining a user-defined target level of fairness, meaning that each protected group is sufficiently represented in each cluster. The objective is to minimize the clustering cost, defined as the sum of squared Euclidean distances between the objects and the centers of their clusters. Since clustering cost and fairness are generally in conflict, managing the trade-off between them is essential in practical applications. Existing methods provide limited control over this trade-off and either fail to scale to large datasets or, when they scale, produce low-quality solutions. We propose a general framework for fair clustering that provides precise control over the cost-fairness trade-off and introduce three heuristics based on it. The first heuristic focuses on solution quality and the flexibility to incorporate additional constraints, the second improves scalability while retaining high solution quality, and the third is designed for maximum scalability, producing solutions for instances with millions of objects in seconds. The proposed heuristics outperform existing approaches in comprehensive numerical experiments on benchmark datasets. The source code of our heuristics and instructions for reproducing the experiments are publicly available on GitHub.

Related papers

• ESMC: MLLM-Based Embedding Selection for Explainable Multiple Clustering [79.69917150582633]
  Multi-modal large language models (MLLMs) can be leveraged to achieve user-driven clustering.<n>Our method first discovers that MLLMs' hidden states of text tokens are strongly related to the corresponding features.<n>We also employ a lightweight clustering head augmented with pseudo-label learning, significantly enhancing clustering accuracy.
  arXiv  Detail & Related papers  (2025-11-30T04:36:51Z)
• Parameter-Free Clustering via Self-Supervised Consensus Maximization (Extended Version) [50.41628860536753]
  We propose a novel and fully parameter-free clustering framework via Self-supervised Consensus Maximization, named SCMax.<n>Our framework performs hierarchical agglomerative clustering and cluster evaluation in a single, integrated process.
  arXiv  Detail & Related papers  (2025-11-12T11:17:17Z)
• Towards Fair Representation: Clustering and Consensus [1.7243216387069678]
  We find a consensus clustering that is not only representative but also fair with respect to specific protected attributes.<n>As part of our investigation, we examine how to minimally modify an existing clustering to enforce fairness.<n>We develop an optimal algorithm for datasets with equal group representation and near-linear time constant factor approximation algorithms.
  arXiv  Detail & Related papers  (2025-06-10T10:33:21Z)
• A3S: A General Active Clustering Method with Pairwise Constraints [66.74627463101837]
  A3S features strategic active clustering adjustment on the initial cluster result, which is obtained by an adaptive clustering algorithm. In extensive experiments across diverse real-world datasets, A3S achieves desired results with significantly fewer human queries.
  arXiv  Detail & Related papers  (2024-07-14T13:37:03Z)
• Stable Cluster Discrimination for Deep Clustering [7.175082696240088]
  Deep clustering can optimize representations of instances (i.e., representation learning) and explore the inherent data distribution. The coupled objective implies a trivial solution that all instances collapse to the uniform features. In this work, we first show that the prevalent discrimination task in supervised learning is unstable for one-stage clustering. A novel stable cluster discrimination (SeCu) task is proposed and a new hardness-aware clustering criterion can be obtained accordingly.
  arXiv  Detail & Related papers  (2023-11-24T06:43:26Z)
• Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation [65.268245109828]
  Online deep clustering refers to the joint use of a feature extraction network and a clustering model to assign cluster labels to each new data point or batch as it is processed. While faster and more versatile than offline methods, online clustering can easily reach the collapsed solution where the encoder maps all inputs to the same point and all are put into a single cluster. We propose a method that does not require data augmentation, and that, differently from existing methods, regularizes the hard assignments.
  arXiv  Detail & Related papers  (2023-03-29T08:23:26Z)
• Socially Fair Center-based and Linear Subspace Clustering [8.355270405285909]
  Center-based clustering and linear subspace clustering are popular techniques to partition real-world data into smaller clusters. Different clustering cost per point for different sensitive groups can lead to fairness-related harms. We propose a unified framework to solve socially fair center-based clustering and linear subspace clustering.
  arXiv  Detail & Related papers  (2022-08-22T07:10:17Z)
• Clustering to the Fewest Clusters Under Intra-Cluster Dissimilarity Constraints [0.0]
  equiwide clustering relies neither on density nor on a predefined number of expected classes, but on a dissimilarity threshold. We review and evaluate suitable clustering algorithms to identify trade-offs between the various practical solutions for this clustering problem.
  arXiv  Detail & Related papers  (2021-09-28T12:02:18Z)
• Fair Clustering Under a Bounded Cost [33.50262066253557]
  Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective.
  arXiv  Detail & Related papers  (2021-06-14T08:47:36Z)
• You Never Cluster Alone [150.94921340034688]
  We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation. We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one. By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
  arXiv  Detail & Related papers  (2021-06-03T14:59:59Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.