# Sublinear Algorithms for Hierarchical Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 67 references that are in the map.
- First posted on arXiv 15 Jun 2022.

## Builds on (most cited first, 23 of 23)

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training](https://mlsanity.com/paper/2104.11981/) (2021)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Hierarchical Clustering better than Average-Linkage](https://mlsanity.com/paper/1808.02227/) (2018)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Communication Steps for Parallel Query Processing](https://mlsanity.com/paper/1306.5972/) (2013)
- [Scaling Hierarchical Agglomerative Clustering to Billion-sized Datasets](https://mlsanity.com/paper/2105.11653/) (2021)
- [Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection](https://mlsanity.com/paper/1912.06983/) (2019)
- [Hierarchical Clustering: a 0.585 Revenue Approximation](https://mlsanity.com/paper/2006.01933/) (2020)
- [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)
- [Parallel Algorithms for Geometric Graph Problems](https://mlsanity.com/paper/1401.0042/) (2013)
- [Hierarchical Clustering for Euclidean Data](https://mlsanity.com/paper/1812.10582/) (2018)
- [Near-linear Size Hypergraph Cut Sparsifiers](https://mlsanity.com/paper/2009.04992/) (2020)
- [Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under ℓp-Distances](https://mlsanity.com/paper/1710.01431/) (2017)
- [Probabilistic Spectral Sparsification In Sublinear Time](https://mlsanity.com/paper/1401.0085/) (2013)
- [Communities and Hierarchical Structures in Dynamic Social Networks: Analysis and Visualization](https://mlsanity.com/paper/1409.5040/) (2014)
- [Improved Hierarchical Clustering on Massive Datasets with Broad Guarantees](https://mlsanity.com/paper/2101.04818/) (2021)
- [Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries](https://mlsanity.com/paper/2106.10386/) (2021)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)

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

- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)

## Abstract (arXiv)

Hierarchical clustering over graphs is a fundamental task in data mining and machine learning with applications in domains such as phylogenetics, social network analysis, and information retrieval. Specifically, we consider the recently popularized objective function for hierarchical clustering due to Dasgupta. Previous algorithms for (approximately) minimizing this objective function require linear time/space complexity. In many applications the underlying graph can be massive in size making it computationally challenging to process the graph even using a linear time/space algorithm. As a result, there is a strong interest in designing algorithms that can perform global computation using only sublinear resources. The focus of this work is to study hierarchical clustering for massive graphs under three well-studied models of sublinear computation which focus on space, time, and communication, respectively, as the primary resources to optimize: (1) (dynamic) streaming model where edges are presented as a stream, (2) query model where the graph is queried using neighbor and degree queries, (3) MPC model where the graph edges are partitioned over several machines connected via a communication channel. We design sublinear algorithms for hierarchical clustering in all three models above. At the heart of our algorithmic results is a view of the objective in terms of cuts in the graph, which allows us to use a relaxed notion of cut sparsifiers to do hierarchical clustering while introducing only a small distortion in the objective function. Our main algorithmic contributions are then to show how cut sparsifiers of the desired form can be efficiently constructed in the query model and the MPC model. We complement our algorithmic results by establishing nearly matching lower bounds that rule out the possibility of designing better algorithms in each of these models.