Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 a manifestation that the hyperbolic space can be regarded as a 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 as WordNet (Miller, 1995) and YAGO (Suchanek et al., 2007) contain many 1-N (1 child links to multiple parents) cases and multitree structures (Griggs et al., 2012), which are 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 a 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 a 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 are still retained.
For empirical evaluation, we evaluate different geometrical embedding models on various hierarchically 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 a novel embedding approach based on the
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 an extensive range of synthetic and real-world data and show the remarkable improvements of our approach.

heading: 2 RELATED WORK
text: 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 Poincaré ball model of the hyperbolic space and outperformed the Euclidean embedding methods for taxonomies. The Poincaré 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 (Bécigneul and Ganea, 2019).
Another branch of study (Sala et al., 2018; Sonthalia and Gilbert, 2020) learned the hyperbolic embeddings through combinatorial construction. Instead of optimizing the soft-ranking loss by Riemannian optimization as in (Nickel and Kiela, 2017; 2018), the construction-based methods minimize the reconstruction distortion by combinatorial construction. However, both the optimizationbased and construction-based hyperbolic embeddings suffer from the limitation in hierarchical graphs with varying local structures. To tackle the challenge, Gu et al. (2019) extended the construction-based method by jointly learning the curvature and the embeddings of data in a product manifold. Although it can provide a better representation than a single space with constant curvature, it is impractical to search for the best manifold combination among enormous combinations for each new structure.
Motivated by the promising results of previous works, extensions to the multi-relational graph hyperbolic embeddings (Balazevic et al., 2019; Chami et al., 2020; Sun et al., 2020) and hyperbolic neural networks (Ganea et al., 2018b; Gülçehre et al., 2019; Liu et al., 2019; Chami et al., 2019; Zhu et al., 2020; Dai et al., 2021a; Shimizu et al., 2021) were explored. Notably, (Chami et al., 2019; 2020) leverages the trainable curvature to compensate for the disparity between the actual data structures and the constant-curvature hyperbolic space, where each layer in the graph neural network or each relation in the multi-relational graph has its own curvature parameterization. Since we only focus on the single-relation graph embeddings and taxonomy embeddings in this work, we do not evaluate the multi-relational knowledge graph embedding models or the neural networks in our tasks.
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 et 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 as ComplEx (Trouillon et al., 2016) 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.

heading: 3 PRELIMINARIES

heading: 3.1 HYPERBOLIC GEOMETRY
text: Hyperbolic space1 is a homogeneous space with constant negative curvature.2 In the hyperbolic space HnR(K) of dimension n and curvature K, the volume of a ball grows exponentially with its radius ρ:
vol(BHnR (K)(ρ)) ∼ e √ −K(n−1)ρ. (1)
1In this paper, we use hyperbolic space to refer to real hyperbolic space and hyperbolic embeddings to refer to real hyperbolic embeddings for avoiding wordiness.
2In this paper, curvature refers to the sectional curvature. Please see Appendix A.1 for definition.
Contrastively, in the Euclidean space En, the curvature is 0 and the volume of a ball grows polynomially with its radius:
vol(BEn(ρ)) = πn/2
Γ(n/2) ρn ∼ ρn. (2)
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 a tree, while the Euclidean space is too flat and narrow to embed trees.

heading: 3.2 COMPLEX HYPERBOLIC GEOMETRY
text: Complex hyperbolic space is a homogeneous space of variable negative curvature. Its ambient Hermitian vector space Cn,1 is the complex Euclidean space Cn+1 endowed with some Hermitian form 〈〈z,w〉〉, where z,w ∈ Cn+1. Then the Hermitian space Cn,1 can be divided into three subsets: V− = {z ∈ Cn,1|〈〈z, z〉〉 < 0}, V0 = {z ∈ Cn,1 −{0}|〈〈z, z〉〉 = 0}, and V+ = {z ∈ Cn,1|〈〈z, z〉〉 > 0}. Let P be a projection map P : Cn,1 − {zn+1 = 0} → Cn, i.e.,
P :  z1... zn+1  7→ z1/zn+1... zn/zn+1  ,where zn+1 6= 0. (3) Then the complex hyperbolic space HnC and its boundary ∂HnC are defined using the projectivization:
HnC = PV−, ∂HnC = PV0. (4)
The curvature of the complex hyperbolic space is summarized by (Goldman, 1999) as follows:
Theorem 1. The curvature is not constant in HnC. It is pinched between −1 (in the directions of complex projective lines) and −1/4 (in the directions of totally real planes).
We leave the full proof in Appendix B. The non-constant curvature, which we expect to be favorable for embedding various hierarchical structures, is one of the main differences between HnC and HnR.
The complex hyperbolic space also has the tree-like exponential volume growth property. The volume of a ball with radius ρ in HnC is given by
vol(BHnC (ρ)) = 8nσ2n−1 2n sinh2n(ρ/2) ∼ enρ, (5)
where σ2n−1 = 2πn/n! is the Euclidean volume of the unit sphere S2n−1 ∈ Cn. 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 1 while preserving the tree-like properties as shown in Eq. (5).
From this section, we see that complex hyperbolic geometry and hyperbolic geometry are typically of different characteristics. The n-dimensional (n-d) complex hyperbolic space is not simply the 2n-d hyperbolic space or the product of two n-d hyperbolic spaces. This implies that our complex hyperbolic embedding model is intrinsically different from the hyperbolic embedding methods (Nickel and Kiela, 2017; 2018) or the product manifold embeddings (Gu et al., 2019).

