Fast and effective algorithms for fair clustering at scale

Claudio Mantuano, Manuel Kammermann, Philipp Baumann[6pt] Department of Business Administration, University of Bern,Engehaldenstrasse 4, 3012 Bern, Switzerland · 2026

Read Fast and effective algorithms for fair clustering at scale by Claudio Mantuano, Manuel Kammermann, Philipp Baumann[6pt] Department of Business Administration, University of Bern,Engehaldenstrasse 4, 3012 Bern, Switzerland (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13759.txt.

Introduction

Claudio Mantuano, Manuel Kammermann and Philipp Baumann address fair grouping at scale, splitting objects into a set cluster count with each guarded group shown in each cluster. The goal is cutting grouping cost, the sum of squared straight gaps between objects and cluster centres, against a user-defined fairness target. The authors propose a general frame giving precise cost-fairness trade-off control, with three rules. One targets answer quality and limit freedom, one lifts scale while keeping quality, and one tops scale, solving million-object cases in seconds.

Catalog record

CREATORClaudio Mantuano, Manuel Kammermann, Philipp Baumann[6pt] Department of Business Administration, University of Bern,Engehaldenstrasse 4, 3012 Bern, Switzerland
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104124
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13759

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast and effective algorithms for fair clustering at scale Claudio Mantuano, Manuel Kammermann, Philipp Baumann[6pt] Department of Business Administration, University of Bern,Engehaldenstrasse 4, 3012 Bern, Switzerland 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 1 1 1 https://github.com/claudio-mantuano/fair-clustering-at-scale . Keywords : Combinatorial optimization; Machine learning; Fair clustering; Heuristics; Minimum-cost flow † † footnotetext: * Corresponding author. Emails: [email protected], [email protected], [email protected]. 1 Introduction Clustering is an unsupervised machine learning task that consists of partitioning a dataset into subsets, called clusters, of similar objects. Clustering has a wide range of applications and is increasingly used to support or automate decisions that can have a direct impact on people’s lives. Common examples include bank loan disbursement ( 54 ; 7 ; 17 ; 9 ) , human resources performance management ( 56 ) , recruitment ( 52 ; 55 ) , student evaluation ( 35 ) , and college admissions ( 42 ; 16 ) . In such settings, vanilla clustering algorithms (i.e., conventional algorithms that do not explicitly account for fairness) may produce clusters in which certain groups of individuals are under-represented relative to their proportion in the dataset. This under-representation may introduce social disparities or amplify existing ones. According to the disparate impact doctrine of 23 , the outcomes of algorithmic decision-making systems should not adversely affect specific groups of individuals. Simply removing the sensitive feature (e.g., race) that identifies the protected groups (e.g., African-American, Asian, Caucasian) is generally ineffective. Other non-sensitive features (such as income or height) may still be correlated with the sensitive feature. For instance, 37 found that removing the sensitive feature “race” from a decision support system used for college admissions reduced the diversity of the top-ranked pool without improving the academic merit of the students in that pool. Building on the disparate impact doctrine, 19 introduced the concept of fair clustering, marking the foundation of a now well-established line of research aimed at ensuring a fair assignment of protected groups to clusters. More recent studies have broadened the original scope of fair clustering by exploring its application to new domains, such as the security of cyber-physical systems ( 49 ; 27 ; 44 ; 20 ) . Several variants of fair clustering problems have been introduced in the literature (see 18 ). These variants differ mainly in how clustering cost is defined and how fairness is measured. We consider here the most common definition of the fair clustering problem, where center-based clustering cost (such as the well-known k -means clustering cost) and a group-level fairness notion based on 19 (the balance) are employed. More specifically, the fair clustering problem considered here can be defined as follows. Given are a set of objects, represented by feature vectors, a set of sensitive features with two or more protected groups, and a number of clusters to be constructed. Each object belongs to one protected group of each sensitive feature. The goal is to partition the objects into clusters such that the k -means clustering cost, defined as the sum of squared Euclidean distances between the objects and the corresponding cluster centers, is minimized. The cluster centers are computed as the mean of the feature vectors of the objects assigned to each cluster. Fairness is measured for each cluster based on the distribution of protected groups within that cluster. A clustering solution is considered fair if each protected group is sufficiently represented in each cluster. The highest level of fairness is achieved when a protected group has the same representation in each cluster as it does in the entire dataset. The lowest level of fairness is achieved when a protected group is not represented at all in one of the clusters. We propose determining the required level of representation for each protected group using a single control parameter, which we refer to as the tolerance parameter. A tolerance value of zero requires the highest level of fairness, while a tolerance value of one imposes no representation requirement. Hence, the tolerance parameter allows us to control the cost-fairness trade-off. The fair clustering problem considered here is NP-hard, as it generalizes the k -means clustering problem (see 3 ). 19 were the first to introduce fair clustering. They proposed a two-step approach that first constructs small fairness-preserving micro-clusters (fairlets) and then applies a vanilla clustering algorithm to group these fairlets. Following the seminal work of 19 , a wide range of fair clustering methods has been developed. The development of algorithms has focused on three main research directions. The first research direction has focused on developing algorithms for extended or modified versions of the fair clustering problem (e.g., see 14 ; 50 ; 15 ). The second research direction has focused on the development of algorithms for analyzing the trade-off between clustering cost and fairness (e.g., see 59 ; 38 ). The third research direction has focused on developing scalable fair clustering approaches. 6 proposed a more efficient technique for constructing fairlets, which enables the fair clustering approach of 19 to scale to much larger datasets. 50 introduced a preprocessing technique for constructing so-called coresets for fair clustering. The coresets are summaries of objects of the dataset and allow fair clustering to be sped up by reducing the input size. In contrast to fairlets, coresets are not fairness-preserving, which implies that fair clustering algorithms need to be applied instead of vanilla clustering algorithms. Despite the vast research effort, the existing algorithms still have limitations that hinder their use in practice. A limitation that affects most existing algorithms is that they are only applicable to specific variants of the fair clustering problem and lack the flexibility to incorporate practical constraints such as cardinality constraints or must-link and cannot-link constraints. A limitation of existing algorithms for analyzing the cost-fairness trade-off is that they rely on a weight parameter to

Read the complete text