Research map / Learning theory and algorithms / Clustering
Ultrametric Cluster Hierarchies: I Want ‘em All!
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that optimal k-center and (k,z)-clustering (k-means, k-median) solutions for all k can be computed in Sort(n) time over any ultrametric/LCA-tree, yielding hierarchical solutions, and introduces the SHiP framework combining ultrametric fitting, center-based hierarchies, and partition extraction.
Problem
Center-based clustering (k-means, k-median, k-center) is NP-hard in general, and hierarchical clustering only extracts flat partitions from fixed hierarchies; the paper asks whether these objectives can be solved optimally and quickly over ultrametrics, producing new hierarchies.
Approach
Relaxed ultrametrics are encoded as LCA-trees; in them farthest-first traversal becomes optimal for k-center and reduces to sorting node values, while (k,z)-clustering reduces to k-center on a new LCA-tree of cost-decreases, so all k are solved in Sort(n) time and the resulting center hierarchies are themselves relaxed ultrametrics. The SHiP framework pairs any ultrametric (DC tree, Cover tree, KD
Key results
- Given an ultrametric on n points, all optimal k-center and (k,z)-clustering solutions for every k are obtained in Sort(n) time, and the hierarchy/partition step takes milliseconds after the ultrametric is fit (e.g., dc-dist fit took ~14s on Boxes vs 33ms for k-means hierarchy).
- On the DC tree, SHiP combinations reach ARI 99.3 on Boxes (k-median/MoE) and 92.0 on D31 in the best cases, matching or beating Euclidean k-means (92.0 on D31 with ground-truth k).
- Cover-tree (HST) combinations consistently perform worse than Euclidean k-means, while DC-tree combinations are competitive, indicating the choice of ultrametric matters most.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DC tree instead of Cover tree (ablation) | SHiP clustering combinations · Boxes, D31, airway, lactate, HAR, letterrec., PenDigits, COIL20, COIL100, cmu_faces, OptDigits, USPS, MNIST | ARI | Helped |
| Use the DC tree with k-median/MoE instead of k-center/Stability or k-means/elbow | SHiP · Boxes and airway | ARI | Mixed |
| Use the DC tree with k-means/elbow instead of k-center/Stability or k-median/MoE | SHiP · lactate, HAR, letterrec., PenDigits, cmu_faces, MNIST | ARI | Mixed |
| Use the DC tree with k-center/Stability instead of the other DC-tree pairings | SHiP · COIL20, COIL100 | ARI | Mixed |
| Give SHiP the ground-truth number of clusters for k-median or k-means | DC-tree SHiP · Datasets in Table 6 | ARI | Helped |
Surprising findings
- HST-based ultrametrics (Cover tree, KD tree, HST-DPO) consistently fail to preserve cluster structure, performing worse than Euclidean k-means across hierarchies and partitions.
- Even standard-ultrametric (k,z)-clustering reduces to k-center in a relaxed ultrametric, so relaxed ultrametrics are needed for the proofs.
Limitations
- Clustering quality depends strongly on the choice of ultrametric; HST-based ultrametrics give subpar results.
- The initial ultrametric computation (e.g., DC tree, Cover tree on MNIST) remains the runtime bottleneck.
- Optimal solutions are not unique; the paper's choice among equivalent optimal solutions relies on heuristics discussed only in the appendix.
Experimental setup
Datasets: Boxes D31 airway lactate HAR letterrec PenDigits COIL20 COIL100 cmu_faces OptDigits USPS
Benchmarks: Boxes D31 airway lactate HAR letterrec PenDigits COIL20 COIL100 cmu_faces OptDigits USPS
Metrics: adjusted rand index runtime NMI AMI correlation coefficient
Baselines: k-means Ward agglomerative clustering SCAR AMD-DBSCAN DPC HDBSCAN
Builds on: HDBSCAN DBSCAN farthest-first traversal Cohen-Addad et al. tree k-median Beer et al. dc-dist k-center
Closest papers by meaning
- From Logits to Hierarchies: Hierarchical Clustering made Simple (ICML 2025 · similarity 0.90)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.89)
- Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.89)
- Expected Probabilistic Hierarchies (NeurIPS 2024 · similarity 0.88)
- Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples (NeurIPS 2026 · similarity 0.88)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.