mlsanityData to 14 Oct 2026

Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

arXiv 2306.09950 ↗First posted 16 Jun 2023cs.DS cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

This paper presents two efficient hierarchical clustering (HC) algorithms with respect to Dasgupta's cost function. For any input graph G with a clear cluster-structure, our designed algorithms run in nearly-linear time in the input size of G, and return an O(1)-approximate HC tree with respect to Dasgupta's cost function. We compare the performance of our algorithm against the previous state-of-the-art on synthetic and real-world datasets and show that our designed algorithm produces comparable or better HC trees with much lower running time.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 13 of its 39 references that are in the map. First posted on arXiv 16 Jun 2023.

Builds on

13 of 39 references.

References · 13

  1. 2015A cost function for similarity-based hierarchical clusteringcited by 63
  2. 2018GEMSEC: Graph Embedding with Self Clusteringcited by 61
  3. 2016Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metricscited by 26
  4. 2016Hierarchical Clustering via Spreading Metricscited by 17
  5. 2018Hierarchical Clustering better than Average-Linkagecited by 16
  6. 2022A Tighter Analysis of Spectral Clustering, and Beyondcited by 13
  7. 2019Improved Analysis of Spectral Algorithm for Clusteringcited by 8
  8. 2019Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisectioncited by 8
  9. 2020Hierarchical Clustering: a 0.585 Revenue Approximationcited by 8
  10. 2021Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphscited by 8
  11. 2013Partitioning into Expanderscited by 7
  12. 2019Online Hierarchical Clustering Approximationscited by 7
1 more
  1. 2022Approximating Dasgupta Cost in Sublinear Time from a Few Random Seedscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 2; 2026: 2.

7 papers.

  1. 2023Unsupervised Skin Lesion Segmentation via Structural Entropy Minimization on Multi-Scale Superpixel Graphscited by 7
  2. 2025Hyperbolic Continuous Structural Entropy for Hierarchical Clusteringcited by 3
  3. 2023USL-Net: Uncertainty Self-Learning Network for Unsupervised Skin Lesion Segmentationcited by 2
  4. 2024A Spectral Framework for Tracking Communities in Evolving Networkscited by 0
  5. 2025On the Price of Differential Privacy for Hierarchical Clusteringcited by 0
  6. 2026Rethinking Divisive Hierarchical Clustering from a Distributional Perspectivecited by 0
  7. 2026Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examplescited by 0