heading: 4 UNIT BALL EMBEDDINGS
text: We propose to embed the hierarchically structured data into the unit ball model of the complex hyperbolic space. In this section, we introduce our approach in detail.

heading: 4.1 THE UNIT BALL MODEL
text: 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.
Take the Hermitian form of Cn,1 in Section 3.2 to be a standard Hermitian form:
〈〈z,w〉〉 = z1w1 + · · ·+ znwn − zn+1wn+1, (6) where w is the conjugate of w. Take zn+1 = 1 in the projection map P in Eq. (3). Then from Eq. (4), we can derive the formula of the unit ball model:
BnC = P({z ∈ Cn,1|〈〈z, z〉〉 < 0}) = {(z1, · · · , zn, 1)||z1|2 + · · ·+ |zn|2 < 1}. (7)
The metric on BnC is Bergman metric, which takes the formula below in 2-d case:
ds2 = −4 〈〈z, z〉〉2 det [ 〈〈z, z〉〉 〈〈dz, z〉〉 〈〈z, dz〉〉 〈〈dz, dz〉〉 ] . (8)
The distance function on BnC is given by dBnC (z,w) = arcosh ( 2 〈〈z,w〉〉〈〈w, z〉〉 〈〈z, z〉〉〈〈w,w〉〉 − 1 ) , (9)
Note that there are other choices of the Hermitian form 〈〈z,w〉〉, which corresponds to other models of complex hyperbolic geometry, such as 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.

heading: 4.2 EMBEDDINGS IN THE UNIT BALL MODEL
text: Given the hierarchical data containing a set of nodes X = {xp}mp=1 and a set of edges E = {(xp, xq)|xp, xq ∈ X}, we aim to learn the embeddings of the nodes Z = {zp}mp=1, where zp ∈ BnC. The objective of the embeddings is to recover the structures of input data, including the distances between the nodes as well as the partial order in the hierarchies. Here we adopt the soft ranking loss used in the Poincaré ball embeddings (Nickel and Kiela, 2017) and the hyperboloid embeddings (Nickel and Kiela, 2018), which aims at preserving the hierarchical relationships among nodes:
L = ∑
(xp,xq)∈E
log e −dBnC (zp,zq)∑
xk∈N (xp) e −dBnC (zp,zk)
, (10)
where N (xp) = {xk : (xp, xk) /∈ E} ∪ {xp} is the set of negative examples for xp together with xp. dBnC is the distance function in the unit ball model given in Eq. (9). The minimization of L makes the connected nodes closer in the embedding space than those with no observed edges.
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 to deal with more varying structures. The experiments in Section 5 exhibit that the unit ball model learns the high-quality embeddings and captures the various hierarchical structures.

heading: 4.3 RIEMANNIAN OPTIMIZATION IN THE UNIT BALL MODEL
text: We learn the embeddings Z = {zp}mp=1 through solving the optimization problem with constraint: Z← arg min
Z L s.t.∀zp ∈ Z, zp ∈ BnC. (11)
For the optimization problems in Riemannian manifolds, Bonnabel (2013) presented the Riemannian stochastic gradient descent (RSGD) algorithm, which we employ to optimize Eq. (11). To update an embedding z ∈ BnC,3 we need to obtain its Riemannian gradient ∇R. Specifically, the embedding is updated at the t-th iteration by z(t) ← z(t−1) − η(t)∇RL(z), where η(t) is the learning rate at the t-th iteration and∇RL(z) is the Riemannian gradient of L(z).
3Here we omit the subscript of zp for concision.
Algorithm 1 RSGD of the unit ball embeddings. Input: initialization z(0), number of iterations T , learning rates {η(t)}Tt=1. for t = 1 to T do
Compute ∂dBnC ∂x and ∂dBnC ∂y by Eqs. (13) and (14). Compute ∇EL(z) and∇RL(z) by Eq. (12). Update z(t) by Eq. (16).
end for
The Riemannian gradient ∇R can be derived from rescaling the Euclidean gradient ∇E with the inverse of the metric tensor ds2 in Eq. (8). Apply the chain rule of differential functions and we have:
∇RL(z) = 1
ds2 ∇EL(z) =
1 ds2 ∂L(z)
∂dBnC (z,w) ∇EdBnC (z,w). (12)
∂L(z) ∂dBnC (z,w) is trivial to compute from Eq. (10). In practical training, we implement and compute the complex hyperbolic embedding as its real part and imaginary part, i.e., z = x + iy, where i represents the imaginary unit, i.e., i2 = −1. In order to get the gradient of the distance function ∇EdBnC (z,w) in Eq. (12), we get the partial derivative with regard to the real part and the imaginary part, i.e., ∇EdBnC (z,w) = ∂dBnC (z,w) ∂x + i ∂dBnC (z,w) ∂y .
The partial derivatives of the unit ball model distance take the following formulas:
∂dBnC ∂x = 4√ p2 − 1 (Re(〈〈z,w〉〉w) 〈〈z, z〉〉〈〈w,w〉〉 − 〈〈z,w〉〉〈〈w, z〉〉x 〈〈z, z〉〉2〈〈w,w〉〉 ) , (13)
∂dBnC ∂y = 4√ p2 − 1 (Im(〈〈z,w〉〉w) 〈〈z, z〉〉〈〈w,w〉〉 − 〈〈z,w〉〉〈〈w, z〉〉y 〈〈z, z〉〉2〈〈w,w〉〉 ) , (14)
where p = cosh(dBnC (z,w)). Re(·) and Im(·) denote the real and the imaginary part respectively. The full derivation of Eqs. (13) and (14) is given in Appendix C.
Since the embedding z should be constrained within the unit ball model, we apply the same projection strategy as (Nickel and Kiela, 2017) via a small constant ε:
proj(z) = z/(|z| − ε), if |z| ≥ 1, else z. (15)
To sum up, the update of z at the t-th iteration is
z(t) ← proj ( z(t−1) − η(t)∇RL(z) ) = proj ( z(t−1) − η(t) 1
ds2 ∇EL(z)
) . (16)
The RSGD steps of the unit ball embeddings are presented in Algorithm 1.

