An arXiv v1 preprint dated 26 August 2026 examines a problem that sits at the heart of fair hierarchical clustering: a system can satisfy fairness checks among close neighbors yet need a much larger allowance to make those checks work across the full tree. The paper frames the task as a feasibility problem. It seeks an ultrametric, a distance structure that encodes a hierarchy, that dominates the input metric, meaning it does not assign smaller distances, while also meeting multiplicative fairness constraints inside each point’s k-nearest-neighbor neighborhood.
Here, slack is the multiplicative factor that allows the hierarchy to meet both demands. Under the paper’s mutual-neighborhood version of fairness, the theory sets a hard lower bound: any dominating fair ultrametric requires slack at least as large as the local mutual heterogeneity ratio. That ratio is therefore a necessary local threshold, not by itself a guarantee that the same factor will be enough globally.
A local floor, not a global answer
The paper constructs a family of n-point metrics with a local mutual ratio of 1 but a minimum feasible global slack that grows on the order of log n. A local check can therefore look perfectly tight while the hierarchy as a whole still needs a much larger factor.
At the same time, the theory offers a general ceiling. For every finite metric with n points and every neighborhood size k of at least 1, it proves that a dominated fair ultrametric exists with multiplicative slack O(log n), or logarithmic-order slack. Another theorem says the minimum feasible slack cannot decrease as k grows.
The analysis also asks how sensitive the local threshold is to small changes in measured distances. It finds Lipschitz-continuous behavior under infinity-norm perturbations, meaning bounded changes assessed by the largest distance change, when the identities of the k nearest neighbors remain stable. The condition limits the claim: if the neighborhood identities change, the stated stability result no longer directly applies.
The gap appears in synthetic metrics
Computational tests showed how widely the local and global figures can separate. The synthetic evaluation used Gaussian mixtures in two-dimensional space and shortest-path metrics from random 3-regular graphs. In Gaussian-mixture instances with k = 3, the local mutual threshold was 5.0830, compared with an algorithmic global slack of 17.46. The reported search returned no feasible hierarchy through alpha = 17 and a feasible one at approximately alpha = 18.
Random 3-regular graph metrics produced a similar separation. The local mutual heterogeneity ratio was 1.0 at n = 32, 64 and 128, while the reported global slack was 5.21, 5.21 and 6.00, respectively. Those values compare a local ratio with a global value returned under the paper’s construction; they should not be read as the two quantities being interchangeable.
The distinction is important because the experimental endpoint is algorithmic. In the study, alpha-star means the smallest alpha for which FCAC returns a feasible ultrametric, so each reported alpha-star is an upper bound on the true feasibility threshold. It is not presented as the exact minimum over every possible ultrametric.
Real data do not behave alike
Tests on real-world data showed still more variation. The evaluation used the Adult, Statlog (German Credit Data) and Iris datasets. On Adult with n = 100, alpha-star rose from 2.53 at k = 1 to 2.91 at k = 3 and then stayed constant in the tested range. German remained approximately 1.48 across the tested neighborhood sizes, while the triangle-based Iris obstruction had alpha-star = 2.
The sample-size comparisons were also dataset-dependent. At k = 3, Adult’s reported slack increased from 2.91 at n = 100 to 11.34 at n = 500. German’s rose from 1.48 at n = 100 to 1.68 at n = 1,000. The increase was much larger for Adult, although these are the reported sample-size points rather than a broad scaling curve.
Lower slack comes with a time cost
FCAC, the paper’s Fairness Constrained Agglomerative Clustering procedure, is the paper’s route from the feasibility formulation to an actual hierarchy. It separates linkage-based merge ordering from the merge heights used to enforce dominance, then applies one-sided neighborhood fairness when choosing which merge to make. Its reported worst-case cost is cubic in n times k for time and quadratic in n for space.
On the Adult dataset with n = 800, a comparison averaged over five random seeds put the tradeoff plainly. FCAC’s MST-based version had mean slack 1.00, with a standard deviation of 0.00, and took 73.19 seconds. FRT had mean slack 67.26, standard deviation 20.59, and took 20.47 seconds. In this reported comparison, FCAC used more time but returned a much lower mean slack.
The measurement has a boundary
A separate perturbation test examined the stability boundary in one instance with alpha-star = 17.46. The absolute change in alpha-star was 0.0000 at perturbations of 0.0000, 0.0011, 0.0022 and 0.0033. It then rose to 0.4987 at 0.0044, 0.9975 at 0.0056 and 5.4862 at 0.0100.
There is also a difference between the theory and the experiments. The key lower-bound theorem uses mutual-neighborhood fairness, while FCAC’s experiments enforce one-sided neighborhood fairness. The results are therefore related, but they are not measurements under exactly the same fairness constraint.
The study’s message is more limited and more precise: the theory supplies a local lower bound and a logarithmic-order existence guarantee, while the experimental alpha-star values remain FCAC-based upper bounds. Across the constructed metrics and listed datasets, the gap changes with the geometry being represented, so the local fairness check alone does not determine the global slack in these examples.
Paper data and sources
Original title: Individual Fairness in Hierarchical Clustering
Authors: Binita Maity, Shrutimoy Das
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text