Source-linked AI summary
Fair Algorithms for Clustering
Suman K. Bera, Deeparnab Chakrabarty, Nicolas J. Flores, Maryam Negahbani
TL;DR
The paper asks how to obtain low-cost clusterings that fairly represent protected groups when groups may overlap. It introduces tunable upper and lower representation constraints and a black-box transformation from vanilla ℓp-norm clustering algorithms. The resulting solutions achieve a (ρ + 2)-approximation with additive violations bounded by 4∆+ 3, while experiments report costs at most 15% above optimum.
Problem
Fair clustering must control protected-group representation in clusters, but prior approaches use stringent constraints, restrict groups to partitions, and provide good algorithms mainly for k-center.
Method
The paper defines tunable restricted-dominance and minority-protection bounds for possibly overlapping groups and transforms any vanilla ℓp-norm clustering solution through a fair assignment problem and iterative rounding.
Results
Any ρ-approximation becomes a (ρ + 2)-approximation with additive RD and MP violations of 4∆+ 3; experiments report costs at most 15% above optimum.
Takeaways & Limitations
The framework covers k-center, k-median, and k-means while simultaneously supporting user-specified fairness parameters and overlapping protected groups.
Takeaways & Limitations
The fairness guarantees depend on ∆, the maximum number of groups to which one individual belongs, and exact zero-violation constant-factor assignment remains an open question.
Abstract
from arXiv · showhide
We study the problem of finding low-cost Fair Clusterings in data where each data point may belong to many protected groups. Our work significantly generalizes the seminal work of Chierichetti et.al. (NIPS 2017) as follows. - We allow the user to specify the parameters that define fair representation. More precisely, these parameters define the maximum over- and minimum under-representation of any group in any cluster. - Our clustering algorithm works on any $\ell_p$-norm objective (e.g. $k$-means, $k$-median, and $k$-center). Indeed, our algorithm transforms any vanilla clustering solution into a fair one incurring only a slight loss in quality. - Our algorithm also allows individuals to lie in multiple protected groups. In other words, we do not need the protected groups to partition the data and we can maintain fairness across different groups simultaneously. Our experiments show that on established data sets, our algorithm performs much better in practice than what our theoretical results suggest.
1 Introduction
The paper generalizes fair clustering to tunable fairness constraints, overlapping protected groups, and any ℓp-norm objective, while transforming vanilla solutions into nearly fair clusterings with small quality loss. It also gives a lower-bounded clustering approximation and reports stronger empirical performance than the theory guarantees.
- Motivation: Fair clustering addresses whether requiring approximately equal protected-group representation in every cluster causes a loss in clustering quality.The question arises from disparate-impact concerns in algorithmic decisions and clustering.
- Prior limitations: Prior work used partitioned color classes, stringent balance constraints, and primarily k-center algorithms, excluding overlapping protected groups.The paper identifies these as three shortcomings and motivates allowing individuals to belong to multiple protected classes.
- Fairness model: The proposed fairness model lets users set α_i and β_i for each possibly overlapping group, bounding its maximum and minimum fraction in every cluster.Restricted dominance limits representation to α_i, while minority protection requires at least β_i.
- Main results: Any ρ-approximation for a vanilla ℓp-norm clustering objective can be converted into a (ρ + 2)-approximation to the best fair clustering, with additive violations of 4∆+ 3.The objectives include k-center, k-median, and k-means; experiments report violations almost never exceeding 3 and costs at most 15% above optimum.
- Algorithm: The method defines a fair assignment problem from a vanilla solution and solves it by iterative rounding, producing small additive fairness violations.For disjoint groups with ∆=1, a simpler one-iteration rounding algorithm suffices.
- Lower-bounded clustering: For lower-bounded clustering, a ρ-approximation yields a (ρ+2)-approximation in O(2^k poly(n)) time, including a 3.736-factor lower-bounded k-median algorithm.The result is fixed-parameter tractable and improves on the large O(1)-approximation constants available in polynomial time for k-median.
2 Preliminaries
The paper defines fair clustering with tunable upper and lower representation bounds for overlapping protected groups, then gives approximation guarantees for broad ℓp objectives and a lower-bounded variant.
- Problem formulation: Fair clustering partitions clients among at most k facilities while minimizing an ℓp assignment objective.The cases p=1,2,∞ correspond to k-median, k-means, and k-center.
- Fairness model: Each client may belong to multiple protected groups, with Δ denoting the maximum number of groups containing one client.The groups need not be disjoint.
- Fairness model: Restricted dominance caps each group’s cluster fraction at α_i, while minority protection requires at least β_i.The parameters α_i and β_i are user-specified values in [0,1].
- Fairness model: Fair solutions may assign clients to non-nearest open facilities because assignments must satisfy the fairness constraints.A fair solution is represented by the pair (S, φ).
- Guarantees: Theorem 1 gives a (ρ+2)-approximate fair clustering with (4Δ+3)-additive violation from any ρ-approximate vanilla solver.For Δ=1, the additive violation is at most +3.
- Lower-bounded clustering: The same technique yields a (ρ+2)-approximation for lower-bounded clustering in O(T + 2^k · poly(n)) time.The lower-bounded problem requires at least L clients per opened facility.
3 Algorithm for the FAIR (k, p)-CLUSTERING problem
The algorithm first obtains vanilla cluster centers, then solves a fair reassignment problem on those fixed centers. Its black-box reduction combines approximation preservation with controlled fairness violations from iterative rounding.
- Reduction: The two-step template runs a vanilla clustering algorithm and then computes a fair reassignment on the same facilities.The returned solution is the fixed center set together with the new assignment.
- Reduction: The reduction preserves a (ρ+2)-approximation when the fair assignment subroutine has λ-additive violation.Theorem 3 treats the vanilla solver and assignment solver as separate components.
- Approximation analysis: Mapping each optimal fair center to its nearest center from the vanilla solution produces a feasible reassignment with cost at most (ρ+2)OPTfair.The proof uses triangle inequality and monotonicity of the ℓp norm.
- Fair assignment: Theorem 7 provides a (4Δ+3)-violating algorithm for FAIR p-ASSIGNMENT.The LP relaxation is used as the starting point for iterative rounding.
- Fair assignment: The fair assignment problem is formulated as an LP and rounded integrally while preserving cost and allowing bounded constraint violations.The rounding procedure simulates a minimum degree-bounded matroid basis algorithm.
- Open question: The paper leaves open whether bicriteria approximation is necessary, although exact feasibility with zero violation is NP-hard to decide.A constant-factor algorithm with zero violation is not ruled out.
4 Lower-bounded clustering
The same reduction technique addresses lower-bounded clustering, where every opened facility must serve at least L clients, yielding improved parameterized-time approximation guarantees.
- Context: The approach improves prior lower-bounded k-median constants in O(2^k poly(n)) time relative to the large constants known for earlier O(1)-factor algorithms.For lower-bounded k-center, a 3-approximation was already known.
- Problem: Lower-bounded clustering minimizes an ℓp objective while requiring every opened facility to receive at least L clients.Assignments need not use the nearest open facility.
- Reduction: A vanilla ρ-approximation running in time T yields a (ρ+2)-approximation in O(T + 2^k · poly(n)) time.The result applies to the lower-bounded k-clustering problem.
- Results: The method gives a 4.676-factor polynomial-time approximation and a 3.736-factor k^O(k)poly(n)-time approximation for lower-bounded k-median.These bounds combine the reduction with known k-median algorithms.
- Algorithm: The algorithm enumerates subsets of the vanilla centers and solves a lower-bounded matching problem for each subset.There are 2^k candidate subsets.
- Extensions: The framework also extends to strong privacy constraints requiring group-specific lower bounds and to more general center constraints.Examples include knapsack median and matroid-constrained center variants.
5 Experiments
Experiments evaluate fairness, cost, overlapping-group effects, runtime, and fairness–utility trade-offs across established datasets and clustering objectives. The algorithm generally achieves low additive violations and modest cost increases while revealing why multiple protected groups should be considered jointly.
- Fairness evaluation: Vanilla clustering is often unfair, whereas the algorithm’s additive violation is almost always less than 3, even with ∆ = 2.This comparison holds across a wide range of fairness parameters.
- Cost analysis: The fair clustering cost is at most 15% more than vanilla cost for k ≤ 10 and significantly improves reported k-median costs from prior work.The experiments also find the algorithm close to the best fair clustering allowing additive violations.
- Overlapping protected groups: Considering overlapping groups matters: enforcing fairness for one attribute can leave substantial unfairness on another, while ∆ = 2 can produce the fairest solution across both.On census, fairness by race also yields fairness on sex, but fairness by sex leaves substantial unfairness on race.
- Runtime and datasets: A fair solution for census1990 with 500K points and 13 features is found in less than 30 minutes for k-means.The experiments use Python 3.6, CPLEX for linear programs, and UCI datasets including bank, census, creditcard, and census1990.
- Fairness–utility trade-offs: The experiments study how clustering cost changes with fairness strictness, helping users assess fairness–utility trade-offs when selecting thresholds.The fairness parameterization sets δ = 0.2 for the reported experiments, corresponding to the 80%-rule interpretation.
- Cost analysis: For k-means, the algorithm’s cost is at most 15% above vanilla cost for k ≤ 10 across all datasets; on creditcard, the fairness cost is at most 6%.The creditcard result occurs despite an extremely unfair vanilla solution.