Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors study the important problem of clustering graph in a hierarchical way optimizing and present novel algorithms for the special case of graphs with expender structure or well clusterable graphs, The algorithms have state of the art approximation for such cases and in practice are implementable. The experimental evidence that the algorithms are in line with other baselins in synthetic graphs, and on real data have better performance than some theoretical algorithm (but worse than simple baselines like average linkage).
main_review: 
The authors study the important problem of clustering graph in a hierarchical way optimizing an objective function introduced by Dasgupta [13] .
The authors study the problem under the assumption that the graph is well clusterable, in particular that it has high conductance (O(1)) this means that the graph is an expander and has no sparse cut separating two parts of the graph. Under this assumption they show a very fast near linear algorithm constant factor algorithm (while state of the art algorithm have logarithmic approximation and use complex poly time subroutines). Then they generalize this to well clustered graphs going beyond the stochastic block model to arbitrary graphs with this property.

Moreover the paper is complemented with an empirical analysis. 

The first structural observation is that if the graph has constant conductance and constant ratio of min max degree any tree is a constant approx solution. Then they introduce an algorithm which simply sorts nodes by degree and builds a tree balancing the nodes in order. Surprisingly this algorithm is a O(1/poly(conductance)) approximate despite being oblivious to the structure of the graph. 
This suggests to me that getting a constant approximate hierarchical clustering of such graphs (despite the theoretical interest( is not an practically interesting result and as such the algorithm is not practically useful (expect as a building block).
Then they adapt their algorithm to well clustered graphs using results from Trevisan et al. on finding sparse cuts. The algorithm is non trivial,

Then they provide an empirical evaluation of their algorithm against standard heuristic baselines for HC and some algorithms with theoretical guarantees for special cases of the HC problem.  First they compare on synthetic SBM data where the performance ties with state of the art. On other synthetic data with multiple densities they improve over some baselines but the performance is tied with average linkage. Finally on real data their performance is better than some state off the art method (for HC in some objective and setting) but worse than the baselines of Average and complete linkage. 


Minor:
very interesting theoretical fact, -> perhaps just interesting.
limitations_and_societal_impact: All in all the paper is technically interesting but the experimental evidence shows that it does not improve over simple baseline algorithms like average and complete linkage this may suggest that the perhaps the assumption of well-clusterability is not practically useful in this problem on real data.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Dasgupta's is a popular objective for hierarchical clustering. Given graph of similarities (weights w_uv), find the smallest subtree T_uv containing both u and v. The objective is \sum w_uv |T_uv|.

This can be optimized to within \sqrt \log n approximation, and constant factor is thought to be hard to achieve in general. There are recent work showing that this goal is possible for special graphs.

Cohen-Addad et al. present 1+o(1) approximation for a hierarchical generalization of SBM. This work takes a different perspective and looks at well-clusterable graphs in terms of conductance: There exists a partition V_i of the vertices into k parts such that (1) the subgraph induced on each V_i has large ("inner") conductance, and (2) each V_i has low ("outer") conductance. They show that one can get approximations depending on K and the conductance bounds. In particular, this gives const factors for expanders in the case of small k.

First they have a simple lemma with an upper bound for cost of any hierarchy in terms of conductance and degree distribution (ratio of d_max over d_avg and ratio of d_avg over d_min). This already gives const factor for const-degree expanders. Planting a large clique makes the bound polynomial, though there is a simple solution with small cost. They present a very simple algorithm (basically by sorting according to degree and recursively splitting the tree almost equally) which gives const factor for expanders.

Next they move to well-clusterable graphs, and show that Gharan-Trevisan decomposition is not sufficient, as simply joining the clusters in a tree may not work to get a good value for the objective (due to high cut values). Instead, they augment the decomposition theorem to identify a set of "critical nodes" with potentially high cut values. Then they break some of the clusters (more precisely, the greedily built trees for clusters) at those points, and finally merge everything into one tree by means of their degree-sorting algorithm.
main_review: Clustering well-clusterable graphs is a top topic, and this work certainly adds to the literature. The algorithms and theoretical bounds are not very practical, though. The gains in practice are small.

The paper is easy to read despite the heavy math.
limitations_and_societal_impact: Not really
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the cost function introduced by Dasgupta [13] and present polynomial-time approximation algorithms for well-clustered graphs. The well-clusterable assumptions mostly include an underlying structure of a fixed number of clusters, such that the subgraph induced by each cluster has high conductance, yet the cut between the clusters are sparse. The algorithm design bypasses the popular sparsest-cut subroutine, which was first proposed in Dasgupta [13] and often used by the community when studying this particular objective. The result is also more general than the state-of-the-art constant approximation results for this objective. The proposed algorithm also turns out to have reasonable performance empirically.
main_review: Overall I think this is a solid theory paper. Roughly speaking, the technical part of the paper is structured as follows:
- It starts with a discussion on graphs with high conductance. Such a graph can be though of as one single cluster for which there might not be a reasonable cut. With a motivating example (Figure 1), the authors proposed to group vertices of similar degrees first to reduce the hierarchical clustering cost.
- On such a graph, the authors designs Algorithm 1 which constructs the hierarchical clustering tree based on degrees, and proves it is a constant approximation by moving vertices around in the HC tree and slightly modifying the HC tree step by step. Such movements of vertices are centered around a "dense branch" which is a path in the HC tree, where the internal nodes represent clusters whose sizes are bigger than their siblings.
- The paper then considers a well-clustered graph which is composed of a given number of such high-conductance subgraphs (clusters), where the inter-cluster edges are more sparse than intra-cluster edges.

Originality: The paper contains novel ideas for performing theoretical analysis on HC algorithms and in particular for Dasgupta's objective. Some of the techniques used in the paper, including focusing on the "dense branch" and reconstructing trees by slighly modifying some of the branches, were also adopted by previous work, but this paper carefully managed to put them to good use, and, has found a nice breakthrough for HC-related theory, in my opinion. Analysis for Dasgupta's objective function often comes hand in hand with finding sparsest-cut, and the methods proposed in this paper at least offered a different perspective.

The submission seems to be technically sound. The writing quality is good. The underlying algorithms are quite complicated but the authors were able to at least convey the main ideas. In particular, they have motived the assumptions and the algorithm design very well.

Significance: The paper's main contributions are theoretical. Assuming it is correct, it adds to the community's understanding of HC objective functions and may contain some new tools that can be used for studying Dasgupta's objective. Emprically, the algorithm is on par with other algorithms developed in previous work. It does not outperform the most widey used HC algorithms yet, but the results may still enlighten us.

Minor Comments:
- In Algorithm 1, by definition, for some |V| values r could be very close to |V|? For example if |V| = 2^m + 1, does it mean r = |V| - 1? It seems a bit unusual then, since the algorithm splits off one point. I wasn't able to check the details due to time limits, but maybe the authors can share some intuition about why this is fine?
- The intuition behind the algorithm is to group vertices of similar degrees first, which is also a bit non-intuitive, as I cannot really tell why it might give good HC trees at the high level. It might work in this context, but I wonder whether it is easily extendable.
limitations_and_societal_impact: The authors have adequately addressed the limitations. The potential negative societal impact of their work was marked as N/A.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the problem of finding a good hierarchical clustering with respect to Dasgupta's objective function.

In particular, it gives algorithms that achieve constant-factor approximation for:
a) graphs that have good expansion properties
b) well-clusterable graphs, that is graphs that can be naturally clustered into sets of good expansion

