Probabilistic Fair Clustering

Seyed A. Esmaeili; Brian Brubach; Leonidas Tsepenekas; John P. Dickerson

Source-linked AI summary

Probabilistic Fair Clustering

Seyed A. Esmaeili, Brian Brubach, Leonidas Tsepenekas, John P. Dickerson

arXiv:2006.10916v3Jun 19, 2020cs.LGcs.AIcs.DSstat.ML

TL;DR

Fair clustering traditionally assumes deterministic group membership, but real applications may provide only uncertain membership estimates. The paper develops probabilistic and ordered metric-membership clustering models with approximation guarantees, finding bounded fairness violations and low efficiency loss in its reported experiments.

Problem
Prior fair clustering assumes deterministic group membership, despite applications where group membership is uncertain or estimated.
Method
The paper develops probabilistic fair-clustering models, including metric membership, and algorithms with approximation-ratio guarantees.
Results
The algorithms achieve a violation at most ϵ and approximation ratio (α + 2) with high probability in O(2kpoly(n)) time, while experiments report POF ≤1.02.
Takeaways & Limitations
Fair clustering can be extended to uncertain group membership while retaining theoretical guarantees and low reported relative efficiency loss.
Takeaways & Limitations
The approach addresses one fairness definition, and biased membership estimators can transfer bias into the final clustering.

Abstract

from arXiv · show

In clustering problems, a central decision-maker is given a complete metric graph over vertices and must provide a clustering of vertices that minimizes some objective function. In fair clustering problems, vertices are endowed with a color (e.g., membership in a group), and the features of a valid clustering might also include the representation of colors in that clustering. Prior work in fair clustering assumes complete knowledge of group membership. In this paper, we generalize prior work by assuming imperfect knowledge of group membership through probabilistic assignments. We present clustering algorithms in this more general setting with approximation ratio guarantees. We also address the problem of "metric membership", where different groups have a notion of order and distance. Experiments are conducted using our proposed algorithms as well as baselines to validate our approach and also surface nuanced concerns when group membership is not known deterministically.

1 Introduction

The paper extends fair clustering to settings where group membership is uncertain, motivated by socially consequential biases in automated decision systems. It introduces probabilistic and metric-membership models, approximation algorithms, and empirical validation.

Fair clustering addresses the social risks of biased automated decision systems by incorporating vertex colors into clustering decisions.Examples include biased hiring, advertising, recidivism, and healthcare allocation systems.
The paper studies fair clustering when each vertex’s group membership is probabilistic rather than known deterministically.Fairness constraints require cluster color proportions to hold in expectation.
It introduces two models: unordered probabilistic colors and metric membership, where colors have an order and distance.Metric membership targets attributes such as age or income.
The paper presents approximation algorithms with theoretical guarantees and also considers the large-cluster setting.The large-cluster assumption excludes pathologically small optimal clusters.
Experiments on four real-world datasets evaluate the proposed approaches and expose concerns arising from uncertain group membership.

2 Related Work

Prior fair metric-clustering research assumes known demographic colors, whereas this paper considers probability distributions over colors. The proposed setting generalizes deterministic membership while remaining distinct from multi-color assignments and addresses an unsolved uncertainty model in unsupervised metric clustering.

Earlier fair clustering work studied known colors, multiple objectives, multiple colors, and intersecting demographic groups.This literature includes k-center, k-median, and k-means variants.
This paper assigns each point a distribution over possible colors while assuming it still has one true color.
Probabilistic membership generalizes deterministic single-color assignments but differs from assigning multiple colors to one point.
Although uncertain group membership was studied in supervised learning [9], prior work had not addressed this uncertainty for unsupervised metric clustering.

3 Preliminaries and Problem Definition

The paper formulates metric clustering with fairness constraints based on color representation, then replaces deterministic colors with probabilistic expectations and extends the model to ordered one-dimensional memberships. It also defines approximate feasibility through constraint-violation measures.