heading: 5 EXPERIMENTS
text: In experiments, we evaluate the performances of our approach and baselines on 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 are reported in this section. For more experiments, please refer to Appendix F.

heading: 5.1 EXPERIMENTAL SETTINGS

heading: 5.1.1 DATA
text: 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.1.
Synthetic. We generate various balanced trees and compressed graphs using NetworkX package (Hagberg et al., 2008). For balanced trees, we generate the balanced tree with degree r and depth h. For
compressed graphs, we generate k random trees on m nodes and then aggregate their edges to form a graph. Some examples of the synthetic data are given in Appendix F.1.
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 on 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) (Brä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 of the sampled taxonomy to construct the YAGO3-wikiObjects dataset.
WordNet-noun. WordNet (Miller, 1995) is a 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-wikiObjects, WordNetnoun), we randomly split the edges into train-validation-test sets with the ratio 90%:5%:5%. We make sure that any node in the validation and test sets must occur in the training set since otherwise, 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 1. The Gromov’s δ-hyperbolicity (Gromov, 1987) measures the tree-likeness of graphs (refer to Appendix D for definition). The lower δ corresponds to the more tree-like graph and trees have 0 δ-hyperbolicity.

heading: 5.1.2 TASKS
text: 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.

heading: 5.1.3 BASELINES
text: We compare our approach UnitBall to the following methods: the sate-of-the-art combinatorial construction-based hyperbolic embedding method TreeRep (Sonthalia and Gilbert, 2020), the optimization-based hyperbolic embeddings in the Poincaré ball model (Nickel and Kiela, 2017) and the Hyperboloid model (Nickel and Kiela, 2018), the simple Euclidean embedding model. Euclidean, Poincaré, 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, we use their released codes to train the embeddings. For all methods, the hyperparameters 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 F.2 and the hyperparameters are listed in Appendix F.3. In all experiments, we report the mean results over 5 running executions. The code of our approach will be publicly available after the publication of the paper.
Under review as a conference paper at ICLR 2022
100 200 300 400 500 600 700 800 900100 0
m (on k=5)
0
10
20
30
40
50
M AP
(% )
100 200 300 400 500 600 700 800 900100 0
m (on k=5)
10
20
30
40
50
60
70
80
Hi ts
@ 3
(% )
1 2 3 4 5 6 7 8 9 10 k (on m=500)
0
10
20
30
40
50
60
70
80
M AP
(% )
1 2 3 4 5 6 7 8 9 10 k (on m=500)
20
30
40
50
60
70
80
90
Hi ts
@ 3
(% )
TreeRep Poincare Hyperboloid UnitBall
000 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016
017
018
019
020
021
022
023
024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054
m(k = 5) 100 200 300 400 500 600 700 800 900 1000 Edges 478 982 1474 1,965 2,468 2,976 3,476 3,983 4,468 4,970 δ-hyperbolicity 1.0 1.0 1.0 1.0 1.0 1.5 1.5 1.5 1.5 1.5
k(m = 500) 1 2 3 4 5 6 7 8 9 10 Edges 499 998 1,496 1,985 2,468 2,966 3,452 3,939 4,426 4,890 δ-hyperbolicity 0.0 2.5 1.5 1.0 1.0 1.0 1.0 1.0 1.0 1.0
000 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 39 040 041 042 043
044
045
046
047
048
049
050
051
052 053 054
m(k = 5) 100 200 300 400 500 600 700 800 900 1000 Edges 478 982 1474 1,965 2,468 2,976 3,476 3,983 4,468 4,970 δ-hyperbolicity 1.0 1.0 1.0 1.0 1.0 1.5 1.5 1.5 1.5 1.5 k(m = 500) 1 2 3 4 5 6 7 8 9 10 Edges 499 998 1,496 1,985 2,468 2,966 3,452 3,939 4,426 4,890 δ-hyperbolicity 0.0 2.5 1.5 1.0 1.0 1.0 1.0 1.0 1.0 1.0
Figure 1: Evaluation of graph reconstruction on synthetic compressed graphs in 20-d embedding spaces (10-d complex hyperbolic space for UnitBall). m 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.