These results are in contrast to known hardness results which rule out constant factor approximation under rather natural assumptions. Also, the algorithm generalizes an earlier result, which assumed much stronger properties of the input graph.
The paper also evaluates the new algorithm empirically, comparing it to a few existing baselines.
main_review: ## Strengths

* The paper  broadens our understanding of the Dasgupta objective, and for this reason I consider it an important contribution to the area of hierarchical clustering. For example, the algorithm presented in the paper for the 'expander' case only uses the node degrees. 
* I find the theoretical contribution highly nontrivial. On one hand, the fact that good expansion implies that the problem is tractable is not surprising (at least to me). However, turning this into an algorithm that also works in the case of clusterable graphs takes some highly nontrivial technical work.
* The paper is well-written and generally clear.

## Weaknesses
* The empirical evaluation says the algorithm improves upon "state-of-the-art", but I think this may be misleading, as the algorithm from the paper is typically outperformed by average-linkage clustering. I think the paper should comment on this and try to analyze the phenomenon, instead of ignoring the issue entirely.
* The result is unsurprising, in the sense that it's expected that by assuming stronger conditions on the input, one can obtain a better approximation guarantees. Still, making this idea work looks like solid piece of work.

## Specific comments

* Line 27: Is some word missing between 'is' and 'with'?
* Line 68: O(1 + o(1)) can be simplified to O(1). Do you mean O(1) or 1+o(1)?
* line 153: I think that condition (2) is redundant, as it is implied by condition (3)
* Lemma 4.1: Is \ell a parameter or something that the algorithm computes?

## Questions for authors
* Please analyze the empirical results taking average linkage into account, and be open about what it shows and what it does not. The analyzed algorithm is theoretical in nature, and I highly doubt one can show this can be a competitive method in practice. One approach would be to focus on comparison to the previous theoretical algorithm, include hierarchical stochastic block model in the studied datasets, and comment that average/single linkage are only added for reference. Right now, the writing in the empirical section is highly misleading to me, i.e., suggests the proposed method *is* competitive in practice, which, in my understanding, is contradicted by the pictures.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: The authors present a new hierarchical algorithm to cluster graphs. The main result showed in the paper is that the new algorithm returns a constant approximation for a well-clustered graph. The paper is a clear extension of previous work in NeurIPS and it presents interesting theoretical results. One shortcoming of the current write-up is that the proposed algorithm does not have great experimental performances. Overall, the paper is interesting and proposes some novel ideas and it will be a nice contribution to NeurIPS.

Decision: Accept (Poster)