An Information-theoretic Perspective of Hierarchical Clustering
Authors: Yicheng Pan
Bingchen Fan
Feng Zheng
Yang Wu
Venue: NeurIPS 2022 Submitted (2022)
Keywords: hierarchical clustering
information theory
non-binary cluster tree

Abstract: A combinatorial cost function for hierarchical clustering was introduced by Dasgupta \cite{dasgupta2016cost}. It has received great attention and several new cost functions from similar combinatorial perspective have been proposed. In this paper, we investigate hierarchical clustering from the \emph{information-theoretic} perspective and formulate a new objective function. We also establish the relationship between these two perspectives. In algorithmic aspect, we present two algorithms for expander-like and well-clustered cardinality weighted graphs, respectively, and show that both of them achieve $O(1)$-approximation for our new objective function. For practical use, we consider non-binary hierarchical clustering problem. We get rid of the traditional top-down and bottom-up frameworks, and present a new one. Our new framework stratifies the sparsest level of a cluster tree recursively in guide with our objective function. Our algorithm called HCSE outputs a $k$-level cluster tree by an interpretable mechanism to choose $k$ automatically without any hyper-parameter. Our experimental results on synthetic datasets show that HCSE has its own superiority in finding the intrinsic number of hierarchies, and the results on real datasets show that HCSE also achieves competitive costs over the popular non-binary hierarchical clustering algorithms LOUVAIN and HLP.