heading: 5.1.4 EVALUATION
text: We use the mean average precision (MAP), mean reciprocal rank (MRR), and Hits@N as 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.

heading: 5.2 GRAPH RECONSTRUCTION

heading: 5.2.1 RESULTS ON COMPRESSED GRAPHS
text: To illustrate the benefits of 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 m nodes and is aggregated from k random trees on the m nodes. The bigger k corresponds to the denser and noisier graph.
Figure 1 depicts that the graph reconstruction results drop down with the increase of m and k, 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-based method TreeRep learns a 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 k = 1, the graph is exactly a tree, i.e., δ = 0. However, when k > 1 and δ > 0, the data metrics deviate from tree metrics, in which case it does not help much to learn a tree structure from the data as an intermediate step.

heading: 5.2.2 RESULTS ON MULTITREE STRUCTURE
text: In this section, we compare the performances of the hyperbolic models and UnitBall on Xiphophorus. Xiphophorus is 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 E 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 a stronger ability to represent the multitree structure.

heading: 5.3 LINK PREDICTION

heading: 5.3.1 RESULTS ON THE REAL-WORLD TAXONOMIES
text: In this section, we evaluate the performances on the link prediction task for real-world taxonomies. Table 2 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 hierarchically-structured data, which is consistent with the results in previous works (Nickel and Kiela, 2017; 2018). Similar to the results on the graph reconstruction task, Poincaré 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 hierarchical structures on real-world taxonomies.
We notice that TreeRep does not perform well on 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 are more suitable to 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.

heading: 5.3.2 EXPLORING THE EMBEDDING DIMENSIONS
text: In this section, we explore the performances in different embedding dimensions. The results on YAGO3-wikiObjects are presented in Table 3. 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 in 128-d still cannot surpass other methods in 8-d. TreeRep also achieves better results with the increase of dimension, but overall its performances on the link prediction task are not very promising. By comparison, Poincaré, Hyperboloid, and UnitBall achieve great results steadily. 8-d is already enough for Poincaré and Hyperboloid to handle the link prediction task while
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 in a tree each node except the root is linked to only 1 parent node. To investigate the advantages of complex hyperbolic geometry on the 1-N structures, we evaluate the performances of UnitBall, Poincaré, and Hyperboloid on predicting the 1-N edges. We evaluate on YAGO3-wikiObjects since it contains abundant 1-N 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.
In this experiment, we train the embeddings on the full transitive closure of YAGO3-wikiObjects and then predict the 1-N edges. The Hits@10 scores are reported on Table 4. 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, i.e., the edge pattern of 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 as well as handling more complicated hierarchical structures compared with the real hyperbolic embeddings.

heading: 6 CONCLUSION AND FUTURE WORK
text: In this paper, we present a 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 our theoretical grounding and empirical success, we believe the complex hyperbolic embeddings will have promising improvements on the knowledge graph embeddings, neural networks, and other related applications.

heading: REPRODUCIBILITY STATEMENT
text: • Please see Section 3 and 4 for the full set of assumptions of all theoretical results. Please see Appendix B and C for complete proofs of all theoretical results.
• Please see Section 5.1 and Appendix F.2, F.3 for the experimental details (e.g., data splits, hyperparameters, hardware, etc).
• The data used in the paper are publicly available. We cite the corresponding references and give the public data links in Appendix F.1.
• The code is proprietary for this moment. The code will be released after the the publication of the paper.

heading: A MORE PRELIMINARIES

heading: A.1 DEFINITION OF CURVATURE
text: The curvature describes the curve of Riemannian manifolds and controls the rate of geodesic deviation. In this paper, curvature refers to the sectional curvature. Definition 1 (Curvature). Given a Riemannian manifold and two linearly independent tangent vectors at the same point, u and v, the (sectional) curvature is defined as
K(u,v) = 〈R(u,v)v,u〉
〈u,u〉〈v,v〉 − 〈u,v〉2 ,
where R is the Riemann curvature tensor, defined by the convention R(u,v)w = ∇u∇vw − ∇v∇uw−∇[u,v]w. Here∇ indicates the Levi-Civita connection, whose definitions are given below.
Before defining Levi-Civita connection, we need to first define the affine connection. Definition 2 (Affine connection). LetM be a smooth manifold and let Γ(TM) be the space of vector fields on M , i.e., the space of smooth sections of the tangent bundle TM . Then an affine connection on M is a bilinear map
Γ(TM)× Γ(TM)→ Γ(TM) (X,Y ) 7→ ∇XY,
such that for all f in the set of smooth functions on M , written C∞(M,R), and all vector fields X,Y on M :
1. ∇fXY = f∇XY , i.e.,∇ is C∞(M,R)-linear in the first variable;
2. ∇X(fY ) = ∂XfY + f∇XY , where ∂X denotes the directional derivative, i.e.,∇ satisfies Leibniz rule in the second variable.
Next, we define the Levi-Civita connection. Definition 3 (Levi-Civita connection). An affine connection∇ is called a Levi-Civita connection if
1. it preserves the metric, i.e.,∇g = 0.
2. it is torsion-free, i.e., for any vector fields X and Y we have ∇XY − ∇YX = [X,Y ], where [X,Y ] is the Lie bracket of the vector fields X and Y .

