Unit Ball Model for Embedding Hierarchical Structures in the Complex Hyperbolic Space
Authors: Huiru Xiao
Caigao JIANG
Yangqiu Song
James Y. Zhang
Junwu Xiong
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Complex hyperbolic embeddings
taxonomy embeddings
representation learning for hierarchical structures

Abstract: Learning the representation of data with hierarchical structures in the hyperbolic space attracts increasing attention in recent years. 
Due to the constant negative curvature, the hyperbolic space resembles tree metrics and captures the tree-like properties naturally, which enables the hyperbolic embeddings to improve over traditional Euclidean models. However, many real-world hierarchically structured data such as taxonomies and multitree networks have varying local structures and they are not trees, thus they do not ubiquitously match the constant curvature property of the hyperbolic space. To address this limitation of hyperbolic embeddings, we explore the complex hyperbolic space, which has the variable negative curvature, for representation learning. Specifically, we propose to learn the embeddings of hierarchically structured data in the unit ball model of the complex hyperbolic space. The unit ball model based embeddings have a more powerful representation capacity to capture a variety of hierarchical structures. Through experiments on synthetic and real-world data, we show that our approach improves over the hyperbolic embedding models significantly.

Unit Ball Model for Embedding Hierarchical Structures in the Complex Hyperbolic Space
Anonymous Author(s)
Affiliation
Address email
Abstract
Learning the representation of data with hierarchical structures in the hyperbolic space attracts increasing attention in recent years. Due to the constant negative curvature, the hyperbolic space resembles tree metrics and captures the tree-like properties naturally, which enables the hyperbolic embeddings to improve over traditional Euclidean models. However, many real-world hierarchically structured data such as taxonomies and multitree networks have varying local structures and they are not trees. thus they do not ubiquitously match the constant curvature property of the hyperbolic space. To address this limitation of hyperbolic embed- dings, we explore the complex hyperbolic space, which has the variable negative curvature, for representation learning. Specifically, we propose to learn the em- beddings of hierarchically structured data in the unit ball model of the complex hyperbolic space. The unit ball model based embeddings have a more powerful representation capacity to capture variety of hierarchical structures. Through experiments on synthetic and real-worle data, we show that our approach improves over the hyperbolic embedding models significantly.
10
11
12
14
Introduction
16
Representation learning of data with hierarchical structures is important machine learning task with many applications, such as taxonomy induction (Fu et al., 2014) and hypernymy detection (Shwartz et al. (216)). In recent years, the hyperbolic embeddings (Nickel and Kiela, 2017 (018)) have been proposed to improve the traditional Euclidean embedding models (Nickel et al. 2011 Bordes et al.. 2013). The constant negative curvature of the hyperbolic space produces several manifestations, where the most desirable property for representation learning is that the hyperbolic space can be regarded
18
20
21
22
continuous approximation capable of embedding any finite tree while preserving the distances approximately (Grromov) 1987). As result of the tree-like properties, the hyperbolic space is more suitable embed hicrarchically structured data than Euclidean space.
trees (Krioukov al., 20T0). The hyperbolic space is
24
25
26
However, the real-world hierarchically structured data usually not trees since they can have varying local structures while being tree-like globally. For example, although the taxonomies such as WordNet (Miller 1995) and YAGO (Suchanek et al. (007)) have underlying hierarchical structures,
28
30 they contain many I-m (1 child links to multiple parents) cases and multitree structures (Griggs et al., 2012), which are much more complicated than trees. Thus, the general hierarchically structured data cannot ubiquitously match the constant negative curvature property of the hyperbolic space.
31
32
To address the challenge, in this paper, present hierarchically structured data. Specificallyy we embed the data with hierarchical structures into the unit ball model of the complex hyperbolic space. The unit ball model is projective geometry based
approach to learning the embeddings of
34
36 model to identify the complex hyperbolic space. One of the main differences between the complex
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 and the real hyperbolic space is that the curvature is no longer constant in the complex hyperbolic
38 space. Instead, it has the variable negative curvature. In practice, the variable negative curvature
39 makes the unit ball model based embeddings more flexible in handling varying structures while the tree-like properties retain the superiority in hierarchies.
40
41
For empirical evaluation, we first compare our approach with the hyperbolic embedding methods on tree structures show that the complex hyperbolic space maintains the tree-like properties. Then we evaluate our approach and the baselines on various hierarchically structured data, including synthetic graphs and real-world taxonomies. The experimental results demonstrate the advantages of our approach. To summarize, our work has the following main contributions:
42
43
44
45
48
1.
We present a novel embedding approach, which takes advantage of the variable negative curvature of the complex hyperbolic space, to handle data with complicated and various hierarchical structures. To the best of our knowledge, our work is the first to propose complex hyperbolic embeddings.
47
48
49
50
2. We introduce the embedding algorithm in the unit ball model of the complex hyperbolic space. We formulate the learning and Riemannian optimization in the unit ball model.
51
52
3. We evaluate our approach with experiments on an extensive range of synthetic and real- world data and show the remarkable improvements of our approach.
53
2
Related work
54
55
Hyperbolic embeddings. Hyperbolic embedding methods have become the leading approach for representation learning of hierarchical structures. (Nickel and Kiela 2017) learned the representations of hierarchical graphs in the Poncaré ball model of the hyperbolic space and obtained high-quality embeddings for taxonomies. (Ganea et al.) 2018a) introduced the hyperbolic entailment cones to formally define the partial ordering relation. (Nickel and Kiela| 2018) proposed to learn the embeddings in the hyperboloid model (also known as the Lorentz model) of the hyperbolic space to avoid the numerical instabilities of the Poncaré ball model. These methods learned the hyperbolic embeddings by Riemannian optimization (Bonnabel, 2013). which was further improved by the Riemannian adaptive optimization (Bécigneul and Ganeal 2019). Additionally, (Yu and Sa 2019) used an maseer-based tiling to solve the numerical instabilities in the hyperbolic embeddings.
56
57
58
59
60
61
62
64
65
Another branch of study (Sala et al. 2018 Sonthalia and Gilbert 2020) learned the hyperbolic embeddings through combinatorial construction. Instead of optimizing the soft-ranking loss by Riemannian SGD to preserve the hierarchical relationships as in (Nickel and Kiela| [017]] 2011)). 2 the construction- reconstruction task. Remarkably, TreeRep (Sonthalia and Gilbert 2020) can exactly recover the original tree structure when the given graph is tree. However, both the optimization-based and construction- based hyperbolic embeddings suffer from the limitation in hicrarchical graphs with varying local structures. To tackle the challenge, (Gu et al. 2019) extended the construction based method by jointly learning the curvature and the embeddings of data in product manifold. Although it can provide a better representation than a single space with constant curvature, it is impractical to search for the best manifold combination among enormous combinations for each new structure.
66
67
68
methods minimize the reconstruction distortion and focus on the graph
69
70
71
72
73
74
75
76 Note that our complex hyperbolic embedding model is different from the hyperbolic embedding methods (Nickel and Kiela, 2017 2018) or the product manifold embeddings (Gu et al. (2019) since the geometrical spaces are typically of different characteristics. The nedimenniinal (n-d) complex hyperbolic space is not simply the 2n-d hyperbolic space or the product of two n-- hyperbolic spaces. Section will show that their geometries differ markedly.
78
79
80
81 Motivated by the promising results of previous works, extensions to the multi-relational graph
82 hyperbolic embeddings (Balazevic et al., 2019; Chami al. 2020, Sun et al.
2020) and hyperbolic
83
neural networks (Ganea et 20118b Gülçehre et al. 2019] Liu et al. 2019 Chami et al., 2019 Dai
84 et al. 202T; [Shimizu et al., (222)) were explored. Notably, (Chami et al.
[219 (020)) leverages
85
the trainable curvature to compensate for the disparity between the actual data structures and the
86
corssare- hyperbolic space, where each layer in the graph neural network or each relation
87 in the multi-relational graph has its own curvature parameterization. Since we only focus on the
88 single-relation graph embeddings and taxonomy embeddings in this work, we do not evaluate the
89 multi-rclational knowledge graph embedding models or the neural networks in our tasks.

---

90
Complex embeddings. The traditional knowledge graph embeddings were learned in the real Euclidean space (Nickel et al. 201T, Bordes et al., 2013 Yang et al. 2013) and were used for knowledge graph inference and reasoning. In recent years, several works suggested utilizing the complex Euclidean space for inferring more relation patterns, such as ComplEx (Trouillon et al.) 2016) and RotatE (Sun et al.] 2019). The computation operations and transformations in the complex space have been demonstrated to be effective in the knowledge graph embeddings. The success of the complex embeddings reveals the potential of the complex space and inspires us to explore the complex hyperbolic space.
91
93
94
96
97
Preliminaries
98
99
3.1
Curvature
100
Before introducing the hyperbolic geometry and the complex hyperbolic geometry, we need to give the definition of curvature, which describes the curve of Riemannian manifolds and controls the rate of geodesic deviation. In this paper, curvature refers to the sectional curvature.
101
102
103
Definition (Curvature). Given a Riemannian manifold and two linearty independent tangent vectors the same point, u and v, the (sectional) curvature defined as
104
(R(u, v)v, u) K(u, v) uv. (u.v)?'
where R is the Riemann curvature tensor, defined by the convention R(u, v)w V.w. 105
106
V. V aww V "n.v]
107
3.2
Hyperbolic geometry
Hyperbolic spacq is homogeneous space with constant negative curvature. Here constant means constant both at all points and in all pairs of directions. In the hyperbolic space ( of dimension and curvature K < 0, the volume of ball grows exponentially with its radius p:
109
vol vol(Bug(()(P)) e (n=K(n
111
Contrastively, in the Euclidean space EE, the curvature is 0 and the volume of a ball grows polynomi- ally with its radius:
(B I(
p" pp"
113 The exponential volume growth rate enables the hyperbolic space to have powerful representation capability for tree structures since the number of nodes grows exponentially with the depth in tree, while the Euclidean space is too flat and narrow to embed trees.
115
116
3.3
Complex hyperbolic geometry
117
Complex hyperbolic space is a homogeneous geometry of variable negative curvature. Its ambient
Hermitian vector space C is the complex Euclidean space C*+1 endowed with a Hermitian form
118
(z, w),, where z, w E @n+1 Then the Hermitian space Cn.l can be divided into three subsets: {z E C C z) 0}. Vo = (z C
119
{0) (z) z)) 0}, and V+ {z C². ((z z)) >
120
0}. Let IP be projection map P. C {zn+1
0] C" i.e.,
$1/ $1/2n+1 Zn+1
P
where 2n+1 #
(3)
1n++1
L 2n/2n111
122
Then the complex hyperbolic space Hi and its boundary OHE are defined using the projectivization:
H
PV.
PV,
(4)
The curvature of the complex hyperbolic space is summarized by (Goldman 1999) follows:
In this paper, we use hyperbolic space refer to real hyperbolic space and hyperbolic embeddings to refer real hyperbolic embeddings for avoiding wordiness.
3

---

124
Theorem 1. The curvature is not constant in H.. It is pinched between -1 (in the directions of complex projective lines) and - (in the directions of totally real planes).
125
128
We leave the full proof in Appendix A. The non-constant curvature, which we expect to be favorable for embedding various hierarchical structures, is one of the main differences between Hü and the real hyperbolic space H.S.
127
128
The complex hyperbolic space also has the tree-like exponential volume growth property. The volume of a ball with radius in HH is given by
130
vol Bug (p)) 8d 0nn-1
8" 8" cxP,
sinh 20 (p/2)
(5)
2n
2n
where 22 2mn /n! is the Fuclidean volume of the unit sphere 52n-1 C".
132
From the properties of the complex hyperbolie geometry, we expect that the complex hyperbolic space can naturally handle data with diverse local structures in virtue of the variable curvature as presented in Theorem [
134
while preserving the tree-like properties as shown in Eq. (5)
Unit ball embeddings
135
We propose to embed the hierarchically structured data into the unit ball model of the complex hyperbolic space. In this section, We introduce our approach detail.
137
138
4.1
The unit ball model
139
The unit ball model is one model used to identify the complex hyperbolic space, which can be derived via the projective geometry (Goldman 1999). We now provide the derivation sketch.
140
Take the Hermitian form of C in Section 3.3 to be a standard Hermitian form:
141
(z. w 21
2n M/ 2n Mx++1;
(6)
142 where w is the conjugate of w. Take 2n+1 = 1 in the projection map IP in Eq. can derive the formula of the unit ball model:
B then from Eq.
(4
B (E Fn, 1)][21)
Fnz
+ |zz 1}:
144 where is the Euclidean norm.
145 The metric on B is Bergman metric, which takes the formula below in 2-d case:
ds 4
(12, 2)) ((2,, dz
(dz, 2)) (dzz, dz))
det
(8)
(z, 2)
146
The distance function on B is given by
d (z, w) = arcosh(2 (z, w/) w. z) (2, ()) (ww w)
1),
(9)
where the Hermitian form (z. w)) is defined in Eq. (6).
4.2
Embeddings in the unit ball model
149
Given the hierarchical data containing a set of nodes X
im and a set of edges E ((T "y)( Zig X}. we aim to learn the embeddings of the nodes {2p]y where z, E B3
150
151
The objective of the embeddings is to recover the structures of input data, including the distances between the nodes well the partial order in the hierarchies. Here adopt the soft ranking loss used in the Poincaré ball embeddings (Nickel and Kiela (017)) and the hyperboloid embed- dings (Nickel and Kiela 2018), which aims preserving the hierarchical relationships among nodes:
153
154
155
dag (kp.
Σ (E
log EmeEN(a day (2))
(10)
4

---

Algorithm RSGD of the unit ball embeddings.
Input:
initialization _ number of iterations T, learning rates (1)
for / - to T do
ödgg
0dgg
Compute 8x and by by Eqs. 14 and 150.
Compute (ZL(Z) and VRL(Z) by Eq. 13
Update (+) by Eq. 17 end for
156
where (appp) = { (Ip, 2x) & E U {xpp is the set negative examples for xp together with
Tp. døg the distance function in the unit ball model given in Eq. (9). The minimization of L makes the connected nodes closer in the embedding space than those with no observed edges.
157
158
Note that instead of manually setting the curvature of the learning space or training the curvature as extra parameters, we learn the embeddings directly in the complex hyperbolic space, where the curvature is variable. The learned embeddings are located in different submanifolds of the unit ball model, whose curvatures are different.
160
162
163
4.3
Riemannian optimization in the unit ball model
164
We learn the embeddings Z = +Zp) through solving the optimization problem with constraint:
Z + arg min L
s.t.VZ, E Z, Zp
B
(11)
185
For the optimization problems in Riemannian manifolds, (Bonnabel 2013) presented the Riemannian stochastic gradient descent (RSGD) algorithm, which we employ optimize Eq. (TT). To update an embedding 8 2 we need to obtain its Riemannian gradient V n- Specifically, denote Tx as tangent space of z, then the embedding updated the 1-th iteration by
186
188
z (1) + z (1-1) n7 ( RRL(z).
(12)
where (1()) is the learning rate at the t-th iteration and V VRL(z) T& is the Riemannian gradient of Lzz). Then the Riemannian gradient VR can be derived from rescaling the Euclidean gradient V g with the inverse of the metric tensor ds² and applying the chain rule of differential functions:
170
VRL(Z) 1 ds
1
0L(z)
VEL(Z)
V VEdgg (z, w),
(13)
ds² Odge (z, w)
172 where ds2 in Eq. and OL(2) is trivial compute from Eq. Ödgg (x.w)
10
In practical training, implement and compute the complex hyperbolic embedding as its real part 174 and imaginary part, i.e., z = x + iy, where represents the imaginary unit, i.e., 12 = -. In order to get the gradient of the distance function Vgdgy (z, w) in Eq. (13.. get the partial derivative with
regard to the real part and the imaginary part, i.e., V VEdgy (z, w) adgg (z.w) adgg (a.w)
176
8x
by
177 The partial derivatives of the unit ball model distance take the following formulas: Odga
Re(((z, ((z, w//w) (2,,2) (w, w))
(zz w)) (ww, z))xx (z, x))² ((w, w))
(14)
0x
V2²
Ödg
4
(iz, w)) ((w, z))y Lmr( (iz, w)) w)
(15)
Oy
V 2
(2, x)) (ww w)
(2, z)) (ww, w))
178 where p = cos (z, w)). Re(-) and (-)) denote the real and the imaginary part respectively.
179 The full derivation of Eqs. (14) and (15) is given in Appendix B.
180 Since the embedding z should constrained within the unit ball model, we apply the same projection
strategy (Nickel and Kiela 2017) via small constant 8:
z 2|z - 5) if 2
proj
(16)
z
otherwise.
Here omit the subscript of 2p for concision.
5

---

Table 1: The real-world datasets statistics.
ICD10
YAGOs-wikiOhjeats
WordNet-noun
Nodes
19.155
17,375
82,
Edges
78,357
153,643
743,086
Depth
16
20
Training edges
70,521
138,277
668,776
Valid/Test edges
3,918
7,683
37,155
6 6-hyperbolicity
0.0
1.0
0.5
182
To sum up, the update of z at the t-th iteration
+ proj (-1) -1'' = proj(z -
V L()))
(17)
ds?
183
The RSGD steps of the unit ball embeddings are presented in Algorithm
Experiments
184
185
In this section, we evaluate the performances of our approach tree structures and various hier- archical structures, including synthetic graphs and real-world taxonomies. We focus on the graph reconstruction and link prediction tasks. For more experiments, please refer to Appendix D.
186
187
188
5.1
Experimental settings
5.1.1
Data
190
We synthetic and real-world data that exhibit underlying hierarchical structures evaluate our approach. The details are as follows.
131
Synthetic. We generate various balanced trees and compressed graphs using NetworkX package (Hag) berg et al. 2008)) For balanced trees, we generate the balanced tree with degree r and depth h. For nodes and then aggregate their edges to form
193
compressed graphs, generate & random trees a graph. Some examples of the synthetic data are given Appendix D.1.
195
196
ICD10. The 10-th revision of International Statistical Classification of Diseases and Related Health Problems (ICDI0 4 (Brämer 1988) medical classification list provided by the World Health Organization. The classification list forms a tree structure. We construct its full transitive closure as ICD10 dataset.
197
199
YAGO. Mahdisoltani et al. 2015) is huge semantic knowledge base. provides a taxonomy derived from Wikipedia and WordNet. We extract the Wikipedia concepts and entities that are descendants of (wikicat Objects) as well as the hypernymy edges among them. We compute the transitive closure the sampled taxonomy to construct the YAGO3-wikiObjees dataset.
200
201
202
203
204
WordNet-noun. WordNe (Miller 1995) is large lexical database. The hypernymy relation among all nouns forms a noun hierarchy. We use its full transitive closure the WordNet-noun dataset.
206
For each real-world dataset, we randomly split the edges into maiin-vlidation--ess sets with the ratio 90%:5%:5%. We make sure that any node in the validation and test sets must occur in the training set since otherwise, cannot predicted. But the edges in the validation and test sets not occur training set since they disjoint. We provide the statistics of the real-world datasets in Table The Gromov's 's 9-hyperbolicity (Gromov) 1987p measures the viceliieness of graphs (refer to Appendix for definition). The lower corresponds to the more tree-like graph and trees have 0 o-hyperbolicity.
208
210
212
5.1.2
Tasks
213
evaluate the following two tasks:
hatpee//ygo-knoolleee..oom http:::/wordnet.priieeee htw.:/ordddet..rrrcccoooeeeeeeld

