# Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 40 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Discrimination in Online Ad Delivery](https://mlsanity.com/paper/1301.6822/) (2013)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Fair Algorithms for Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2005.03197/) (2020)
- [Protecting the Protected Group: Circumventing Harmful Fairness](https://mlsanity.com/paper/1905.10546/) (2019)
- [Hierarchical Clustering for Euclidean Data](https://mlsanity.com/paper/1812.10582/) (2018)

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

- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Fair Polylog-Approximate Low-Cost Hierarchical Clustering](https://mlsanity.com/paper/2311.12501/) (2023)
- [Robust Fair Clustering with Group Membership Uncertainty Sets](https://mlsanity.com/paper/2406.00599/) (2024)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)

## Abstract (arXiv)

Clustering is a fundamental building block of modern statistical analysis pipelines. Fair clustering has seen much attention from the machine learning community in recent years. We are some of the first to study fairness in the context of hierarchical clustering, after the results of Ahmadian et al. from NeurIPS in 2020. We evaluate our results using Dasgupta's cost function, perhaps one of the most prevalent theoretical metrics for hierarchical clustering evaluation. Our work vastly improves the previous O(n5/6polylog(n)) fair approximation for cost to a near polylogarithmic O(nδ polylog(n)) fair approximation for any constant δ∈(0,1). This result establishes a cost-fairness tradeoff and extends to broader fairness constraints than the previous work. We also show how to alter existing hierarchical clusterings to guarantee fairness and cluster balance across any level in the hierarchy.