3 Preliminaries and Problem Definition: A k-clustering selects at most k centers in a metric space and assigns every point to a center to minimize an objective such as k-center, k-median, or k-means.The point-to-set distance is the minimum distance to any selected center.
3 Preliminaries and Problem Definition: Classical clustering assigns each point to its nearest chosen center, but additional size or fairness constraints can invalidate that property.
3 Preliminaries and Problem Definition: Deterministic fair clustering constrains each cluster’s proportion of every color between specified lower and upper bounds.The bounds are denoted l_hℓ and u_hℓ.
3 Preliminaries and Problem Definition: Probabilistic fair clustering gives each point a probability for each color and requires expected cluster color counts to satisfy the fairness bounds.The probabilities for a point sum to 1.
3 Preliminaries and Problem Definition: A γ-violating solution measures how much a clustering exceeds or falls short of its fairness constraints.
3.2 Metric Membership Fair Clustering: Metric membership represents ordered attributes as consecutive integers in a one-dimensional Euclidean space and constrains each cluster’s average value to an interval.This formulation captures attributes such as age or income.

4 Approximation Algorithms and Theoretical Guarantees

The algorithms first choose centers without fairness, then solve a fair-assignment LP and round fractional assignments using minimum-cost flow, obtaining approximation and violation guarantees for probabilistic and metric-membership clustering.

An α-approximation for color-blind clustering combined with a γ-violating fair-assignment algorithm yields an (α + 2)-approximation with violation at most γ.
4.1 Algorithms for the Two Color and Metric Membership Case: The method selects centers using an ordinary color-blind α-approximation before enforcing fairness through an assignment LP.The LP uses x_ij to assign points to selected centers and adapts constraints for probabilistic or metric membership.
4.1.3 Rounding for the Two Color and Metric Membership Case: Fractional assignments are rounded by constructing a minimum-cost flow network that sorts assigned vertices by membership values and accumulates unit assignments.Edges have unit capacities; assignment-edge costs encode k-median or k-means distances, while either setting suffices for k-center.
4.1.3 Rounding for the Two Color and Metric Membership Case: Theorem 4.2 bounds cluster-size violation by 1, metric-membership average-value violation by 2R, and probabilistic expected-value violation by 2.The integral minimum-cost flow is computable in polynomial time because demands, capacities, and distances are integral.
4.1.3 Rounding for the Two Color and Metric Membership Case: Metric-membership rounding is asymptotically optimal because every rounding scheme can incur fairness violation at least R^2 in the worst case.The paper constructs a five-point instance where the rounded solution changes each cluster’s assignment value by R^2.
4.2 Algorithms for the Multiple Color Case Under a Large Cluster Assumption: Under the large-cluster assumption, trying all center-opening and center-closing combinations gives an (α + 2)-approximation in O(2^k poly(n)) time and violation at most ϵ with high probability.Independent sampling and a Chernoff bound provide concentration around expected color amounts when clusters have size at least L.

5 Experiments

Experiments evaluate the proposed algorithms on unordered probabilistic colors, metric membership, and multiple probabilistic colors under a large-cluster assumption. Across these settings, the method generally maintains its theoretical violation guarantees, while efficiency costs vary with labeling accuracy, feature correlations, and cluster-size bounds.

5.2 Two Color Case: Violations of the color-blind solution reach 25, while the proposed algorithm stays below 1 and achieves POF ≤1.02 in the two-color case.The comparison uses Bank data with probabilistic marital-status assignments at pacc values of 0.7 and 0.8.
5.2 Two Color Case: As pacc increases from random to deterministic assignments, POF increases for both δ = 0.2 and δ = 0.1.At pacc = 0.2, assignments are completely random and cost matches the color-blind cost; the maximum occurs at pacc = 1.
5.2 Two Color Case: Thresholding probabilistic labels can satisfy proportions with small violations but incurs much higher POF and can produce an infeasible deterministic problem.The proposed algorithm achieves the same violations with smaller POF than thresholding followed by deterministic fair clustering.
5.3 Metric Membership: For metric membership, POF is below 5% on Adult but reaches 25% on CreditCard and generally rises with the number of clusters.The higher CreditCard cost may be explained by correlation between credit and other features represented in the metric space.
5.3 Metric Membership: The normalized maximum additive violation remains below 2 for the proposed algorithm but reaches 250 for the color-blind solution.This comparison varies the number of clusters and normalizes violation by the maximum membership value R.
5.4 The Large Cluster Assumption: Under the large-cluster setting on Census1990, normalized violation decreases as the cluster-size lower bound increases, while POF remains below 50%.The experiment uses 100,000 points, k = 5 clusters, seven age groups, and probabilistic memberships predicted with an SVM of around 68% accuracy; one rare group is merged to satisfy the assumption.