Motivated by Dasgupta's 's cost function, Cohen-Addad et al. [S] proposed admissible cost functions. 34 In their definition, the size of each LCA in Dasgupta's 's objective is generalized to be a function of the sizes of its left and right children. For all similarity based graphs generated from minimal ultrametric, a cluster tree achieves the minimum cost if and only if it is a generating tree that is a An Information-theoreti Perspective of Hierarchical Clustering
Anonymous Author(s)
Affiliation Address email
Abstract
A combinatorial cost function for hierarchical clustering was introduced by Das- gupta [[τ]]. It has received great attention and several new cost functions from sim- ilar combinatorial perspective have been proposed. In this paper, we investigate hierarchical clustering from the informationn-hheortiic perspective and formulate a new objective function. We also establish the relationship between these two perspectives. In algorithmic aspect, we present two algorithms for expander-iike and well-clustered cardinality weighted graphs, respectively, and show that both of them achieve ((1-)xpprxximationn for our new objective function. For practi- cal use, we consider non-binary hierarchical clustering problem. We get rid of the traditional top-down and bottom-up frameworks, and present new one. Our new framework stratifies the sparsest level of cluster tree recursively in guide with our objective function. Our algorithm called HCSE outputs a k-level cluster tree by interpretable mechanism to choose k automatically without any hyper- parameter. Our experimental results on synthetic datasets show that HCSE has its own superiority in finding the intrinsic number of hierarchies, and the results on real datasets show that HCSE also achieves competitive costs over the popular non- binarinar hierarchical clustering algorithms LOUVAIN and HLP.
10
11
12
14
16
Introduction
18
Hierarchical clustering for graphs plays important role in the structural analysis of given data set. Understanding hierarchical structures on the levels of multiple granularities is fundamental in 20
21
various disciplines including artificial intelligence, physies, biology, sociology, [8], [[] [3] E]] Hierarchical clustering requires a cluster tree that represents a recursive partitioning of a graph into smaller clusters the nodes get deeper. A leaf represents graph node while non-leaf node represents a cluster containing its descendant leaves. The root is the largest one containing all leaves.
22
24
Clustering is usually formulated as optimization problem with some objective function. For hier- archical clustering, no cost function with a clear and reasonable combinatorial explanation was de- veloped until Dasgupta [То]] introduced cost function for cluster trees. In this definition, similarity or dissimilarity between data points is represented by weighted edges. Taking the similarity-baa based metrics as example, cluster is set of nodes with relatively denser intra-links compared with its inter-links, and in a good cluster tree, heavier edges tend to connect leaves whose lowest common ancestor (I.CA) is deep possible. This intuition leads Dasgupta's cost function that is bilinear combination of edge weights and the sizes of corresponding LCAs.
26
28
30
32
36
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37
89 hierarchy number is solety determined by the number of rounds when the algorithm terminates. So quite poor. Our experimental results on synthetic datasets show that HCSE 91 has a great advantage in finding the intrinsic number of hierarchies, and the results on real datasets "natural" ground truth tree in an axiomatic sense therein. A necessary condition of admissibility of an objective function is that it achieves the same value for every cluster tree for uniformly weighted clique that has no structure in common sense. However, any slight deviation of edge weights would generally separate the two end-points of light edge on a high level of its optimal (similarity-hased cluster tree. Thus, it seems that admissible objective functions, which take Dasgupta's cost function as a specific form, ought to be an unchallenged criterion in evaluating cluster trees since they are formulated by an axiomatic approach.
38
39
40
41
42
43
44
However, an admissible cost function seems imperfect in practice. The arbitrariness of optima of cluster trees for cliques indicates that the division of each internal node on an optimal cluster tree totally neglects the balance of its two children. Edge weight the unique factor that decides the structure of optimal trees. But a balanced tree is commonly considered as an ideal candidate in hierarchical clustering compared to an unbalanced one. Even clustering for cliques, a balanced partition should be preferable for each internal node. At least, an optimal cluster tree whose height logarithm of graph size n intuitively more reasonable than a caterpillar shaped cluster tree whose height is 1. Moreover, simple proof would imply that the optimal cluster tree for any connected graphs is binary. This property is not always useful in practice since a real system usually has its inherent number of hierarchies and natural partition for each internal cluster. For instance,
45
46
47
48
49
50
51
52
54 the natural levels of administrative division in a country is usually intrinsic, and it is not suitable to differentiate hierarchies for parallel cities in the same state. This structure cannot be obtained by simply minimizing admissible cost functions.
56
57
In this paper, we investigate the hierarchical clustering from the perspective of information theory. Our study based on Li and Pan's structural information theory [[44] whose core concept named structural entropy measures the complexity of hierarchical networks. We summarize our contribu- tions as follows.
58
59
60
61
(I) We formulate a new objective function from the information-theoreti perspective, which builds the bridge for combinatorial and information-theorrticc perspectíves for hierarchical cluster- ing. For this cost function. the balance of cluster trees will be involved naturally as factor just 64 like we design optimal codes, for which the balance of probability over objects is fundamental in constructing an efficient coding tree. We also define cluster trees with a specific height, which is coincident with our cognition of natural clustering.
62
63
65
66
(2) For our new objective function, we present two polynomial-time approximation algorithms respectively for two cases of the conductance F(G') of cardinality weighted graph G. Our first 69 result shows that any cluster tree of G has a approximation factor ( (Theorem D.)). So
67
70 a meerfemanmmerge" heuristic that solely depends on the degrees of vertices achieves this guaran-
71 tee, and it achieves O ((1)-aprroiimation when ((G) is a constant. The second result is a O(1)-
72 approximation algorithm for G that can be well clustered into a constant number of expanders (The-
73 orem B. The main idea of this algorithm is inspired by very recent Manghiuc and Sun's 's work [[>]]
74 and our approximation factors for our new objective also match their results in these two cases.
75 (3) For practical use, we develop a new interpretable framework for natural hierarchical clus- tering that outputs non-binary cluster tree. The idea of our framework is essentially different from the traditional recursive division or agglomeration ones. In our framework, the sparsest level of the cluster tree is stratified recursively. This coincide with the intuition that when we differentiate the hierarchies of a complex system, the clearest level should be stratified first, rather than in a rigid divisive or agglomerative fashion. Therefore, this framework has much better interpretability than
77
78
79
80
81 the traditional ones.
(4) We develop a new non-binary clustering algorithm (HCSE) under the new clustering frame- 83 work. To find the sparsest level in each iteration, we formulate two basic operations called stretch and compress, respectively. HCSE terminates when specific criterion that intuitively coincides 85 with the natural hierarchies is met, and no hyperparameter is needed. Our extensive experiments on both synthetic and real datasets demonstrate that HCSE outperforms the present popular heuristic algorithms LOUVAIN [[] and HLP [[]]] These two algorithms proceed simply by recursively in- 88 voking flat clustering algorithms based on modularity and label propagation, respectively, and the
84
87
90 their interpretability
92 show that HCSE achieves much better costs than HLP and competitive costs to LOUVAIN.
2

---

93
In this section, we introduce Li and Pan's structural information theory [|_]]] and the combinatorial cost functions of Dasgupta [[C] and Cohen-Addad al. [8]. Then we propose new cost func- tion that is developed from structural information theory and establish the relationship between the information-thootee Related work. The first combinatorial objective function was proposed by Dasgupta [r]] Along with this line of study, several alternative objectives have been presented. All of them are bilinear functions of edge weights and some function of the corresponding ICAAs. For Dasgupta's 's cost func- tion and for the worst case study, Dasgupta showed that a recursively bipartition applying Arora's seminal algorithm for sparsest cut problem [2]] yields Ollog 1. n) aapproximation, and it was im-
94
95
96
97
98
proved by [20]] and [S] X] to (log r1) and vlog n, respectively. It is NP-hard to optimize the cluster tree ||C]] and even a aappppoooinnn is impossible under the Small Set Expansion hypothesis
99
100
120 Dij Beyond the worst case, Cohen-Addar et al. [8] showed that SVD-based algorithm achieves a 0 + (a)))aaproxiiaaiion for the stochastic block model with high probability. Manghiue and ((1)-pppromatio algorithm for more generalized well-clustered graphs. The outline of their method is to utilize a flat clustering algorithm [022] to obtain the underlying clusters first, and then some relatively easy heuristics for clustering in and out of these clusters are enough for the guarantee. Our proof follows this route also.
101
102
Sun [0:5] presented
103
105
106
For other lines of this study, Moseley and Wang [I6@]] studied the dual of Dasgupta's 's cost function and showed that the average-linkage algorithm achieves (1/3) apprroxxxxiinnnnn. This factor has been improved by a series of works to 0.336 [[]], 0.4246 [+] and 0.585 [II], respectively. Cohen-
107
108
109
Addad et al. [8] considered maximization of Dasgupta's 's cost function for the dissimilarity-bass metrics. They proved that the average-link and random partitioning algorithms achieve (2/3)-
110
111
approximation, which has been improved to 0.667 [6]. 0.716 [TS]] and 0.74 [1Z]], respectively.
112
For non-binary cluster tree construction, the most popular algorithm for practical use is LOUVAIN [].. More recently, a hierarchical label propagation based algorithm HLP has been presented [[9]]. Both of these two algorithms construct a non-binary cluster tree with the same framework, that is, the hierarchies are formed from bottom to top one by one. In each round, they invoke different flat clustering algorithms, Modularity and Label Propagation, respectively.
113
114
115
116
117
2
A cost function from information- perspective
118
119
120
121
and combinatorial perspectives.
122
Notations. Let G = (V. E, w) be an undirected weighted graph with a set of vertices V, set of edges E and weight function w : E - RR+, where IR+ denotes the set of all positive real numbers. An unweighted multigraph can be viewed as a cardinality weighted one whose edge weight is the number of parallel edges. For each vertex u E V. denote by dy = Ee w(u, v) the weighted degree of u. For a subset of vertices S C V. define the volume of S to be the sum of degrees of vertices. We denote it by vol(S) = Eves du. We denote by G[S] the subgraph induced by S. A cluster tree T for graph G is a rooted tree with [V] leaves, each of which is labeled by a distinct vertex v E V. Each non-leaf node on T is labeled by a subset S of V that consists of all the leaves treating S as an ancestor. For each node a on T, denote by a the parent of a, and by [a] its size. For each pair of leaves and v, denote by u V the LCA of them on on T.
123
124
125
126
127
128
129
130
131
132
Structural entropy of graphs. Because of the tense space limit, we just give the definition of the
core concept structural entropy in structural information theory. The idea of this definition is briefly introduced in Appendix Al. Readers could also refer to |I]] for more information on this theory.
134
135
Given a weighted graph G = (V. E, w) and cluster tree T for G. the structural entropy of G on T defined as
196
H² - Σ
log vol(a) m vol(V) vol(a-))
Ja
aET
137
where a denotes the parent of tree node a, and Ja denotes the sum of weights of edges in G with exactly one end-point in the set of vertices corresponding to a. The structural entropy of G is defined as the minimum one among all cluster trees, denoted by H(G) miny (HT(()):
138
139
For notational convenience, for the root À of I' set À = A. So the term for À in the summation is 0. In this paper, the omitted base of logarithm is always 2.
3

---

140
Combinatorial explanation of structural entropy. The cost function of a cluster tree T for graph
G -V, EV.E) introduced by Dasgupta [TC]] is defined to be c" = w(u, v) u V v/. The
141
142
admissible cost function introduced by Cohen- et al. [8] generalizes the term |u V el in the
definition of (G) to be a general function g(|L], RR), where L and R. are the two children of
143
144
u Ve, respectively. Dasgupta defined g(2, 3) = x + y. For both definitions, the optimal hierarchical clustering of G is in correspondence with cluster tree of minimum cost in the combinatorial sense that heavy edges are cut as far down the tree as possible. The following proposition establishes the relationship between structural entropy and this kind of combinatorial form of cost functions.
145
146
147
Proposition 2.1. For a weighted graph G = (V, w), minimizing H (G) (over T) is equivalent minimizing the cost function
148
149
cost (G) =
Σ (u,n)EE
w(u, log vol(u V v).
150
We defer the proof of Proposition | Appendix B
We call cost(SE) the cost function in Propo- sition [. from now on. Proposition P indicates that when we view g as a function of the LCA rather than that of its size and define g(u, v) = log vol(u V v), the "admissible" function becomes equivalent to structural entropy in evaluating cluster trees, although it is not admissible any more.
152
154
So what is the difference between these two cost functions? As stated by Cohen-Addad al. [. an important axiomatic hypothesis for admissible function, thus also for Dasgupta's 's cost function, that the cost for every binary cluster tree of an unweighted clique is identical. So any binary tree for clustering on cliques is reasonable, which coincides with the common sense that structureless datasets can be organized hierarchically free. However, for structural entropy, the following theorem indicates that balanced organization is of importance even though for structureless dataset.
155
156
157
158
159
160
Proposition 2.2. For any positive integer n, let Kn, be the clique of n vertices with identical weight on every edge. Then a cluster tree T of Kn achieves minimum structural entropy if and only if T is a balanced binary tree, that is, the two children clusters of each sub-tree of have difference size at most 1.
161
162
163
164
The proof of Proposition
2 is a bit technical, and defer it Appendix [1 The intuition behind Proposition 2 is that balanced codes are the most efficient encoding scheme for unrelated data. So the codewords of the random walk that jumps freely among clusters on each level of cluster tree have the minimum average length if all the clusters on this level are in balance.
185
166
187
168 It is worth noting that the admissible function introduced by Cohen-Addad et al. [8] is defined from the viewpoint that a generating tree T of a similarity- -bsed graph G that is generated from a minimal ultrametric achieves the minimum cost. In this definition, the monotonicity of edge weights between clusters on each level from bottom to top on T, which is given by Cohen-Addat et al. [S] as a property of "natural" ground-truth hierarchical clustering, is the unique factor when evaluating T. However, Proposition A implies that for COst(SE), besides cluster weights, the balance of cluster trees is implicitly involved as another factor. Moreover, for cliques, the minimum cost should be achieved on every subtree, which makes an optimal cluster tree balanced everywhere. This optimal clustering for cliques also robust in the sense that slight perturbation the minimal ultrametric, which can be considered as slight variations to the weights of a batch of edges, will not change the optimal cluster tree structure wildly due to the holdback force of balance.
169
171
172
179
174
175
178
177
178
3
Approximation algorithms for SE-based cost function
179
180
In this section, we present approximation algorithms for expander-like and well-clustered graphs, respectively. These algorithms work for cardinality edge weights (e.g. the multiplicity of edges).
182
Why cardinality weights? In general, the term log vol(u v) in Eq. M and thus cost(SE) may be negative when the volume of V v varies, which may lead to pathosis in approximation analysis. The cardinality weight function we is at least one, which makes cSst(SF) non-negative. The depen- dence of CSF) on the scale of edge weights violates the scale-invariance principle. However, we emphasize that H (G) is scalc-invariant and Proposition 2 holds for any scale variation. In this paper, we present approximation algorithms for COst(SE) in well-defined settings.
183
184
185
186
Theorem 3.1. For any cardinality weighted graph G = (V, F, w) with conductance (GG), it holds that any cluster tree has a cost (($(G)-1) -1). OPT, where OPT is the minimum cost(SE) of G.
188
4

---

190
We defer the proof of Theorem B to Appendix D When (G)) is constant, Theorem B implies that any cluster tree achieves apprrxxxxonnnnonnn for expanders. Thus, the balance of a cluster tree has significant impact on its cost. Considering balance as an important factor, we present Huffman-merginn heuristic (Algorithm I... will serve as subroutine for the algorithm for well- clustered graphs.
191
193
194
Algorithm 1: HuffmanMerge
Input:
graph G EV w) A cluster tree T of G
Output:
Create singleton trees;
2
while there are at least two trees do
Select the two trees Ti and T2 with the least volumes;
Construct new tree To with Ti and 72 as two subtrees of the root;
5 Return the resulting binary tree To-
Next, consider well-clustered graphs that are composed by a collection of densely-connecte components with high inner conductance and weakly interconnections. Our settings for well- clustered graphs is the same as those in [TS]] We start from the following (Din, ) ddero-ddcooooittionn presented by Gharan and Trevisan [ Let A be the k-th smallest eigenvalue of the normalized Laplacian matrix of G and (S) be the conductance of a vertex set S in G.
196
198
200
Lemma 3.1. ([UZ), Theorem 1.5) Let G = (V, E, w) be graph such that A > 0, for some k 2 1. Then, there is a local search algorithm that finds a l-partition {P:)i- of V, for some k, such that for every 1 S i < I, Pa(P.) = O(ko ( and ((G[P.) = /k*)
201
202
I Lemma 3.1 implies that, when graph G exhibits a clear clustering structure, there is partition P.) of V such that for each P; both the outer and inner conductance can be bounded. This is one of the most crucial insights that we can use (P: directly to construct a cluster tree.
204
205
206
For a high-level description, our algorithm consists of two phases: Partition and Merge. In the Partition phase, it invokes the algorithm in Lemma B. partion V into sets {P.) In the Merge
207
phase it combines the trees in a "caterpillar style" according an increasing order of their volumes. This algorithm described as Algorithm D
209
Algorithm 2:
CaterpillarMerge
Input: A graph G = (V, E, w). an integer 2 such that A > 0
Output: A cluster tree T of G
Apply the partitioning algorithm in Lemma 6 on input (G, k) to obtain (P:M for some
[< k;
2 Sort Pl...., Pj be such that vola(P,) S (Pi1)) for all 1 < <ik
Let Ti HuffmanMerre(([[e]]
4 Initialize T 0-=77 Ti:
for 2, ...,, do
L
Let T be the tree with T and Tj as its two children;
7 Return
Note that Algorithm Ø degenerates to Algorithm @ when k 2. For the approximation guarantee, we have the following theorem.
211
212
Theorem 3.2. Let G (V,E, be a cardinality weighted graph such that Ax. > 0 for some
213
> L. Then Algoritium E constructs in polynomial time a cluster tree T of G that achieves [I-a33 log I <pproximatiin for cost" (G), where a O(k / B ((X2/kk) Con- sequently, when X = ((1/poly(k)) and dạ-1 ((1 such that a < 1 - p for some constant In addition, when k is constant,
k
214
215
P (0, Algorithm E achieves ((poly(*))
217
Algorithm 2 achieves ( app))xpppximntiionn.
The proof of Theorem S is given in Appendix
5

---

4
Practically used non-binary hierarchical clustering algorithm
219
220
In this section, we develop a non-binary hierarchical clustering algorithm based on Cost(SE) opti- mization. At present, all existing algorithms for hierarchical clustering can be categorized into two frameworks: top-down division and bottom-up agglomeration [8]. The top-down division approach usually yields a binary tree by recursively dividing cluster into two parts with a cut-related eri- terion. But a binary clustering tree is far from a practical one as we introduced in Section MI For practical use, bottom-up agglomeration that is also known as hierarchical agglomerative clustering
221
222
223
224
225
228
(HAC) is commonly preferable. It constructs a cluster tree from leaves to the root recursively, during each round of which the newly generated clusters shrink into single vertices.
227
228
Our algorithm jumps out of these two frameworks. We establish a new one that stratifies the sparsest level of cluster tree recursively rather than in a sequential order. In general, in guide with cost(SE), we construct a l: + 1-level cluster tree from the previous k-level one, during which we find the level whose stratification makes the average cost in a local reduced subgraph decrease most, and then differentiate it into two levels. The process of stratification consists of two basic operations: stretch and compression. Generally speaking, in stretch steps, given an internal node of a cluster tree, a local binary subtree is constructed, while in compression steps, the paths that are overlength from the root leaves on the binary tree compressed by shrinking tree edges that make the cost reduce most. The intuition behind the "stretch-and- -od--eersss-sss" scheme is as follows. First, we run a fast and simple, but probably rough clustering algorithm to obtain a binary cluster subtree. So intuitively. after stretch, we unfold all the potential hierarchies such that the sparsest level is possibly to be seen. Second, we compress every overlength path that is supposed to get through each level of this subtree, during which, the edge on the sparsest level whose compression makes too many graph edges amplify the sizes of their I.CAs to a large extent will be retained.
229
230
231
232
233
234
235
236
237
238
239
241
242
We remark that this framework can be collocated with any cost function and any binary cluster tree algorithm. For computational efficiency, especially for real networks of large scale more than 10*, we will adopt in our experiments an HAC construction of binary cluster trees in stretch steps.
243
244
Stretch and compress. Given a cluster tree T for graph G EV, let u be internal node on T and U1 U2,..... Ug be its children. We call this local parent-children structure rooted at u to be u-triangle of T, denoted by T.,. These two operations are defined on u-triangles. Note that each child 1; of u is a cluster in G. We reduce G by shrinking each en to be a single vertex of while maintaining each inter-link and ignoring each internal edge of v;. This reduction captures the connections of clusters at this level in the parent cluster u. The stretch operation constructs a binary tree for u-triangle. We adopt a common HAC construction in this u-triangle. That is, initially, view each dy as a cluster and recursively combine two clusters into a new one for which CSst(SE) drops most. The sequence of combinations yields binary subtree T5 rooted at u which has UI, 02 Ue as leaves. Then the compression operation is proposed to reduce the height of T2 to be 2. Let B(T')) be the set of edges on 7", each of which appears on a path of length more than 2 from the root of T" to some Icaf. Denote by A(e) for edge e be the amount of structural entropy enhanced by the shrink of e. We pick from É(T.) the edge e with least A(e). Note that the compression of a tree edge makes the grandchildren of some internal node to be children, which must amplify the cost.
246
248
248
250
251
252
253
254
255
256
257
258
259
The compression operation picks the least amplification. The processes of stretch and compress are illustrated in Figure and stated in Algorithms and E. respectively (see Appendix G).
280
281
Sparsest level. Let U, be the set of j-level nodes on cluster tree T. that is, Uy is the set of nodes each of which has distance j from I's root. Suppose that the height of T is k, then Un UI...., U is a partition for all internal nodes of T. For each internal node u, define
262
263
vol(e) H(w)= Σ Eer vol(ir log vol(u]- Note that H(u) is the partial sum contributed by in H (G).
265
After a arretch-and-compress round on u-triangle, denote by AH(u) the structural entropy by which the new cluster tree reduces. Since the reconstruction of u-triangle stratifies cluster u, AH(u)
286
287
always non-negative. Define the sparsity of u to be Spar(u) AH(U)
*M(")* which the relative varia-
268
tion of structural entropy in cluster u. From the information-theone theoreetc perspective, this means that the uncertainty of random walk can be measured locally in any internal cluster, which reflects the quality of clustering this local area. At last, we define the sparsest level of to be the j-th level such that the average sparsity of triangles rooted at nodes in U3 is maximum, that is arg max, (T)ar,(T)),
270

---

272
where Spar (T) EnEr, Spar(u)/\Ugl- Then stratification works for the sparsest level of T, This process is illustrated in Figure E (see Appendix G
For given positive integer to construct cluster tree of height cluster tree that involves all vertices of G as leaves. Then we do not stop stratifying at the sparsest level recursively until a k-llvel cluster tree is obtained. This process is described in Algorithm
start from the trivial 1-level
275
278
Algorithm 3: k-Hiirrrchical clustering based on structural entropy (k-HCSE)
Input: a graph G (V, E), E Z+ Output: k-level cluster tree T
Initialize T to be the 1-level cluster tree; height(T);
while h < & do
j' + arg maxx (7)}; // Find the sparsest level of I" (breaking ties arbitraily);
if Spar (T) break; // No cost will be saved by any further clustering;
then
for u E Uy do
To Streech Tw): Compress(T.):
10
h h+h+1:
for j E IJ' + 1, do Update Uj;
12
13 return 7
277
To determine the height of the cluster tree automatically, we derive the natural clustering from the variation of sparsity on each level. Intuitively, a natural hierarchical cluster tree 7 should have not only sparse boundary on clusters, but also low sparsity for triangles of T, which means that stratification within the reduced subgraphs corresponding to the triangles on the sparsest level makes
279
281
little sense. For this reason, we consider the inflection points of the sequence (7,()))t==1)))) where (H) is the structural entropy by which the i-th round of stratification reduces. Formally, denote A,H = br-((H) - ó, (H) for each t 2 2. We say that A,H is an inflection point if both H, > A H and H A141H hold. Our algorithm finds the least & such that A,H is an inflection point and fix the height of the cluster tree to be t (Note that after t - rounds of stratification, the number of levels is t). This process is described Algorithm !1
283
285
Algorithm 4: Hierarchical clustering based on structural entropy (HCSE)
Input:
a graph G (V, E) Output: cluster tree T
1 xx+22 2;
while A. < 17l or 4,H < A do
if 1 (T)rr then
break;
t+
return t-HCSE(T)
287
Time complexity. The running time of HCSE on graph G = (V, E)) for which [V] n and E m depends mainly on the iterations of stratification for the sparsest level. For each round of t-HCSE in Algorithm E. since the change of structure entropy can be calculated incrementally and locally when merge siblings, the time complexity for the Stretch process is O(mh logn), where is the height of the binary tree that Stretch yields. Since at most n times of shrinking operations on tree edges
288
290
291
will happen, the time complexity for the Compress process is (hm).. Let Amaa be the maximum height among the binary trees that appear during all iterations. The time complexity of HCSE (and also k: &-HCSE) is Okkmbmax logn khmaaz)). practice, à is usually very small (we can even
292
294
set k O(1) in k- C-HCSE). Moreover, the balance property of structural entropy tends produce
7

---

P
HCSE
HLP
LOU
Exerinent OT N50075500
P2
4.5
0.89
0.79
0.92
Bacsom
P1
1.5E(-3)
0.93
0.75
0.92
Po
6E(-6)
0.62
0.58
0.35
P2
5.5E(-2)
0.87
0.89
0.89
0.30
P1 1.5E(-3)
0.95
0.87
0.87
Po
4E(-6)
0.72
P2
6.5E(-2)
0.96
0.95
0.99
P1
4.5E(-3)
0.94
0.81
0.99
Po
2.5E(-6)
0.80
Table 1: NMI for three algorithms. Fach dataset has 2, 500 vertices, and the cluster numbers at three levels are 5, 25 and 250, re- spectively, for which the size each cluster is accordingly generated at random. = 0.9 for each graph. "- means the algorithm does not find this level.
Figure 1: (HH) variations for HCSE. It can be observed easily that the inflection points for all the three datasets appear on 4, which is also the ground-truth num- ber of hierarchies.
296 balanced binary tree after stretch, which makes Imax O(log n). Therefore, in this case, the time complexity is merely (m log n).
5 Experiments
289
We evaluate experimentally our practically used non-binary clustering algorithm both on synthetic networks generated from the Hicrarchical Stochastic Block Model (HSBM) and on real datasets, respectively. We compare HCSE with the popular practical algorithms LOUVAIN [[] and HLP To avoid wver-fitting to higher levels, which possibly results in under-fitting to lower levels, LOUVAIN admits a sequential input of vertices. Usually, to avert the worst-case trap, the vertices
300
301
302
[[]]
303
304
come randomly, and the resulting cluster tree depends on their order. HLP invokes the common LP algorithm recursively, and so cannot be guaranteed to avoid under-fitiing in each round. This can be seen in our experiments synthetic datasets, for which these two algorithms usually miss grruh levels. For real datasets, as far as we know, no public real datasets have clear ground truth for hierarchical clustering. We do the comparative experiments on real networks. Some of them have (overlapping, possibly hierarchical) ground truth, e-g. Amazon, while others do not have. We evaluate the resulting cluster trees for the Amazon network by Jaccard index, and show the results in Appendix E. For other networks without ground truth, we evaluate results by both CSE and Dasgupta's cost function cost(Das). All the source code can be downloaded from ht https://qithui ctwp samwu- 1ew.eeeareeaaaea
305
306
307
309
311
313
314 Synthetic datasets generated from HSBM. Our experiments on synthetic datasets utilize 4-level HSBM For simplicity, let p' (Po- P1. P2, Ps) be the probability vector for which p; the proba- bility of generating edges for vertex pairs whose LCA on the ground-truth cluster tree has depth i. Note that the O-depth node the root. We compare the Normalized Mutual Information (NMI) at each level of the ground-truth cluster tree to those of three algorithms. Note that the randomness in LOUVAIN, and breaking-tice -ies rule as well as convergence of HLP make different results, we choose the most effective strategy and pick the best results in five runs for both of them. Compared to their uncertainty, our algorithm HCSE yields stable results.
315
317
319
321
322
Table M demonstrates the results in three groups of probabilities, for which the hierarchical structures get clearer one by one. Each dataset has 2, 500 vertices, and the cluster numbers at three levels are 5, 25 and 250, respectively, for which the size of each cluster is accordingly generated at random.
323
324
325
P3 = 0.9 for each graph. Our algorithm HCSE always able to find the right number of levels,
while LOUVAIN always misses the top level, and HLP misses the top level in two groups. The
327
inflection points for choosing the intrinsic hierarchy number L = 4 of hierarchies are demonstrated
in Figure M
8

---

Networks
HCSE
HLP
LOUVAIN
CSphd
1.30E4/ 5.19E4/
1.54E4 / 5.58E4 /
1.28E4/7.610
ib-pages-goverrment
2,48E6 1.18E8 /4
2.53E6/ 1.76E8 /
2.43E6 1.33E8 /4
email-univ
1.16E5 / 2.20E6 3
1.46E5 / 6.1416 3
1.14E5 2.20E6 4
fb-messages
1.58E5 4.5006 4
1.76E5 8.12E6 /
1.52E5
4.96E6 4
G22
/ /
6.1 4.00E7
5.63E5 / 2.80E7
As20000102
2.64E5 10445/2.3660 2.36E7 /
3.62E5 / 7.63E7 /3
2.42E5 2.42E7 5
bibd-13-6
7.41E5 2.56E7 /
8.05E5 03985/4.417// /
7.50E5 2.75E7 /
delaunay-n10
4.65F4/3.39F5 /
4.87F4/3.55H5 /
4.24E4 / 4.25E5 5
02p-Gnutella05
0005//1.8888 3
1.01E6/ /
8.05E5 1.49E8 5
p2p- Gaptela0
5.59E5/5.5113 /4
6.36E5 1.28E8 /
4.88E5 6.03E7 /
Table 2: "cost(SE)/ / cost(Das) k" for three algorithms, where k is the hierarchy number that the algorithm finds.
329
Real datasets. We do our experiments on series of real networks without ground truth. We compare cost(SE) and cost(Das), respectively. Since the different level numbers given by the three algorithms influence the costs seriously, that is, lower costs are obtained just due to greater heights, we only list in Table Z the networks for which the three algorithms yield similar level numbers that differ by at most or 2. It can be observed that HLP does not achieve optima for any network, while HCSE performs best w.r.t. cost(Das) for all networks, but does not outperform LOUVAIN for most networks. This is mainly due to the fact that LOUVAIN always finds no less number emphasize that of hierarchies than HCSE, and the better cost benefits from its depth. Moreover,
331
333
335
337
there is no evidence to indicate that the lower cost(SE) or cost(Das) is, the better a non- mon-binary cluster tree is. Our experiments these real datasets are just demonstrations of the effectiveness for interpretable mechanism in hierarchical clustering.
339
Conclusions and future discussions
340
In this paper, investigate the hierarchical clustering problem from information-theorete per- spective and propose a new objective function that relates to the combinatorial cost functions raised by Dasgupta [IC]] For optimization of this function, we present two O(1) apprroxiiiiiiioo algorithms for expander-like and well-clustered cardinality weighted graphs, respectively. For practical use, we propose a new interpretable non-binary hierarchical clustering framework that stratifies the sparsest level of the cluster tree recursively, which can be collocated with any cost function. We also present an interpretable strategy find the intrinsic number of levels without any hyper-part parameter. The ex- pelieental results on k-level HSBM demonstrate that our algorithm HCSE has great advantage in finding & compared to the popular but strongly heuristic algorithms LOUVAIN and HLP. Our results on real datasets show that HCSE also achieves competitive costs compared to these two algorithms.
342
343
344
345
346
347
348
349
351
There are several directions that are worth further study. The first problem about the relationship between the concavity of of the cost function and the balance of the optimal cluster tree. It can be checked that for cliques, being concave not a sufficient condition for total balance. Whether it necessary condition? Moreover, is there any explicit necessary and sufficient condition for total bal- ance of the optimal cluster tree for cliques? The second problem is about approximation algorithms for both structural entropy and cost(SE) in the worst case. Due to the lin-linear and volume-related function g, many previous proof techniques for approximation algorithms seems unavailable. The third one is about more precise characterizations for "natural" hierarchical clustering whose depth is limited. Since any reasonable choice of g makes the cost function achieve optimum on some binary tree, a blind pursuit of minimization of cost functions seems not to be rational approach. More criteria this scenario need to be studied.
352
353
354
355
356
357
359
361
hutp://ietwonteppssioooooommmeet

---

References
362
363
[1] Noga Alon, Yossi Azar, and Danny Vainstein. Hierarchical clustering: A 0.585 revenue ap- proximation. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, July 2020, Virtual Event |Graz, Austria), volume 125 of Proceedings of Machine Learning Research, pages 153-162. PMLR, 2020.
384
385
386
387
[2] Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1-5:37 2009.
388
389
[3] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment,
370
371
2008
372
[4] Peter F Brown, Vincent Della Pietra, Peter V Desouza, Jennifer C Lai, and Robert L Mercer. Class-based n-gram models of natural language. Computational linguistics, 18(4))467-480, 1992.
373
374
375
[5] Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Philip N. Klein, editor, Proceedingy of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 19,19, pages 841-854. SIAM, 2017.
378
377
378
379
66]
Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh. Hierarchical clustering better than average-linkage. In Timothy M. Chan, editor. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California. USA, January 6-9, 2019. pages 2291-2304. SIAM, 2019.
380
381
382
383
[7]
Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ah- madian, Alessandro Epasto, and Mohammad Mahdian. Bisect and conquer: Hierarchical clus- tering via max-uncut bisection. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 Au- gust 2020, Online [Palermo, Sicily, Italy), volume 108 of Proceedings of Machine Learning Research, pages 3121-3132, PMLR, 2020.
384
385
386
387
388
389
[8] Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Tremi and Claire Mathieu. Hierar- chical clustering: Objective functions and algorithms. Journal of the ACM (JACM), 66(4):1 42. 2019.
390
382
[9] Aron Culotta, Pallika Kanani, Robert Hall, Michael Wick, and Andrew McCallum. Author disambiguation using error-driven machine learning with a ranking loss function. In Sixth International Workshop on Information Integration on the Web (I/Web-07), Vancouver, Canada, 2007.
383
394
396
[10]
Sanjoy Dasgupta. A cost function for similarity- hierarchical clustering. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 118-127. ACM, 2016
398
400
[11] Michael B Eisen, Paul T Spellman, Patrick Brown, and David Botstein. Cluster analysis and display of genome-wide expression patterns. Proceedings of the National Academy of Sciences, 95(25);14863-1486
402
1998.
[12] Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 2256-1266. SIAM, 2014.
404
406
[13] Alexander N Gorban, Balázs Kégl, Donald C Wunsch, Andrei Y Zinovyev, et al. Principal manifolds for data visualization and dimension reduction, volume 58. Springer, 2008
408
[14] Angsheng Li and Yicheng Pan. Structural information and dynamical complexity of networks. IEEE Trans. Inf. Theory, 6206)333 2016
10

---

410
[15] Bogdan- Adrian Manghiuc and He Sun. Hierarchical clustering: O(1) approxxiiatonnn for well- clustered graphs. In Mare' Aurelio Ranzato. Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, De- cember 14, 2021, virtual, pages
411
413
414
2021.
[16] Benjamin Moseley and Joshua R. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3094-3103, 2017.
416
418
420
[17] Stanislav Naumov, Grigory Yaroslavtsev, and Dmitrii Avdiukhin. Objective- based hierarchical clustering of deep embedding vectors. In Thirty-Fifth AAAI Conference on Artificial Intel- ligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelli- gence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 9055-9063. AAAI Press, 2021.
422
423
424
[18] Mirmahdi Rahgoshay and Mohammad R. Salavatipour. Hierarchical clustering: New bounds and objective. CoRR, abs/2111 1.01666663,,... 2021.
427
428
[19] Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Fast hierarchical graph clustering in linear-time, In Companion Proceedings of the Web Conference 2020, pages 10- 12, 2020.
429
430
[20] Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metries. J. Mach. Learn. Rex., 18:88:1-88:355 2017.
432
Checklist
433
434
1. For all authors...
435
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Abstract and Section M1
437
(b) Did you describe the limitations of your work? [Yes] See Section K and F
438
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
439
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
442
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section E
443
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices
444
3. If you ran experiments..
445
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] See Section
447
S
448
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
449
450
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
452
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We do not compare the speed of computing, and so due the space limit we have omitted resource introduction.
453
454
4. If you using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] All codes are written by the authors, and all datasets we use is public. We have provided the URLs that link
457
to the datascts use.
11

