Expected Probabilistic Hierarchies
Authors: Marcel Kollovieh
Bertrand Charpentier
Daniel Zügner
Stephan Günnemann
Venue: NeurIPS 2024 poster (2024)
Keywords: hierarchical clustering
graph clustering
clustering
unsupervised learning
probabilistic models
Primary area: probabilistic_methods
TL;DR: Probabilistic model learning hierarchies in data by optimizing the expected metrics via gradient descent outperforming several baselines.

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 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 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 optimization, 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 quantitatively and provides meaningful hierarchies in qualitative evaluations.

Expected Probabilistic Hierarchies
Marcel Kollovieh" 1,2,3
Bertrand Charpentier
Daniel Zügner
Stephan Günnemann 1,3,444
School of Computation, Information and Technology. Technical University of Munich 2 Munich Data Science Institute Munich Center for Machine Learning Pruna AI Microsoft Research Al for Science
Correspondence to: m. w.l.ooiehettmm.co
Abstract
Hierarchical clustering has usually been addressed by discrete optimization using heuristics or continuous optimization of relaxed scores for hierarchies. In this work, propose to optimize expected scores under probabilistic model over hierar- chies. (1) We show theoretically that the global optimal values of the expected Dasgupta cost and Tree-Sanee Saep-inm divergence (TSD), unsupervised metrics for hierarchical clustering, are equal to the optimal values of their discrete counterparts contrary 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 optimization, and an unbiased subgraph sampling approach to scale large datasets. (3) We evaluate EPH on synthetic and real-world datasets includ- ing vector and graph datasets. EPH outperforms all other approaches quantitatively and provides meaningful hierarchies in qualitative evaluations.
Introduction
fundamental problem in unsupervised learning is clustering. Given dataset, the task partition the instances into similar groups. While flat clustering algorithms such as k-means group data points into disjoint groups, hierarchical clustering divides the data recursively into smaller clusters, which yields several ad advantages over flat onc. Instead of only providing cluster assignments of the data points, captures the clustering multiple granularities, allowing user choose the desired level of fine and coarseness depending on the task. The hierarchical structure can be easily visualized in dendrogram (e.g., .. see Fig. 4), making it easy interpret and analyze. Hierarchical clustering finds applications in many areas, from personalized recommendation [39] and document clustering [35] to gene-expression [16] and phylogenetics [17]. Furthermore, the presence of hierarchical structures can be observed in various real-world graphs in nature and society [33].
first family of methods for hierarchical clustering are discrete approaches. They aim optimizing some hierarchical clustering quality scores on a discrete search space, i.c.:
max score X, (,T) s.t.f discrete hierarchies,
(1)
where X denotes a given (vector or graph) dataset. Examples of score optimization could be minimization of the discrete Dasgupta score [12], the minimization of the error sum of squares [37],
the maximization of the discrete TSD [8], or the maximization of the modularity score [4]. Discrete approaches have two main limitations: the optimization search space of discrete hicrarchies is large and constrained, which often makes the problem intractable without using heuristics, and the learning procedure is not differentiable and thus not amenable gradient-based optimization, done by
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

most deep learning approaches. To mitigate these issues, a second, more recent family of continuous methods proposes to optimize some soft-ssscress on continuous search space of relaxed hierarchies:
max softscoroe (X,7) s.t.7 E relaxed hicrarchies.
(2)
T
Examples the relaxation of Dasgupta [7, 10, 41] TSD scores [41]. A major drawback of continuous methods is that the optimal hierarchy of soft scores might not align with their discrete counterparts.
Contributions. In this work, we propose to optimize expected discrete scores, called Exp-Das and Exp-TSD, moving away from prior work on relaxed soft scores. In particular, our contributions can be summarized as follows:
Theoretical contribution: We analyze the theoretical properties of both soft and expected scores. We show that the minimal value of a continuous relaxation can different from that of the discrete Dasgupta cost while the optimal values of the expected scores are equal to their optimal discrete counterparts.
We propose new method called Expected Probabilistic Hierarchies (EPH) to optimize Exp-Das and Exp-TSD. EPH provides an unbiased estimate of Exp-Das and EXp-TSD with biased gradients based differentiable hierarchy sampling. By utilizing an unbiased subgraph sampling procedure, EPH scales to large (vector) datasets.
Model contribution:
Experimental contribution: In quantitative experiments, we show that EPH outperforms other baselines on 20/24 cases on 16 datasets, including both graph and vector datasets. In qualitative experiments, we show that EPH provides meaningful hierarchies.
2 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 new cluster. There are several ways to define the similarity of two clusters. The average linkage (AL) method uses the average similarity, while single linkage (SL) and complete linkage (CL)
the minimum and maximum similarity between the groups, respectively [18]. Finally, the ward linkage (WL) algorithm [37] operates Euclidean distances and merges the two clusters with the lowest increase in the sum of squares. In contrast, Bayesian Hierarchical Clustering [19] uses statistical hypothesis tests to decide which clusters to merge. Another agglomerative approach is the Louvain algorithm [4], which iteratively maximizes the modularity score. A more recent parallelized agglomerative graph-based approach, ParHAC. enables scaling massive datasets. In terms of quality, however, ParHAC performs inferior to AL w.r.t. the Dasgupta cost [14]. Unlike agglomerative methods, divisive algorithms work in a top-down fashion. Initially, all leaves share the same cluster and recursively divided into smaller ones using flat clustering algorithms. Famous examples are based on the k-means algorithm [35] or use approximations of the sparsest cut [12].
Continuous Methods. recent years, many continuous algorithms have emerged to solve hierarchical clustering. These methods minimize continuous relaxations of the Dasgupta cost using gradient descent based optimizers. Monath et al. [27] optimized a probabilistic cost version. To parametrize the probabilities, they performed softmax operation learnable routing functions from each node on a fixed binary hierarchy. Chierchia and Perret [10] proposed UFit, a model operating in the ultrametric space. Furthermore, optimize their model, they presented a soft-cardinal measure to compute a differentiable relaxed version of the Dasgupta cost. Other approaches operate on continuous representations in hyperbolic space, such as gHHC [28] and HypHC [7].
Zügner et al. [41] recently presented a flexible probabilistic hicrarchy model (FPH). FPH directly parametrizes a probabilistic hierarchy and substitutes the discrete terms in the Dasgupta cost and Tree- Sre--Samlingg Divergence with their probabilistic counterparts. This results in a 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 Gunbbe-SSotmax [20] or Gunbbe--Snkhom [26] are used to
retain gradients when sampling discrete variables. These differentiable sampling methods have been

---