6 Conclusions & Future Research

The paper generalizes fair clustering to probabilistic group membership, provides approximation-guaranteed algorithms, and addresses metric membership. Experiments support the theoretical guarantees while identifying future extensions and practical concerns.

Probabilistic fair clustering generalizes prior deterministic-membership models and includes metric membership with ordered, distance-aware groups.
The proposed algorithms have strong theoretical guarantees, and experiments show those guarantees are easily met on real-world data.
Future work includes assigning multiple colors to vertices and removing assumptions such as the large cluster assumption.

7 Broader Impact

The paper addresses probabilistic group membership as a broader fairness setting, but emphasizes that fairness definitions and membership estimates can carry application-specific and societal risks. Its approach is therefore one component of a larger ecosystem requiring stakeholder involvement.

Probabilistic membership broadens fair clustering to settings where group attributes are estimated rather than known deterministically.
The approach should be considered part of a larger application ecosystem, with open dialogue among technicians, policymakers, and other stakeholders.
The paper formalizes one common fairness definition, while acknowledging that fairness is morally laden, application-specific, and not universally captured by a single definition.
If membership estimates come from biased machine-learning models, the resulting clustering may reflect that bias.

A.2 General Theorem for Lower Bounded Deterministic Fair Clustering

For deterministic fair clustering with lower-bounded cluster sizes, the paper combines color-blind clustering with a fair assignment procedure. It obtains an α+2 approximation, violation at most γ, and fixed-parameter tractable running time.

The method defines a fair assignment problem that enforces fairness constraints and a minimum cluster size L for a fixed center set.
The theorem achieves approximation ratio α+2 and violation at most γ for deterministic fair clustering with lower-bounded cluster sizes.
The algorithm runs in fixed-parameter tractable time O(2^k poly(n)).
Trying all possible close-and-open combinations for color-blind centers yields the O(2^k poly(n)) fixed-parameter tractable procedure.
The proof combines a color-blind α-approximation with a γ-violating fair-assignment algorithm whose objective value equals the fair-assignment optimum.

B.1 Independent Sampling and the Resulting Concentration Bounds

Independent sampling preserves expected color amounts but changes the joint distribution and enables Chernoff concentration. The analysis shows that bound relaxation and lower-bounded cluster sizes can be necessary for probabilistic validity.

Independent sampling preserves the expected amount of each color for any point collection, while providing a Chernoff bound for the sampled color count.
The true and independently sampled joint distributions generally differ, despite agreeing on marginal probabilities and color-count expectations.
When a cluster must exactly meet a color proportion, Chernoff concentration is insufficient, so relaxing fairness bounds may be necessary for high-probability validity.
Figure 9 illustrates that independent sampling can make distant outliers form a seemingly balanced cluster even when that cluster is invalid for the probabilistic instance.
Enforcing a lower cluster-size bound is necessary to ensure solutions from independently sampled deterministic instances remain valid with high probability.

C Example on Forming the Network Flow Graph for the Two-Color (Metric Membership) Case

The example constructs a network-flow graph by converting fractional center assignments into cluster subgraphs, then joining those subgraphs through their centers and a terminal vertex. For metric membership, the construction is unchanged except that vertices are ordered by their metric-membership values rather than probabilities.

C Example on Forming the Network Flow Graph for the Two-Color (Metric Membership) Case: The example starts from fractional assignments and probability values for five vertices distributed across two centers.Center 1 has assignments x11 = 0.3, x12 = 0.6, x13 = 0.7, x14 = 0, x15 = 1.0; center 2 has x21 = 0.7, x22 = 0.4, x23 = 0.3, x24 = 1.0, x25 = 0.
C Example on Forming the Network Flow Graph for the Two-Color (Metric Membership) Case: For center 1, the assigned vertices are sorted by non-increasing probability as A1 = [2, 1, 3, 5], producing the cluster-1 graph.The construction uses |C1| = 3 vertices and the nonzero-assignment set {1, 2, 3, 5}.
C Example on Forming the Network Flow Graph for the Two-Color (Metric Membership) Case: For center 2, the nonzero-assignment vertices are sorted as A2 = [4, 2, 1, 3], producing the cluster-2 graph.The resulting cluster-2 subgraph gives each displayed cluster vertex a total assignment of 1 except the last vertex c3.
C Example on Forming the Network Flow Graph for the Two-Color (Metric Membership) Case: The complete flow graph unions the two subgraphs without duplicating vertices, connects each cluster vertex to its corresponding center, and connects both centers to t.Assignment weights are omitted after construction because they have no significance in the following steps.
C Example on Forming the Network Flow Graph for the Two-Color (Metric Membership) Case: Metric membership changes only the ordering rule: vertices are sorted by their metric-membership value rv instead of probability pv.The graph-construction procedure itself remains unaltered.

D Further details on solving the lower bounded fair clustering problem

The lower-bounded fair-clustering solution combines a color-blind approximation algorithm, an LP with minimum cluster-size constraints, and network-flow or dependent-rounding procedures. It achieves an α + 2 approximation, with fairness and cluster-size violations bounded or concentrated under the stated assumptions, while fractional optimization can require O(2^k poly(n)) time.

D Further details on solving the lower bounded fair clustering problem: The method first runs a color-blind approximation algorithm with ratio α, then solves an LP that retains deterministic fairness constraints and adds a lower bound on cluster size.The rounding stage uses network flow and produces violations of at most 1 in cluster size and at most 1 per color within any cluster.
D Further details on solving the lower bounded fair clustering problem: The resulting lower-bounded deterministic fair-clustering solution has approximation ratio α + 2 after enumerating center-opening choices.Trying all 2^k combinations fixes the issue that a color-blind solution may close a center while the lower-bound constraint requires it to contain at least L points, yielding runtime O(2^k poly(n)).
E.2 Multiple Color Large Cluster solution using Dependent Rounding: Dependent rounding applies to fractional assignments represented as weighted edges in a bipartite graph between data vertices and cluster centers.The graph uses all vertices of C on one side and all centers in S on the other, with LP assignments xij as edge weights.
E.2 Multiple Color Large Cluster solution using Dependent Rounding: Dependent rounding preserves zero assignments and expected color mass, so points are not assigned to centers excluded by the LP and expected cluster color counts match LP assignments.The proof invokes property 1 to establish both zero-preservation and EDR[Xij] = xij.
E.2 Multiple Color Large Cluster solution using Dependent Rounding: With high probability, the integral solution’s color assignments concentrate around the fair LP assignments.This provides the probabilistic fairness guarantee for the rounded solution.
E.2 Multiple Color Large Cluster solution using Dependent Rounding: The optimal fractional solution required by the dependent-rounding approach takes O(2^k poly(n)) time to obtain.The stated runtime is a scope boundary for the method’s optimization step.
Implementation details: In the experiments, numeric features define Euclidean distances after normalization, while the fairness attribute is excluded from coordinates in metric-membership settings.Distances in min-cost flow are scaled by 1000 and rounded for solving, then original distances are used to verify the resulting cost.

F.2 Further Experiments

Experiments evaluate the proposed algorithms on k-center and k-median under probabilistic colors and metric membership. Across the reported figures, violations remain below 1, matching the theoretical guarantees, while POF is reported alongside violation as the number of clusters varies.

F.2 Further Experiments: The evaluation varies the number of clusters and reports both fairness violation and POF across the k-center and k-median settings.All datasets are subsampled to 1,000 points, and the two-color probabilistic experiments use pacc = 0.9.
F.2 Further Experiments: Violations remain below 1 for both two-color probabilistic k-center and metric-membership k-center, matching the theoretical guarantee.Figure 13 reports maximum violation for Bank, while Figure 14 reports normalized maximum violation for Adult with age-based metric membership.
F.2 Further Experiments: The k-median experiments likewise show small violations not exceeding 1 for probabilistic colors and metric membership.Figure 15 covers the Bank two-color probabilistic case, and Figure 16 covers CreditCard metric membership over credit.