Expected Probabilistic Hierarchies
Authors: Marcel Kollovieh
Bertrand Charpentier
Daniel Zügner
Stephan Günnemann
Venue: Submitted to ICLR 2023 (2023)
Keywords: Hierarchical Clustering
Graph Clustering
Clustering
Probabilistic Models

Abstract: Hierarchical clustering has usually been addressed by discrete optimization using heuristics or continuous optimization of relaxed scores for hierarchies. In this work, we propose to optimize expected scores under a probabilistic model over hierarchies. (1) We show theoretically that the global optimum of the expected Dasgupta cost and Tree-Sampling divergence (TSD), two unsupervised metrics for hierarchical clustering scores, are equal to the optimum of their discrete counterparts contrary to some relaxed scores. (2) We propose Expected Probabilistic Hierarchies (EPH), a probabilistic model to learn hierarchies in data by optimizing expected scores. EPH uses differentiable hierarchy sampling enabling end-to-end gradient-descent based optimizations, and an unbiased subgraph sampling approach to scale to large datasets. (3) We evaluate EPH on synthetic and real-world datasets including vector and graph datasets. EPH outperforms all other approaches on quantitative results and provides meaningful hierarchies in qualitative evaluations.

Under review as a conference paper at ICLR 2023
EXPECTED PROBABILISTIC HIERARCHIES
Anonymous authors
Paper under double-blind review
ABSTRACT
Hierarchical clustering has usually been addressed by discrete optimization us- ing heuristics or continuous optimization of relaxed scores for hierarchies. In this work, we propose to optimize expected scores under a probabilistic model over hierarchies. (1) We show theoretically that the global optimal values of the expected Dasgupta cost and Tree-Sampling divergence (TSD), two unsupervised metrics for hierarchical clustering, are equal to the optimal values of their díscrete counterparts contrary to some relaxed scores. (2) We propose Expected Proba- bilistic Hicrarchies (EPH), probabilistic model to learn hierarchies in data by optimizing expected scores. EPH uses differentiable hierarchy sampling enabling end-to-end gradient-descent based optimization, and unbiased subgraph sam- pling approach to scale to large datasets. (3) We evaluate EPH on synthetic and real-world datasets including vector and graph datasets. EPH outperforms all other approaches on quantitative results and provides meaningful hierarchies in qualitative evaluations.
INTRODUCTION
fundamental problem in unsupervised learning is clustering. Given a dataset, the task is to parti- tion the instances into similar groups. While flat clustering algorithms such k-means group data points into disjoint groups, a hierarchical clustering divides the data recursively into smaller clus- ters, which yields several advantages over flat one. Instead of only providing cluster assignments of the data points, it captures the clustering at multiple granularities, allowing the user to choose the desired level of fine and coarseness depending on the task. The hierarchical structure can be easily visualized in a dendrogram (e.g. see Fig. 4 making it easy to interpret and analyze. Hierarchical clustering finds applications in many areas, from personalized recommendation (Zhang al.) 2014) and document clustering (Steinbach et al. (2000) to gene- eene-exprossion (Eisen et al. 1998) and phylo- genetics (Felsenstein) 2004). Furthermore, the presence of hierarchical structures can be observed in many real-world graphs in nature and society (Ravasz & Barabási] 2003).
first family of methods for hierarchical clustering are discrete approaches. They aim optimizing some hierarchical clustering quality scores on a discrete search space, i.e.:
max score X, ?) s. E discrete hierarchies,
(1)
where X denotes a given (vector or graph) dataset. Examples of scores optimization could be the minimization of the discrete Dasgupta score Dasgupta (2016), the minimization of the error sum of squares (Ward Jr 1963), the maximization of the discrete TSD Charppenet & Bonald (2019), or the maximization of the modularity score (Blondel et al. 2008). Discrete approaches have two main limitations: the optimization search space of discrete hierarchies is large and constrained which often makes the problem intractable without using heuristics, and the learning procedure is not differentiable and thus not amenable to gradient-base approaches. To mitigate these issues, a second more recent family of continuous methods proposes to optimize some (soft-)scores on a continuous search space of relaxed hierarchies:
optimization, as done by most deep learning
max soft-score X, T) s.t.T E relaxed hierarchies,
Examples the relaxation of Dasgupta (Chami et al. 2020 Chierchia & Perret 2019 Zügner
ct al. 202T) or TSD scores (Zügner et al. 2021). A major drawback continuous methods is that the optimal value of soft scores might not align with their discrete counterparts.

---

