Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search
Hierarchical clustering is a data analysis method that has been used for decades. Despite its widespread use, the method has an underdeveloped analytical foundation. Having a well understood foundation would both support the currently used methods and help guide future improvements. The goal of this paper is to give an analytic framework to better understand observations seen in practice. This paper considers the dual of a problem framework for hierarchical clustering introduced by Dasgupta [Das16]. The main result is that one of the most popular algorithms used in practice, average linkage agglomerative clustering, has a small constant approximation ratio for this objective. Furthermore, this paper establishes that using bisecting k-means divisive clustering has a very poor lower bound on its approximation ratio for the same objective. However, we show that there are divisive algorithms that perform well with respect to this objective by giving two constant approximation algorithms. This paper is some of the first work to establish guarantees on widely used hierarchical algorithms for a natural objective function. This objective and analysis give insight into what these popular algorithms are optimizing and when they will perform well.
The paper extends the work of Dasgupta towards defining a theoretical framework for evaluating hierarchical clustering. The paper defines an objective function that is equivalent to that of Dasgupta in the sense that an optimal solution for the cost function defined by Dasgupta will also be optimal for the one defined in this paper and vice versa. The behaviour of approximate solution will differ though because the cost function is of the form D(G) - C(T), where D is a constant (depending on the input G) and C(T) is the cost (defined by Dasgupta) and T is the hierarchical solution. The authors show a constant approximation guarantee w.r.t. their objective function for the popular average linkage algorithm for hierarchical clustering. They complement this approximation guarantee by showing that this approximation guarantee is almost tight. They also show that the decisive algorithm for hierarchical clustering gives poor results w.r.t. their objective function. They also claim to show approximation guarantee for a local search based algorithm.
Significance:
The results discussed in the paper are non-trivial extensions to the work of Dasgupta. Even though the model is similar the the previous work, it is interesting in the sense that the paper is able to give theoretical guarantees for the average linkage algorithm that is a popular technique for hierarchical clustering.
Originality:
The paper uses basic set of techniques for analysis and is simple to read. The analysis is original as per my knowledge of the related literature.
Clarity: 
The paper uses simple set of techniques and is simple to read. The authors do a fair job in explaining the results and putting things in context with respect to previous work. The explanations are to the point and simple. There are a few places where more clarity will be appreciated. These are included in the specific comments below.
Quality:
There is a technical error in line 261. It is not clear how the very first inequality is obtained. Furthermore, the last inequality is not justified. The authors should note that as per the analysis, in case (iii) you assume that |B|<=|A| and not the other way around.
Given this, I do not know how to fix these errors in a simple way.
Specific comments:
1. Please use proper references [C] can mean [CC17] or [CKMM17]
2. Line 69: “Let leaves …”. I think you mean leaves denote the set of leaves and not number.
3.Line 91: Please correct the equation. The factor of n is missing from the right hand side.
4. Line 219: Figure 1 is missing from the main submission. Please fix this, as the proof is incomplete without the figure which is given in the appendix.