Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

Code

• github.com/steinarlaenen/nearly-optimal-hierarchical-clustering-for-well-clustered-graphs
  OfficialIn papernone★ 2

Abstract

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.

Tasks

Reproductions