Hierarchical Clustering Beyond the Worst-Case
Hiererachical clustering, that is computing a recursive partitioning of a dataset to obtain clusters at increasingly finer granularity is a fundamental problem in data analysis. Although hierarchical clustering has mostly been studied through procedures such as linkage algorithms, or top-down heuristics, rather than as optimization problems, Dasgupta [9] recently proposed an objective function for hierarchical clustering and initiated a line of work developing algorithms that explicitly optimize an objective (see also [7, 22, 8]). In this paper, we consider a fairly general random graph model for hierarchical clustering, called the hierarchical stochastic block model (HSBM), and show that in certain regimes the SVD approach of McSherry [18]  combined with specific linkage methods results in a clustering that give an Op1q approximation to Dasgupta's cost function. Finally, we report empirical evaluation on synthetic and real-world data showing that our proposed SVD-based method does indeed achieve a better cost than other widely-used heurstics and also results in a better classification accuracy when the underlying problem was that of multi-class classification.
Summary of paper:
The paper studies hierarchical clustering in the recent framework of [1], which provides a formal  cost function for the problem. [4] proposed a hierarchical stochastic block model (HSBM) for this problem, and showed that under this model, one can obtain a constant factor approximation of Dasgupta’s cost function [1]. 
The present work generalises the HSBM model slightly, where they do not restrict the number of clusters to be fixed, and hence, the cluster sizes may be sub-linear in the data size. The authors prove guarantees of a proposed algorithm under this model. They further extend their analysis to a semi-random setting where an adversary may remove some inter-cluster edges.
They also perform experiments on some benchmark datasets to show the performance of the method.
Quality:
The paper is of decent quality. While the paper is theoretically sound, the experiment section is not very convincing. Why would one consider 5 flat cluster datasets and only one hierarchical dataset in a hierarchical clustering paper? Even for the last case, only a subset of 6 classes are used. Further, 3 out of 5 methods in comparison are variations of Linkage++, the other two being two standard agglomerative techniques. What about divisive algorithms?
Clarity:
Most parts of the paper can be followed, but in some places, the authors compressed the material a lot and one needs to refer to cited papers for intuitive understanding (for instance, Definition 2.1). There are minor typos throughout the paper, example in lines 41, 114, 126, 179, 201, 342. 
Originality:
The paper derives a considerable portion from [4]. Though some extensions are claimed, I wonder if there is any technical challenges in proving the additional results (I did not see the details in supplementary).
For example, is there any difference between Linkage++ and the method in [4]? Apparently I did not find any significant difference.
The analysis on HSBM may allow growing k, but is there truly a challenge in doing so. At least for first step of algorithm, achieving n_min > \sqrt{n}  does not seem a big hurdle.
Analysis on the semi-random setting is new, but I wonder if there are any challenges in this scenario. Or does it immediately follow from combining HSBM analysis with standard techniques of semi-random graph partitioning?
Significance:
In general, hierarchical clustering in the framework of [1] has considerable significance, and [4] is also a quite interesting paper. However, I consider the present paper a minor extension of [4], with the only possible interesting aspect being the result in the semi-random setting. 
---------------------------
Update after rebuttal:
I thank the authors for clarifying the technical challenges with proving the new results. Hence, I have now increased my score (though I am still concerned about the algorithmic and experimental contributions).
Regarding the experiments, I do agree that there are not many well-defined benchmark out there. The papers that I know are also from early 2000s, but the authors may want to check the datasets used here:
1. Zhao, Karypis. Hierarchical Clustering Algorithms for Document Datasets. Data Mining and Knowledge Discovery, 2005
2. Alizadeh et al. Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling. Nature, 2000
Apart from these, UCI repository has Glass and Reuters that I know have been used for hierarchical clustering. Perhaps, there are also more recent document / gene expression datasets in recent data mining papers.