Search papers, labs, and topics across Lattice.
This paper investigates the effects of hierarchical clustering on individual fairness by imposing constraints on relative distortion within local $k$-nearest neighborhoods. The authors formulate this challenge as a feasibility problem over dominated ultrametrics, revealing a critical local threshold and proving stability under bounded perturbations. Their findings demonstrate a significant $\Theta(\log n)$ separation between local and global realizability, supported by experiments on both synthetic and real-world datasets.
Individual fairness in hierarchical clustering can be achieved without sacrificing local similarities, revealing a surprising $\Theta(\log n)$ gap between local and global constraints.
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 $\Theta(\log n)$ separation between local and global realizability. Experiments on synthetic and real world datasets support our theoretical results.
