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: ICLR 2022 Submitted (2022)
Keywords: Complex hyperbolic embeddings
hierarchical data embeddings
taxonomy embeddings

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, most 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. We also explore the competence of complex hyperbolic geometry on the multitree structure and 1-N structure.

Under review as a conference paper at ICLR 2022
UNIT BALL MODEL FOR EMBEDDING HIERARCHICAL STRUCTURES IN THE COMPLEX HYPERBOLIC SPACE
Anonymous authors Paper under double-blind review
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 metries and captures the tree-like properties naturally, which enables the hyperbolic embeddings to improve over tra- ditional Euclidean models. However, most 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, show that our approach improves over the hyper- bolic embedding models significantly. We also explore the competence of complex hyperbolic geometry on the multitree structure and 1-N structure.
INTRODUCTION
Representation learning of data with hierarchical structures is an important machine learning task with many applications, such as taxonomy induction (Fu et al., 2014) and hypernymy detection (Shwartz et al. 2016). In recent years, the hyperbolic embeddings (Nickel and Kiela 2017: 2018) have been proposed to improve the traditional Euclidean embedding models. The constant negative curvature of the hyperbolic space produces manifestation that the hyperbolic space be regarded continuous approximation to trees (Krioukov et al., 2010). The hyperbolic space is capable of embedding any finite tree while preserving the distances approximately (Gromov 1987).
However, most real- world hierarchical data do not belong to tree structures since they can have varying local structures while being tree-like globally. For example, the taxonomies such WordNet (Miller 1995) and YAGO (Suchanek et al.) 2007) contain many 1-N (1 child links to multiple parents) cases and multitree structures (Griggs al.. 2012), which much more complicated than the tree structure. In consequence, the hyperbolic space which resembles tree metrics has limitations on capturing the general hierarchically structured data.
To address the challenge, in this paper, we propose new approach to learning the embeddings of hierarchically structured data. Specifically, we embed the hierarchical data into the unit ball model of the complex hyperbolic space. The unit ball model is projective geometry based model to identify the complex hyperbolic space. One of the main differences between the complex and the real hyperbolic space is that the curvature is non-constant in the complex hyperbolic space. In practice, the variable negative curvature makes the complex hyperbolic space more flexible in handling varying structures while the tree-like properties still retained.
For empirical evaluation, we evaluate different geometrical embedding models on various hierar- chically structured data, including synthetic graphs and real-world data. The experimental results demonstrate the advantages of our approach. In addition, we investigate two specific structures in which complex hyperbolic geometry shows outstanding performances, namely the multitree structure and 1-N structure, which are highly common and typical in real-world data. To summarize. our work has the following main contributions: 1. We present novel embedding approach based on the

---