---

214
Graph reconstruction. We train the embeddings of the full data and then reconstruct it from the embeddings. The task evaluates representation capacity.
215
216
Link prediction. We train the embeddings on the training set and predict the edges in the test set. The task evaluates generalization performance.
218
5.1.3
Baselines
219
We compare our approach UnitBall to the following methods: the sate-of-the-ars combinatorial construction-basee hyperbolic embedding method TreeRep (Sonthalia and Gilbert, 2020), the
220
221
optimization-bazt hyperbolic embeddings in the Poincaré ball model (Nickel and Kiela 2017) ) and
the Hyperboloid model (Nickel and Kiela 2018), the simple Euclidean embedding model using the same loss function with (Nickel and Kiela 2017 2018). Recall that we use the same loss function with Poincaré and Hyperboloid but learn in the unit ball model. Therefore, the comparisons among UnitBall, Poincaré, Hyperboloid. and Euclidean reveal the representation capacities of different geometrical models in different spaces.
223
225
227
For the baselines, we use their public codes to train the embeddings. For all methods, the hyperparam- eters are tuned on each validation set for link prediction task and on balanced tree-(15,3) for graph reconstruction task. The hardware information given in Appendix D.2 and the hyperparameters are listed in Appendix D.3. In all experiments, report the mean results over 5 rumning executions. The code of our approach will be publicly available after the publishing of the paper.
229
231
232
5.1.4
Evaluation
233
We use the mean average precision (MAP), mean reciprocal rank (MRR), and Hits@N N as our evaluation metries, which are widely used for evaluating ranking and link prediction. The details of prediction steps and the evaluation metrics are given in Appendix D.4.
234
235
The n-d complex hyperbolic embeddings have around double parameters of the n-d real embeddings since the n-d complex hyperbolic vectors have n-d real part and n-d imaginary part. For a fair comparison, in each experimental setting, compare our n-d complex hyperbolic embeddings of UnitBall against the 2n-d embeddings of the baselines. The results will also demonstrate that the n-d complex hyperbolic space is not simply the 2n-d hyperbolic space, they have different capacities.
237
239
5.2
Graph reconstruction
242
5.2.1
Results on balanced trees
243
To compare the representation capacities of UnitBall and the hyperbolic embedding models for the tree structures, we first evaluate the graph reconstruction task on the synthetic balanced trees. A balanced tree-(r, h) has degree r and depth so it has r + nodes and r +...+tr " edges. The 8- d-hyperbolicity of any balanced tree is O. We embed the balanced trees into 20-d hyperbolic space for the baselines and 10-d complex hyperbolic space for UnitBall.
244
245
246
247
248
Figure [ presents the MAP and Hits @3 scores with varying r and h. We see that when the tree in small scale, e-g., hr (15,3) 3), (10, 2), (10, 3). all methods have very good performances, demonstrating the expected powerful capacities of hyperbolic geometry and complex hyperbolic geometry on tree structures. However, when the breadth the depth increases, the performances of Poincaré and Hyperboloid drop rapidly, suggesting that the optimization-basee embeddings in H:20 are not effective enough for reconstructing trees of such scales.
249
250
251
252
253
254
In comparison, UnitBall and TreeRep achieve stable performances for larger trees. TreeRep learns strueture from the data hyperbolic space using Sarkar's construction (Sarkar] 201T). When the input data is tree, TreeRep exactly recovers the original tree structure. Figure shows that UnitBall achieves comparable even better performances than TreeRep on the balanced trees. The results demonstrate that UnitBall does not compromise trees. It produces high-quality embeddings for tree structures.
intermediate step and then embeds the learned trees into the
256
257
258
259
260
5.2.2
Results on compressed graphs
261
To illustrate the benefits of UnitBall on varying hierarchical structures, we now evaluate on the synthetic compressed graphs. The compressed graphs have local tree structures while being more
7

---

Trudhes
UniBull
100
166
120
100
80
10.
60-
MAP
Hi.g33
40
28
20
15
1w25
1w
rw25
h-2
horh
h-
Hitag h-
MAP (on 10)
Hitsgaa (on 10)
Figure I: Evaluation of graph reconstruction on synthetic balanced trees in 20-d embedding spaces (10-d complex hyperbolic space for UnitBall). represents the degree while h represents the depth.
Treafoo
To ncars
Ryperosid
+
Jn tSel
70-
60-
Hoog (06)
8
20
S
26-
S
100 10
6 g
5
(on
km
m lon k-5)
K m-500)
ton m=500l
300
400
220
Kapestika 110
10
15
01
11
Figure 2: Evaluation of graph reconstruction on synthetic compressed graphs in 20-d embedding spaces (10-d complex hyperbolic space for UnitBall). represents the number of nodes in the graph while k represents the number of random trees aggregated to the graph (k controls the denseness and noise level of the graph). The statistics of the compressed graphs are provided in the tables.
263
complicated than trees. Each compressed graph-(m, k)) consists of m nodes and aggregated from random trees the nodes. The bigger corresponds to the denser and noisier graph.
265
Figure 2 depicts the reconstruction results as a function of varying m and The results on the compressed graphs are not good as on balanced trees, especially with the increase of m and k. which represents the increase of graph scale and denseness respectively. Notably, UnitBall outperforms all other methods on the challenging data, showing that UnitBall handles the noisy locally tree-like like structures better. TreeRep has comparable results with other methods when (m, k) (500, 1) since
286
267
268
269
when h = 1, the graph is exactly a tree, i.e., 5 = 0. However, when & > and 5 > O, TreeRep cannot achieve promising results, because when the data metrics deviate from tree metrics, does not help much to learn tree structure from the data as an intermediate step.
271
273
5.3
Link prediction
274
5.3.1
Overall results
275
In this section, evaluate the performances on the link prediction task for the real-world taxonomies. pareee]sesentts the results in 32-d embedding spaces for baselines and 16-d complex hyperbolic space for UnitBall. Predicting missing links requires stronger generalization capacity than reconstructing graphs, and UnitBall still has the best performances on all three datasets. Besides, we see that Euclidean shows shortages on these hierarchically-strueuii
276
277
278
279
data, which is consistent with the results in previous works (Nickel and Kiela, 2017 2013 8). Similar to the results on the graph reconstruction task, Poincaré and Hyperboloid have very close performances, while Hyperboloid has slightly better results. They have significant improvements over Euclidean, but they still fall behind UnitBall, which
281

---

Table 2: Evaluation of taxonomy link prediction in 32-d embedding spaces (16-d complex hyperbolic space for UnitBall). The best results are shown in boldface. The second best results are underlined.
ICDI0
YAGoe-wikiOhjeats
WordNet-noun
MAP
MRR
Hits @3
MAP
MRR
Hits @
MAP
MRR
Hits
Euclidean
3.75
3.72
2.39
4,85
4.45
2.78
5.59
5.36
3.16
TreeRep
4.96
7.92
8.49
20.19
21.85
27.19
9.30
9.98
11.90
Poincaré
35.24
34.45
52.71
30.06
28.47
41.61
25.46
23.99
27.80
Hyperholoid
34.80
34.01
52.88
30.80
29.21
43.17
25.65
24.15
27.50
UnitBall 47.88
46.96
70.28
33.33
31.85
47.41
27.29
25.93
32.95
Table 3: Evaluation of laxonomy link prediction in different embedding dimensions (the embedding dimension for UnitBall is half of other models). The best results are shown in boldface. The second best results underlined.
YAGOs-wikOOheeas
8-dimensional
32- 32-dimensional
-i-ddmmnnsioall
MAP
MRR
Hits
MAP
MRR
Hits@
MAP
MRR
Hits
Euclidean
1.02
0.92
0.57
4.85
4.45
2.78
16.67
15.76
15.97
TreeRep 16.91
17.48
27.53
20.19
21.85
27.19
21.18
23.44
32.84
Poincaré
29.70
28.13
41.64
30.06
28.47
41.61
29.93
28.35
41.53
Hyperboloid
30.87
29.28
43.50
30.80
29.21
43.17
30.68
29.07
42.86
UnitBall 31.40
29.98
44.25
33.33
31.85
47.41
32.76
31.28
46,25
demonstrates claims that the non-constant negative curvature of the complex hyperbolic space addresses the varying hierarchical structures on real-world datasets.
284
285
We notice that TreeRep does not perform well on the link prediction task. As mentioned in Section 2 the combinatorial construction based embedding methods (Sala al., 2018 Gu et al. 2019 (Sonthalaa and Gilbert) 2020) target on minimizing the reconstruction distortion of data and they can achieve very good results on the graph reconstruction task. But minimizing the reconstruction distortion may overfit the training set, thus resulting in the unpromising generalization performance for unobserved edges. Hence, they are more suitable to learn the representation of graph data without missing links. We also evaluate TreeRep on the real-world taxonomy reconstruction task in Appendix D.5.
286
286
290
292
5.3.2
Exploring the embedding dimensions
293
In this section, we explore the performances in different embedding dimensions. The results on YAGO3-wikiObjedt
presented in Table Results other datasets are in Appendix D.6. We find that with the increase of the embedding dimension, Euclidean can have big improvements, but its performances in 128-d still cannot surpass other methods in 8-d. TreeRep also achieves better results with the increase dimension, but overall its performances on the link prediction task are not very promising. By comparison, Poincaré, Hyperboloid, and UnitBall achieve great results steadily. 8-d is already enough for Poincaré and Hyperboloid to handle the link prediction task. We notice that UnitBall has small improvements from 4-d 16-d, then converges the stable performance. The results demonstrate that the Euclidean embeddings need to increase the dimension to better model the increasing complex hierarchies, while the complex hyperbolic space and the hyperbolic space have strong generalization competence for hierarchical structures.
295
297
299
301
303
Conclusion
304
305
In this paper, we present novel approach for learning the embeddings of hierarchical structures in the unit ball model of the complex hyperbolic space. We characterize the geometrical properties of the complex hyperbolic space, including the variable negative curvature and the exponential growth
306
307
308
of volume of geodesic balls, which are beneficial for data with various hierarchical structures. We exemplify the superiority of our approach over the graph reconstruction task and the link prediction
309
task on both synthetic and real-world data, which cover the tree structures as well the general hierarchical structures. The empirical results show that our approach outperforms the hyperbolic embedding methods in terms of representation capacity and generalization performance.
311

---

References
314 I. Balazevic, C. Allen, and T. M. Hospedales. Multi-relational poincaré graph embeddings. In NeurlPS, pages 4465-4473 2019.
316
G. Bécigneul and O. Ganea. Riemannian adaptive optimization methods. In ICLR (Poster). OpenRe- view.net, 2019.
S. Bonnabel. Stochastic gradient descent riemannian manifolds. IEEE Trans. Autom, Control., 58 (9):2217-2229, 2013.
319
A. Bordes, N. Usumier, A. García- Durán, J. Weston, and O. Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pages 2787-2795, 2013.
321
322 G. R. Brämer. International statistical classification of diseases and related health problems. tenth revision. World health statistics quarterly. Rapport trimestriel de statistiques sanitaires mondiales, 41(1):32-36, 1988.
323
324
I. Chami, Z. Ying, C. Ré, and J. Leskovec. Hyperbolic graph convolutional neural networks. In NeurIPS, pages 4869-4880, 2019.
326
I. Chami, A. Wolf, D. Juan, F. Sala, S. Ravi, and C. Ré. Low-dimensional hyperbolic knowledge graph embeddings. ACL, pages 6901-6914. Association for Computational Linguistics, 2020.
328
329
J. Dai, Y. Wu, Z. Gao, and Y. Jia. A bypperbolic-to--yyyroooiii graph convolutional network. In CVPR, 2021.
330
331
R. Fu, J. Guo, B. Qin, W. Che, H. Wang, and T. Liu. Learning semantic hierarchies via word embeddings. In ACL (I), pages 1199-1209. The Association for Computer Linguistics, 2014.
333
O. Ganea, G. Bécigneul, and Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In ICML., volume 80 of Proceedings of Machine Learning Research, pages 1632-1641. PMLR, 2018a.
335
336
O. Ganea, G. Bécigneul, and T. Hofmann. Hyperbolic neural networks. In NeurlPS, pages 5350-5360, 2018b.
337
338
W. M. Goldman. Complex hyperbolic geometry. Oxford University Press, 1999.
J. R. Griggs, W. Li, and L. Lu. Diamond-free families. J. Comb. Theory, Ser. A, 119(2)311-322, 2012.
340
341
M. Gromov. Hyperbolic groups. In Essays in group theory, pages 75-263. Springer, 1987.
342
A. Gu, F. Sala, B. Gunel, and C. Ré. Learning mixed-curvature representations in product spaces, In ICLR (Poster). OpenReview.net, 2019.
343
344 C. Gülçehre, M. Denil, M. Malinowski, A. Razavi, R. Pascanu, K. M. Hermann, W. Battaglia, V. Bapst, D. Raposo, A. Santoro, and N. de Freitas. Hyperbolic attention networks. In ICLR (Poster). OpenReview.net, 2019.
346
A. A. Hagberg, D. A. Schult, and P. J. Swart. Exploring network structure, dynamics, and function using networkx. In G. Varoquaux, T. Vaught, and J. Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 15, Pasadena, CA USA, 2008.
348
350 D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, Sep 2010. doi: 10. 1010/PPysseeeE..22.06000 URL https://link: http://iiinkapp....o.pppm org /wwgg//oo//1.... wtt.://///oo//...1////////////// 1103/PhysRevE....mm 02.882.03333 036106
352
apw.
353
Q Liu, M. Nickel, and D. Kiela. Hyperbolic graph neural networks. In NewrlPS, pages 8228-8239, 2019.
355
Mahdisoltani, Biega, and F. M. Suchanek. YAGO3: A knowledge base from multilingual wikipedias. In CIDR. www.cidrdb.org, 2015.
10

---

357
G. A. Miller. Wordnet: A lexical database for english. Commun. ACM, 38(1 19:311)394411 41, 1995.
358
M. Nickel and D. Kiela. Poincaré embeddings for learning hierarchical representations. In NIPS, pages 6338-6347, 2017.
359
360
M. Nickel and D. Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In ICML,, volume 80 of Proceedings of Machine Learning Research, pages 3776-3785. PMLR, 2018.
362
365
M. Nickel, Tresp, and H. Kriegel. A thyee-way model for collective learning on multi-relational data. In ICMI, pages 809-816. Omnipress, 2011.
F. Sala, C. D. Sa, A. Gu, and C. Ré. Representation tradeoffs for hyperbolic embeddings. In ICML, volume
366
Proceedings of Machine Learning Research, pages 4457-4466. PMLR, 2018
367
R. Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. Graph Drawing, volume 7034 of Lecture Notes in Computer Science, pages 355-366. Springer, 2011.
R. Shimizu, Y. Mukuta, and T. Harada. Hyperbolic neural networks++. In ICLR (Poster), 2021.
V. Shwartz, Y. Goldberg, and Dagan. Improving hypernymy detection with an integrated path-based and distributional method. In ACL (1). The Association for Computer Linguistics, 2016.
371
372
R. Sonthalia and A. C. Gilbert. Tree! am no tree! I am low dimensional hyperbolic embedding. In NeurlPS, 2020.
F. M. Suchanek, G. Kasneci, and G. Weikum. Yago: core of semantic knowledge. In WWW, pages 697-706. ACM, 2007.
375
376
Z. Sun, Z. Deng, J. Nie, and Tang, Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR (Poster). OpenReview.net. 2019.
Z. Sun, M. Chen, W. Hu, C. Wang, J. Dai, and W. Zhang. Knowledge association with hyperbolic knowledge graph embeddings. In EMNLP (I), pages 5704-5716. Association for Computational Linguistics, 2020.
379
380
381 T. Trouillon, J. Welbl, S. Riedel, É. Gaussier, and G. Bouchard. Complex embeddings for simple link prediction. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages JMLR.org, 2016.
383
384 B. Yang, W. Yih, X. He, J. Gao, and L. Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR (Poster), 2015.
T. Yu and C. D. Sa. Numerically accurate hyperbolic embeddings using tiling-based models. In NeurlPS, pages 2021-2031, 2019.
387
Checklist
388
389
For all authors...
390
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The discussions on the limitations
393
of our work are mainly presented in Experiments both in the paper and Appendix.
394
(c) Did you discuss any potential negative societal impacts of your work? [No]
385
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
396
2. If you including theoretical results...
398
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
399
and
400
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix and
B.

---

402
3. If you ran experiments...
403
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material proprietary for this moment. The code will be released after the the publishing of the paper.
404
URL)? [No] The code is
405
407
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5.1 and Appendix D.3.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [No] We report the mean results over 5 running times.
410
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix D.2.
412
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5.1.1 The data are publicly available. We cite the corresponding references and give the public data links.
415
(b) Did you mention the license of the assets? [No]
418
(c) Did you include any new assets either in the supplemental material or as a URL? [No] We do not create new datasets. We sample taxonomy from YAGO3 and will release it after the the publishing the paper.
419
420
421
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
424
425
5. If you used crowdsourcing or conducted research with human subjects...
426
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
427
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
429
430
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
431
12


Reviews:
[{"review_id": "bFY9NA99OuB", "reviewer": "Reviewer_TUo7", "summary": "This paper proposes a method to learn embeddings in complex hyperbolic spaces. In contrast with real hyperbolic spaces, complex hyperbolic spaces have a variable negative curvature, which can handle more flexible graph structures. Experiments show that complex hyperbolic embeddings outperform real hyperbolic embeddings on synthetic and real-world graphs. ", "questions": "", "limitations": "", "rating": 5, "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": "Strengths: \n- This paper is interesting and the first to leverage complex hyperbolic spaces. \n- The paper is well written and easy to follow.\n- Experiments show significant improvements from using complex hyperbolic geometry.   \n\nWeaknesses: \n- The main weakness of this work is the lack of motivation for using a complex hyperbolic space. While the authors mention that having a variable negative curvature can capture diverse structures, it is not clear how these variations in curvature relate to different degrees of hierarchy in graphs. It would be good to provide intuition for how curvature changes in this geometry, visualizations would have been very helpful here. Simple examples of graphs where this space is a better candidate than the real hyperbolic space would make the motivation clearer. \n\nMinor comments: \n- It would be interesting to understand the precision-distortion tradeoffs in complex hyperbolic geometry. For instance, it is known that real hyperbolic spaces are ideal candidates for balanced trees (section 5.2.1) but have limited capacity due to limited machine precision (Sala et al. 2018). It would therefore be interesting to investigate whether the improvements of complex hyperbolic embeddings are related to precision, and if distortion scales better with precision in this geometry. \n- The Levi-Civita connection notation in definition 1 is not defined. \n- Moving eq. (6) to section 3.3 would improve the flow. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "F-RpvKGnZHV", "reviewer": "Reviewer_XZ2r", "summary": "The paper proposes the complex hyperbolic space for embedding hierarchical data. The authors demonstrate the superiority of the proposed optimization approach for the tasks of graph reconstruction and link prediction.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- To the best of my knowledge, the proposed approach is novel.\n- In the experiments, the complex hyperbolic space outperforms the baselines (Euclidean embeddings and several implementations of hyperbolic embeddings).\n\nWeaknesses (more details below):\n- The technical part of the paper is hard to follow (defining notation and more explanation would help).\n- The motivation is not very clear: in which cases non-constant curvature is expected to help.\n- Limited experimental evaluation (unclear whether the proposed approach would help in more practical tasks).\n\nRegarding motivation, it is claimed that a non-constant negative curvature is beneficial. However, it is not discussed why. The reason why negative curvature is beneficial for tree structures is the exponential growth of balls’ volumes (Nickel and Kiela, 2017); the examples of structures that are suitable for positive/zero/negative curvature are also discussed in (Gu et al., 2019). Similarly, it would be useful to understand for which structures the complex hyperbolic space is beneficial and why. Experiments suggest that for the considered synthetic graphs the complex hyperbolic space is indeed useful, but without much explanation.\n\nRegarding the technical part, I have to admit that I could not fully digest the theoretical part of the paper. In particular, there is little background explaining the technical differences between standard and complex hyperbolic spaces. Regarding the background on curvature, I would expect to see all notation being defined. Then, the notation \\sim seems to be not conventionally used: for instance, in (1) some terms depending on n seem to be missing, and in (2) the same happens. Regarding the proofs, is it true that the proof of Theorem 1 is not new and is provided just for completeness? Similar question regarding the derivations in Section 4.1. Also, how the formula (5) is obtained?  Am I right that the main technical novelty is the derivation in Section 4.3?\n\nSome comments regarding the experiments: \n- In the first set of experiments, the authors first compare the ability of different spaces to embed balanced trees. Here, they make an interesting observation: the performance of Poincare and Hyperboloid drops with the size of a tree, while the proposed UnitBall and the baseline TreeRep work quite well. For the standard hyperbolic space, combinatorial optimization (TreeRep) outperforms gradient-based approaches (Poincare and Hyperboloid). So, it is interesting to see that UnitBall works well while it also uses Riemannian SGD. In other words, we see that both complex and standard hyperbolic spaces work well, so what is the reason for UnitBall to outperform Poincare and Hyperboloid?\n- The experiments are conducted on three real datasets. Comparing with (Nickel and Kiela, 2017), there is the same WordNet dataset, but the values for MAP are sufficiently smaller. What difference in the experimental setup causes this? It would be useful to see the numbers in a comparable setup.\n- Unfortunately, the source code is not present.\n\nMinor comments:\n- \\cite -> \\citet in multiple places, when citations are used as part of the sentence (line 56 and below).\n- Line 137 We -> we\n- What is \\mathcal{T} in line 156?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "DDihmxMqO7F", "reviewer": "Reviewer_BtXz", "summary": "Complex hyperbolic space is new for embedding.", "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 work is technically sound and well organized. But there are some problems that I am concerned about:\n\n(1) \"The real-world hierarchically structured data are usually not trees since they can have varying local structures while being tree-like globally\".  The authors present a novel embedding approach, which takes advantage of the variable negative curvature of the complex hyperbolic space, to handle data with complicated and various hierarchical structures.  However, it is not clear how the complex hyperbolic space solves the problem and why complex hyperbolic space can solve the problem of varying local structures.\n\n(2) HGCN [1] leverages the trainable curvature to compensate for the disparity between the actual data structures and the constant-curvature hyperbolic space; the mixed curvature method [2] introduce a heuristic to estimate the sectional curvature of graph data and directly determine an appropriate signature; Graph Geometry Interaction Learning[3] also try to the problem of varying local structures? how about comparing it with this method?\n\nReferences:\n\n[1]NeurIPS'19 Hyperbolic graph neural network\n\n[2]ICLR'19 Learning Mixed-Curvature Representations in Product Spaces\n\n[3] NeurIPS'20 Graph Geometry Interaction Learning\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 Hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method to learn representations of hierarchical structures by embedding them into complex hyperbolic space. Reviewers and the AC agreed that the proposed approach is a promising direction to advance hyperbolic embeddings as it allows for variable negative curvature which has, for instance, the potential to improve the embedding quality of real-world graphs (which in almost all cases won't be represented adequately with constant curvature). Furthermore, the proposed approach shows promising empirical results and is clearly relevant to the NeurIPS community. However, all reviewers raised concerns regarding the clarity of discussion, especially with regard to the motivation and justification of the approach as well as the presentation of technical aspects. These concerns were not resolved after the author response and further discussion among reviewers. In relation to this, reviewers raised also concerns regarding the experimental evaluation as further analyses could provide needed insights into the approach and how it utilizes variable curvature. After rebuttal and discussion, no reviewer strongly supported the acceptance of the paper, with two reviewers indicating weak accept and one reviewer indicating weak reject. Taking rebuttal and discussion into account, I narrowly agree that the manuscript is currently not ready yet for acceptance at NeurIPS and would require an additional revision to resolve the above concerns. However, the idea to utilize complex hyperbolic space is clearly promising and I encourage the authors to revise and resubmit their work based on the feedback from this reviewing round.
Decision: Reject