Summary
This paper studies three different related notions of fair clustering that have been proposed in the literature for metric centroid clustering: (1) proportional fairness, (2) individual fairness, and (3) transferable core. Prior work has separately defined, motivated, and studied the existence and computation of clusterings optimizing all of these notions of fairness.
The present work attempts to synthesize these different notions in two senses. First, the paper shows that up to [small] constant factors, approximate proportional fairness implies approximate individual fairness and vice versa, and approximate proportional fairness implies approximate transferable core.
Second, the paper considers metric adaptations of the concepts of justified representation (mJR) and proportional justified representation (mPJR) from approval-based committee selection, an important fair representation problem in computational social choice, and show that these imply approximations of the aforementioned fair clustering concepts. Specifically, any solution satisfying mJR simultaneously satisfies the best known approximations to individual and proportional fairness, and to the transferable core. The paper shows that the Greedy Capture algorithm from prior work on proportional fairness satisfies this mJR property and thus is simultaneously approximately fair in all three senses. Furthermore, the Expanding Approvals algorithm from prior work satisfies the stronger mPJR property. The paper turns to the implications of mPJR for another generalized notion of proportional fairness (the q-core) in contexts where agents measure cost by distance to the q’th most distant center (q=1 being the typical centroid clustering setting) motivated by prior work in sortition (selecting a fair and representative sample of a population), showing that mPJR implies a 5-approximation for all q.
Finally, the paper shows two additional results extending prior work. First, that the known efficient algorithms (e.g., Greedy Capture and Expanding Approvals) can be extended to handle the case of an infinite number of center candidates (e.g., can select any points in the real plane) by simply considering the set of agents as the candidates, and that this restriction preserves small constant approximations of fairness. Second, that the analysis of the Fair Greedy Capture algorithm from recent work on sortition can be tightened to yield a better constant bound on the approximation of the q-core.
Strengths
The paper does a very good job of providing a comprehensive survey connecting different fair clustering desiderata that have been considered separately in the literature. The result is a convincing story that there is a more “general” phenomenon of proportionality at work in all these group-agnostic structural notions of fairness in clustering. The greatest contribution may therefore be in clarifying the state of the field for future work seeking to extend or build on these notions. It is also nice to see a formal connection between the last several years of work on fair approval-based committee selection in computational social choice and the work in the ML clustering space.
Generally the writing and discussion is clear. Effort has clearly been put into communicating ideas effectively in the forms of the results diagram in figure 1, illustrative examples, and extensive consideration of related work and the connections between other work and the current.
Results are well substantiated by the formal arguments, and claims are all measured and accurate to what is shown.
Weaknesses
The work is largely incremental within the fair clustering space, focusing on the relationship between prior notions of fairness, the existence and computation of which have already been studied. The algorithmic contribution is limited in this sense as well, focusing mostly on tightening or demonstrating relationships between guarantees and analysis. In these senses, the impact of the paper may be limited.
Post-rebuttal clarification to the above: The weakness discussed is really with respect to algorithmic contributions, and I agree that connecting different work in the field is a valuable contribution.
A minor comment: In Lemma 9, lines 315-316, I think it should be “…let C’ be a set of…candidates” and “…there is a set $N^{''} \subseteq N^{'}$...”
Questions
No pressing questions, though if the authors feel that I have misunderstood the potential of the work for improving clustering algorithms in my weaknesses, I would be happy to hear different perspectives.