Source-linked AI summary
Fair k-Center Clustering for Data Summarization
Matthäus Kleindessner, Pranjal Awasthi, Jamie Morgenstern
TL;DR
Fair data summarization asks how to select k-center prototypes while enforcing demographic group quotas, despite prior fair-clustering methods requiring super-quadratic time. The paper develops a simple approximation algorithm with running time linear in the data-set size and k, achieving a 5-approximation for two groups while its general-group guarantee grows exponentially with the number of groups.
Problem
Fair data summarization requires selecting representative k-center prototypes subject to demographic group quotas, while existing constrained-clustering algorithms are super-quadratic in data-set size.
Method
The paper develops a simple approximation algorithm for fair k-center clustering that runs in time linear in |S| and k.
Results
For two groups, the algorithm is a 5-approximation; for m groups, the guarantee is (3·2^(m−1)−1) with the stated near-linear running-time bound.
Takeaways & Limitations
The approach closes the fair-versus-standard k-center running-time gap, with constant-factor approximation overhead when the number of demographic groups is small.
Takeaways & Limitations
For more than two groups, the proven approximation factor grows exponentially with m, and the authors do not know whether this dependence is necessary.
Abstract
from arXiv · showhide
In data summarization we want to choose $k$ prototypes in order to summarize a data set. We study a setting where the data set comprises several demographic groups and we are restricted to choose $k_i$ prototypes belonging to group $i$. A common approach to the problem without the fairness constraint is to optimize a centroid-based clustering objective such as $k$-center. A natural extension then is to incorporate the fairness constraint into the clustering problem. Existing algorithms for doing so run in time super-quadratic in the size of the data set, which is in contrast to the standard $k$-center problem being approximable in linear time. In this paper, we resolve this gap by providing a simple approximation algorithm for the $k$-center problem under the fairness constraint with running time linear in the size of the data set and $k$. If the number of demographic groups is small, the approximation guarantee of our algorithm only incurs a constant-factor overhead.
1. Introduction
The paper frames fair data summarization as selecting representative prototypes while controlling demographic representation. It targets a computational gap between fair and standard k-center clustering.
- Motivation: Data summarization outputs a small, representative subset, but image-search summaries can underrepresent demographic groups.The paper cites CEO image-search results as an example of demographic imbalance.
- Motivation: Centroid-based clustering uses selected data points as representatives of clusters and supports summarization across domains.Examples include text summarization and robotics.
- Fair summarization: Fair summaries constrain the number of selected centroids from each demographic group, allowing proportional or balanced representation.The constraint specifies k_Si centroids from each group S_i.
- Computational gap: Existing fair-clustering algorithms run in ω(|S|^2) time, whereas standard k-center admits linear-time approximation.The paper argues that this slowdown may be prohibitive for massive data sets.
- Contribution: The paper provides a simple fair k-center approximation algorithm running in time linear in |S| and k.The approximation guarantee worsens with many demographic groups, but the authors report no large factors in extensive simulations.
2. Definition of k-Center and Fair k-Center
The section defines standard k-center over a metric space and extends it with group-specific center quotas and optional required centers. It contrasts the proposed computational goal with slower prior approaches.
- Standard k-center: Standard k-center minimizes the maximum distance from each data point to its nearest center under a metric satisfying the triangle inequality.The objective selects k centers from S and uses d(s,C)=min_c∈C d(s,c).
- Standard k-center: Gonzalez’s greedy strategy gives a 2-approximation in O(k|S|) time when distances are evaluated in constant time.It repeatedly adds the point farthest from the current centers.
- Fair k-center: The fair variant partitions S into demographic groups and requires exactly k_Si centers from group S_i, with quotas summing to k.It also permits a subset C_0 that must be included among the centers.
- Related computational cost: A prior matroid-center approach requires sorting all pairwise distances and therefore takes at least Ω(|S|^2 log |S|) time.This is contrasted with the paper’s focus on faster fair k-center approximation.
3. A Linear-time Approximation Algorithm
The paper develops a recursive approximation algorithm for fair k-center clustering, beginning with a two-group procedure and extending it to arbitrary numbers of groups. It achieves linear dependence on |S| while providing explicit approximation guarantees, including a tight 5-approximation for two groups.
- Two groups: 2-approximation with running time O((k + |C′0|)|S|) under constant-time distance evaluation is provided for the unfair problem with initially given centers.
- Two groups: The algorithm first applies the greedy unfair k-center procedure, then exchanges centers within their clusters to satisfy group-specific center counts.For two groups, excess centers from one group are replaced by elements from the other group; unresolved instances are solved recursively.
- Two groups: 5-approximation with running time O((k + |C0|)|S|) is achieved for fair k-center with two groups, and no (5 − ε)-approximation is possible for this algorithm.The analysis is tight for the stated algorithm.
- Arbitrary number of groups: For three or more groups, center exchanges may require a series of swaps rather than a direct replacement between two groups.The exchange process uses a directed graph to identify a strict subset of groups for recursive processing.
- Arbitrary number of groups: The arbitrary-group algorithm recursively reduces the number of unresolved groups and achieves a (3·2^m−1 −1)-approximation in time O((|C0|m + km^2)|S| + km^4).The algorithm is well-defined and terminates, and for m ≥ 3 it is not a (8 − ε)-approximation algorithm for any ε > 0.
- Arbitrary number of groups: For arbitrary numbers of groups, the authors do not know whether the stated approximation analysis is tight; experiments never observed a factor greater than 8.
4. Related Work
The paper positions its contribution within fair unsupervised learning and distinguishes its representative-summary objective from alternative fairness and summarization objectives. Its method requires only a metric, rather than feature representations.
- Fairness: The paper contributes to fair unsupervised learning by studying data summarization under a constraint requiring kSi selected elements from each demographic group Si.
- Fair data summarization: Celis et al. study the same group-count constraint but optimize diversity, whereas this paper optimizes representativeness through proximity to summary centers.
- Fair data summarization: The paper's representative-summary approach applies to metric data and does not require the points to have feature representations in R^n.
- Fair clustering: Related work also studies a different fairness notion requiring approximately equal representation of every group within each cluster, including k-medoid and k-center settings.
- Centroid-based clustering: Prior work on the same fairness constraint includes approximation algorithms for two-group k-medoid and a matroid-center formulation of the fair k-center problem.
5. Experiments
The experiments illustrate unfair summaries, compare approximation and running time against prior methods, and evaluate output costs against heuristics and the unfair algorithm.
- Motivating Example: Algorithm 1 produced summaries containing three or four female doctors despite equal numbers of female and male images.The motivating data set contained 14 doctor images, split evenly between the two groups.
- Motivating Example: Our algorithm and Celis et al. (2018b) allow the requested numbers of female and male images to be specified explicitly.The experiments note that which summaries are more useful depends on the image feature representations.
- Approximation Factor and Comparison with Chen et al. (2016): The approximation factor of our algorithm increased very moderately with the number of groups in the simulated experiment.The experiment used 100 optimal centers and 10000 sampled points, with m ranging from 2 to 20.
- Comparison with Baseline Approaches: The two linear-time heuristics had costs comparable to our algorithm despite lacking worst-case guarantees.The heuristics were evaluated on synthetic and Adult data sets.
- Comparison with Algorithm 1: The experiments compared our algorithm with Algorithm 1 in terms of cost and measured how unevenly Algorithm 1 distributed centers across groups.They also examined the resulting price of fairness.
6. Discussion
The paper gives a linear-time fair k-center approximation algorithm, proves a 5-approximation for two groups, and identifies exponential group dependence as unresolved.
- Discussion: The algorithm runs in time linear in the data-set size |S| and number of centers k.This addresses the prior super-quadratic running time for fair k-center approximation.
- Discussion: A 5-approximation guarantee is proved when S consists of two groups.For more than two groups, the proven upper bound increases exponentially with the number of groups.
- Discussion: Whether the exponential dependence on the number of groups is necessary remains unknown, although extensive numerical simulations never observed a large approximation factor.The paper also proposes extending the analysis to k-medoid clustering and characterizing data sets where fast algorithms are optimal.
A. Proofs
The proofs establish approximation guarantees for the greedy and recursive algorithms, while also exhibiting tight counterexamples for Algorithm 2 and bounding Algorithm 4's running time.
- Algorithm 1 is a 2-approximation for the unfair k-center problem and can be implemented in time O((k + |C′|)|S|).
- Algorithm 2 is proved to be a 5-approximation algorithm for the fair problem.
- Algorithm 2 cannot guarantee any factor strictly below 5, as a constructed instance yields cost 5 − δ versus optimal fair cost 1 + δ.
- Algorithm 4's recursive proof establishes a (3 · 2^(m−1) − 1)-approximation guarantee.
- The proof maintains distance bounds through recursive center exchanges, including a 4r*fair bound after Algorithm 3 exchanges centers.
- Algorithm 4 makes at most m recursive calls and has running time O((|C0|m + km^2)|S| + km^4).
B. Further Experiments
Further experiments compare the costs of the paper’s algorithm with Chen et al.’s method and revisit earlier experiments under alternative group-specific prototype counts.
- The paper compares the output cost of its algorithm (Alg. 4) with Chen et al.’s algorithm (M.C.) in a run-time experiment.Additional experiments reproduce the settings of Figures 6, 2, and 5.
- Figure 10 varies group-specific prototype counts on the Adult data set for two- and five-group demographic partitions.The plots include both unequal and equal allocations across groups.
- Figure 11 compares six summaries of 16 face images produced by the unfair Algorithm 1, the paper’s algorithm, and Celis et al. (2018b).The data set contains 8 female and 8 male faces and is intentionally small for visual inspection.
- Figure 12 repeats the Adult-data-set experiments with the same four alternative group-specific prototype allocations used in Figure 10.It includes two-group and five-group settings, with both equal and unequal allocations.