heading: A.2 THE DISTANCE FUNCTION ON THE UNIT BALL MODEL
text: 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 a point is closer to the origin, it has relatively smaller distances to 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 are embedded farther away from the origin. Recall that the distance function in the real hyperbolic space (Nickel and Kiela, 2017) has similar properties since the real hyperbolic space, as the totally geodesic subspace of 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).

heading: B PROOF OF THEOREM 1
text: In Section 3.2 in the paper, we presented Theorem 1 about the curvature of the complex hyperbolic space HnC (Goldman, 1999). The sketch explanation is that all unit tangent vectors are equivalent, but not all directions are spanned by two unit tangent vectors. Before proving Theorem 1, we need to introduce the definition of Kähler structure (Mok, 1989). Definition 4 (Kähler structure). A Kähler structure can be defined in any of the following equivalent ways:
1. A complex structure with a closed, positive (1, 1)-form.
2. A Riemannian structure with a complex structure such that the corresponding exterior 2-form is closed.
3. A symplectic structure with a compatible integrable almost complex structure which is positive.
Recall that in Section 3.2, we defined the complex hyperbolic space HnC using the projectivization of the negative zone with a Hermitian form 〈〈z,w〉〉. Denote ω as the imaginary part of the Hermitian form 〈〈, 〉〉, i.e., ω(z,w) = 12i (〈〈z,w〉〉 − 〈〈w, z〉〉), then according to (Goldman, 1999), the metric ω is positive and closed, and necesssarily has type (1, 1). Then by the first definition in Definition 4, HnC is a Kähler structure.
Let M be a Kähler manifold and z ∈ M . Denote TzM as the tangent space of M at z and J : TM → TM is an endomorphism. As proved in (Kobayashi and Nomizu, 1963), the curvature of real 2-planes in the tangent space TzM has the following properties: Theorem 2. Let M be a connected Kähler manifold of complex dimension n ≥ 2. If the holomorphic sectional curvature K(p), where p is a plane in TzM invariant by J , depends only on z, then M is a space of constant holomorphic sectional curvature.
Next, we give a proposition in (Kobayashi and Nomizu, 1963), which is about the curvature of a plane.
Proposition 1. If u,v is an orthonormal basis for a plane p and if we set the curvature of p as K(p) = R(u,v), where R(u,v) is the Riemann curvature tensor, then
K(p) = 1
4 (1 + 3 cos2 α(p)),
where α(p) is the angle between p and J(p).
Finally, we prove Theorem 1 as follows.
Proof. Let M be a Kähler manifold and z ∈ M . From Theorem 2, the corresponding sectional curvature function of real 2-planes in TzM is completely determined by the sectional curvature function restricted to complex lines in TzM . If the sectional curvature of every complex line in TM equals κ, then M is said to have constant holomorphic sectional curvature κ.
Then from Proposition 1, we can know that in this case, the sectional curvature of a 2-dimensional subspace S ⊂ TM is
K(S) = κ 1 + 3 cos2 α(S)
4 , (17)
where α(S) is the angle of holomorphy, defined as 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 HnC is a Kähler structure with κ = −1. Since 0 ≤ cos2 α(S) ≤ 1, then from Eq. (17), we can have −1 ≤ K(S) ≤ −1/4 for any 2-dimensional subspace S ⊂ TM of HnC, i.e., the (sectional) curvature is not constant in HnC, but pinched between −1 and −1/4. Thus we proved the non-constant curvature of HnC. Specifically, we discuss the complex projective lines and totally real planes in the unit ball model of the complex hyperbolic space:
BnC = {(z1, · · · , zn, 1)||z1|2 + · · ·+ |zn|2 < 1}. (18)
First let’s consider the case of complex projective lines. Consider a complex line L in Cn that intersects the unit ball model BnC. Let z be any point in L∩BnC. We can apply an element of PU(n, 1) to L so that it becomes the last coordinate axis {(0, zn)|zn ∈ C}, whose intersection with BnC is the disk |zn| < 1. Then the restriction of the Bergman metric to this disc is the Poincaré metric (Beardon, 2012) of constant curvature −1.
In order to see this, let z = (0, zn, 1) and w = (0, wn, 1), z,w ∈ L ∩ BnC, then from Eq. (9) in Section 4.1, the distance between z and w is given by Eq. (9). Then we have
cosh2( dBnC (z,w) 2 ) = 〈〈z,w〉〉〈〈w, z〉〉 〈〈z, z〉〉〈〈w,w〉〉 = |znwn − 1|2 (|zn|2 − 1)(|wn|2 − 1) , (19)
which is just the Poincaré 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 BnC with real coordinates, that is actually an embedded copy of the real hyperbolic space HnR = {(x1, . . . , xn)|x1, . . . , xn ∈ R}. This subspace intersects BnC in the subset consisting of those points with x21 + · · · + x2n < 1. 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 Rn with constant curvature −1/4. To see this, let x = (x1, . . . , xn, 1) and y = (y1, . . . , yn, 1), x,y ∈ HnR ∩ BnC, then apply the similar process with the above, we have
cosh2( dBnC (x,y) 2 ) = 〈〈x,y〉〉〈〈y,x〉〉 〈〈x,x〉〉〈〈y,y〉〉 = (x1y1 + · · ·+ xnyn − 1)2 (x21 + · · ·+ x2n − 1)(y21 + · · ·+ y2n − 1) , (20)
which is the Klein-Beltrami metric (Ratcliffe et al., 1994) on the unit ball in Rn with constant curvature −1/4. Therefore, we proved that the curvature of HnC is −1 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 not 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 a constant multiplier 4). In Section 5 and Figure 5 of (Fisher), the author explored the curvature of a triangle in complex hyperbolic geometry with numerical computation.

