Year: 2018

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.

heading: 1 INTRODUCTION
text: 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 Sd = {x ∈ Rd : ‖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 Poincaré 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 Poincaré 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 Poincaré 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 Poincaré 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 Poincaré 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 Poincaré 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 Poincaré 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.

heading: 2 BACKGROUND
text: 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.

heading: 2.1 NOTATION AND DEFINITIONS
text: To simplify the notation, we consider that vectors are row vectors and ‖ · ‖ is the `2-norm. In the following, we consider three important spaces.
Poincaré ball: The Poincaré ball Pd is defined as the set of d-dimensional vectors with Euclidean norm smaller than 1 (i.e. Pd = {x ∈ Rd : ‖x‖ < 1}). Its associated distance is the Poincaré distance metric defined in Eq. (3).
Hyperboloid model: We consider some specific hyperboloid modelsHd,β defined as follows: Hd,β := {a = (a0, · · · , ad) ∈ Rd+1 : ‖a‖2L = −β, a0 > 0, β > 0} (1) where ‖a‖2L = 〈a,a〉L is the squared Lorentzian norm of a. The squared Lorentzian norm is derived from the Lorentzian inner product defined as:
∀a = (a0, · · · , ad) ∈ Hd,β ,b = (b0, · · · , bd) ∈ Hd,β , 〈a,b〉L := −a0b0 + d∑ i=1 aibi ≤ −β (2)
It is worth noting that 〈a,b〉L = −β iff a = b. Otherwise, 〈a,b〉L < −β for all pair (a,b) ∈ (Hd,β)2. Vectors inHd,β are a subset of positive time-like vectors2. Moreover, every vector a ∈ Hd,β satisfies a0 = √ β + ∑d i=1 a 2 i . We note Hd := Hd,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 noteFd ⊆ Rd the output space of our model (e.g. the output representation of some linear model or neural network). In the following, we consider that Fd = Rd.

heading: 2.2 OPTIMIZING THE POINCARÉ DISTANCE METRIC
text: Most methods that compare hyperbolic representations (Nickel & Kiela, 2017; 2018; Ganea et al., 2018; Gulcehre et al., 2018) consider the Poincaré distance metric defined as:
∀c ∈ Pd,d ∈ Pd, dP(c,d) = arcosh ( 1 + 2
‖c− d‖2
(1− ‖c‖2)(1− ‖d‖2)
) (3)
1The curvature of the considered hyperboloid models is negative and is -1 for the unit hyperboloid model. 2A vector a that satisfies 〈a,a〉L < 0 is called time-like and it is called positive iff a0 > 0.
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 Poincaré 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 dP in the unit hyperboloid model. They use the fact that there exists an invertible mapping h : Hd,β → Pd defined as:
∀a = (a0, · · · , ad) ∈ Hd,β , h(a) := 1 1 + √ 1 + ∑d i=1 a 2 i (a1, · · · , ad) ∈ Pd (4)
When β = 1, we have the following equivalence:
∀a ∈ Hd,b ∈ Hd, dH(a,b) = dP (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 dH(a,b) tends to 0. Interestingly, one can observe from Eq. (5) that preserving the order of Poincaré 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.

heading: 3 PROPOSED METHOD
text: We present in this section the (squared) Lorentzian distance function dL (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.

heading: 3.1 LORENTZIAN DISTANCE AND MAPPINGS
text: The squared Lorentzian distance (Ratcliffe, 2006) is defined as:
∀a ∈ Hd,β ,b ∈ Hd,β , d2L(a,b) = ‖a−b‖2L = ‖a‖2L+ ‖b‖2L− 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 d2L is linear in both a and b. Moreover, when β = 1, it defines the hyperbolic length of a curve inHd (Ratcliffe, 2006). Mapping: Current hyperbolic machine learning models re-project at each iteration their learned representations onto the Poincaré 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β : Fd → Hd,β defined as:
∀f = (f1, · · · , fd) ∈ Fd, gβ(f) := ( √ ‖f‖2 + β, f1, · · · , fd) ∈ Hd,β (7)
As mentioned in Section 2.1, Fd is the space of our model; it is Rd in practice. To be fair with baselines, the examples in Fd in our experiments are non-parametric embeddings. Fd may also be the output space of some parametric model such as a neural network.
We compare two examples f1 ∈ Fd and f2 ∈ Fd with d2L by calculating:
∀f1 ∈ Fd, f2 ∈ Fd, d2L(gβ(f1), gβ(f2)) = −2β − 2〈gβ(f1), gβ(f2)〉L (8) = −2 [ β + 〈f1, f2〉 − √ ‖f1‖2 + β √ ‖f2‖2 + β ] (9)
Preserved order of Euclidean norms: Although examples are compared with d2L in the hyperbolic space Hd,β 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 Fd,Hd,β and Pd with the mappings gβ and h. The preservation with gβ is straightforward: ∀f1, f2 ∈ Fd, ‖f1‖ < ‖f2‖ ⇐⇒√ 2‖f1‖2 + β = ‖gβ(f1)‖ < ‖gβ(f2)‖. 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:
∀a ∈ Fd,b ∈ Fd, ‖a‖ < ‖b‖ ⇐⇒ ‖h(gβ(a))‖ < ‖h(gβ(b))‖ (10)
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.

heading: 3.2 CENTROID PROPERTIES
text: 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 µ ∈ Hd,β that maximizes the following problem maxµ∈Hd,β ∑n i=1 νi〈xi,µ〉L where ∀i,xi ∈ Hd,β , ∀i, νi ≥ 0, ∑ i νi > 0 is:
µ = √ β ∑n i=1 νixi
|‖ ∑n i=1 νixi‖L|
= √ β ∑n i=1 νixi√
−‖ ∑n i=1 νixi‖2L
(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. Theorem 3.3 (Centroid of the squared Lorentzian distance). The point µ ∈ Hd,β that minimizes the problem minµ∈Hd,β ∑n i=1 νid 2 L(xi,µ) where ∀i,xi ∈ Hd,β , νi ≥ 0, ∑ i νi > 0 is given in Eq. (11)
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. Theorem 3.4. The Euclidean norm inPd 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 Poincaré ball representation of the centroid of a set of 10 different points w.r.t. to the Poincaré metric, the gyrodistance (Ungar, 2010), and the squared Lorentzian distance for different values of β > 0. The Euclidean norm in Pd of the centroid does decrease as β decreases.
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 aj ∈ A = {ak ∈ Hd,β}mk=1 that minimizes the problem minaj∈A ∑n i=1 d 2 L(xi,aj) where ∀i,xi ∈ Hd,β is the example in A that is the closest to the centroid of x1, · · · ,xn 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 f1 tends to 0 for any vector f2 that can be written f2 = τ f1 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 Poincaré metric formulation? As defined in Eq. (5), the curvature of the hyperboloid model cannot be decreased in the Poincaré 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 Poincaré metric.

heading: 3.3 OPTIMIZATION PROBLEM AND SOLVER
text: 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 Poincaré 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 {fi}ni=1 that minimize:
Lneighborhood = − ∑
(u,v)∈D
log e−d(fu,fv)∑
v′∈N (u)∪{v} e −d(fu,fv′ )
(12)
where d is the chosen distance function. The problem is optimized via projected gradient-based method. We replace d(fu, fv) by d2L(gβ(fu), gβ(fv)) 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 → Hd,β . 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.

heading: 4 RESULTS
text: 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.

heading: 4.1 REPRESENTATION OF HIERARCHIES
text: 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:
rank(u) = sp(u)
sp(u) + lp(u) ∈ [0, 1] (13)
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 {fi ∈ Fd}ni=1 that minimize the following problem: Lneighborhood + λ ∑
{(u,v):rank(u)<rank(v)}
max(‖fu‖2 − ‖fv‖2, 0) (14)
where λ ≥ 0 is a regularization parameter. The first term defined in Eq. (12) 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 Fd. 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. (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 Lneighborhood, we then select 5% of the possible
3We use the source code available at https://github.com/facebookresearch/ poincare-embeddings
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 Poincaré 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 Lneighborhood that considers only local similarity orders between pairs of examples. The loss Lneighborhood 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.

heading: 4.2 BINARY CLASSIFICATION
text: 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.
Ganea et al. (2018) extract some pre-trained hyperbolic embeddings of the WordNet nouns hierarchy, those representations are learned with the Poincaré 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 to Ganea et al. (2018) for details on the baselines.
Our goal is to evaluate the relevance of the Lorentzian distance to represent hierarchical datasets. We then use the embeddings trained with our approach (with β = 0.01 and different values of λ) and classify a test node by assigning it to the category of the nearest training example w.r.t. the Lorentzian
(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% log0 + 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%
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.

heading: 4.3 COMMUNITY DETECTION
text: 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) 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.
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 Poincaré 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.
When learning 10-dimensional representations, the MR is 1.0 and the MAP is 100%. When λ = 0, the embeddings with smallest Euclidean norm are in that order: Sejnowski T. (52), Jordan M. (45), Tishby N. (29), Dayan P. (25), Koch C. (46), Singh S. (27), Hinton G. (32), Scholkopf B. (36), Mozer M. (21), Bialek W. (27), Singer Y. (19), Vapnik V. (23), Bengio Y. (33), Shawe-Taylor J. (22), Zemel R. (13). The authors with a large number of co-authors then tend to have smallest Euclidean norms.
Since hyperbolic distances are appropriate to represent hierarchies, we perform a hierarchical agglomerative clustering with the learned squared Lorentzian distance (with dimensionality d = 10) based on complete-linkage clustering (Defays, 1977) (i.e. linkage uses the maximum distances between all observations of two sets to merge them into a same cluster). Some examples of extracted clusters are given in Table 4. Fig 5 illustrates how the researchers from the kernel method clusters of Table 4 are represented in Fig 2.
Most of them are close to the same radius of the Poincaré ball. This simple example shows that the Lorentzian distance can be applied to datasets that are not only hierarchical.

heading: 5 CONCLUSION
text: In 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 Poincaré 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.

heading: A PROOFS
text: 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:
∀c = (c1, · · · , cd) ∈ Pd, h−1(c) = √∥∥∥∥ 2c1− ‖c‖2 ∥∥∥∥2 + β, 2c11− ‖c‖2 , · · · , 2cd1− ‖c‖2  ∈ Hd,β (15)
= √∥∥∥∥ 2c1− ‖c‖2 ∥∥∥∥2 + β, 2c1− ‖c‖2  ∈ Hd,β (16) The vector g−1β (h −1(c)) is obtained by removing the first element of h−1(c):
∀c ∈ Pd, g−1β (h −1(c)) =
2c
1− ‖c‖2 (17)
By using these definitions, we have the following implication: we recall that ∀c ∈ Pd, ‖c‖ < 1 due to the definition of Pd. 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:
max µ∈Hd,β n∑ i=1 νi〈xi,µ〉L = max µ∈Hd,β 〈 n∑ i=1 νixi,µ〉L (18)
Since µ ∈ Hd,β and ∀a ∈ Hd,β ,b ∈ Hd,β , 〈a,b〉L is maximized if a = b, Eq. (18) is then maximized for the scaling factor γ > 0 that satisfies (γ ∑n i=1 νixi) = µ ∈ Hd,β . 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 ∈ Hd,β by definition since √ βb is positive) and we then have γ = √ β
|‖ ∑n i=1 νixi‖L| . QED
A.3 PROOF OF THEOREM 3.4
Let f1, · · · , fn be a set of at least two different points in Fd, and µ be the centroid of the set gβ(f1), · · · , gβ(fn) (with same weighting ∀i, νi = 1). The squared Euclidean norm of g−1β (µ) ∈ Fd is:
‖g−1β (µ)‖ 2 =
β −‖ ∑n i=1 gβ(fi)‖2L ‖ n∑ i=1 fi‖2 (19)
Since ‖ ∑n i=1 fi‖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 β.
The reciprocal of β−‖∑ni=1 gβ(fi)‖2L is: −‖ ∑n i=1 gβ(fi)‖2L β = −[ ∑n i=1 ‖gβ(fi)‖2L + 2 ∑n i=1 ∑n j>i〈gβ(fi), gβ(fj)〉L] β (20)
= n− 2 β n∑ i=1 n∑ j>i 〈gβ(fi), gβ(fj)〉L (21)
= n+ 2
β n∑ i=1 n∑ j>i 〈 √ ‖fi‖2 + β, √ ‖fj‖2 + β〉 − 〈fi, fj〉 (22)
We then need to show that the function
1
β
[ 〈 √ ‖fi‖2 + β, √ ‖fj‖2 + β〉 − 〈fi, fj〉 ] (23)
is decreasing in β if fi 6= fj . For this purpose, We study the sign of its gradient. The gradient of Eq. (23) w.r.t. β is written:
2〈fi, fj〉 √ ‖fi‖2 + β √ ‖fj‖2 + β − β(‖fi‖2 + ‖fj‖2)− 2‖fi‖2‖fj‖2
2β2 √ ‖fi‖2 + β √ ‖fj‖2 + β
(24)
The denominator is positive. If 〈fi, fj〉 is negative, then Eq. (24) is negative. If 〈fi, fj〉 = 0, then Eq. (24) is 0 if fi = fj = 0, and negative otherwise. Otherwise, the Cauchy-Schwarz inequality is used to prove that Eq. (24) is negative. In other words, we need to prove that (assuming that 〈fi, fj〉 is positive):
2〈fi, fj〉 √ ‖fi‖2 + β √ ‖fj‖2 + β − β(‖fi‖2 + ‖fj‖2)− 2‖fi‖2‖fj‖2 < 0 (25)
⇐⇒2〈fi, fj〉 √ ‖fi‖2 + β √ ‖fj‖2 + β < β(‖fi‖2 + ‖fj‖2) + 2‖fi‖2‖fj‖2 (26)
⇐⇒(2〈fi, fj〉 √ ‖fi‖2 + β √ ‖fj‖2 + β)2 < [β(‖fi‖2 + ‖fj‖2) + 2‖fi‖2‖fj‖2]2 (27)
⇐⇒4〈fi, fj〉2(‖fi‖2 + β)(‖fj‖2 + β) = 4〈fi, fj〉2(‖fi‖2‖fj‖2 + β‖fi‖2 + β‖fj‖2 + β2) (28) < 4‖fi‖4‖fj‖4 + 4β‖fi‖2‖fj‖2(‖fi‖2 + ‖fj‖2) + β2‖fi‖4 + β2‖fj‖4 + 2β2‖fi‖2‖fj‖2
(29)
Since, by the Cauchy-Schwarz inequality, we have:
〈fi, fj〉2 ≤ ‖fi‖2‖fj‖2 (30)
we then have (term by term):
4〈fi, fj〉2‖fi‖2‖fj‖2 ≤ 4‖fi‖4‖fj‖4 (31) 4β〈fi, fj〉2‖fi‖2 ≤ 4β‖fi‖2‖fj‖2‖fi‖2 (32) 4β〈fi, fj〉2‖fj‖2 ≤ 4β‖fi‖2‖fj‖2‖fj‖2 (33)
2β2〈fi, fj〉2 ≤ 2β2‖fi‖2‖fj‖2 (34) 2β2〈fi, fj〉2 ≤ 2β2‖fi‖2‖fj‖2 ≤ β2‖fi‖4 + β2‖fj‖4 (35)
Eq. (35) is explained by β2‖fi‖4 + β2‖fj‖4 − 2β2‖fi‖2‖fj‖2 = β2(‖fi‖2 − ‖fj‖2)2 ≥ 0.
Eq. (35) is then an equality iff ‖fi‖2 = ‖fj‖2, and the Cauchy-Schwarz relation is an equality iff fi are linearly fj dependent. Both of these conditions are satisfied iff fi = fj (assuming that 〈fi, fj〉 is positive). However, we assume that there are at least two different points fi and fj such that fi 6= fj , which then implies that Eq. (24) is negative for this choice of fi and fj .
This proves that the Euclidean norm in Fd of the centroid of different points decreases as β > 0 decreases. From Section A.1, the Euclidean norm of a point in Pd increases as the Euclidean norm of its projection in Fd increases, which completes the proof.

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

The paper proposes a new approach to compute hyperbolic embeddings based on the squared Lorentzian distance. This choice of distance function is motivated by the observation that the ranking of these distances is equivalent to the ranking of the true hyperbolic distance (e.g., on the hyperboloid). For this reason, the paper proposes to use this distance function in combination with ranking losses as proposed by Nickel & Kiela (2017), as it might be easier to optimize. Moreover, the paper proposes to use Weierstrass coordinates as a representation for points on the hyperboloid.