🤖 machine learning

Fast and effective algorithms for fair clustering at scale

This paper proposes a general framework and three scalable heuristics for fair clustering that effectively balance the trade-off between minimizing clustering cost and ensuring user-defined fairness constraints across protected groups, outperforming existing methods on large-scale datasets.

Original authors: Claudio Mantuano, Manuel Kammermann, Philipp Baumann

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Claudio Mantuano, Manuel Kammermann, Philipp Baumann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a party planner tasked with seating 1,000 guests at 10 round tables. Your goal is to seat people who know each other or have similar interests together (this is clustering). However, you also have a strict rule: every table must have a fair mix of guests from different backgrounds, such as different ages, genders, or neighborhoods (this is fairness).

If you just put the most similar people together without thinking about the mix, you might accidentally end up with a table full of only one group and another table full of only another. This creates "unfair" tables. The problem is that making the tables perfectly mixed often means you have to seat people further apart from their "best friends," which makes the party less efficient.

This paper introduces three new, super-fast ways to solve this seating arrangement problem for massive parties (datasets with millions of people) while keeping the tables fair and the guests happy.

The Core Problem: The "Fairness vs. Cost" Tug-of-War

The authors describe a constant struggle between two goals:

Low Cost: Keeping guests close to their "center" (the average person at the table) so they feel comfortable.
High Fairness: Ensuring every table has the right proportion of different groups.

Usually, if you force a table to be perfectly fair, the "cost" (the distance guests have to travel to sit there) goes up. Existing methods were like clumsy planners: they either couldn't handle huge parties, or they gave the planner very little control over how fair the tables should be. They often used a "weight" knob that was hard to tune precisely.

The Solution: A Three-Tool Kit

The authors propose a general framework (a master plan) and three specific tools (heuristics) to handle different party sizes. All three tools use a "decomposition scheme," which is like a two-step dance:

Assign: Decide who sits at which table.
Update: Move the center of the table to the average position of the people sitting there.
They repeat this dance until the seating arrangement stops improving.

Here are the three tools:

1. MPFC: The "Precision Architect"

Best for: Medium-sized parties (up to 100,000 guests).
How it works: This tool treats the seating assignment like a complex math puzzle (a Binary Linear Program). It calculates the perfect way to seat everyone to meet the fairness rules while minimizing distance.
The Analogy: Imagine a super-strict architect who checks every single possible seating chart against a blueprint before picking the best one. It's incredibly accurate and flexible (you can add rules like "these two people must sit together"), but it gets slow if the party gets too huge.

2. MS-FlowFC: The "Traffic Manager"

Best for: Large parties with one specific type of diversity (e.g., just gender, or just age).
How it works: Instead of solving one giant math puzzle, this tool breaks the problem into smaller, faster steps. It uses a "minimum-cost flow" algorithm, which is like managing traffic on a highway. It sends groups of people to tables in stages, ensuring no road gets jammed and the rules are followed.
The Analogy: Think of a traffic cop directing cars. Instead of planning the whole city's traffic at once, they direct one lane of cars, then the next, ensuring everyone gets to their destination quickly without crashing. It's much faster than the Architect but works best when there's only one type of "traffic rule" (one sensitive feature).

3. S-MPFC: The "Crowd Summarizer"

Best for: Massive parties (millions of guests).
How it works: This is the ultimate speed tool. Before the dance begins, it groups similar guests together into "batches" and creates a single "representative" for each batch. It then solves the seating problem for these representatives (a tiny version of the party) and maps the results back to the real guests.
The Analogy: Imagine you have a crowd of a million people. Instead of asking everyone where they want to sit, you ask 100 "spokespeople" to represent groups of 10,000 people. You figure out where the 100 spokespeople sit, and then everyone else just follows their representative. This allows the planner to solve the problem in seconds.

The Results: Why This Matters

The authors tested these tools against existing methods using real-world data (like credit card records, census data, and even cyber-security logs).

Speed: The new tools are drastically faster. On a dataset with nearly 2.5 million people, the "Crowd Summarizer" (S-MPFC) was 99.7% faster than the previous best method while still finding better seating arrangements.
Quality: The new methods found solutions that were not only faster but also had lower "cost" (guests were happier) than the competition.
Control: The authors introduced a "tolerance parameter" (a dial from 0 to 1).
- Turn it to 0: You demand perfect fairness (every table is a perfect mirror of the whole crowd).
- Turn it to 1: You ignore fairness completely (standard clustering).
- The Magic: This dial gives the user precise control. Previous methods were like a light switch (on/off); this is a dimmer switch, allowing you to find the exact balance you need.

Summary

The paper doesn't just say "we made it faster." It claims to have built a flexible, precise, and scalable system that solves the "fair clustering" problem better than anything currently available. Whether you have 100 guests or 10 million, there is a tool in this kit that can seat them fairly and efficiently, giving the planner exact control over how strict the fairness rules should be.

Technical Summary: Fast and Effective Algorithms for Fair Clustering at Scale

Problem Definition

The paper addresses the fair clustering problem, an extension of the unsupervised machine learning task of partitioning a dataset into $k$ clusters of similar objects. In this context, objects possess sensitive features (e.g., race, gender) defining protected groups. The goal is to minimize the clustering cost (defined as the sum of squared Euclidean distances between objects and their cluster centers, i.e., $k$ -means) while satisfying fairness constraints.

Fairness is measured using the concept of balance, originally introduced by Chierichetti et al. (2017). A clustering solution is considered fair if, for every sensitive feature, the ratio of objects from any two protected groups within a cluster meets a minimum threshold. The authors introduce a tolerance parameter $\lambda \in [0, 1]$ to control the target balance. A value of $\lambda=0$ requires the highest level of fairness (matching the dataset's global balance), while $\lambda=1$ imposes no fairness requirements, reducing the problem to vanilla $k$ -means. The problem is NP-hard, generalizing the standard $k$ -means problem.

Existing methods suffer from three primary limitations:

Lack of Flexibility: Many are restricted to specific problem variants and cannot easily incorporate practical constraints (e.g., cardinality constraints, must-link/cannot-link constraints).
Coarse Control: Methods analyzing the cost-fairness trade-off often rely on weight parameters in the objective function, offering only indirect and imprecise control over the desired fairness level.
Scalability vs. Quality: Scalable approaches often rely on approximations (fairlets or coresets) that can lead to information loss and degraded solution quality, or they fail to scale to millions of objects.

Methodology

The authors propose a general framework based on the $k$ -means decomposition scheme (alternating between object assignment and cluster center updates) and introduce three heuristics that differ in their implementation of the assignment step:

1. Mathematical Programming-based Fair Clustering (MPFC)

Mechanism: In the assignment step, objects are assigned to fixed cluster centers by solving a Binary Linear Program (BLP).
Constraints: The BLP includes constraints ensuring the target balance is met for every sensitive feature and cluster. The constraints are linearized using the tolerance parameter $\lambda$ .
Scope: Suitable for instances up to ~100,000 objects. It offers high flexibility to incorporate additional constraints (e.g., cardinality, must-link) directly into the BLP.
Limitation: Solving the full BLP becomes computationally expensive for very large $n$ and $k$ .

2. Multi-stage Minimum-Cost Flow-based Fair Clustering (MS-FlowFC)

Mechanism: Designed for instances with a single sensitive feature. The assignment step is decomposed into multiple stages, one for each protected group (ordered by size).
Algorithm: Instead of a single BLP, the assignment is solved as a sequence of minimum-cost flow problems.
- Stage 1: The largest protected group is assigned to nearest centers.
- Subsequent Stages: Remaining groups are assigned by solving a flow network where node demands and arc capacities are dynamically adjusted to respect fairness bounds derived from previous stages.
Advantage: Minimum-cost flow problems are solvable in polynomial time, offering significant speedups over MPFC while maintaining high solution quality.
Limitation: Restricted to single sensitive features.

3. Scalable Mathematical Programming-based Fair Clustering (S-MPFC)

Mechanism: Designed for massive-scale datasets (millions of objects). It combines a modified MPFC with a preprocessing technique.
Preprocessing: The dataset is first clustered using vanilla $k$ -means to form "batches" (subsets of similar objects). Each batch is represented by a single representative (the batch centroid) with associated weights indicating the count of objects from each protected group.
Clustering: The BLP is solved on the reduced set of representatives rather than individual objects. The resulting assignments are mapped back to the original objects.
Innovation: Unlike fairlets or coresets, these batches do not need to satisfy fairness constraints internally; the fairness is enforced at the assignment level of the representatives.
Advantage: Capable of processing millions of objects in seconds.

Key Contributions

Precise Control: The framework introduces a single tolerance parameter $\lambda$ that directly controls the target balance, overcoming the coarse control of weight-based trade-off methods.
Flexibility: The BLP-based approaches (MPFC and S-MPFC) can be readily adapted to alternative objectives (e.g., $k$ -median, $k$ -medoids) and can incorporate application-specific constraints like cardinality or linkage constraints.
Scalability Techniques:
- A decomposition strategy for the assignment step using minimum-cost flow (MS-FlowFC) that avoids integer programming solvers.
- A preprocessing technique (S-MPFC) that aggregates data without imposing internal fairness constraints on the subsets, preserving more information than traditional fairlet decomposition.
Exact Benchmarks: The authors provide two exact methods for benchmarking: a Mixed-Integer Quadratically Constrained Programming (MIQCP) model and a Set-Variable-based (SetVars) formulation, which are claimed to be the first exact methods for this specific fair $k$ -means problem.

Experimental Results

The authors evaluated their methods on synthetic and real-world datasets (ranging from 21 to ~2.5 million objects) against benchmarks including the scalable fair clustering (SFC) algorithm of Backurs et al. (2019) and the order-and-cut (O&C) algorithm of Li et al. (2024).

Solution Quality:
- On small instances, MPFC and MS-FlowFC consistently found optimal or near-optimal solutions, often outperforming exact solvers within reasonable time limits.
- On medium-scale datasets (e.g., BANK-40K, ADULT), MPFC and MS-FlowFC consistently achieved lower clustering costs than SFC, with improvements ranging from ~1% to over 40% depending on the number of clusters and fairness level.
- On large-scale datasets (CENSUS1990, ~2.5M objects), S-MPFC produced higher-quality solutions than SFC.
Scalability and Running Time:
- S-MPFC demonstrated exceptional scalability, solving instances with 2.5 million objects in seconds. On the largest dataset, it reduced running time by 99.70% compared to SFC while improving solution quality.
- MS-FlowFC was the fastest among the non-scalable methods, with average running times 95.47% lower than SFC on medium-scale datasets.
- The proposed methods showed lower variability in solution quality across random seeds compared to SFC.
Cost-Fairness Trade-off:
- The proposed heuristics demonstrated precise control over the trade-off via $\lambda$ .
- Compared to O&C, MPFC and MS-FlowFC achieved the same or higher fairness levels with significantly lower clustering costs (average reduction of 24.33%).
- The cost increase required to achieve high fairness was marginal for the proposed methods compared to the steep cost increases observed in O&C.

Significance and Claims

The paper claims that the proposed heuristics address critical gaps in the fair clustering literature by providing a general framework that balances solution quality, scalability, and flexibility.

Practical Applicability: The methods are designed for real-world deployment where datasets are large and fairness requirements are strict. The ability to handle millions of objects in seconds makes them suitable for time-sensitive applications.
Superior Trade-off Management: The authors assert that their approach offers superior control over the cost-fairness trade-off compared to existing state-of-the-art methods, allowing practitioners to achieve specific fairness targets without incurring excessive clustering costs.
Robustness: The results indicate that the proposed methods are robust across different dataset sizes, cluster counts, and fairness levels, consistently outperforming leading benchmarks in both efficiency and effectiveness.

The authors conclude that while future work could explore additional constraints and alternative initialization strategies, the current heuristics represent a significant step forward in making fair clustering viable for large-scale, practical applications.