heading: C DERIVATION OF DISTANCE GRADIENT IN THE UNIT BALL MODEL
text: The distance function in the unit ball model is given by Eq. (9). We need to compute the distance gradient ∇EdBnC (z,w) = ∂dBnC (z,w) ∂x + i ∂dBnC (z,w)
∂y during the Riemannian optimization. The full derivation is as follows.
First, we need to introduce Wirtinger derivatives (Wirtinger, 1927), which constructs a differential calculus for differential functions on complex domains.
Definition 5 (Wirtinger derivatives). The partial derivatives of a (complex) function f(z) of a complex variable z = x + iy ∈ C, x, y ∈ R, with respect to z and z̄ = x − iy, respectively, are defined as:
∂f(z, z̄)
∂z =
1 2 ( ∂ ∂x − i ∂ ∂y )f(z, z̄),
∂f(z, z̄)
∂z̄ =
1 2 ( ∂ ∂x + i ∂ ∂y )f(z, z̄).
The Wirtinger derivatives can be rewritten as:
∂f(z, z̄)
∂x = (
∂
∂z +
∂
∂z̄ )f(z, z̄), (21)
∂f(z, z̄)
∂y = i(
∂ ∂z − ∂ ∂z̄ )f(z, z̄), (22)
Let p = cosh(dBnC (z,w)) = 2 〈〈z,w〉〉〈〈w,z〉〉 〈〈z,z〉〉〈〈w,w〉〉 − 1, then dBnC (z,w) = arcosh(p) = ln(p+
√ p2 − 1).
Let z = (z1, . . . , zn, 1) ∈ BnC, then
∂dBnC (z,w) ∂zj = ∂dBnC (z,w) ∂p · ∂p ∂zj = 1√ p2 − 1 · ∂p ∂zj
= 2√ p2 − 1 · ∂
(z1w1+···+znwn−1)·〈〈w,z〉〉 (z1z1+···+znzn−1)·〈〈w,w〉〉
∂zj
= 2√ p2 − 1 · ( wj〈〈w, z〉〉 〈〈z, z〉〉 · 〈〈w,w〉〉 − zj〈〈z,w〉〉 · 〈〈w, z〉〉 〈〈z, z〉〉2 · 〈〈w,w〉〉 ) , (23)
for 1 ≤ j ≤ n. Similarly, we can have
∂dBnC (z,w)
∂zj = 2√ p2 − 1 · ( wj〈〈z,w〉〉 〈〈z, z〉〉 · 〈〈w,w〉〉 − zj〈〈z,w〉〉 · 〈〈w, z〉〉 〈〈z, z〉〉2 · 〈〈w,w〉〉 ) . (24)
Then by Eqs. (21), (23), and (24), we obtain
∂dBnC ∂xj = ∂dBnC (z,w) ∂zj + ∂dBnC (z,w) ∂zj = 4√ p2 − 1 (Re(〈〈z,w〉〉wj) 〈〈z, z〉〉〈〈w,w〉〉 − 〈〈z,w〉〉〈〈w, z〉〉xj 〈〈z, z〉〉2〈〈w,w〉〉 ) . (25)
Similarly, by Eqs. (22), (23), and (24), we can get
∂dBnC ∂yj = i( ∂dBnC (z,w) ∂zj − ∂dBnC (z,w) ∂zj ) = 4√ p2 − 1 (Im(〈〈z,w〉〉wj) 〈〈z, z〉〉〈〈w,w〉〉 − 〈〈z,w〉〉〈〈w, z〉〉yj 〈〈z, z〉〉2〈〈w,w〉〉 ) , (26)
where Re(·) and Im(·) denote the real and the imaginary part respectively. Then we can have
∂dBnC ∂x = 4√ p2 − 1 (Re(〈〈z,w〉〉w) 〈〈z, z〉〉〈〈w,w〉〉 − 〈〈z,w〉〉〈〈w, z〉〉x 〈〈z, z〉〉2〈〈w,w〉〉 ) ,
∂dBnC ∂y = 4√ p2 − 1 (Im(〈〈z,w〉〉w) 〈〈z, z〉〉〈〈w,w〉〉 − 〈〈z,w〉〉〈〈w, z〉〉y 〈〈z, z〉〉2〈〈w,w〉〉 ) ,
which are Eqs. (13) and (14) in Section 4.3.
D DEFINITION OF δ-HYPERBOLICITY
In this section, we give the definition of δ-hyperbolicity (Gromov, 1987), which measures the treelikeness of graphs. The lower δ corresponds to the more tree-like graph. Trees have 0 δ-hyperbolicity. Definition 6 (δ-hyperbolicity). Let a, b, c, d be vertices of the graph G. Let S1, S2 and S3 be
S1 = dist(a, b) + dist(d, c), S2 = dist(a, c) + dist(b, d), S3 = dist(a, d) + dist(b, c).
Suppose M1 and M2 are the two largest values among S1, S2, S3 and M1 ≥ M2. Define hyp(a, b, c, d) = M1 −M2. Then the δ-hyperbolicity of G is defined as
δ(G) = 1
2 max a,b,c,d∈V (G) hyp(a, b, c, d).
That is, δ(G) is the maximum of hyp over all possible 4-tuples (a, b, c, d) divided by 2.

heading: E MULTITREE STRUCTURE
text: In combinatorics and order-theoretic mathematics, a multitree structure is a directed acyclic graph (DAG) in which the set of vertices reachable from any vertex induces a tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and
a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset (Griggs et al., 2012)).4
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 a diamond-free poset. By comparison, the 1-N structure is more general in taxonomies. For example, the subgraph of YAGO3-wikiObjects {(Nei Gaiman, 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 a 1-N structure, but it is not a multitree structure, because British screenwriters and British fantasy writers are incomparable to each other, i.e., there is no partial order between them.
Recall that our synthetic compressed graph is also aggregated from multiple trees, but it is not the multitree either. A compressed graph is aggregated from multiple random trees on the same set of nodes while the trees in a 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 a multitree structure containing 160 trees on 26 leaf nodes. Some examples of its subtrees are in Figure 3 and its cloud tree plot is in Figure 2.

heading: F MORE EXPERIMENTS

heading: F.1 DATA
text: In Section 5.1.1 in the paper, we introduced how we generate the synthetic data: 4Here ≤ denotes the partial order defined in the graph, e.g., the hypernymy relation.
Synthetic. We generate various balanced trees and compressed graphs using the NetworkX package (Hagberg et al., 2008).5 For balanced trees, we generate the balanced tree with degree r and depth h. For compressed graphs, we generate k random trees on m nodes and then aggregate their edges to form a graph.
We give some examples of the synthetic data in Figure 4. As we can see, the compressed graphs(m = 7, k = 1) are random trees on 7 nodes, so their δ-hyperbolicities are 0. The compressed graph-(m = 7, k = 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),6 ICD10 (Brämer, 1988),7 YAGO3-wikiObjects (Mahdisoltani et al., 2015),8 WordNetnoun (Miller, 1995).9

heading: F.2 HARDWARE
text: We conduct all the experiments except TreeRep on 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.
5https://networkx.org/documentation/stable/reference/generators.html. 6https://toytree.readthedocs.io/en/latest/7-multitrees.html. 7https://www.who.int/standards/classifications/classification-of-diseases. 8https://yago-knowledge.org/. 9https://wordnet.princeton.edu/.

heading: F.3 HYPERPARAMETERS
text: For the baselines (TreeRep (Sonthalia and Gilbert, 2020),10 Euclidean, Poincaré (Nickel and Kiela, 2017), and Hyperboloid (Nickel and Kiela, 2018)),11 we use 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 5.

heading: F.4 EVALUATION
text: 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 (z, w), we compute the distance between the embeddings dBnC (z,w) and rank it among the distances of all unobserved edges for z: {dBnC (z,w
′) : (z, w′) /∈ Training}. We then report the following evaluation metrics of the rankings. Denote Etest as the test edge set and V = {z|∃w, (z, w) ∈ Etest} as the test node set. Let NEz = {w1, w2, . . . , w|NEz|} be the ground truth neighbor set of node z.
Mean average precision (MAP). The average precision (AP) is a way to summarize the precisionrecall 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 a node z, from the learned embeddings, we can obtain the nodes closest to its embedding z. Let Rz,wi be the smallest set of such nodes that contains wi (the i-th neighbor of z). Then the MAP is defined as:
MAP = 1 |V | ∑ z∈V 1 |NEz| ∑ wi∈NEz Precision(Rz,wi).
Mean reciprocal rank (MRR). The MRR is a statistic measure for evaluating a list of possible responses to a sample of queries, ordered by the probability of correctness. For a node z, from the learned embeddings, we can rank its distances with other nodes from the smallest to the largest. Let rankwi be the rank of wi (the i-th neighbor of z). Then the MRR is defined as:
MRR = 1 |V | ∑ z∈V 1 |NEz| ∑ wi∈NEz
1
rankwi .
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 z, from the learned embeddings, we can obtain the set of N nodes closest to its embedding z, denoted as RNz . Then the Hits@N is defined as:
Hits@N = 1 |V | ∑ z∈V I(|RNz ∩NEz| ≥ 1),
where I(|RNz ∩NEz| ≥ 1) is the indicator function.

heading: F.5 GRAPH RECONSTRUCTION RESULTS ON BALANCED TREES
text: 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, h) has degree r and depth h, so it has r0 + · · ·+ rd nodes and r0 + · · ·+ rd − 1 edges. The δ-hyperbolicity of any balanced tree is 0. 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 is in small scale, e.g., (r, h) = (15, 3), (10, 2), (10, 3), all methods have very good performances,
10https://github.com/rsonthal/TreeRep. 11https://github.com/facebookresearch/poincare-embeddings. The repository pro-
vides the implementation for Euclidean, Poincaré, and Hyperboloid.
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 Poincaré and Hyperboloid drop rapidly, suggesting that the optimization-based embeddings in H20R are not effective enough for reconstructing trees of such scales.
In comparison, UnitBall and TreeRep achieve stable performances for larger trees. TreeRep learns a 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). When the input data is a tree, TreeRep exactly recovers the original tree structure. Figure 5 shows that UnitBall achieves comparable or even better performances than TreeRep on the balanced trees. The results demonstrate that UnitBall does not compromise on trees. It produces high-quality embeddings for tree structures.

