# Hierarchical Clustering via Spreading Metrics

arXiv: https://arxiv.org/abs/1610.09269 · HTML: https://mlsanity.com/paper/1610.09269/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2016.

## Built on by (most cited first, 17 of 17)

- [Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time](https://mlsanity.com/paper/2106.05610/) (2021)
- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs](https://mlsanity.com/paper/2306.09950/) (2023)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Hierarchical clustering with dot products recovers hidden tree structure](https://mlsanity.com/paper/2305.15022/) (2023)
- [Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints](https://mlsanity.com/paper/2401.07091/) (2024)
- [Exact and Approximate Hierarchical Clustering Using A*](https://mlsanity.com/paper/2104.07061/) (2021)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)
- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)
- [An objective function for order preserving hierarchical clustering](https://mlsanity.com/paper/2109.04266/) (2021)
- [Expanding the class of global objective functions for dissimilarity-based hierarchical clustering](https://mlsanity.com/paper/2207.14375/) (2022)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Rethinking Divisive Hierarchical Clustering from a Distributional Perspective](https://mlsanity.com/paper/2601.19718/) (2026)
- [Multi-Domain Learning with Global Expert Mapping](https://mlsanity.com/paper/2604.18842/) (2026)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)

## Abstract (arXiv)

We study the cost function for hierarchical clusterings introduced by [arXiv:1510.05043] where hierarchies are treated as first-class objects rather than deriving their cost from projections into flat clusters. It was also shown in [arXiv:1510.05043] that a top-down algorithm returns a hierarchical clustering of cost at most Oleft(αn log nright) times the cost of the optimal hierarchical clustering, where αn is the approximation ratio of the Sparsest Cut subroutine used. Thus using the best known approximation algorithm for Sparsest Cut due to Arora-Rao-Vazirani, the top down algorithm returns a hierarchical clustering of cost at most Oleft(log3/2 nright) times the cost of the optimal solution. We improve this by giving an O(logn)-approximation algorithm for this problem. Our main technical ingredients are a combinatorial characterization of ultrametrics induced by this cost function, deriving an Integer Linear Programming (ILP) formulation for this family of ultrametrics, and showing how to iteratively round an LP relaxation of this formulation by using the idea of sphere growing which has been extensively used in the context of graph partitioning. We also prove that our algorithm returns an O(logn)-approximate hierarchical clustering for a generalization of this cost function also studied in [arXiv:1510.05043]. Experiments show that the hierarchies found by using the ILP formulation as well as our rounding algorithm often have better projections into flat clusters than the standard linkage based algorithms. We also give constant factor inapproximability results for this problem.