# Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics

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

## Key facts

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

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

- [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)
- [An Information-theoretic Perspective of Hierarchical Clustering](https://mlsanity.com/paper/2108.06036/) (2021)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)
- [HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering](https://mlsanity.com/paper/2205.09721/) (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)
- [Fair Polylog-Approximate Low-Cost Hierarchical Clustering](https://mlsanity.com/paper/2311.12501/) (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)
- [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)
- [Hierarchical Clustering via Local Search](https://mlsanity.com/paper/2405.15983/) (2024)
- [A Greedy Strategy for Graph Cut](https://mlsanity.com/paper/2412.20035/) (2024)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Characterizing Admissible Objective Functions for Hierarchical Clustering](https://mlsanity.com/paper/2604.23628/) (2026)
- [Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation](https://mlsanity.com/paper/2605.00529/) (2026)
- [Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Nets](https://mlsanity.com/paper/2606.09051/) (2026)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)
- [Hierarchical F-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs](https://mlsanity.com/paper/2607.13217/) (2026)
- [Graph Partitioning with Demands: Generalized Conductance and its Applications](https://mlsanity.com/paper/2607.13218/) (2026)
- [Prefix Sharing Is a Sorting Problem](https://mlsanity.com/paper/2609.13692/) (2026)

## Abstract (arXiv)

Dasgupta recently introduced a cost function for the hierarchical clustering of a set of points given pairwise similarities between them. He showed that this function is NP-hard to optimize, but a top-down recursive partitioning heuristic based on an alpha_n-approximation algorithm for uniform sparsest cut gives an approximation of O(alpha_n log n) (the current best algorithm has alpha_n=O(sqrt{log n})). We show that the aforementioned sparsest cut heuristic in fact obtains an O(alpha_n)-approximation for hierarchical clustering. The algorithm also applies to a generalized cost function studied by Dasgupta. Moreover, we obtain a strong inapproximability result, showing that the hierarchical clustering objective is hard to approximate to within any constant factor assuming the Small-Set Expansion (SSE) Hypothesis. Finally, we discuss approximation algorithms based on convex relaxations. We present a spreading metric SDP relaxation for the problem and show that it has integrality gap at most O(sqrt{log n}). The advantage of the SDP relative to the sparsest cut heuristic is that it provides an explicit lower bound on the optimal solution and could potentially yield an even better approximation for hierarchical clustering. In fact our analysis of this SDP served as the inspiration for our improved analysis of the sparsest cut heuristic. We also show that a spreading metric LP relaxation gives an O(log n)-approximation.