Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper proposes an information-theoretic cost function for hierarchical clustering of graphs. The cost function is inspired by structural information theory, which measures the complexity of a hierarchical network with structural entropy. The paper proves that minimizing the structural entropy cost function is equivalent to minimizing a cost function similar to admissible functions defined in previous works. The paper proposes two constant factor approximation algorithms for expander-like and for well-clustered graphs. It also describes a new framework for non-binary hierarchical clustering (i.e., internal nodes may have >2 children), which can be used with structural entropy cost or other cost functions. The non-binary hierarchical clustering approach is tested on simulated and real data, and compared with previously proposed methods LOUVAIN and HLP.
strengths_and_weaknesses: Strengths: 
- the proposed approach for non-binary clustering builds on a nice idea
- the proved relation between structural entropy cost and a cost analogous to admissible functions (Proposition 2.1) is a nice result bridging the information-theoretic and combinatorial approaches

Weaknesses:
- the method works for graph data, but this is not clear in the title and abstract
- the motivation in the Introduction is not very clear, since the shortcomings and weaknesses of admissible cost functions are not well described. The main motivation seems to be that when a clique is to be split in clusters, the authors suggest that it is better to split it in balanced clusters, while admissible cost functions would split the clique arbitrarily. However, the latter choice seems more natural to me, since from the point of view of clustering all partitions of a clique are equivalent.
- The paper presents very different contributions, with Section 4 (the algorithm for non-binary clustering) that does not seem to belong in the “information-theoretic perspective” on hierarchical clustering (it is a generic framework, not tied to the information-theoretic perspective of the previous sections)
- The evaluation is performed only for the non-binary clustering algorithm, making the experimental evaluation less significant
- The experimental evaluation is not entirely clear. In particular, the procedure to choose the number of levels does not seem to match with the plots
- In section 2 v is used to represent both a node of T and the set of nodes of G that v represents, which is sometimes confusing (see below for additional requests of clarification)
- (minor) Some figures appear only the supplement but they are references in the main text without marking them as Supplemental Figures or as appearing in Supplemental Material

questions: What is a real-world example where it would make sense to cluster a clique into two balanced clusters instead than in arbitrary clusters?

Is there a reason why the binary clustering algorithms have not been experimentally evaluated?

Lemma 3.1: what is \Phi_G(P_i)? It is not defined in the paper.

Theorem 3.2: if \alpha = O(k^6 \sqrt{\lambda_{k-1}}), it seems that the approximation factor can be negative

Line 249: “while maintaining each intra-link and ignoring each internal edge of v_i” isn’t this a contradiction?

Section 5: using cost(Das) and cost(SE) seems to be biased to favor your algorithm, since it does use cost(SE) and cost(Das) is somehow related to cost(SE) by Proposition 2.1. Is this not correct? 

Fig.1: according to the definition of inflection point in section 4, t=4 is not an inflection point for the blue plot (\delta_4 is negative, while \delta_5 is essentially 0). What is the inflection point?

Section 5, “real datasets”: what is the message of such results?

limitations: There is no discussion, but it seems not needed for such a paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the hierarchical clustering problem on graphs. This paper introduces a simple new objective function for measuring the quality of a hierarchical clustering tree which is in some way more 'natural' than the one proposed by Dasgupta. In particular, the new objective function encourages the tree to be balanced.

The paper also provides an algorithm, closely related to the one by Manghiuc and Sun [15], and proves that it achieves an O(1)-approximation of the optimal objective for well-clustered graphs.

Finally, the paper describes a heuristic algorithm for hierarchical clustering which is neither bottom-up nor top-down and demonstrates that this new clustering perspective can produce good results in practice.
strengths_and_weaknesses: ### Strengths
This paper makes a valuable contribution to an important problem. The newly introduced objective function is natural, and well motivated. It is useful to have an alternative objective function to the one proposed by Dasgupta, and this paper provides some nice discussion on the relative merits of the two objectives. The paper is generally well written and easy to follow.

### Weaknesses
The primary weakness of the paper is that the proposed practical algorithm, and the one used in the experimental evaluation, does not have any theoretical guarantee on its performance.
questions: I would be interested in a little more discussion on the implications of Theorem 3.1. Given that *any* tree gives an $O(1/\Phi)$ approximation, does this mean that an $O(1/\Phi)$-approximation (e.g. the guarantee on Line 71) is somehow 'nothing special' and doesn't really tell us anything about the resulting tree?

### Minor issues
Minor issues which do not affect my evaluation:
* Line 31 - when LCA is introduced it seems to mean the *node* which is the LCA of $u$ and $v$, however throughout the paper it is used to mean the *subtree* rooted at the lowest common ancestor
* Lines 36-37 - I didn't understand this phrase: "a 'natural' ground truth tree in an axiomatic sense therein". Similarly, the sentence on Lines 41-43 is not clear.
* Line 49-50 - strange phrasing - maybe should be "An optimal cluster tree whose height is $\log(n)$ is intuitively..."
* Line 73 typo: 'rencent' -> 'recent'
* Line 127: should this be "$G[S]$ the subgraph *induced* by $S$"?
* Line 143: if $u$ and $v$ are vertices, then the notation $|u|$ in $g(|u|, |v|)$ has not been defined. Similarly the phrase "of their numbers" on line 152 is not precise.
* Line 182 - should this be "the term $\log(\mathrm{vol}(u \lor v))$"?
* Line 186 typo: "Theorem 2.1" -> "Proposition 2.1".
* Theorem 3.1 - $\mathrm{OPT}$ has not been defined.
* Line 208 typo: "there" -> "their"
* Line 353 grammar: "Whether it is a necessary condition?" needs revision 


limitations: The authors adequately address the limitations of the paper.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The manuscript proposes an information-theoretic cost function for hierarchical clustering that is based on structural entropy. Based on the theoretical analysis of the cost function, the authors propose algorithms for special classes of graphs (Algorithm 1 for expander-like graphs and Algorithm 2 for well-clustered graphs) as well as for general graphs (Algorithms 3 and 4). In their experiments they show that their method outperforms modularity- and label propagation-based clustering in terms of finding the correct number of hierarchies.
strengths_and_weaknesses: The paper treats an interesting topic and proposes, to the best of my knowledge, a novel cost function. The algorithmic approach (stretch and compress) seems very promising. The paper is theoretically deep and accompanies cost function and algorithm with performance bounds and runtime analyses.

What prevents me from assigning a better score is the fact that the experiments are not convincing. While the results in Table 1 are promising, I am confused by the results in Table 2. There it is shown that LOUVAIN performs better in terms of the cost function on which HCSE is based, occasionally also for the same number of hierarchies. This could indicate that not the cost function yields improved performance, but rather its algorithmic implementation. A simple check would be to accompany Table 1 with cost(SE) values, but I also suggest more in-depth ablation analyses (e.g., replace the optimization of cost(SE) by a different algorithm, potentially a global optimization heuristic). Further, experiments on hierarchical graphs with ground truth would be welcome.

Second, the authors claim that their approach is interpretable, or even more interpretable than hierarchical Louvain or label propagation (lines 80-81, 89-90, and Section 6). I do not fully agree. On the one hand, the proposed cost function based on structural entropy is not easily accessible, at least not when compared to modularity. And second, the algorithmic implementation (stretch and compress) is, in my opinion, less interpretable than the procedure of propagating labels. In my opinion, the claim of interpretability seems not justified.

A final shortcoming of the manuscript is that it is not always clear. For example, the title and abstract are not clear about whether we consider hierarchical clustering for graphs or for general data (but see also questions below). Several paragraphs are hard to parse, e.g., lines 33-36, 51-58, 229-232, 239-241, and 268-270, and terms like "pathosis" (line 183) or phrases like "when $\phi(G)$ is as large as a constant" are not perfectly clear. This is not a critical, though, as I believe that these shortcomings can be repaired easily. While revising, I further suggest proof reading by an English native speaker.
questions: 1) In line 143, the usage of $g(|u|,|v|)$ is not clear. If $u$ and $v$ are vertices, as suggested by the sum in line 141, then what is the meaning of $|u|$?
2) What is an ultrametric (line 170)?
3) Should line 10 in Algorithm 3 really be indented?
4) (How) Is $\Delta_t\mathcal{H}$ in lines 282-286 connected with $\Delta\mathcal{H}(u)$?
5) Referring to Fig. 1, the text claims that the inflection points are at $t=4$ -- I do see two more inflection points at $t=2$ for two of the datasets. How should they be accounted for?
limitations: While the authors did not discuss the limitations of their work, they pointed out interested directions for future research. An important limitation in my opinion is clearly the lack of extensive experimental evidence (as pointed out above).
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes to use the structural entropy as a cost function in hierarchical clustering. Theoretical analysis shows that the proposed cost function implicitly prefers balanced clusters, which is different from the existing cost functions and a remarkable feature of the proposal. Moreover, an approximation algorithm with its theoretical guarantee is presented. Furthermore, a more realistic efficient algorithm is also proposed and it is empirically examined on synthetic and real-world datasets.
strengths_and_weaknesses: ## Originality

