Individual Fairness in Hierarchical Clustering

Binita Maity; Shrutimoy Das

cs.LGAug 26, 2026

Individual Fairness in Hierarchical Clustering

Authors: Binita Maity, Shrutimoy Das

Organizations: Indian Institute of Technology, Gandhinagar

Abstract

Hierarchical clustering produces ultrametric representations that impose strong global geometric constraints and may distort local similarities in ways that disproportionately affect individual data points. We study hierarchical clustering under an individual fairness requirement that bounds relative distortion within local $k$ -nearest neighborhoods. We formulate this requirement as a feasibility problem over dominated ultrametrics and characterize the minimal multiplicative slack required for feasibility. We identify a sharp local threshold, prove stability under bounded perturbations, establish monotonicity in $k$ , and show an intrinsic $Θ(\log n)$ separation between local and global realizability. Experiments on synthetic and real world datasets support our theoretical results.

Figures & tables

Panel of Figure 1 — Figure 1: Feasibility threshold in Gaussian mixture data.

$n$	$\alpha_{k}^{\mathrm{mut}}(d_{n})$	$\alpha^{\star}(d_{n})$
32	1.0	5.21
64	1.0	5.21
128	1.0	6.00

Table 1: Shortest path metrics of random

3

regular graphs. Although the local mutual heterogeneity ratio equals

1

, the minimal feasible global slack

\alpha^{\star}

is strictly larger, demonstrating a strict local–global separation.

Panel of Figure 2 — Figure 2: Growth of minimal distortion parameter $\alpha^{\star}$ with instance size $n$ .

Panel of Figure 3 — Figure 3: Minimal slack $\alpha^{\star}(d,k)$ versus neighborhood size $k$ . Obstruction saturates at small $k$ across datasets.

Panel of Figure 4 — Figure 4: Scaling of minimal slack $\alpha^{\star}(k=3)$ with sample size. Adult exhibits strong growth, while German remains stable.

Method	Mean Slack $\alpha$	Std	Runtime (s)
FCAC (MST-based)	1.00	0.00	73.19
FRT	67.26	20.59	20.47

Table 2: Slack and runtime comparison on Adult (

n=800

). While FRT provides an expected

O(\log n)

distortion guarantee (

\log n\approx 6.68

), its empirical slack is substantially larger. FCAC achieves unit slack at increased computational cost.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Minimal slack $\alpha^{\star}$ as a function of neighborhood size $k$ on Gaussian data. Increasing $k$ strengthens fairness constraints and requires progressively larger global distortion.

$\epsilon$	$\|\Delta\alpha\|$
0.0000	0.0000
0.0011	0.0000
0.0022	0.0000
0.0033	0.0000
0.0044	0.4987
0.0056	0.9975

Appendix

Table 3: Stability of

\alpha^{\star}

under

\ell_{\infty}

metric perturbations. The distortion parameter remains unchanged for sufficiently small

\epsilon

and changes only once neighborhood identities are altered.

Panel of Figure 6 — Figure 6: Local global gap $\alpha^{\star}(d,k)-\alpha_{\mathrm{mut}}(k)$ . The sign reversal reflects transition from global obstruction to local constraint explosion.

Hierarchical Clustering

Hierarchical clustering organizes data into nested groups, revealing structure at multiple scales through trees of successive merges or splits.

See all 28 papers

Fast and effective algorithms for fair clustering at scale
May 13, 2026Claudio Mantuano, Manuel Kammermann, Philipp BaumannClustering Algorithmic Fairness
Department of Business Administration, University of Bern, Engehaldenstrasse 4, 3012 Bern, Switzerland
UniFair: A unified fair clustering approach based on separation and compactness
Jun 3, 2026Antonia Karra, Vasiliki Papanikou, Georgios Vardakas +2Clustering Algorithmic Fairness
University of Ioannina, Greece · Archimedes/Athena Research Center, Greece
Proportionally Representative Clustering
Apr 27, 2023Haris Aziz, Barton E. Lee, Sean Morota Chu +1Clustering Algorithmic Fairness
UNSW Sydney · ETH Zürich · Northwestern University

May 13, 2026J/K move · Enter open · S save

Fast and effective algorithms for fair clustering at scale

Claudio Mantuano, Manuel Kammermann, Philipp Baumann

Department of Business Administration, University of Bern, Engehaldenstrasse 4, 3012 Bern, Switzerland

Clustering Algorithmic Fairness Group Fairness

Open paper AskPDF arXiv

Clustering is an unsupervised machine learning task that consists of identifying groups of similar objects. It has numerous applications and is increasingly used in fairness-sensitive domains where objects represent individuals, such as customers, employees, or students. We address a fair clustering problem in which objects belong to protected groups. The problem consists of partitioning the objects into a predefined number of clusters while attaining a user-defined target level of fairness, meaning that each protected group is sufficiently represented in each cluster. The objective is to minimize the clustering cost, defined as the sum of squared Euclidean distances between the objects and the centers of their clusters. Since clustering cost and fairness are generally in conflict, managing the trade-off between them is essential in practical applications. Existing methods provide limited control over this trade-off and either fail to scale to large datasets or, when they scale, produce low-quality solutions. We propose a general framework for fair clustering that provides precise control over the cost-fairness trade-off and introduce three heuristics based on it. The first heuristic focuses on solution quality and the flexibility to incorporate additional constraints, the second improves scalability while retaining high solution quality, and the third is designed for maximum scalability, producing solutions for instances with millions of objects in seconds. The proposed heuristics outperform existing approaches in comprehensive numerical experiments on benchmark datasets. The source code of our heuristics and instructions for reproducing the experiments are publicly available on GitHub.

Abstract

Hierarchical Clustering

Explore similar work

Fast and effective algorithms for fair clustering at scale

UniFair: A unified fair clustering approach based on separation and compactness

Proportionally Representative Clustering