---

459
(b)
Did you mention the license of the assets? [N/A]
460
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
461
462
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [No] All datasets we used are public.
(e) Did you diseuss whether the data you using/curating contains personally identifi- able information or offensive content? [No] No such content is included.
465
468
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
468
489
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
472
A A brief introduction to structural information
473
The idea of structural information is to encode random walk with certain rule by using high- dimensional encoding system for graph G. It is well known that a random walk, for which a neigh- bor is randomly chosen with probability proportional edge weights, has stationary distribution on vertices that is proportional to vertex degree." So to position random walk under its stationary distribution, the amount of information needed typically the Shannon's 's entropy, denoted by
de vol(V)
(G)=
log vol(V)
DEV
474 By Shannon's 's noiseless coding theorem, (G) is the limit of average code length generated from the memoryless source for step of the random walk. However, dependence of locations may shorten the code length. For each level on cluster trees, the uncertainty of locations is measured by the entropy of the stationary distribution on the clusters of this level. Consider an encoding for every cluster, including the leaves. Each non-root node is labeled by its order among the children of
478
477
478
479
its parent a_ So the amount of self-information of a within this local parent-children substructure is - log( vol (a)/vol(az )). which is also roughly the length of Shannon code for a and its siblings. The codeword of a consists of the sequential labels of nodes along the unique path from the root (excluded) to itself (included). The key idea is as follows. For one step of the random walk from u to in G. to indicate v, we omit from v's codeword the longest common prefix of u and that exactly the codeword of u V u. This means that the random walk takes this step in the cluster V (and also V e's ancestors) and the uncertainty at this level may not be involved. Therefore, intuitively, quality similarity-
480
481
482
483
484
485
cluster tree would trap the random walk with high frequency in the deep clusters that are from the root, and long codeword of u v would be omitted. This shortens the average code length of the random walk. Note that we ignore the uniqueness of decoding since practical design of codewords is not our purpose. We utilize this scheme to evaluate and differentiate hierarchical structures.
487
489
491
Then we formulate the above scheme and measure the average code length as follows. Given weighted graph G = (V, E, w) and a cluster tree T for G, note that under the stationary distribution, the random walk takes one step out of cluster a on with probability ga)vvo((). Therefore, the aforementioned uncertainty measured by the average code length is
492
493
484
Jc log vol(a) aET vol(V) vol(a-))
HT - Σ
495
which is defined as the structural entropy of G on T. To minimize this uncertainty, the structural entropy H(G) of G is defined as the minimum one among all cluster trees. Note that the structural
496
entropy of G on the trivial 1-level cluster tree is consistent with the previously defined (((1)() doesn't 't have any non-trive convirivial cluster.
497
498
For connected graphs, this stationary distribution is unique, but not for disconnected ones. Here, we consider this canonical one for all graphs.
12

---

B Proof of Proposition 2.
500 Proof. For each internal node a on T, denote by a(a) the sets of edges in G with exactly one
501 end-point in the set of vertices corresponding to a. So Leco(a) w(e). Note that
Ja log vol(a) vol(V)
GG)
- aeT
vol(a-)
w(u, log vol(a)
= Σ
vol(V)
vol(a-)
aET (u,))
w(u,v)
log vol(a) vol(a-)
E
Σ
vol(V)
(u.e)EE
(=(,,))Ega
502 For single edge (u, E. all the terms log( (og(vo((a//vol(a for leaf satisfying (u, go
503 sum (over a) up to log(du/ (dd/vol(u V o)) along the unique path from u to u V v. It is symmetric for v.
504 Therefore, considering ordered pair (u, v) E.
w(u,v) log du vol(V)
H (G)
E
vol(u Vo)
(a,D)EE
Σ ucV
du log du +
Σ
w(u, v) log vol(u V u)
vol(V)
ordered (a,))EE
Σ WEV
du log du +2.
Σ
w(u, v) log vol(u V
vol(V)
(U,0)E
505
The second equality follows from the fact Σnev du = Eondered (M.))E w(u v) vol(V) and the last equality from the symmetry of (u, v). Since the first summation is independent of T, Proposition follows.
506
507
C
Proof of Proposition 2.2
508
509
We restate Proposition 2.2 as follows.
Theorem 2.2. For any positive inleger n. let Kn, be the clique of n. vertices with identical weight on every edge. Then cluster tree T of Kn, achieves minimum structural entropy if and only if is balanced binary tree, that is, the two children clusters of each sub-tree of T have difference in size at most 1.
511
513
Note that balanced binary tree (BBT for abbreviation) means the tree is balanced every internal node. Formally, for an internal node of cluster size k, its two sub-trees are of cluster sizes [ and [k/2], respectively.
515
517
For cliques, since the weights of each edge are identical, we assume it safely be By Theorem 2.1, minimizing the structural entropy is equivalent to minimizing the cost function (over 7)
cost" (G)
Σ (a
log vol(u V v)
Σ
log ((n 1) (u/vvel) vel
(u,))E
Σ
log(n 1) +
Σ log Ju V e|
(u,e)EE
(a.)EE
Since the first term in the last equation is independent of T, the optimization turns to minimizing 520 the last term, which we denote by T(T). Grouping all edges in E. by LCA of two end-points, the
cost (TT) can be written the sum of the cost 7 at every internal node N of Formally, for every
13

---

522 internal node N, let A, B S V be the leaves of the sub-trees rooted at the left and right child of N,
523 respectively. We have
I(T)
Ex(N)
N
((V)
Σ
1 log (|A] + [B)
FEA,
[A|
|B|
log | + (B)
624
Now we only have to show the following lemma.
525
Lemma C.1. For any positive integer n, cluster tree T of K₂, achieves minimum cost (T) if and only if T is a BBT.
526
527
Proof. Lemma K. is proved by induction on V The key technique of tree swapping we use here is inspired by Cohen-Addad et al [4]. The basis step holds since for [V] = 2 or 3, the cluster tree is balanced and unique. It certainly achieves the minimum cost exclusively.
528
529
530
Now, consider a clique G = (V, E) with n |V| 2 4. Let Ti be an arbitrary unbalanced cluster tree and be its root. We need to prove that the cost r(T1) does not achieve the minimum. Without loss of generality, we can safely assume the root node is unbalanced, since otherwise, we set T1 to be the sub-tree that is rooted an unbalanced node. Let T2 be tree with root À whose left and right sub-trees are BBTs such that they have the same sizes with the left and right sub-trees of Ti respectively. Let Vu, Vr, Vr and Vrr be the sets of nodes on the four sub-trees at the second level of T2 and nu. Mer. Pyt and f,r denote their sizes, respectively. Our proof is also available when some of them are empty. We always assume ng I nty and ni, 2 Ryy- Next, we construct T3 by swapping (transplanting) Vir and Vn with each other. Finally, let T4 be tree with root À whose left and right sub-trees are BBTs after balancing the left and right sub-trees of Ta. So T4 is BBT. Then we only have prove that ((Ti) > I(T4). Note that the strict ">" is necessary since we need to negate all unbalanced cluster trees.
531
532
533
535
536
537
539
541
542
Then we show that the transformation process that consists of the above three steps makes the cost decrease step by step. Formally,
543
544
(a) Ti to Tg. The sub-trees of Tj become BBTs in Tg. Since the number of edges whose end-points treat the root as LCA is the same, by induction we have [(T1) I(T2).
(b) Th T3. We will show that r(T2) I(T3) in Lemma M
(c) Ta to T4. The sub-trees of T3 become BBTs in T4. For the same reason as (a), we have T(Ta) 2 I(T4).
548
549
Putting them together, we get [(Ti) > T(Ta) and Lemma Mi follows.
551
Lemma C.2. After swapping Vir and VrL, we obtain T3 from Tz, for which ((T2) > I(Ts).
552
Proof. We only need to consider the changes in cost of three nodes: root and its left and right children, since the cost contributed by each of the remaining nodes does not change after swapping.
553
554
Ignoring the unchanged costs, define
cost(T2) n,n, log + TAUTH log n + TyylDbr log fl
nmm, log + n4
n2r
log
+ 2
log nr.
2
2
555
where = 1111 + Mirs ny
Tept + myy- Both of them are at least 1. Similarly, define
cost(Tz)
= (nu + (
+ npr) ) log n + nunty log (nu + v2,)) + nyy log (nur
+ n)rr))
n
n4
n,
12
nr
m
n2
n2
2 2
log n +
log
+
+
log
+
2
2
2
2
2
2
2
2
14

---

556
Denote
A
T(T2)
((T3)
= cost 22)
cost(Ty)
Th
711
71
7hr
1hr
log
log
2
n
2
72
n2
nr
+
74
n4
log
log
(2)
2
2
2
2
557
So we only have to show that A > 0. We consider the following three cases according to the odevity of ny and ny.
558
559
Case 1: ny and ny are even.
560
Case 2: ny and ny are odd.
561
Case 3: ny odd while n, even.
562
The case that ny is even while n, is odd is symmetric to Case
563
For Case 1, if both ny and are even, then notations of rounding in Eq. (2)) can be removed and A
564
can be simplified
2
ni log
12,
A
log
+
565
Let = ni/n.q n,/n, and so 1. Recall that Ti is unbalanced on the root X, so is T2.
Thus + q. Multiplying by A on both sides, we only have to prove that
588
1² logg 9² logg 2pq 0.
That is,
P
log + logg + 2>> 0.
q
587
Let g(x) 1-x log Then we only need to show that g(p) + g(4) + 2 when p + q. Since
(1-z) In
g((x)
In2 (1 x)
x² In
gx(x) = In x11 - x)3
It is casy to check that g"(x) > 0 when 0 < 1. So g(x) is strictly convex in the interval (0, 1).
Since p *
p p -
glv) g(1) > 2g
588
Thus A > holds.
For Case 2, if both ny and n, are odd, then A can be split into two parts A A1 + Ag, in which
ni
n
n4
ni74
A. =
log
+
log
+
4
4
2
A2 1
111
1
Tlp
log
log
4
Since we have shown that A O, if we can prove A₂ 2 O. then the lemma will hold for Case 2. 571 Due to the convexity logarithmic function, this holds clearly since
2 2
log ny + log nyy
For Case 3, if is odd while ny even,
n2
77
Nr log
(n:
1)nr log
n2 (n-1)
(n:
1)m,
n
log
+
+
log
4
Y2
4
72
4
2n
2n
15

---

573
Multiplying the above equation by 4n 2, without changing its sign, yields
(4 (nî 1)
T2
7
In
Mrr
(mu 1)n, In
12 nー
+ (nr + 1)n, In
(n+1)
2n
2n
Splitting the right hand side into two parts,
A n In
n11
+ n
In
Ter + 2n1m In2
72
n4 n
(n) + 1) In (1 n :)) -m( (ny -mn- 1)m, In (1 (1-1) m
B In
575
Since n is odd and the root À of T2 unbalanced, we only need consider the case that ny
576
(n i)/2, n, (n + 2)/2 (Note that ny and n, are symmetric. So if (n - 2)/2 is even, exchange
577
ny and nt)), where both n and i are odd satisfying n > 2 3. Next we show that in this case,
A > ln(1/5) + 4 (n4/5) + 2 4ln 2 and B In 2 3/4 (2/3) (1/5²). By calculation,
579
B > 0 for Case 3.
580
Claim C.I. A 2 (m/5)) 4a ln(4/5) + 2- 4 for odd integers n > >
581
Proof. Substituting n4 = (n- - 1)/2, ny = (n + i)/2
into the A yields
A = C(,. i) A
n
2 In
n
+
n +
In
n +
+ 2
n
n +
In 2.
2n
2
2n
2
2
582
Treat n as a continuous variable, we have
OC(n, i)
12
Ön 2 (n + i) In
1 + (n 1)In
n
583
Multiplying the above equation by 2/n and setting i/n yields
f(x) & (1 (1+ x) (1 x) In(1 x) x²
f((x) = In(1+x) - In(1 x) 2x,
2x
(x()) = 1-x²2
584 is easy to check that f(0) 0 and f'(0) 0. When
1, f"(x) > 0. Thus f'(x) > 0 and f(x) > 0. This means that 8C(n, (C) i) > 0 for all n > 0. So C(n, 2 C(i
for 2 ii 2 586 (When is fixed, the minimum value of n can taken to 2, which makes 74 (n 1)/2 and
n, = (n + i)/2 integral). The curves of C(n, i) for varying are plotted in Figure 0
15.0
12.5
Cin.i
10.0
7.5
2.5
0.0
10
15
20
25
Figure 2: Functions C(n,t)
16

---

588
When = =i+2. 2, we get = (n i)/2 = and n, = (n + f)/2 = n 1. Substituting them into
589
yields
+ (n - 1n) (1- + 2(n 1) In
A In D(n) dD
2 2 + 2(n - ln (1 (1-
1 -
dn
When 2, it is easy check that / 0. So the minimum value of d(n), which is also the
581
minimum value of C(i + 2, 2) is achieved at = + =5. So = C(n, i) 2 C(i + 2, 2
582
C(5, 3) ln(1/5) 4 (4/5)) 2 4ln2.
Claim C.2. B > In 3/4 (2/3) (1/5²).
Proof. Due to the facts that
+
11
2n2
3nd
1
1
1
In
11
2n
3n3
595
we have
B
In
11
(ni + 1)n, In
1
1
(n:
1)n, In
(1-
1
11
71
n
72
n2
2ny
2n,
In
n22
3nd
74
14 n1
2n,
2
11
3n2
Let n/nn then
2
B
- Ina a(1 - a) 2 a)
3n2
3 2
2 hn2
4 3n²
597 When n 2 5, B 1n -3/ - (2/3) (1/5²).
596
Combining Claims C and
Lemma follows.
This completes the proof of Proposition M
D Proof of Theorem 3.1
600
Proof. Note that costT for any cluster tree T' has a trivial upper bound. That is,
Σ log(vol(G)) < vol(G) log(vol(G))
cost" (G) cost"(G)= = Σ cost" (c) -
eEE
cEE
where cost (e) w. log vol(( Let T* be the optimal cluster tree that achieves the mini- mum cost, we present here a lower bound for cost (G). Referring to the dense branch technique 602
603 [0O. IS],, we start with the root node An and walk along 7 recursively as follows: at every internal
node A,, walk down to the node A;+1 of higher volume between its two children. This process stops
605
2vol(G), Denote A & Aş well B & V\ By construction, it holds that (A) vol(G) and vBl 2 val(C) Moreover, vola 2val(G)
when we reach node As such that vola(As) <
3
17

---

607 for every 0 0 < k. The basic idea behind the dense branch is that the cut(A, B) has significant contribution to cost"" (G).
cost (G)
Σ
log(volo V v))
we
e=fu,0}
Σ
We Voeloo(vol((uV
== fu,e) rER(A,B)
w( (), B) log 2vol(G)
3
vol
2vol(G)
(G)
log
3
3
Let T be an arbitrary cluster tree, and T be optimal tree. We have
cost" (G)
3
log( (o((vol(G) O(
cost (G)
(G(
log 2vol(G)
609
E Proof of Theorem 3
611
Proof. To prove Theorem 2 we only have to prove the following lemma. Then the theorem follows from a simplification of the approximation factor.
612
Lemma E.1. Let max, (DG(())) and 8 min,( (((10g
Algorithm M achieves
1-a ( +1)
2a I-a (1 + log 1-a) )) 2 (g)) approximaation
Proof. We group the edges of G into two categories: let Ei be the set of edges in the induced subgraphs G:P: for si i.e.
E ULLEEII
and Eg be the remaining crossing edges. Then we have
cost (ost = Σ cost
(ost + Σ cost (e))
eEE,
eEEa
We denote by PP.) the volume of the induced graph G[P.). by volg (P:) the volume of P, in G. and by parent" T (P.) the parent of P. on T. Then it holds for every P: that
vola (parent (P.)) < k volg(P,).
By the construction of 7' we have that
vola(parent
T (P.))
Σ
i--vol(PP) k
1=1
Note that
w P., V V(P.) (P.) vol(G <a vola(P,,,
(1 (1-a) a) (P.) vol(G))))
and thus
vole (P.)) < k volo < b
(o..))
1
18

---

615 Combining the above, we have that
Σ
cost
(e)
Σ
log(volo(PP))
e
cE
Σ
We log
1
vol(G(P.)
cE
Σ
We log
1
+ we (og(vol(G(P.)))
1
e
k vol(G[P:)) (vol (((P)))
$
log
+
1- a a
2
1=1
616 and
Σ cost"(e)
S
Σ
(P,, V\P.)
log(vola (P.))
eE
f=1
k
<
vol() log [I-a
1-a a
f=1
a
k
<
1 log
1
1
j=1
2a
k
vol(G[P.))
log(vol (og(vol
= 1-a
1 +
log
1-
2
J=1
Let T be the optimal cluster tree of G, and OPT be the optimal value. We have
OPT: costa
costr-(e) 2 Σ OPT
EEB(GIP.)
Denote by
h(a,k)= ((1g (l1g log I-a a +1
2a
1 log k- ))
1
617
We have
cost (
Σ cost
costT(e)+ + Σ cost (e)
ces
R
F2
vol()) log(vol
< l1(a, k)
k
([[P)) ((I(.)
S li(a, k)
Σ
Go..)) log(3 vol(()))) OPTGPP
24
j=1
3 (oo
< h(a, k). max 24 log( 2 (T..))
OPTGPA
1=1
3 loo
S h( k) max 20 log( vol())
OPTc
I h(a,k) k) 23 log(
OPTe
618 Lemma B. follows.
619 Note that h( k) = =0 (17-1) log 1-a Theorem 3.2 follows.
(T-
19

---

Experimental results on Amazon network
620
We do our experiments on Amazon network for which the of ground-truth clusters has been given. For two sets A, B, the Jaccard Index of them is defined as J(A, B) = |An BJ U BJ. We pick the largest cluster which subgraph with 58283 vertices and 133178 edges. We run HCSE algorithm on it. For each ground-truth cluster that appears in this subgraph, we find from the resulting cluster tree an internal node that has maximum Jaccard index with c. Then we calculate
622
623
624
625
628
the average Jaccard index J over all such c. We also calculate cost(SE) and cost(Das). The results demonstrated in Table BI HCSE performs better for J and cost(SE), while LOUVAIN performs better for cost Das).. Because of unbalance in over-fitting and under- under-fitting traps, HLP outperforms
628
629
none of the other algorithms for all criteria.
index
HCSE
HLP LOUVAIN
J
0.20
0.16
0.17
cost(SE)
1.85E6
2.05E6
1.89E6
cost(Das)
5.57E8
3.99E8
3.08E8
Table 3: Comparisons of the average Jaccard index (J), cost function based on structural entropy (cost(SE)) and Dasgupta's cost function (cost(Das)).
G Some figures and pseudocodes
630
Stretch
Compeess
Figure 3: Illustaaioons of stretch and compress for u-triangle. A binary cluster tree is constructed first by stretch, and then edge e compressed, which yields a non-binary tree.
Figure 4: Illustration of stratification for 2-1evel cluster tree. The preference of (a) and (b) depends on the average sparsity of triangles at each level.
http://snapp.sanffrd..dde
20

---

Algorithm 5: Stretch
Input: a u-triangle Tu
Output: a binary tree rooted
Let {1i, "2,..., J be the set of leaves of Tw:
2 Compute 17 b) which is the reduced by merging siblings a, b into a single cluster;
for t E [ 1] do
(a, (3 f arg (a.(a. siblings {n(a, b)]:
Add
node 7/
7.parent + a.parent;
a.parent = 7,
8.parent = Y:
return Tu
Algorithm Compress
Input: a binary tree T
while T's height is more than do
+ arg fi(r) {A(e'))
Denote (u, v) where u is the parent of e; for w E v.children do L w.parent +- u;
Delete from T;
21


Reviews:
[{"review_id": "u2i4fXw0P8P", "reviewer": "Reviewer_xKCS", "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.", "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|$?\n2) What is an ultrametric (line 170)?\n3) Should line 10 in Algorithm 3 really be indented?\n4) (How) Is $\\Delta_t\\mathcal{H}$ in lines 282-286 connected with $\\Delta\\mathcal{H}(u)$?\n5) 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).", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWhat 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.\n\nSecond, 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.\n\nA 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rx-7SAgpHKS", "reviewer": "Reviewer_BgEL", "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.\n\nThe 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.\n\nFinally, 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.", "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?\n\n### Minor issues\nMinor issues which do not affect my evaluation:\n* 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\n* 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.\n* Line 49-50 - strange phrasing - maybe should be \"An optimal cluster tree whose height is $\\log(n)$ is intuitively...\"\n* Line 73 typo: 'rencent' -> 'recent'\n* Line 127: should this be \"$G[S]$ the subgraph *induced* by $S$\"?\n* 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.\n* Line 182 - should this be \"the term $\\log(\\mathrm{vol}(u \\lor v))$\"?\n* Line 186 typo: \"Theorem 2.1\" -> \"Proposition 2.1\".\n* Theorem 3.1 - $\\mathrm{OPT}$ has not been defined.\n* Line 208 typo: \"there\" -> \"their\"\n* Line 353 grammar: \"Whether it is a necessary condition?\" needs revision \n\n", "limitations": "The authors adequately address the limitations of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThis 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.\n\n### Weaknesses\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SeHXtlj5vD0", "reviewer": "Reviewer_uGUC", "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.", "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.\n", "limitations": "Potential negative societal impact is not described. it would be better to discuss it with respect to forcing balanced hierarchical clusters. \n", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n\nThe 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.\nAlthough 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].\nOf 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.\n\n## Quality\n\nThe 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.\n\nIn 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.\n\nIn 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? \n\n## Clarity\n\nThere are a number of unclear points:\n\n- 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.\n\n- 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?\n\n- 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.\n\n- In line 182, I think $\\log(u \\vee v)$ should be $\\log vol(u \\vee v)$.\n\n- In Theorem 3.1, the conductance $\\Phi_G$ is used without any definition. Please define it beforehand.\n\n- In Theorem 3.2, what is the definition of $O(\\cdot)$-approximation in terms of hierarchical clustering?\n\n- 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?\n\n## Significance\n\nFrom 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.\n\nFrom the empirical viewpoint, the significance is not high as the proposed algorithm is not directly examined.\nIn 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.\nTherefore, 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.\n\nIn addition to the above issue, in experiments, using real-world datasets with the ground-truth labels is strongly recommended for evaluation.\nI 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Q8zcGzH5QEP", "reviewer": "Reviewer_cybk", "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.", "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?\n\nIs there a reason why the binary clustering algorithms have not been experimentally evaluated?\n\nLemma 3.1: what is \\Phi_G(P_i)? It is not defined in the paper.\n\nTheorem 3.2: if \\alpha = O(k^6 \\sqrt{\\lambda_{k-1}}), it seems that the approximation factor can be negative\n\nLine 249: “while maintaining each intra-link and ignoring each internal edge of v_i” isn’t this a contradiction?\n\nSection 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? \n\nFig.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?\n\nSection 5, “real datasets”: what is the message of such results?\n", "limitations": "There is no discussion, but it seems not needed for such a paper.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- the proposed approach for non-binary clustering builds on a nice idea\n- 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\n\nWeaknesses:\n- the method works for graph data, but this is not clear in the title and abstract\n- 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.\n- 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)\n- The evaluation is performed only for the non-binary clustering algorithm, making the experimental evaluation less significant\n- 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\n- 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)\n- (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\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject