End-to-End Learning of Probabilistic Hierarchies on Graphs
Authors: Daniel Zügner
Bertrand Charpentier
Morgane Ayle
Sascha Geringer
Stephan Günnemann
Venue: ICLR 2022 Poster (2022)
Keywords: hierarchical clustering
graphs
networks
graph mining
network mining
graph custering

Abstract: We propose a novel probabilistic model over hierarchies on graphs obtained by continuous relaxation of tree-based hierarchies. We draw connections to Markov chain theory, enabling us to perform hierarchical clustering by efficient end-to-end optimization of relaxed versions of quality metrics such as Dasgupta cost or Tree-Sampling Divergence (TSD). 
We show that our model learns rich, high-quality hierarchies present in 11 real world graphs, including a large  graph with 2.3M nodes. Our model consistently outperforms recent as well as strong traditional baselines such as average linkage. 
Our model also obtains strong results on link prediction despite not being trained on this task, highlighting the quality of the hierarchies discovered by our model.

Published as a conference paper at ICLR 2022
END-TO-END LEARNING OF PROBABILISTIC HIERARCHIES ON GRAPHS
Daniel Zügner, Bertrand Charpentier, Sascha Geringer, Morgane Ayle,
Stephan Günnemann Technical University of Munich (zuegnerd, charpent, geringer, ayle, guennemann sin. tum. de
ABSTRACT
We propose novel probabilistic model over hierarchies on graphs obtained by continuous relaxation of tree-based hierarchies. We draw connections Markov chain theory, enabling to perform hierarchical clustering by efficient end-to-end optimization relaxed versions of quality metrics such as Dasgupta cost or Tree- Sampling Divergence (TSD). We show that our model learns rich, high-quality hierarchies present in 11 real world graphs, including a large graph with 2.3M nodes. Our model consistently outperforms recent well strong traditional baselines such as average linkage. Our model also obtains strong results on link prediction despite not being trained this task, highlighting the quality of the hierarchies discovered by our model.
INTRODUCTION
Clustering is a fundamental problem in unsupervised learning, both in theory and practice. In contrast to traditional 'flat' clustering, hierarchical clustering brings several advantages. It enables to naturally analyze (Zhao & Karypis 2002) and visualize (Himberg et al.] (2044) given dataset on different scales. Further, different downstream tasks may require different granularities. Hierarchical clustering lets us pick the desired granularity after learning. It can also be used for personalized recommendation (Zhang et al., (014) to solve record linkage tasks (Wick et al.] 2012). In an influential paper, Eisen et al. (1998) perform hierarchical clustering gene expression data and argue that it could be used discover the yet-unknown meaning of certain genes, which could lead to advances in medicine. Besides traditional vector data, real-world graphs are often scale-free and hierarchically organized (Ravasz & Barabási, 2003 Barabási Pósfai 2016). This makes them interesting candidates for uncovering the underlying hierarchy via hierarchical clustering. Thus, the hierarchical clustering method we introduce is particularly useful for analyzing scale-free real- world networks such as Web graphs, citation networks, flight networks, biological networks.
Related work. We can group hicrarchical clustering algorithms into discrete and continuous opti- mization methods. Discrete optimization methods themselves be decomposed into agglomerative approaches and divisive approaches. Agglomerative methods like the famous linkage algorithms (Gower Ross 1969 Jardine & Sibson 1968, Bonald et al. 2018 Charpentier] 2019) follow a bottom-up approach and iteratively aggregate the two most similar clusters w.r.t. a given simi- larity measure. Divisive methods follow a top-down approach and recursively split larger clusters into smaller ones using, e.g., k-means (Steinbach et al. 2000) or spectral clustering (Charikar & Chatziafratis 2016). While Moseley with explicit objective functions, those methods are mainly based on heuristics to avoid exhaustive combinatorial optimization.
(201)] Kamvar et al. (2002) have shown connections
On the other hand, continuous optimization methods circumvent this issue by (i) relaxing the discrete
tree structure, (ii) defining an explicit quality metric for hierarchies, and (iii) optimizing it using gradient-based optimizers. Chierchia & Perret (2019); Monath et al. (2017 2019); Chami al.) (2020) focus on minimizing the Dasgupta cost (Dasgupta 2016) (see Eq. 11] to fit an ultrametric. hyperbolic embeddings, probabilistic model over cluster assignments, Monath et al. (2017) lears a probabilistic assignment the samples to leaves of a tree with a fixed binary structure. The method of Monath al. (2019) requires approximation for the computation of lowest common ancestors

---

Published as a conference paper at ICLR 2022
(LCA) probabilities and regularization losses. Beyond the Dasgupta cost, Charpentier & Bonald (019) propose the Tree Sampling Divergence (TSD), quality metric for hierarchies on graphs. Both metrics have the benefit be internal metrics, i.e. they do not require ground truth information to evaluate the quality of a hierarchy. Most of the aforementioned methods focus on vector data.
Contributions. We (1) propose probabilistic model over hierarchies via continuous relaxation of tree's parent assignment matrices. We (2) theoretically analyze the model by drawing connections to absorbing Markov chains, which allows (3) efficient and exact computation of relevant quantities (e.g., LCA probabilities). This enables us to (4) learn hierarchies on graphs by efficient, end-to-end optimization of relaxed versions of quality metrics such as Dasgupta cost and the TSD score. Our extensive experimental evaluation on I1 real-world graphs, including a massive graph with more than 2M nodes and 60M edges, highlights the effectiveness of our Flexible Probabilistic Hierarchy model (FPH). It outperforms all baselines, traditional and recent, on the quality of the learned hierarchies measured both by TSD and Dasgupta cost. Remarkably, FPH also performs competitively on link prediction despite not being trained this task.
2 HIERARCHICAL GRAPH CLUSTERING PRELIMINARIES
We define a graph 9 = (E, V) with nodes and undi- rected edges. We let w(v,, v,) be equal to the weight of edge (V,, vj) ) if they are connected and to other- wise, and w(v,) = Σ, w(ve, vÿ) to be equal to the p(g weight of node Vi. This allows us to define the edge distribution P(v,, vy) oc w(vs, vz) normalized over all edges s.t. Eig P(v., Vy) = and the node distribution P(v:) w(:)) s.t. Σ, P(v;) 1, which are later needed to compute the quality metrics of learned hierarchies.
p(gl())
8
Hierarchy
Matrix Form
Discrete hierarchical clustering. We define a hierarchi- cal clustering T of a graph G tree structured partition- ing of the nodes V. We denote the nodes of the tree F with nı' E N internal nodes by {X1. Xn+n') }. The tree nodes can be decomposed into the Icaf nodes (v1.-.,, Vn) corresponding the nodes of the input graph, and the internal nodes {71,..., "....,'''') repre- (V1,..., Vn U fZ1,,-.. Zn J. Since any tree is directed acyclic graph (DAG), we impose w.l.o.g. topological ordering the internal nodes of the tree in the remainder of this work. That is, cannot be a parent of z; if < j; Zn,' denotes the root node. We can uniquely define tree T (Á, B) with two adjacency matrices, Å {0, 1] 1 and В {0, 1]" xn', Å describes the connections from the leaves to the internal nodes, i.c. Å, = 1 if internal node 7 is the parent of leaf node B describes the connections between the internal nodes, i.e. B = 1 internal node 77 is the parent of internal node 7g. Since in tree any node has exactly one parent, Å is row-stochastic and B is row-stochastic; except its last row B. correspond- ing to the root, whose sum is O. We denote by V, A V, the internal node which the lowest common ancestor (LCA) of v,, V, in the tree. The maximum possible number of internal nodes is n'
Observed Graph
Figure 1: Model overview.
senting clusters of leaf nodes; overall (x1,..., xntz/
Probabilistic hierarchical clustering. The central idea of FPH is to define a probabilistic tree T via continuous relaxation of the binary-valued valued adjacency matrices A, B. Le.. we define A. B such that A [0. 1jaxn' and B E [0, 1|n2 xn' while keeping the row-stochasticity constraints, ie., " Arj = 1 for < i S n, Σ B = 1, < < n', and for the root node we have Er B = 0. This describes probabilistic hierarchy: the probability of an internal node z, be parent of a leaf or an internal node is Au == p(zzlv;) or B:j := (z)) respectively. See Fig. for visualization. Our key technical contribution are efficient closed-fond expressions for the lowest common ancestor probabilities that arise when sampling discrete trees from the probabilistic one.
2.1 INTERNAL METRICS FOR HIERARCHICAL CLUSTERING
Internal metrics are commonly used to evaluate clustering methods, and they have the important advantage of not requiring external labels. For hierarchical clustering graphs, two internal metrics have been proposed to assess the quality of discrete hierarchy 7 given input graph G: Dasgupta
2

---

Published as a conference paper at ICLR 2022
cost (Das.) (Dasgupta 2016), and Tree-Samphle Pree-Sampling Divergence (TSD) Charpentier & Bonald 2019).
While the Dasgupta cost can be used for graphs and vector data, TSD is tailored specifically to graphs.
Das(T)=
Σ P(vs, vy) [deenn,,dd)), TSD(T) (L(p(z)llo(z) V.NJEV
(1)
For Das., c(z) Evey [[kean(vv.]] denotes the number of leaves for which the internal node z is an ancestor. Intuitively, the cost is large if v; and v, are connected by an edge and their lowest common ancestor contains many leaves, i.e., is close the root. Thus, Dasgupta favors leaves connected by an edge to have LCAs low in the hierarchy. For Das., lower scores indicate better hierarchies.
TSD defines two distributions over the internal nodes, p(z) Lyy., [[==AA, P(v;, Vz), induced by the edge distribution, and q(2) = Ev.., [[z=vAvr)] P(v.) induced by the independent node distribution. Intuitively, we expect the graph distribution p(z) (induced by edge sampling) and the null model distribution q(z) (induced by independent node sampling) to differ significantly if the tree I indeed represents the hierarchical structure of the graph, leading to high TSD scores.
Continuous relaxation. To enable end-to-end gradient- optimization of Dasgupta or TSD, we replace the discrete hierarchy f = (Á, B) with its continuous relaxation T (A, B). This leads to probabilistic parent assignments of leaves to internal nodes. By itself, this does not help in hierarchical clustering as it is not clear how to compute the lowest common ancestor probabilities when sampling discrete hierarchies from the relaxed one, i.c., the probability that internal node is the lowest common ancestor of two leaves. Our main theoretical contribution to derive closed-form expressions for the lowest common ancestor probabilities in Sec. 3 This gives rise to continuous versions of TSD and Dasgupta (details in Appendix [A.]] which we will refer to as Soft-TSD and Soft-Das., respectively. For the first time, this allows to directly optimize for hierarchical clustering quality metrics in an end-to-end fashion instead of proxy losses or heuristic algorithms.
For optimization over hierarchies, we either minimize the Dasgupta cost maximize TSD: min Soft-Das (A, B)) or max SOft-TSD(T -AA, B)),
A.B
A.B
where A E [0, 1jnxn' B E [0, 10,1,'xx xx' are the continuous relaxations of the parent assignment matrices as described in Sec. 2 Note that for both metrics recover the same score as their discrete versions in the case of deterministic probabilistic model, i.e. when A, B are binary-valued.
2.2 SAMPLING DISCRETE HIERARCHIES
Given the probability matrices A and B sampling discrete matrices Å and B, which in turn describe (discrete) tree TT For each leaf and internal node we independently sample its parent from the categorical distribution described by the respective row in A or B. As we show in Appendix A.2 this tree-sampling procedure (denoted T= B) ~ (T)) leads to valid tree hicrarchies. and we can directly compute the probability of any discrete hierarchy given the probabilistic one. We denote probabilities associated with the tree-sampling perspective as (.)) Note that we can easily obtain a discrete tree given continuous A, B in deterministic way by selecting for each leaf and internal node its most likely parent.
easily recover a discrete hierarchical clustering by
3 EFFICIENT, DIFFERENTIABLE HIERARCHIES VIA MARKOV CHAINS
Outline. This section is organized as follows. The goal is to derive efficient, closed- equations to compute (lowest common) ancestor probabilities which are consistent with the samplinn pro- cedure explained in the previous section. For this, we draw connections to absorbing Markov chains how to compute the desired quantities efficiently under this sim- plifying Markov Chain perspective. Then, show that these equations under the Markov chain and the tree-sampling perspectives are equivalent, i.c., we do not introduce any error by the Markov chain assumptions. Finally, we show in Sec. 3.3 how exploit the independence assumptions of the Markov chain to compute the (lowest common) ancestor probabilities efficiently and in a vectorized way.
in Sec. and show Secs. 3.1 3.2
We start by showing that the probabilistic model described in the previous section indeed defines an absorbing Markov chain. Intuitively, A and B can be interpreted as transition matrices from leaves to internal nodes and among internal nodes, respectively.
3

---

Published as a conference paper at ICLR 2022
Definition 1 (Tree Markov Chain). Let A E [0, 1j Ay vi n and B e
[0, 11 xx Ej= Buy = 1 S i < n', Σÿ=1 Buy = We define a Markov chain M = U (w), T) with state set S U {w} and transition matrix T, where S = {V1, V2,...,, Val U (21, 22,,..,; Zul) Further,
Q w 0 1
0 A O
T REIISIIISHHH
QE
DERRIIIISI
B
is the transition matrix of the Markov chain M in canonical form, where w E R| (0, 1, is the vector of transition probabilities to state w. Note that we add here auxiliary state w. which acts as final absorbing state from the root.
Theorem 1. Let M be a tree Markov chain as defined in Definition 7 M is acyclic absorbing Markov chain with w being its only absorbing state. (See proof in App. A.3
Thus, our probabilistic hierarchy defined by A and B describes an absorbing and acyclic Markov chain. In our hierarchical clustering interpretation. a random walk starts at one of the leaves and first randomly transitions to the internal nodes based on A, followed by transitions among the internal nodes via B. Once the root is reached, the random walk is absorbed after one last step to w.
In the remainder, we denote the probabilities arising from the tree Markov-chain as p(M) (-) to distinguish them from their tree-sampling counterparts p (-). In general, the two perspectives are not equal, c.g., when considering pairs of leaf nodes. Here, the Markov chain introduces an independence assumption of pairs of random walks. Under tree-sampling, two leaves' paths to the root are dependent in general, i.e., two paths traversing some internal node Zy implies that all subsequent transitions are identical. While Markov-chain probabilities p(a)(-) (.) often have efficient and analytical solutions grounded in Markov chain theory, is unclear a-priori how leverage them for hierarchical clustering. In the following, we relate central tree-sampling probabilities p()) i.e., (lowest common) ancestor probabilities, to their Markov chain counterparts (.).
3.1 ANCESTOR PROBABILITIES
First, we want to compute the probability ( (7* v2) of an internal node 7 being an ancestor of leaf Vj under the row-wise tree-sampling procedure (see Sec. (.2). We call this ancestor probability.
Theorem 2. Let T () (T. be a discrete hierarchy obtained by tree-sampling. Further, let W(::) be random walk on M rooted in V; resulting in path f.. We have that
Pu v2) = p(zk E f.)) P.M (zk 1v).
(3)
(See proof in App. A.4
Note that any random walk on M must result in path since, because M is acyclic, transient state can be visited more than one time in a random walk. Theorem 2 means that we can use ancestor probabilities arising from the tree-sampling and Markov chain views interchangeably.
3.2 LOWEST COMMON ANCESTOR PROBABILITIES
For the hierarchical clustering problem we are interested in the lowest common ancestor (LCA) of two leaf nodes v; and Vj. which we denote by v, A Vj. The LCAs are required to compute both the Dasgupta cost as well as the Tree-Sampling Divergence (TSD). Therefore, when optimizing for good Dasgupta or TSD scores, it crucial exactly and efficiently compute the LCA probabilities that arise. We denote these ICA probabilities by p(7) (7+ vzAV)). Previous work resorts heuristics in approximating the LCA probabilities (Monath et al. 2019). In contrast, our connection to absorbing Markov chains admits efficient closed-form computation of LCA probabilities, as we now show.
Theorem 3. Let A and B be transition matrices describing a (soft or discrete) hierarchy as intro- duced in Section 2 Let (r( (I.
(T-1) Za:) denote path from leaf V; ( to the root Za', where |ra| = T. Then, the probability of internal node Zu being the lowest common ancestor V; A Vj
..... . ,,,"T
of leaf nodes v, + vj under the rree-samplng procedure from Section 2.2 is
(Zx = =vAAvz)
Σ
p(r:) p(T)),
(4)
4

---

Published as a conference paper at ICLR 2022
where y3 is the part of a path from V; up (and including) internal node Zko i.e. Yi 3.... Zk). (See proof in App. A..
(1)
For ,, an LCA probability is trivially the parent probability, i.., p(z)=v,Av)) p(zz V2). From Eq. (4) it seems that a straightforward way to compute the LCA probabilities is to enumerate the set (;:; 7 V; A V;} of all pairs of potential paths from v; and vj to the internal node & and sum their probabilities. However, this is intractable in practice because the size of the set grows exponentially in the 'depth' of the internal node k (see App. [A.8 Thm. 77. In Thm. we show how to compute the LCA probabilities that arise when sampling pairs of random walks from M.
Theorem 4. Let M be Markov chain defined in Definition [ 7x: be an internal node, and # v, be leaf nodes. Let W(v:). ( be independent random walks on M rooted in v, and V3, respectively. Then, the probability that internal node Zy the lowest internal node (as by the topological order) traversed by both random walks, i.e,, the lowest common ancestor of v: and vj. is
p
(. (ZK [3) = Panc (Zk (2) (z Vj)
Σ
(M -v (3))Pac(22222
(5)
(See proof in App. A.6
Thus, due to the independence of pairs of random walks in the Markov chain M, we can compute LCA probabiliiiees efficiently in closed form the Markov chain. However, the joint ancestor probability (M)) (7& V; Vj) does not reflect the underlying process of sampling T (A, B) ~ PA.B(T) any more, i.e., in general pane (zx Va, Vj) Pane (7x Vz) Pame (Zx (V)) F Pinc (z&lVi, Vz))
As our main theoretical result, we show next that, remarkably, the LCA probabilities obtained from the Markov chain are indeed equivalent the tree-sampling LCA probabilities:
Theorem 5. Let A and B be transition matrices describing a (soft or discrete) hierarchy as described in Sec. The LCA probabilities arising from tree-sampling and the Markov chain are equal, i.e.,
p (Zk = V4 A vy) pl (z (z== Vv))))
(See proof App. A.7
This result is surprising at first, since we made the assumption that pairs of random walks are independent in the Markov chain sampling process. However, recall that two paths in the tree- sampling process are disjoint and independent until they meet at their LCA Z₁. Thus, for this subset of the pairs of paths leading Zk, the independence assumption in M does not lead to an error.
The result is also very useful in practice, since it means that we can use efficient computations from the Markov chain view exactly compute the tree-sampling L.C probabilities. As we show in the following, we can jointly compute I.A probabilities for all pairs of leaves in vectorized way.
3.3 EFFICIENT VECTORIZED COMPUTATION
Definition 2 (Fundamental Matrix). Let M be an absorbing Markov chain and Q in Definition The fundamental matrix N of Markov chain M is
I
A(I (I-BBi B) - 0 (I-B)-
N NERISKIS =
Ni equals the expected number of visits of state j when starting a random walk in state i. Since M is acyclic, each transient state can be visited at most once, i... Nij is the probability of state j being on a random path to the root starting from i. Observing the block structure N in Eq. 77. we define
panc = A(I - A[--B)-1
Fanc E RRa xn'
(8)
Pij Panc (z)lvs) is the probability of internal node z, ending up being ancestor of v, under the tree-sampling procedure. Analogously, pane provides the ancestor probabilities among the internal nodes, i.e. Junc Panc (z,) Note that we subtract the identity matrix in Eq. (8) since the diagonal entries of the fundamental matrix block (I - B) B) are always trivially 1, as they correspond to the probability of traversing an internal node 2ą when also starting from Zę. By subtracting I we obtain the ancestor probabilities by enforcing that an internal node is not its own ancestor. Since B is strictly upper triangular, the inverse (I B1 always exists and is efficient compute in O
5

---

Published as a conference paper at ICLR 2022
Theorem 6.
The vector of LCA probabilities of all internal nodes w.r.t. leaf nodes V, and Vy can be computed in a vectorized way via
PlCA, E E.R'' = (Prt.c @ P (I+ Panc @ pamee=
PLCA
Avi.
(9)
where 2 denotes the element-wise (Hadamard) product. (See proof in App. A.9
Complexity analysis. As show in App. A.P. can exploit sparsity in real-world graphs and
thus do not have construct the full IN _xxxxxn LCA tensor PLCA, This leads complexity of ( x n²²) for both Soft-Das. and Soft-TSD, which is efficient since typically we have n < n. All equations are vectorized and thus benefit from GPU acceleration. More details in App. A.12
3.4 INTEGRAL SOLUTIONS
In App. A.13 A.1.AA.13 we analyze the properties of the relaxed problem Soft-TSD which our method FPH optimizes. We prove in Theorem [00 that the optimization problem is integral, i.e., the global maximum is discrete. This is remarkable, since we are actually optimizing over continuous hierarchies parameterized by and B. This implies that the global maximum the relaxed problem the same as for the combinatorial problem of optimizing over discrete hierarchies. Soft-Das. is not obviously convex or concave, thus not obviously integral.
3.5 FURTHER CONSIDERATIONS
Choice of n'. The number of internal nodes n' is important hyperparameter of our method (as well as most baselines). Similar to, e.g., the number of clusters l k-means, large numbers of internal nodes n' lead more expressive hierarchies, which on the other hand are less interpretable by a human and require more memory and computation. In Fig. 2 we show how the expressiveness (as measured by TSD/Dasgupta) improves for increasing values of n', and in App. B.6 visualize learned hierarchies with different n'. Since FPH typically trains within few minutes, our general recommendation is to use the elbow method (Thordikee (953) determine n'.
Constrained vs. unconstrained optimization. Since our probabilistic hierarchy model leads to fully differentiable metrics (i.e., Soft-Das. and Soft-TSD), we can optimize the metrics in an end-to-end fashion via gradient descent. Note that the matrices A and B are constrained to be row-stochastic; we therefore experiment with two optimization schemes: unconstrained optimization of A and B (e.g. using Adam optimizer and softmax to obtain row-stochastic matrices), or constrained optimization via projected gradient descent (PGD). In our ablation study we found that the PGD optimization consistently leads to better results (sce Fig. 4 We attribute this performance difference to the severe gradient re-scaling in the softmax operation when the parameters become very large or small, leading to very small step sizes (Niculae 2020;; thus, unless otherwise stated, FPH uses PGD optimization.
Scaling to large graphs. For fast training on large graphs on commodity GPUs, we propose a simple yet effective batching scheme. We uniformly pick K random leaves from the graph at each iteration. Then we select the induced subgraph of these K nodes and their neighbors while capping the total number of nodes by some constant C. We then compute the loss and perform the update based on the selected subgraph. By using our batching procedure we do not need to have all parameters on the GPU, which enables scaling to very large graphs
Node embeddings, In our default setting, we directly parameterize the matrices A and B as learnable parameters via gradient descent. That is, the direct parent probabilities p(z+ lv.) and p(zzlzz are the only trainable parameters. As an alternative, we also experiment with learning a node embedding for each leaf and internal node. We compute the parent probabilities A and B via softmax on the negative Fuclidean distances of the embeddings. Given fixed embedding size, this leads to parameterization that scales linearly in the number of leaf nodes and internal nodes.
Initialization. We have found that our model (as well as most of the baselines) can greatly benefit from a "smart" initialization scheme. For the direct parameterization, we have found initializing from the solution obtained from the average linkage algorithm (Jardine & Sibson 1968) to work well. Unless stated otherwise, FPH uses initialization from average linkage. In contrast to vector data, linkage algorithms fast graph data and can be performed in ((m) (Benzécri 1982 Murtagh &
Contreras 2012), thus not affecting the complexity of FPH. In the embedding parameterization we experiment with initializing the embeddings using DeepWalk (Perozzi et al. 2014).

---

Published as a conference paper at ICLR 2022
Dasgupta cost (ower is better)
Normalized TSD (higher is bettec)
Alg.
Ward
Louv.
UF
HyplIC
HGHC
RGHC
Avg. lk.
FPH
Ward
Louv.
UF
HypHC
HGHC
RGBIC
lk.
FVH
712.33
57L64
749.40
556.57
OpenFlight
463.43
488.90
355.61
39.56
57.72
Genes
202.17
247.26
251.01
495.26
306.53
247.07
19% 50
183663
06.30
67.47
62.95
20.66
53.33
51.81
66.72
67.69
Chesserr
92.27
178.23
98.61
215.62
150.26
131.89
85.09
77.16
09 03.43
68.45
67.40
37.22
57.61
50.61
67.50
69.37
Cor ML
281.82
336,86
34286
442.09
411.49
350.00
292.77
254.78
56.47
57.51
53.06
30.73
16.76
12,68
55.30
58.02
PolBlogs
377.63
433.77
25.25
WikiPhysies
736.1
32
753.81
759.07
840.15
74087
658.04
537.95
43
46.03
43.40
32,02
39 29
38. 39.39
43.15
49.97
oghe--nnity
22,870
11.655
52,666
DDM
22,076
24007
20,671
14,354
36.77
37.75
24.75
00M
26.05
25.21
33.64
39.66
oghi-collah
13,835
20.664
807
0OM
34,934
21,067
15,716
13,493
45.3
22.12
27.90
00M
24.80
34,07
45.44
48.36
DBLP
31,138
40,744
148,499
0OM
94,384
44,424
36,463
38.26
40.92
20.21
00M
15.96
27.82
38.99
41.66
Table 1: Hierarchical clustering results (n' 512). Bold/underline indicate best/second best scores.
Avg.
BGHC
HypHC
Wird
120
Desgupa
000
ISD
8
a00
330
8
612
15
5
Num. modlss
Internal
Intervaa
Num.
modes
(a) Dasgupta- Cora-ML
(b) Dasgupta- PolBlogs
(c) TSD Cora-ML
(d) TSD PolBlogs
Figure 2: Hierarchical clustering results measured by Dasgupta cost (lower is better) and TSD (higher is better). More results in Fig. in the appendix.
EXPERIMENTS
Datasets. We use 11 real world datasets (McCallum et al. 2000 Sen et al. 2008 Aspert ct al. 2019
Amunts al. 2013 Cho et al. 2014 Adamic & Glance 2005 Patokallio Wang et al. 2020 Yang
& Leskovee| 2013). including the very large ogbn-products dataset with around 2.3M nodes and 62M edges (Hu al. 2020). We always select the largest connected component (LCC) preprocessing step and convert each graph to an undirected one. We provide further information about the datasets in Table including number of nodes, number of edges and mutual information (MI) between nodes which is an upper-bound on the TSD score (Charpentier & Bonald 2019). In our experiments we report normalized TSD in percent.
Baselines. We compare our method with the following deep learning baselines: Routing Gradient- based clustering (RGHC) (Monath et al.) 2017). Hyperbolic Gradient-based Clustering (HGHC) (Monath et al. 2019), Ultrametric Fitting (UF) (Chierchia & Perret 2019), and HypHC (Chami ct al. 2020). Importantly RGHC, HGHC and HypHC also optimize a relaxed version of the Dasgupta cost. Moreover, we compare to the average linkage algorithm (Avg. link.). as well as the Ward linkage algorithm (Ward) (Ward Jr. 1963). Finally, we compare to the Louvain method (Blondel et al. 2008) (Louvain). For RGHC, HGHC, and HypHC, which require vector data input (as opposed to graphs), we use DeepWalk Walk embeddings as node features. Note that linkage algorithms use the compression scheme introduced in
return a full hierarchy with n'
1. Therefore (Charpentier & Bonald 2019) to reduce the size of the hierarchies to the desired number of internal nodes. See App. B.7 for hyperparameter choices.
For the results on Dasgupta and TSD, we train each baseline 5 times and report results for the best run For all models, we apply a post-processing treatment consisting in pruning unused internal nodes. For FPH, we select for each node its most likely parent to obtain a discrete tree.
4.1 RESULTS
Hierarchical clustering. We report results on hierarchical clustering with n'' = 512 internal nodes in Table [ FPH outperforms all baselines on all datasets on TSD and on all except one dataset on the Dasgupta cost. Remarkably, the average linkage algorithm outperforms most of the deep-learning based baselines. We partially attribute this to the fact that the baselines use DeepWalk embeddings as node altributes.
'Since are not using any label information, this does not lead to data leakage or overfitting on test data; we show standard deviations in Table TT Since FPH is deterministic, we only run once.
7

---

Published as a conference paper at ICLR 2022
Model
Citeseer
Cora
Polblogs
ogbn-arxiv
DBLPP
Avg.
0.367
0.420
0.507
0.216
0.526
RGHC
0,281
0.400
0.730
0.286
0.510
HGHC
0.365
0.379
0.177
0.290
0.408
Ward
0.368
0.504
0.702
0.411
0.591
UF
0,347
0.428
0.676
0.254
0.598
HypHC
0.270
0.121
0.691
0OM
O0M
Louvain
0.329
0.500
0.640
0.395
0.558
FPH
0.398
0,462
0.680
0.251
0.560
FPH (Louv.)
0,380
0.502
0.614
0.399
0.564
FPH (Ward)
0.393
0,516
0.708
0.401
0.604
Table 2: NMI results on real-world datasets. FPH (Louv.) and FPH (Ward) refer to FPH initialized from the solutions of Louvain and Ward, respectively.
Moreover, we noticed that HypHC requires an excessive amount of triplet samples to obtain good results. Even n², as suggested by the authors, performs poorly. We use 50M triplets for all datasets, which is more than 4.5 times the recommended number of n² on Wiki-Physics. This took almost 24 hours to compute, which is why we could not go higher. We clearly see a dependence of HypHC's performance on the number of triplets, as it performs competitively on PolBlogs, our smallest dataset, and poorly on Wiki- Wiki-Physics, the largest dataset on which we were able to run HypHC. In Tbls. 8 show baseline results with DW d 128 embeddings, which did not improve results consistently.
In Figure 2 we show how the models perform for different numbers of internal nodes n'. As expected, the models generally obtain better scores for higher capacity. Again, we observe that FPH performs best across datasets and values of n', highlighting the effectiveness of our approach. Specifically on the Dasgupta cost, FPH substantially outperforms the baselines. This is remarkable since RGHC, HGHC and HypHC also optimize relaxed version of the Dasgupta cost.
External evaluation. As typically have knowledge about ground-truth hierarchies in real- world data, it is difficult to perform external evaluation. To address this, we propose the following:
(i) We compute the normalized mutual information (NMI) between the ground-truth class labels and the learned hierarchies when cutting them appropriately to divide the leaves into the same number of (flat) clusters. We set n' 256 for all models (except RGHC, since ran OOM; we use n' 128 instead) and set FPH to optimize TSD. Note, though, that the node labels are not necessarily solely based on connectivity of nodes, but e.g., also on node attributes. to which the models do not have access. Thus, we cannot expect perfect correlation of "good" hierarchies in the sense of explaining edges in the graph and NMI w.r.t. ground-truth node labels. In Table 2 we show the results; the hierarchies learned by FPH achieve strong scores, highlighting its effectiveness.
(ii) Similarly, we can use the ground-truth clustering from synthetic hicrarchical stochastic block- model (HSBM) (Lyzinski al. 2016) graphs to compute the NMI scores at each level of the hierarchy, We use five HSBM graphs with 100 and 1000 nodes, respectively. The graphs have three levels (see Figs. 7 7 for example graphs) On the small graphs set n' 64; on the large graphs, same settings as in (i). In Table 10 we show the results. FPH outperforms all baselines and is able to recover the ground-truth hierarchies to very high accuracy.
the
Ablation study. In our ablation study, we compare (i) FPH (i.e., with constrained optimization using PGD) vs. unconstrained optimization with Adam (FPH-U) and using softmax; (ii) average linkage initialization vs. random initialization (FPH-R, FPH-UR); (iii) direct optimization of A, B vs. learning node embeddings (FPH Emb.). Here, we experiment with random initialization (FPH-R Emb.) as well as Deep Walk initialization (FPH Emb. DW). The results, obtained on the Wiki- Physies dataset, are displayed in Figure f (App.). We observe that FPH, i.e. constrained PGD optimization of A and B with initialization from average linkage performs best. In similar way, "smart" initialization from DeepWalk tends to improve the results on FPH Emb., too, but the effect less pronounced. In general, FPH variants learning embeddings perform worse than our full version; this may be due to the gradient-rescaliig due to softmax, which we also suspect is a reason why unconstrained optimization achieves weaker results than FPH.
Scalability. We run experiments on the very large graph dataset ogbn-products which has about 2.3M nodes and 62M edges. We train FPH both with n' 5525 and 1024 internal nodes performing batching as explained in Sec. Se3. We show the results in Table 3 FPH outperforms all baselines TSD and is competitive Dasgupta, with both 5/=512 and 1024. Note that we could not compare
8

---

Published as a conference paper at ICLR 2022
Dasgupta
Norm.
TSD
Dataset
FPH
DCSBM
DW
Ad/Ad.
VGAE
n
512
1024
512
1024
Cora-ML
95.7
95.5
94.3
86.5
95.9
Ward
144,157
127,968
37.05
40.59
Citeseer
96.2
93.6
96.0
76.8
94.8
HGHC
219,959
168,851
35.90
39.53
PolBlogs
WikiPhysscs
97.2
94.3
94,9
96.9
92.9
84.8
92.6
96.6
97.0
92.8
RGHC
184,688
35.35
Brain
94.1
95.2
83.8
90.7
93.2
Avg. link.
175,571
168,753
40.33
43.21
OpenFlight
99.3
99.0
94.3
98.4
99.0
FPH
147,169
142,404
43.79
45.57
Genes
69.8
66.9
70.3
53.0
66.6
Table 3: Results on ogbn-products.
Table 4: AUC-PR score (%) for link prediction.
with HypHC, since (a) the implementation constructs dense n X n matrix, which would require more than 14TB memory assuming single precision; (b) sampling n² triplets, as recommended by the authors, would take weeks. Further, we do not report results on UF since it did not converge. RGHC out of memory for n0=1024.
Runtime. Due to the efficient, vectorized computations, a full epoch of a complete dataset to compute Soft-TSD or Soft-Dasgupta using model is very fast. A complete forward pass on Wiki-Physics with 512 internal nodes takes only about 130ms on GPU and about 2s on CPU. On the other hand, a full evaluation on ogbn- proon--ssuuts takes only about 13 minutes (758s) CPU, and training the model on a GPU takes approximately 3.5 hours for 2K epochs (with batching).
Link prediction. As the TSD score be interpreted in terms of reconstruction loss, we can use the scores of the reconstruction scheme in Eq. (25) (App. B. for predicting links. We compare with WeepWalk (DW) and the variational graph autoencoder (VGAE) (Kipf & Welling 2016), where the
link prediction score of two nodes is the cosine of their respective embeddings. Further, we compare with degree-corrected stochastic blockmodels (DCSBM) (Karrer & Newman, 2011) and Adamic Adar (Ad./Ad.) (Adamic & Adar 2001}, which are established strong baselines for link prediction in non-attributed graphs. See App. B.2 for details. Importantly, none of the models use node features, including FPH. As shown in Table FPH achieves best or second-best performance on all datasets. This is remarkable, since FPH is not trained specifically for this task, which highlights the generality and usefulness of the hierarchies discovered by FPH.
Root
Level
Level
Qualitative analysis. In Table we provide insight into our model trained on the Cora-ML dataset. We
neural,
asocs, peneralization, dynamic
genviic, reinforeement, search
show the first three levels of internal nodes of the learned hierarchy. Each cell corresponds to an inter- nal node and contains the three most frequent words of the abstracts of all papers (i.e., leaf nodes) as- signed to the respective internal nodes. Words from node are excluded from its children avoid dupli- cates. Terms tend from more general at the root (c.g., 'problem') towards more specific at the lower levels (e.g., 'memc'). Further, we can identify categories of machine learning approaches, e-g., reinforcement learning (L.2, row 2). symbolic Al (L2, row 4), or variational inference (I.2, row 6). Again, FPH did not see any text information (node attributes) and performed the clustering based citations (edges) alone. Besides offering qualitative evidence that the learned hierarchies are reasonable, this also showcases a potential wollworld application of FPH: scholar can explore the hierarchy of topics in an academic field to discover relevant papers.
networks
paper.
relseming knowledge, planning
tsiiiing
chali,, markow, sampler
series, time, hayesian
leamning, algorislu, problem
giBls, distribition, mome
dimmes, evolutionary. species
hinary, camparison
periect, grapli,, parameterize
technical, report, polynomaa
stahility, systems,
control, gain, corput
proved, injectory, hounded
linear
Iyapnov, state, online
wavelet, minimax, estimation
Table 5: Cora-ML hierarchy visualization.
5 CONCLUSION
We propose a new probabilistic model over hierarchies on graphs which can be learned using end-to-end gradient-based optimization. By drawing connections to absorbing Markov chains we can compute relevant quantities such as lowest common ancestor probabilities exactly and efficiently in vectorized way. For the first time, this allows to directly optimize for relaxed versions of quality metrics for hierarchical clustering such as Dasgupta cost or Tree-Sane pree-Snnl Divergence (TSD) in an end-to-end fashion. Our Flexible Probabilistic Hierarchy model outperforms strong traditional as well as recent deep-leamnig- baase baselines on nearly all datasets and tasks considered and easily scales to massive graphs with millions of nodes.
9

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
Since our method does not directly focus on specific real-world application, good or bad societal outcomes depend on how practitioners and researchers use in practice. This means that it could potentially be abused, e.g., by corporations governments, to identify groups and hierarchies of dissidents via recorded metadata. For instance, phone call metadata routinely collected at scale by service providers and governments. By using our method on the large-scale call graph it could be possible to identify groups of political dissidents and to repress them. On the other hand, we argue that our method can also have positive impact, e.g., by making corpora of literature to users or by enabling scientists, e.g., to discover cliques and hierarchies in biological networks. Moreover, our contribution is algorithmic in nature and does not consider the effects of potential biases or discrimination in the underlying network data.
accessible
REPRODUCIBILITY STATEMENT
For reproducibility and verifiability of our theoretical results, we provide complete proofs of all ten theorems of our work in Appendices A.33 We further make explicit all assumptions derive results. For reproducibility of our experimental results, first highlight that our model's 's core implementation a straightforward PyTorch implementation of the matrix equations in this work. Further, we detail our experimental approach in Sec. and provide hyperparameter choices for our method as well as the baselines in Table 7 in the appendix. For the baselines, we use the authors' official implementations and use the suggested hyperparameters. To compute the Dasgupta and TSD metrics (as well as to obtain the results for the Louvain algorithm), we use the sknetwork Python library Our implementation available at https: / www daml in. tum. de/ fph
and definitions
REFERENCES
Lada A. Adamic and Eytan Adar. Friends and neighbors on the web. SOCIAL NETWORKS, 2001.
Lada A. Adamic and Natalie Glance. The political blogosphere and the 2004 u.s. election: Divided they blog. In LinkKDD, 2005.
Katrin Amunts, Claude Lepage, Louis Borgeat, Hartmut Mohlberg, Timo Dickscheid, MarenEtienne Rousseau, Sebastian Bludau, Pierre-Louis Bazin, Lindsay Lewis, Ana-Maria Oros-Peusquens, N. Shah, Thomas Lippert, Karl Zilles, and Alan Evans. Bigbrain: An ultrahigh-resolution 3d human brain model. Science, 2013.
Nicolas Aspert, Volodymyr Miz, Benjamin Ricaud, and Pierre Vandergheynst. A graph-structured dataset for wikipedia research. In WWW, 2019.
Albert-László Barabási and Márton Pósfai. Nenwork Science. Cambridge University Press, Cambridge, edition, 2016. ISBN 178-1-107-07626-6.
Harold P. Benson. Concave Minimization: Theory, Applications and Algorithms, pp. 43-148, Springer US, Boston, MA. 1995. ISBN
doi: 10.1007/978-1 1-077------11-225---- URL
Jean-Paul Benzécri. Fast hierarchical clustering using reciprocal nearest-neighhor chain algorithm. Notebook of the data analysis, 1982.
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 (10):P10008, 2008
Aleksandar Bojchevski and Stephan Günnemann. Bayesian robust attributed graph clustering: Joint learning of partial anomalies and group structure. In AAAI, 2018.
http::// httel//ccsssoo///o//ee/oo/oo
10

---

Published as a conference paper at ICLR 2022
Thomas Bonald, Bertrand Charpentier, Alexis Galland, and Alexandre Hollocou. Hierarchical graph clustering using node pair sampling. KDD Workshop MLG, 2018.
Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From trees to continuous embed- dings and back: Hyperbolic hierarchical clustering. In NeurlPS, 2020.
Moses Charikar and Vaggos Chatziafratis. Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics. arXiv e-prints, 2016.
Bertrand Charpentier. Multi-scale clustering in graphs using modularity. DiVA, 2019.
Bertrand Charpentier and Thomas Bonald. Tree sampling divergence: An information-theoreet metric for hierarchical graph clustering. In IJCAI, 2019.
Giovanni Chierchia and Benjamin Perret. Ultrametric fitting by gradient descent. In NeurlPS. 2019.
Ara Cho, Junha Shin, Sohyun Hwang, Chanyoung Kim, Hongseok Shim, Hyojin Kim, Hanhae Kim, and Insuk Lee. Wormnet v3: A network-assisted hypothesis generating server for caenorhabditis elegans. Nucleic acids research, 2014.
bypethesis-generatinng
Sanjoy Dasgupta. cost function for similarity- based hierarchical clustering. In ACM Symposium on Theory of Computing, pp. 118-127, 2016.
Michael B. Eisen, Paul T. Spellman, Patrick O. Brown, and David Botstein. Cluster analysis and display of genome- wide expression patterns. Proceedings of the National Academy of Sciences, 95(25) 14833-1488, 1998. ISSN 0027-8424. URL https: //wp:///wwwwwww/ /www pnas org/content/ 95/25/1486)
C. Gower and J. S. Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society: Series C, 1969.
Johan Himberg, Aapo Hyvärinen, and Fabrizio Esposito. Validating the independent components of ncuroimaging time series via clustering and visualization. Neurolmage, 2213):1244-1222. July 2004. doi: 10. www...eerommagee2000..0. neuroi 2004. 03. 027
URL http::::///oi..r//111.0000 10166/
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning Graphs. In NeurIPS, 2020.
N. Jardine and R. Sibson. The Construction of Hierarchic and Non-Hierarchic Classifications. The Computer Journal, 1968.
Sepandar D. Kamvar, Dan Klein, and Christopher D. Manning. Interpreting and Extending Classical Agglomerative Clustering Algorithms using Model-Basee approach. In ICML, 2002.
Brian Karrer and M.E.J. Newman. Stochastic blockmodels and community structure in networks. Physical review. E, 2011.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian
Deep Learning, 2016.
Vince Lyzinski, Minh Tang, Avanti Athreya, Youngser Park, and Carey E Priebe. Community detection and classification in hierarchical stochastic blockmodels. IEEE Transactions on Network Science and Engineering, 4(1):13-26, 2016.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Inf. Retr. 2000.
Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. Gradient-basce hicrarchical clustering. NeurIPS Workshop DISCML, 2017.
Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. Gradient-baig basee hierarchical clustering using continuous representations of trees in hyperbolic space. In KDD, 2019.
11

---

Published as a conference paper at ICLR 2022
Benjamin Moseley and Joshua Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In NeurIPS. 2017.
Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. WIREs
Data Mining and Knowledge Discovery, 2012.
V. Niculae. Optimizing with constraints: reparametrization and geometry. 2020.
Jani Patokallio. Openflight. online https://openfighttsoorg
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In KDD, 2014.
Erzsébet Ravasz and Albert-László Barabási. Hierarchical organization in complex networks. Physical review E, 67(2):026112 12, 2003.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Raa Raad Collective classification in network data. 2008
Michael Steinbach, George Karypis, and Vipin Kumar. comparison of document clustering techniques. KDD Workshop TM, 2000.
Robert L. Thorndike. Who belongs in the family? Psychometrika, 18(4):267-276, Dec 1953. ISSN 1860-0980. doi: 10. 10.000//002288263. /ttptttpee///.....r//000000////0
Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong. and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1): 396-413, 2020.
Joe H. Ward Jr. Hicrarchical grouping optimize objective function. Journal of the American Statistical Association, 1963.
Michael Wick, Sameer Singh, and Andrew McCallum. A discriminative hierarchical model for fast coreference at large scale. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 379-388, Jeju Island, Korea, July 2012. Association for Computational Linguistics. URL https: http:s/s/acaaanthlooooo org/ P12-1040
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181-22 2015.
Yuchen Zhang, Amr Ahmed, Vanja Josifovski, and Alexander J Smola. Taxonomy discovery for personalized recommendation. In ACM International Conference Web Search And Data Mining (WSDM), 2014.
Ying Zhao and George Karypis. Evaluation of hierarchical clustering algorithms for document datasets. In Proceedings of the Fleventh International Conference on Information and Knowledge Management, CIKM '02, pp. 515-524, New York, NY, USA, 2002. Association for Computing Machinery, ISBN 138143 1145/ 01155884792.58535 584877
doi: 10. 10.1145554492..54887, URL
12

---

Published as a conference paper at ICLR 2022
A PROOFS AND THEORETICAL ANALYSIS
A.1 CONTINUOUS VERSIONS OF TSD AND DASGUPTA
Our probabilistic hierarchy model enables us to replace the discrete parent assignments in the Dasgupta cost and TSD with the parent probabilities from the relaxed adjacency matrices A and B. This, in turn, leads to LCA probabilities which are consistent under the tree-sampling procedure. For the first time, this allows us to directly and efficiently optimize for relaxed versions of hierarchical clustering quality metries in an end-to-end fashion instead of proxy losses or heuristic algorithms.
EnWYYv P(vi, Vz) v,)En (p,,,Av,)c(22) c(z) is the number of leaves for which internal node is ancestor, i.e., c(z) Ever [ZEano(v]] Thus, we get
Recall the equation of the discrete Dasgupta cost, Das(T) =
Das
=
Σ P(vi,
Σ 12=vANs Σ [peanctv]]-
Vi,YEV
VVV
We propose the soft Dasgupta cost (Soft-Das) by replacing the indicators Iμ with their expectations, ie., with their associated probabílities:
Soft-Das(PA.(TT) = Σ P(v., vj) Ep(z= Σ Panc (z/v)
V.NjEV
Intuitivelyy Soft-Das is the Dasgupta cost of the expected hierarchy obtained via sampling from Ideally, we would like to optimize
A, B, i.e., (P).)(( = Das(E+-PA the expected Dasgupta cost when sampling discrete hierarchies, i... Exp-Das(PA.B(T))
PP..AT [T) i.e. to put the expectation outside the Das function, which is nontrivial. We leave this extension for future work.
In the same way, we propose differentiable version of the soft Tree Sampling Divergence (Soft- TSD). To this end, we replace the discrete assignments in the distributions p(z) and q(z) with probabilistic assignments, i.e.
Soft-TSD(PA..(TT) = -KT(((2)((())) = Σ p(z) log p(z)
q(z)
where p(z) Σp(z v. v,
V.Ny
((2) = Σ pf
V..y
Analogously above, Soft-TSD effectively computes the TSD score of the expected hierarchy obtained via sampling from A, B. Extending our model to compute Exp-TSD(PA.
Ej-PA. (T)) [TD((T] is left for future work. Note that for both Soft-TSD and Soft-Das we recover the same score as their discrete formulations in the case of a deterministic probabilistic model, i.e. when A and B are binary-valued.
A.2 TREE-SAMPLING PROCEDURE
Recall our assumption that the internal nodes are ordered, and that Bij Of < i. This implies that there are no possible cycles, or equivalently that B is strictly upper- upier-triangular matrix, i.c., it describes directed acyclic graph (DAG). Combined with the fact that each node tree (except the root) has exactly one parent, we see that the sampled discrete hierarchy is indeed tree. We denote this tree-sampling process by T = (Å, B) ~ (T, We can also compute the probability of any tree T under the sampling procedure described above:
PA = (Á,
A
II 6
Bgg
(10)
13

---

Published as a conference paper at ICLR 2022
Note that A and Br are the probabilities of internal nodes Z, and Zy' to be a parent of leaf and internal nodes v, and z respectively while A., and By are equal to these connections exist in the tree T, else 0.
A.3 PROOF OF THEOREM 1
Proof. For M to be absorbing (1) it must have at least one absorbing state, and (ii) at least one absorbing state must be reachable from any state in finite number of steps. For (i), is absorbing its corresponding index in
state since its self-transition probability T& = 1, where k = [S] + the transition matrix T. Thus, once reached, random walk cannot leave the state To show (ii), note that since the transient state transition matrix Q is a strictly upper-triangular matrix, any random walk on M must lead state Zn,. From state Zn,, the random walk transits to with probability wwy = 1. Thus, since ní' is finite, state wa can be reached from any state in a finite number of steps. Further, the only absorbing state since all self transition probabilities of states in S are zero as diag Q) O. Since Q is strictly upper-triame trianglrianguaar none of the transient states can be visited more than once on random walk, and therefore M is acyelic.
A.4 PROOF OF THROREM 2
Proof. We can arbitrarily define the order in which sample from the categorical distributions in A and B because of the independence of the sampling steps. We choose to start by sampling first from A,, i.e., the row corresponding to the leaf node v, under consideration: w(!) Cat(A,). Next, we sample from the row corresponding to w)(1), and repeat until we reach Zj. i.e.
( Cat B (t-))) for 1 <tst
where w(2) Z For the remaining entries, continue in arbitrary order. Observe that (w(1), ..... w(T) are the ancestors of Icaf in T. Further observe that this sampling procedure is identical to how the path f; is generated in the random walk W(v;), completing the proof.
A.5 PROOF OF THEOREM
3
Proof. First, recall that all paths end in the root node, such that r; necessarily ends in 7 (T) When reasoning about the lowest common ancestors, it is no longer sufficient to consider the ancestors (or, equivalently, path the root) of single leaf node in isolation. Instead, we need consider pairs of dependent paths (r:: ry) + j rooted in and v,, respectively. Note that and rj necessarily converge at some internal node 2І V; A Vj - the latest at the root node 2,z-
Thus, we denote with r; (r]
A vj) the first part of the path r; until (and including) its lowest common ancestor with rj. i.e., V; A Vz. Analogously,
(r/ (x1+1) ..... Zw'), such that r, = (I,, 7:). Further, note that the paths ri and ry are on the same underlying hierarchy T, thus Ty. both paths have the same trajectory to the root once they have reached their lowest common ancestor, i.e., they are dependent.
The probability of observing the pair of paths (yi, under the tree-sampling perspective is
Ira
Iral
(
(vs) I
p(r (v))
P
II
pl Ir
(11)
More compactly,
(TTrT)))) p(rz) p(rs) p(TT) = p((r..T))) p(TT) p(( r;)) -((7))
(12)
Importantly, we can see from Eq. 122 that, in general, (T) ((rs, ry)) * p(r:) p(r;) i.e., the paths r, and ry are not independent. We denote pane (74|v,, vj) the probability of the internal node 74 to be the ancestor of leaf nodes v, and v, under the ricessamling perspective. Hence, the probability of the internal node Z to be the ancestor of leaf nodes v, and v, under dependent and independent random walks different i.e. Panc (7 VV, Vz) # Panc Panc(7a (v<Vv))
Punc (7 lVy)) This makes intuitive sense
14

---

Published as a conference paper at ICLR 2022
because knowing that Z is ancestor of and Vj in tree T. additional knowledge that Zk, k: W an ancestor of v, implies that Zy is also an ancestor of v,.
However, for the parts of and ry before they converge, Eq. (2) shows that ((()))))))))
This is because all transitions in r; and ry disjoint thus independent. This is important insight because it means that the probability of observing two paths both converging at internal node 7 factorizes.
A.6 PROOF OF THROREM 4
Proof. We start by reorganizing Eq. (5)
(6i8)
(6)
(13)
Panc (Zk Pan ( plM) (zK V4 (Ay)
p (iM) v, Vy Pane (Zx 1
In words, we can split the event "Z is an ancestor of v; and v;" (i) into two mutually exclusive events: (ii) Zı: is the lowest common ancestor of v; and Vy; or (iii) some internal node lower in the topological order is the LCA of v, and Vj, and further, both random walks also traverse through Zy. (ii) and (iii) are mutually exclusive since exactly one internal node is the LCA for v, and Vj on any two random walks.
Since the two random walks are independent, the probability of 7 being traversed on both walks factorizes. Thus, plre)) (z& vi, yy) Panc (z&) (v, Pane (zx (zx(v,) and therefore is the probability of z being an ancestor of V; and Vj in our Markov chain M.
The events in (iii) can indeed be expressed:
(MM) (ZK- =
Vj, Zi E anc (v:, vý)) = p( (z Vv vz) p(M) (zulzz) E anc (v:, vz))
(14)
where in the last step we exploit that z = V. A vy implies znd E anc (Vs, Vy) as well as the Markov property of the random walks. Further, note that
(M) ( la E anccv,, vy)) = Panc (7xmc(7x122 (zk E anc(v.)) Panc ( E anc(v;)) Panc
(15)
Panc (z [xx)
where we first exploit factorization due to independence and in the last step again the Markov property of the random walks.
A.7 PROOF OF THEOREM 5
Proof. Let A E P(vs), fy E P(v;) be two independent random walks on M rooted v, and v,. respectively. Then,
( (2) = =vA (P.
Σ p((feff)),,
(16)
where A; = (F(1) ..... zx) ) is the first part of A until reaches Zς- Note that the second part of the paths, Fy and F,, which are theoretically independent under our Markov chain model, are marginalized out the LCA formula.
However, due to the independence of the first part of the paths f and fg under both models (see Eq. (4)). we can write:
p (2 = -vA)))=
Σ
p((f. fy))
(F. (
Σ
p(fe) p(f,)
(17)
(FAFF))i -vAAN
= (T v. A Av)). 0
15

---

Published as a conference paper at ICLR 2022
A.8 NUMBER OF PAIRS OF LCA PATHS.
Theorem 7. Let M be Markov chain as defined in Definition The number of pairs of paths from two leaves Vs, Vj for which an internal node Zi is the lowest common ancestor is 3k-1
Proof. Proof by induction over k. For the base case l: the LCA, i.e. directly from V; to Zy and v, to Z₁.. Assume that for internal node Z there are 3R-1 unique pairs of paths for which 2ς. is the LCA. For each of these paths can generate three unique paths for which Z is the LCA. (1) rewire the last transition of v;'s path to go to Z instead of Zд. (2) do the same but for Vz. (3) rewire both v and V last transition go to Z instead of 24- Thus, the number of pairs of paths from V, and V, 7 is 3 3 3
have one pair of paths for which z is
A.9 PROOF OF THEBREM
We provide here the proof for the fast vectorized computation of PLCA in Theorem. Yuy;
Proof. For the case vi e Vj. we start by reorganizing Eq. 9):
amc pane
P.I.A. ViNy
+ P.CA. pano C pane 41,9g
(18)
Note that the inverse (I Pane Pane Pane a strictly upper triangular and therefore nilpotent matrix. The k-th entry thus:
pane is guaranteed to exist and is efficient compute because
pane
pI.CA VENyyN
+
PlCA V.
pane
pane
Plugging in the definitions of Eq. (8) using Theorem and observing that due to the upper triangular structure Pirce = for k' we obtain
k-1 Pane (Zk Vz) Panc (zxlv)) =p(z= vv Σ plzz v A.A))) Pane (zu )
For V; = Vj, we have PICC Viig = Av,, i.e., again simply the parent probabilities of v;-
A. VECTORIZED COMPUTATIONS
All quantities involved in Soft-Das and Soft-TSD can be computed in closed-form based on the Markov chain M and its fundamental matrix. However, their computation should not be done naively, as this involves unnecessary computations. Constructing the full tensor of LCA probabilities is expensive since PL.C E paxaxn' Note, however. that to compute the Soft Dasgupta loss or the distribution p(z) in TSD we only require the LCA probabilities p(z = v; A v2) for pairs of leaves connected by an edge (i.e., P(y;, v2) > 0). That is, we only need to construct an LCA probability matrix of shape mmxx' Thus, we exploit the sparsity of real world graphs, as typically & n².
In a similar way, the computation of the distribution g(z) does also not require the expensive explicit computation of p(z+ v, Vz) for all pairs of leaf nodes. Instead, the Markov chain M. First, observe that the equation of q(z) in Soft-TSD describes an expectation:
again exploit insights from
q(z) Px,s,-Pty [p(z A Av2))
(19)
Defining game p" pane the computation this expectation can be vectorized similarly to Theorem (see derivation in App. A.II):
q (fjano ganc) (p 3 T) pane pan) (I + panc ( pane (p T A.
16

---

Published as a conference paper at ICLR 2022
A.11 VECTORIZED q COMPUTATION.
We provide here the proof for the fast vectorized computation of q in Eq. 19
Proof. We first rewrite the expectation Eq. 19 vectorized form:
PLCA Viyy Pv;
Pv.
where we denote P(vs) Pv;- Subsequently, we can plug the PLCA formula Eq. (9 and pull pv into the Hadamard product which is done over the internal node dimension.
q = Σ
Pv. Pu,Py, (Pree
(I + pane
paney -1
6j
T
Σ Pv.
pane C Σ Pr, Pare
(I + pane
2 panc)=
T
Σ Pv.
Pune Vi
Σe pane Prg
(I+ pane pane
iee
@ p
y
(I +
pane pame)- -1
where sanc =p² _ pane However, recall that for v; = Vy the LCA probabilities are Av, thus, need to correct for this difference to obtain q:
q = Σ Pv, PlCyp Pv, + Σ Pv.
SLCA P.C.P...
143
9 Σ
Pv. PICA
+
Σ Pr. Vi Pv:
+ q = q + Σ pv: PlCA Pv;
Σ
Pr. PLCA Pv: = ④+ Ep.,Au, - Σ pr. P.C.
SICA
= + (p p) A - A-(p p)² PLCA
= =(piee c p
cane T (p p) p)²
panc pan) (I + Pane
panc)= -1 + (p
where PL.CA vc.y
pune pame (I pame
pane
(obtained by using Eq. equation 9).
Note that, unless stated otherwise, we use g as proxy for q in our experiments for simplicity.
A.12 COMPLEXITY ANALYSIS.
Both Dasgupta and TSD computations require compute the ancestor probabilities (Eq. 8) which can be done in On 22 (i.e. inverse of triangular matrix (I B) I=' xn' plus matrix multiplication with A E Ruxn') Then, Soft-Das. the distribution p(z) for the Soft-TSD loss require the LCA probabilities (Eq. for all leaves connected by an edge only, amounting to O n² operations, where m is the number of edges in the graph. Note that similarly Eq. (8), the inverse computation in to
Eq. (9) can be done in O(n²)), Additionally, Soft-TSD requires the computation of q(() ( (complexity O x ))) Both Soft-Das. and Soft-TSD computations are dominated by the O(m X n²²) term.
This leads to efficient time complexity as long we assume small number of internal nodes
n' & n, which reasonable in practice.
A.13 CONVEXITY OF SOFT-TSD
Theorem 8. Let H E [0, 1 xnxn be a tensor whose elements Hgi = p(zz = v. A v2) are the LCA probabilities of internal nodey w.r.t. pairs of leaf nodes. Soft-TSD(H) convex in H.
17

---

Published as a conference paper at ICLR 2022
Proof. Let H H be two LCA probability tensors defined above, and 0 S 1. We first compute the distribution induced by the edge distribution. We have that
p(aH! + (1-a)H
E P(v.,
vy) ki aa)
(1
Σ P(v., v,
kij + +(1 (1- a) a) Σ
P(v,,V) H
(20)
= a
Very
=a (H - a) p (2)
Analogously compute the distribution induced by the independent node distribution. We have that
q(aH k + (1-a)) ( = a q ( () + (1 (1-a) a) ((H) 2)
(21)
We combine this with the well-known fact that KL-divergence convex w.r.t pairs of distributions, i..,
(L(opr (1) on (z) hul.://////aa/aaaa//a//aa///---0
to obtain the desired result:
Coft-TSD(aH (1) + - (1-a) H < ()f + (1 a. Soft- Soft-TSD(H*S (2).
(22)
Theorem 9. Let Hren (H 3A, E H FPH( B)} denote the set of probabilis- tic hierarchies which can be represented by FPH. Here, 2nn, re) are the constraints FPH places on A, B (see Sec. 2). and FPH (A, B) is shorthand the mapping from transition matrices to lowest common ancestor probability tensors defined in Theorems and Here, Hkij = p(zz = V; A Avj) the LCA probabilities of internal nodes w.r.t. pairs of leaf nodes. This set Heru is convex.
Proof. We start by recalling form Theorems 4 and 5 that FPH computes lowest common ancestor probabilities p(zı = V; A Av) from the continuous parent probability matrices A and B such that the LCA probabilities are consistent with the expected result from the tree-sampling procedure described in Sec. A.2 More formally,
Hag == p(zz vv) = (A [L|ZA
V. A vall
(23)
=EA((A,B)
Hus
E
H
kij
where A E {0, 1] x
Xnxn is a discrete hierarchy obtained via tree-sampling from A and B. By definition of the expectation we write
TEE
Σ p(H),B) H.
(24)
HEH(n.n")
where H(n, n²)) ) is the set of all valid discrete hierarchies with n leafs and n' internal nodes. Thus, any continuous hierarchy H learned by FPH is convex combination of discrete hierarchies H. This completes the proof.
Theorem 10.
The Soft-TSD optimization problem solved by FPH is integral. That is, the global maximum of the Soft-TSD optimization problem solved by FPH is the same as the global optimum of the discrete optimization problem of optimizing TSD over discrete hierarchies.
Proof. This follows from Theorems and Theorem 8 establishes that the Soft-TSD objective function convex in the hierarchy tensors H: Theorem proves that the set of hierarchies FPH optimizes over is convex. When maximizing a convex function over convex set, we are guaranteed to find the global optimum at a vertex of the constraint set, which are discrete hierarchies in the case of FPH. Thus, the global maximizer is discrete hierarchy; this discrete hierarchy must also be the maximizer of the discrete TSD optimization problem, since our relaxation optimizes over a superset of all discrete hierarchies.
18

---

Published as a conference paper at ICLR 2022
Dataset
Nodes (LCC)
Edges (LCC)
MI (LCC)
License
PolBlegs. (Adamic Glance 2005
1,222
16,715
2.39
wa
Brain. Ambins 0r 2013
1,770
8,957
3,37
n/à
Citeseer: Scn ol 2008
2,110
3,694
5.69
W/
Gemes C Cho 0r
2014
2,194
2,688
6.12
n/a
Cora-SIL, McCalumm cral 2000
Bojchevski & Gianemina 2018
2,800
7,981
5.23
W/
WiktPhystcs, Aspeit
3,309
31,251
3,44
n/a
Openflight, Fatosallio
3,097
18,193
3,44
ODBL
Oybn produc5, 0ybn-prodic25,
2020
2,385,900 902
61,806,367
9.29
Amazzn license
Ogbn-arxiv, Hral 2020
Wane et
2020
169,343
1,157,799
7,40
ODC-BY
Oybl collab,
2020
Wang
232,865
961,883
9.02
ODC-BY
DBLP. Yang & Leskovee 2015
317,080
1,049,866
9.64
w/a
Table 6: Dataset summary; we convert directed datasets to undirected and select the largest connected component (LCC).
Implications of Theorems 8 and 10 In the previous theorems, we have shown that are maximizing convex function over convex set. In general, maximizing a convex function over convex set is NP-hard (Benson 1995). Thus, cannot hope to efficiently recover the global optimum. However, our continuous relaxation brings several practical benefits for the optimization.
First, observe that directly optimizing over the convex set continuous hierarchies described in Theorem is not practical. This is because there are exponentially many corners of the set, and encoding the constraints of the set is very difficult, Our parameterization (continuous) hierarchies via A. B and being able to efficiently compute the expected lowest common ancestor probabilty tensor enables us to optimize over a fairly low-dimensional and convex set. The constraints on A, B, ie., entries in [0, 1]. unit row sums and upper- trianglri structure of B, are easy to encode and enforce during optimization. This comes at the cost that mapping from A and B to the LCA tensor H is nonconvex (yet describes, per Theorem the optimization problem with off-the-shelf methods such as projected gradient descent and benefit from the elaborate techniques from nonconvex optimization. While in non-discrete local optima during optimization, we can easily obtain a discrete and valid hierarchy given the non-discrete local optimizer via tree-sampling or selecting the most likely parent for all leaves and internal nodes under A and B, as described in Sec. 2.2
convex over hierarchies). Thus, we solve
possible that FPH gets stuck
B EXPERIMENT INFORMATION
B. LINK PREDICTION WITH SOFT-TSD
The TSD can be interpreted in terms of retrieved information when reconstructing the original graph from the tree representation (Charpentier & Bonald 2019). this case, the reconstruction scheme for the edge weights of the reconstructed graph g is:
p(v, A v2)
w(v, v,) = wV.)uu(v)) g(v; A
(25)
B.2 LINK PREDICTION SETUP
For all datasets, we randomly select 10% of edges to hold out for testing while making sure that the graph remains connected. Further, we set n' = 256 and minimize Soft-TSD via FPH. For DC-SBM, we use the Python package 'graph-tool' and follow the documentation? with default parameters to learn the model. For VGAE, we use the default hyperparameters by the authors (one hidden layer, latent dimensions [32, 16), learning rate 0.01, training for 200 epochs). We use the variant described in the paper which replaces the node attributes by the n x n identity matrix. For DeepWalk, we set the embedding dimension to 10.
B.3 DATASET SUMMARY
See Table for an overview of the datasets we used.
https://graph-ttee skewed. de/ http://wweeeeeeeeeecoc/ocoooo/ee
19

---

Published as a conference paper at ICLR 2022
FPI
Avg. link.
RGHC
HIGHC
HyplIC
Ward
000
D iptts
Nomn TSD
000
Num. internal modes
Num. Internal, nodes
Nam. internal modes
Num.. Internal modes
(a) Dasgupta- OpenFlight
(b) Dasgupta Brain
(c) TSD OpenFlight
(d) TSD Brain
Figure 3: Results on hierarchical clustering measured by Dasgupta cost (lower is better) and TSD (higher is better).
PPE-
7PH Enb. DW
FFH-C
FPB-UR
Norm TSD
Dosgupta
30
2-5
522
.3
512
Nam. internal uodes
Num internal nodes
(a) TSD WikiPhysics
(b) Dasgupta WikiPhysics
Figure 4: Ablation study results.
B.4 ADDITIONAL RESULT FIGURES
In Fig. we show results for four more datasets.
B.5 ABLATION STUDY
See Fig 4 for the comparison of different FPH model variants, and our full discussion in Sec. 4.1
B.6 HIERARCHY VISUALIZATION
(a) Dasgupta- 10 clusters
(b) Dasgupta 50 clusters
(c) Das. Dendrogram
(d) TSD 10 clusters
(e) TSD 50 clusters
TSD Dendrogram
Figure 5: Visual comparison of trees obtained after Boft-TSD and Soft-Dasgupta optimization OpenFlight.
We conduct qualitative study of the structure discovered by FPH. In Figure compare the hierarchies learned by FPH when optimizing for TSD or Dasgupta, respectively. We cut at different levels of the dendrogram obtain coarse hierarchy (10 clusters) and fine-grained structure (50
20

---

Published as a conference paper at ICLR 2022
clusters). Comparing Figure (a) and (d). notice that the coarse structure learned by optimizing Soft-Dasgupta looks more appealing. as TSD essentially splits only into the Americas and the rest of the world. At 50 clusters, however, observe the opposite: TSD splits the airports across the world into meaningful, coherent geographical regions, whereas Dasgupta looks mostly unchanged from the coarse version, highlighting the complementarity of both quality metries. In addition, the dendrogram learned by TSD in (f) appears to be of higher quality and more balanced than the Dasgupta dendrogram in (c).
B.7 HYPERPARAMETERS
We use the hyperparameters for models and baselines described in Tab. For smaller datasets, we train FPH for I, 1,000 epochs and restore the best hierarchy after training. For ogbn-products, ogbn- arxiv, ogbl-collab, and DBLP, we train for 2,000 epochs. Similarly, we use different learning rates
Model
Hyperparameter
Value
learning rate
150
FPH (TSD)
Batch size K**
10,000
Batch cutoff C**
200,000
FPH-R (TSD)
Learning
200
Learning rate
0.05
FPH (Das.)
Batch size K
10,000
Batch cutoff C*
200,000
FPH Emb.
Learning
0.1
Routing NN dim Iterations Learning rate
128
RGHC
5000
0.0001
Init. method
K-means + agglom. linkage
HGHC
Iterations
10
Learning rate
0.1
Loss
Closest + cluster size
UF
Epochs
500
learning rate
0.1
Num. triples Epochs
50M
50
HypHC
Learning rate Temperature
0.001
0.1
Embedding dim Embedding dim
10
DeepWalk
32
Used for oigh-pproducts. oghn-arxiv, ogbl-collah, DBLP. Used for ogbn-products
Table 7: Hyperparameter settings.
for A and B for FPH (Das.) ogbn-arxiv, ogbl-collab, ogbn-products, and DBLP (IrA le - 2,
Ir = le (e--)) 9).
B.8 COMPUTING INFRASTRUCTURE
We train all models on a single GPU (NVIDIA GTX 1080 Ti or NVIDIA GTX 2080 Ti, 11 GB memory) in own in-house compute cluster. The machines have 10-core Intel CPUs. We use Python 3 and PyTorch for all our experiments.
B.9 HSBM GRAPHS
We generated HSBMs with n = 100 leaf nodes and n = 1000 leaf nodes for our external evaluation. The small HSBMs have 3 levels with edge probabilities in [.01, .1, .6,, branching factor of and core community sizes in [10, 15). The large HSBMs have levels with edge probabilities in [.001, 01, 11 1,, branching factor in [2, and core community sizes in 35). In Fig. and
21

---

Published as a conference paper at ICLR 2022
Figure 6: Example HSBM graph with n 100, n' 7, and three levels in the hierarchy.
Figure 7: Example HSBM graph with n 1000, n' 53, and three levels in the hierarchy.
Fig. we plot one of the five synthetic HSBM graphs used in our experiments (right), and their corresponding dendrograms (left). The graphs have = 100 and 1000 leaf nodes and three levels of hierarchy.
C ADDITIONAL RESULTS
Dasgupta cost (lower better)
Normalized TSD (higher better)
Alg.
Ward
UF
HypHC
HGHC
RGHC
Ward
HypHC
HGHC
RGHC
Brain
596.73
938.49
568.18
894.87
650.53
32.43
26.28
17.68
17.31
16.54
OpenFlight
416.05
643.45
423.80
477.51
469.98
55,59
49.88
40.06
47.52
45.84
Genes
221.76
258.21
467.12
482.11
444.82
66.87
63.73
23.94
50.59
40.98
Citeseer
105.12
280.66
271.80
224.63
200.91
69.28
62.95
31.74
52.53
47.66
Cora-ML
301.47
673.27
441.21
516.87
499.49
57.22
47.96
29.10
42.10
35.19
PolBlogs
383.51
726.34
334.69
428.52
376.94
27.01
10.73
21.60
20.30
20.78
WikiPhysics
808.87
958.20
701.14
919.27
790.39
45.54
41.55
33.85
34.51
36.51
ogbn-arxiv
22,046
64,950
OOM
37.177
26.286
37.43
26.22
OOM
17.55
25.20
ogbl-collab
14,834
101,562
OOM
112,048
17,964
45.20
30.50
0OM
11.11
37.73
DBLP
33,349
160,742
OOM
171,975
41,796
38.87
22.62
OOM
5.61
29.9
Table 8: Hierarchical clustering results (n' = 512, d = 128).
22

---

Published as a conference paper at ICLR 2022
Model
Citeseer
Cora
Polblogs
DBLP
ogbn-arxiv
RGHC
0.218
0.394
0.756
0,510
0.358
HGHC
0.304
0.362
0.604
0.655
0,385
Ward
0.363
0.445
0.436
0.587
0,402
UF
0.180
0.242
0.102
0.395
0.143
HypHC
0.285
0.390
0.740
Table 9: NMI results for d = 128 Deep Walk embeddings.
n1 100
n
1000
Model
Level
Level 2
Level
Level 1
Level
Level 3
Avg.
0.985
0.952
0.791
0.990
0.978
0.965
RGHC
1.0
0.881
0.766
0.567
0.897
0.745
HGHC
0.874
0.872
0.705
0.840
0.942
0.786
Ward
1.0
0.975
0.765
0.991
0.841
UF
1.0
0,921
0.707
1.0
0.987
0.791
HypHC
1.0
0.892
0.768
0.933
0.846
0.702
Louvain
0.693
0.955
0.795
0.678
1.0
0.993
FPH
1.0
0.994
0.829
1.0
0,994
Table 10: NMI results synthetic HSBM graphs.
TSD standard deviation
Dasgupta standard deviation
Alg.
HypHC
HGHC
RGHC
HypHC
HGHC
RGHC
Brain
0.53 (3%)
0.06 (<0.5%)
0.6 (3%)
19.96 (3%)
38.56 (5%)
14.18 (3%)
OpenFlight
1.15 (3%)
0.4 (1%)
0.7 (2%)
26.61 (6%)
31.14 (6%)
23.9 (5%)
Genes
0.61 (3%)
0.12 (40.5%)
1.19 (2%)
13.3 (3%)
2.88 (1%)
17.31 (7%)
Citeseer
0.19 (1%)
0.09 (<0.5%
1.29 (3%)
6.93 (3%)
5.56 (4%)
8.02 (6%)
Cora-MI
0.96 (3%)
0.13 (40.5%)
0.61 (1%)
17.39 (4%)
21.78 (5%)
12.98 (4%)
PolBlogs
0.13 (1%)
0.09 (c0.5%)
0.18 (1%)
4.04 (1%)
(1%)
3.4 (1%)
WikiPhysics
0.47 (1%)
0.14 (<0.5%)
0.56 (1%)
5.77 (1%)
6.83 (1%)
30.88 (4%)
ogbn-arxiv
0.15 (1%)
1.31 (5%)
405 (2%)
765 (3%)
ogbl-collab
0.16 (1%)
0.61 (2%)
1,592 (5%)
625 (3%)
DBLPP
0.47 (3%)
0.81 (3%)
2,482 (3%)
1,005 (2%)
Table 11: Standard deviations of non-deterministic baselines. In parentheses report the standard deviation in relation to the best value reported in Table in percent.
23


Reviews:
[{"review_id": "yEpediF9J_b", "reviewer": "Reviewer_knNt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of hierarchical probabilistic clustering inference from the trees seems novel and interesting. Dasgupta loss is a relatively new development in the clustering literature; the contributions of this work are timely.\nNote: since this is an emergence review, I did not check correctness of the proofs in the Appendix. \n\nThe experimental section is very unconvincing, however. The comparisons are performed only wrt. primitive graph clustering methods; for instance, in a graph clustering paper I would expect to find heuristic greedy modularity optimization (Blondel et al., 2008), hierarchical SBM fitting, and possibly some non-hierarchical algorithms.\n\nCrucially, the metric space clustering baselines are given very suboptimal features for the clustering: DeepWalk's d=10 is far too low. The original DW paper uses d=128 for all graph sizes, and neural embedding-based models are known to perform poorly in low dimensional regime.\n\nThe scalability of the method is concerning as well. While the paper claims scalability, it is only being evaluated on one large-scale dataset, which is not supporting the claim.\n\nBased on two findings above, I am ready to raise my score, given that the paper is updated with:\n- A re-run of the experiments, or at least a sample of them (Table 2), with d=128, as is default for DeepWalk.\n- A comparison (Tables 2-3, and possibly 5) some classical graph baselines for clustering, including Louvain.\n- Results from OBG-arXiv to Table 2, and add at least one-two more medium-scale dataset (# of nodes 50k+) without graph subsampling tricks.\n\nIn the current state, it is very hard to find support for the claims in the paper experimentally. I am sorry for asking quite a lot in a short timeframe; I hope the authors/ACs do understand my reasoning. In case authors think my asks are unreasonable, please suggest some alternative ways to prove the points that are currently weak.", "summary_of_the_paper": "The paper proposes a probabilistic clustering method based on two losses: Dasgupta loss and Tree-sampling divergence. A scalable sampling-based optimization is proposed. The modes is optimized with the projected gradient descent.", "summary_of_the_review": "The idea and the model in the paper sound reasonable; however, the experimental results are very unconvincing: (1) Three of the baselines are operating on the embedding of the data potentially built by an ill-configured model (2) the claimed scalability is only empirically supported on *one* dataset of size 100000 (3) there is a ton of missed baselines from the graph clustering literature.\n\nAfter seeing the rebuttal I raise my score to the accept category.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qkXhSWw4PU", "reviewer": "Reviewer_8G7Q", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1) This paper is well-written and organized. The notations used throughout the paper is consistent and easy to follow. 2) Instead of providing a heuristic driven method, this method proposed in this paper has solid theoretical supports. 3) The model optimizes directly for the objectives in an end-to-end fashion. It is scalable and achieves state-of-art performance compared with both past and current baselines. 4) The experimentation setting is complete and very informative. \n\nHowever, the implementation part could add more details. Also, the implementation/code is claimed to be present in the supplement materials but it is not.", "summary_of_the_paper": "The paper proposes a probabilistic model of tree-based hierarchical clustering by considering a continuous relaxation. The authors establishes the theorical connections between tree-sampling and the Markov chain that is specifically constructed. This allows an end-to-end gradient-based learning to optimize the internal metrics of graph clustering, namely the Dasgupta cost and Tree Sampling Divergence. This method allows efficient and effective modeling of the graph clustering. Extensive experiments results on different types of graph, including some of the large scale ones, suggests the proposed method behave favorably. ", "summary_of_the_review": "This paper proposes a novel graph clustering method with solid theoretical supports and strong practical performance. The paper itself provides complete reasonings of the motivations and derivations. Overall, it is a impressive paper that brings huge improvement to an important problem of graphs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "kOSQYlRG3kJ", "reviewer": "Reviewer_1sXn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Among the strengths of this paper I can mention that: \nUsing the adjacency information of the graph structure to identify tree-based hierarchies can be useful and computationally a good strategy as proved in other works.\nThe use of a Markov chain over the tree defines an acyclic chain that could be used for inference. \nThe block formulation of the vectorized computation could be useful for efficient implementations.\nWith respect to the weaknesses, there are a few items that could be clarified. Namely:\nThe paper states that in early experiments “PGD optimization leads to faster and better convergence” can you ellaborate what the early experiments entailed?\nThe paper states that the baselines were trained 5 times and results were reported for the best run, could you also report the variance for the baseline and the proposed model to have an estimate of the stability of the results?\nWhy were only a few datasets selected to report in certain experiments? e.g. in Table 2 only three datasets appear.", "summary_of_the_paper": "This paper presents a hierarchical clustering over graphs using a probabilistic model via continuous relaxation of the discrete tree-based hierarchies. It uses two metrics the Dasgupta cost and the Tree-Sampling Divergence. The paper presents an efficient vectorized computation and discusses several details on the choice of hyper parameters. The article presents empirical evaluation on 8 real datasets and compares the technique with several baselines on hierarchical clustering (using NMI), comparing also results on controlled clusters (ground truth class labels, synthetic stochastic block-model) and link prediction (best or second based performance), as well as on meta-analysis which includes ablation, scalability, runtime, and a qualitative assessment.", "summary_of_the_review": "The paper has some strengths that could be useful in applications of graph or network clustering and inference. I find the continuous tree-based hierarchy and associated Markov chain interesting and results promising. I do have some reservations about some decisions made about what to report as I highlighted above. Overall, it may be an interesting addition to ICLR if the authors can improve on the weaknesses I pointed out.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors introduce a novel probabilistic hierarchical clustering method for graphs. In particular they design an end-to-end gradient-based learning to optimize the Dasgupta cost and Tree Sampling Divergence cost at the same time.

Overall the paper presents solid results both from a theoretical and experimental perspective so I think it is a good fit for the conference and I suggest accepting it.
Decision: Accept (Poster)