Research map / Learning theory and algorithms / Clustering
Fair Clustering via Alignment
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Fair Clustering via Alignment (FCA), which decomposes the perfectly fair K-means objective into an optimal-transport coupling cost plus clustering cost in an aligned space, alternating coupling (linear program) and K-means center updates, with a relaxed FCA-C variant for controlling fairness level.
Problem
Fair clustering under group (proportional) fairness: maximizing clustering utility (low K-means cost) while satisfying a given balance/fairness level, where existing pre-, in-, and post-processing methods are suboptimal or numerically unstable.
Approach
Decompose the perfectly fair K-means cost into a transport cost between two protected groups' points plus a clustering cost on their midpoints (aligned space); alternately optimize a joint coupling via linear programming and cluster centers on the aligned space, so matching and centers are jointly optimized without explicit fairness constraints.
Key results
- On Adult with L2 normalization, FCA attains Bal 0.493 at Cost 0.328 versus FRAC 0.490 at Cost 0.340 and SFC 0.489 at Cost 0.534 (Bal* 0.494).
- On Census, FCA reaches Bal 0.962 with Cost 0.477, while VFC only reaches Bal 0.749 (Cost 0.432) with L2 normalization.
- On RMNIST, FCA achieves ACC 89.0 and Bal 1.000, the best among compared methods, slightly above FCMI (ACC 88.4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FCA instead of fair-unaware standard clustering | K-means on Adult, Bank, and Census · Adult, Bank, Census | Bal: Adult: 0.223 -> 0.493; Bank: 0.325 -> 0.645; Census: 0.024 -> 0.962 | Helped |
| Use FCA instead of SFC | Fair clustering on Adult, Bank, and Census · Adult, Bank, Census | Cost: Adult: 0.534 -> 0.328; Bank: 0.410 -> 0.264; Census: 1.015 -> 0.477 | Helped |
| Use FCA instead of VFC | Fair clustering on Adult, Bank, and Census · Adult, Bank, Census | Bal: Adult: 0.437 -> 0.493; Bank: 0.568 -> 0.645; Census: 0.749 -> 0.962 | Helped |
| Use FCA instead of FCMI | Visual clustering on RMNIST · RMNIST | ACC: 88.4 -> 89.0 | Helped |
| Use FCA instead of FCMI | Visual clustering on Office-31 · Office-31 | ACC: 70.0 -> 67.6 | Hurt |
| Use FCA instead of DFC | Visual clustering on Office-31 · Office-31 | Bal: 0.165 -> 0.270 | Helped |
| Use FCA instead of VFC | Fair clustering on Bank with three protected groups · Bank (3 groups: single/married/divorced) | Cost: 0.228 -> 0.222 | Helped |
| Use Adam instead of Lloyd's algorithm for optimizing cluster centers (ablation) | FCA · Fair clustering; datasets not specified in provided results | Cost | No clear effect |
| Vary the cluster-center initialization (ablation) | FCA · Fair clustering; datasets not specified in provided results | Cost | No clear effect |
| Vary the partition size m (ablation) | FCA partitioning technique · Fair clustering; datasets not specified in provided results | Cost | No clear effect |
| Use Sinkhorn instead of linear programming to optimize the joint distribution (ablation) | FCA · Fair clustering; datasets not specified in provided results | Cost | No clear effect |
| Increase K across the tested values (ablation) | FCA versus baseline methods · Fair clustering; K in {5, 10, 20, 40} | Cost | Helped |
Surprising findings
- VFC fails to reach near-perfect balance (at most ~90% of Bal*) and overflows on Census without normalization, while FCA remains stable.
Limitations
- Theoretical guarantee for FCA-C is stated for the population version (densities assumed), and violation term 3R*epsilon grows with epsilon.
- Requires solving a linear program over the coupling, costly for large n without partitioning.
- Focuses on proportional (group) fairness and two protected groups in the main text; other fairness notions are not addressed.
Experimental setup
Datasets: Adult Bank Census RMNIST Office-31
Benchmarks: Adult Bank Census RMNIST Office-31
Metrics: Cost Bal ACC NMI
Baselines: Standard (fair-unaware) K-means FCBC SFC FRAC VFC DFC FCMI
Builds on: fairlet decomposition Kantorovich optimal transport K-means++ VFC
Closest papers by meaning
- Fair Clustering Through Fairlets (NeurIPS 2017 · similarity 0.92)
- Fair Algorithms for Clustering (NeurIPS 2019 · similarity 0.92)
- The Fairness-Quality Tradeoff in Clustering (NeurIPS 2024 · similarity 0.91)
- Towards Fairer Centroids in K-means Clustering (AAAI 2024 · similarity 0.91)
- Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.90)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.