Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

Hierarchical clustering (HC) is the recursive partitioning of a dataset into increasingly smaller clusters via an effective binary tree representation, and has been employed as a standard package in data analysis with widespread applications in practice. Traditional HC algorithms are typically based on agglomerative heuristics and, due to the lack of a clear objective function, there was limited work on their analysis. Dasgupta [Das16] introduced a simple cost function for hierarchical clustering, and this work has inspired a number of algorithmic studies on hierarchical clustering. In this paper we study efficient hierarchical clustering for graphs with a clear structure of clusters.