The structural entropy is originally defined on a graph with a partition, hence its application to hierarchical clustering, proposed in this paper, seems to be straightforward.
Although its theoretical analysis, including Proposition 2.2 and Theorem 3.2, is interesting, the overall originality of this paper is not so remarkable since it is a straightforward combination of [8], [10], and [14].
Of course, such a combination definitely has a potential of a significant contribution, while currently it is not well demonstrated as stated in the following sections.

## Quality

The motivation is not so clear. I understand that the proposal is suitable for finding balanced clusters, while its importance in the context of hierarchical clustering is not well discussed. That is, why do we need to find balanced clusters? What kind of application do we have for balanced hierarchical clustering? I would recommend carefully discussing the motivation of the proposal in this paper.

In addition, the effectiveness of balanced hierarchical clustering is not empirically examined in experiments. Please present a scenario with synthetic and/or real-world datasets in which balanced clusters are preferable and the proposal actually can find such clusters with better performance compared with existing methods.

In the problem setting, any undirected weighted graph is in the scope of this paper. However, in theoretical analysis, it is always assumed that a given graph is a cardinality weighted graph. Does this mean that the presented theoretical results only apply to a special case of graphs? How restrictive is this assumption? 

## Clarity

There are a number of unclear points:

- The definition of $g_\alpha$ is not clear. In line 137, it is explained as "$g_\alpha$ denotes the sum of weights of edges in $G$ with exactly one end-point in the set of vertices corresponding to $\alpha$". Does this mean $g_\alpha$ is equivalent to $d_\alpha$? Also, it is used as $(u, v) \in g_\alpha$ in the proof of Proposition 2.1. It is confusing as $g_\alpha$ should be a real number. Please revise it.

- In line 143, it is said that $g(x, y) = x + y$, which means that $g(|u|, |v|) = |u| + |v|$. Although it is said that $g(|u|, |v|)$ is a generalized term of $|u \vee v|$, I think in general $|u| + |v| = |u \vee v|$ does not hold. What is the reasoning of this?

- In the paragraph immediately preceding Prop.2.2, the authors discuss the difference between the proposed cost function and that in [8]. Does this discussion mean that the proposal does not satisfy the desirable condition "the cost for every binary cluster tree of an unweighted clique is identical"? If so, a more careful discussion of why the balanced clusters is more important than the above condition in practical situations would be desirable.

- In line 182, I think $\log(u \vee v)$ should be $\log vol(u \vee v)$.

- In Theorem 3.1, the conductance $\Phi_G$ is used without any definition. Please define it beforehand.

- In Theorem 3.2, what is the definition of $O(\cdot)$-approximation in terms of hierarchical clustering?

- In experiments, it is not clear to me how to generate ground-truth clusters. Why is the length of $\vec{p}$ fixed to 4? Does this mean that the level of hierarchy is always fixed to 4 regardless of the sample size?

## Significance

From the theoretical viewpoint, this paper theoretically analyzes the property of the proposed cost function in Prop. 2.1 and 2.2., and carefully design its approximation algorithm with its theoretical guarantee in Theorem 3.2. I think this is a good contribution and can be valuable in the task of hierarchical clustering.

From the empirical viewpoint, the significance is not high as the proposed algorithm is not directly examined.
In experiments, Algorithms 3 and 4 are used as the proposed method, while they are different from Algorithms 1 and 2, which are the key contribution of this paper and carefully theoretically analyzed.
Therefore, to empirically examine the proposal, Algorithms 1 and 2 should be used in experiments. If they cannot be used for some reason, at least the relationship between Algorithms 1&2 and 3&4 should be presented.

In addition to the above issue, in experiments, using real-world datasets with the ground-truth labels is strongly recommended for evaluation.
I understand that it is difficult to obtain ground-truth hierarchies, while it is possible to collect datasets with ground-truth flat partitions (that is, labels). Then, for example, one can use the dendrogram purity to quantify the goodness of obtained hierarchies. See: Kobren et al.,  A hierarchical algorithm for extreme clustering, SIGKDD2017.

questions: It would be great if you could address my concerns listed in the quality section (motivation, assumption) and the significance section (empirical evaluation), and clarify each of the points in the clarity section.

limitations: Potential negative societal impact is not described. it would be better to discuss it with respect to forcing balanced hierarchical clusters.
review_title: null

Meta-review: metareview: The paper introduces a new cost function inspired by structural information theory for hierarchical clustering of graphs. The paper show the relationship of the new cost function with previous work and proposes two algorithms to obtain a constant factor approximation for  expander-like and for well-clustered graphs.

The paper presents some new ideas and some interesting results although additional work is needed and the paper is not ready for publication in the current state. The main weaknesses highlighted by the committee are:
- the new cost function is not well-motivated and additional discussion will be needed
- the experiments are not too convincing
- the current presentation should be substantially improved before acceptance
confidence: Certain
Decision: Reject