Under review as a conference paper at ICLR 2022
complex hyperbolic geometry 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. 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. 3. We evaluate our approach with experiments on extensive range of synthetic and real-world data and show the remarkable improvements of our approach.
2 RELATED WORK
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 Poincaré ball model of the hyperbolic space and outperformed the Euclidean embedding methods for taxonomies. The Poincaré embedding model was then improved
by follow-up works on hyperbolic emebddings (Ganea et al. 2018a Nickel and Kiela 2018). These
methods learned the hyperbolic embeddings by Riemannian optimization (Bonnabel 2013). which
was further improved by the Riemannian adaptive optimization (Bécigneul and Ganea (2019).
Another branch of study (Sala al. 2018 Sonthalia and Gilbert 2020) learned the hyperbolic embeddings through combinatorial construction. Instead of optimizing the soft-ranking loss by Riemannian optimization in (Nickel and Kiela 2017 2018), the construction-basee minimize the reconstruction distortion by combinatorial construction. However, both the optimization- hyperbolic embeddings suffer from the limitation in hierarchical graphs
methods
based and construction-base with varying local structures. To tackle the challenge, (Gu et al. (2019) extended the construction-bar method by jointly learning the curvature and the embeddings of data in product manifold. Although it can provide better representation than single space with constant curvature, it is impractical to search for the best manifold combination among enormous combinations for each new structure.
Motivated by the promising results of previous works, extensions to the multi-relational graph hyperbolic embeddings (Balazevic et al., 2019: Chami al., 2020 Sun et al. 2020p and hyperbolic Chami et al. 2019
neural networks (Ganea et al. [018b)] Gülgehre et al. [219 Liu et al. 2019 |
Zhu et al. 2020: Dai et al.] 2021a; Shimizu et al.J (021)) were explored. Notably, (Chami al.
(019|20200 leverages the trainable curvature to compensate for the disparity between the actual data hyperbolic space, where each layer the graph neural network graph has its own curvature parameterization. Since we only focus on the singlc-relation graph embeddings and taxonomy embeddings this work, we do not evaluate the multi-relational knowledge graph embedding models the neural networks in our tasks.
structures and the constant-curvattee or each relation in the
The hyperbolic learning also inspired other research tasks and applications, such as classification (Cho et al. 2019), image reconstruction (Skopek et al. 2020). text generation (Dai al. 2021b), etc.
Complex embeddings. The traditional knowledge graph embeddings were learned in the real Euclidean space (Nickel et al. 2011 Bordes et al.) 2013 Yang et al. 2015) 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 ComplEx (Trouillon et al. (016)) and RotatE (Sun et al. 2019). These models have been demonstrated to be effective in 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.
3 PRELIMINARIES
3.1 HYPERBOLIC GEOMETRY
Hyperbolic space a homogeneous space with constant negative curvature In the hyperbolic space H (K) of dimension n and curvature K, the volume of a ball grows exponentially with its radius pt
vol Bag (K) e (n-(p_
In this paper, we use hyperbolic space refer to real hyperholic space and hyperbolic embeddings to refer to real hyperbolic embeddings for avoiding wordiness.
In this paper, curvature refers the sectional curvature. Please see Appendix A.1 for definition.
2

---

Under review as a conference paper at ICLR 2022
Contrastively, in the Euclidean space E", the curvature is 0 and the volume of ball grows polynomi- ally with its radius:
T//
vol( (0))
T(n/2) p".
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 Fuclidean space is too flat and narrow to embed trees.
3.2 COMPLEX HYPERBOLIC GEOMETRY
Complex hyperbolic space is a homogeneous space of variable negative curvature. Its ambient Hermitian vector space C is the complex Euclidean space C=+1 endowed with some Hermitian form (z. w). where z, w E C=+1 Then the Hermitian space C can be divided into three subsets: V_ {z E C ((z, z}} < 0}. Vo- = =z C".1 {0H(Z. z)) 0}, and V+ {z C CZ, z)} >
0}. Let be a projection map C
{ 0} + C" i.e.,
21 2n-1
P:
+
where 2x+1 # O.
(3)
Fn++1
2n/ 2n/22411
Then the complex hyperbolic space HDS and its boundary OHL are defined using the projectivization:
H PV-,
ThE TPVo-
The curvature of the complex hyperbolic space is summarized by (Goldman, 1999) follows:
Theorem 1. The curvature is not constant in H.. It is pinched between -1 (in the directions of complex projective lines) and 114 (in the directions of totally real planes).
We leave the full proof in Appendix B The non-constant curvature, which we expect be favorable for embedding various hierarchical structures, one of the main differences between H& and H
The complex hyperbolic space also has the tree-like exponential volume growth property. The volume of ball with radius p in HIS is given by
8" 8"02n-1
voll (p))
sinh 2d (p/2)
~ ExP,
(5)
2n
where 02n-1 2x /n! is the Euclidean volume of the unit sphere S2n-1 C
From the properties of the complex hyperbolic 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 I while preserving the tree-like properties as shown in Eq. (5).
From this section, of different characteristics. The n-dimensional (n-d) complex hyperbolic space is not simply the 2n-d hyperbolic space the product of two n-d hyperbolic spaces. This implies that complex hyperbolic embedding model is intrinsically different from the hyperbolic embedding methods (Nickel
that complex hyperbolic geometry and hyperbolic geometry typically
and Kiela 2017 2018) or the product manifold embeddings (Gu al. 2019
UNIT BALL EMBEDDINGS
We propose embed the hierarchically structured data into the unit ball model of the complex hyperbolic space. In this section, we introduce our approach in detail.
4.1 THE UNIT BALL MODEL
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 necessary derivation.
3

---

Under review as a conference paper at ICLR 2022
Take the Hermitian form of C in Section 3.2 to be standard Hermitian form:
(z. w) = 21 wi +
2n W Zn++1 Wn+1,
(6)
where w is the conjugate of w. Take 2x+1 1 in the projection map IP in Eq. we can derive the formula of the unit ball model:
3 Then from Eq.
4
_ P( "(z, 2) 0}) {(21,-. 2n. 1)
lanl << 1}.
The metric on B is Bergman metrie, which takes the formula below in 2-d case:
(22, z)) dai))
Edz,, 2)) (dz,, dzi))
ds²
(z, z) det
(8)
The distance function g is given by
dap (z, w) arcosh (2 (z, w/) (w, (2, w) 1).
(9)
Note that there are other choices of the Hermitian form (zz, w). which corresponds to other models of complex hyperbolic geometry, such the Siegel domain model. We choose the unit ball model for the relatively simple formula as well as convenient computations of the metric and distance function.
4.2 EMBEDDINGS IN THE UNIT BALL MODEL
Given the hierarchical data containing a set of nodes X {(1p, "g)1=p, F.g X}, we aim to learn the embeddings of the nodes (zp1y=1. where Zp E B
{-p]p= and a set of edges E
The objective of the embeddings is to recover the structures of input data, including the distances between the nodes as well the partial order in the hierarchies. Here we 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 at preserving the hierarchical relationships among nodes:
deg 22,)
L=
Σ log (E
(10)
EmtEN(op)) dag (xp.
where [(xp)= {xx (Ip, 2x) & E} U {x,}} is the set of negative examples for xp together with xp- dæy is the distance function in the unit ball model given in Eq. (9). The minimization of T. makes the connected nodes closer in the embedding space than those with no observed edges.
The learning process implicitly aligns the geometric structures of the embedding space and the underlying graph structures of data since the loss function aims at preserving the hierarchical relationships among nodes while the underlying graph structures are reflected by the hierarchical relationships. We learn the embeddings in the unit ball model, where the variable negative curvature of the complex hyperbolic space provides the capacity deal with more varying structures. The experiments in Section exhibit that the unit ball model learns the high-quality embeddings and captures the various hierarchical structures.
4.3 RIEMANNIAN OPTIMIZATION IN THE UNIT BALL MODEL.
We learn the embeddings Z } 1m
through solving the optimization problem with constraint:
Z + arg min L S.t. E Z, up B
(II)
2
For the optimization problems in Riemannian manifolds, Bonnabel (2013) presented the Riemannian stochastic gradient descent (RSGD) algorithm, which we employ to optimize Eq. (II). To update an embedding E B we need to obtain its Riemannian gradient V R. Specifically, the embedding updated at the t-th iteration by (t) +- (t-1) 7 ( (z),, where r7(*) is the learning rate at the
t-th iteration and V RL)(Z) is the Riemannian gradient of Lzz).
Here omit the subscript of z, for concision.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 RSGD of the unit ball embeddings.
Input:
initialization z("), number of iterations T, learning rates (1)
for ( = to ddo do
adgg Compute -xx and by by Eqs. 13 and 14b.
adgg
Compute V (z) and V R (z) by Eq. 12
Update (+() by Eq. 16
end for
The Riemannian gradient V can be derived from rescaling the Euclidean gradient VE e with the inverse of the metric tensor ds² in Eq. (8. Apply the chain rule of differential functions and we have:
@L(z) dsa 0dga (z, w)
1
VRL(Z)= VEL(Z)
V VEdBy (z, w).
(12)
ds
Bd (2.w) trivial compute from Eq. (10 In practical training, we implement and compute
aLiz)
the complex hyperbolic embedding its real part and imaginary part, i.c., x + iy, where represents the imaginary unit, i.c., d² -. In order to get the gradient of the distance function VEdgy (z, w) in Eq. 12). we get the partial derivative with regard the real part and the imaginary (dgp (2.w)
Adgn (x.w)
part, i.e. V gdgg (z, w)
By
The partial derivatives of the unit ball model distance take the following formulas:
ddb:
Ree((z, w)) w)
(z, w)) (w, z)}x
(13)
0x
p2
((z, z)) (w, w)
(z. z)) ([ (w, w))
0dg
4
Iml (iz, w)) w)
((z, w)) ((w, z))y
(14)
22
(2, z)) (W: w)
(2, 2) ((w, w))
where p = cosh (dgg (z, w)). Re(-) and (m(-) denote the real and the imaginary part respectively.
The full derivation of Eqs. 13 and (14) is given in Appendix [
Since the embedding z should constrained within the unit ball model, we apply the same projection strategy as (Nickel and Kiela 2017) via a small constant 8:
(z)j z/( -)). =). if [z| 1, else z.
(15)
To sum up, the update of z at the t-th iteration
proj (2 (t (()))() = proj (2 (t) (EL(Z))
(16)
ds
The RSGD steps of the unit ball embeddings are presented in Algorithm
EXPERIMENTS
In experiments, we evaluate the performances of our approach and baselines various hierarchical structures, including synthetic graphs and real-world data. We focus on the graph reconstruction task and the link prediction task. The main results reported in this section. For more experiments, please refer to Appendix F
5.1 EXPERIMENTAL SETTINGS
5.1.1 DATA
We use synthetic and real-world data that exhibit underlying hierarchical structures to evaluate our approach. The public links or generator package links of the data are given in Appendix [F.]]
Synthetic. We generate various balanced trees and compressed graphs using NetworkX package (Hag berg et al. 2008). For balanced trees, generate the balanced tree with degree and depth h. For
5

---

Under review as a conference paper at ICLR 2022
Table The real-world datasets statistics.
Xiphophorus
ICD10
YAGOs-wikiOhjects
WordNet-noun
Nodes
3,562
19,155
17,375
82,115
Edges
7,536
78,357
153,643
743,086
Depth/
13
6
16
20
Training edges
7,536
70,521
138,277
668,776
Valid/Test edges
4,160
3,918
7,683
37,155
6-hyperbolicity
2.5
0.0
1.0
0.5
compressed graphs, we generate k random trees on nodes and then aggregate their edges to form graph. Some examples of the synthetic data are given Appendix F.I
Xiphophorus, The Xiphophorus is a multitree dataset from (Cui et al. 2013), which contains 160 trees representing mrbayes consensus trees inferred for different genomic regions 26 Xiphophorus fishes. We use the saved MultiTree object in toytree package.
ICD10. The 10-th revision of International Statistical Classification of Diseases and Related Health Problems (ICD10) (Brämer 1988) is a medical classification list provided by the World Health Organization. We construct its full transitive closure as the ICD10 dataset.
YAGO3-wikiObjects, YAGO3 (Mahdisoltani et al. 2015) is a huge semantic knowledge base. It 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-
dataset.
WordNet-noun. WordNet (Miller 1995) is large lexical database. The hypernymy relation among all nouns forms a noun hierarchy. We use its full transitive closure as the WordNet-noun dataset.
For the multitree (Xiphophorus), we use the full dataset as the training set and the edges containing the leaf nodes as the test set. For each real-world taxonomy (ICD10, YAGO3-wikiOhject, WordNet- sets with the ratio 90%:5%%:5% We
noun), randomly split the edges into nnin-validation-tee make sure that any node the validation and test sets must occur in the training set since otherwise, it cannot be predicted. But the edges in the validation and test sets do not occur in the training set since they are disjoint. We provide the statistics of the real-world datasets in Table The Gromov's 's 5 d-hyperbolicity (Gromov 1987) measures the tree-likeness of graphs (refer to Appendix for definition). The lower corresponds to the more tree-like graph and trees have 0 9-hyperbolicity.
5.1.2 TASKS
We evaluate the following two tasks:
Graph reconstruction: we train the embeddings of the full data and then reconstruct it from the embeddings. The task evaluates representation capacity. Link prediction: we train the embeddings on the training set and predict the edges in the test set. The task evaluates generalization performance.
5.1.3 BASELINES
We compare our approach UnitBall the following methods: the sate-of-the-art combinatorial construction-bast hyperbolic embedding method TreeRep (Sonthalia and Gilbert 2020), the optimization-bast based hyperbolic embeddings in the Poincaré ball model (Nickel and Kielaj 2017) and the Hyperboloid model (Nickel and Kiela| 2018). the simple Fuclidean embedding model. Fuclidean, Poincaré, Hyperboloid, and our approach UnitBall use the same loss function but learn in the different geometrical spaces. Therefore, the comparisons reveal the capacities of different geometrical models in different spaces.
For the baselines, use their released codes train the embeddings. For all methods, the hyperpa- rameters are tuned on each validation set for the link prediction task and on balanced tree-(15,3) for the graph reconstruction task. The hardware information is given in Appendix F22 and the hyperpa- rameters are listed in Appendix(F33 In experiments, we report the mean results over running executions. The code of approach will be publicly available after the publication of the paper.

---

Under review as a conference paper at ICLR 2022
20
60
(SC
HatD03 (%)
50-
80-
20
20
1000
( 40 1009
(on (:3)
lon k=))
Bige
876
100
1010
1885
2.000
2009
3,615
3583
1.455
4.70
Edaes
400
060
1.480
1,00
2,45
2 995
3,622
3.00
4.636
4,000
Akrpersticct
3.0
1.2
Figure I: 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.
5.1.4 EVALUATION
We use the mean average precision (MAP), mean reciprocal rank (MRR), and Hits@N our evaluation metrics, which are widely used for evaluating ranking and link prediction. The details of prediction steps and the evaluation metrics are given in Appendix F.4
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, we 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.
5.2
GRAPH RECONSTRUCTION
5.2.1
RESULTS ON COMPRESSED GRAPHS
To illustrate the benefits UnitBall on varying hierarchical structures, we evaluate on the synthetic compressed graphs. The compressed graphs have local tree structures while being much more complicated than trees. Each compressed graph-(m, k) consists of nodes and aggregated from random trees on the m nodes. The bigger corresponds to the denser and noisier graph.
Figure [ depicts that the graph reconstruction results drop down with the increase of m and which represents the increase of graph scale and denseness respectively. Remarkably, UnitBall outperforms all baselines on the challenging data, showing that UnitBall handles the noisy locally tree-like structures better. The construction- -ased method TreeRep learns tree structure from the data as an intermediate step and then embeds the learned trees into the hyperbolic space using Sarkar's construction (Sarkar 2011). TreeRep has comparable results with other methods when (m, k) = (500, 1) since when = the graph is exactly a tree, i.e., 8 = 0. However, when l > 1 and 8 0, the data metrics deviate from metrics, in which case it does not help much learn tree structure from the data as an intermediate step.
5.2.2 RESULTS ON MULTITREE STRUCTURE
In this section, compare the performances of the hyperbolic models and UnitBall on Xiphophorus. Xiphophorus a multitree dataset that is formed of 160 mrbayes consensus trees on 26 Xiphophorus fishes. Its cloud tree plot is in Figure 2 The multitree structure is widely used to represent multiple overlapping taxonomies over the same ground set (please refer to Appendix for details). We reconstruct the edges containing the leaf nodes on Xiphophorus since the leaf links have the practical taxonomic meaning. The results are reported in the last column of Table 4 The results show that the complex hyperbolic geometry has stronger ability represent the multitree structure.
7

---

Under review as a conference paper at ICLR 2022
12503
2213792317
10100
2.4 Sincuus
6003
X. gond ceree
x. veak non manaaa
a Prrtooo
GARC
2503
x.
2-5 6-10
11-20
V2O
N (eParents limbed the model
Figure 2: Left: The cloud tree plot of Xiphophorus. Right: The 1-N structure statistics in YAGO3- wikiObjects original taxonomy. The horizontal axis represents the number of parents linked to node. The vertical axis counts the number of nodes and edges in the 1-N structures, For example, there are 107 nodes that link to N parents for S N 5, and these links count to 10, 550 edges.
Table 2: Evaluation of laxonomy 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
WordNet-noun MRR
MAP
MRR
Hits @
MAP
MRR
Hits@3
MAP
Hits@3
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
Hyperboloid
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
5.3
LINK PREDICTION
5.3.1
RESULTS ON THE REAL- WORLD TAXONOMIES
In this section, we evaluate the performances on the link prediction task for real-world taxonomies. Table [ presents the results in 32-d embedding spaces for baselines and 16-d complex hyperbolic space for UnitBall. Predicting missing links requires generalization capacity, and UnitBall still has the best performances on all three datasets. Besides, we see that Euclidean shows shortages on these data, which is consistent with the results in previous works (Nickel and Kiela 2017 2018). Similar 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 demonstrates our claims that the non-constant negative curvature of the complex hyperbolic space addresses the varying hicrarchical structures on real-world taxonomies.
hierarchically-strueeee
We notice that TreeRep does not perform well the link prediction task. As mentioned in Section 2. the combinatorial construction- based embedding methods target minimizing the reconstruction distortion of data. However, minimizing the reconstruction distortion may overfit the training set, thus resulting in the unpromising generalization performance for unobserved edges. Hence, they more suitable learn the representation of graph data without missing links. The evaluation of TreeRep on the graph reconstruction task can be referred to Section 5.2.1 Appendix F.5 and F.6
5.3.2 EXPLORING THE EMBEDDING DIMENSIONS
In this section, we explore the performances in different embedding dimensions. The results on YAGOJ-wikiObjeets are presented in Table Results on other datasets are in Appendix F.7 We find that with the increase of the embedding dimension, Euclidean can have big improvements, but its performances 128-d still cannot surpass other methods in 8-d. TreeRep also achieves better results with the increase of dimension, but overall its performances not very promising. By comparison, Poincaré, Hyperboloid, and UnitBall achieve great results steadily. 8-d is already enough for Poincaré and Hyperholoid to handle the link prediction task while
the link prediction task
8

---

Under review as a conference paper at ICLR 2022
Table 3: Evaluation of taxonomy 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 are underlined.
YAGO3- -iioo-wikiOseetts
S-dimensional
32-dimensional
128-dimensional
MAP
MRR
Hits@3
MAP
MRR
Hits@3
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
Hyperholoid
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
Table 4: Results of Hits@ 10 on predicting 1-N edges in YAGO3-wikiObjeets and results of MAP on reconstructing the leaf node links in Xiphophorus. The embedding dimension is 16 for UnitBall and 32 for other models. The best results are shown in boldface.
YAGOeewikkOhhectss (Hits@ 10)
Xiphophorus (MAP)
for 1-N edges
2 2~
6
10
11
20
20
Leaf Links Reconstruction
Poincaré
93.10
65.48
60.11
49.09
43.97
63.29
89.
Hyperboloid 92.80
65.51
63.49
51.93
45.39
63.95
89.80
UnitBall 92.42
76.35
65.91
66.19
70.21
74.03
91.95
UnitBall has small improvements from 4-d to 16-d, then converges to the stable performance. The results demonstrate that the Euclidean embeddings need to increase the dimension to better model the hierarchies, while the complex hyperbolic space and the hyperbolic space have strong generalization competence for hierarchical structures.
5.3.3 EXPLORING 1-N STRUCTURE
A noteworthy difference between the real-world taxonomies and the tree structures is that the taxonomies contain many 1-N (1 child links to multiple parents) cases while tree each node except the root is linked to only parent node. To investigate the advantages of complex hyperbolic geometry on the 1-N structures, we evaluate the performances UnitBall, Poincaré, and Hyperboloid on predicting the 1-N edges. We evaluate structures. The statistics of the 1-N structures in YAGO3-wikiObjects original taxonomy (original means without computing the transitive closure) are given in Figure 2
since it contains abundant 1-N
In this experiment, we train the embeddings on the full transitive closure YAGO3-wikiObject, and then predict the 1-N edges. The Hits @ 10 scores are reported on Table For results of other metrics, please refer to Appendix F.8 We can see that UnitBall has a very small compromise for the 1-1 edges, ie., the edge pattern tree structures. Furthermore, UnitBall outperforms the hyperbolic models largely on 1-N structures for N > 1. Even for nodes that link to more than 20 parents, UnitBall can have accurate top 10 predictions for these edges. The results demonstrate that the complex hyperbolic embeddings maintain the advantages in the edge pattern of tree structures well as handling more complicated hierarchical structures compared with the real hyperbolic embeddings.
CONCLUSION AND FUTURE WORK
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 and formulate the embedding algorithm in the unit ball model. We exemplify the superiority of our approach over the graph reconstruction task and the link prediction task on both synthetic and real-world data, which cover the various hierarchical structures and two specific structures, namely multitree structure and 1-N structure. The empirical results show that our approach outperforms the hyperbolic embedding methods in terms of representation capacity and generalization performance. Motivated by theoretical grounding and empirical success, believe the complex hyperbolic embeddings will have promising improvements on the knowledge graph embeddings, neural networks, and other related applications.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Please see Section and for the full set of assumptions of all theoretical results. Please see Appendix B and for complete proof' of all theoretical results.
Please see Section 5. and Appendix hyperparameters, hardware, etc).
for the experimental details (e.g., data splits,
The data used in the paper are publicly available. We cite the corresponding references and give the public data links in Appendix [F.T]
The code is proprietary for this moment. The code will be released after the the publication of the paper.
REFERENCES
I. Balazevic, C. Allen, and T. M. Hospedales. Multi-relational poincaré graph embeddings. In NeurlPS, pages 4465 4475, 2019.
A. F. Beardon. The geometry of discrete groups, volume 91. Springer Science & Business Media, 2012.
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.
A. Bordes, N. Usunier, A. Garcia-Durán. Weston, and O. Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pages 2787-2795, 2013.
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.
I. Chami, Z. Ying, C. Ré, and J. Leskovec. Hyperbolic graph convolutional neural networks. In NeurIPS, pages 4869 4880, 2019.
I. Chami, A. Wolf, D. Juan, F. Sala, S. Ravi, and C. Ré. Low-dimensional hyperbolic knowledge graph embeddings. In ACL, pages 6901-6914 Association for Computational Linguistics, 2020.
H. Cho, B. Demeo, J. Peng, and B. Berger. Large-margin classification in hyperbolie space. In AISTATS, volume 89 of Proceedings of Machine Learning Research, pages 1832-1840. PMLR, 2019.
R. Cui, M. Schumer, K. Kruesi, R. Walter, P. Andolfatto, and G. Rosenthal. Data from: phylogenomics reveals extensive reticulate evolution in xiphophorus fishes. Dryad Data Repository, 2013.
J. Dai, Y. Wu, Z. Gao, and Y. Jia. A byperbolic-coo-hyprooliii graph convolutional network. In CVPR, 2021a.
S. Dai, Z. Gan, Y. Cheng, C. Tao, L. Carin, and J. Liu. Ape-vae: Text generation in hyperbolic space.
In NAACL-HIT, pages 416-431. Association for Computational Linguistics, 2021b.
N. Fisher. Notes on curvature in complex hyperbolic space. URL htttts::/sitts.ttuu
R. Fu, J. Guo, B. Qin, W. Che, H. Wang, and T. Liu. Learning semantic hierarchies via word embeddings. ACL (I), pages 1199-1209, The Association for Computer Linguistics, 2014.
O. Ganea, G. Bécigneul, and T. Hofmann. Hyperbolic entailment cones for learning hicrarchical embeddings. In ICML,, volume 80 of Proceedings Machine Learning Research, pages 1632-1641. PMLR, 2018a
O. Ganea, G. Bécigneul, and T. Hofmann. Hyperbolic neural networks. In NeurlPS, pages 5350-5360, 2018b.
10

---

Under review as a conference paper at ICLR 2022
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)310-322 2012.
M. Gromov. Hyperbolic groups. In Essays in group theory, pages 75-263, Springer, 1987.
A. Gu, F. Sala, B. Gunel, and C. Ré. Learning mixed-curvature representations in product spaces, In ICLR (Poster). OpenReview.net, 2019.
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.
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.
S. Kobayashi and K. Nomizu. Foundations of differential geometry, volume 1. New York, London, 1963.
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.1 https://link aps wttps//////o/o.ooo//////. 1103/ 1103/h/ysee/ee 82. 036106
URL
Q. Liu, M. Nickel, and D. Kiela. Hyperbolic graph neural networks. In NeurlPS, pages 2228-239,, 2019.
Mahdisoltani, J. Biega, and F. M. Suchanek. YAGO3: knowledge base from multilingual wikipedias. In CIDR. www.cidrdb.org. 2015.
G. A. Miller. Wordnet: A lexical database for english. Commun, ACM, 38(11):39-41, 1995.
N. Mok. Metric rigidity theorems Hermitian locally symmetric manifolds, volume 6. World Scientific, 1989.
M. Nickel and D. Kiela. Poincaré embeddings for learning hierarchical representations. In NIPS, pages 6338-6347, 2017.
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.
M. Nickel, Tresp, and H. Kriegel. A three-way model for collective learning on multi-relational data. In ICML, pages 809-816. Omnipress, 2011.
G. Rateliffe, S. Axler, and K. Ribet. Foundations of hyperbolic manifolds, volume 149. Springer, 1994.
F. Sala, C. D. Sa, A. Gu, and C. Ré. Representation tradeoffs for hyperbolic embeddings. In ICML., volume 80 Proceedings of Machine Learning Research, pages 4457-4466. PMLR, 2018.
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++. ICLR (Poster), 2021.
V. Shwartz, Y. Goldberg, and Dagan. Improving hypernymy detection with an integrated path- path-based and distributional method. In ACL The Association for Computer Linguistics, 2016.
O. Skopek, O. Ganea, and G. Bécigneul. Mixed-curvature variational autoencoders. In ICLR. OpenReview.net, 2020.
R. Sonthalia and A. C. Gilbert. Tree! am no tree! I am low dimensional hyperbolic embedding. In NeurIPS, 2020.
11

---

Under review as a conference paper at ICLR 2022
F. M. Suchanek, G. Kasneci, and G. Weikum. Yago: core of semantic knowledge. In WWW, pages 697-706. ACM, 2007.
Z. Sun, Z. Deng, J. Nie, and J. Tang, Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR (Poster). OpenReview.net, 2019.
Sun, M. Chen, W. Hu, C. Wang, J. Dai, and Zhang. Knowledge association with hyperbolic knowledge graph embeddings. In EMNLP (1), pages 5704-5716. Association for Computational Linguistics, 2020.
T. Trouillon, J. Welbi, S. Riedel, É. Gaussier, and G. Bouchard. Complex embeddings for simple link prediction. In ICML, volume 48 JMLR Workshop and Conference Proceedings, pages 2071-2080. JMLR.org. 2016.
W. Wirtinger. Zur formalen theorie der funktionen mehr komplexen veränderlichen. Mathematis- che Annalen, 97(1):357-375 1927.
B. Yang, W. Yih, X. He. J. Gao, and L. Deng. Embedding entities and relations for learning and inference knowledge bases. In ICLR (Poster), 2015.
Zhu, Pan, C. Zhou, Wu, Cao, and B. Wang. Graph geometry interaction learning. In NeurlPS, 2020.
12

---

Under review as a conference paper at ICLR 2022
A MORE PRELIMINARIES
A.1 DEFINITION OF CURVATURE
The curvature describes the curve of Riemannian manifolds and controls the of geodesic deviation. In this paper, curvature refers to the sectional curvature.
Definition (Curvature). Given a Riemannian manifold and two linearly independent tangent vectors at the same point, and V, the (sectional) curvature defined as
(R(u, u) K(u, (v. (u.
where R is the Riemann curvature tensor, defined by the convention R(u, v)w = Vn V.w V. V. Vl,,v]. w. Here V indicates the Levi-Civita connection, whose definitions are given below.
Before defining Levi-Civita connection, need to first define the affine connection.
Definition (Affine connection). Let M be smooth manifold and let (T) be the space vector fields M, i.e., the space of smooth sections of the langent bundle T M. Then an affine connection on M is bilinear map
T(TM) ((TM) + I(TM) (X,Y) VXY,
such that for all f in the set of smooth functions on M, written C (M,R), and all vector fields X, Y.Y M:
1. 1 Le. is C (M, in the first variable;
2. Vx( 0x + JVXY, where dx denotes the directional derivative, i.e., V satisfies
Leibniz rule the second variable.
Next, define the Levi-Civita connection.
Definition 3 (Levi-Civita connection). An affine connection V is called Levi-Civita connection if
1. it preserves the metric, iee. vg=0. =0
2. it is lorsion-free, i.e., for any vector fields X and Y we have VxY Vy [X,Y], where [X, Y] is the Lie bracket of the vector fields X and Y.
A.2 THE DISTANCE FUNCTION ON THE UNIT BALL MODEL
The distance function in Eq. (9) maintains the tree-like metric properties, When the points are very close to the origin, it approximates to the Euclidean distance. Additionally, when point closer to the origin, it has relatively smaller distances the other points. Correspondingly, the points near the boundary have very large distances from each other. Therefore, in ideal conditions, the root node of a tree is embedded in the origin while the deeper nodes embedded farther away from the origin. Recall that the distance function in the real hyperbolic space (Nickel and Kiela (017)) has similar properties since the real hyperbolic space, the totally geodesie subspace the complex hyperbolic space, inherits the tree-like metrics. More details about the Bergman metric and distance function can be referred to Chapter 3.1 in [Goldman 1999.
B PROOF OF THEOREM
In Section 3.2 the paper, we presented Theorem about the curvature of the complex hyperbolic space H Goldman 1999). The sketch explanation is that all unit tangent vectors are equivalent, but all directions are spanned by two unit tangent vectors. Before proving Theorem 1, we need to introduce the definition of Kühler structure (Mok) 1989).
Definition (Kähler structure). A Kühler structure can be defined any of the following equivalent
ways:
13

---

Under review as a conference paper at ICLR 2022
1. A complex structure with closed, positive (1,1)-form.
2. A Riemannian structure with complex structure such that the corresponding exterior 2-form is closed.
3. A symplectic structure with compatible integrable almost complex structure which is positive.
Recall that in Section 3.2 we defined the complex hyperbolic space HH using the projectivization of the negative zone with Hermitian form ((z, w)). Denote as the imaginary part of the Hermitian form (. i.e., w(z, w) z/2 ((zz, w)) ([w, z}i ). then according to (Goldman 1999). the metric w positive and closed, and necesssarily has type (1, 1). Then by the first definition in Definition HIG is Kähler structure.
Let M be a Kähler manifold and z M. Denote T.M as the tangent space of M at and J: TTM - 'TM is an endomorphism. As proved in (Kobayashi and Nomizu 1963), the curvature of real 2-planes the tangent space T&M has the following properties:
Theorem Let M be a connected Kähler manifold of complex dimension 2. If the holomorphic sectional curvalure K (p), where is plane in TaM invariant by J. depends only then M is space of constant holomorphic sectional curvature.
Next, we give proposition in (Kobayashi and Nomizu 1963). which is about the curvature of plane.
Proposition 1. If u, v is orthonormal basis for plane and we set the curvature of K(p) = R(u, v), where R(u, v) is the Riemann curvature tensor, then
K(p) = 1 3 cos² a(p)).
where ad()) is the angle between p and (p).
Finally, we prove Theorem as follows.
Proof. Let M be Kähler manifold and E M. From Theorem 2 the corresponding sectional curvature function of real 2-planes in Tz M is completely determined by the sectional curvature function restricted complex lines T M, If the sectional curvature of every complex line in TM equals k, then M is said to have constant holomorphic sectional curvature k.
Then from Proposition we can know that in this case, the sectional curvature 2-dimensional subspace S C TTMiL is
K(S) 1 + 3 cos a(S)
(17)
where (sS) is the angle of holomorphy, defined the smallest angle between two nonzero vectors from two linear subspaces of the underlying real vector space of M.
In particular, the complex hyperbolic space HI is Kähler structure with -1. Since 0 < cos 2 ({S) < 1, then from Eq. (17). we can have -1 < K(S) < -1/4 for any 2-dimensional subspace S C M of HIg, i.e., the (sectional) curvature is not constant in Hi, but pinched between -1 and -/44. Thus we proved the non-constant curvature of Hg.
Specifically, discuss the complex projective lines and totally real planes in the unit ball model of the complex hyperbolic space:
B = (21, 1) + + 12 1 < 1}.
(18)
First let's consider the case of complex projective lines. Consider a complex line L in C that intersects the unit ball model B Let z be any point in L. We can apply an element of PU(n, 1) to L so that it becomes the last coordinate axis {0, 2n 12, E C). whose intersection with 8 is the disk [,, < 1. Then the restriction of the Bergman metrie to this disc is the Poincaré metric (Beardon. 2012) of constant eurvature -1.
By
14

---

Under review as a conference paper at ICLR 2022
In order this, let (0,
2n, 1) and (0, Wn: 1).
E L n B then from Eq. (9) in
Section 4.1 the distance between z and w is given by Eq.
Then we have
cosh?
d (z, w)
Zz w w. z))
2n w
1
(19)
2
Zz z)
( W. w)
(12n 2
1)([ml 1 1)
which is just the Poincaré metric (Beardon 2012)
Next consider a totally real plane p. Any totally real plane p is the image under an element of PU(n, 1) of the subspace comprising those points of B with real coordinates, that is actually an embedded copy of the real hyperbolic space Hi = [(x1..... -En [r)).i,,.....
E [R]. This subspace
intersects BE in the subset consisting of those points with 2 + ..... + In < Then the Bergman metric restricted to this real-space unit ball is just the Klein- Beltrami metric (Ratcliffe et al. 1994) on the unit ball in R" with constant curvature 1/44.
To see this, let x = (#1...., In. 1) and y (V1.... Un. 1), x, y E H2 n B then apply the similar process with the above, we have
coshi2 d (x. (x,
x x)
(E18/1 + ... Fnyn 1)2
(20)
2
y)
{if + x. 1)(v + u2 1)
which the curvature 1/4
metric (Rateliffe et al. 1994] on the unit ball in R" with constant
Therefore, we proved that the curvature of HD is - in the directions of complex projective lines while 1/4 in the directions of totally real planes.
Remark. Curvature in the complex hyperbolic space is a very complicated topic in geometric group theory and differential geometry. The complex projective lines and the totally real planes are two kinds of special subspaces, whose curvatures are presented above. For the subspace that lives in between the two special cases, its curvature can be computed accordingly. Since digging into all the curvature details of the complex hyperbolic geometry is the essential part of our work, we have omitted the related content in our paper. We refer the interested readers to (Fisher) for an interesting example in the complex hyperbolic space (its curvature differs with our work with constant multiplier 4). In Section 5 and Figure 5 of (Fisher). the author explored the curvature of triangle complex hyperbolic geometry with numerical computation.
C DERIVATION OF DISTANCE GRADIENT IN THE UNIT BALL MODEL
The distance function in the unit ball model is given by Eq. ( We need to compute the distance gradient V Edgg (z, w) adgp (z.w) Bdgg (z.w) during the Riemannian optimization. The full By
8x
derivation is as follows.
First, we need to introduce Wirtinger derivatives (Wirtinger 1927). which constructs differential calculus for differential functions on complex domains.
Definition 5 (Wirtinger derivatives). The partial derivatives of (complex) function f(z) of complex variable z x + iy C, C. E TR, with respect to and T iy, respectively, are defined as:
0f(2,
a - 1 )),,)) dr
0f(z,z)
i ( + i f
1 0
Oy
0z
2
Ox
Oy
The Wirtinger derivatives can be rewritten as:
0f(z,
à i
+ f(z,
(21)
Or
0=
03
0
0
02 f(
(22)
Oy
02
15

---

Under review as a conference paper at ICLR 2022
Let cos (z, w)) = 2 2.w (..))
1, then dap (z, w) arcosh(p) In(p + vp² - 1).
(xx)) (w.w))
Let (21, 2n, 1) BC then
Zd (2, w)
Odgg (z, w)
Op
Op
Ozj
Op
dzj
p2
Ozj
(=10T+ t-2 Wh
1). (w.z).
(2121 f Zn Rn
w.w.
V12
Ōzj
W (W, z))
27 w)) ((w, z))
(23)
Vp2 -1
(1z, 2)
((w, w))
(2, 2)1²
((w, w))
for 1 م S n. Similarly, we can have
Ødgy (z, w)
Wy (1z, w\)
24 flz w)) (Ww, 23) (1z, 2i3² ((w, w)
(24)
dzj
p
(12 2))
((w, w))
Then by Eqs. 21 23
and
24 we obtain
By (z, w)
Bd (z, w)
4 Re ((z, w w))
(2, w)) ((.. ((w,
(25)
dr,
Ōzj
Uzj
pp²
(z, z)) (w. w)
(1z, z)) ((w, w))
Similarly, by Eqs. 12
23
and (24 we can get
Ödgg i( Ødgg (z. w)
Odg (z, w)
mml ((z, w)ww;) (12, 2)) (w, w) (z. 2)) (ww, wi)
(z, w 2398)1 (26)
Oyj
Ōzj
Ōzj
Vp²
where Re(.) and Im(-) denote the real and the imaginary part respectively. Then we can have
ddgg
4
Re(((z, w))w)
(z, w|) (( (w, z)ix
0x
V p2 (12, 2))
(w, w))
(z, z)} {/ (w: w)
0dg
4
Iml ((z, w))w)
(zz, w }) (ww 2)yy
Qy
p2
(1z, x)) ((w. w)
(z, 2) (1 (ww, w))
which are Eqs.
and
14] in Section
4.3
D DEFINITION OF 8- H-HYPERBOLICITY
In this section, we give the definition of 6-hyperbolicity (Gromov) 1987> which measures the tree- likeness of graphs. The lower corresponds to the more tree-like graph. Trees have 6-hyperbolicity. Definition (8- (6-hyperbolicity). Let a, b, d be vertices of the graph Let S₁, S2 and S3 be S1 dist(a, b) + dist(d, c), e2
dist(a,e) + dist(b, d), dist(a, d) + dist(b. c).
Suppose Mi and M2 are the two largest values among S,, S2. S3 and Mi 2 M2. Define by c, M1 M2. Then the 6-hyperbolicity of G is defined
8(G) =
max hyp(a, b, c.c).. d). a.b.c.deV(())
That is, 8(G) is the maximum of hyp over all possible 4-mples (a, b, c, d) divided by 2.
E MULTITREE STRUCTURE
In combinatories and thher-the mathematics, multitree structure is directed acyclic graph (DAG) in which the set of vertices reachable from any vertex induces a tree, or partially ordered set (poset) that does not have four items o, and d forming diamond suborder with b S d and
16

---

Under review as a conference paper at ICLR 2022
Priapella
Priapella
Priapella
Priapella
Psjonesii
Psjonesii
P Psjonesi
Psjonesil
Xmaculatus
Xalvarezi
Xhellerii
Xmaculatus
Xandersi
Xhellerii
Xsignum
Xandersi
Xxiphidium
Xmayae
Xalvarezi
Xmilleni
Xmilleri
Xsignum
Xmayae
Xevelynae
Xevelynae
Xmonticolus
Xcontinens
Xvariatus
Xvariatus
Xclemenciae
Xpygmaeus
Xcouchianus
Xcouchianus
Xmaculatus J
Xmnllilineatus
Xgordoni
Xgordoni
Xevelynae
Xnigrensis
Xmeyen
Xmillen
Xmontezumae
Xxiphidium
Xclemenciae
Xandersi
Xnezahuacoyo
Xmonticolus
Xmonticolus
Xvariatus
Xcortezi
Xclemenciae
Xsignum
Xxiphidium
Xbirchmanni,
Xhelleri
Xhélleri
Xcouchlanus
Xmalinche CH
Xsignum
Xalvarezi
Xgordoni
Xmontcoolus
Xalvarezi
Xciemenc lae
Xmayse
Xcontinens
Xcontinens
Xmaculatus
Xconônens
Xpyamaeus
Xpygmaeus
Xmilleri
Xpygmaeus
Xmultiineatuus
Xmulblineatus
Xevelynae
Xmuubiiinaauu
Xnigrensis
Xnigrensis
Xvariatus
Xnigrensis
Xmontezumae
xmontezumae
Xandersi
Xmontezumae
Xnezahuacoyo
Xmalinche CH
E
Xxiphidium
Xbirchraann Xmalinche CH Xcortezi Xnezahuacoyo
Xcortezi
Abirchmanit
Xcouchianus
Xbirchmanni
T
Xcortezi Xmezahuacoyo
Xgordoni
Xmalinche
Xmeyeri
Figure 3: Some subtrees of Xiphophorus. The multitree dataset Xiphophorus contains 160 trees on
26 Xiphophorus fishes as leaf nodes.
6
2
5
balanced tree: r=2, h=2 0-hyperbulicity--
compressed graph: m=7. k=1 8hyperbolicity-00
compressed graph: m=7. k=1 6-hyperbolicity-0
compressed graph: m-7, k-2 d-hyperbulicity-O..
Figure Simple examples of the synthetic data. The numbers (0, I,...: 6} represent the nodes. The compressed graph-(m = 7, k 2) on the right are aggregated from the middle two compressed graphs-(m = =1).
a but with and incomparable to each other (also called a diamond-free poset (Griggs al. 2012
Obviously, the multitree structure is not a tree since one child node can have multiple parents in multitree. Note that the multitree structure is also different with 1-N structure since the multitree has more strict conditions, that is, the multitree is diamond -rre poset. By comparison, the 1-N structure more general taxonomies. For example, the subgraph of TAG03-wikiObie is-a, British screenwriters), (Neil Gaiman, is-a, British fantasy writers), (British screenwriters, is-a, British writers), (British fantasy writers, is-a, British writers)] is 1-N structure, but it not multitree structure, because British screenwriters and British fantasy writers are incomparable to each other, i.c., there is no partial order between them.
{(Nii Gaiman,
Recall that our synthetic compressed graph is also aggregated from multiple trees, but it is not the multitree either. compressed graph is aggregated from multiple random trees on the same set of nodes while the trees in multitree structure share the same leaf nodes. Multitrees are widely used to represent multiple overlapping taxonomies over the same ground set. The dataset Xiphophorus is multitree structure containing 160 trees 26 leaf nodes. Some examples of its subtrees are in Figure 3 and its cloud tree plot in Figure
F
MORE EXPERIMENTS
F.I
DATA
In Section 5.1.I in the paper, introduced how generate the synthetic data:
*Here denotes the partial order defined in the graph, e.g., the hypemymyy relation.
17

---

Under review as a conference paper at ICLR 2022
Table 5: Hyperparameters of all methods.
Model
Synthetic & Xiphophorns
ICD10
WordNet-noun
Retations:
Meraaione: 32;
lientions: 32;
Serations:
optimiration: no opr;
optimization: no spe:
optiiizatio:: no oyt,
optimization: no opt:
TreeRop
pre allocation fraction: 2.0;
aihreade: 16;
nbrreas: 16;
allocation fractio: 1.3:
pre allocation fraction: 1.3: athrend:: 16:
pre Pre-aalooattonn fraction: 1.3:
nthreads: 16;
terminatedd edge weight:
terminated edge weight
terminated edge weight:
terminated odge weight: O:
tialv/daaset 3
mabslhaasee:: 3
triali/Sateeet
ttalsshhtsset
mantiold: exclidion:
mansfodd: enclddene
mannioos:: euclidean:
leaming
learning 1:
learning
epocls: 1500;
epcchs: 1200:
opochs: 1500:
dampening: 0.70;
dungening: 0.73;
dampening: U.75;
Eaelidean
burnin; 20:
bumin: 20:
burnin. 20; auittiplee:: 0
muhippie:: 0.01;
bumin multiplier:
negative sample: 50:
negative sample: 50:
negative sample: 50:
negative multiplier: 0.1;
negative multipiier D.1:
negative mulliplie:: 0.1;
max nana: 5OUD0
max noraw GDOOI
max noem: 50000
mamioot:: polocare:
maniloki: potticure.
maniiold: poincare;
caamitou:: potscare:
learning rale: 0.3;
leaming rale: 1;
learning rate: 1:
learning rale: 1:
epochs: 1510:
epocts:: 1500:
epochs: 1200;
epochs:: 1500,
dampening: 0. 75:
dampening: 1.0;
dumpening: 1.0:
dampening: 1.0;
Poincaré
burnis: 20:
burnin: 20;
bumin:
burain mule 01:
burnin muhiipier: 0.01;
bumin muttipker: U.D1:
burnin multipler:: 0) U.U1;
neguiive sample: 50;
negative sample: 50;
negative sample: 50;
negutive sample: S0:
neguiive multplier:: 0.1:
negative multiplier: 0.1;
negative mulippier. 0.1:
negative muliipier::
max norm:
5
max nome: 1 e 0
max norm: e
max norm:
mamifod: loreurt:
muniiok: loventz
manifoll: Joreniz:
mamifokE forenc:
learning mile:
laminn rate: 0.5;
learning rate:
kesning
epochs; 1500:
epochs: 1500:
epechs: 1200:
epochs: 1500:
dampening: 0.75:
dampening: 1.0;
dampening: 1.0:
dampening: 1.0;
Hyperboloid
burnin: 20:
burnin; 20:
bumin: 20:
burnin: 20:
burnin multiplier: 01:
burnin multiplie:: 0.01:
bumin multiplier: 01:
multiplie::
negative sample: 50;
negative sample: 50;
negative sample: 50:
negative sample: 50;
negutive muttilier: U.1:
negative multiplier: 0.1:
negative muhippier 0.1:
negative multiglee:: 0.1:
max
mamoon
no Mustorn
stanifold: woitsoll;
maniloki: unibaai.
musifld: anitball
manifodd muitbol!
learning mie: &
leaming rate: 11;
learning rate: 14;
lesrning mie: 12:
epochs: 1500:
epochs: 200;
epocha: 1200:
epachs: 900;
dampening: O.
dampening: 1.0;
dumgeninn: 1.0.
dampening:
UnidBall
burnin: 20:
burnin: 20:
humin: 20:
burein: 20:
bursin multipllr:: 0.01:
burnin mahtipiie: 0.01;
humin multiplier: D.D1;
burein sultiplier: 0.01:
neguive sample: 50:
negative sample: 50:
negative sample: 50:
negative sample: 50:
negative mulippier:
negative multiplier: 0.1;
negorive mullipiien
negative multiplier:
mus norm:
max norm: I e
mas norm: -
max norm: -
Synthetic. We generate various balanced trees and compressed graphs using the NetworkX pack- age (Hagberg et al., 2 For balanced trees, we generate the balanced tree with degree r and depth h. For compressed graphs, we generate random trees on m nodes and then aggregate their edges to form graph.
We give some examples of the synthetic data in Figure 4 As we can see, the compressed graphs- (m = 7, h 1) are random trees on 7 nodes, so their d-hyperbolicities are O. The compressed graph-(m = 7, = 2) is no longer a tree after aggregating from two trees. Its local structures are more varying and complicated.
Here we also give the public links of the real-world data used in our experiments: Xiphophorus (Cui et al. 2013) ICD10 (Brämer 1988 YAGO3- (Mahdisoltani et al. 2015) WordNet- noun Miller 1995
F.2 HARDWARE
We conduct all the experiments except TreeRep four NVIDIA GTX 1080Ti GPUs with 8GB memory each, For TreeRep, we need more memory to store the distance matrices, so we use a 96-core NVIDIA T4 GPU server with 503GB memory.
httas://aag--kovledep...
httss//uerdnet.rrinttto....
18

---

Under review as a conference paper at ICLR 2022
F.3 HYPERPARAMETERS
For the baselines (TreeRep (Sonthalia and Gilbert 2020 10 Euclidean, Poincaré (Nickel and Kiela 2017), and Hyperboloid (Nickel and Kiela 2018) we their public codes to train the embeddings. For all methods, we tune the hyperparameters by grid search. For the graph reconstruction task, we tune the hyperparameters on balanced tree-(15.3) in 20-dimensional embedding spaces (10- dimensional complex hyperbolic space for UnitBall), while for the link prediction task, we tune the hyperparameters on the validation sets in 32-dimensional embedding spaces (16-dimensional complex hyperbolic space for UnitBall). The hyperparameters are given in Table
F.4 EVALUATION
Our evaluation closely follows the setting of (Nickel and Kiela 2017 2018), which infers the hierarchies from distances in the embedding space. Specifically, for each test edge w),, compute the distance between the embeddings day (z, w) and rank it among the distances of all unobserved edges for z: {dag (z, w') (z, w') & "rrininng]. We then report the following evaluation metrics of the rankings. Denote Freest as the test edge set and V = (=|Rw, (z, w) E Frest) ) as the test node set. Let N E.g {WI, 122,..... NE, be the ground truth neighbor of node z.
Mean average precision (MAP). The average precision (AP) is way to summarize the precision- recall curve into a single value representing the average of all precisions and the MAP score is calculated by taking the mean AP over all classes. For node from the learned embeddings, can obtain the nodes closest to its embedding z. Let Riz., be the smallest set of such nodes that contains w; (the i-th neighbor of 2). Then the MAP is defined as:
MAP
Σ MENNE,
Precision(Rag
IV
NE
ZEV
Mean reciprocal rank (MRR). The MRR is statistic measure for evaluating list of possible responses a sample of queries, ordered by the probability of correctness. For node 2, from the learned embeddings, we can rank its distances with other nodes from the smallest to the largest. Let ranking be the rank of wa (the i-th neighbor of z). Then the MRR defined as:
1 MRR
Σ NEV NE
Σ WENE,
V
rank
The proportion of correct types that rank no larger than N (Hits@N). Hits@ N measures whether the top N predictions contain the ground truth labels. For a node from the learned embeddings, we can obtain the set of N nodes closest its embedding z, denoted as R. Then the Hits@ N is defined as:
Σ I(IR ONE, 21,, =EV
Hits @ N
IV
where IQIRNN O ONE the indicator function.
F.5 GRAPH RECONSTRUCTION RESULTS ON BALANCED TREES
To compare the representation capacities of UnitBall and the hyperbolic embedding models for the tree structures, we evaluate the graph reconstruction task on the synthetic balanced trees. A balanced tree-(r, it) has degree and depth h, it has 7 +... + pd nodes and 7 +... + pd 1 edges. The 5 b-hyperbolicity of any balanced tree O. We embed the balanced trees into 20-d hyperbolic space for the baselines and 10-d complex hyperbolic space for UnitBall.
Figure 5 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), 2), (10,3), all methods have very good performances,
16 httpps://giii httpt:/ss//giichhb.coooocs/e/ees http:/wwww.oooooooa/ooe /Treekee
pp weaare-mbeddiine vides the implementation for Fuclidean, Poincaré, and Hyperholoid.
ptttps://githie thub. com http://ccccaccoc///e htmm/facebookreseee
The repository pro-
19

---

Under review as a conference paper at ICLR 2022
Hyperbolii
100
210
1.3
100
03
80
63
80
Hitgp 3 (K6)
Hitsg33
20
20
15
p=20
r-15
cm25
MAP hm
Hitsog hm3)
10)
(on 1=10)
Figure 5: 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.
Table Evaluation of graph reconstruction on the real-worf world taxonomies (the dimension is 32 for TreeRep and 16 for UnitBall). For memory cost, the unit is GiB.
ICDI0
VAGO3-wikiObije Hits@1
WordNet- noun Hits@
MRR
Hits@1
Memory
MRR
Memory
MRR
Memory
TreeRep
26.74
91.97
30
36.71
95.39
21
16.99
90.51
226
UnitBall
47.47
98.93
0.005
39.65
96.10
0,005
28.88
94.95
0.02
demonstrating the expected powerful capacities of hyperbolic geometry and complex hyperbolic geometry on tree structures. However, when the breadth or the depth increases, the performances of Poincaré and Hyperboloid drop rapidly, suggesting that the optimization-basee embeddings in H are not effective enough for reconstructing trees of such scales.
In comparison, UnitBall and TreeRep achieve stable performances for larger trees. TreeRep learns tree structure 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 showws that UnitBall achieves comparable 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
F.6 COMPARISON WITH TREEREP ON REAL- WORLD TAXONOMY RECONSTRUCTION
In this section, we compare UnitBall with TreeRep on the real-world taxonomy reconstruction task. The results are presented in Table 6 As we analyzed in Section 5.3.1 TreeRep, as a combinatorial construction- based embedding method, performance is much better than that the link prediction task. In addition, UnitBall still outperforms TreeRep on reconstructing real-world taxonomies.
more suitable for the graph reconstruction task. Its
We also notice the memory issues of the combinatorial ienitrucctionbbased embedding methods. Although TreeRep is very efficient in embedding tree structures since it does not need the gradient- based optimization steps, it costs data. It basically a computation time vs. memory cost trade-off issue. For graph with m nodes, TreeRep needs construct matrix of size x e construct the tree structure, where 1 S c < 2 is a hyperparameter. We report the memory cost (GiB) in Table UnitBall costs much less memory to learn the embeddings.
memory resources for constructing the tree structures from
F.7 MORE RESULTS ON VARIOUS DIMENSIONS
we reported the performances in different embedding dimensions on YAGO3- wikiObjects because of the page limits. Here we present the results in 8-d, 32-d, and 128-d embedding spaces (4-d, 16-d and 64-d complex hyperbolic spaces for UnitBall) on ICDI0 and WordNet-noun in Table 7 Again, see that with the increase of the embedding dimension, Fuclidean can have big
In Section 5.3.2
20

---

Under review as a conference paper at ICLR 2022
Table 7: Evaluation of taxonomy 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 are underlined. TreeRep is not applicable 128-d WordNet-noun due the large memory cost so we do not include the results.
ICD10
S-dimensional
52-dimensional
128-dimensional
MAP
MRR
Hits@3
MAP
MRR
Hits
MAP
MRR
Hits
Euclidean
2.57
2.57
1.32
3.75
3.72
2.39
10.83
10.48
4.66
TreeRep
3.44
3,90
4.96
7.92
8.49
8.09
8.74
17.23
Poincaré
35.73
34.94
53.10
35.24
34.45
52.71
34.47
33.70
52.19
Hyperboloid
35.56
34.77
51.90
34,80
34.01
52.88
34.93
34.15
52.98
UnitBall
44.05
43.26
61.54
47.88
46.96
70.28
46.54
45.59
70.03
WordNet-noun 32-dimensional
S-dimensional
128-dimensional
MAP
MRR
Hits@3
MAP
MRR
Hits@
MAP
MRR
Hlis
Buclidean
1.07
0.63
5.59
5.36
3.16
14.33
13.35
Poincaré 25.23
23.78
27.63
25.46
23.99
27.80
25.33
23.86
27.41
Hyperboloid
25.73
24.24
27.67
25.65
24.15
27.50
25.77
24.27
27.65
UnitBall 24.91
23.76
30.27
27.29
25.93
32.95
27.29
25.91
32.77
Table 8: Results of MAP and Hits@1 I predicting 1-N edges in YAGO3-wikiObjetts. The
embedding dimension 16 for UnitBall while 32 for other models. The best results are shown in boldface.
YAkOessikOOheettss (MAP)
N for 1-N edges
1
2 ~ 5
6 ~ 10
11 ~ 20
> 20
>
Poincaré
60.73
16.87
9.28
9.31
15.29
Hyperboloid
61.49
15.01
9.25
9.50
9.54
13.80
UnitBall 58.41
26.73
13.28
10.17
11.64
23.61
YAGOS-wikiObjects (Hits@ 1)
Poincaré
36.94
12.13
0.97
0.87
0.00
9,83
Hyperboloid
38.24
12.20
0.97
0.95
0.00
6.95
UnitBall 37.64
28.63
18.98
11.82
17.73
26.02
improvements, but its performances in 128-d still cannot surpass UnitBall and the hyperbolic models in 8-d. UnitBall outperforms the baselines almost all the time. Although WordNet-noun. UnitBall in 4-d has slightly lower MAP and MRR than Poincaré and Hyperboloid 8-d, it has much higher H.ts@3.
F.8 MORE RESULTS ON 1-N STRUCTURE
In Section 5.3.3 we explored the performances on 1-N structures. Here we present results of more evaluation metrics in Table The results of UnitBall close with Poincaré and Hyperboloid in 1-1 structure. Nevertheless, UnitBall outperforms the hyperbolic baselines by a big margin in 1-N structure for N > Moreover, Unitball has considerably huge improvement for N 6, where the hyperbolic embedding models fail to make accurate predictions.
F,9 COMPARISON WITH TRAINABLE CURVATURE METHOD ArTH
Our work focuses on the representation single-relation graphs, which is a different research topic with multi-relational graph embeddings knowledge graph embeddings, it is hard to find an appropriate experimental setting to compare them. Nevertheless, to address the concerns of comparison with the trainable curvature method, here evaluate AttH (Chami et al. 2020) on the single-relation taxonomy link prediction task. We tune the hyperparameters on the validation set and report the mean results 5 running executions.
21

---

Under review as a conference paper at ICLR 2022
Table 9: Evaluation of taxonomy link prediction YAGO3-wikiOhjeess (the dimension is 32 for AttH and 16 for UnitBall).
MAP
MRR
Hits@1 1
Hits@3
AttH
30.22
28.47
9.10
43.83
UnitBall
33.33
31.85
15.62
47.41
Table 10: Evaluation on link prediction task of GIL paper in ROC AUC (the dimension is for UnitBall and 16 for HGCN and GIL.).
Disease
Airport
Pubmed
Citeseer
Cora
HGCN
90.80
96.43
95.13
96.63
93.81
GIL
99.90
98.77
95.49
99.85
98.2
UnitBall
99.09
96.61
98.80
99.34
97.64
From the results in Table 9 see that UnitBall outperforms AtH in the single hypernymy relation link prediction task. However, UnitBall cannot infer multiple relations like AtHH for now. MWe believe the future work of the complex hyperbolic embeddings will have promising improvements on multi-relational graph embeddings.
F.10 COMPARISON WITH HYPERBOLIC GNNS
Our work focuses the single-relation graph embeddings and taxonomy embeddings, so do not evaluate the neural networks in our tasks the main body of the paper. Although hyperbolic GNNs also involve graph embeddings and can deal with the link prediction task, they make use of not only the edges between nodes but also the node features. The message propagation and attention mechanism make GNNs more flexible to handle various downstream tasks than shallow embeddings. In this section, we evaluate UnitBall on the link prediction task on the datasets of GIL (Zhu et al.) 2020). The results of HGCN (Chami et al., 2019) and GIL. (Zhu et al.) (020) are copied from Table 2 of the GIL's original paper (Zhu et al. (020). We strictly follow their experimental settings and report the mean results of UnitBall in AUC over running executions. The dimension 8 for UnitBall and 16 for HGCN and GIL.
We can see that UnitBall outperforms HGCN on the five datasets. GIL is slightly better than UnitBall on most datasets while being outperformed by UnitBall on Pubmed. The results are very promising for UnitBall since UnitBall is a shallow embedding approach without deep architecture or feature interaction. We believe the complex hyperbolic embeddings will help to improve the GNNs and bring more insights into geometric deep learning.
F.11 COMPARISON WITH PRODUCT EMBEDDINGS
As mentioned in Section 2 the product space embeddings (Gu et al., 2019) tackles the challenges in varying local structures by jointly learning the curvature and the embeddings of data in product manifold. Although it is impractical to search for the best manifold combination among enormous combinations for each new structure, it is worth exploring the comparisons between the complex hyperbolic embeddings and products of hyperbolic embeddings. Therefore, in this section, we conduct experiments on the reconstruction task in synthetic compressed graphs. We evaluated the 16-dimensional UnitBall complex hyperbolic embeddings and 32-dimensional product hyperbolic embeddings on (G
1 (HH S (THE) The results are reported Table 11
Recall that each compressed graph-(m, k) consists of nodes and is aggregated from A random
trees on the m nodes. The bigger & corresponds to the denser and noisier graph. When & = 1 (6 = 0), the graph is exactly tree structure, UnitBall and the product hyperbolic embeddings both have much better performances in this case. When > 1, UnitBall still outperforms the product hyperbolic embeddings by a large margin. Especially when graph deviates from tree structures a lot, the product hyperbolic embeddings fail to reconstruct the graph while UnitBall successfully handles the noisy structures.
500, k 2, 3, the 8 is big, which means the
22

---

Under review as a conference paper at ICLR 2022
Table 11: Results of MAP and Hits graph reconstruction in synthetic compressed graphs. The best results are shown in boldface. The second best results are underlined.
Compressed graph-(m, k) (MAP)
k (m=500) 9-hyperbolicity
2
3
5
8
10
0.0
2.5
1.5
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Product- (IH 1
66.06
7.60
7.55
11.09
20.81
24.56
24.07
21.62
18.79
16.16
Product- (H 8
65.77
7.14
7.24
11.79
20.60
24.94
22.85
22.32
18.50
16.27
Product- (IT (Tr))
65.42
6.28
6.81
11.43
19.03
23.88
24.99
20.50
18.99
16.45
UnitBall
84.72
52.74
44.73
39.75
35.32
33.17
32.48
29.13
29.86
28.58
Compressed graph- (m, k]) (Hits(@3)
Product- ( 1
80.34
8.14
14.81
37.45
45.97
47.89
47.19
40.85
38.88
Product- [ )
80.34
8.35
9.43
16.23
36.23
47.98
44.87
47.19
39.84
36.87
Product- (Hr])
79.36
6.21
10.25
16.63
31.38
44.15
49.50
43.57
40.64
40.08
UnitBall-HBp
97.71
75.87
72.61
74.92
73.21
73.12
76.12
76.57
75.72
74.08
Compressed graph (m, k) (MAP)
(k=5)
100
200
300
400
500
600
700
800
900
1000
6-hyperbolicity
1.0
1.0
1.0
1.0
1.5
1.5
1.5
1.5
Product- (HT )
30.53
29.15
25.72
21.74
20.81
19.34
19.07
16.63
15.59
Product- ( (H+))
32.03
27.63
23.82
22.32
20.60
17.94
19.12
17.36
15.39
14.74
Product- (IH.) 4
31.39
27.95
23.17
19,90
19.03
17.96
18.09
16.13
13.86
13.47
UnitBall- 47.80
40.93
38.52
35.81
35.32
35.68
34.73
34.69
34.92
34.88
Compressed graph- (m k) @)))
Product-( ( 2
38.78
52.02
43.58
35.61
37.45
34.29
34.54
28.34
27.44
24.77
Product- (Hr
46.94
43,43
39.53
38.38
36.23
29.58
35.84
29.35
27.55
27.60
Product- (1H 54.08
42,42
35.47
33.59
31.38
32.44
30.49
29.72
24.64
24.57
UnitBall-HiP 84.35
75.42
77.36
72.14
73.21
73.00
73.99
72.63
72.23
74.01
Table 12: Nodes embedded in the simple totally real plane of the unit ball model. The embeddings are trained by UnitBall model on link prediction task in Section [3.3.] Considering the possible numerical error, we allow the embeddings deviate the plane for small threshold instead of strictly lying in the plane.
Datascts
Nodes embedded in the totally real plane
ICD10
ICDI0-root
YAGO3-wikee tikkbess WordNet-noum
Objects (root), Physical objects, Organisms, Men entity.n.01 (root)
F.12 CASE STUDY OF NODES EMBEDDED IN THE TOTALLY REAL PLANE
Although as analyzed in Appendix curvature in the complex hyperbolic space is a very complicated topic in geometric group theory and differential geometry. Computing the curvature of an arbitrary point in the complex hyperbolic space or visualizing the curvatures everywhere are highly complicated problems, the existing work usually explored few examples by numerical computation. However, the curvatures in two special subspaces, i.e., the complex projective lines and the totally real planes, are well-studied. It is interesting to see which nodes lie the special subspaces. In this section, we find the nodes of the real-world taxonomies that are embedded in the most simple totally real plane of the unit ball model, i.c., HH B,, where H = { ((11..... xx.) "..]......)).................... l.,,,,,, E IR...
Table 12 shows that the root node of all three taxonomies are embedded in the totally real plane, which is in accordance with expectations since the root nodes are usually embedded close with the origin. For the more fine-go -rained taxonomy YAGO3-wikiOby embedded in this totally real plane. These nodes actually form chain of hypernymy relation in the taxonomy: Men + Organisms Physical objects Objects. Recall Theorem states
some high-level nodes also
23

---

Under review as a conference paper at ICLR 2022
that the curvature in complex hyperbolic space is pinched between -1 (in the directions of complex projective lines) and -1/4 (in the directions totally real planes). From the results in the three taxonomies, that the high-level nodes in the hierarchical structure tend to lie in the totally real planes, which are the least curved subspaces of the complex hyperbolic space.
24


Reviews:
[{"review_id": "tHeABfrUe6", "reviewer": "Reviewer_ZxKu", "summary": "", "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 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, the author's work shows promising empirical results.\n\n## Weakness\n**1. The motivation is not clear to me. How do complex hyperbolic spaces solve the varying local structures?**\n\nThe network structure in the real world is complicated, and the use of one space with a constant curvature is likely to cause distortion. However,  the curvature of hyperbolic space is global. How does it deal with different local structures in the same network? For example, there are both tree local structures and ring local structures in a network. When using a global curvature -1, it is still difficult to take into account the two local structures simultaneously.\n\n**2. What kind of graphs are suitable to be embedded in the complex hyperbolic space is not clear**\n\n(More questions could be raised in the following discussion.)\n\n", "summary_of_the_paper": "In most real-world hierarchically structured data such as taxonomies and multitree networks have varying local structures and they\nare not trees, thus they do not ubiquitously match the constant curvature property of the hyperbolic space. The authors explore the complex hyperbolic space when EMBEDDING HIERARCHICAL STRUCTURES.", "summary_of_the_review": "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, the author's work shows promising empirical results. However, there are two key problems causing my concerns.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pDOOzPBUr0", "reviewer": "Reviewer_N6rj", "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": "## Pros:\n\n(+) The idea and intuition of introducing complex hyperbolic embedding are novel and clear.\n\n(+) The experiment shows the great performance of the proposed method.\n\n## Cons:\n\n(-) Although it is intuitively correct that variable curvature can better suit the real-world data, it is not well demonstrated in the paper besides the performance metric in the experiment. I hope there will be a figure to illustrate at least one such example.\n\n(-) In the experiment section, the authors only compare with the standard (real) hyperbolic embedding method. Why not compare with the product space with multiple hyperbolic signatures?\n\n## Detail comments\n\nOverall, I like the paper where their key idea is interesting and inspiring. The extensive experiments on different tasks and datasets (including both synthetic and real-world) are appreciated. However, I have some slight concerns about the paper.\n\nFirst, I get that intuitively we want variable curvature spaces to account for varying local structures in data. However, I wonder what is the exact effect of such “variable curvature”? For example, is it possible to show (either by figure or experiment) that certain graph structures induced embeddings concentrate more at the place with smaller/larger curvature? I think one such example can greatly improve the overall clarity, as we do see a direct effect of variable curvature in the complex hyperbolic space.\n\nSecond, the authors keep mentioning that their embedding is different from the product space of two n-dimensional real hyperbolic spaces. While I can get this through the analysis provided by the authors, it is then natural to ask whether it is better or not. I find that the authors do not conduct such experiments and thus I think it is unsatisfactory. For example, given dimension 8, can the 4-dim UnitBall embedding outperform embeddings from product spaces of 4H^2 and 2H^4? Note that according to the experiments in [1], these products of small dimension hyperbolic spaces give much better results compared to H^8 (single large dimension hyperbolic space). See also the similar findings in terms of classification downstream tasks in [2]. Also, I do not fully understand why the authors do not compare UnitBall with neural network based embedding methods such as mixed-curvature VAE [3]. Even if restricting the signature to be hyperbolic is good enough. Please either provide more experiments or elaborate on why such an experiment is not done.\n\nFinally, I find the related work section can be slightly improved. Although neural networks are overwhelming nowadays in hyperbolic learning. Classical methods such as perceptrons and SVM [4,5] should not be ignored, as they come with convergence guarantees.\n\n## References\n\n[1] LEARNING MIXED-CURVATURE REPRESENTATIONS IN PRODUCTS OF MODEL SPACES, Gu et al. ICLR 2019.\n\n[2] Linear Classifiers in Product Space Forms, Tabaghi et al. ArXiv 2021.\n\n[3] Mixed-curvature variational ´ autoencoders, Skopek et al. ICLR 2020.\n\n[4] Large-margin classification in hyperbolic space, Cho et al. AISTATS 2019.\n\n[5] Highly Scalable and Provably Accurate Classification in Poincare Balls, Chien et al. ICDM 2021.\n", "summary_of_the_paper": "The authors propose to learn complex hyperbolic embedding, which outperforms the real hyperbolic embedding in graph reconstruction and link prediction tasks. The authors argue that the complex hyperbolic space can have variable negative curvature, which can better capture the varying local structures in real-world data.", "summary_of_the_review": "Despite the slight concerns mentioned above, I still think the idea and the methodology of the paper is good enough for ICLR. The proposed complex hyperbolic spaces can potentially inspire more advanced method in the field. Hence, I lean to recommend accept of this paper.", "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": "SUnnzkmWEm9", "reviewer": "Reviewer_1y6j", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Hyperbolic spaces have gained a lot of interest for representing hierarchical data due to their relative simplicity and computational tractability – both in terms of computing the embeddings and for designing algorithms for downstream applications in such spaces (see, e.g., (Ganea et al., NeurIPS ‘18), (Cho et al., AISTATS ’19), (Weber et al., NeurIPS ‘20)). What implications has the switch to non-constant negative curvature? In comparison with embeddings spaces that are products of constant-curvature manifolds or that don’t have a constraint on the sign of curvature, how simple and tractable are the respective tools? Does this merit the additional representation power that we gain compared to the commonly used models of hyperbolic space?\n- How scalable is your approach, especially in comparison to the established hyperbolic embedding approaches you compare against? Some of the real-world data sets that you analyze are larger in size, but I did not see a comment on the computational cost of your approach.\n- In your experiments you only compare against two hyperbolic embedding approaches (Nickel and Kiela, NeurIPS ‘17 + ICML ‘18), but not against more recent methods. In particular, it is known that when learning representations in the Poincare model, data points get often mapped to points close to the boundary, which impacts the downstream performance. This can be mitigated by regularizations. It would also be good to include a comparison with embeddings into products of constant-curvature manifolds (e.g., Gu et al., ICRL ‘19).\n", "summary_of_the_paper": "The authors propose a new approach for representation learning on hierarchical data. They propose to embed hierarchical data not into the commonly used models of hyperbolic space (the Poincare and Lorentz models), but into complex hyperbolic space instead. ", "summary_of_the_review": "The paper proposes an interesting approach for embedding hierarchical data into complex hyperbolic space. By choosing complex hyperbolic space as the target embedding space, the approach tries to gain additional representation power. I have some conceptual concerns and also think that a more comprehensive experimental comparison with existing approaches would improve the paper (see comments above).", "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": "LnX4Pg4Kf3q", "reviewer": "Reviewer_PCHz", "summary": "", "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": "The paper is well written in general, and the optimization framework is clear although not novel since it follows standard Riemannian optimization.\n\n- One major weakness of the paper is that the motivation of using the complex hyperbolic space instead of more recent approaches such as mixed curvature representations [E] or ultrahyperbolic embeddings [F] is not clear. In Section 2, the authors argue that it is impractical to search for the best manifold combination of [E] for each graph. Therefore, ref [E] is ignored from the baselines in the experimental section and the only relevant baselines are standard hyperbolic approaches [B,C] that are known to be outperformed by most of their variants. The improvement over baselines [B,C] does not seem significant so it is difficult to justify using the complex hyperbolic space. At least, ref [E] should have been used for comparison.\n\nMoreover, even after reading the appendix and the experimental section, I do not understand the type of relationship that the distance function in Eq. (9) is supposed to describe. In [B,C,E,F], the motivation of the geodesic distances is given (e.g., high-level nodes tend to be closer to the origin in [B,C]). In the submission, there is no illustration or toy dataset/analysis to understand the embeddings that are learned. \n\nMost of the details (e.g., description of the dataset, optimization framework) could have been moved to the appendix to give a better intuition of the learned representations to the reader.\n\n- Another weakness of the paper is the fact that the learned representations are nonparametric embeddings. For instance, hyperbolic embeddings have been extended to hyperbolic (graph) neural networks, just like ref [E] was extended to graph neural networks [G]. How easy is it to extend the exploited manifold to (graph) neural network and perform inference of test examples?\n\n[A] Goldman, Complex Hyperbolic Geometry, Oxford University Press, 1999\n\n[B] Nickel and Kiela, Poincaré embeddings for learning hierarchical representations, NIPS 2017\n\n[C] Nickel and Kiela, Learning continuous hierarchies in the Lorentz model of hyperbolic geometry, ICML 2018\n\n[D] Absil et al, Optimization algorithms on matrix manifolds. Princeton University Press, 2009\n\n[E] Gu et al., Learning Mixed-Curvature representations in product spaces, ICLR 2019\n\n[F] Law and Stam, Ultrahyperbolic representation learning, NeurIPS 2020\n\n[G] Bachmann et al., Constant curvature graph convolutional networks, ICML 2020", "summary_of_the_paper": "The paper introduces an extension of real hyperbolic embeddings to the complex hyperbolic space [A]. The exploited geometry is an extension of the Poincaré ball that contains complex vectors (instead of real vectors) whose norm is smaller than 1. The resulting manifold is of nonconstant negative curvature, which the authors expect to be favorable for embedding various hierarchical structures. \nFollowing the optimization framework of [B] and since the complex hyperbolic space is a Riemannian manifold, Section 4.3 presents a standard Riemannian optimization framework to learn nonparametric embeddings. The proposed manifold shows (slightly) superior results compared to real hyperbolic embeddings proposed in [B,C] in the graph reconstruction and link prediction tasks.", "summary_of_the_review": "The idea looks interesting but the paper lacks providing the intuition of the learned representations, and baselines are lacking.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to learn embeddings into complex hyperbolic space. This is an extension of the popular hyperbolic-space embeddings which have shown success on graph-like and tree-like data. Reviews and discussion mostly centered around the lack of clear motivation for the work (why complex hyperbolic spaces?) and the lack of a clear advantage over other manifold embedding methods that have varying curvature. The reviewers mentioned many questions and points that they thought the work should cover. There was also concern about the baselines against which the method was compared. There was not a consensus that the paper should be accepted, and no reviewer argued strongly for acceptance, even after the author response. As a result, I recommend that this paper not be accepted at this time. I expect a new version of this paper, incorporating this reviewer feedback and especially improving the explanation of the motivation, will be a good submission for a future conference.
Decision: Reject