Source-linked AI summary
Scalable Fair Clustering
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner
TL;DR
Fair k-median seeks low-distance clusters while maintaining color balance, but prior fairlet decomposition is too slow for large data. This paper introduces a nearly linear-time decomposition based on hierarchical tree metrics and reports comparable clustering quality with almost-linear empirical runtime, while retaining a logarithmic approximation factor.
Problem
Fair k-median must balance colored points within clusters, but prior fairlet decomposition takes at least quadratic time and limits applications to relatively small data sets.
Method
The paper embeds Euclidean points into an HST and greedily constructs (r, b)-fairlets by minimizing cross-subtree fairlets.
Results
Clustering quality is comparable to Chierichetti et al. (2017), while empirical runtime scales almost linearly in the number of points.
Takeaways & Limitations
The algorithm supports massive data sets and allows finer control of balance through arbitrary integer r and b parameters.
Takeaways & Limitations
The paper's approximation factor is logarithmic, and designing a constant-factor algorithm with near-linear running time remains open.
Abstract
from arXiv · showhide
We study the fair variant of the classic $k$-median problem introduced by Chierichetti et al. [2017]. In the standard $k$-median problem, given an input pointset $P$, the goal is to find $k$ centers $C$ and assign each input point to one of the centers in $C$ such that the average distance of points to their cluster center is minimized. In the fair variant of $k$-median, the points are colored, and the goal is to minimize the same average distance objective while ensuring that all clusters have an "approximately equal" number of points of each color. Chierichetti et al. proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the $k$-median objective. In the second step, fairlets are merged into $k$ clusters by one of the existing $k$-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time. Our algorithm additionally allows for finer control over the balance of resulting clusters than the original work. We complement our theoretical bounds with empirical evaluation.
1 Introduction
The paper develops scalable fair k-median clustering through nearly linear-time fairlet decomposition, supporting arbitrary integer balance parameters and finer control over cluster balance. It combines theoretical guarantees with empirical evidence that runtime scales almost linearly while clustering quality remains comparable to prior work.
- Problem: Fair clustering constrains every cluster to maintain a minimum fraction of the less frequent color while optimizing clustering distance.The paper focuses on the two-color formulation of fair clustering and the k-median objective.
- Problem: Chierichetti et al.'s fairlet decomposition approach has at least quadratic running time, limiting its applicability to relatively small data sets.Fairlets are balanced subsets later merged into clusters.
- Contribution: The paper proposes a near-linear-time fairlet decomposition algorithm for (r, b)-fairness with arbitrary integer balance parameters.The algorithm targets Euclidean data in d-dimensional space and focuses on k-median.
- Guarantees: Theorem 1.1 gives running time O(d·n·log n+T(n, d, k)) and approximation factor O_r,b(d·log n+α) relative to optimal fair k-median.T(n, d, k) is the running time of an α-approximation algorithm for ordinary k-median over n points in R^d.
- Evaluation: Experiments find clustering quality comparable to Chierichetti et al. (2017), while empirical runtime scales almost linearly with the number of points.The reported scaling is intended to support application to massive data sets.
- Limitation: The paper retains a logarithmic approximation factor, whereas constant-factor approximation with near-linear running time remains an open problem.The experiments report that the logarithmic factor does not seem to affect empirical solution quality.
- Method: The method embeds points into a hierarchical tree metric and greedily constructs local fairlets by minimizing cross-subtree fairlets.The Minimum Heavy Point problem yields an O(1)-approximate fairlet decomposition with respect to the tree distance.
2 Preliminaries
The preliminaries define fairlet decompositions, probabilistic metrics, and γ-HSTs, then invoke probabilistic tree embeddings as the structural basis for the algorithm. The paper assumes polynomial aspect ratio and does not address weighted pointsets.
- Fairlet decomposition: An (r, b)-fairlet decomposition partitions a red-blue pointset into disjoint fairlets, each of size at most b+r and balance at least b/r.The parameters satisfy 1 ≤ b ≤ r and gcd(r, b) = 1.
- Probabilistic metrics: A probabilistic metric is a distribution over multiple metrics on the same point set, combined through expected distances.The representation uses metrics d_1, ..., d_ℓ with probabilities α_1, ..., α_ℓ.
- Scope: Combining the approach with core-sets would require extending the clustering algorithm to weighted pointsets, which the paper does not consider.The issue arises because core-sets typically assign weights to data points.
- γ-HST: A γ-HST is a rooted weighted tree whose child edges from each node have equal lengths and shrink geometrically along root-to-leaf paths.The child distance is at most 1/γ times the distance to the parent.
- Assumption: The analysis assumes that the input pointset has polynomial aspect ratio.The aspect ratio is the ratio between maximum and minimum distances.
- Embedding: Bartal's result supplies a probabilistic embedding into γ-HST metrics with O(γ · d · log_γ n) distortion and O(d · n · log_γ n) construction time.This embedding provides the tree-metric foundation used by the algorithm.
3 High-level Description of Our Algorithm
The algorithm first embeds points into a randomly shifted γ-HST, then computes fairlets on the tree and merges them into k clusters. Its fairlet phase has a nearly linear-time guarantee, and the two phases together yield the paper’s fair k-median result.
- Overall pipeline: The algorithm follows a two-phase pipeline: compute an approximately optimal fairlet decomposition, then cluster the fairlets into k clusters.The second phase uses a β-approximate k-median algorithm after representing each fairlet by a weighted center point.
- Preprocessing: A randomly shifted grid hierarchy embeds the Euclidean input into a γ-HST with exponentially decreasing edge lengths.The construction recursively subdivides grid cells and connects their corresponding tree nodes with edges proportional to cell diameter.
- Phase 1: fairlet decomposition: At each tree node, Step 1 approximately minimizes removed heavy points while making every child and their union (r, b)-balanced.The removed points are then decomposed into fairlets, while the algorithm recursively processes each non-empty child.
- Phase 1: fairlet decomposition: Theorem 3.3 gives an O(d · n · logγ n)-time fairlet algorithm with expected approximation factor O(d · (r8 + b8) · log n).The guarantee is stated relative to the optimal (r, b)-fairlet decomposition under costmedian.
- Phase 2: merging fairlets: Theorem 3.4 bounds the final clustering approximation by α+(r+b)·β, and Theorems 3.3 and 3.4 together imply Theorem 1.1.Here α is the fairlet-decomposition approximation and β is the guarantee of the invoked k-median algorithm.
4 Fairlet Decomposition: a Top-down Approach on γ-HST
The fairlet decomposition algorithm embeds points into a γ-HST and then constructs balanced fairlets through a top-down tree procedure. It achieves near-linear runtime with approximation guarantees that combine tree distortion and fairlet construction.
- Overview: The algorithm first embeds the input point set into a γ-HST and then computes an (r, b)-fairlet decomposition using distances induced by the tree.The embedding distortion contributes to the overall approximation factor.
- Guarantees: O(r^3 + b^3)-approximation is achieved for fairlet decomposition on the HST in near-linear time.The input embedding must be an O(r^5 + b^5)-HST.
- Guarantees: O(d · (r^8 + b^8) · log n)-approximation follows after combining HST distortion with the fairlet decomposition guarantee.The result applies to points in R^d and uses an O(r^5 + b^5)-HST embedding.
- Runtime: The overall algorithm runs in eO(n) time because HST construction takes O(d · n · log n) time and fairlet decomposition is near-linear.The two stages are the embedding and the fairlet-decomposition algorithm.
- Cost model: The modified costmed objective relaxes finding the best center in each fairlet while remaining within a factor of r + b of costmedian.For every fairlet S, costmedian(S) ≤ costmed(S) ≤ (r + b) · costmedian(S) under the tree distance.
5 Experiments
The evaluation tests the fair k-median algorithm on four datasets and reports both runtime and clustering quality. The algorithm achieves empirical improvements over Chierichetti et al. and scales almost linearly with the number of input points.
- Datasets: The evaluation uses Diabetes, Bank, Census, and Census II datasets with sensitive attributes including gender and marital-status.The datasets represent points using selected numeric attributes; Census II uses 25 numeric attributes and gender as its sensitive attribute.
- Algorithm: The implementation embeds points into a 2-HST, computes fairlets for specified balance parameters, and then applies an existing K-medoids subroutine.This is the practical implementation used for the empirical evaluation.
- Results: The algorithm achieves empirical cost improvements on all instances compared with Chierichetti et al. (2017).The paper attributes this efficiency particularly to low-dimensional input spaces in Diabetes, Bank, and Census.
- Results: Its empirical runtime scales almost linearly with the number of input points, and the algorithm can run on the whole dataset for each dataset.Figure 2 reports fairlet-decomposition runtime across sample sizes, while Table 3 reports performance on all points.
- Evaluation protocol: The reported runtime for each sample size is the median over 10 sample sets of that size.This protocol applies to the runtimes shown in Figure 2 and Tables 1 and 3.
A Missing Proofs
The appendix proves bounds for the tree-based fairlet decomposition and its conversion into fair k-median clustering. The proof tracks affected points and shows how the resulting costs relate to optimal decompositions and clustering.
- Proof structure: The proof proceeds by induction on the height of the HST node, with the leaf case solved optimally.The induction hypothesis is applied to vertices at the preceding height.
- Proof structure: The optimal fairlet decomposition is partitioned by lowest common ancestor locations and heavy fairlets, with heavy points tracked separately.For each child subtree T(v_i), OPT_i contains fairlets whose lowest common ancestors lie there, while OPT_H contains heavy fairlets.
- Proof structure: The constructed solution is decomposed analogously into child-subtree components and heavy points for cost comparison.The notation distinguishes sol_i, sol_H, and the heavy points H_sol within each child subtree.
- Fairlet construction: The appendix constructs fairlets in three steps: balance affected points, add remaining points to existing fairlets, then mix residual points with nonsaturated fairlets.The steps preserve the (r, b)-balanced property while bounding the added tree-distance cost.
- Cost bound: cost(OPTi) + |Q0| · b · (r + b) · hT(v_i) bounds the cost after augmenting the affected-point construction.This bound follows from the separate costs incurred in the three augmentation steps.
- Fairlet-to-clustering bound: Theorem 3.4 combines an α-approximate fairlet decomposition with a β-approximate k-median algorithm to obtain an α + (r + b)·β approximation.The conversion uses fairlet centers and compares the resulting clustering cost with optimal fair clustering.