Title: LORENTZIAN DISTANCE LEARNING

Abstract: This paper introduces an approach to learn representations based on the Lorentzian distance in hyperbolic geometry. Hyperbolic geometry is especially suited to hierarchically-structured datasets, which are prevalent in the real world. Current hyperbolic representation learning methods compare examples with the Poincaré distance metric. They formulate the problem as minimizing the distance of each node in a hierarchy with its descendants while maximizing its distance with other nodes. This formulation produces node representations close to the centroid of their descendants. We exploit the fact that the centroid w.r.t the squared Lorentzian distance can be written in closed-form. We show that the Euclidean norm of such a centroid decreases as the curvature of the hyperbolic space decreases. This property makes it appropriate to represent hierarchies where parent nodes minimize the distances to their descendants and have smaller Euclidean norm than their children. Our approach obtains state-of-the-art results in retrieval and classification tasks on different datasets.

1. INTRODUCTION:

Generalizations of Euclidean space are important forms of data representation in machine learning. For instance, kernel methods rely on Hilbert spaces that possess the structure of the inner product and can therefore be used to compare examples. The properties of such spaces are well-known and closed-form relations are often exploited to obtain efficient, scalable, and interpretable training algorithms. While representing examples in a Euclidean space is appropriate to compare lengths and angles, non-Euclidean representations are useful when the task requires specific structure.

A common and natural non-Euclidean representation space is the spherical model (e.g. (Wang et al., 2017) ) where the data lies on a unit hypersphere S d = {x ∈ R d : x = 1} and angles are compared with the cosine similarity function. Recently, some machine learning approaches (Nickel & Kiela, 2017; 2018; Ganea et al., 2018) have considered representing hierarchical datasets with the hyperbolic model. The motivation is that any finite tree can be mapped into a finite hyperbolic space while approximately preserving distances (Gromov, 1987) . Since hierarchies can be formulated as trees, hyperbolic spaces can be used to represent hierarchically structured data where the high-level nodes of the hierarchy are represented close to the origin (i.e. with small Euclidean norm) whereas leaves are further away from the origin.

Since their first formulation in the early nineteenth century by Lobachevsky and Bolyai, hyperbolic spaces have been used in many domains. In particular, they became popular in mathematics (e.g. space theory and differential geometry (Ratcliffe, 2006) ), and physics when Varicak (1908) discovered that special relativity theory (Einstein, 1905) had a natural interpretation in hyperbolic geometry. Various hyperbolic geometries and related distances have been studied since then. Among them are the Poincaré metric, the Lorentzian distance (Ratcliffe, 2006) , and the gyrodistance (Ungar, 2010).

In the case of hierarchical datasets, machine learning approaches that learn hyperbolic representations designed to preserve the hierarchical similarity order have typically employed the Poincaré metric. Usually, the optimization problem is formulated so that the representation of a node in a hierarchy should be closer to the representation of its children and other descendants than to any other node in the hierarchy. Based on Gromov (1987) , the Poincaré metric is a sensible dissimilarity function as it satisfies all the properties of a distance metric and is thus natural to interpret.

In this paper, we propose to exploit the squared Lorentzian distance instead of the usual Poincaré distance. The squared Lorentzian distance is linear in the hyperbolic representations and differentiable on the whole domain, which avoids numerical instabilities and exploding gradients. Moreover, the order of the Poincaré distances between pairs of points is the same as the order of the (squared) Lorentzian distances in the unit hyperboloid model. We may therefore directly adapt existing approaches by replacing Poincaré distances with squared Lorentzian distances. The main property of interest is that the center of mass w.r.t. the squared Lorentzian distance can be written in closed form and is then easy to interpret. In particular, we show that the Euclidean norm of the center of mass of a set of different points decreases as the curvature of the exploited hyperboloid model1 decreases and tends to -∞. This property makes it ideal to represent hierarchical structures since we would like the root of a subtree to minimize the distance to all of its descendants (i.e. it should be their centroid w.r.t. to the chosen distance function) and have smaller Euclidean norm than them.

Our contributions are both analytic and experimental. We study properties of the chosen dissimilarity function and explain why they make it appropriate for the task of interest. In particular, we show that the Euclidean norm of the center of mass in the Poincaré ball representation decreases as the curvature -1/β ∈ R -of the hyperboloid model decreases (i.e. as β > 0 decreases). Curvature can then be used as a hyperparameter to implicitly enforce the root of a subtree to have smaller Euclidean norm than the other nodes. We experimentally show on different problems that exploiting the squared Lorentzian distance improves retrieval and classification performance.

2. BACKGROUND:

In this section, we provide some technical background about hyperbolic geometry and introduce relevant notation. The interested reader may refer to (Ratcliffe, 2006) for more detail.

2.1. NOTATION AND DEFINITIONS:

To simplify the notation, we consider that vectors are row vectors and • is the 2 -norm. In the following, we consider three important spaces.

Poincaré ball: The Poincaré ball P d is defined as the set of d-dimensional vectors with Euclidean norm smaller than 1 (i.e. P d = {x ∈ R d : x < 1}). Its associated distance is the Poincaré distance metric defined in Eq. (3).

Hyperboloid model: We consider some specific hyperboloid models H d,β defined as follows:

H d,β := {a = (a 0 , • • • , a d ) ∈ R d+1 : a 2 L = -β, a 0 > 0, β > 0}

(1) where a2 L = a, a L is the squared Lorentzian norm of a. The squared Lorentzian norm is derived from the Lorentzian inner product defined as:

∀a = (a 0 , • • • , a d ) ∈ H d,β , b = (b 0 , • • • , b d ) ∈ H d,β , a, b L := -a 0 b 0 + d i=1 a i b i ≤ -β (2) It is worth noting that a, b L = -β iff a = b. Otherwise, a, b L < -β for all pair (a, b) ∈ (H d,β ) 2 . Vectors in H d,β are a subset of positive time-like vectors 2 . Moreover, every vector a ∈ H d,β satisfies a 0 = β + d i=1 a 2 i .

We note H d := H d,1 the space obtained when β = 1; it is usually called the (positive sheet of the) unit hyperboloid model and is the main hyperboloid model considered in the literature.

Model space: Finally, we note F d ⊆ R d the output space of our model (e.g. the output representation of some linear model or neural network). In the following, we consider that F d = R d .

2.2. OPTIMIZING THE POINCAR É DISTANCE METRIC:

Most methods that compare hyperbolic representations (Nickel & Kiela, 2017; 2018; Ganea et al., 2018; Gulcehre et al., 2018) consider the Poincaré distance metric defined as:

∀c ∈ P d , d ∈ P d , d P (c, d) = arcosh 1 + 2 c -d 2 (1 -c 2 )(1 -d 2 ) (3)

which satisfies all the properties of a distance metric and is therefore natural to interpret. Direct optimization of problems using the distance formulation in Eq. ( 3) is numerically instable for two main reasons (see for instance (Nickel & Kiela, 2018) or (Ganea et al., 2018, Section 4) ). First, the denominator depends on the norm of examples, so optimizing over c and d when either of their norms is close to 1 leads to numerical instability. Second, elements have to be re-projected onto the Poincaré ball at each iteration with a fixed maximum norm.

To increase the numerical stability of their solver, Nickel & Kiela (2018) propose to use an equivalent formulation of d P in the unit hyperboloid model. They use the fact that there exists an invertible mapping h : H d,β → P d defined as:

EQUATION

When β = 1, we have the following equivalence:

∀a ∈ H d , b ∈ H d , d H (a, b) = d P (h(a), h(b)) = arcosh (-a, b L ) (5)

which corresponds to the (Lorentzian) angle between a and b. It is shown in (Nickel & Kiela, 2018) that optimizing the formulation in Eq. ( 5) is more stable numerically. Nonetheless, the gradient of Eq. ( 5) still tends to +∞ as d H (a, b) tends to 0. Interestingly, one can observe from Eq. ( 5) that preserving the order of Poincaré distances is equivalent to preserving the order of the opposite of Lorentzian inner products since the arcosh function is monotonically increasing on its domain [1, +∞). In the same way as kernel methods that consider inner products in Hilbert spaces as similarity measures, we consider in this paper the Lorentzian inner product.

3. PROPOSED METHOD:

We present in this section the (squared) Lorentzian distance function d L (Ratcliffe, 2006) and mention the properties that make it appropriate for our task. We give the formulation of its center of mass and observe that its Euclidean norm depends on the curvature -1/β which can then be used as a hyper-parameter of the model to implicitly enforce centroids to have small Euclidean norm. We also discuss optimization details.

3.1. LORENTZIAN DISTANCE AND MAPPINGS:

The squared Lorentzian distance (Ratcliffe, 2006) is defined as:

∀a ∈ H d,β , b ∈ H d,β , d 2 L (a, b) = a -b 2 L = a 2 L + b 2 L -2 a, b L = -2β -2 a, b L (6)

It satisfies all the axioms of a distance metric except the triangle inequality (i.e. non-negativity, symmetry, identity of indiscernibles). One interesting property is that d 2 L is linear in both a and b. Moreover, when β = 1, it defines the hyperbolic length of a curve in H d (Ratcliffe, 2006) .

Mapping: Current hyperbolic machine learning models re-project at each iteration their learned representations onto the Poincaré ball (Nickel & Kiela, 2017) or use some exponential map (Nickel & Kiela, 2018; Gulcehre et al., 2018) to directly optimize on the unit hyperboloid model (i.e. when β = 1). Since our approach does not necessarily consider that β = 1, we consider the invertible mapping g β : F d → H d,β defined as:

EQUATION

As mentioned in Section 2.1, F d is the space of our model; it is R d in practice. To be fair with baselines, the examples in F d in our experiments are non-parametric embeddings. F d may also be the output space of some parametric model such as a neural network.

We compare two examples

f 1 ∈ F d and f 2 ∈ F d with d 2 L by calculating: ∀f 1 ∈ F d , f 2 ∈ F d , d 2 L (g β (f 1 ), g β (f 2 )) = -2β -2 g β (f 1 ), g β (f 2 ) L (8) = -2 β + f 1 , f 2 - f 1 2 + β f 2 2 + β (9)

Preserved order of Euclidean norms: Although examples are compared with d 2 L in the hyperbolic space H d,β where all the points have the same Lorentzian norm, it is worth noting that the order of the Euclidean norms of examples is preserved along the three spaces F d , H d,β and P d with the mappings g β and h. The preservation with g β is straightforward:

∀f 1 , f 2 ∈ F d , f 1 < f 2 ⇐⇒ 2 f 1 2 + β = g β (f 1 ) < g β (f 2 )

. The proof of the following theorem is given in the appendix: Theorem 3.1 (Order of Euclidean norms). The following order of norms is preserved with h • g:

EQUATION

In conclusion, the Euclidean norms of examples can be compared equivalently in any space. This is particularly useful if we want to study the Euclidean norm of centroids w.r.t. examples, and also understand the significance of the following section.

3.2. CENTROID PROPERTIES:

We now study the center of mass w.r.t. the squared Lorentzian distance. Ideally, we would like the centroid of node representations to be (close to) the representation of their least common ancestor. Lemma 3.2 (Center of mass of the Lorentzian inner product). the point µ ∈ H d,β that maximizes the following problem

max µ∈H d,β n i=1 ν i x i , µ L where ∀i, x i ∈ H d,β , ∀i, ν i ≥ 0, i ν i > 0 is: µ = β n i=1 ν i x i | n i=1 ν i x i L | = β n i=1 ν i x i - n i=1 ν i x i 2 L (11)

where | a L | is the modulus of the imaginary Lorentzian norm of the positive time-like vector a. The proof is given in the appendix.

EQUATION

)

The proof exploits the formulation given in Eq. ( 6). From Eq. ( 11), one can see that the centroid of one example is the example itself. We provide in the following some side remarks that are useful to understand the behavior of the Lorentzian distance. In particular, we explain its behavior in extreme cases when β tends to 0. Theorem 3.5 (Nearest point of the squared Lorentzian distance). The point

a j ∈ A = {a k ∈ H d,β } m k=1 that minimizes the problem min aj ∈A n i=1 d 2 L (x i , a j ) where ∀i, x i ∈ H d,β is the example in A that is the closest to the centroid of x 1 , • • • , x n w.r.t. the squared Lorentzian distance.

The theorem can be used to compute medoids. It shows that distances with a set of points can be compared with only one point which is the centroid. The main interest of this theorem in our case is that it helps understand the significance of studying the properties of the centroid w.r.t. the Lorentzian distance. Interpreting distances to a set of points can be done by interpreting their centroid.

Moreover, from the Cauchy-Schwarz inequality, as β tends to 0, the Lorentzian distance in Eq. ( 9) to f 1 tends to 0 for any vector f 2 that can be written f 2 = τ f 1 with τ ≥ 0. The distance is greater otherwise. Therefore, the Lorentzian distance with a set of different points tends to be smaller along the ray that contains elements that can be written τ µ where τ ≥ 0 and µ is their centroid as can be seen in Fig. 3 .

Decreasing the curvature in the Poincaré metric formulation? As defined in Eq. ( 5), the curvature of the hyperboloid model cannot be decreased in the Poincaré metric. Indeed, the domain of arcosh is [1, +∞), and the values of the opposite of the Lorentzian inner product are in the interval [β, +∞), which is why β has to be greater than or equal to 1 when using the Poincaré metric. 

