Source-linked AI summary
Individual Fairness in Hierarchical Clustering
Binita Maity, Shrutimoy Das
TL;DR
Hierarchical clustering can distort local similarities because ultrametric structure imposes global constraints. The paper formulates individual fairness as feasibility over dominated ultrametrics, characterizes minimal slack, and establishes sharp local thresholds, stability, monotonicity, and an intrinsic Θ(log n) local-global separation, with empirical support.
Problem
Hierarchical clustering lacks guarantees that nearby individuals receive similar treatment, motivating fairness constraints that bound relative distortion within local k-nearest neighborhoods.
Method
The paper seeks dominated ultrametrics that satisfy local multiplicative fairness constraints and analyzes the minimal slack required for feasibility.
Results
The paper identifies a sharp local threshold, proves stability and monotonicity in k, establishes an intrinsic Θ(log n) local-global separation, and reports consistent empirical patterns.
Takeaways & Limitations
Local feasibility conditions need not determine global realizability, so fairness slack reflects both neighborhood structure and global ultrametric geometry.
Takeaways & Limitations
The precise computational complexity of deciding feasibility over all ultrametrics, and tractable structural subclasses, remain open.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames individual fairness in hierarchical clustering as the problem of reconciling local similarity constraints with globally constrained ultrametric structure. It develops theoretical characterizations, algorithmic support, and empirical validation.
- Motivation: Hierarchical clustering can distort distances between nearby points because early merge decisions propagate through coarser tree resolutions.This may produce large relative distortion for individual points despite a reasonable overall hierarchy.
- Problem formulation: The authors seek a dominated ultrametric satisfying multiplicative fairness constraints within k-nearest neighborhoods.The central quantity is the minimal slack α⋆(d, k) needed for feasibility.
- Theoretical results: A sharp local threshold αmut_k(d) makes fairness infeasible whenever slack falls below that value.The threshold is determined by scale heterogeneity within mutual k-nearest neighborhoods.
- Theoretical results: The minimal feasible slack α⋆(d, k) is stable under bounded perturbations preserving neighborhood identities and nondecreasing in k.These results describe how metric perturbations and stronger neighborhood constraints affect feasibility.
- Local-global separation: Some metric families have αmut_k(d) = 1 yet every dominating ultrametric requires Θ(log n) distortion.Theorem 3 supplies matching O(log n) sufficiency guarantees through classical tree embedding techniques.
- Empirical evaluation: Experiments on five synthetic and real-world datasets validate the theoretical claims, including sharp feasibility thresholds and dataset-dependent distortion regimes.Observed behavior also includes saturation in neighborhood size.
2 Related Work
The paper distinguishes its geometric feasibility perspective from prior work on individually fair clustering, tree embeddings, and constrained or objective-based hierarchical clustering.
- Individual fairness and clustering: Prior individual-fairness clustering work includes several algorithms and scalable variants, whereas this paper studies structural feasibility in hierarchical clustering.
- Hierarchical clustering and tree embeddings: The ultrametric interpretation connects hierarchical clustering to dendrograms, tree metrics, and classical probabilistic tree embeddings.These embedding results underpin the paper’s sufficiency guarantees and interpret fairness slack as embedding distortion.
- Constrained hierarchical clustering: Unlike prior pairwise or triplet-constrained and objective-based approaches, the paper characterizes intrinsic distortion bounds imposed by ultrametric structure.
3 Problem Setup
The problem setup represents hierarchical clusterings as ultrametrics on a finite metric space and imposes dominance, neighborhood-based fairness, and feasibility through minimal multiplicative slack.
- Dendrograms and ultrametrics: A dendrogram is a rooted tree whose leaves correspond to points and whose nondecreasing node heights induce merge heights.For points i and j, u(i, j) is the height of their lowest common ancestor.
- Dendrograms and ultrametrics: Ultrametrics satisfy the strong triangle inequality u(i, j) ≤ max{u(i, k), u(k, j)} and correspond one-to-one with dendrograms.
- Neighborhoods: The fairness framework uses k nearest neighbors under d, with deterministic tie-breaking and strict separation at the k-th-distance boundary for stability results.
- Fair ultrametrics: A dominated ultrametric satisfies u(i, j) ≥ d(i, j), preventing distance contraction.
- Fair ultrametrics: Individual fairness is specialized to ultrametrics through a feasible set parameterized by k, α, and β, with symmetric local Lipschitz constraints among neighbors.
- Feasibility and slack: Feasibility asks whether such an ultrametric exists, while α⋆(d, k) measures the smallest multiplicative distortion needed for feasibility.
4 Feasibility Theory
The paper characterizes feasibility of individually fair ultrametrics through local neighborhood heterogeneity, stability, and monotonicity, then establishes a logarithmic gap between local and global realizability.
- Feasibility formulation: Feasibility asks whether a dominating ultrametric can satisfy multiplicative fairness constraints within k-nearest neighborhoods.The minimal feasible slack is denoted α⋆(d, k).
- Local necessary slack: The local mutual heterogeneity ratio measures maximum scale separation within mutual k-nearest-neighbor stars and equals 1 when the metric is locally ultrametric.The ratio provides a necessary lower bound on feasible multiplicative slack.
- Stability: Bounded ℓ∞ perturbations preserve the relevant neighborhood structure under ε-stability, making the threshold Lipschitz-stable.The k-nearest-neighbor sets remain identical when the k-th and (k+1)-th distances are sufficiently separated.
- Intrinsic local-global gap: Θ(log n) separates local and global realizability: some metrics have αmut_k(d)=1 while every feasible ultrametric requires logarithmic slack.Tree-embedding theory supplies a matching O(log n) sufficiency guarantee.
- Monotonicity: The minimal feasible slack is nondecreasing in k because larger neighborhoods impose all constraints from smaller neighborhoods and possibly additional ones.Thus strengthening local fairness constraints cannot reduce the required slack.
5 Fairness Constrained Agglomerative Clustering (FCAC)
FCAC adapts agglomerative clustering by enforcing fairness during merge selection while assigning dominance-preserving merge heights; it is sound when it returns an ultrametric, but general feasibility remains combinatorial.
- Merge construction: FCAC uses linkage only to order candidate merges and assigns each merge height as the larger of linkage and cross-cluster metric diameter.This construction ensures merge heights dominate all cross-cluster distances.
- Merge selection: FCAC selects the smallest linkage-ordered merge satisfying the fairness constraint and returns Infeasible if no candidate qualifies.Accepted merges assign their height to every cross-cluster pair.
- Ultrametric validity: Nondecreasing dominance heights ensure that the constructed distance function is an ultrametric.Cluster enlargement makes cross-cluster maxima nondecreasing across iterations.
- Correctness: When FCAC returns an ultrametric, the output satisfies both dominance and one-sided neighborhood fairness.The algorithm verifies the fairness bound when each neighborhood pair first joins a cluster.
- Complexity: FCAC has worst-case time complexity O(n^3k) and space usage O(n^2).The runtime accounts for candidate cluster pairs, neighborhood checks, and up to n−1 merges.
- Feasibility complexity: For a fixed dendrogram feasibility is polynomially verifiable, but deciding existence over all ultrametrics remains combinatorial and its precise complexity is open.Local consistency does not guarantee global realizability because merge heights are globally coupled through the tree.
6 Experimental Results
Experiments evaluate feasibility thresholds, local–global distortion gaps, scaling with instance size and neighborhood size, and algorithmic performance on synthetic and real-world metrics.
- FCAC experiments measure α⋆(d, k) as the smallest slack yielding a feasible ultrametric, providing algorithmic upper bounds on the true threshold.
- Synthetic Datasets: αmut_k(dn) = 1 while α⋆(dn) is strictly larger on random 3-regular graph metrics, demonstrating global distortion despite uniform local scale.
- Synthetic Datasets: α⋆ grows with n on random 3-regular graph metrics, indicating that larger instances amplify intrinsic global obstruction.
- Real world results: Adult shows two-phase neighborhood behavior: α⋆ rises from 2.53 at k = 1 to 2.91 at k = 3, then stabilizes, while αmut(k) continues increasing.
- Real world results: Adult α⋆(k = 3) increases from 2.91 at n = 100 to 11.34 at n = 500, whereas German rises mildly from 1.48 at n = 100 to 1.68 at n = 1000.
- Real world results: FCAC attains unit slack on Adult at n = 800, while FRT has substantially larger empirical distortion despite its expected O(log n) guarantee.FCAC requires increased computational cost.
7 Conclusion and Future Work
The paper frames individual fairness in hierarchical clustering as feasibility of dominated ultrametrics with bounded local distortion. It establishes sharp thresholds, stability, monotonicity, and a Θ(log n) local–global separation, while identifying computational scalability as an open direction.
- The framework studies individual fairness through dominated ultrametric embeddings and interprets multiplicative distortion as the slack needed to reconcile local constraints with hierarchy.
- The paper identifies an intrinsic Θ(log n) separation between local feasibility and global realizability, alongside sharp feasibility transitions and dataset-dependent distortion regimes.
- Future Work: The computational complexity of feasibility and scalable approximation algorithms remain open directions.
- Classical tree-embedding theory supplies O(log n) sufficiency guarantees for fairness feasibility.
B Proof of Proposition 1
The proof constructs constant-degree expander metrics with trivial local structure but logarithmic global ultrametric distortion, establishing the intrinsic local–global gap.
- A constant-degree expander graph G_n uses its shortest-path metric d_n, with degree D independent of n.
- For k = D, graph neighbors are exactly mutual k-nearest neighbors and each has distance 1, yielding αmut_k(d_n) = 1.
- Every tree embedding of a constant-degree expander’s shortest-path metric incurs Ω(log n) distortion.
- Because ultrametrics are tree metrics, the same lower bound applies to every dominating ultrametric.
- At least one fairness-constrained edge therefore requires Ω(log n) multiplicative slack, establishing the intrinsic gap.
C Experimental Results
Additional experiments examine neighborhood-size effects and perturbation stability, showing that stronger local constraints require larger slack while small perturbations preserve the distortion parameter.
- Increasing k strengthens fairness constraints and requires progressively larger global distortion on Gaussian data.
- The stability table reports α⋆ remaining unchanged under sufficiently small ℓ∞ perturbations and changing only after neighborhood identities are altered.
C.1 Synthetic dataset
On Gaussian data, increasing neighborhood size k rapidly raises the minimal slack α⋆, while bounded metric perturbations leave it stable until nearest-neighbor identities change. Overall, α⋆ captures the trade-off between stronger local fairness constraints and global ultrametric consistency.
- Larger k imposes fairness constraints on more pairs, tightening the local Lipschitz requirements.
- α⋆ increases rapidly as k grows, reflecting geometric tension between broader neighborhood fairness and ultrametric structure.
- For α⋆=17.46, metric perturbations were evaluated through the observed variation |∆α| := |α⋆(d′) −α⋆(d)|.
- For ϵ ≤0.003, α⋆ remains unchanged; deviations occur only after nearest-neighbor identities shift.
- α⋆ exhibits sharp feasibility thresholds, grows with structural complexity, increases with stronger fairness constraints, and remains stable under bounded perturbations.
C.2 real world dataset
Real-world datasets show that fairness-constrained hierarchical compatibility is dataset dependent, with local constraints eventually overtaking global ultrametric obstruction as k grows. Comparisons between experimental and mutual thresholds require care because they use different neighborhood-fairness formulations.
- German Credit has low distortion, with α⋆≈1.5–1.7, indicating proximity to hierarchical structure.
- Adult requires substantially larger slack than German Credit, particularly as sample size increases.
- Local Global Gap: For both Adult and German, the local-global gap is positive at k = 1 but becomes negative for larger k.
- Local Global Gap: The gap sign reversal marks a transition from geometry-dominated to combinatorially dominated infeasibility.
- Experiments enforce one-sided neighborhood fairness, whereas αmut(k) uses the mutual formulation, so the two thresholds need not coincide.