heading: F.6 COMPARISON WITH TREEREP ON REAL-WORLD TAXONOMY RECONSTRUCTION
text: 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, is more suitable for the graph reconstruction task. Its performance is much better than that on the link prediction task. In addition, UnitBall still outperforms TreeRep on reconstructing real-world taxonomies.
We also notice the memory issues of the combinatorial construction-based embedding methods. Although TreeRep is very efficient in embedding tree structures since it does not need the gradientbased optimization steps, it costs more memory resources for constructing the tree structures from data. It is basically a computation time vs. memory cost trade-off issue. For a graph with m nodes, TreeRep needs to construct a matrix of size c · m × c · m to construct the tree structure, where 1 ≤ c ≤ 2 is a hyperparameter. We report the memory cost (GiB) in Table 6. UnitBall costs much less memory to learn the embeddings.

heading: F.7 MORE RESULTS ON VARIOUS DIMENSIONS
text: In Section 5.3.2, we reported the performances in different embedding dimensions on YAGO3wikiObjects 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 ICD10 and WordNet-noun in Table 7. Again, we see that with the increase of the embedding dimension, Euclidean can have big
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 on WordNet-noun, UnitBall in 4-d has slightly lower MAP and MRR than Poincaré and Hyperboloid in 8-d, it has much higher Hits@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 8. The results of UnitBall are close with Poincaré and Hyperboloid in 1-1 structure. Nevertheless, UnitBall outperforms the hyperbolic baselines by a big margin in 1-N structure for N > 1. Moreover, Unitball has considerably huge improvement for N > 6, where the hyperbolic embedding models fail to make accurate predictions.

heading: F.9 COMPARISON WITH TRAINABLE CURVATURE METHOD ATTH
text: Our work focuses on the representation of single-relation graphs, which is a different research topic with multi-relational graph embeddings or knowledge graph embeddings, so 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 we 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 over 5 running executions.
From the results in Table 9, we see that UnitBall outperforms AttH in the single hypernymy relation link prediction task. However, UnitBall cannot infer multiple relations like AttH for now. MWe believe the future work of the complex hyperbolic embeddings will have promising improvements on multi-relational graph embeddings.

heading: F.10 COMPARISON WITH HYPERBOLIC GNNS
text: Our work focuses on the single-relation graph embeddings and taxonomy embeddings, so we do not evaluate the neural networks in our tasks in 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., 2020) are copied from Table 2 of the GIL’s original paper (Zhu et al., 2020). We strictly follow their experimental settings and report the mean results of UnitBall in ROC AUC over 5 running executions. The dimension is 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.

heading: F.11 COMPARISON WITH PRODUCT EMBEDDINGS
text: 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 a 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 (H2R)16, (H4R)8, (H8R)4. The results are reported in Table 11.
Recall that each compressed graph-(m, k) consists of m nodes and is aggregated from k random trees on the m nodes. The bigger k corresponds to the denser and noisier graph. When k = 1 (δ = 0), the graph is exactly a tree structure, UnitBall and the product hyperbolic embeddings both have much better performances in this case. When k > 1, UnitBall still outperforms the product hyperbolic embeddings by a large margin. Especially when m = 500, k = 2, 3, the δ is big, which means the graph deviates from tree structures a lot, the product hyperbolic embeddings fail to reconstruct the graph while UnitBall successfully handles the noisy structures.

heading: F.12 CASE STUDY OF NODES EMBEDDED IN THE TOTALLY REAL PLANE
text: Although as analyzed in Appendix B, 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 a 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 in 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.e., HnR ∩ BnC, where HnR = {(x1, . . . , xn)|x1, . . . , xn ∈ R}. 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-grained taxonomy YAGO3-wikiObjects, some high-level nodes are also embedded in this totally real plane. These nodes actually form a chain of hypernymy relation in the taxonomy: Men → Organisms → Physical objects → Objects. Recall Theorem 1 states
that the curvature in complex hyperbolic space is pinched between −1 (in the directions of complex projective lines) and −1/4 (in the directions of totally real planes). From the results in the three taxonomies, we can see 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.

Review summaries:
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.  Following 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.

This paper proposes a method to learn embeddings in complex hyperbolic spaces. In contrast with real hyperbolic spaces, complex hyperbolic spaces have a variable negative curvature, which can handle more flexible graph structures. Experiments show that complex hyperbolic embeddings outperform real hyperbolic embeddings on synthetic and real-world graphs.