3.3. OPTIMIZATION PROBLEM AND SOLVER:

The primary contribution of this paper is the study of the squared Lorentzian distance to represent hierarchically-structured datasets. Even if models that exploit it do not optimize some centroid-based approach such as (Law et al., 2017; Snell et al., 2017) , our analysis provides tools to interpret distances between sets of similar points.

We replace the Poincaré metric used by current hyperbolic representation learning models (Nickel & Kiela, 2017; 2018) with the squared Lorentzian distance. Unfortunately, none of these approaches formulate their constraints so that the common ancestor of a set of nodes is their centroid. Nonetheless, they try to minimize the distances between similar examples to preserve orders of distances so that ancestors are closer to their descendants than to unrelated nodes. This indirectly enforces an example similar to a set of examples to be close to their centroids. We briefly describe the constraints used in Nickel & Kiela (2017) , though we note that the Lorentzian distance can be exploited in any metric learning problem.

Constraints: Nickel & Kiela (2017) consider subsumption relations in a hierarchy (e.g. WordNet nouns). They consider the set D = {(u, v)} such that each node u is an ancestor of v in the tree. For each node u, a set of negative nodes N (u) is created: each example in N (u) is not a descendant of u in the tree. Their problem is then formulated as learning the representations {f i } n i=1 that minimize:

EQUATION

)

where d is the chosen distance function. The problem is optimized via projected gradient-based method. We replace

d(f u , f v ) by d 2 L (g β (f u ), g β (f v ))

as defined in Eq. ( 9). Solver and numerical stability: Our formulation defined in Eq. ( 9) is differentiable on the whole domain F. Moreover it does not require reprojection on the hyperbolic domain due to the mapping g β : F → H d,β . We do not need to use Riemannian stochastic gradient descent (RSGD) as in (Nickel & Kiela, 2018) and can thus use any momentum-based method that keeps track of the gradient history.

In our experiments we use standard SGD optimization with momentum.

4. RESULTS:

We evaluate the Lorentzian distance in three different tasks. The first one considers similarity constraints based on subsumption in hierarchies as described in Section 3.3. The second experiment performs binary classification to determine whether or not a test node belongs to a specific subtree of the hierarchy. The final experiment is qualitative in nature and presents a community detection algorithm based on hierarchical clustering with hyperbolic distances.

4.1. REPRESENTATION OF HIERARCHIES:

The goal of the first experiment is to learn the hyperbolic representation of a hierarchy. To this end, we consider the same evaluation protocol as Nickel & Kiela (2018) and the same datasets. Each dataset can be seen as a Directed Acyclic Graph (DAG) where a parent node links to its children and descendants in the tree to create a set of edges D described in Section 3.3. The quality of the learned embeddings is measured with the following metrics: the Mean Rank (MR), the Mean Average Precision (MAP) and the Spearman rank-order correlation p (SROC) between the Euclidean norms of the learned embeddings and the normalized ranks of nodes. Following (Nickel & Kiela, 2018) , the normalized rank of a node u is formulated:

EQUATION

where lp(u) is the longest path between u and one of its descendant leaves; sp(u) is the shortest path from the root of the hierarchy to u. A leaf in the hierarchy tree then has a normalized rank equal to 1, and nodes closer to the root have smaller normalized rank. ρ is measured as the SROC between the list of Euclidean norms of embeddings and their normalized rank. We learn the representations {f i ∈ F d } n i=1 that minimize the following problem:

EQUATION

where λ ≥ 0 is a regularization parameter. The first term defined in Eq. ( 12 4) Wordnet: (Miller, 1998) is a large lexical database. As in Nickel & Kiela (2018) , we consider the noun and verb hierarchy of WordNet. More details about these datasets can be found in (Nickel & Kiela, 2018) .

Implementation details: Following (Nickel & Kiela, 2017) 3 , we implemented our method in Pytorch 0.3.1. We use the standard SGD optimizer with a learning rate of 0.1 and momentum of 0.9. For the largest datasets Wordnet Nouns and MeSH, we stop training after 1500 epochs. We stop training at 3000 epochs for the other datasets. The mini-batch size is 50, and the number of sampled negatives per example is 50. The weights of the embeddings are initialized from the continuous uniform distribution in the interval [-10 -4 , 10 -4 ]. The dimensionality of our embeddings is 10. To sample {(u, v) : rank(u) < rank(v)} in a mini-batch, we randomly sample κ examples from the set of positive and negative examples that are sampled for L neighborhood , we then select 5% of the possible ordered pairs. κ = 150 for all the datasets, except for WordNet nouns where κ = 50 and MeSH where κ = 100 due to their large size.

Results: We compare in Table 1 the Poincaré distance metric as optimized in (Nickel & Kiela, 2017; 2018) with our method for different values of β and λ (indicated in the table). Here we separately analyze the case where λ = 0, which corresponds to using the same constraints as those reported in (Nickel & Kiela, 2018) , and where λ > 0.

-Case where λ = 0: Our approach obtains better Mean Rank and Mean Average Precision scores than Nickel & Kiela (2018) for small values of β when we use the same constraints. The fact that the retrieval performance of our approach changes with different values of β ∈ {0.01, 0.1, 1} shows that the curvature of the space has an impact on the distances between examples and on the behavior of the model. As explained in Section 3.2, the squared Lorentzian distance tends to behave more radially (i.e. the distance tends to decrease along the ray that can be written τ µ where τ ≥ 0 and µ is the centroid) as β decreases. Children then tend to have larger Euclidean norm than their parents while being close w.r.t. the Lorentzian distance. We evaluate in Table 2 the percentage of nodes that have a Euclidean norm greater than their parent in the tree. More than 90% of pairs (parent,child) satisfy the desired order of Euclidean norms. The percentage increases with smaller values of β, this illustrates our point on the impact on the Euclidean norm of the center of mass.

On the other hand, our approach obtains worse performance for the SROC metric which evaluates how the order of the Euclidean norms is correlated with their normalized rank/depth in the hierarchy tree. This result is expected due to the formulation of the constraints of L neighborhood that considers only local similarity orders between pairs of examples. The loss L neighborhood does not take into account the global structure of the tree; it only considers whether pairs of concepts subsume each other or not.

As a consequence, although the root of a subtree may have a smaller Euclidean norm than all the other nodes of the subtree, this does not necessarily enforce its children to have comparable norms. They can have Euclidean norms smaller or greater than the norms of the descendants of their siblings.

In other words, although our representations do not preserve the global structure of the tree, most subtrees preserve produce a root with smaller Euclidean norm than their descendants.

-Case where λ > 0: As a consequence of the worse SROC performance, we evaluate the performance of our model when including normalized rank information during training. As can be seen in Table 1 , this greatly improves the SROC performance and outperforms the baselines (Nickel & Kiela, 2017; 2018) for all the evaluation metrics on some datasets. The Mean Rank and Mean Average Precision performances remain comparable with the case where λ = 0. Global rank information can then be used during training without having a significant impact on retrieval performance.

In conclusion, we have shown that the curvature of the hyperbolic space has an impact on the retrieval performance of the model. Moreover, the fact the Euclidean norms of parents tend to be smaller than those of children as β > 0 decreases experimentally demonstrates that the most similar points (i.e. high level nodes) tend to get closer to the origin as their set of similar points (i.e. number of descendant nodes) increases.

4.2. BINARY CLASSIFICATION:

Another task of interest for hyperbolic representations is to determine whether a given node belongs to a specific subtree of the hierarchy or not. We follow the same binary classification protocol as Ganea et al. (2018) on the same datasets. We describe their protocol below. 14) with λ = 0.01 distance (with β = 1). The test performance of our approach is reported in Table 3 . It outperforms the classification performance of the baselines, which shows that our embeddings can also be used to perform classification.

4.3. COMMUNITY DETECTION:

In our last experiment, our dataset does not correspond to a hierarchy tree. It is an undirected graph G = (V, D) where V is the set of vertices/nodes, and D the set of edges. We use the co-authorship information of the NIPS 1-17 dataset (Globerson et al., 2007) The main difference with the hierarchical case is that the transitivity relation (u, v) ∈ D, (v, w) ∈ D ⇒ (u, w) ∈ D is not necessarily true in the undirected graph case.

Figures 2 and 4 illustrate the 2-dimensional Poincaré representations learned with Eq. ( 14) for different values of λ ≥ 0. The number of co-authors is written in parenthesis, authors that have at least 20 co-authors are in red, those between 10 and 19 co-authors in blue. The MR and MAP are similar between both approaches (the MR is about 20 and the MAP about 55%) but the SROC with the number of co-authors is 93% for Fig. 2 . One can observe some communities such as the kernel method researchers (Shawe-Taylor, Vapnik, Smola etc...) are close to the same radius.

A PROOFS:

A.1 PROOF OF THEOREM 3.1:

• We first show (⇒): let us note α = a 2 , we have the following equality h(g β (a)) 2 = α ( √ α+1+1) 2 which is an increasing function in α when α is positive.

• We now show (⇐): We give the formulation of g -1 β • h -1 :

EQUATION

The vector g -1 β (h -1 (c)) is obtained by removing the first element of h -1 (c):

∀c ∈ P d , g -1 β (h -1 (c)) = 2c 1 -c 2 (17)

By using these definitions, we have the following implication: we recall that ∀c ∈ P d , c < 1 due to the definition of P d . Let us note γ = c 2 < 1, we have g -1 β (h -1 (c)) 2 = 4γ (1-γ) 2 which is an increasing function in γ on (0, 1). QED A.2 PROOF OF LEMMA 3.2 By using the linearity of the Lorentzian inner product, we have the following equality: Let f 1 , • • • , f n be a set of at least two different points in F d , and µ be the centroid of the set g β (f 1 ), • • • , g β (f n ) (with same weighting ∀i, ν i = 1). The squared Euclidean norm of g -1 β (µ) ∈ F d is: 

g -1 β (µ) 2 = β - n i=1 g β (f i ) 2 L n i=1 f i 2 (19)

:

The curvature of the considered hyperboloid models is negative and is -1 for the unit hyperboloid model.

A vector a that satisfies a, a L < 0 is called time-like and it is called positive iff a0 > 0.

We use the source code available at https://github.com/facebookresearch/ poincare-embeddings

CONCLUSIONIn this paper, we proposed a distance learning approach based on the Lorentzian distance to represent hierarchically-structured datasets. Unlike most of the literature that considers the unit hyperboloid model, we show that the performance of the learned model can be improved when the chosen hyperboloid model has low curvature. We give a formulation of the centroid w.r.t. the squared Lorentzian distance as a function of the curvature, and we show that the Euclidean norm of its projection in the Poincaré ball decreases as the curvature decreases. Hierarchy constraints are generally formulated such that high-level nodes are similar to all their descendants and thus their representation should be close to the centroid of the descendants. Using low curvature implicitly enforces high-level nodes to have smaller Euclidean norm than their descendants and is therefore is more appropriate for learning representations of hierachically-structured datasets.

Figures and Tables:

Theorem 3.4. The Euclidean norm in P d of the center of mass of a set of different examples decreases as β > 0 decreases. The proof is given in the appendix. Fig. 1 illustrates the 2-dimensional Poincaré ball representation of the centroid of a set of 10 different points w.r.t. to the Poincaré metric, the gyrodistance (Ungar, 2010), and the squared Lorentzian distance for different values of β > 0. The Euclidean norm in P d of the centroid does decrease as β decreases.

Figure 1: 10 examples are represented in green in a Poincaré ball. Their centroid w.r.t. the chosen distance function is in magenta and the level sets represent the sum of the distances between the current point and the training examples. The centroid w.r.t. the squared Lorentzian distance can be calculated in closed-form. Smaller values of β induce smaller Euclidean norms of the centroid.

) tries to get similar examples close to each other. The second term tries to satisfy the order of the embedding norms to match the normalized ranks. Using Theorem 3.1, we optimize Euclidean norms in F d . Datasets: We consider the following datasets: (1) 2012 ACM Computing Classification System: is classification system for the computing field used by ACM journal. (2) EuroVoc: is a thesaurus maintained by the European Union. (3) Medical Subject Headings (MeSH): (Rogers, 1963) is a medical thesaurus provided by the U.S. National Library of Medicine. (

Figure 2: 2-dimensional Poincaré representations learned when optimizing Eq. (14) with λ = 0.01

which contains information from papers published at NIPS from 1988 to 2003. The graph G is constructed by considering each author as a node, and an edge (u, v) ∈ D is created iff the authors u ∈ V and v ∈ D are co-authors. The number of authors is 2865 and the number of edges is |D| = 9466. Only |V| = 2715 authors have at least one co-author and the edges are neither weighted by the number of authors per paper nor by the number of times a pair of authors are co-authors.

i , µ L = max µ∈H d,β n i=1 ν i x i , µ L (18) Since µ ∈ H d,β and ∀a ∈ H d,β , b ∈ H d,β , a, b L is maximized if a = b, Eq. (18) is then maximized for the scaling factor γ > 0 that satisfies (γn i=1 ν i x i ) = µ ∈ H d,β. We explain in the next paragraph how to construct such a γ.For any positive time-like vector a, the vector b =1 | a L | a satisfies b, b L = a,a L | a,a L | = -1. Therefore, β b, b L = √ βb, √ βb L = -β (i.e. √ βb ∈ H d,β by definition since √ βb is positive) and we then have γ = √ β | n i=1 νixi L | . QED A.3 PROOF OF THEOREM 3.4

Since n i=1 f i 2 does not depend on β and the factorβ n i=1 g β (fi) 2L is positive for β > 0, we only need to show that it is a increasing function in β, or equivalently, that its reciprocal is decreasing in β.

Figure 4: 2-dimensional Poincaré representations learned when optimizing Eq. (14) with λ = 0

Figure 5: 2-dimensional Poincaré representations of researchers reported in the two kernel method clusters of Table 4, as in Fig 2, they are learned when optimizing Eq. (14) with λ = 0

Evaluation of Taxonomy embeddings. MR: Mean Rank (lower is better). MAP: Mean Average Precision (higher is better). ρ: Spearman's rank-order correlation (higher is better).

Table content: <table><tr><td>Method</td><td/><td colspan="2">dP in P d dP in H d</td><td>Ours</td><td>Ours</td><td>Ours</td><td>Ours</td></tr><tr><td/><td/><td/><td/><td colspan="4">β = 0.01 β = 0.1 β = 1 β = 0.01</td></tr><tr><td/><td/><td/><td/><td>λ = 0</td><td>λ = 0</td><td colspan="2">λ = 0 λ = 0.01</td></tr><tr><td/><td>MR</td><td>4.02</td><td>2.95</td><td>1.46</td><td>1.59</td><td>1.72</td><td>1.47</td></tr><tr><td colspan="2">WordNet Nouns MAP</td><td>86.5</td><td>92.8</td><td>94.0</td><td>93.5</td><td>91.5</td><td>94.7</td></tr><tr><td/><td>ρ</td><td>58.5</td><td>59.5</td><td>40.2</td><td>45.2</td><td>43.1</td><td>71.1</td></tr><tr><td/><td>MR</td><td>1.35</td><td>1.23</td><td>1.11</td><td>1.14</td><td>1.23</td><td>1.13</td></tr><tr><td>WordNet Verbs</td><td>MAP</td><td>91.2</td><td>93.5</td><td>94.6</td><td>93.7</td><td>91.9</td><td>94.0</td></tr><tr><td/><td>ρ</td><td>55.1</td><td>56.6</td><td>36.8</td><td>38.7</td><td>37.2</td><td>73.0</td></tr><tr><td/><td>MR</td><td>1.23</td><td>1.17</td><td>1.06</td><td>1.06</td><td>1.09</td><td>1.06</td></tr><tr><td>EuroVoc</td><td>MAP</td><td>94.4</td><td>96.5</td><td>96.5</td><td>96.0</td><td>95.0</td><td>96.1</td></tr><tr><td/><td>ρ</td><td>61.4</td><td>67.5</td><td>41.8</td><td>44.2</td><td>45.6</td><td>61.7</td></tr><tr><td/><td>MR</td><td>1.71</td><td>1.63</td><td>1.03</td><td>1.06</td><td>1.16</td><td>1.04</td></tr><tr><td>ACM</td><td>MAP</td><td>94.8</td><td>97.0</td><td>98.8</td><td>96.9</td><td>94.1</td><td>98.1</td></tr><tr><td/><td>ρ</td><td>62.9</td><td>65.9</td><td>53.9</td><td>55.9</td><td>46.7</td><td>66.4</td></tr><tr><td/><td>MR</td><td>12.8</td><td>12.4</td><td>1.31</td><td>1.30</td><td>1.40</td><td>1.33</td></tr><tr><td>MeSH</td><td>MAP</td><td>79.4</td><td>79.9</td><td>90.1</td><td>90.5</td><td>85.5</td><td>90.3</td></tr><tr><td/><td>ρ</td><td>74.9</td><td>76.3</td><td>46.1</td><td>47.2</td><td>41.5</td><td>78.7</td></tr></table>

Percentage of node representations that have smaller Euclidean norm than their children in the tree when λ = 0

Table content: <table><tr><td>Method</td><td colspan="3">Wordnet Nouns Wordnet Verbs EuroVoc</td><td>ACM</td><td>MeSH</td></tr><tr><td>Ours (β = 0.01)</td><td>97.2%</td><td>96.3%</td><td>98.6%</td><td colspan="2">98.3% 97.7%</td></tr><tr><td>Ours (β = 0.1)</td><td>97.9%</td><td>96.0%</td><td>98.4%</td><td colspan="2">98.0% 97.5%</td></tr><tr><td>Ours (β = 1)</td><td>94.3%</td><td>92.0%</td><td>98.3%</td><td colspan="2">94.3% 93.2%</td></tr></table>

Ganea et al. (2018) extract some pre-trained hyperbolic embeddings of the WordNet nouns hierarchy, those representations are learned with the Poincaré metric. They then consider four subtrees whose roots are the following synsets: animal.n.01, group.n.01, worker.n.01 and mammal.n.01. For each subtree, they consider that every node that belongs to it is positive and all the other nodes of Wordnet nouns are negative. They then select 80% of the positive nodes for training, the rest for test. They select the same percentage of negative nodes for training and test. At test time, they evaluate the F1 score of the binary classification performance. They do it for 3 different training/test splits. We refer toGanea et al. (2018) for details on the baselines.

Table content: <table/>

Test F1 classification scores for four different subtrees of WordNet noun tree. Ganea et al., 2018) 99.26 ± 0.59% 91.91 ± 3.07% 66.83 ± 11.83% 91.37 ± 6.09% Euclidean dist 99.36 ± 0.18% 91.38 ± 1.19% 47.29 ± 3.93% 77.76 ± 5.08% log 0 + Eucl 98.27 ± 0.70% 91.41 ± 0.18% 36.66 ± 2.74% 56.11 ± 2.21% Ours (β = λ = 0.01)99.57 ± 0.24% 99.75 ± 0.11% 94.50 ± 1.21% 96.65 ± 1.18% Ours (β = 0.01, λ = 0) 99.77 ± 0.17% 99.86 ± 0.03% 96.32 ± 1.05% 97.73 ± 0.86%

Table content: <table><tr><td>Dataset</td><td>animal.n.01</td><td>group.n.01</td><td>worker.n.01</td><td>mammal.n.01</td></tr><tr><td>(</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 Summary Learning embeddings of graphs in hyperbolic space have become popular and yielded promising results. A core reason for that is learning hierarchical representations of the graphs is easier in hyperbolic space due to the curvature and the geometrical properties of the hyperbolic space. Similar to [1, 2], this paper uses Lorentzian model of the hyperbolic space in order to learn embeddings of the graph. The main difference of the proposed approach in this paper is that they come up with a closed-form solution such that each node representation close to the centroid of their descendants. A curious property of the equation for the centroids proposed to learn the embeddings of each node also encodes information related to the specificity in the Euclidean norm of the centroid. Also this paper introduces two additional hyperparameters. Beta hyperparameter is selected to control the curvature of the space. Depending on the task the optimal curvature can be tuned to be a different value. This also ties closely with the de-Sitter spaces. Authors provide results on different graph embedding benchmark tasks. The paper claims that, an advantage of the proposed approach is that the embedding of the model can be tuned with regular SGD without needing to use Riemannian optimization techniques. Questions Have you tried learning beta instead of selecting as a hyperparameter? The paper claims that Riemannian optimization is not necessary for this model, but have you tried optimizing the model with the Riemannian optimization methods? Equation 11, bears lots of similarity to the Einstein gyro-midpoint method proposed by Abraham Ungar which is also used by [2]. Have you investigated the relationship between the two formulations? On Eurovoc dataset the results of the proposed method is worse than the d_P in H^d. Do you have a justification of why that happens? Pros The paper delivers some interesting theoretical findings about the embeddings learned in hyperbolic space, e.g. a closed for equation in the The paper is written well. The goal and motivations are clear. Cons Experiments are only limited to small scale-traditional graph datasets. It would be more interesting to see how those embeddings would perform on large-scale datasets such as to learn knowledge-base embeddings or for recommendation systems. Although the idea is interesting. Learning graph embeddings have already been explored in [1]. The main contribution of this paper is thus mainly focuses on the close-form equation for the centroid and the curvature hyperparameter. These changes provide significant improvements on the results but still the novelty of the approach is in that sense limited compared to [1]. Minor comment: It is really difficult to understand what is in Figure 2 and 3. Can you reduce the number of data points and just emphasize a few nodes in the graph that shows a clear hierarchy. [1] Nickel, Maximilian, and Douwe Kiela. "Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry." arXiv preprint arXiv:1806.03417 (2018). [2] Gulcehre, Caglar, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia et al. "Hyperbolic Attention Networks." arXiv preprint arXiv:1805.09786 (2018).