Under review as a conference paper at ICLR 2023
Contributions. In this work, we propose to optimize expected discrete scores, called Exp- Das and Exp-TSD instead of the relaxed soft scores called Soft-Das and Soft-TSD Zügner et al. 2021 In particular, contributions can be summarized as follows:
Theoretical contribution: We analyze the theoretical properties of both the soft scores and the expected scores. We show that the optimal values of the expected scores are equal to their optimal discrete counterparts. Further, we show that the minimal value of Soft-Das can be different from that of the discrete Dasgupta cost.
Model contribution: We propose
method called Expected Probabilistic Hierarchies (EPH) to optimize the Exp-Das and Exp-TSD. EPH provides an umbiased estimate of Exp- Das and EXp-TSD with biased gradients based on differentiable hierarchy sampling, EPH scales to even large (vector) datasets based on unbiased subgraph sampling.
Experimental contribution: In quantitative experiments, we show that EPH outperforms other baselines 20/24 cases 16 datasets including both graph and vector datasets. In qualitative experiments, we show that EPH provides meaningful hierarchies.
RELATED WORK
Discrete Methods. We further differentiate between agglomerative (bottom-up) and divisive (top- down) discrete algorithms. Well-established agglomerative methods are the linkage algorithms that subsequently merge the two clusters with the lowest distance, into a new cluster. There are several ways to define the similarity of two clusters. The average linkage (AL.) method uses the average sim- ilarity, while single linkage (SL) and complete linkage (CL) use the minimum and maximum similar- ity between the groups, respectively (Hastie et al., 2009).. Finally, the ward linkage (WL) algorithm (Ward Jr. 1963) operates on Euclidean distances and merges the two clusters with the lowest increase the sum of squares. Another agglomerative approach the Louvain algorithm (Blondel et al. 2008) which maximizes iteratively the modularity score. Unlike agglomerative methods, divisive al- gorithms work a top-down fashion. Initially, leaves share the same cluster and are recursively divided into smaller ones using flat clustering algorithms. Famous examples are based on the k- means algorithm (Steinbach et al. 2000) or use approximations of the sparsest cut (Dasgupta) 2016).
Continuous Methods. In recent years, many continuous algorithms emerged to solve hierarchical clustering. These methods minimize continuous relaxations of the Dasgupta cost using gradient de- scent based optimizers. MMonthh al. (017) optimized probabilistic cost version. To parametrize the probabilities, they performed a softmax operation on learnable routing functions from each node on fixed binary hierarchy. [Cherchii & Perret (2019) proposed UFit, model operating in the ultra-metric space. Furthermore, to optimize their model, they presented soft-cardinal measure to compute differentiable relaxed version of the Dasgupta cost. Other approaches operate on continuous representations in hyperbolic space such as gHHC (Monath et al., 2019) and HypHC (Chami al. 2020). Zügner et al. (202T) recently presented a flexible probabilistic hierarchy model (FPH), on which our method is based. FPH directly parametrizes probabilistic hierarchy and substitutes the discrete terms in the Dasgupta cost and Tree-Sampling Divergence with their probabilistic counterparts. This results in differentiable objective function which they optimize using projected gradient descent.
Differentiable Sampling Methods. Stochastic models with discrete random variables are difficult to train as the backpropagation algorithm requires all operations to be differentiable. To address this problem, estimators such as the Gumbel-Softmas (Jang et al. 2016) Gumbel-Sinkhorn (Mena ct al., 2018) are used to retain gradients when sampling discrete variables. These diffcrentiable sampling methods have been used for several tasks including DAG predictions (Charpentier al.) 2022). spanning trees or subset selection (Paulus et al., (020) and generating graphs BBjccheskii al. (2018). Note that sampling spanning trees is not applicable in our case since we have restricted structure, where the nodes of the graph correspond to the leaves of the tree.
3 PROBABILISTIC HIERARCHICAL CLUSTERING
We consider a graph dataset. Let g = (V, E) be a graph with n vertices = {Vi...., vn and m edges F. (e Let way denote the weight of the edge connecting the nodes v, and v if
2

---

Under review as a conference paper at ICLR 2023
Probabilistcc liierarcy:: 7
Distrete Hieruchies 7 p.y F66
Dilinentiable
hieaaddy
sampling
Graphi
Subgraph
Loss
Subgraph
E/paare| (7) |m
2 80 (0)
Hackoward
Figure 1: Overview of our proposed EPH model. A formal description is given in App. B.8
(i,j) E E. 0 otherwise and wi Eg wa, the weight of the node vę- We define the edge distribution P(v.. V5) for pairs of nodes, P(v., v,) x Wa.j. s.t. E V.ev P(y;, v2) and equivalently the node distribution P(v,) Wi s.t. Evev P(v:) 1. We can extend this representation any vector dataset D = {xI..... } and interpret the dataset as a graph by using the data points x; as nodes and pairwise similarities (e.g. cosine similarities) as edge weights.
Discrete hierarchical clustering. We define a discrete hierarchical clustering 7 of graph g as a rooted tree with leaves and n' internal nodes. The leaves V = {v1. ....... vn.) represent the nodes of G. while the internal nodes Z {z1, Z2..... } represent clusters, with Z,' being the root node. Each internal node groups the data into disjoint sub-clusters, where edges reflect memberships of clusters. We can represent the hierarchy using two binary adjacency matrices Á E {0, j and B E {0. 1) xn", i.e. + = (Á, B). While Å describes the edges from the leaves to the internal nodes, B specifies the edges between the internal nodes. Since every node in the hierarchy except the root haş exactly one outgoing edge, we have the following constraints: E Åi, for 1 < S > B.,- 1 for < i < n' and Σ B,' 0 for the last row. Thus, except for the last row of B, both matrices are row-stochastic. "We denote the ancestors of as anc(v), and the lowest common ancestor (LCC) of the two leaves v, and v, in 7 as V, A Vy-
Probabilistic hierarchical clustering. Zügner et al.. (202T) recently proposed probabilistic hierarchies. The idea is to use continuous relaxation of the binary adjacency matrices while keeping the row-stochasticity constraints. Thus, end up with two matrices A [0, 1|mxn' and B E [0, 11 ' xn' The entries represent parent probabilities, i.c. Aij : p(zylv:) describes the probability of the internal node Zj being the parent of v, and Brj := p(z,l2;) the probability of the internal node z, being the parent of 2, Together, they define probabilistic hierarchy T (A, B). Given such a probabilistic hierarchy, one can easily obtain discrete hierarchy by interpreting the corresponding rows of A and B categorical distributions. We sample an outgoing edge for each leaf and internal node. Since B is restricted to be an upper triangular matrix, this tree-sampling procedure will result in a valid discrete hierarchy, denoted by 7 (A, B) PT.
EXPECTED PROBABILISTIC HIERARCHICAL CLUSTERING
4.1 EXPECTED METRICS
Unlike flat clusterings, there has been a shortage of objective functions for hierarchical cluster- ings. Thus, many algorithms to derive hierarchies were developed without a precise objective. An objective function not only allows us to evaluate the performance of a hierarchy, but also yields possibilities for optimization techniques. Recently the two unsupervised functions Dasgupta cost (Das) (Dasguptal 2016) and Tree- Sampling Divergence (TSD) (Charpentier & Bonald, 2019 were proposed, triggering the development of new generation of hierarchical clustering algorithms. The Dasgupta cost is a well-established metric for graphs and vector data, while the TSD is a recent met- ric specifically designed for graphs. In addition being unsupervised, i.e., applicable in cases where
3

---

Under review as a conference paper at ICLR 2023
the data is unlabeled, both metrics also have intuitive motivations. The metrics be written as: Das(
Σ P(ve, vy)c(veAv,)) and TSD( kL(b(2)llo(z))
ViAgEv
where c(z) the number of leaves whose ancestor is 7, i.e. c(z) = Ever [= and p(z) and q(z) are two distributions induced by the edge and node distributions, i.e. Importantly, both
p(z) = Ev.y. 1 Iizen,Avi Vj) and g(z) => 1 ((v,)) Dasgupta and TSD scores have intuitive motivations. Dasgupta favors similar leaves to have lowest common ancestors low in the hierarchy (Dasgupta 2016). TSD quantifies the ability to reconstruct the graph from the hierarchy in terms of information loss Charpentier & Bonald (2019). Recently, Zügner et al. (202T) proposed the Flexible Probabilistic Hierarchy (FPH) method. FPH substitutes the indicator functions with their corresponding probabilities under the tree-sampling procedure, obtaining cost functions for probabilistic hierarchies, called Soft-Das and Soft-TSD. These two metrics correspond to the scores of the expected hierarchies (see [..]..]). In contrast, propose in this work to optimize the expected metrics under the tree-sampling procedure. Intuitively, this corresponds to moving the expectation from inside the metric functions outside, reflecting the natural way of performing Monte-Carke approximation via (tree-) sampling. More specifically, our objectives are:
min B [ass(T)] s.t. 7 PA.B(T) and A.B
max E, [TSD(T)] s.t. J PA,B(T), (4) A,B
which we denote Exp-Das and EXp-TSD. Note that we optimize over A and B, which parametrize probabilistic hierarchy, while the edge weights are given by the dataset and used to compute the node and edge distribution. We show in Section 4.2 that the optimal values of the expected scores share the same intuitive meaning as their discrete counterparts. While the probabilities used in the FPH computation are consistent, their relaxed scores are not consistent with the expected scores under the tree- procedure. In Fig. 2 we show simple case where Doft-Das does not align with the global optimal value whereas Exp-Das does.
4.2 THEORETICAL ANALYSIS OF EPH AND FPH
The main motivation use the expected metries is the property that their global optimal value, ie. the score obtained by the globally optimal hierarchy (the optimizer), is equal to their discrete counterparts show in Theo. [
Theorem 1. Let A and B be probabilistic transition matrices. Then the following equalities hold,
min E T-PA. A.B
[Ts
min Das(T)
and
max E T~ A.B
(TSD(T)] max TSD(T)
f
(See proof in App. A.5
Consequently, optimizing cost function aims find the optimal discrete hierarchy. Furthermore, we prove in Theo. 2 that Soft-Das is a lower bound of Exp-Das, therefore its minimum is lower bound of the optimal discrete Dasgupta cost.
Theorem 2. Let and B be transition matrices describing a probabilistic hierarchy. Then, Soft-Das will be lower than or equal the expected Dasgupta cost under the tree-sampling pro- cedure, ie., (see proof in App. A.4
Soft-Das(T) S E.-PA.N(T
[Das(T)]
In Fig. 2 we show specific example where the minimizer of Soft-Das is continuous and FPH fails to find the optimal hierarchy. For EPH, we know that an integral solution exists since Exp-Das and Exp-TSD are convex combinations of their discrete counterparts. Furthermore, Exp-Das is neither convex nor concave, as we show in App. A.6 In Table D we provide an overview of properties of the cost functions of FPH and EPH.
4.3 UNBIASED COMPUTATION OF EXPECTED SCORES VIA DIFFERENTIABLE SAMPLING
In order to compute the expected scores we can use a closed-form expression. To derive these for Exp-Das and EXp-TSD, need to be able to calculate the probability p p v, A Vj, Z anc(v))
4

---

Under review as a conference paper at ICLR 2023
V2
Z3
Z3
Z3
72
71
72
71
V3
V2
V3 V4
V1
V2
V3
V1
V2
V3
Vi
(a) K4 Graph
(b) minimizing hierarchy
FPH
(d) EPH
Figure 2: Example where FPH fails to infer a minimizing hierarchy. A hierarchy minimizing the Dasgupta cost and the inferred hierarchies by FPH and EPH on the unweighted K₃ graph. i.c. every normalized edge weight is equal to &. While FPH achieves Dasgupta cost of 4.0 after discretization, the continuous hierarchy has a Soft-Das score below 3.0. On the other hand, EPH finds minimizing hierarchy with the cost of 10
3
Table I: Properties of Soft-Das, Exp-Das, Soft-TSD, and EXp-TSD.
Property
Problem Type
Convex/Concuve
Integral
Optimal
Consistent
Soft-Das
Min.
Neither w.r.t A and B (see Fig (left)
X
Exp-Das
Min.
Neither w.r.t A and B (see A.6
Soft-TSD
Max.
Convex w.t.t LCA probabilities (Zügner et 2021
Exp-TSD
Max.
for which no known solution exists, and the expectancy of logarithm (see Eq. 13 and Eq. An alternative to the closed-form solution is to approximate the expectancies via the Monte Carlo method. We propose approximate Exp-Das and Exp-TSD with N differentiably sampled hierar- chies (T(1), ((.,,.,(([T)) (see "Loss computation" in Fig. D
T(M)
N Σ (0) and Exp-TSD(TT 2 N
N N Σ TSD(T()).
Exp-Das(T) ~
(7)
However, differentiable sampling of discrete structures like hierarchies is often complex. To this
end, our differentiable hierarchy sampling algorithm combines the tree-sampling procedure (Zügner
al. 202T) and straight-throug! Gumbel-Softman estimator (Jang et al. 2016) three steps: (I)
We sample the parents of the leaf nodes by interpreting the column of A as parameters of straight- through Gumbel-Softman estimators. (2) We sample the parents of the leaf nodes by interpreting
the column of B parameters of straight-through Gumbel-Softmax estimators. This procedure differentiable each step is differentiable and expressive it can sample any hierarchy with n leaves and n' internal nodes. (3) We use the Monte Carlo method to approximate the expectancies by computing the arithmetic mean of the scores of the sampled hierarchies. We reuse the differentiable computation of Soft-Das and Soft-TSD which match the discrete scores for discrete hierarchies while providing gradients w.r.t. A and B (see Fig. for an overview).
Complexity. Since we sample hicrarchies from n' + n many categorical distributions with (nr') classes, the sampling process can be done with a complexity of O(N x x''nn +N x The dominating term the computation of the Das and TSD scores with a complexity of O(N x n22 for graph datasets and O 2 xnx r2 for vector datasets (Zügner et al. 2021). This is often efficient as we typically have n' & and for graphs m & n². Sec. 4.4 we propose subgraph sampling approach to reduce the complexity to M xn +n)) for large vector datasets, where M < n².
Limitations. While the previously explained MC estimators of the expectancies are unbiased in the forward pass, the estimation of the gradients is not (Paulus et al. 2021) thus impacting the EPH optimization. Furthermore, even though the global optimal values of the expected and discrete scores match, EPH does not guarantee convergence into global optimum when optimizing using gradient descent methods.
4.4 SCALABLE EXP-DAS COMPUTATION VIA SUBGRAPI SAMPLING
As discussed in the complexity analysis the limiting factor is On n corresponding to the evaluation of the Dasgupta cost, which becomes prohibitive for large datasets. To reduce the complexity propose unbiased subgraph sampling approach. First, we note that the normalized
5

---

Under review as a conference paper at ICLR 2023
similarities P(v., vz) can be interpreted as a probability mass function of categorical distribution. This interpretation allows the Dasgupta cost to be rewritten as an expectancy and approximated via sampling procedure. More specifically,
M
Das(T) Σ P(y., ((ye,,)e(yvAA))) = B(v.,)))((v))) [c(v, Avj) R
1 M
(K) Eelv k=1
(
(8)
VeNy
( are M edges sampled from the edge distribution P(vs. Vy), which can be done in (M + n²) Kronmal & Peterson 1979). We refer this sampling approach as subgraph sampling (see Fig. Using the same procedure, we can approximate the expected Dasgupta cost. In contrast to Exp-Das, Exp-TSD cannot be easily viewed as an expectation of edges, thus making the approximation via sub-graph sampling impractical. However, since TSD is a metric originally designed for graphs which are generally sparse, it would not yield substantial benefits.
where {(v(), v (1))
(M) (v(M)
Note that we end up with two different sampling procedures. First, we have the differentiable hi- erarchy sampling (see Eq. 77. This is necessary to approximate the expectancies. Since we do not have a closed-form expression of Exp-Das and Exp-TSD, we sample discrete hierarchies from the probabilistic ones and average the scores. Secondly, we have the subgraph sampling (see Eq. ( which interprets the Dasgupta cost tor datasets since the number of pairwise similarities grows quadratically in the number of data points. The estimation is unbiased and introduces additional parameter, i.e. the number of sam- pled edges, which allows a trade-off between runtime and quality. By inserting the probabilistic edge sampling approach into the tree-sampling, we estimate Exp-Das scale it to large vector datasets. An overview of our model is shown in Fig. and a formal description in App. B.8
expectancy. This is done to speed up the runtime for vec-
5 EXPERIMENTS
5.1 EXPERIMENTAL SETUP
Datasets. We evaluate our method on both graph and vector datasets. Graph datasets: We the same graphs and preprocessing as Zügner et al. (202T). More specifically, we use the datasets Pol- blogs (Adamic & Glance| 22005) Brain (Amunts al. 2013), Citeseer (Sen et al. 22008), Genes (Cho et al. 2014). Cora-ML (McCallum et al. 2000 Bojchevski & Günnemann 2018)). OpenFlight (Pa- tokallio), WikiPhysies (Aspert et al. 2019), and DBLP (Yang & Leskovee| 2015). To preprocess the graph, we first collect the largest connected component. Secondly, every edge is made bidirectional and unweighted. An overview of the graphs shown in Tab. T the appendíx. Vector datasets: We test our method on vector data for the Dasgupta cost. Here we selected the seven datasets Zoo, Iris, Glass, Digits, Segmentation, Spambase, and Letter from the UCI Machine Learning repository (Dua & Grafi 2017). Furthermore, we also use Cifar- 100 (Krizhevsky et al. 2009). Digits and Cifar- 100 are image datasets, the remaining ones are vector data, While we only flatten the images of Digits, preprocess Cifar- 100 using the ResNet- 101 B-T-M- by Kolesnikov et al. 2020 which was pretrained on ImageNet-2111 (Deng et al. 2009 More specifically, we use the 2048 dimen- sional activations of the final layer for each image in Cifar-100 as feature vector. Furthermore, we normalize all features to have mean of zero and a standard deviation of one. We compute cosine similarities between all pairs of data points using their normalized features. This results dense similarity matrix. Finally, we remove the self-loops. Note that in contrast to the graph datasets, the vector data similarities are weighted. An overview is shown in Tab. 7 in the appendix. Since we are in an unsupervised setting we have no train/test split, i.e. we train and evaluate on the whole graph.
Baselines. We compare our model against both discrete and continuous approuches. For discrete approaches, we use the single, average, complete (Hastic et al.) 2009) and ward linkage (Ward Jr. [963] algorithm, respectively referred to as SL. AL., CL and WL. We do not report results of SL and CL on the graph datasets which do not have edge weights since these methods are not applicable for unweighted graphs. In addition to the linkage algorithms, we also compare to the recursive sparsest cut (RSC) (Dasgupta) 2016) and the Louvain method (Louv.) (Blondel et al.) 2008). For continuous approaches, we use the gradient- optimization approaches Ultrametric Fitting (UF) (Chierchia & Perret 2019). Hyperbolical Hierarchical Clustering (HypHC) (Chami ct al. 2020), gradient- Hyperbolic Hierarchical Clustering (gHHC) (Monath et al.) (201)) and Flexible Probabilistic Hierarchy (FPH) (Zügner et al. 2021). While the linkage algorithms derive

---

Under review as a conference paper at ICLR 2023
Table 2: Results for the graph datasets.
Dasgupta cost
Tree-sampling divergence
Daraset
PolBI.
Brain
Cites.
Genes
Cora-MI.
OpenI:
WikiP.
DBLP
PolBi.
Brain
Cites.
Genes
Cora-MI.
Openi:
WikiP.
DBLP
WL
338.52
567.90
137,80
270. 18
301.68
379.68
660.12
00M
26.59
25.
62.14
60.93
52.76
50.59
42.18
0OM
556.68
292.77
658.04
36,463
66.72
52.02
Lanv.
344.47
582.45
158.79
247.27
335.57
798.75
40,726
28.86
67.51
58.18
52.97
47.81
41.40
RSC
307.70
526.17
K5.41
188.82
264.62
367.36
630.55
00M
28.04
29.19
67.39
66.28
56.14
52.01
44.86
COM
UF
331.79
506.30
91.36
208.51
305.43
410.17
560.45
00M
21.77
24.49
60.13
59.45
48.42
47.64
42.37
OOM
595.70
147.17
313.29
672.84
87,344
21.70
$1.36
HypHCC
272.81
519.96
416.38
632.02
594,23
529.04
678.45
00M
19.65
7.26
18.98
13.00
19.18
26.82
23.92
OOM
FPE
238.65
425.70
76.01
182.91
257.42
355.61
46240
31.67
31.37
12.75
69.38
67.78
59.55
$7.58
49.87
41.62
EPH
238.50
400.20
74.01
176.57
238.28
312.31
456.26
30,000
32,05
34.24
59.36
36
67.75
59.41
57.83
50.23
42.74
hierarchy based on heuristics or local objectives, UF, HypHC, gHHC, and FPH aim to reduce relaxed Dasgupta cost. For all the methods, we set a time limit of 120 hours and provide a budget of 512GB of memory for each experiment.
Experimental Setup. We repeat the randomized methods with five random seeds and report the scores of the discrete hierarchies. We use the same experimental setup as ZZigner al. (2021). i.e.,
we use n²' 512 internal nodes, compress hierarchies using the scheme presented by Charpentier & Booaadd (2199) and use 10 and 32-dimensional DeepWalk embeddings (Perozzi et al. 2014) on
the graphs for methods that require features. We train EPH using PAdamax (projected Adamax (Kingma & Ba 2014)) for 10000 epochs for Exp-Das and 3000 epochs for Exp-TSD. Additionally, every 1000 epochs we reduce the learning rate for B by a factor of 0.1 and reset the probabilistic hierarchy to the so far best discrete hierarchy. To approximate the expectancy of EPH, we use 20 samples, except for Spambase, Letter, and Cifar- 100 where we use 10, 1, and 1, respectively, to reduce the runtime. On the datasets Digits, Segmentation. Spambase, Letter, and Cifar- 100, we train EPH and FPH by sampling n n edges, on the remaining datasets, we use the full graph. Both, EPH and FPH are initialized using the average linkage algorithm. We train FPH with its original setting and proposed scheduler and report the minimum of both for each dataset. Finally, to obtain the discrete hierarchy for EPH and FPH we take the most likely edge for each row in A and B as Züggner et al. (202T) did. For the remaining methods, we use the recommended hyperparameters. An overview of the hyperparameters is shown in Tab. and an ablation study in App. B.5
5.2 RESULTS
Graph Dataset Results. We report the Dasgupta and Tree-Sampling Divergence results for the graph datasets in Tab. 2 EPH achieves 13/16 best scores and second best scores otherwise. In particular, EPH which optimizes Exp-Das always achieves a better Dasgupta cost compared to FPH which optimizes Soft-Das. This observation aligns with the theoretical advantages of Exp-Das compared to Soft-Das (see Sec. 4.2). EPH and FPH which both use the tree sampling probabilistic framework always achieve the best results. This highlights the benefit of the tree
sampling probabilistic framework for hierarchical clustering. The discrete approaches which uses heuristics achieve competitive results but are constantly inferior than EPH.
Furthermore, we can observe that the performance of the linkage algorithms, WL and AL, and the Louvain method is competitive, even though they use heuristics or local objectives infer hierarchy. Finally, the inferior performance of gHHC and HypHC can intuitively be explained by the fact that these methods are originally designed for vector datasets. WL, UF, and HypHC were not able to scale to the DBLP datasets within the memory budget. Indeed, they require to compute a dense n similarity matrix leading to out-of- out-of-memory (OOM) issues.
Vector Dataset Results. We report the Dasgupta costs of several methods on the vector datasets in Tab. Similarly to the graph datasets, EPH outperforms all baselines and achieves 7/8 best scores. These results demonstrate the capacity of EPH to also adapt to vector datasets. Further, EPH constantly outperforms FPH. This emphasized the benefit of optimizing expected scores compared to soft scores. In contrast with graph datasets, HypHC performs competitively on vector datasets. It is reasonable since this method is originally designed for vector datasets. FPH has a slightly worse performance than HypHC on most datasets and is only better Iris.
Hyperparameter study. We show in Fig. 3 (left) the effect of the number of sampled hierarchies on the EPH performances. On one hand, we observe that large number of sampled hierarchies (i.c. N 2 20) generally yields better results than a small number of sampled hierarchies (i.c. N < 10) except for Citeseer. Intuitively, higher number of sampled hierarchies should lead more
7

---

Under review as a conference paper at ICLR 2023
Table 3: Results for the vector datasets.
Dasgupta cost
Accuracy
Dataset
Zoo
Iris
Glass
Digits
Segi.
Spam.
Letter
Cifar
Zoo
Iris
Glass
Digits
Segm.
Spam.
Letter
Cifar
WL
56.26
69.98
122.16
1126.77
1266. 17
2962
12241
32979
0.74
0.76
0.44
0.82
0.61
0.76
0.33
0,49
AL.
121.64
1121
1258.22
2952.
12181
32972
0144
0.65
0.82
0.31
St.
57.67
126.33
1166.05
1368.21
3042
13166
33314
0.37
0.10
0:15
0.61
0:04
0.01
CL.
55.78
70.10
123,02
1140.26
1277.48
2971.59 199
12396
33131
0.81
0.77
0.40
0.59
0.51
0.74
0.26
0.33
Louv.
56.26
72.31
125.94
1126.48
1238.35
2916.48
11946
32940
0.60
0.83
0.42
0.68
0.29
0.86
0.18
0.05
RSC
55,94
69.10
121.45
1119,43
1257.20
1917.07
11895
32907
0.35
0.38
0.39
0.51
0.84
0.11
0.05
UF
122.43
1998.
0OM
gHHC
60.09
69.63
123,33
1119.74
1269
3018
12151
53089
0.59
0.71
0.42
0.51
0.30
0.69
0.08
0.01
HypHC
56.05
69:22
121.52
1118.08
125
2921 38
11930
(XIM
0.79
0.82
0.52
0.42
0.29
0.66
0.10
COM
FPH
56.13
09.13
122.00
1152.84
1258.55
2933, 56
12197
33224
0158
0,83
0.40
0.30
0.44
0.51
0.06
0.03
EPH
55.77
69.10
120.94
1117.58
1230.0
2916.17
11894
32913
0.70
0.83
0.40
0.65
0.53
0.86
0.14
0.18
Normalized Desguupa cost
-1
nvn
Number of sampled hierarchies
Number sampled edges
Brain
Genes
Cora-ML
WikiPhysics
Zoo
Segmentation
OpenFlight
Giteseer
Polblogs
Digits
Spambase
Figure 3: Hyperparameter study. Normalized Dasgupta costs for different numbers of sampled hierarchies (left) and different number of sampled edges (right) after the EPH training. including the average linkage algorithm (AL.) and a training on the full graph (FG). The scores are normalized such that each dataset has a mean of zero and standard deviation of one.
accurate expected score approximation. On the other hand, we observe that a very large number for sampled hicrarchies (i.e. N 2 100) might not lead to significant improvements while requiring more computational resources. Intuitively, the noise induced by a lower number of sampled hierarchies could be beneficial to escape local optima. In general, we found that 20 samples lead to satisfactory results for all datasets, thus achieving a good trade-off between approximation accuracy, optimiza- tion noise, and computational requirements. We show in Fig. 3 (right) the effect of the number of sampled edges on the EPH performances on vector datasets. Using more edges consistently leads to better results. In particular, going from n to n/nn shows significant performance improvement while going from nynn to n² yields only minor improvements. Hence, controlling the amount of sampled edges allows us to scale our method to large datasets while maintaining high performance. On the small datasets Zoo, Iris and Glass, we use the whole graph, while for the other datasets, we sample / n edges as a trade-off between runtime and quality of the hierarchical clustering.
External Evaluation. We propose to complement the evaluation with Dasgupta and TSD which are internal metrics with external evaluation metrics. However, since we typically do not have access to ground-truth hierarchies in real-world data, it is difficult to perform external evaluation. To address this, evaluate our models synthetic datasets with known ground troun hierarchies and investigate whether the inferred hierarchies on the vector datasets preserve the flat class-labels.
For the graph datasets, we use hierarchical stochastic block models (HSBMs) which allow us to compare the inferred hierarchies with the ground-truth hierarchies. As the HSBM graphs are generated based on random process, the ground-truth hierarchy not necessarily the best in terms of the Dasgupta cost or Tree-Sampling Divergence. Hence, we observe that the Dasgupta cost and Tree-Sampling Divergence of the hierarchies inferred by EPH are even better than the ground-truth hierarchies on the HSBMs. This underlines the great capacity of EPH to optimize the Dasgupta and TSD scores. Furthermore, we compute the normalized mutual information (NMI) between the different levels of the ground-truth hierarchy and the inferred hierarchy (see Tab. 4 We observe that EPH recovers almost perfectly the first three levels of the ground-truth hierarchy. Interestingly, the TSD objective appears to be more suitable metric to recover the ground-tru truth HSBM levels. We show the results of FPH in App. B.3 We show a visualization of the ground truth and inferred hierarchies in Fig.
For vector datasets, we flatten the derived hierarchies and compare clusters with the avail- able ground-truth labels, by applying the Hungarian algorithm align the cluster assign- ments with the labels as explained by Zhou et al. (2022). This procedure allows us to com- pute the accuracy, which we show the right-hand side in Tab. 3 While the linkage al-
8

---

Under review as a conference paper at ICLR 2023
Table 4: Results of EPH for the HSBMs with n'=# Cluster.
Dasgupta
sampling divergence
Method
HSBM Small
HSBM Large
HSBM Small
HSBM Large
GT EPH
26.29
130.16 121.08
43.14
51.50
26.19
43,56
51.53
Level
Normalized Mutual Information
Normalized Mutual Information
Level
1.0
1.0
Level 2
1,0
1.0
1.0
1,0
Level
0.77
0.81
0.87
0.99
(a) Small HSBM GT
(b) Small HSBM Exp-Das
(c) Small HSBM EXD-TSD
10
(d) Large HSBM GT
(e) Large HSBM Exp-Das
(I) Large HSBM Exp-TSD
Figure 4: Ground truth clusters and dendrograms compared the inferred ones for the HSBMs.
gorithms were inferior to the continuous optimization algorithms terms of Dasgupta cost, they dominate here. EPH, which was trained Exp-Das, yields the best accuracies only on Iris and Spambase. As the linkage algorithms and Louvain generate hierarchies using heuristics while the continuous methods aim minimize the Dasgupta cost the results not surprising, since the Dasgupta cost and other metrics do not necessarily go hand in hand.
Qualitative Evaluation. We visu- alize the largest cluster, i.e. most directly connected leaves, inferred on Cifar-100 using EPH. More specif- ically, we select the internal nodes with the most directly connected leaves. Furthermore, we sort the images by their probability, i.e. their entry in the matrix A. We show the 16 images with the highest prob- ability and the 16 with the lowest probability for the largest cluster in
(a) Highest Probability
(b) Lowest Prohahility
Figure 5: Largest derived cluster Cifar-100.
Fig. []] We observe that the images with high probabilities related insects. This shows that EPH is able to group similar images together. In contrast, the last images with the lowest probability. do not fit into the group. This demonstrates the capacity of EPH measure the uncertainty in the cluster assignments. We show additional results with the same behavior for other clusters in App. B.4 (see Fig. 9 and Fig. I0 Fig. 8). Furthermore, we visualize the graph and inferred hierar- chies of EPH for OpenFlight in Fig. 11 in the appendix. Both, minimizing Exp-Das and Exp-TSD generate reasonable clusters and are able to successfully distinguish different world regions.
CONCLUSION
In this work, we propose EPH, novel end-to-end learnable approach to infer hierarchies in data. EPH operates on probabilistic hierarchies and directly optimizes the expected Dasgupta cost and expected Tree-Sampling Divergence using differentiable hierarchy sampling. We show that the global optima of the expected scores are equal to their discrete counterparts. Furthermore, we present unbiased subgraph sampling approach to scale EPH large datasets. We demonstrate the capacity of our model by evaluating it on several synthetic and woal-world datasets. EPH outperforms traditional and recent state-of-the-ar baselines.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
EPH is not used on a specific real-world application, therefore, the outcome solely depends on how the practitioner uses This could potentially be abused by governments corporations by analyzing collected data at large scales using our algorithm. However, EPH can also have positive contributions by supporting scientists finding hierarchies in data.
While EPH outperforms other state-of-the-ar methods for hierarchical clustering we raise awareness of the possibility that the algorithm fails generate meaningful hierarchies, especially novel setting. Therefore, the result should carefully be assessed by its practitioner.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our experiments we provide overview of our datasets in App. B Furthermore, we provide a detailed description of the experimental setup and data preprocessing in Sec[5.1 and an overview of the hyperparameters we used in Table 9 Our model is implemented in PyTorch and will be publicly available upon acceptance. We use skleam to flatten the hierarchies and compute the Louvain algorithm. We provide proofs of the theorems we used in App. A for verifiability our theoretical results.
hhtpps//Acikii-lemmmmm/ssstaaaaa html
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pp. 36-43, 2005,
Katrin Amunts, Claude Lepage, Louis Borgeat, Hartmut Mohlberg, Timo Dickscheid, Marc-Etienne Rousseau, Sehastian Bludau, Pierre-Louis Bazin, Lindsay B Lewis, Ana-Maria Pess-eeus, et al. Bigbrain: an ultrahigh-resolution 3d human brain model. Science, 34066139;:472-14755 2013.
Nicolas Aspert, Volodymyr Miz, Benjamin Ricaud, and Pierre Vandergheynst. A graph-structured dataset for wikipedia research. In Companion Proceedings The 2019 World Wide Web Confer- ence, pp. 1 1188-119,, 2019.
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, 2008 (10):P10008, 2008
Aleksandar Bojchevski and Stephan Günnemann. Bayesian robust attributed graph clustering: Joint learning of partial anomalics and group structure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Gen- crating graphs via random walks. In International conference on machine learning, pp. 610-619.
PMLR, 2018.
Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré, From trees to continuous embed- dings and back: Hyperbolic hierarchical clustering. Advances in Neural Information Processing Systems, 33:15065-15076, 2020.
Bertrand Charpentier and Thomas Bonald. Tree sampling divergence: an information-theorrtic metric for hierarchical graph clustering. In IJCAI-19, 2019.
Bertrand Charpentier, Simon Kibler, and Stephan Günnemann. Differentiable dag sampling. arXiv preprint arXiv:2203.08500 2022.
Giovanni Chierchia and Benjamin Perret. Ultrametric fitting by gradient descent. Advances in neural information processing systems, 32, 2019.
Ara Cho, Junha Shin, Sohyun Hwang, Chanyoung Kim. Hongscok Shim, Hyojin Kim, Hanhae Kim, and Insuk Lee. Wormnet v3: a network-assisted hypothesis genssritingneningggg server for cacnorhabditis elegans. Nucleic acids research, 42 42(W1))W76-W8) 2014.
Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In Proceedings of the forth-eighth annual ACM symposium on Theory of Computing, pp. 118-127, 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://arcciiee. ics. uci aou..edumm
Michael B Eisen, Paul Spellman, Patrick O Brown, and David Botstein. Cluster analysis and display of gedeme-wide expression patterns. Proceedings of the National Academy of Sciences, 95(25): 1998.
Joseph Felsenstein. Inferring phylogenies, volume 2. Sinauer associates Sunderland, MA, 2004.
Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint 161 I. 1.0l 144, 2016.
11

---

Under review as a conference paper at ICLR 2023
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung. Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In European confer- ence on computer vision, pp. 491-507. Springer, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Richard A. Kronmal and Arthur V. Peterson. On the alias method for gemerating random variables from discrete distribution. The American Statistician, 33(4): 2022/09/29/ 1979. ISSN 00031305. doi: 10. 10.2307/2683739 URL https://doi. wtt.///00.00.0000222333333
Full
publication date: Nov., 1979.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbel-sinkhorn networks. arXiv preprint arXiv: urXiv:/802.000 1802.08665 2018.
Nicholas Monath, Ari Kobren, Akshay Krishnamurthy, and Andrew McCallum. Gradient-based hi- erarchical clustering. In 31 Conference on neural information processing systems (NIPS 2017), Long Beach, CA, USA, 2017.
Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. Gradient- based hierarchical clustering using continuous representations of trees in hyperbolic space. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 714-722, 2019.
Jani Patokallio. Openflights. URL /tRl/tttpp://ppee..igttssooo
Max Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris Maddison. Gradient estimation with stochastic softmax tricks. Advances in Neural Information Processing Systems, 33:5691- 5704, 2020.
Max Paulus, Chris J. Maddison, and Andreas Krause. Rao-blackwellizingg the straight-through gumbel-softmax gradient estimator. In International Conference on Learning Representations, 2021. URL httttttt/o/peeeeeeeee
net/ http::/www....eeooooooooeeeeeeee
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning social repre-
sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710, 2014.
Erzsébet Ravasz and Albert-László Barabási. Hierarchical organization in complex networks. Phys- ical review E, 67(2):0221 12, 2003.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Michael Steinbach, George Karypis, and Vipin Kumar. comparison of document clustering tech- niques. 2000.
Joe H Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301) ):236224:34 1963.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based ground- truth. Knowledge and Information Systems. 42(1):181-213, 2015.
Yuchen Zhang, Amr Ahmed, Vanja Josifovski. and Alexander Smola. Taxonomy discovery for personalized recommendation. In Proceedings of the 7th ACM international conference on Web search and data mining, pp. 243-252, 2014.
12

---

Under review as a conference paper at ICLR 2023
Sheng Zhou, Hongjia Xu, Zhuonan Zheng, Jiawei Chen, Jiajun Bu, Jia Wu, Xin Wang, Wenwu Zhu, Martin Ester, et al. A comprehensive survey on deep clustering. Taxonomy, challenges, and future directions. arXiv preprint arXiv:220..07579, 2022.
Daniel Zügner, Bertrand Charpentier, Morgane Ayle, Sascha Geringer, and Stephan Günnemann. End-to-end learning of probabilistic hierarchies on graphs. In International Conference on Learn- ing Representations, 2021.
13

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 EQUATIONS OF SOFT-DAS AND SOFT-TSD
In the following, we show the equations of Soft-Das and Soft-TSD.
Soft-Das(T)=
Σ
P(vs, v3)
M v, (x) P( anc(v))
NEN
p(z) log p(z)
Soft-TSD(T) = Σ
(10)
q(z)
ZEZ
where p(z)
Σ
P(vi, (yye:))p((==AAM
(11)
V.
((2)
Σ P())(()))(==AM))
(12)
VaSEV
A.2 CLOSED FORM SOLUTIONS OF EXP-DAS AND EXP-TSD
To compute closed form solutions of the expectancies, the following equations need to be solved:
Exp-Das(T)
Σ P(v.,
V V3, anc(v))
(13)
VoYyEV
ZEZ
p(z) log p(z)
Exp-TSD(T) = Σ E BT..AABT=(AABB)
(14)
g(z)
A.3 RELATION BETWEEN JOINT AND INDEPENDENT LCA AND ANCESTOR PROBABILISTIES
While the LCA probabilities crucial compute Soft-Das, Exp-Das requires the joint LCA and ancestor probabilities, i.e. p(z+ = V, A v,, v E anc():)), for the leaves v,, Vy and and the internal node Zę. In Theo. 3 we show that the joint probabilities are an upper bound of the product of the single terms.
7
ze
Z
Vi
V2
Vi
V2
Vi
V2
(a) r and ret meet at node Zgr.
(b) r and rég meet at node Zg.
(c) r r and rét meet at node
Figure 6: The different cases of the event p (z v1 v2lz4 anc(v)). While the LCA of v1 and V2 Zạ in every case, the LCA of and and the LCA of v2 and v are different. We have three cases: either the paths from v or V2 and v meet before zμ at node Zμr (shown in (a) and (b)), or all paths meet for the first time at Z (shown in fig. (c)).
Theorem 3. Let describe the probability under the tree-sampling procedure, 74 an internal node, V1, V2 and v leaves. Then, the following inequality holds:
p(zx- V1 v2)p(74 <anc(v)) (7x A V2, 7 anc(v))
(15)
14

---

Under review as a conference paper at ICLR 2023
Proof. First, observe that the right-hand side of the inequality be rewritten
p (zz = Vi A V2, 24 E anc(v)) = p (zs = V1 v2lzz E anc(v)) P(zz E anc(v)).
(16)
To prove the non-trivial case p (Zk anc(v)) # O, need to show that the following holds:
[zx = V1 A v2) S p (z = V1 A v2lzz E anc(v)).
(17)
Let 1: = (V, denote path from a leaf V. to an internal node 2, and let 2nd be the root node. Recalling from Zügner al. (2021) that the paired path probability under the tree-sampling procedure is
p((r)) (rggg) p(rt)) with 2 A V2, rewrite the LCA probabilities
(18)
plz+ Av/
Σ
p(r1))((())
(19)
Adding the condition Zţ E anc(v) means there exists path from the leaf v to the internal node Zμ- There are three different cases: first, the path meets rth and rig Z₁: for the first time, or the path meets the path ri or ri in a lower node 7u, with K <' The cases are shown in Fig. 6 In the first case, all three paths are independent. Thus, the LCA probabilities do not change. In the other two cases, they are only independent up to the node zur The probability for the path res is equal to since know that Z E anc(v). More formally, the conditional probability is
p [zx = V1 A v2lze E anc(v)) =
Σ
p(r") Zi: E anc(v))p(r"%) lak E anc(v)). (20)
Assuming that the path from to Zy meets the path from V1 to Zy in the node zu with & s k, we have
p(r z anc(v)))(r?2)z E ano(v)) = p(r (p(r)))))))))))))))()))))))))) 2 p(r())(((()
(21)
The last inequality follows since rv. is subpath of rt) and therefore has higher probability. This concludes the proof.
A.4 PROOF OF THEO. 2
In the following, we provide the proof of the inequality shown in Theo 2
Proof. To prove we first write out the definitions of Soft-Das and the expected Dasgupta cost,
Soft-Das(T) = Σ
P(v1, V2)
ΣΣ P(z= vı A v2) anc(v))
(22)
v1.22
and
E Ei-PA (T))
[ass(t)]
E E.PPAM(T)
Σ P(v1, V2)
ΣΣ
[xeamct))]
(23)
V1.V2
-BT-PA.(T)
P(vi, V2)
ΣΣ
T| (1
(24)
V1.12
Σ P(v1, v2)
Σ
E E [
(25)
VINa
Σ P(yi, v2)
Σ Σ
P(z=viAV2: anc(v))
(26)
v1.22
The proof follows by using Theo.
3
A.5 PROOF OF THEO. 0
Here we provide the proof of Theo.
Proof. To prove the left-hand side, we first observe that the expected Dasgupta cost can be rewritten convex combination of the Dasgupta costs of all possible hierarchies under the tree-sampling
15

---

Under review as a conference paper at ICLR 2023
procedure. More formally,
R PA.(T)
[Ta((T)
Σ (A.
(27)
TEH(m."")
where H(n, n') describes the set of all valid hierarchies with n leaves and n' internal nodes. Thus, the minimizer of the expected Dasgupta cost convex combination of all minimizing hierarchies, with the minimum being equal to the optimal Dasgupta cost. The equation on the right-hand side for TSD can be proved equivalently.
Note that, since the expectation operator is convex, any discrete optimizer (i.e. discrete hierarchies achieving the optimum value) of the discrete scores will be an optimizer of the expected scores and vice-versa. In this case discrete hierarchies this case discrete hierarchies are represented by deterministic A, B matrices. Only probabilistic hierarchies which are optmizers of the expected scores, represented by non-discrete A, matrices, are not optimizers of the discrete scores. This is expected since those probalistic hicrarchies do not belong to the valid input domain the discrete scores. addition, any sample we draw from these probabilistic optimizers is also discrete optimizer of Dasgupta or TSD because of the convexity of the expectation operator.
represented by deterministic A, B matrices. In
A.6 NON-CONVEXITY AND NON-CONCAVITY OF EXP-DAS
Minimizing convex function using gradient descent is easier than concave one. In constrained setting, minimizing a concave function heavily depends on the initialization. Exp-Das = (A, B)) neither convex nor concave with respect A and B. For both, counter-example exists. This implies that we can not tell whether Exp-Das converges into local or global minimum when train- ing. To show that Exp-Das
concave, is sufficient to find two hierarchies B1) and
To = (A2, B2) such that:
(Ts)) + Exp-Das(TT) Das((T)) 2 Exp-Das Das
(T + +T)
(28)
2
and equivalently to show that it is not convex:
Exp- Das (T)) + Exp-Das T2) 5 Das
- (Ti 2Tx++ T2)
(29)
2
where Tı + T - (A1 + A2, B + B2). In Fig. 7 we show these two examples. In (a) and (b) we
show two hierarchies and in (c) linear interpolation of these two. The graph in (d) satisfies Eq. [2
while the graph in (e) satisfies Eq. 29 We report the Dasgupta costs for all hierarchy and graph combinations in Tab.
Hierarchy
T2
Ti
Convex Example
3.5
3.5
3.375
Concave Example
3.0
3.0
3.25
Table 5: Dasgupta costs for all combinations of hierarchies and graphs from Fig.
B EXPERIMENTS INFORMATION
B. DATASETS
An overview of the graph and vector datasets are given in Tab. 6 and Tab. The deatils of the HSBMs are shown Tab.
16

---

Under review as a conference paper at ICLR 2023
Z3
Z3
Z3
A1
1/
A1
12
4
12
V1
V2
Va
V4
V1
V2
V3
V4
V1
V2
V3
V4
(a) Fi (Ā,, B1)
(b) T2
(Áz, B₂)
(c) Tr
0.5 F
0.5
T2
V1
V2
V3
V4
V3
VA
(d) Convex Example
(e) Concave Example
Figure 7: Three hierarchies and graphs that show that Exp-Das is neither convex nor concave with respect to A and B. The hierarchy in (c) is a linear interpolation of the hierarchies in (a) and (b). The graphs in (d) and (e) are counter-examples, with convex and concave behavior, respectively.
Table 6: Overview of the graph datasets.
Dataset
Number of Nodes
Number of Edges
PolBlogs
1222
16715
Brain
1770
8957
Citeseer
2110
3694
Genes
2194
2688
Cora-ML
2810
7981
OpenFlight
3097
18193
WikiPhysics
3309
31251
DBLP
317080
1049866
B.2 HYPERPARAMETERS
We show an overview of the hyperparameters we used in Tab.
B.3 HSBM RESULTS FOR FPH
We show the results for FPH on the HSBM graphs Tab 10
17

---

Under review as a conference paper at ICLR 2023
Table 7: Overview of the vector datasets.
Dataset
Number of Data Points
Number of Attributes
Number of Classes
Zoo
101
17
Iris
150
4
3
Glass
214
10
Digits
1797
8x8
10
Segmentation
2310
19
Spambase
4601
57
2
Letter
20000
16
26
Cifar- E00
50000
2048
100
Table Overview the HSBMs.
Dataset
Number of Nodes
Number of Edges
Number of Clusters
Small HSBM
101 1186
1428 27028
15
Large HSBM
53
B.4 ADDITIONAL VISUALISATIONS
0
3 0
0
(a) Largest Cluster
(b) Second Largest Cluster
5
(c) Third Largest Cluster
(d) Fourth Largest Cluster
Figure 8: Largest derived clusters on Digits. On the left in each subplot the 16 images with the highest probability, on the right the 16 images with the lowest probability.
18

---

Under review as a conference paper at ICLR 2023
Table Overview of the Hyperparameters.
Method
Hyperparameter
Value
LR
Scheduler
Initialization
Average Linkage 20
EPH
Num. Samples
Num. Samples"
10
Num. Samples"
1
LR
min(Scheduler, 0.05)
FPH
LR
min SScheuuue,,, 150]
Initialization Epochs
Average Linkage
1000
LR
min 1e 5e
le 1e-
Temp.
min [1e .5
_e
LR Temp. 6.0 Epochs
le-3
HypHC
le
50
Num. Triplets
n²
Loss LR Epochs
min(Dasgupta, Closest+Size)
UF
0.1
500
LRA (Exp-Das)
0.1
LR (Exp-Dat (aa)
0.05
LR (Exp-Das)
0.1
Scheduler
LR (Exp-Das)
0.01
LR, (Exp-TSD)
150
LR (Exp-TSD)
500
Sampling frequency
1000
Sampling frequency" .*...
2000
Epochs (Exp-Das)
10000
Epochs (EXp-TSD)
3000
Embedding Dim.
10
DeepWalk
Embedding Dim. *OUEN
32
Used DBLP and Spambase
Used for Letter and Cifar- 100
Used for Letter
Used for Cifar- 100
.*.. Used for DBLP
19

---

Under review as a conference paper at ICLR 2023
Table 10: Results of EPH for the HSBMs with n'=# Cluster.
Dasgupta cost
Tree-sampling divergence
Method
HSBM Small
HSBM Large
HSBM Small
HSBM Large
GT Level
26.29
130.16
43.14
51.50
27.84
127.99
43.53
51.53
Level
1.0
0.99
1.0
1.0
Level
1.0
0.95
1.0
1.0
Level 3
0.77
0.81
0.87
0.99
(a) Highest Probability
(b) Lowest Probability
Figure 9: Second largest derived cluster on Cifar-10k 100..
B.5 ABLATION
For our ablation study we use a simplified optimization scheme. More specifically, we use a fixed learning rate of 0.05 and only train for 1000 epochs.
Constrained vs. Unconstrained Optimization. We require the rows of the matrices A and B to be row-stochastic. There are several possibilities to enforce this. Either can perform constrained optimization using projections onto the probabilistic simplex or simply perform softmax operation over the rows. In Tab. TT we show comparison of the Dasgupta costs on the graph datasets for several graph datasets. We can observe that the constrained optimization,i.e using projections after each step yields better results than the unconstrained optimization on every graph. This aligns with the findings of Zügner et al. (021), Therefore, recommend using constrained optimization.
Initialization. The initialization model can play a crucial role. Zügner et al. 202T) found that using the AL algorithm initialization yields substantial improvements. Therefore, compare
(a) Highest Probability
(b) Lowest Probability
Figure 10: Third largest derived cluster Cifar-100...
20

---

Under review as a conference paper at ICLR 2023
(a) Das 64 clusters
(b) TSD clusters
Figure 11: Inferred clusters inferred by EPH optimizing Exp-Das and Exp-TSD. 64 clusters highlighted in the graphs and dendrograms.
Table 11: Dasgupta costs for constrained and unconstrained optimization several graph datasets with n' = 512 internal nodes.
Dataset
PolBlogs
Brain
Citeseer
Genes
Cora-ML
OpenFlight
WikiPhysies
Constrained
252.55
428.40
74.84
178.90
242.38
324.45 349.20
481.92
Unconstrained
272.60
457.62
79.47
188.02
269.10
526.99
21

---

Under review as a conference paper at ICLR 2023
Soft-Das Interpolation
Exp-Das Interpolation
Nomalizel Sont
0.8
2.5
0.6
Norma Ized ExPr
0.2
0.2
0.5
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
D.4
0.6
0.8
1.0
Factor a
Factor a
Brein
Citeseer
Core-ML
Genes
Openflight
Polblogs
WikiPhysis
Figure 12: Linear interpolation of Soft-Das and Exp-Das scores from the average linkage hierarchy to the hierarchy inferred by Exp-Das.
both initializations and additionally test using their algorithm FPH as initialization. We show the Dasgupta costs for several graph datasets Tab. 12 As expected, using the AL algorithm or FPH
Table 12: Dasgupta costs for different initializations several graph datasets with n' = 512 internal nodes. In the first three rows the initial Dasgupta costs and in the last three rows the Dasgupta costs after the training. Best scores in bold, second best underlined.
Dataset
PolBlogs
Brain
Citeseer
Genes
Cora-ML
OpenFlight
WikiPhysics
Random
914.11
1285.68
1574.76
1621.82
2107.65
2302.13
2479.51
AL
355.60
556.68
83.69
196.50
292.77
363.40
658.04
FPH
262.47
453.17
77.05
179.55
257.42
355.61
538.47
Exp-Das (Random)
275.44
499.12
307.52
368.66
564.35
502.22
624.27
Exp-Das (AL)
252.55
428.40
74.84
178.90
242.87
324.45
481.92
Exp-Das (FPH) 251.55
431.15
74.88
177.32
245.79
326.46
527.02
as initialization yields significant improvements over a random initialization. Even though the FPH initialization starts with a better hierarchy, the resulting hierarchies are inferior than the AL. initializa- tion. This could be caused by local minima, in which the model gets stuck. We recommend using AL. as initialization since it performs best on most datasets and has a lower computational cost than FPH.
Direct vs. Embedding Parametrization. Additionally to the direct parametrization of the matrices A and B, we test an embedding parametrization for each node in the hierarchy. More specifically we use d-dimensional embeddings for the leaves and internal nodes. To infer A and B, we perform a softmax operation with an additional learnable temperature parameter t, over the cosine similarities between the embeddings. The main advantage of the embedding approach that, additionally to the hierarchical clustering, we gain node embeddings that can be used for downstream tasks such classification regression. We test the embedding parametrization with = 128 on several graph datasets. Once we let éę be learnable and once we freeze it to & 1. We compare the results the constrained optimization. While we train the direct parametrization for 1000 epochs, the embedding approach is trained for 20000 epochs. This is done to ensure convergence since randomly initialized. We show the results in Tab. 13 First, we observe that
Table 13: Dasgupta costs for the direct and embedding parametrization on several graph datasets
with n' = 512 internal nodes. Best scores in bold, second best underlined.
Dataset
PolBlogs
Brain
Citescer
Genes
Cora-ML.
OpenFlight
WikiPhysics
Direct
252.55
428.40
74.84
178.90
242.38
324.45
481.92
Embedding (f, 1)
451.63
659.11
1008.23
1146.86
1261.91
968.41
1108.42
Embedding
249.84
440.29
213.99
290.19
409.68
373.07
514.91
not using a temperature parameter yields substantially worse results. Furthermore, the embedding parametrization is inferior to the direct parametrization, even though it was trained for 20000 epochs, while the constrained optimization was only trained for 1000. Only on the dataset PolBlogs the embedding approach is slightly better than the direct parametrization. We attribute the inferior
22

---

Under review as a conference paper at ICLR 2023
Peddays
Erg
222
500
235
32.5 200
125
220
22.95
124
220
Figure 13: Dasgupta costs for different numbers of internal nodes.
Munber ntaral todas
Humoe
WL
Hypii
MHi
Figure 14: TSD scores for different numbers of internal nodes.
Table 14: Standard Deviations for the graph datasets.
Dasgupta cost
Tree-sampling divergence
Dataset
PolBl.
Brain
Cites.
Genes
Corn ML.
OpenI:
WikiP.
DBLP
PolBI.
Bruin
Cites.
Genes
Cona-ML
OpenI:
WikiP.
DBLP
3HHC
7.43
16.19
7.49
12:05
192.38
200.76
42.82
4,887.56
0.09
0.18
0.12
0.16
5.93
7.97
0.16
0.28
HypHC:
6.37
9.08
22.93
51.74
28.83
36.64
00M
0.47
0.64
0.71
0.35
1447
1.02
EPH
0.43
1.31
0.10
2.17
1.02
2.19
2.95
35.89
0.31
0.39
0.01
0.07
0.02
0.12
0.15
0.03
Table 15: Standard Deviations for the vector datasets.
Daagupta cost
Accaracy
Dateset
Zoo
Iris
Glass
Digits
Segrnnntation
Spambuse
Letter
Cilar
Zuo
Iris
Glass
Digits
Segmentation
Spamiuse
Letter
Cifir
aHHC
0.03
0.35
2.30
5.98
40.55
1.02
167.34
167 34
0.09
0.04
0.04
0.08
0.01
0.03
0.03
0.01
HypHC
0.08
0.27
1.37
0.46
2.04
45.10
00M
0.05
0.01
0.05
0.07
0.06
<0.01
0.01
00M
EPH
0.01
0.01
0.01
0.11
0.22
1.11
2.42
5.73
0.03
<0.01
0.01
0.06
0.05
<0.01
0.01
0.01
performance to the random initialization and the fact that we have to use a softmax operation instead of projections. Our results are in line with the ablation study of Zügner et al. (202T). They also parametrized their model using embeddings and used the softmax function on the negative Euclidean distances infer the matrices and B. Since the embedding approach yields worse results with longer training times, we recommend using the direct parametrization.
Number of Internal Nodes. As in many real-world problems we do not know the number of internal nodes n' beforehand in our experiments. While increasing n' generally leads to more refined and expressive hierarchies, it reduces interpretability and comes with higher computational cost. To select the hyperparameter n', we test various choices several datasets. We show the corresponding Dasgupta costs and TSD scores in Fig. 13 and Fig. 14 We found that n' = 512 is sufficient to capture most information. In practice we recommend using the Elbow method.
Number of Sampled Hierarchies. Another crucial hyperparameter for EPH is the number of sampled hierarchies. Additionally to Fig. 3 we provide the raw Dasgupta costs and standard errors after the training in Fig. 15 Furthermore, we show the influence the number of samples to approximate the expected Dasgupta cost randomly initialized hicrarchies in Fig. 16
B.6 STANDAARD DEVIATIONS
We show the standard deviations of the randomized models on the graph datasets in Tab. 14 and for the vector datasets in Tab. 15
23

---

Under review as a conference paper at ICLR 2023
Table 16: Runtime in seconds for the graph datasets with n' = 512 internal nodes.
PolBlogs
Brain
Citeseer
Genes
Cora-ML
OpenFlight
WikiPhysics
DBLP
# Nodes
1222
1770
2110 3694
2194
2810 7981
3097 18193
3309
317080
# Edges
16715
8957
2688
31251
1049866
WL
<1
<1
OOM
<1
Louv.
1031
RSC
92
78
104
427
280
626
863
OOM
UF
OOM
gHHC
75
79
73
78
73
79
83
15630
HypHC
2043
4163
5981
6816
11557
14278
16778
0OM
FPH
452
547
345
373
644
592
667
6647
EPH
3834
3402
2609
2848
3322
4419
6389
224331
Table 17: Runtime in seconds for the vector datasets with n' min(n 1,512) internal nodes.
Zoo
Iris
Glass
Digits
Segmentation
Spambase
Letter
Cifar- 100
# Points
101
150
214
1797
2310
4601
20000
50000
WL
<1
<1
<1
8
13
51
983
8316
AL
<1
<1
<1
8
13
51
985
8564
SL
<1
<1
51
975
8494
CL
<1
<1
<1
8
13
52
986
8594
Louv.
<1
<1
<1
14
55
1065
7324
RSC
1
2
27
40
127
2009
14110
UF
<1
<1
<1
9
14
57
1132
OOM
gHHC
47
57
59
83
66
89
110
8462
HypHC
47
60
77
3385
5814
26933
250792
OOM
FPH
87
144
2586
3963
13876
134845
427557
EPH
1058
1541
2407
23574
44251
31435
130227
430322
24

---

Under review as a conference paper at ICLR 2023
Eram
Opand fyr.
Gone
Chosee
382
106
13
300
200
10
20
252
430
402
Number stanckkhheurcke
Number sins hiuurhii
Nunzer dtaargee haracchi
Figure 15: Dasgupta costs and standard error for different numbers of sampled hierarchies after the EPH training.
2483
225
3223
2000
2457
2000
Nurber staatckcheeurcee
Number sins Narrrhhia
Nunoar dtaagged harachhi
Number of samplls hararchi
Figure 16: Approximated Expected Dasgupta costs for different numbers of sampled hierarchies for randomly initialized probabilistic hierarchies.
B.7 RUNTIMES
We report the runtimes for EPH and the baselines in Tab. 16 and Tab. 17 While HypHC, FPH and EPH are executed on GPU (NVIDIA A100), the remaining method do not support or did not re- quire GPU acceleration. Since gHHC has lower computational runtime than the other randomized methods, we run with 50 random seeds instead of 5.
B.8 PSEUDOCODE
the following we provide formal description of our EPH algorithm, the subgraph sampling, and how normalize graphs.
Algorithm 2 NormalizeGraph
Algorithm EPH
Require: G EV; Graph 1: P(v;, Vÿ) 4- Eaver Wa.v
Require: g (V, E): Graph
Wi,
Require: T = B): Initial hierarchy
2: P(v.) E Ky
Require: a: Learning rate
Require: K: Number of sampled hierarchies
for 1,... do
Algorithm SampleSubgraph
2: 9t +- 0
3: for I,...,
......,K K do + SampleSubgraph(()
Graph Require: M: Number of sampled edges
Require: G = (V, G=VV,
4:
É + MultiSet() allow duplicate edges
5:
T~ PA,
2: for m = 1... do
6:
9: + + Vcocore
(vr,v,) P(vs, vy)
7:
end for
4: Ê.add(e)
8:
Te T
K gt
5: end for
9:
T (T)))
simplex projection
6: 9 + (V, B)
10:
end for
11: return Te
7: NormalizeGraph(()
8: return
25


Reviews:
[{"review_id": "AuXIrts0A96", "reviewer": "Reviewer_Cazv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper considers hierarchical clustering with expected objectives.  This problem aims to optimize the expected objective (e.g. Dasgupta cost or Tree-sampling divergence) over a distribution of discrete hierarchies. They show that this problem has the same global objective as its discrete counterpart.  They propose a new method called the expected probabilistic hierarchies (EPH), which is an end-to-end gradient-descent-based optimization by using a differentiable hierarchy sampling. They also scale this method to large graphs with an unbiased subgraph sampling approach. They show that their algorithm performs well on real-world datasets.", "summary_of_the_review": "The problem considered in this paper is essentially the same as its discrete counterpart. They propose a new end-to-end learning framework for this problem while the techniques are quite standard. Their method achieve better performance than baselines while the improvement is very marginal and the objectives of some baselines are different from the evaluation objective.", "strength_and_weaknesses": "Strengths:\n1. They propose an expected optimization problem over hierarchies.\n2. They propose a new end-to-end learning framework for this problem.\n3. Their method outperforms baselines on real-world datasets. \n\nWeaknesses:\n1. The proposed two expected optimization problems seem identical to their discrete counterparts.\n2. How would this new method compare with the method based on iterative sparsest cuts for Dasgupta's cost?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3u2z_B_vIN3", "reviewer": "Reviewer_9qMA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper builds on a recent modelling of the hierarchical clustering of [Zugner et al. 2021] to learn discrete structures by gradient descent.\nThe structure is modelled using two row-stochastic parameter matrices: $A$ parametrizes the probability distributions of each sample of belonging to a cluster ($n$ distributions); $B$, a strictly upper triangular matrix, parametrizes the hierarchy between clusters, i.e. the probability of a cluster of being a child of another cluster up in the ordering ($n'-1$ distributions).\n\nWhile [Zugner et al. 2021] optimizes soft-version of the objectives Das and TDS, the current work proposes to optimize a Monte Carlo approximation of the expected objectives using a perturb-and-MAP sampling scheme, more precisely leveraging the gumbel-softmax trick.\nBecause in the considered parametrization each probability distribution is an independent categorical, this optimization procedure is unbiased in the space of continuous hierarchies. \n\nThe method is finally applied on graph and vector data, and shown to outperform existing methods when optimizing the metric used for evaluation (not when evaluating accuracy).", "summary_of_the_review": "The paper has several weaknesses, that I believe should be easy to fix. The most concerning one is the inaccuracy on the unbiasedness of the learning procedure.\nOtherwise, the paper is well-written. The contributions have limited novelty, but could have a good impact in the hierarchical clustering domain.\n\n**update after discussion**\n\nThe authors addressed the concerns I raised and revised the paper accordingly. Because of this, I raised my score to 6.\nI am not willing to increase it more as the work boils down to an application of well-known techniques in discrete optimization that (i) did not require deriving any new results and (ii) in practice does not provide better structures (see Table 3 - accuracy).", "strength_and_weaknesses": "### Strengths\nThe paper is very well-written: the motivation is convincing and the contributions are stated clearly. The theoretical and model contributions are somehow novel, as they correspond to a novel application (i.e., hierarchical clustering) of well-known techniques and results in discrete optimization.\n\n### Weaknesses\n1. Several times in the paper (e.g., abstract, introduction) it is claimed that **\"the optimum of the expected scores is equal to the optimum of their discrete counterparts\"**. This statement **is not accurate**: the optimal score is the same (and this is what is proved in the appendix) but the optima are the same only in the case that the optimum of the discrete score is unique (i.e., not degenerate).\nFurthermore, **this claim coupled with the statement that \"EPH provides an unbiased estimate of Exp-Das and Exp-TSD\" misleads the reader to think that the overall optimization is unbiased w.r.t. the discrete hierarchy**, which is not true (see discussion in [1] and [2]). Although these claims are partially rectified in Section 4.3, under Limitations, I encourage the authors to clarify all these points from the beginning.\n\n2. Regarding the chosen parametrization of the hierarchies from [Zugner et al. 2021], I have a concern about the modelling of the cluster hierarchy by B.  Because it is row-stochastic, the only constraint enforced is that the probabilities of a non-root node of being a child of the other nodes sum to 1. This means that non-hierarchical structures are allowed in this parametrization. \nTo give an example, suppose we have 3 clusters: the root $z_3$, and $z_1$, $z_2$ internal nodes. if z_2 belongs to z_3 and z_1 belongs to z_2, with the chosen parametrization $z_1$ can also belong to z_3. Could the authors elaborate on this point?\n\n3. In Eq. 3 it would be helpful to specify which variables are given by the task at hand and which are optimized. While reading the paper, it is not clear whether the node and edge probabilities are determined by the dataset (e.g., by the similarities). This confusion stems from the existence of two different graphs in the problem formulation: the undirected graph given by the dataset and the learned directed acyclic graph for the hierarchy. It would help the reader to stress this difference and use different terms for the edges and nodes of the dataset graph.\n\n4. In Figure 2, without the similarities between nodes in the $K_4$ graph it is hard to appreciate that hierarchies (b) and (d) model the problem better than (c). As all the nodes are connected to all the others, hierarchy (c) seems on the contrary more suited as it assigns all nodes to the same cluster. Moreover, without the similarities the scores given in the caption come out of the blue. \n\n5. In the empirical evaluation, it is not clear whether the datasets are split into training/test samples. It is important to clarify this point in order to appreciate the results of Table 2 and 3. Are the scores reported for EPH and FPH the training losses? Also, which objective is used when reporting accuracy: Das or TSD? In general, the standard deviations of the results should be also reported, in order to assess the significance of the gaps.\n\n### Minors\n- page 4: \"of which $z$ is an ancestor of\" -> whose ancestor is $z$\n- page 7: hierarchical -> hierarchy\n\n[1] Chris J. Maddison, Andriy Mnih, Yee Whye Teh: The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. ICLR, 2017\n\n[2] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, Andriy Mnih: Monte Carlo Gradient Estimation in Machine Learning. J. Mach. Learn. Res., 2020\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-ZAiAebzQx", "reviewer": "Reviewer_EPYj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors consider the problem of inferring a hierarchal clustering of dataset instances.  The problem has typically been approached as either a discrete optimization problem or a continuous, relaxed form of the discrete problem.  In the discrete setting one searches over all possible hierarchies - with each instance having a single internal parent node and each internal node (other than the root) having a single internal parent node.  In the continuous setting, nodes are softly assigned to more than one parent node.  The authors focus on probabilistic hierarchical clustering, which maintains a distribution over discrete hierarchies and introduce Expected Probabilistic Hierarchies (EPH) as a means to optimize two hierarchical clustering cost metrics - Dasgupta cost and Tree-Sampling Divergence - in expectation.  They show that maximizing these two cost methods in expectation is consistent with the non-probabilistic variant, introduce a method for efficiently sampling hierarchies as the number of instances grows and demonstrate the effectiveness of the method on some real datasets and synthetic datasets.", "summary_of_the_review": "Overall, I like this paper.  The idea of sampling over a distribution of hierarchies is appealing and I think the authors did a nice job of illustrating how to use the probabilistic model to optimize over the dasgupta cost and TSD.  However, I’m not sure if the paper in its current form is quite good enough.  With additional clarity of the procedure and of the theoeretical result, it could be good enough.", "strength_and_weaknesses": "Overall, I thought the paper was well written and had a clear and natural development.  The main idea is a logical extension of prior work, but to the best of my knowledge is novel and is a non-trivial extension. The main theoretical results are intuitive and provide a nice justification for the proposed sampling procedure.\n\nWhile the paper was well written, I do think the authors could have devoted more time to explaining the reasons for using the Dasgupta cost and TSD?  Is it because prior art already existed for them?  Also, I am not an expert in probabilistic hierarchical clustering methods and the distinction between EHC and Zugner et al.’s FPH method was unclear.  In addition, I would liked to have seen a more formal description of the proposed algorithm, including the subgraph sampling procedure.  EPH seems primarily like a way to model distributions over hierarchies under different cost metrics. The reader is left to infer the steps needed to actually optimize over this model.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject