Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications

AI summary

Overview

Research area: Theoretical machine learning and algorithm design — specifically fairness in unsupervised clustering, approximation algorithms, and computational hardness.

Technical level: Advanced. The paper is a theory paper: NP-hardness reductions and approximation guarantees, with no empirical experiments reported.

Scope: The paper generalizes the "closest fair clustering" problem from two protected groups to an arbitrary number of groups, proves the generalized problem is NP-hard, and gives near-linear-time approximation algorithms that also improve bounds for fair correlation clustering and fair consensus clustering.

What This Paper Is About

Clustering algorithms can produce clusters that under-represent marginalized groups because of bias in the training data. A natural fix is post-processing: take an existing clustering and change as few point assignments as possible until every cluster reflects the global proportions of each protected group — this is the "closest fair clustering" problem. Prior work (Chakraborty et al., COLT'25) solved only the two-group case; this paper addresses the realistic setting where points carry many groups reflecting attributes such as age, ethnicity, and gender.

Key Contributions

1. Generalized closest fair clustering to |χ| groups. For arbitrary global proportions p₁:p₂:…:p_|χ|, the authors give an O(|χ|^{3.81})-approximation running in O(|V| log|V|) time, where χ is the set of colors and V the point set.

2. Stronger guarantees for the equi-proportion case. When every group must appear equally in each output cluster, they give an O(|χ|^{1.6} log^{2.81}|χ|)-approximation, improved to O(|χ|^{1.6}) when |χ| is a power of two.

3. NP-hardness for more than two groups. They prove k-Closest EquiFair is NP-hard for any k ≥ 3, even when all color groups are equal in size — a stark contrast with the two-group case, where an exact near-linear-time algorithm exists.

4. Improved bounds for two downstream problems. They derive an O(|χ|^{3.81})-approximation for fair correlation clustering that removes the dependence on the max-min color ratio (which can be polynomial in |V|) present in the earlier O(q²|χ|²) bound, and give the first approximation algorithms for fair consensus clustering with more than two groups.

Main Findings

• General-ratio closest fair clustering: An O(|χ|^{3.81})-approximation in O(|V| log|V|) time via a two-stage algorithm (create-pdc then make-pdc-fair), where the first stage produces an O(|χ|)-close p-divisible clustering (Lemma 3) and the second contributes an O(|χ|^{2.81}) factor (Lemma 2).

• Equi-proportion closest fair clustering: O(|χ|^{1.6} log^{2.81}|χ|)-approximation; O(|χ|^{1.6}) when |χ| is a power of two, obtained by the fairpower-of-two algorithm, whose factor arises as 3^{log|χ|} = |χ|^{1.6} from log|χ| iterations each costing a factor of 2.

• Hardness gap: k-Closest EquiFair is NP-hard for every k ≥ 3 (Theorem 3), shown by reduction from 3-Partition (Garey and Johnson 1975). The exact algorithm available for two groups therefore does not extend.

• Fair correlation clustering: O(|χ|^{3.81})-approximation for arbitrary ratios, versus the prior O(q²|χ|²) bound of Ahmadian et al. (AISTATS'20) and Ahmadi et al. (2020), where q = max(p_j)/min(p_j) can be as large as a polynomial in |V|. Equi-proportion improves to O(|χ|^{1.6} log^{2.81}|χ|), and to O(|χ|^{1.6}) for |χ| a power of two, beating the prior O(|χ|²).

• Fair consensus clustering: The same guarantees (O(|χ|^{3.81}) general, O(|χ|^{1.6} log^{2.81}|χ|) equi-proportion, O(|χ|^{1.6}) for power-of-two |χ|), obtained by combining a triangle-inequality argument with the closest fair clustering results. This is the first treatment of the multi-group case; prior work covered only two groups. Details are deferred to the appendix.

• Empirical evaluation: None reported. The paper contains no datasets, benchmarks, or experimental results; the claims are algorithmic and complexity-theoretic.

Methodology in Plain English

The approach is to reduce the hard multi-group problem into easier pieces that can each be handled with a bounded loss, then combine the losses.

For the equi-proportion case, the algorithm works in log|χ| iterations. Colors are grouped into blocks whose sizes double each round, and within each block the counts of different colors are equalized by comparing neighboring blocks, trimming the larger one to match the smaller, and greedily merging trimmed pieces into fair clusters (the multi-GM subroutine). A separate routine combines these intra-block guarantees across blocks.

For arbitrary proportions, the authors split the work in two. First, create-pdc transforms any input clustering into one where the count of color c_j in each cluster is a multiple of p_j (a "p-divisible" clustering), classifying clusters as CUT or MERGE and shifting surplus points between them. Second, make-pdc-fair builds the final fair clustering by hierarchically merging color groups into blocks and rebalancing each cluster so that group proportions are respected, using T = ⌈log₂ r⌉ iterations.

Because the problem is NP-hard for k ≥ 3, exact solutions are out of reach, so the paper proves approximation factors by chaining a sequence of intermediate clusterings, each losing only a constant factor, and multiplying the losses across the log-many levels. Hardness is established by a polynomial-time reduction from the restricted 3-Partition problem, where each integer lies in (T/4, T/2) and is at most d^b, with a "yes"/"no" threshold τ constructed so that satisfiable instances correspond exactly to clusterings within distance τ.

Why This Matters

Impact on research: The paper settles an open direction from Chakraborty et al. (COLT'25) and shows a qualitative complexity jump between two groups and three or more — exact algorithms exist for the former, NP-hardness holds for the latter. It also improves the state of the art for fair correlation clustering and opens fair consensus clustering to multi-group settings.

Real-world applications (as described in the paper):

• Auditing and repairing deployed clusterings used for decision-making or analysis, since biased clusters can lead to inequitable treatment.
• Correlation clustering in data mining, social network analysis, computational biology, and marketing analysis, where edges labeled + or − must be partitioned fairly.
• Consensus clustering in bioinformatics, data mining, and community detection, where one representative clustering must be extracted from many.
• Fairness across intersecting sensitive attributes such as age, ethnicity, gender, and race, which binary coloring schemes cannot capture.

Industry relevance: Since the algorithms run in near-linear time and act as a post-processing step, they can be layered on top of existing clustering pipelines that already produce biased outputs, rather than requiring those pipelines to be rebuilt.

Future Directions

• Empirical validation: No experiments are reported, so testing the algorithms on real datasets and measuring practical running time and solution quality remains open.
• Tightening approximation ratios: Closing the gap between the O(|χ|^{1.6} log^{2.81}|χ|) or O(|χ|^{3.81}) guarantees and the NP-hardness results, and establishing matching hardness-of-approximation bounds.
• Relaxed fairness notions: Extending the approach to the relaxed fairness setting studied by Ahmadian and Negahbani (2023) for correlation clustering.
• Broader clustering variants: Applying the framework to other fair clustering objectives such as k-center, k-median, k-means, proportional clustering, and pairwise fair clustering, which the related-work section lists but the paper does not solve.
• Non-disjoint and non-binary attributes: The formalism assumes disjoint color groups; real protected attributes are often multiple and non-binary, so handling overlapping attributes is a natural extension.

Target Audience

Researchers in algorithmic fairness, approximation algorithms, and theoretical computer science who work on constrained clustering; graduate students looking for open problems at the intersection of fairness and combinatorial optimization; and practitioners designing post-processing fairness repairs for clustering-based systems who need algorithms with provable guarantees. Readers should be comfortable with NP-hardness, approximation factors, and clustering distance measures.

Authors’ abstract

Clustering is a fundamental task in machine learning and data analysis, but it frequently fails to provide fair representation for various marginalized communities defined by multiple protected attributes -- a shortcoming often caused by biases in the training data. As a result, there is a growing need to enhance the fairness of clustering outcomes, ideally by making minimal modifications, possibly as a post-processing step after conventional clustering. Recently, Chakraborty et al. [COLT'25] initiated the study of \emph{closest fair clustering}, though in a restricted scenario where data points belong to only two groups. In practice, however, data points are typically characterized by many groups, reflecting diverse protected attributes such as age, ethnicity, gender, etc. In this work, we generalize the study of the \emph{closest fair clustering} problem to settings with an arbitrary number (more than two) of groups. We begin by showing that the problem is NP-hard even when all groups are of equal size -- a stark contrast with the two-group case, for which an exact algorithm exists. Next, we propose near-linear time approximation algorithms that efficiently handle arbitrary-sized multiple groups, thereby answering an open question posed by Chakraborty et al. [COLT'25]. Leveraging our closest fair clustering algorithms, we further achieve improved approximation guarantees for the \emph{fair correlation clustering} problem, advancing the state-of-the-art results established by Ahmadian et al. [AISTATS'20] and Ahmadi et al. [2020]. Additionally, we are the first to provide approximation algorithms for the \emph{fair consensus clustering} problem involving multiple (more than two) groups, thus addressing another open direction highlighted by Chakraborty et al. [COLT'25].