# Proportional Fairness in Non-Centroid Clustering

arXiv: https://arxiv.org/abs/2410.23273 · HTML: https://mlsanity.com/paper/2410.23273/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 30 Oct 2024.

## Builds on (most cited first, 9 of 9)

- [Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraints](https://mlsanity.com/paper/1910.01991/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Proportional Participatory Budgeting with Additive Utilities](https://mlsanity.com/paper/2008.13276/) (2020)
- [Fairness in Federated Learning via Core-Stability](https://mlsanity.com/paper/2211.02091/) (2022)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Fractional Hedonic Games](https://mlsanity.com/paper/1705.10116/) (2017)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Social Clustering in Epidemic Spread on Coevolving Networks](https://mlsanity.com/paper/1707.04933/) (2017)

## Built on by (most cited first, 6 of 6)

- [Metritocracy: Representative Metrics for Lite Benchmarks](https://mlsanity.com/paper/2506.09813/) (2025)
- [Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals](https://mlsanity.com/paper/2601.16091/) (2026)
- [The Core in Max-Loss Non-Centroid Clustering Can Be Empty](https://mlsanity.com/paper/2511.19107/) (2025)
- [Fair Transit Stop Placement: A Clustering Perspective and Beyond](https://mlsanity.com/paper/2602.06776/) (2026)
- [Online Multi-Class Selection with Group Fairness Guarantee](https://mlsanity.com/paper/2510.21055/) (2025)
- [Optimally Selecting Representative Agents from a Metric Space](https://mlsanity.com/paper/2608.29097/) (2026)

## Abstract (arXiv)

We revisit the recently developed framework of proportionally fair clustering, where the goal is to provide group fairness guarantees that become stronger for groups of data points (agents) that are large and cohesive. Prior work applies this framework to centroid clustering, where the loss of an agent is its distance to the centroid assigned to its cluster. We expand the framework to non-centroid clustering, where the loss of an agent is a function of the other agents in its cluster, by adapting two proportional fairness criteria -- the core and its relaxation, fully justified representation (FJR) -- to this setting. We show that the core can be approximated only under structured loss functions, and even then, the best approximation we are able to establish, using an adaptation of the GreedyCapture algorithm developed for centroid clustering [Chen et al., 2019; Micha and Shah, 2020], is unappealing for a natural loss function. In contrast, we design a new (inefficient) algorithm, GreedyCohesiveClustering, which achieves the relaxation FJR exactly under arbitrary loss functions, and show that the efficient GreedyCapture algorithm achieves a constant approximation of FJR. We also design an efficient auditing algorithm, which estimates the FJR approximation of any given clustering solution up to a constant factor. Our experiments on real data suggest that traditional clustering algorithms are highly unfair, whereas GreedyCapture is considerably fairer and incurs only a modest loss in common clustering objectives.