used for several tasks, including DAG predictions [9], spanning trees or subset selection [30], and generating graphs [6]. In contrast to prior work, EPH enables optimizing the expected clustering scores under a probabilistic hierarchy by utilizing differentiable sampling. Note that sampling spanning trees is not applicable our case since we have a restricted structure where the nodes of the graph correspond to the leaves of the tree.
3 Probabilistic Hierarchical Clustering
We consider graph dataset. Let = (V, be graph with n vertices V {Vi,.... ..). and m edges F = (ei,...,ee,, em)- Let Wi, denote the weight of the edge connecting the nodes v; and vj if ( E F., 0 otherwise, and wy Σj Why Ey the weight of the node v,. In general, we assume a directed graph, i.e., Way # W9.5- We défine the edge distribution P(v;, Vz) for pairs of nodes, P(v;, vj) x Wi.j. s.t. EY.NEV P(v,, V2) = and equivalently the node distribution P(v:) x wa, s.t. Ever P(v.) = 1. We can extend this representation to any vector dataset D = {xI...., Xn and interpret the dataset
graph by using the data points x; nodes and pairwise similarities (e.g..
cosine similarities) as edge weights.
Discrete Hierarchical Clustering. We define a discrete hierarchical clustering t of a graph G as rooted tree with leaves and n' internal nodes. The leaves V = (V1, V2.-..; Vn. represent the nodes of G. while the internal nodes Z = {z1, 72. 2, 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, 1 j"xxn' and B E {0, 1) xn', i.c., i = (A, B). While A 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, has exactly one outgoing edge, we have the following constraints: Σj Ai,-
S n, Σn BL,- = for S < n', and Σ Bu. = O for the last row. Thus, except for the last row of
for
B, both matrices are row-stochastic. We denote the ancestors of v as anc(v), and the lowest common ancestor (LCA) of the two leaves V; and V, in T as V; v.-
Probabilistic Hierarchical Clustering. Zügner et al. [41] recently proposed probabilistic hierarchies. The idea is to use continuous relaxation of the binary adjacency matrices while keeping the row- stochasticity constraints. Thus, we end up with two matrices A E [0, 1|mxn' and B [0, 1]x xx', The entries represent parent probabilities, i.c., A.j == p(z; v:) describes the probability of the internal node z, being the parent of v; and B.j := p(z;] (4) the probability of the internal node zj being the parent of z; Together, they define probabilistic hierarchy T = (A, B). Given such a probabilistic hierarchy, one can easily obtain a discrete hierarchy by interpreting the corresponding rows of A and B as categorical distributions. We sample an outgoing edge for each leaf and internal node. Since B restricted to be an upper triangular matrix, this tree-sampling procedure will result in valid discrete hierarchy, denoted by T (A, B) (T, Alternatively, instead of sampling a discrete hierar- chy, one can take the most likely edge for each node. This can be efficiently done by selecting the entry with the highest probability in each row, resulting in the discrete matrices Á and B. This approach serves as a greedy approximation to extract the most likely hicrarchy from the probabilistic one.
4 Expected Probabilistic Hierarchical Clustering
4.1 Expected Metrics
Unlike flat clusterings, there has been a shortage of objective functions for hierarchical clusterings. Thus, many algorithms to derive hierarchies were developed without a precise objective. An objective function not only allows to evaluate the quality of hierarchy but also yields possibilities for optimization techniques. Recently, the two unsupervised functions Dasgupta cost (Das) [12] and Tree-Sampling Divergence (TSD) [8] 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 recent metric specifically tailored graphs. In addition to being unsupervised, i.c., applicable in cases where the data is unlabeled, both metrics have intuitive motivations. The metrics can be written as:
Das(T)= = Σ P(v., vy)c(v, A vz)
and
TSD(T) = -KL((2)]l((z)),
(3)
VAREVV
3

---

Hierarchy:
Discrete Hierarchies: (1, F
Differentiable
hiemrchy
sampling
Graph
Subgraph
Loss computation
Subgraph
B B [ecor(()] ss
E, Score(T
sampling
N
Forward
Rackward
Figure 1: Overview of our proposed EPH model. During training, EPH first samples discrete hierarchies using our differentiable hierarchy sampling (Sec. 4.3) and a subgraph using our subgraph sampling procedure (Sec. 4.4). The expected scores are then computed and averaged. Finally, the probabilistic hierarchy is updated via backpropagation. formal description is given in App. C.7.
where c(z) is the number of leaves whose ancestor is Z, i.c. d(z) = Ev,ev 1 (xeanc()))) and p(z) and qzz) are two distributions induced by the edge and node distributions, i.e., (ii,,,,,PP(ss, Vy) and q(z) Ev.,, [[z=v,vv) P(,,) P(v,).((v) Dasgupta favors similar
p(z) = >v.,, leaves to have their lowest common ancestor low in the hierarchy [12]. TSD quantifies the ability to reconstruct the graph from the hierarchy in terms of information loss [8]. Hence, any hierarchy achieving good score provides a good compression of the original graph. In practice, both metrics good indicators of meaningful hierarchies [12, 8, 7]. Recently, Züggnrr al. [41] proposed the Flexible Probabilistic Hierarchy (FPH) method. FPH substitutes the indicator functions with their corresponding probabilities under the tree-sampling procedure (see App. A.1), obtaining cost functions for probabilistic hierarchies called Soft-Das and Soft-TSD, These two metrics correspond propose
the scores of the expected hierarchies under the tree-sampling procedure. In contrast, to optimize the expected metrics in this work. Intuitively, this corresponds to moving the expectation from inside the metric functions outside, reflecting the natural way of performing Monte- Carlo approximation via (tree-) sampling. More specifically, our objectives are:
min F [as( s.t. 7 (A.((T) and A.B
max E. (TSD(T)) s.t. 7 ~ PAB((T) A.B
(4)
which we denote Exp-Das and Exp-TSD. Note that we optimize over A and B, which parametrize a probabilistic hierarchy, while the edge weights are given by the dataset and used to compute the node and edge distribution. We show in Sec. 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 seeplinmling procedure. In Fig. 2, we show a simple case where Soft-Das does not align with the global optimal value, whereas Exp-Das does.
Note that while the Dasgupta cost favors binary branches [12], EPH and the probabilistic hierarchies are not limited to these. While binary hierarchies offer fine-grained clustering, non-binary hierarchies provide more flexibility by allowing nodes to have more than two children, which often aligns better with real- world clustering tasks.

---

Z3
Z3
Z4
VJ
Vi
V2
V3
V4
V1
V2
V3
V4
V1
V2
V3
Vi
(a) Graph
(b) minimizing hierarchy
(c) FPH
(d)
Figure 2: An example where FPH fails to infer a minimizing hierarchy. A hierarchy minimizing the Dasgupta cost and the inferred hierarchies by FPH and EPH the unweighted Ka graph, i.e., every normalized edge weight equal to 6. While FPH achieves a Dasgupta cost of 4.0 after discretization, the continuous hierarchy has Soft-Das score below 3.0. On the other hand, EPH finds minimizing hierarchy with a cost 10 A weighted example is shown Fig.
3.
4.2 Theoretical Analysis of EPH and FPH
The main motivation to use the expected metrics 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, as we show in Prop. 4.1.
Proposition 4.1. Let and B be transition matrices describing probabilistic hierarchy. Then, the following equalities hold:
min E ( A.B
min Das(T) and
max BT-PAB(T) [TSD(T)] max TSD(T). A.B
T
T
(5)
(See proof App. A.5)
Consequently, optimizing our cost function aims to find the optimal discrete hierarchy. Furthermore, we prove Prop. 4.2 that Soft-Das is a lower bound of Exp-Das, therefore its minimum is lower bound of the optimal discrete Dasgupta cost.
Proposition 4.2. Let and be transition matrices describing a probabilistic hierarchy. Then, Soft-Das Das will be lower than or equal to the expected Dasgupta cost under the tree-sampling procedure:
Soft-Das(T) (EAPPAB(T) (T)s
(6)
(See proof App. A.4)
In Fig. 2, we provide a specific example illustrating a case where the minimizer of Soft-Das is continuous, and FPH fails find the optimal hierarchy, i.e., obtaining minimal Dasgupta cost. We know an integral solution exists for EPH 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 Tab. 1, we provide an overview of properties of the cost functions of FPH and EPH.
Table I: Properties of Soft-Das, Exp-Das, Soft-TSD, and Exp-TSD.
Property
Problem Type
Convex/Concave
Integral
Optimal
Consistent
Soft-Das
Min.
Neither w.r.t. A and B (see F4g.14 (left))
x
x
Exp-Das
Min.
Neither w.r.t A and B (see A.p.A.6)
/
/
Soft-TSD
Max.
Convex w.r.t I.A probabilities [41]
/
/
Exp-TSD
Max.
/
/
4.3 Unbiased Computation of Expected Scores via Differentiable Sampling
In order to compute the expected scores, one could attempt to use a closed-form expression. To derive these for Exp-Das and EXp-TSD, however, we would need to calculate the probability p (z = V, A v,,z z E anc(v)) for which no known solution exists, and the expectation of a logarithm, respectively (see Eq. 13 and Eq. 14). An alternative to the closed-form solution is to approximate the
5

---

expectations via the Monte Carlo method. We propose to approximate Exp-Das and Exp-TSD with N differentiably sampled hierarchies {T(1, ,..., } (see "Loss computation" in Fig. 1):
Exp-Score (T)
Σ (core(F())
N
However, differentiable sampling of discrete structures like hierarchies is often complex. To this end, our differentiable hierarchy sampling algorithm consists of three steps integrating the tree-sampling Gumbel-Softmas estimator [20]: (1) We sample the parents of
procedure and the straight-throug the leaf nodes by interpreting the columns of as parameters of straight-through Gumbel-Softmax estimators. (2) We sample the parents of the internal nodes by interpreting the columns of B as 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 expectation 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 hicrarchics while providing gradients w.r.t A and B (see Fig. for overview).
Complexity. Since we sample N hierarchies from n' + -n-1 many categorical distributions with (nn)) classes, the sampling process can be done with a complexity of O(N x + +N x n²²). The dominating term is the computation of the Das and TSD scores with a complexity of O(N m x n²²) for graph datasets and O(N x n² x nt?) ) for vector datasets [41]. This is often efficient as we typically have n' < n and for graphs m & n². In Sec. 4.4, we propose a subgraph sampling approach to
reduce the complexity to O(N x M n² + n²) for large vector datasets, where M <n.
4.4 Scalable Expected Dasgupta Cost Computation via Subgraph Sampling
As discussed in the complexity analysis, the limiting factor is O(n² x n²)), corresponding to the evaluation of the Dasgupta cost, which becomes prohibitive for large datasets. To reduce the complexity, we propose unbiased subgraph sampling approach. First, we note that we can interpret the normalized similarities P(v:.V) as a probability mass function of a categorical distribution. This interpretation allows to rewrite the Dasgupta cost as expectation and approximate it via sampling procedure. More specifically,
M Σ
Das(T) = P( folv. Avyl R
cly AV
(8)
M
where (vv!), )........ (M) v () are M edges sampled from the edge distribution P(v., vz). which can be done O(M+ +2) [24]. We refer to this sampling approach as subgraph sampling (see Fig. 1). We can approximate the expected Dasgupta cost using the same procedure. In contrast to Exp- Das, Exp-TSD cannot be easily viewed as an expectation of edges, thus making the approximation via subgraph sampling impractical. However, since TSD is metric originally designed for graphs, which are generally sparse, it would yield little benefits.
Note that we end up with two different sampling procedures. First, we have the differentiable hierarchy sampling (see Eq. 7). This necessary to approximate the expectations. 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. 8), which interprets the Dasgupta cost as an expectation. This is done to reduce the computational overhead for vector datasets since the number of pairwise similarities grows quadratically in the number of data points. This estimation is unbiased and introduces an additional parameter, i.e., the number of sampled edges, which allows a trade-off between computational cost and quality. By inserting the probabilistic edge sampling approach into the tree sampling, we estimate Exp-Das to scale it to large vector datasets. An overview of our model is shown in Fig. 1, and a formal description is given in App. C.7.
In contrast to other approaches, the loss function of EPH is consistent with the discrete scores, meaning that probabilistic hierarchies with a better training score encode better discrete hierarchies. Following from Prop. 1. we know that any discrete hierarchy sampled from the optimal probabilistic hierarchy is optimal discrete hierarchy. While global optimality is not guaranteed, the training loss provides a reliable indicator of the discrete evaluation performance since the loss functions, Exp-Das and Exp-TSD, are computed on discrete hierarchies.

---

5 Experiments
5.1 Experimental Setup
Datasets. We evaluate our method on both graph and vector datasets. Graph datasets: We use the datasets Polblogs [1]. Brain [2], Citeseer [34], Genes []1], Cora-ML [25, 5], OpenFlight [29], WikiPhyssis [3], and DBLP [38]. To preprocess the graph, we first collect the largest connected component. Secondly, every edge is made bidirectional and unweighted. An overview of the graphs is shown in Tab. 7 in App. B.I. 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 [15]. Furthermore, we also use Cifar- 100 [23]. Digits and Cifar- 100 image datasets, the remaining
vector data. While we only flatten the images of Digits, we preprocess Cifar- 100 using the ResNet-101 101 BiT-M-RI0Ix by Kolesnikov et al. [22], which was pretrained on ImageNet-21k [13]. More specifically, we use the 2048 dimensional activations of the final layer for each image in Cifar- 100 as feature vectors. Furthermore, we normalize all features to have mean of zero and standard deviation of one. We compute cosine similarities between all pairs of data points using their normalized features. This results in dense similarity matrices. 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. 8 in App. B.1. Since we are in an unsupervised setting, we have no train/test split, i.c., we train and evaluate on the whole graph.
Baselines. We compare our model against both discrete and continuous approaches. For discrete approaches, we use the single, average, complete [18], and ward linkage [37] algorithms, respectively referred to as SL, AL, CL, and WL. We do not report the results of SL and CL on the graph datasets that do not have edge weights since these methods are not applicable unweighted graphs. In addition to the linkage algorithms, we also compare to the recursive sparsest cut (RSC) [12] and the Louvain method (Louv.) [4]. For continuous approaches, we use the gradient-basee optimization approaches Ultrametric Fitting (UF) [10]. Hyperbolical Hierarchical Clustering (HypHC) [7]. gradient- based Hyperbolic Hierarchical Clustering (gHHC) [28], and Flexible Probabilistic Hierarchy (FPH) [41]. While the linkage algorithms derive a hierarchy based on heuristics or local objectives, UF, HypHC, gHHC, and FPH aim to optimize a relaxed Dasgupta cost or TSD score. We set a time limit of 120 hours for all the methods and provided a budget of 5 512GB of memory for each experiment.
Practical Considerations. We repeat the randomized methods with five random seeds and report the best score of the discrete hierarchies. We use the same experimental setup as Zügner et al. [41], i.e., we use n' = 512 internal nodes, compress full hierarchies using the scheme presented by Charpentier and Bonald [8], and use WeepWalk embeddings [32] on the graphs for methods that require features. We train EPH using PAdamax (projected Adamax [21]), reduce the learning rate for B by a factor of 0.1 every 1000 epochs, and reset the probabilistic hierarchy to the so-far best discrete hierarchy. To approximate the expectation of EPH, we use 20 samples, except for Spambase, Letter, and Cifar- 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. edges. For the remaining datasets and during all validation steps, we use the whole graph. Both EPH and FPH are initialized using the average linkage algorithm. We train FPH with its original setting and our proposed scheduler and report the minimum of both for each dataset. For the remaining methods, we use the recommended hyperparameters. An overview of the hyperparameters and an ablation study in App. C.4. Finally, all methods are evaluated on discrete hierarchies. For EPH, we take the most likely edge for each node as explained in Sec. 3.
shown Tab. 10,
5.2 Results
Graph Dataset Results. We report the discrete Dasgupta costs and TSD scores for the graph datasets in Tab. 2. EPH achieves best scores across 13/16 settings and second- beest otherwise. In particular, EPH, which optimizes Exp-Das, consistently achieves better Dasgupta cost than FPH, which optimizes Soft-Das. This observation aligns with the theoretical advantages Exp-Das compared to Soft-Das (see Sec. 4.2). EPH and FPH, which both use the tree-sampling probabilistic framework, consistently achieve the best results. This underscores the effectiveness of tree sampling for hierarchical clustering.
Code available at
hierarchies
7

---

Nomallzed Dasgupta cost
2
10 Number of sampled hierarchies
Number sampled edges
Brain
Genes
Cora MLL
WikiPhysics
Zoo
Glass
Segmentation
Openhtight
Citeseer
Polblogs
Digits
Sparbbaese
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 mean of zero and standard deviation of one.
Table 2: Results for the graph datasets. Best scores in bold, second best underlined.
Daagupea cost (1)
Tre-simpling divergance (?)
Damseer
PelBI.
Reain
Cites.
Gienes
Ciea-MI.
OpenF
WikiP
DRLP
PolRI.
Brain
Cltes.
Genes
Com-MI.
OpenF:
WiLIP.
DRLP
338.52
567.90
301/68
660
50.59
AL.
355.61
556.68
83.09
196.50
292.77
363.41
65%.04
36, 26.463
25:25
2x.91
67.80
66.72
55.30)
52,012
43.15
38,99
Lows.
344.47
562.45
158.79
247.27
335.57
501.20
798.75
40,726
28.86
30,74
68.09
67.51
58.18
$2.97
47.01
41.40
RSC
907.70
526.17
85.41
188.82
264.62
367.36
630.51
0OM
28.04
20.19
67.39
66.28
96.14
$2.01
44 44.86
00M
UP
331.79
508.30
91.85
208.51
305.43
410.17
560.45
00M
21.77
24.19
60.13
59.45
68.42
47.64
42.37
00M
HypHC
519.96
02
594.23
675.45
7.26
26.82
PPI
238.65
125.
76,03
182.91
257.42
355.61
4R2
31,687
31.37
32.75
69.38
67.78
57.58
19.87
41.62
235.50
400.20
74.01
176.57
238.28
312.31
456.26
30,600
32.05
34.24
59.36
67.75
59.41
$7.83
50.23
42.74
Furthermore, the performance of the discrete approaches, i.e., the linkage algorithms WL and AL, the Louvain method, and RSC, is competitive with the other continuous methods, even though they use heuristics or local objectives to infer the hierarchies. The inferior performance of gHHC and HypHC can be intuitively explained by the fact that these methods were originally designed for vector datasets. WL, UF, and HypHC could not scale to DBLP within the memory budget, as they require the computation of dense n² similarity matrix, leading to out-of-memooe (OOM) issues.
Vector Dataset Results. We report the discrete Dasgupta costs of several methods on the vector datasets in Tab. 3. Consistent with the results on the graph datasets, EPH outperforms all baselines and achieves the best scores across 7/8 datasets. These results demonstrate the capacity of EPH to not only cluster graphs but also adapt vector datasets. Further, EPH consistently outperforms FPH. again emphasizing the benefit of optimizing expected scores over soft scores. contrast with graph datasets, HypHC performs competitively vector datasets. This is reasonable since this method was originally designed for vector datasets. FPH performs slightly worse than HypHC on most datasets and is only better on Iris.
Table 3: Dasgupta costs (L) for the vector datasets. Best
scores in bold, second best underlined.
Danset
7oe
fris
Glass
Dights
Segm.
5gam
Tutter
Cifrr
WL.
56.28
122.16
1126.77
1266.17
2062.60
32979
AL.
1121.68
57.67
70.71
126.33
1166.05
1368.21
3042.08
13166
CI.
55.78
70.10
123.02
1140.35
1277.48
2071 59
12396
33131
Louv.
56.26
72.31
125.94
1126.45
1238.35
2915.48
11946
32930
RSC
55.94
69.10
121.45
1119.43
1237.20
2917.07
11885
32907
UF
36.28
2998.17
slnC
1119.74
HYpAC:
56.05
1118.00
1253.07
38
HPH
36.13
09.13
122 DU
1152.84
1258.45
2953.56
12197
35224
FPH
55.77
69.10
120.94
1117.58
1230,60
2916.17
11894
32013
Hyperparameter Study. We show in Fig. (left) the effect of the number of sampled hierarchies on the EPH performances. On the one hand, we observe that a large number of sampled hierarchies (i.e., N > 20) generally yields better results than a small number of sampled hierarchies (i.e.. N < 10) except for Citeseer. Intuitively, a higher number of sampled hierarchies should lead to a more accurate expected score approximation. On the other hand, a very large number for sampled hierarchies (i.e., N 2 100) might not lead to sigmificant improvements while requiring more computational resources. Intuitively, the randomness induced by lower number of sampled hierarchies could be beneficial to escape local optima. In general, we found that 20 samples led to satisfactory results for all datasets, thus achieving good trade-off between approx accuracy, optimization noise, and computational requirements.
8

---

(a) Small HSBM- GT
(b) Small HSBM Exp-Das
(c) Small HSBM
EXp-TSD
(d) Large HSBM
(e) Large HSBM Exp-Das (I) Large HSBM Exp-TSD
Figure 4: Ground truth clusters and dendrograms compared to the inferred ones for the HSBMs.
Table 4: Results of EPH for the HSBMs with n'' = #Cluster.
Dusgupta cost ($)
Tree sampling divergence (?)
Method
HSBM Small
HSBM Large
HSBM Small
HSBM Large
26.29
43.14
EPII
26.19
121.08
43.56
51,53
Level
Normalized Mutual Information
Normalized Mutaal Information
1.0
1.0
Level 2.
1.0
1.0
1.0
1.0
Level
0.77
0.81
0.87
0.99
We show in Fig. (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 nyn shows significant performance improvement while going from nvT 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, use the whole graph, while for the other datasets, we sample n edges as trade-off between runtime and quality of the hierarchical clustering. We provide further experiments in Sec. C.4, including minimized version of EPH outperforming FPH in terms of runtime and results.
External Evaluation. As the Dasgupta cost and Tree-San Tree-Sampling Divergence are internal metrics and do not necessarily measure how closely a derived hierarchy aligns with an external ground truth, complement our unsupervised quantitative evaluation with an external evaluation. Given that ground-truth hierarchies are typically unavailable in real-world data, we evaluate EPH on synthetic graph datasets with known ground-trutt hierarchies. Additionally, we analyze to what extent the inferred hierarchies preserve the flat class labels for the vector datasets in Sec. C.3 in the appendix.
We augment the graph datasets with two hierarchical stochastic block models (HSBMs), which enables us compare the inferred hierarchy with the ground truth. As the HSBM graphs generated in stochastic process, the ground-truth hierarchy necessarily optimal terms of the Dasgupta cost or Free-Sampling Divergence. Furthermore, we compute the normalized mutual information (NMI) across the different levels of the hierarchies, and the cophenetic correlations for the shortest path distance (SPD) and the Euclidean distance of DeepWalk embeddings (see Tab. 4 and Tab. 5). We observe that EPH recovers the first three levels of the ground-truth hierarchy almost perfectly. Moreover, the inferred hierarchies by EPH obtain even better scores than the ground-truth hierarchies on the HSBMs, underlining the remarkable capacity of EPH to optimize the Dasgupta and TSD scores. Additionally, the TSD objective proves be a more suitable metric for recovering the ground-truth levels of the HSBM in terms of NMI. The cophenetic correlations observed between Exp Das and Exp-TSD are notably high
Table 5: Cophenetic correlations (1) of EPH for different distances on the HSBMs with n # Cluster.
Cophenetic Correlation (1)
Shortest path distance
DeepWalk Distance
Method
Small
Large
HSBM Small
Large
GT
0.77453 0.77174
0.67839
0.94001
0.90920
Exp-Das
0.67692
0.93973
ESD
0.77440
0.67838
0.94027
0.90922

---

and closely align with the ground truth, with Exp-TSD even surpassing the ground truth on Deep Walk distances. We attribute this to the fact that a minimal Dasgupta cost favors binary branches, which does not reflect the hierarchies of the HSBMs. Our visual analysis of the graphs and hierarchies (see Fig. 4) confirms this observation. Additional results for FPH are provided in App. C.I.
Qualitative Evaluation. We visualize the largest cluster inferred on Cifar-100 using EPH. More specifically, we select the internal nodes with the most directly connected leaves. Additionally, we sort the images by their probability, i... their entry in the matrix A. We show the 16 images with the highest probability and the 16 with the lowest probability for the largest cluster in Fig. 5. We observe that the images with high probabilities are all similar and related to insects. This shows that EPH is
(b) Lowest Probability Figure 5: Largest derived cluster on Cifar- 100. able to group similar images together. contrast, the last images with the lowest probability do not fit into the group. This demonstrates the capacity of EPH to measure the uncertainty in the cluster assignments. We provide additional results with the same behavior for other clusters in App. C.2 (see Fig. 9. Fig. 10, and Fig. 11). Furthermore,
(a) Highest Probability
visualize the graph and inferred hierarchies of EPH for OpenFlight in Fig. 12 in the appendix. Both minimizing Exp-Das and Exp-TSD generate reasonable clusters and successfully distinguish different world regions. Finally, we visualize the ground truth classes and clusters of selected vector datasets in Fig. 13.
Discussion
Limitations. While the Gumbel-Softmar estimators of the expectations unbiased in the forward pass, the estimation the gradients is not [31] and thus impacts the EPH optimization. Furthermore, though the global optimal values of the expected and discrete scores match, EPH does not guarantee convergence into a global optimum when optimizing using gradient descent methods.
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 Tree-Sampling Divergence using disferentiable hierarchy sampling. We show that the global optima of the expected scores are equal to their discrete counterparts. Furthermore, we present an unbiased subgruph sampling approach to scale EPH to large datasets. We demonstrate the capacity of our model by evaluating on several synthetic and real-world datasets. EPH outperforms traditional and recent ofate-of-the-art baselines.
References
[1] Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop Link discovery, pages 36-43, 2005.
[2] Katrin Amunts, Claude Lepage, Louis Borgeat, Hartmut Mohlberg, Timo Dickscheid, Marc- Étienne Rousseau, Sebastian Bludau, Pierre-Louis Bazin, Lindsay B Lewis, Ana-Maria Oros- Peusquens, et al. Bighrain: an ultrahigh-resolution 3d human brain model. Science, 340(6139): 1472-1475, 2013.
[3] Nicolas Aspert, Volodymyr Miz, Benjamin Ricaud, and Pierre Vandergheynst. A graph- structured dataset for wikipedia research. In Companion Proceedings of The 2019 World Wide Web Conference, pages 1188 1193, 2019.
[4] Vincent D Blondel, Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P1000))) 2008
[5] Aleksandar Bojchevski and Stephan Günnemann. Bayesian robust attributed graph clustering: Joint learning of partial anomalies and group structure, Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
10

---

[6] Aleksandar Bojchevski, Oleksandr Shchur. Daniel Zügner. and Stephan Günnemann. Netgan: Generating graphs via random walks. In International conference on machine learning, pages 610-619, PMLR, 2018.
[7] Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering. Advances in Neural Information Processing Systems. 33:15065-15076, 2020.
[8] Bertrand Charpentier and Thomas Bonald. Tree sampling divergence: an information-theeorticc metric for hierarchical graph clustering. In IJCAI-19, 2019.
[9] Bertrand Charpentier, Simon Kibler, and Stephan Günnemann. Differentiable dag sampling. arXiv preprint arXiv:2203.088. 203008809 2022.
[10] Giovanni Chierchia and Benjamin Perret. Ultrametric fitting by gradient descent. Advances in neural information processing systems, 32, 2019.
[11] Ara Cho, Junha Shin, Sohyun Hwang, Chanyoung Kim, Hongseok Shim, Hyojin Kim, Han- hae Kim, and Insuk Lee. Wormnet v3: a detwork-assister hypothesis hypothesii-generating server for caenorhabditis elegans. Nucleic acids research, 42(W M1WWW6662222 2014.
[12] Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In Proceedings of the firtt- annual ACM symposium on Theory of Computing, pages 118-127, 2016.
[13] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognilion, pages 248-255. lece, 2009.
[14] Laxman Dhulipala, David Eisenstat, Jakub Lacki, Vahab Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in poly-logarithmic depth. Advances Neural Information Processing Systems, 11-22925-22944 2022.
[15] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://///rr ics. uci. cdu/ml.
[16] Michael B Eisen, Paul Spellman, Patrick O Brown, and David Botstein. Cluster analysis and display of genome-wiee wide expression patterss. Proceedings of the National Academy of Sciences, 95(25):14863-144 14868, 1998.
[17] Joseph Felsenstein. Inferring phylogenies, volume 2. Sinauer associates Sunderland, MA, 2004.
[18] 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.
[19] Katherine A Heller and Zoubin Ghahramani. Bayesian hierarchical clustering. In Proceedings of the 22nd international conference on Machine learning, pages 297-304, 2005.
[20] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv: /6///////111 /44, 2016.
[21] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[22] Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In European conference on computer vision, pages 491-507. Springer, 2020.
[23] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[24] Richard A. Kronmal and Arthur V. Peterson. On the alias method for generating random variables from discrete distribution. The American Statistician, 33(4):214-218, 2022/09/29/ 1979. ISSN 00031305, doi: 10.2307/2683739. Full publication date: Nov., 1979.
11

---

[25] 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.
[26] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permuta- tions with gumbel-sinkhen sinkhor networks. arXiv preprint arXiv:/802.08665 2018.
[27] Nicholas Monath, Ari Kobren, Akshay Krishnamurthy, and Andrew McCallum. Gradient-base hierarchical clustering. In 31st Conference neural information processing systems (NIPS 2017), Long Beach, CA, USA, 2017.
[28] 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, pages 714-722, 2019.
[29] Jani Patokallio. Openftights. URL https::/openfllgghhet org/-
[30] 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.
[31] Max B Paulus, Chris J. Maddison, and Andreas Krause. Rao-blackwellizingg the straight-through gumbel-softmax gradient estimator. In International Conference Learning Representations, 2021.
[32] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[33] Erzsébet Ravasz and Albert-László Barabási. Hierarchical organization in complex networks Physical review E, 67(2):0261 12, 2003.
[34] 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.
[35] Michael Steinbach, George Karypis, and Vipin Kumar. A comparison of document clustering techniques. 2000.
[36] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (11). 2008
[37] Joe Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American stutistical association, 58(301):2362444 1963.
[38] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based ground-truth. Knowledge and Information Systems, 42(1):181-213, 2015.
[39] 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, pages 243-252, 2014.
[40] Sheng Zhou, Hongjia Xu, Zhuonan Zheng, Jiawei Chen, Jiajun Bu, Jia Wu, Xin Wang, Wenwu Zhu, Martin Ester, al. A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. arXiv preprint arXiv:2206.0753 2022.
[41] 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 Learning Representations, 2022.
12

---

A Appendix
A.1 Equations of Soft-Das and SoDt-TSD
In the following, we show the equations of Soft-Das and Soft-TSI>.
Soft-Das(T)= = Σ
P(vi, vj)
Σ EEP
p(z= v. A pz) anc(v))
(9)
VivjEV
7EZ
p(z)
Soft-TSD(T) Σ p(z) log
(10)
g(z)
where p(z)
Σ P( ((y.v)))(=-vAAy)
(11)
V.NyEV
((2) = Σ
Pw))((y)p(==AAv)
(12)
A.2
Closed Form Solutions of Exp-Das and Exp-TSD
To compute flosed-form solutions of the expectations, the following equations need to be solved:
Exp-Das(T) = Σ P(v., v2)
pE A vj,2 anc(v))
(13)
Vi,SEV
VEV
p(z) log p(z)
EXp-TSD(T) = Σ
BTTPAB(T=(ABB) E
(14)
g(z)
A.3 Relation between Joint and Independent LCA and Ancestor Probabilities
While the LCA probabilities crucial to compute Soft-Das, Exp-Das requires the joint LCA and ancestor probabilities, i.e. p(zz = v; A V,, E (zz)), for the leaves v,, Vj and v and the internal node Za. In Prop. A.1, we show that the joint probabilities are upper bound of the product of the single terms.
Zk
7k
7
Vi
Va
Vi
(a) ret and ret meet at node
(b) rith and rit meet at node zur-
(c) r rvj and rég meet at node 7k-
Figure 6: The different cases of the event p (Z+ vi A E anc(v)). While the LCA of v and V2 is 2ą in every case, the LCA of vı and v and the LCA of V2 and v are different. We have three cases: either the paths from paths meet for the first time at Z (shown in fig. (c)).
V2 and meet before 24 node z (shown in (a) and (b)), or all
Proposition A.I. Let describe the probability under the tree-sampling procedure, an internal node, V1, V2, and v leaves. Then, the following inequality holds:
plzz v v2)p anc(v)) S p (Zz vi A V2, Zz anc(v))
(15)
Proof. First, we observe that the right-hand side of the inequality can be rewritten as:
p (Zz A V2, Zạ anc(v)) p(z A 2 anc(v)) p(zz anc(v)).
(16)
13

---

To prove the non-trivial case (zy: E anc(v)) * 0, we need to show that the following holds:
p A v2) - [2 V1 A Z E anc(v)).
(17)
Let r (Ve...., , 23) denote path from a leaf v, to an internal node 2, and let Za be the root node. Recalling from [41] that the paired path probability under the tree-sampling procedure is
p((r r()))) (((t, (p(r2)))
(18)
with 2 = V1 A V2, rewrite the LCA probabilities
p v1 A12
Σ
(19)
Adding the condition 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 rij and r 7 for the first time, or the path meets the path ri: or r2 in lower node Za,, with k' < 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 the node Zgz. The probability for the path ri,, is equal to since we know that Z E anc(v). More formally, the conditional probability
p (za = VI Av2 2a anc(v))
Σ
p(rt
Zz E anc(v))p((ft Zu E anc(v)).
(20)
Assuming that the path from to Zạ meets the path from V1 to Z in the node 2 with W s k, we have
p(r Z anc(v))p(r?) Zz E ann(vv) = p )e( p(((t)
(21)
The last inequality follows since r is a subpath of r and therefore has a higher probability. This concludes the proof.
A.4 Proof of Proposition 4.2
In the following, we provide the proof of the inequality shown in Prop. 4.2.
Proof. To prove it, we first write out the definitions of Soft-Das and the expected Dasgupta cost.
Soft-Das(T) Σ
P(v1, V2)
ΣΣ P(z= vi Av E(ncev)))
(22)
v1.22
and
E E
[as(TT)
Σ P(v1,V2) V2)
ΣΣ I 1/z [peane())
(23)
Lii.2
BAmPA.B(T)
Σ P(v..V2)
ΣΣ I|==i
(24)
V2.22
Σ P(V1, v2)
ΣΣ E E+-PANIT) [
(25)
V1.22
Σ P(vi, v2)
ΣΣ P(z= Vi 22, Enc(y)))
(26)
V1.92
The proof follows by using Prop. A.I.
A.5 Proof of Proposition 4.1
Here provide the proof of Prop. 4.1.
14

---

Proof. To prove the left-hand side, we first observe that the expected Dasgupta cost can be rewritten as convex combination of the Dasgupta costs of all possible hierarchies under the tree-sampling procedure. More formally,
B P(TTT)( [Das(T)]
E
PA,B(T)Das(h
(27)
TEH(O,N")
where H(n, n²) describes the set of all valid hierarchies with leaves and n' internal nodes. Thus, the minimizer of the expected Dasgupta cost is a convex combination of all minimizing hierarchies, with the minimum being equal the optimal Dasgupta cost. The equation the right-hand side for TSD can be proved equivalently.
Note that since the expectation operator is convex, any discrete optimizer (i.c., 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 are represented by deterministic A, B matrices. Only probabilistic hierarchies, which are optimizers of the expected scores, described by non-discrete A and matrices, are not optimizers of the discrete scores. This is expected since those probabilistic hierarchies do not belong the valid input domain of the discrete scores. In addition, any sample we draw from these probabilistic optimizers is also a discrete optimizer Dasgupta or TSD because of the convexity of the expectation operator.
A.6 Non-Convexity and Non-Concavity of Exp-Das
Minimizing convex function using gradient descent is easier than concave one. Minimizing concave function heavily depends on the initialization in a constrained setting, Exp-Das(T = (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 training. To show that Exp-Das is not concave, is sufficient to find two hierarchies Ti = (A1, B1) and Th = (A2, B2) such that:
1 (
Exp-Das(Th
Exp-Das((7) 2 Exp-Dat Das
(28)
and equivalently to show that it is not convex:
1 J Exp Exp-Das(TTy + _ Exp-Das(Ta) s Exp-Das
( +T1+TT)) (1(T7++)))
(29)
where Ti + T (A1 + A2, Bi B2). In Fig. 7, we show these two examples. In (a) and (b). we show two hierarchies, and (c), linear interpolation of these two. The graph in (d) satisfies Eq. 28, while the graph in (e) satisfies Eq. 29. We report the Dasgupta costs for all hierarchy and graph combinations in Tab.
Table 6: Dasgupta costs for all combinations of hierarchies and graphs from Fig. 7.
Hierarchy
fi
12
Ti
Convex Example
3.5
3,5
3.375
Concave Example
3.0
3.0
3.25
A.7 Weighted Failing Soft-Das Example
addition to the example in Fig. 2, we show a weighted graph where FPH fails to find the minimizing hierarchy in Fig. 8.
15

---

73
73
21
42
Z1
42
21
22
(a) Fi (Á1, B1)
(b) Tz
(Áz, B₂)
(c) Ti
0.5
+
0.5
T2
V2
12
V8
VA
Convex Example
Concave Example
Figure 7: Three hierarchies and two graphs that show that Exp-Das neither convex nor concave with respect to A and B. The hierarchy in (c) is linear interpolation of the hierarchies in (a) and (b). The graphs in (d) and (e) are examleee with convex and concave behavior, respectively.
73
V2
Zn
Z1
V2
22
71
Va
74
Va
R
Y4
V3
(a) Ka Graph
(b) minimizing hierarchy
(c) FPH
(d) EPH
Figure 8: An example of weighted K4 graph where FPH fails to infer minimizing hierarchy. While FPH achieves a Dasgupta cost of after discretization, the continuous hierarchy has a Soft-Das score below 3.0. On the other hand, EPH finds a minimizing hierarchy with cost of 3.0.
16

---

B Experiments Information
B.1 Datasets
An overview of the graph and vector datasets is given in Tab. 7 and Tab. 8. The details of the HSBMs shown Tab. 9.
Table Overview the graph datasets.
Dataset
Number Nodes
Number Edges
License
PolBlogs
1222
16715
n/a
Brain
1770
8957
a/á
Citeweer
2110
3694
n/a
Genes
2194
2688
n/a
Openflight
3097
18193
OBdl.
WikiPhysics
DBLP
317080
1049866
n/a
Table 8: Overview of the vector datasets.
Dataset
Number of Data Points
Number of Attributes
Number of Classes
License
Zoe
101
CC BY
Iris
150
CCBY 4,0
BY
Digits
1797
8x8
10
CC BY 4,0
Segmentation
2310
BY
Spambase
4601
57
CC BY 4.0
Letier
20000
CC BY
Cifar-100 100
50000
2048
100
n/a
Table Overview the HSBMs.
Dataset
Number Nodes
Number Edges
Number Clusters
Large HSBM
1186
27028
53
17

---

B.2 Hyperparameters
We show an overview of the hyperparameters we used Tab. 10. Furthermore, we compare the original FPH results with the tuned results, ie., the minimum of the original, and using the aforementioned scheduler in Tab. 11.
Table 10: Overview of the Hyperparameters.
Method
Hyperparameter
Value
LR Initialization Samples Num. Samples'
Scheduler Average Linkage 20
ВPH
10
Num. Samples
LR LR
Schedulerr, 0.05)
FPH
min (Scheduler, 150}
Inirialization Epochs
Avenge Linkage
1000
min(le
1e-4)
le
Temp
min(le
1. 5e 2.
le
HypHC
LR
le-3
Temp.
le
Epochns
50
Num. Triplcts
n²
Loss LR Epochs
min Dasgupta, Closeat+Size)
UF
0.1
500
LRA (Exp-Das)
0.1
LR (Exp-Das) *...
0.05
LR Das)
Scheduler
LR (Exp-Das)
0.01
LR (Exp-ISD)
150
LR (Exp-TTDD)
Sampling frequency
1000
Sampling frequency
2000
Epochs (Exp.
Epochs (Exp-TSD)
3000
Embedking Dim. Embedding Dim.
10
DeepWalk
32
Used for DBLP and Spambase
Used for Letter and Cifar-100
*** Used for Letter
Used for Cifar-100
Used for DBLP
Table 11: Dasgupta costs the original FPH (orig.) and with our modifications (tuned). Improve- ments are highlighted in bold.
Dasgapta cost
Tree-sampling divergence
Tattsee
PoIBt
Brain
Cites.
Genes
Cata-MI.
OpenF:
WikiP
DRLP
PolBI.
Brain
Cites.
Gienes
Com-MI.
OpenE:
WiLiP.
DRI P
(orig.)
262
183.63
257-42
355.61
937.95
31,687
31.37
$8.02
(tuned)
257.42
31,687
18

---

C
Additional Results
C.1 HSBM Results for FPH
We show the results for FPH the HSBM graphs in Tab 12.
Table 12: Results of FPH for the HSBMs with n'=# Cluster.
Dasgupia cost
Tree sampling divergence
Metbod
HSBM Small
HSBM Large
HSBM Small
Large
GT
130.16
$1.50
FPH
27.84
127.99
43.53
51.53
Level
Level
1.0
0.95
1.0
1.0
Level
C.2 Additional Visualizations
We show the largest clusters for the Digits and Cifar 100 datasets in Fig. 9, Fig. 10, and Fig. 11. We observe that EPH provides qualitatively reasonable clusters and groups similar images.
3
0
(a) Largest Cluster
(b) Second Largest Cluster
5
(c) Third Largest Cluster
(d) Fourth Largest Cluster
Figure 9: Largest derived clusters on Digits. On the left in each subplot the 16 images with the highest probability, the right the 16 images with the lowest probability.
(b) Lowest Probability Figure 10: Second largest derived cluster on Cifar-
(a) Highest Probability
Additionally, provide visualization of the OpenFlight dataset in Fig. 12, showing that both Exp-Das and Exp-TSD yield meaningful hierarchies and clusters. Finally, we apply 1-SNE [36] to selected datascts and compare the ground-truth labels with clusters inferred by EPH in Fig. 13.
19

---

(a) Highest Probability
(b) Lowest Probability
Figure 11: Third largest derived cluster on Cifar-100
(a) Das clusters
(b) TSD 64 clusters
Figure 12:
Inferred clusters inferred by EPH optimizing Exp-Das and Exp-TSD, 64 clusters are highlighted in the graphs and dendrograms.
C.3 Additional External Evaluation
In addition to the unsupervised metrics, we investigate whether the inferred hierarchies on the vector datasets preserve the flat ground truth class labels. To do this, flatten the derived hierarchies and compare inferred clusters with the available ground-truth labels by applying the Hungarian algorithm align the cluster assignments with the labels, as explained by Zhou al. [40]. Using this procedure, we compute the accuracies, shown in Tab. 13. While the linkage algorithms were inferior the continuous optimization algorithms terms of Dasgupta cost, they dominate here. EPH, trained on 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 to minimize the Dasgupta cost, the results are not surprising since the Dasgupta cost and other metrics do necessarily go hand in hand.
C.4 Ablation
For our ablation study, we use simplified optimization scheme. More specifically, we use fixed learning rate of 0.05 and only train for 1000 epochs.
20

---

(a) Zoo
(b) Iris
(c) Digits
602
(d) Segmentation
(e) Spambase
Figure 13: Ground truth clusters (left) compared to inferred flattened clusters (middle) and den- drograms (right) of EPH for the datasets Zoo, Iris, Digits, Segmentation, and Spambase with n' min(n 112] internal nodes after applying the t-SNE algorithm.
21

---

Interpol ation
Exp Interpolation
1.0
Neraaized Soft-Das
8
2.5
0.6
2.0
200
1.5
0.2
Norm
-.22
0.5
-0.4
0.0
0.0
1.0
0.0
Factor
Factor
Brain
Openflight
Polblogs
WikiPhysics
Figure 14: Linear interpolation of Soft-Das and Exp-Das scores from the average linkage hierarchy the hierarchy inferred by Exp-Das.
Table 13: Accuracies for the vector datasets. Best scores in bold, second best underlined.
Iris
Digits
Segm.
Spam.
Cilar
WL
0.74
0.76
0.44
0.82
0.61
0.76
0.33
0.49
AL 0.80
0.82
0.43
0.65
0.48
0.82
0.31
0.16
SL
0.84
0.67
0.37
0.10
0.15
0.61
0.04
0.01
0.81
0.33
Louv.
0.50
0.83
0.42
0.68
0.29
0,86
0.18
0.05
UF
0.60
0.55
0.43
0.43
0.54
0.54
0.04
0OM
gHHC
0.59
0.71
0.42
0,51
0.30
0.69
0.08
0.11
TyylII
0.79
0.82
0.52
0.42
0.29
0.10
0OM
FPH
0.58
0.83
0.40
0.20
0.44
0.61
0.06
0.03
Constrained vs. Unconstrained Optimization. We require the rows of the matrices and to be row-stochastic. There are several possibilities to enforce this. Either can perform constrained optimization using projections onto the probabilistic simplex or perform softmax operation over the rows. In Tab. 14, compare the Dasgupta costs the graph datasets for several graph datasets. We can observe that the constrained optimization.ice. using projections after each step, yields better
Table 14: Dasgupta costs for constrained and unconstrained optimization several graph datasets with n' 512 internal nodes.
Dataset
PolBlogs
Brain
Citeseer
Genes
Cora-ML
OpenFlight
WikiPhysics
Constrained
252.55
74.84
242.38 269.10
324.45 349.20
481.92
Unconstrained
272.60
457.62
79.47
188.02
526.99
results than the unconstrained optimization on every graph. This aligns with the findings of Zügner et al. [41]. Therefore, we recommend using constrained optimization.
Initialization. The initialization of model can play a crucial role. Zügner al. [41] found that using the AL algorithm as initialization yields substantial improvements. Therefore, we compare both initializations and additionally test using their algorithm FPH initialization. We show the Dasgupta costs for several graph datasets in Tab. 15. As expected, using the AI. algorithm or FPH
Table 15: Dasgupta costs for different initializations on 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 bold, second best underlined.
Dataset
PolBBlogs
Brain
Citeseer
Genes
Cora-ML
Openttight
WikiPhysics
Random
914.11
1285.68
1574.76
1621.82
2107.65
2302.13
2479.51
AT.
355.60
$56.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)
564.35
624.27
Exp Das (AL)
252.55
428.40
74.84
178.90
242.87
324.45
481.92
Exp- Das (FPHT)
251.55
431.15
74.88
177.32
245.79
326.46
$27.02
22

---

as initialization yields significant improvements over a random initialization. Even though the FPH initialization starts with better hierarchy, the resulting hierarchies are inferior to the AL initialization. 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. We perform a softmax operation with an additional learnable temperature parameter i; to infer A and B over the cosine similarities between the embeddings. The main advantage of the embedding approach is that, in addition the hierarchical clustering, we gain node embeddings that can be used for downstream tasks such as classification or regression. We test the embedding parametrization with d = 128 on several graph datasets. Once we let 4 be learnable, and once we freeze to 1, 1. We compare the results to the constrained optimiza- tion. While we train the direct parametrization for 1000 epochs, the embedding approach is trained for 20000 epochs. This is done to ensure convergence since it is randomly initialized. We show the results in Tab. 16. First, we observe that not using temperature parameter yields substantially worse
Table 16: 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
Citesear
Gones
Cora-MI.
OpenFlight
WikiPhysies
252.55
428.40
178.90
242.38
324.45 968. 41
Emberdiing (t; 1)
451.63
659.11
1008.23
I 1146.86
1261.91
108.42
Embedding
249.84
440.29
213.99
290.19
409.68
373.07
514.91
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. Ouly on the dataset PolBlogs the embedding approach is slightly better than the direct parametrization. We attribute the inferior performance 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. [41]. They also parametrized their model using embeddings and used the softmax function on the negative Euclidean distances to infer the matrices A and B. Since the embedding approach yields worse results with longer training times, 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 a higher computational cost. To select the hyperparameter n', we test various choices on several datasets. We show the corresponding Dasgupta costs and TSD scores in Fig. 15 and Fig. 16. We found that n' = 512 is sufficient to capture most information. In practice, we recommend using the Elbow method.
230
242
300
233
202
500
Figure 15: Dasgupta costs for different numbers of internal nodes.
Toklog
Dosh
30
10
2254
225
725
10-
TP
Figure 16: TSD scores for different numbers of internal nodes.
23

---

Number of Sampled Hierarchies. Another crucial hyperparameter for EPH is the number of sampled hierarchies. Additionally Fig. 3, we provide the raw Dasgupta costs and standard errors after the training in Fig. 17. Furthermore, we show the influence of the number of samples to approximate the expected Dasgupta cost on randomly initialized hierarchies in Fig. 18.
Opanf Bhe
Gona
38C
X00
301
100
200
30
320
200
15
20
232
Numbor carplihhie
50 100 200
Crnin
Pelrggs
Wilhhard
560
406
c40
ump hiaurdio
Nunoor starpied
Figure 17: Dasgupta costs and standard error for different numbers of sampled hierarchies after the EPH training.
Crro
Withyata
2220
2457
2403
3225
1.54
1200
2447
3457
Rumber distkkccooocooo
Number Hovrdho
10
320
200
Numoor hearcci
15 20
Tumber harplotheracche
Figure 18: Approximated Expected Dasgupta costs for different numbers of sampled hierarchies for randomly initialized probabilistic hierarchies.
To reduce EPH's runtime, introduce minimized version of our algorithm that samples a single hierarchy and omits validation steps. The final hierarchy selected on the training loss, enabled by the alignment between expected and discrete scores. We compare this minimized version to the original and FPH on the graph datasets in Tab. 17, with all methods trained using the original setup described in Sec. 5.
Minimized Version.
Table 17: Results of the minimized version of EPH for the graph datasets. Best scores in bold, second best underlined.
Dasgupto
Tree sampling divergence
Datascl
CunsMI.
OpenR:
CosssML
OpeaF
DELP
FPH EPP
238.65
425.70
76.03
182.91
257.42
355.61
483
31.687
31.37
32.75
69.35
67.7%
59.55
57.58
49.87
41.62
235.50
460.20
14.01
176.02
238.78
112.31
456.26
30,606
32,86
11.24
69. 36
67.75
59.41
$7.61
50.23
42.74
FIPH (miniiizad)
216.86
404
72
173.56
238.11
309.33
453.63
30.644
31.92
34.36
09
67,88
59.54
57.92
50.19
42.70
Our minimized version outperforms FPH in 14 out of 16 cases while achieving a shorter runtime, as shown Tab. 20.
C.5
Standard Deviations
We show the standard deviations of the randomized models on the graph datasets in Tab. 18 and for the vector datasets in Tab. 19.
C.6 Runtimes
We report the runtimes for EPH and the baselines Tab. 20 and Tab. 21. While HypHC, FPH, and EPH are executed on GPU (NVIDIA A100), the remaining methods do not support or do not require GPU acceleration. Since gHHC has lower computational runtime than the other randomized methods, run with 50 random seeds instead of 5,

---

Table 18: Standard Deviations for the graph datasets.
Dasgupt cost
Tree-sampling divergence
Dutaset
PolBI.
Brain
Cites.
Genes
Cora-ML ML.
OpenI:
WikiP.
DBLP
PulBI.
Brain
Cites.
Genes
Cora-ML
OpenI:
WikiP
DBLP
HyplIC
6.37
9.05
22.93
16.34
51.74
28.83
36.64
00M
0.47
0.64
0.71
0.35
1.47
1.02
1.22
OOM
RPH
0.43
1.31
0.10
2,17
1.02
2,49
2.98
35.89
0.31
0.39
0.01
0.07
0.02
0.12
0.15
0.03
Table 19: Standard Deviations for the vector datasets.
Dasgupta cosl
Accuracy Segmentation
Dataset
Zoo
Glass
Digits
Segmentation
Spambase
Letter
Cifar
Zoo
Glass
Digits
Spamhase
Letter
Cifar
HypHC
0.08
0.58
0.27
1,57
0.46
2,04
45,10
0OM
0.05
0.01
0.05
0.07
0.06
<0.01
0.01
0OM
0.04
0.01
C.7
Pseudocodes
In the following, we provide formal description of our EPH algorithm, the subgraph sampling, and how we normalize graphs.
Algorithm NormalizeGraph
Algorithm EPH
Input: (V,F), Graph P(v;, Vj) 5- Livev Way
Input: G (V, E): Graph
Wh.3
Input: =
(A, (A, Initial hierarchy
P(v.) t Σ, W3
28
Input: Learning rate
Input: K: Number of sampled hicrarchies
for I. 1,... do
Algorithm SampleSuggraph
Jt <-
Input: G GV, Graph
for 1,.... K do
Input: M: Number of sampled edges
9 SampleSubgraph(() T PA.B(T)
È < MultiSet() //allow duplicate edges
for -...M do
9t + 9t + Scorer, 7) end for
e e= (v;, P(v., Vz)
E.add
T - T--1 g + P(Te)
end for G - (V, E)
//simplex projection
end for return Te
NormalizeGraphhG)
return
25

---

Table Runtime seconds the graph datasets with n' 512 internal nodes.
PolBlogs
Brain
Citeseer
Genes
Cora-ML
OpenFlight
WikiPhysies
DBLP
Nodes Edges
1222
1770
2110
2194
2810 7981
3097 18193
3309
317080
16715
8957
3694
2688
31251
1049866
WL
<1
<1
<1
<1
0OM
AL
<1
101
Louv.
1031
RSC
92
78
104
427
280
626
863
0OM
şHHC
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
EPII
1496
1066
749
1196
1654
224331
EPH (minimized)
111
100
85
116
157
4160
Table 21: Runtime seconds for the vector datasets with min h 512) internal nodes.
Zoa
Iris
Glass
Digits
Segmentation
Spambase
Letter
Cifar: 100
Points
101
1797
2310
4601
20000
50000
WL
<1
983
8316
AL
<1
<1
<1
S1
985
8564
SL.
<1
<1
<11
51
975
8494
<11
52
986
8594
Louv:
<1
<1
<11
55
1065
7324
UF
<11
<1
<I
14
57
1132
OOM
gHHC
47
89
110
8462
HyplIC
47
3385
5814
26933
250792
OOM
FPH
87
144
2586
3963
13876
134845
427557
EPH
445
6645
19974
130227
430322
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract accurately describes the contributions and claims of the paper. The methodology is explained in Sec. 4, and theoretical properties and methodology shown and discussed in Sec. 4.2. Our subgraph sampling approach discussed in Sec. 4.4. The results the graph and vector datasets are presented in Sec. 5.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations discussed in Sec. 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
27

---

Answer: [Yes]
Justification: All theoretical results include assumptions and proofs and are presented in App. A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification; All training details and hyperparameters are disclosed. We provide all hyperpa- rameters in Tab. 10, pscudeocodes in Alg. and Alg. 3, and explain the experimental setup
in Sec. 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
28

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
The project page of EPH is attached and the datasets (except the synthetic HSBMs) are publicly available. The baselines not attached since these are all publicly available. Furthermore, the submitted code includes information about the environment used for the experiments.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
sitiiiiisisiccc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. wttccc//pplllcc gwwhc//gguee///eee /ooo//eodimssseeeeeeeeeeee httil////uuidessodeeubbbiiiiii sessssssooooooo onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details are provided in Sec. 5.1 and Tab. 10.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Standard deviations of our experiments are provided in Tab. 18 and Tab. 19. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
29

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Machine and runtimes are stated in Sec. C.6.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://neuts h/tppris//////pp./// cc Caablic/Ethicstiie
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and ensured that the paper is conform with the code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper proposes hierarchical clustering algorithm for graphs and vector data. There are no no broader societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
30

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The proposed models do not pose risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The licenses of the used datasets shown in Tab. and Tab. 8, Furthermore, all basclines and methods are cited accordingly.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
31

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All hyperparameters shown in Tab. 10, pseudeocodes in Alg. 1 and Alg. 3, and the experimental setup is explained in Sec. 5.1
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
32

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "x6Kupu74a0", "reviewer": "Reviewer_xKdT", "summary": "The paper builds on a previous work [40] for probabilistic hierarchical clustering.  Instead of using the “soft” version of Dasgupta cost and Tree-Sampling Divergence in the objective function, the paper proposes to use the expected value of the two cost functions and develops a sampling method for calculating the expected value of the cost functions.  The proposed cost functions have been shown to have some interesting theoretical properties and better empirical clustering performance compared to the previous work.", "questions": "* Can we find the discrete hierarchy that gives the optimal Das or TSD after getting the probabilistic hierarchy with the optimal Exp-Das or Exp-TSD?\n* Section 4.3 says that \"we can use a closed-form expression\", but then it says \"no known solution exists\".  Do you have a closed-form expression of Exp-Das and Exp-TSD?  If so, why don't you use it instead of the sampling method?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper includes theoretical analysis of the proposed Exp-Das and Exp-TSD.  It shows the optimal value of those cost functions for the probabilistic hierarchy is equivalent to the optimal value of their counter-parts (i.e. Das and TSD) for the discrete hierarchy.  It further shows that the Soft-Exp is only a lower bound of Exp-Das and thus less ideal for use to find the hierarchy with optimal Das.\n* The experiments include reasonable number of baseline methods and datasets.  The proposed method EPH is shown to be empirically better than the FPH proposed in the previous work [40].\n* The presentation is satisfactory and the paper is easy to follow.\n* The code of the proposed method is/will be publicly available.", "weaknesses": "* The presentation of the paper and the proposed hierarchical clustering solutions closely resemble a previous work [40] that proposes the generalisation of probabilistic hierarchy and the cost functions Soft-Das and Soft-TSD.  The current paper proposes Exp-Das and Exp-TSD to replace the Soft-Das and Soft-TSD.  The contribution looks incremental in this sense, even with some interesting and nicer theoretical properties over the previous work.\n* The proposed method EPH looks only slightly better than the previous method FPH in the experiments.  The improvement of EPH over FPH is not as significant as that over other baseline methods.\n* The proposed solution may not converge to global optimum of Exp-Das nor Exp-TSD.  This makes the theoretical results less relevant as it is not guaranteed to reach global optimum anyway.  This may also explain why the empirical performance is not markedly better than the previous work.\n* Only the best score of the hierarchies resulting from five random initialisation is reported in the experiments.  It is hard to know how much variance there would be for the performance due to the random initialisation and whether the proposed method EPH is significantly better than the previous method FPH.\n* The qualitative evaluation does not provide very meaningful insights of the performance.  I suppose similar results can be observed by other clustering methods provided that suitable features are available to compute the similarity between images.  I think it would be more interesting if the hierarchy of clusters can be visualised instead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comprehensive feedback. In the following, we address their questions and remarks.\n\n**Comment:** The contribution looks incremental in this sense, even with some interesting and nicer theoretical properties over the previous work.  \n**Response:** While our work builds upon the probabilistic hierarchies introduced in [1], it has several contributions. First, we present new theoretical insights into the limitations of Soft-Das, providing a concrete example where FPH fails to find the optimal hierarchy. To address this issue, we propose expected scores, along with a framework for optimizing these scores. We further justify our approach by demonstrating that their optimal hierarchies align closely with their discrete counterparts. Additionally, we introduce an *unbiased* subgraph sampling algorithm, extending the applicability of both FPH and EPH to vector datasets. Finally, through a thorough empirical evaluation, we demonstrate that our method consistently outperforms existing baselines across both graph and vector datasets, highlighting the practical impact of our contributions.\n\n**Comment:** The improvement of EPH over FPH is not as significant as that over other baseline methods.  \n**Response:** We would like to emphasize that we did various modifications to FPH, improving their results as shown in Table 10 in the appendix. For example, EPH has a >20\\% improvement on the Brain dataset over the original FPH. Even after tuning FPH, EPH reaches improvements of up to >12\\% (OpenFlight).\n\n**Comment:** The proposed solution may not converge to the global optimum of Exp-Das nor Exp-TSD.  \n**Response:** While EPH, like many complex optimization algorithms, may not always converge to the global optimum, its consistency ensures that any probabilistic hierarchy found encoded corresponding discrete hierarchies. The theoretical results remain relevant because they demonstrate that even probabilistic hierarchies correspond to discrete hierarchies with consistent scores. This consistency is a valuable property not guaranteed by FPH or other baselines.\n\n**Comment:** Only the best score of the hierarchies resulting from five random initialisation is reported in the experiments.  \n**Response:** The reason for reporting the best score is that non-deterministic methods can improve their results across multiple runs. To address the concern about variance, we have reported the standard deviations in Tables 16 and 17, which are less than 2% and are substantially lower than the standard deviations of other methods. Additionally, we provide the following table comparing the mean performance of EPH with FPH, demonstrating that even the average performance of EPH is superior:\n\nDasgupta costs:\nModel | Polblogs | Brain | Citeseer | Genes | Cora-ML | OpenFlight | WikiPhysics | DBLP | Zoo | Iris | Glass |\n|-|-|-|-|-|-|-|-|-|-|-|-|\nFPH |238.65 | 425.70 | 76.03 | 182.91 | 257.42 | 355.61 | 482.40 |  31,687 | 56.13 | 69.13 | 122.00 |\nEPH mean | **235.89** | **402.30** | **74.11** | **179.64** | **239.21** | **315.10**| **459.51** | **30,637** | **55.80** | **69.10** | **120.97** |\n\nTSD scores:\nModel | Polblogs | Brain | Citeseer | Genes | Cora-ML | OpenFlight | WikiPhysics | DBLP |\n|-|-|-|-|-|-|-|-|-|\nFPH |31.37|32.75|**69.38**|**67.78**|**59.55**|57.58|49.87|41.62|\nEPH | **31.60** | **33.87** | 69.34 | 67.67 |59.38|**57.63**|**50.04**|**42.69**|\n\nThese results further demonstrate the effectiveness of EPH and its robustness against randomness.\n\n**Comment:** It would be interesting to visualise the hierarchy of the clusters.  \n**Response:** We thank the reviewer for their suggestion. We would like to highlight that we have already visualized hierarchies for the HSBMs in Figure 4 of the main paper and for the OpenFlight dataset in Figure 12 of the appendix. \n\nIn addition to these, we have now also visualized the hierarchies for the vector datasets, as described in the general comment.\n\n\n**Comment:** Can we find the discrete hierarchy that gives the optimal Das or TSD after getting the probabilistic hierarchy with the optimal Exp-Das or Exp-TSD?  \n**Response:** Yes, the optimal discrete hierarchy can be easily obtained from the optimal probabilistic hierarchy. Proposition 4.1 in our paper proves that the optimal expected scores and discrete scores align. Since the expected cost can be expressed as a convex combination of discrete scores, any sampled discrete hierarchy from the optimal probabilistic hierarchy will be optimal. This means that once we obtain the optimal probabilistic hierarchy, we can sample any discrete hierarchy from it, knowing that it will have the optimal Das or TSD score.\n\n**Comment:** Section 4.3 says that \"we can use a closed-form expression\", but then it says \"no known solution exists\".  \n**Response:** We apologize for the confusion caused by the wording. The intention was to emphasize that while closed-form expressions might exist in theory, tractable solutions have yet to be discovered. The phrase \"we can use a closed-form expression\" should have highlighted the theoretical possibility rather than the practical availability. Currently, there are no known closed-form solutions for Exp-Das and Exp-TSD. Consequently, we use the sampling method.\n\nWe again thank the reviewer for their feedback and hope that we have satisfactorily addressed their concerns. If there are any remaining remarks, we are happy to address them.\n\n[1] **Zügner et al.** \"End-to-end learning of probabilistic hierarchies on graphs.\" In International Conference on Learning Representations. 2021.", "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": "", "extra_scores": {}}, {"review_id": "EKBvUGeUst", "reviewer": "Reviewer_AAtX", "summary": "This paper proposes a method for hierarchical clustering by optimizing expected clustering scores (DAS/TSD) over the distribution of hierarchies. They show theoretically that their proposed optimization objective is consistent with their discrete counterparts: that is, the solution for their proposed optimization problem is equivalent to the solution of the intractable discrete optimization problem (this is in contrast with other continuous relaxations such as soft-DAS that do not have this property). They show that this problem can be solved well in practice in an end-to-end manner despite not being convex. The authors show that their method empirically outperforms other known methods.", "questions": "1) In what cases would a practitioner prefer to use your method (EPH) over FPH? It seems that the former is much more computationally expensive. Are there applications that demand such precise clustering? (If I'm understanding correctly, because of the non-convexity, EPH cannot guarantee optimal solution despite consistency anyway).\n\n2) Alternatively, are there reasons to believe future work can significantly speed up EPH to make it competitive (in the runtime sense) with other baselines?", "limitations": "Yes,  the authors addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is extremely well written and technically correct/solid. The problem background is explained well in a way that is accessible to a broader audience as well.", "weaknesses": "The main issue with this paper is the significance of the contribution. Overall, the work seems like a marginal improvement over [1].  In my view, the differentiable sampling techniques used are very standard and the main novel contribution is their theoretical result about consistency of their optimization objective with that of the discrete objective. The experimental results also only show a marginal improvement over the work that it builds on [1]. Furthermore, based on the runtimes from Table 18, it seems that this marginal improvement comes at a great computational overhead compared to FPH [1]. Thus, in the context of the whole paper, while the theoretical result is certainly interesting, this seems like an incremental contribution.\n\n[1] Zügner et al., End-to-End Learning of Probabilistic Hierarchies on Graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and address their concerns in the following.\n\n**Comment:** The experimental results also only show a marginal improvement over the work that it builds on [1]. Based on the runtimes from Table 18, it seems that this marginal improvement comes at a great computational overhead compared to FPH [1]. [...]  \n**Response:** We appreciate the reviewer's feedback and would like to clarify the significance of our contribution. Our proposed method, EPH, introduces several crucial modifications to FPH, which result in notable improvements of FPH itself across multiple datasets, as shown in Table 10. For instance, on the Brain dataset, EPH achieves an over 20% improvement compared to the original FPH, and even after tuning FPH, EPH still provides up to a 12% improvement on the OpenFlight dataset. Furthermore, it is important to note that FPH can only be applied to large vector datasets due to our proposed subgraph sampling algorithm. EPH demonstrates superior scores to many baselines and a lower runtime than the other continuous method, HypHC. We believe these advancements elevate our contribution beyond incremental improvements and hope the reviewer recognizes the broader applicability and potential impact provided by EPH.\n\n**Comment:** In what cases would a practitioner prefer to use your method (EPH) over FPH? [...] Are there applications that demand such precise clustering? EPH cannot guarantee optimal solutions despite consistency.  \n**Response:** While it is true that EPH cannot guarantee convergence to the global optimum, its consistency provides several advantages that make it preferable in specific scenarios. EPH ensures that any reduction in the objective function results in a probabilistic hierarchy where discrete hierarchies are encoded with consistent costs. Unlike FPH, which can diverge from an optimum, EPH's probabilistic approach ensures that the resulting optima contain discrete hierarchies with equivalent costs, allowing for easier sampling of discrete hierarchies. \n\nEPH also provides a valuable trade-off between quality and runtime through adjustable hyperparameters, allowing practitioners to prioritize high-quality hierarchies when computational resources are secondary. In applications where precise clustering is crucial, EPH can uncover hierarchies that deterministic methods like FPH may miss, irrespective of the computational resources available.\n\nA common example where precise clustering is crucial is to predict the clinical prognosis of cancer genomics [2, 3]. \n\n**Comment:** Alternatively, are there reasons to believe future work can significantly speed up EPH to make it competitive with other baselines?  \n**Response:** Our primary focus was on improving the quality of inferred hierarchies rather than optimizing for runtime. However, we see several opportunities for future work to significantly reduce the runtime of EPH. These include:\n\n1. **Parallelizing computations** of different Gumbel samples, which in our current implementation are computed sequentially. By parallelizing, we can achieve a substantial reduction in runtime.\n\n2. **Reducing the number of Gumbel samples** as a trade-off. EPH allows for flexibility in the number of samples needed to approximate the loss, with fewer samples leading to faster computations.\n\n3. **Skipping validation steps** that are necessary for FPH but not for EPH, as EPH's loss is consistent with the discrete Dasgupta cost.\n\nTo demonstrate the feasibility of these improvements, we implemented two modified versions of EPH on the graph datasets: EPH (parallelized) and EPH (minimized). EPH (parallelized) maintains the same numerical results while reducing runtime by up to 80%. EPH (minimized), which reduces the number of Gumbel samples and skips validation steps, achieves a runtime reduction of up to 97.5%, even outperforming FPH in speed, as shown in the following table.\n\n| Method | Polblogs | Brain | Citeseer | Genes | Cora-ML | OpenFlight | WikiPhysics |\n|-|-|-|-|-|-|-|-|\n| FPH |452|547|345|373|644|592|667|\n| EPH |3834|3402|2609|2848|3322|4419|6389|\n| EPH (parallelized) |1496|1066|749|521|1196|1654|2325\n| EPH (minimized)|111|100|72|79|85|116|157 \n\nWhile these modifications offer a significant speed improvement, they still achieve state-of-the-art results, as shown in the following table.\n\nModel|Polblogs|Brain|Citeseer|Genes|Cora-ML|OpenFlight|WikiPhysics|\n|-|-|-|-|-|-|-|-|\nFPH |238.65|425.70|76.03|182.91|257.42|355.61|482.40|\nEPH (minimized) | **236.86** | **404.30** | **72.81** | **173.56** | **238.11** | **309.33** | **463.63** |\n\nWe are optimistic that future research, particularly in sampling approximation methods [4] and GPU-accelerated alias sampling [5], will continue to reduce EPH's runtime, allowing it to scale to even larger datasets. Finally, it is worth noting that EPH's flexibility allows it to be applied to any differentiable metric, enabling future adaptations and applications across a wide range of fields.\n\nWe again thank the reviewer for their feedback and hope that we have addressed their concerns satisfactorily. \n\n[1] **Zügner et al.** \"End-to-end learning of probabilistic hierarchies on graphs.\" In International Conference on Learning Representations. 2021.\n\n[2] **Van't Veer et al.** \"Gene expression profiling predicts clinical outcome of breast cancer.\" nature 415, no. 6871 (2002): 530-536.\n\n[3] **Macaluso et al.** \"Cluster trellis: Data structures & algorithms for exact inference in hierarchical clustering.\" In International Conference on Artificial Intelligence and Statistics, pp. 2467-2475. PMLR, 2021.\n\n[4] **Paulus et al.** \"Rao-blackwellizing the straight-through gumbel-softmax gradient estimator.\" arXiv preprint arXiv:2010.04838 (2020).\n\n[5] **Wang et al.** \"Skywalker: Efficient alias-method-based graph sampling and random walk on gpus.\" In 2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT), pp. 304-317. IEEE, 2021.", "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": "", "extra_scores": {}}, {"review_id": "NVx2tSjmBt", "reviewer": "Reviewer_f9v5", "summary": "This paper studies gradient-based methods for hierarchical clustering, presenting an interesting approach EPH which is both scalable and accurate. The approach uses a subgraph sampling approach for scalability and is interesting in its optimization of expected hierarchical clustering costs.", "questions": "Can you add / discuss more about the implications of binary vs non-binary hierarchies?", "limitations": "adequately addressed", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a very well written paper which: \n* Interesting methodological contributions\n* Has thorough empirical comparisons\n* Clear writing and presentation of ideas\n* Presentation of complexity\n* Presentation of empirical comparisons on a wide variety of datasets", "weaknesses": "Weaknesses of the paper include: \n* Perhaps the methodological ideas are a bit on the simple side, however, this may be an impression given by a well written paper.\n* it is a bit difficult for me to understand when a practitioner would choose this method over some algorithmic alternatives", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable concerns. In the following, we address their comments.\n\n**Comment:** It is a bit difficult for me to understand when a practitioner would choose this method over some algorithmic alternatives.  \n**Response:** EPH is particularly advantageous over alternatives in scenarios where the quality of the hierarchy is crucial and outweighs other factors. Unlike algorithmic alternatives, EPH has the unique ability to uncover hierarchies that deterministic methods are not able to reach, regardless of their computational resources. This makes EPH an ideal choice when the primary objective is to capture intricate data structures that are critical for the analysis.\n\nMoreover, EPH offers flexibility through its adjustable hyperparameters, allowing practitioners to balance the trade-off between clustering precision and computational efficiency. This adaptability enables users to tailor the method to their specific needs, whether they require high-quality clustering or need to optimize for runtime.\n\n**Comment:** Can you add / discuss more about the implications of binary vs non-binary hierarchies?  \n**Response:** Binary hierarchies offer fine-grained clustering and are often easier to analyze with certain theoretical models, e.g., to derive lower bounds for costs [3]. However, they can be computationally intensive. Non-binary hierarchies, in contrast, provide more flexibility by allowing nodes to have more than two children, which often aligns better with real-world clustering tasks. This flexibility can simplify the hierarchy and make it easier to interpret at higher levels. However, it is worth noting that binary hierarchies are required in certain tasks, such as jet physics and cancer genomics [2].\n\nIt is important to note that while the Dasgupta cost tends to favor binary branches [1], as seen in Figure 4, our approach is not restricted to binary hierarchies. EPH allows hierarchies to have any number of children, including binary hierarchies, if that structure is indeed optimal for the data. \n\nWe thank the reviewer again for their feedback and will discuss these points in the updated manuscript. We are happy to address any remaining concerns.\n\n[1] **Dasgupta, Sanjoy.** \"A cost function for similarity-based hierarchical clustering.\" In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 118-127. 2016.\n\n[2] **Macaluso, Sebastian, Craig Greenberg, Nicholas Monath, Ji Ah Lee, Patrick Flaherty, Kyle Cranmer, Andrew McGregor, and Andrew McCallum.** \"Cluster trellis: Data structures & algorithms for exact inference in hierarchical clustering.\" In International Conference on Artificial Intelligence and Statistics, pp. 2467-2475. PMLR, 2021.\n\n[3] **Chami, Ines, Albert Gu, Vaggos Chatziafratis, and Christopher Ré.** \"From trees to continuous embeddings and back: Hyperbolic hierarchical clustering.\" Advances in Neural Information Processing Systems 33 (2020): 15065-15076.", "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": "", "extra_scores": {}}, {"review_id": "6p9Xf5W02l", "reviewer": "Reviewer_KKzQ", "summary": "This paper proposes for hierarchical clustering a new method Expected Probabilistic Hierarchies (EPH) that is developed from the Flexible Probabilistic Hierarchy (FPH) method. Unlike FPH using Soft-Das and Soft-TSD, EPH provides an unbiased estimate on two new objectives called Exp-Das and Exp-TSD. EPH has addressed the alignment issue between continuous and discrete targets, which is supposed to be the reason why it outperforms other continuous methods. Soft-Das is proved to be a lower bound on Exp-Das (Proposition 4.2), which is the main theoretical contribution. A learnable approach based on differentiable hierarchical sampling was proposed, in which the tree sampling procedure and the Gumbel-Softmax estimator are the main techniques to approximate the discrete choices of parent nodes. Experimental results verify the effectiveness of the new method.", "questions": "1. It seems that the Dasgupta cost is robust against the numbers of hierarchies and internal nodes, whose variation may lead to quite different hierarchical structures. However, a real system is believed to have its own intrinsic structure with relatively fixed such numbers. Does it mean that EPH or even Das and TSD costs are not suitable for finding the intrinsic hierarchical structure of real systems? I think that finding the intrinsic numbers is quite a difficult task, and it seems not a good way to treat them as hyper-parameters.\n\n2. How do you restrict the number of hierarchies when in the condition that the number of internal nodes is given?", "limitations": "Yes, the authors have addressed the limitations in their discussions.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors propose a new hierarchical clustering method based on a sampling-based differentiable metric.\n\n2. The authors make comprehensive experiments to demonstrate that their method outperforms the baselines on both synthetic (HSBM) and real (including graph and vector) datasets.", "weaknesses": "The technical contribution is limited since the framework of the algorithm and main techniques almost totally come from (Z$\\ddot{u}$gner et al., 2022). I do understand that EPH has its own scores rather than soft scores, but I don't think the novelty is strong enough for the NeurIPS criterion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and address their comments below.\n\n**Comment:** The technical contribution is limited since the framework of the algorithm and main techniques come from (Zügner et al., 2022).  \n**Response:** While our work builds upon the probabilistic hierarchies introduced by Zügner et al. (2022), it addresses key limitations of their approach and introduces several significant contributions and advancements.\n\nFirstly, we prove that the Soft-Das cost is a lower bound of the discrete Dasgupta cost (Sec. 4.2), and we provide a concrete example where it fails to identify the optimal hierarchy. Building on this insight, we propose the Exp-Das and Exp-TSD metrics (Sec. 4.1) and show that their optimal hierarchies align with the discrete counterparts. Furthermore, we introduce an *unbiased* subgraph sampling algorithm, allowing us to employ both FPH and EPH to vector datasets. \n\nOur empirical evaluation further demonstrates these advancements, showing substantial performance improvements, with gains of over 20%  on certain datasets compared to the original FPH (see Table 10 in the appendix). These improvements are consistently observed across graph and vector datasets, underscoring the practical impact and novelty of our contributions.\n\n\n**Comment:** It seems that the Dasgupta cost is robust against the numbers of hierarchies and internal nodes, whose variation may lead to quite different hierarchical structures. However, a real system is believed to have its own intrinsic structure with relatively fixed such numbers. Does it mean that EPH or even Das and TSD costs are not suitable for finding the intrinsic hierarchical structure of real systems? I think that finding the intrinsic numbers is quite a difficult task, and it seems not a good way to treat them as hyper-parameters.  \n**Resonse:** The Dasgupta cost and TSD metrics tend to improve with an increasing number of internal nodes, but they eventually converge when the hierarchies become expressive enough to capture the intrinsic structure of the data. In an unsupervised setting, the true number of internal nodes is unknown. To address this, we conducted experiments to determine when most of the information is captured, which we found to occur at $n' = 512$ (see Figure 14 and Figure 15). While the choice of internal nodes can depend on the specific application, a higher number is generally preferable as it captures more information and can be pruned later. We do not expect significant structural differences in hierarchies of different sizes, as the metrics maintain consistent and intuitive meanings across configurations.\n\nMoreover, we validated our approach on synthetic HSBMs, where the number of internal nodes is predefined (see Figure 4 and Table 4). The results show that the inferred hierarchies closely align with the ground truth, indicating that EPH, along with the Dasgupta and TSD costs, is suitable for identifying the intrinsic hierarchical structure when the exact number of internal nodes is used to condition the hierarchies.\n\n**Comment:** How do you restrict the number of hierarchies when in the condition that the number of internal nodes is given?  \n**Response:** The number of hierarchies is implicitly constrained by the sizes of $\\mathbf{A}$ and $\\mathbf{B}$. Specifically, selecting $n'$ effectively limits the number of internal nodes, thereby restricting the possible hierarchies that can be inferred.\n\nWe again thank the reviewer and are happy to address any remaining concerns.", "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": "", "extra_scores": {}}, {"review_id": "zkQWZJpcM2", "reviewer": "Reviewer_YnBf", "summary": "This paper considers the problem of hierarchical clustering. This problem is typically handled by discrete optimization approaches, which define a hierarchical clustering quality score (e.g. Dasgupta and TSD) and optimize it on a discrete search space. More recent approaches consider this problem from a probabilistic perspective. They soften the hierarchical clustering scores and optimize them on a continuous space. In this paper, the authors propose an extension of the prior work on Flexible Probabilistic Hierarchy (FPH) [Zügner et al, 2021]. Specifically, they introduce Expected Probabilistic Hierarchies (EPH), a new probabilistic hierarchical clustering objective for continuous optimization. The consistency and advantages of EPH are supported by theoretical analysis. The experimental results on synthetic and real-world datasets show that EPH can outperform existing approaches.", "questions": "- The motivation behind adopting the Dasgupta and TSD is not clearly stated. While the authors provide definitions and references for them, it is still hard to understand why these two particular scores are used and how they are in contrast to each other. Could the authors elaborate on this point?", "limitations": "The authors have discussed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Overall, this paper is well-organized and easy to follow.\n- The contributions are clearly described and well-supported by theoretical analysis and experiments.\n- Extensive experimental results and visualizations are provided.", "weaknesses": "- While I appreciate the theoretical results for supporting the advantages of EPH over FPH, there is a lack of substantial technical improvements. Therefore, the novelty is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comprehensive feedback. In the following, we address their comments. \n\n**Comment:** While I appreciate the theoretical results for supporting the advantages of EPH over FPH, there is a lack of substantial technical improvements. Therefore, the novelty is limited.  \n**Response:** We appreciate the reviewer's recognition of the theoretical results supporting the advantages of EPH over FPH. We want to emphasize that EPH introduces several significant advancements that contribute to its novelty and practical impact.\n\nFirst, EPH demonstrates substantial improvements in performance, with gains of over 20% compared to the original FPH on certain datasets (see Table 10 in the appendix). These improvements are not isolated but consistent across a wide range of datasets, underscoring the effectiveness of our approach.\n\nMoreover, our work introduces a novel *unbiased* subgraph sampling technique that significantly enhances the scalability of EPH, particularly on dense vector datasets. This scalability is a crucial advancement, as it allows EPH to be applied to larger and dense datasets that FPH cannot handle. EPH opens new possibilities for its application in various domains where data similarities are dense.\n\nIn addition to performance and scalability improvements, EPH provides theoretical justification for its framework. Finally, we are hopeful that future work will be able to adapt our algorithm to different use cases, as its only requirement is a differentiable metric.\n\n**Comment:** The motivation behind adopting the Dasgupta and TSD is not clearly stated. While the authors provide definitions and references for them, it is still hard to understand why these two particular scores are used and how they are in contrast to each other. Could the authors elaborate on this point?  \n**Response:** We focused on the Dasgupta cost and TSD because they are well-studied clustering metrics with intuitive meanings. \nThe Dasgupta cost is a widely used metric that measures the quality of a hierarchical clustering by evaluating how close similar leaves are in the hierarchy. Specifically, it quantifies the expected number of leaves for which the lowest common ancestor of a randomly sampled pair of leaves is their shared ancestor. A lower Dasgupta cost indicates that similar items are grouped together in the hierarchy, reflecting a good clustering structure.\n\nThe Tree-Sampling Divergence (TSD), on the other hand, quantifies how well a hierarchy can reconstruct its graph. More specifically, it is defined as the KL divergence between the node and the edge distributions. Its advantage over the Dasgupta cost is that it does not favor binary hierarchies.\n\nBoth metrics are unsupervised and differentiable, which is necessary for the gradient-based optimization in our approach. The unsupervised nature of these metrics allows us to evaluate the quality of the hierarchies without the need for labeled data, making them applicable to a wide range of applications.\n\nWe again thank the reviewer for their feedback and are happy to address any upcoming questions.", "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": "", "extra_scores": {}}]

Author rebuttal:
We want to thank the reviewers for their valuable feedback and for acknowledging the clear writing (xKdT, AAtX, f9v5, YnBf), our extensive experiments (xKdT, f9v5, KKzQ, YnBf), and our methodological contribution including our theoretical analysis (xKdT, f9v5, YnBf).

We have addressed all comments and concerns in the individual responses provided under each review. In this general response, we want to summarize the new results and experiments we have conducted.

**Additional Visualizations**  
In response to reviewer xKdT’s suggestion, we have included additional visualizations by applying the t-SNE algorithm to the vector datasets. These visualizations display the ground-truth labels, clusters inferred from the hierarchies, and their corresponding dendrograms. To enhance the clarity, we aligned the inferred clusters with the ground-truth labels using the Hungarian algorithm, allowing for an intuitive comparison. These visualizations are available in the supplementary PDF.

The additional qualitative evaluation demonstrates a strong alignment between the ground-truth labels and the clusters inferred by EPH. Furthermore, we observe that similarities in the t-SNE space are well-preserved within the dendrograms, indicating the effectiveness of our method.

**Runtime Improvements**  
Following the recommendation of reviewer AAtX, we improved the runtime of EPH by parallelizing the computations of the different Gumbel samples. This optimization does not alter the results but substantially reduces the runtime. The following table shows the improved runtime (in seconds) on the graph datasets:

| Method | Polblogs | Brain | Citeseer | Genes | Cora-ML | OpenFlight | WikiPhysics |
|-|-|-|-|-|-|-|-|
| EPH     | 3834 | 3402 | 2609 | 2848 | 3322 | 4419 | 6389 |
| EPH (parallelized) | 1496 | 1066 | 749 | 521 | 1196 | 1654 | 2325

We again thank all the reviewers and are confident that the feedback will help improve the revised manuscript. We are happy to address any remaining or upcoming concerns.

Meta-review: The reviewers generally felt positive about this paper -- the main concern is that the paper is in some sense incremental over prior work on FPH (citation [40] in the paper). The main idea is the same as this prior work, but the approach just looks at the expected cost over the probability of hierarchies rather than the expected cost of the probabilistic hierarchy itself. This leads to some nicer theory in terms of global optima corresponding for the probabilistic and discrete optimization tasks. The reviewers were swayed ultimately to accept due to the potential for practical relevance of the method, including the demonstration of improved runtimes included in the rebuttal. We hope that these additional results will be included in the final version of the paper.
Decision: Accept (poster)