Research map / Learning theory and algorithms / Clustering
The Fairness-Quality Tradeoff in Clustering
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.
Computes the exact Pareto front between clustering cost and fairness for assignment problems via dynamic programming over attribute patterns, gives a (2+α,1)-approximation for clustering, and a polynomial algorithm for the sum/max of imbalances objectives via matching.
Problem
Fair clustering is usually solved by optimizing cost under a fairness constraint, so practitioners do not see the full trade-off between clustering quality and fairness; the Pareto front of these two objectives is rarely computed.
Approach
Shows that for pattern-based fairness objectives (depending only on counts of sensitive attributes per cluster) and metric-based costs, a dynamic program over attribute patterns recovers the exact Pareto front of the assignment problem, and a routing argument extends this to a (2+α,1)-approximation for clustering; for sum/max of imbalances with two groups, the front is computed in polynomial time
Key results
- The dynamic programming algorithm recovers the exact Pareto front for the assignment problem in time O(k n^{l(k-1)}) for any metric-based cost and pattern-based fairness objective.
- For sum and max of imbalances with l=2, the Pareto front of the assignment problem is computed in polynomial time via reduction to min-weight perfect matching.
- Repeated FCBC recovers few, if any, points on the Pareto front, often returning dominated solutions, while the dynamic programming approach gets strictly better cost at similar fairness values.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use repeated FCBC instead of dynamic programming to recover the Pareto front | Fair clustering · Adult, Census, and BlueBike datasets | Pareto-front recovery accuracy | Hurt |
| Use repeated FCBC instead of dynamic programming | Fair clustering · Adult, Census, and BlueBike datasets | Clustering cost at similar fairness | Hurt |
| Use FCBC for objectives that sum proportional violations across clusters | FCBC · Group Utilitarian-Sum and Group Egalitarian-Sum | Pareto-front recovery | Hurt |
| Increase clustering cost along the Pareto front | Dynamic programming · Adult, Census, and BlueBike datasets, Balance objective | Balance | No clear effect |
| Use weighted matching to compute the assignment Pareto front | Fair clustering with two sensitive groups · Assignment problem, sum of imbalances | Running time | Helped |
Surprising findings
- Changing the fairness target from equal (1:1) proportions to a 1:3 ratio makes finding the best-fairness point NP-complete, so the polynomial result depends on the balanced-group assumption.
- Repeated FCBC sometimes returns only the vanilla clustering point, so the desired fairness trade-off is not realizable through it.
Limitations
- Running time is exponential in k and l, and the exact algorithm is worst-case exponential because the Pareto front can be exponential in size.
- Approximation for clustering inherits the approximation ratio alpha of the vanilla clustering algorithm and has a factor of 2+alpha in cost.
- Assumes sensitive attributes are disjoint and fairness objectives are pattern-based and mergeable.
Experimental setup
Datasets: Adult Census1990 BlueBike trip history
Benchmarks: Adult Census1990 BlueBike
Metrics: clustering cost (k-means) fairness objective values (Balance, Group Utilitarian, Group
Baselines: repeated-FCBC FCBC
Builds on: k-means++ FCBC
Closest papers by meaning
- Fair Clustering via Alignment (ICML 2025 · similarity 0.91)
- Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.90)
- Towards Fairer Centroids in K-means Clustering (AAAI 2024 · similarity 0.89)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.88)
- Accelerating Spectral Clustering under Fairness Constraints (ICML 2025 · similarity 0.87)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.87)
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.