Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost
This work addresses fairness in hierarchical clustering for statistical analysis, representing an incremental advance over prior results.
The paper tackles the problem of ensuring fairness and balance in hierarchical clustering, improving the fair approximation cost from O(n^{5/6} poly log(n)) to O(n^δ poly log(n)) for any constant δ in (0,1), establishing a cost-fairness tradeoff and extending to broader fairness constraints.
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(n^{5/6}poly\log(n))$ fair approximation for cost to a near polylogarithmic $O(n^δpoly\log(n))$ fair approximation for any constant $δ\in(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.