Year: 2019

Abstract:
The quality of the representations achieved by embeddings is determined by how well the geometry of the embedding space matches the structure of the data. Euclidean space has been the workhorse for embeddings; recently hyperbolic and spherical spaces have gained popularity due to their ability to better embed new types of structured data—such as hierarchical data—but most data is not structured so uniformly. We address this problem by proposing learning embeddings in a product manifold combining multiple copies of these model spaces (spherical, hyperbolic, Euclidean), providing a space of heterogeneous curvature suitable for a wide variety of structures. We introduce a heuristic to estimate the sectional curvature of graph data and directly determine an appropriate signature—the number of component spaces and their dimensions—of the product manifold. Empirically, we jointly learn the curvature and the embedding in the product space via Riemannian optimization. We discuss how to define and compute intrinsic quantities such as means—a challenging notion for product manifolds—and provably learnable optimization functions. On a range of datasets and reconstruction tasks, our product space embeddings outperform single Euclidean or hyperbolic spaces used in previous works, reducing distortion by 32.55% on a Facebook social network dataset. We learn word embeddings and find that a product of hyperbolic spaces in 50 dimensions consistently improves on baseline Euclidean and hyperbolic embeddings, by 2.6 points in Spearman rank correlation on similarity tasks and 3.4 points on analogy accuracy.

text: The quality of the representations achieved by embeddings is determined by how well the geometry of the embedding space matches the structure of the data. Euclidean space has been the workhorse for embeddings; recently hyperbolic and spherical spaces have gained popularity due to their ability to better embed new types of structured data—such as hierarchical data—but most data is not structured so uniformly. We address this problem by proposing learning embeddings in a product manifold combining multiple copies of these model spaces (spherical, hyperbolic, Euclidean), providing a space of heterogeneous curvature suitable for a wide variety of structures. We introduce a heuristic to estimate the sectional curvature of graph data and directly determine an appropriate signature—the number of component spaces and their dimensions—of the product manifold. Empirically, we jointly learn the curvature and the embedding in the product space via Riemannian optimization. We discuss how to define and compute intrinsic quantities such as means—a challenging notion for product manifolds—and provably learnable optimization functions. On a range of datasets and reconstruction tasks, our product space embeddings outperform single Euclidean or hyperbolic spaces used in previous works, reducing distortion by 32.55% on a Facebook social network dataset. We learn word embeddings and find that a product of hyperbolic spaces in 50 dimensions consistently improves on baseline Euclidean and hyperbolic embeddings, by 2.6 points in Spearman rank correlation on similarity tasks and 3.4 points on analogy accuracy.

heading: 1 INTRODUCTION
text: With four decades of use, Euclidean space is the venerable elder of embedding spaces. Recently, non-Euclidean spaces—hyperbolic (Nickel & Kiela, 2017; Sala et al., 2018) and spherical (Wilson et al., 2014; Liu et al., 2017)—have gained attention by providing better representations for certain types of structured data. The resulting embeddings offer better reconstruction metrics: higher mean average precision (mAP) and lower distortion compared to their Euclidean counterparts. These three spaces are the model spaces of constant curvature (Lee, 1997), and this improvement in representation fidelity arises from the correspondence between the structure of the data (hierarchical, cyclical) and the geometry of non-Euclidean space (hyperbolic: negatively curved, spherical: positively curved). The notion of curvature plays the key role.
To improve representations for a variety of types of data—beyond hierarchical or cyclical—we seek spaces with heterogeneous curvature. The motivation for such mixed spaces is intuitive: our data may have complicated, varying structure, in some regions tree-like, in others cyclical, and we seek the best of all worlds. We expect mixed spaces to match the geometry of the data and thus provide higher quality representations. However, to employ these spaces, we face several key obstacles. We must perform a challenging manifold optimization to learn both the curvature and the embedding. Afterwards, we also wish to operate on the embedded points. For example, analogy operations for word embeddings in Euclidean vector space (e.g., a− b+ c) must be lifted to manifolds.
We propose embedding into product spaces in which each component has constant curvature. As we show, this allows us to capture a wider range of curvatures than traditional embeddings, while retaining the ability to globally optimize and operate on the resulting embeddings. Specifically, we form a Riemannian product manifold combining hyperbolic, spherical, and Euclidean components and equip it with a decomposable Riemannian metric. While each component space in the product has constant curvature (positive for spherical, negative for hyperbolic, and zero for Euclidean), the resulting mixed space has non-constant curvature. However, selecting appropriate curvatures for the embedding space is a potential challenge. We directly learn the curvature for each component space along with the embedding (via Riemannian optimization), recovering the correct curvature, and thus the matching geometry, directly from data. We show empirically that we can indeed recover non-uniform curvatures and improve performance on reconstruction metrics.
Another technical challenge is to select the underlying number of components and dimensions of the product space; we call this the signature. This concept is vacuous in Euclidean space: the product of Er1 , . . . ,Ern is identical to the single space Er1+...+rn . However, this is not the case with spherical and hyperbolic spaces. For example, the product of the spherical space S1 (the circle) with itself is the torus S1 × S1, which is topologically distinct from the sphere S2. We address this challenge by introducing a theory-guided heuristic estimator for the signature. We do so by matching an empirical notion of discrete curvature in our data with the theoretical distribution of the sectional curvature, a fine-grained measure of curvature on Riemannian manifolds that is amenable to analysis in products. We verify that this approach recovers the correct signature on reconstruction tasks.
Standard techniques such as PCA require centering so that the embedded directions capture components of variation. Centering in turn needs an appropriate generalization of the mean. We develop a formulation of mean for embedded points that exploits the decomposability of the distance and has theoretical guarantees. For T = {p1, . . . , pn} in a manifoldM with dimension r, the mean is µ(T ) := argminp ∑ i d 2 M(p, pi). We give a global existence result: under symmetry conditions on the distribution of the points in T on the spherical components, gradient descent recovers µ(T ) with error ε in time O(nr log ε−1).
We demonstrate the advantages of product space embeddings through a variety of experiments; products are at least as good as single spaces, but can offer significant improvements when applied to structures not suitable for single spaces. We measure reconstruction quality (via mAP and distortion) for synthetic and real datasets over various allocations of embedding spaces. We observe a 32.55% improvement in distortion versus any single space on a Facebook social network graph. Beyond reconstruction, we apply product spaces to skip-gram word embeddings, a popular technique with numerous downstream applications, which crucially require the use of the manifold structure. We find that products of hyperbolic spaces improve performance on benchmark evaluations—suggesting that words form multiple smaller hierarchies rather than one larger one. We see an improvement of 3.4 points over baseline single spaces on the Google word analogy benchmark and of 2.6 points
in Spearman rank correlation on a word similarity task using the WS-353 corpus. Our results and initial exploration suggest that mixed product spaces are a promising area for future study.

heading: 2 PRELIMINARIES & BACKGROUND
text: Embeddings For metric spaces1 U, V equipped with distances dU , dV , an embedding is a mapping f : U → V . The quality of an embedding is measured by various fidelity measures. A standard measure is average distortion Davg. The distortion of a pair of points a, b is (|dV (f(a), f(b)) − dU (a, b)|)/dU (a, b), and Davg is the average over all pairs of points. Distortion is a global metric; it considers the explicit value of all distances. At the other end of the global-local spectrum of fidelity measures is mean average precision (mAP), which applies to unweighted graphs. Let G = (V,E) be a graph and node a ∈ V have neighborhood Na = {b1, . . . , bdeg(a)}, where deg(a) is the degree of a. In the embedding f , defineRa,bi to be the smallest ball around f(a) that contains bi (that is, Ra,bi is the smallest set of nearest points required to retrieve the ith neighbor of a in f ). Then, mAP(f) = 1|V | ∑ a∈V 1 deg(a) ∑|Na| i=1 |Na∩Ra,bi |/|Ra,bi |.
Note that mAP does not track explicit distances; it is a ranking-based measure for local neighborhoods. Observe that mAP(f) ≤ 1 (higher is better) while davg ≥ 0 (lower is better).
Riemannian Manifolds We briefly review some notions from manifolds and Riemannian geometry. A more in-depth treatment can be found in standard texts (Lee, 2012; do Carmo, 1992). Let M be a smooth manifold, p ∈ M be a point, and TpM be the tangent space to the point p. If M is equipped with a Riemannian metric g, then the pair (M, g) is called a Riemannian manifold. The shortest-distance paths on manifolds are called geodesics. To compute distance functions on a Riemannian manifold, the metric tensor g is integrated along the geodesic. This is a smoothly varying function (in p) g : TpM × TpM → R that induces geometric notions such as length and angle by defining an inner product on the tangent space. For example, the norm of v ∈ TpM is defined as ‖v‖g := gp(v, v) 1 2 . In Euclidean space Rd, each tangent space TpRd is canonically identified with Rd, and the metric tensor gE is simply the normal inner product.
Product Manifolds Consider a sequence of smooth manifolds M1, M2, . . . ,Mk. The product manifold is defined as the Cartesian product M = M1 ×M2 × . . . ×Mk. Notationally, we write points p ∈ M through their coordinates p = (p1, . . . , pk) : pi ∈ Mi, and similarly a tangent vector v ∈ TpM can be written (v1, . . . , vk) : vi ∈ TpiMi. If the Mi are equipped with metric tensor gi, then the product M is also Riemannian with metric tensor g(u, v) = ∑k i=1 gi(ui, vi). That is, the product metric decomposes into the sum of the constituent metrics.
Geodesics and Distances Optimization on manifolds requires a notion of taking a step. This step can be performed in the tangent space and transferred to the manifold via the exponential map Expp : TpM → M . In a product manifold P , for tangent vectors v = (v1, . . . , vk) at p = (p1, . . . , pk) ∈M , the exponential map simply decomposes, as do squared distances (Ficken, 1939; Turaga & Srivastava, 2016):
Expp(v) = (Expp1(v1), . . . ,Exppk(vk)), d 2 P(x, y) = k∑ i=1 d2i (xi, yi). (1)
In other words, the shortest path between points in the product travels along the shortest paths in each component simultaneously. Note the analogy to Euclidean products Rd ≡ (R1)d.
Hyperbolic and Spherical Model We use the hyperboloid model of hyperbolic space, with points in Rd+1. Let J ∈ R(d+1)×(d+1) be the diagonal matrix with J00 = −1 and Jii = 1 : i > 0. For p, q ∈ Rd+1, the Minkowski inner product is 〈p, q〉∗ := pTJq = −p0q0 + p1q1 + . . . + pdqd, and the corresponding norm is ‖p‖∗ = 〈p, p〉 1 2 ∗ . For any K > 0, the hyperboloid HdK is defined on the
1In this paper, we use the language of graphs; note that any discrete metric space can be identified with a weighted graph, and all of our algorithms operate on weighted graphs.
subset {p ∈ Rd+1 : ‖p‖∗ = −K1/2, p0 > 0}. When the subscript K is omitted, it is taken to be 1. The hyperbolic distance on Hd is dH(p, q) = acosh(−〈p, q〉∗). Similarly, spherical space SdK is most easily defined when embedded in Rd+1. The manifold is defined on the subset {p ∈ Rd+1 : ‖p‖2 = K1/2}, with metric gS induced by the Euclidean metric on Rd+1. The spherical distance on Sd is dS(p, q) = arccos(〈p, q〉) .

heading: 3 PRODUCT SPACES AND CONSTRUCTIONS
text: We now tackle the challenges of mixed spaces. First, we introduce a product manifold embedding space P composed of multiple copies of simple model spaces, providing heterogeneous curvature. Next, in Section 3.1, given the signature of P (the number of components of each type and their dimensions), we describe how to simultaneously learn an embedding and the curvature for each component through optimization. In Section 3.2, we provide a heuristic to choose the signature by estimating a discrete notion of curvature for given data. Finally, in Section 3.3, given an embedding in P , we introduce a Karcher-style mean which can be recovered efficiently. Let SdK and HdK be the spherical and hyperbolic spaces of dimension d and curvature K,−K, respectively, and Ed the Euclidean space of dimension d.2 We describe our main embedding space: for sequences of dimensions s1, s2, . . . , sm, h1, . . . , hn, and e, we write P = Ss1 × Ss2 × · · · × Ssm ×Hh1 ×Hh2 × · · · ×Hhn × Ee, a product manifold with m+ n+ 1 component spaces and total dimension ∑ i si + ∑ j hj + e. We refer to each Ssi ,Hhi ,Ee as components or factors. We refer to the decomposition, e.g., (H2)2 = H2×H2, as the signature. For convenience, letM1, . . . ,Mm+n+1 refer to the factors in the product.
Distances on P As discussed in Section 2, the product P is a Riemannian manifold defined by the structure of its components. For p, q ∈ P , we write dMi(p, q) for the distance dMi restricted to the appropriate components of p and q in the product. In particular, the squared distance in the product decomposes via (1). In other words, dP is simply the `2 norm of the component distances dMi .
We note that P can also be equipped with different distances (ignoring the Riemannian structure), leading to a different embedding space. Without the underlying manifold structure, we cannot freely operate on the embedded points such as taking geodesics and means, but some simple applications only interact through distances. For such settings, we consider the `1 distance dP,`1(p, q) = ∑sm i=1 dSi(p, q) + ∑hn i=1 dHi(p, q) + dE(p, q) and the min distance dP,min(p, q) = min {dS1(p, q), . . . , dH1(p, q), . . . , dE(p, q)}. These distances provide simple and interpretable embedding spaces using P , enabling us to introduce combinatorial constructions that allow for embeddings without the need for optimization. We give an example below and discuss further in the Appendix. We then focus on the Riemannian distance, which allows Riemannian optimization directly on the manifold, and enables full use of the manifold structure in generic downstream applications.
Example Consider the graph G shown on the right of Figure 2. This graph has a backbone cycle with 9 nodes, each attached to a tree; such topologies are common in networking. If a single edge (a, b) is removed from the cycle, the result is a tree embeddable arbitrarily well into hyperbolic space (Sala et al., 2018). However, a, b (and their subtrees) would then incur an additional distance of 8 − 1 = 7, being forced to go the other way around the cycle. But using the `1 distance, we can embed Gtree into H2 and Gcycle into S1, yielding arbitrarily low distortion for G. We give the full details and another combinatorial construction for the min-distance in the Appendix.

heading: 3.1 OPTIMIZATION & COMPONENT CURVATURES
text: To compute embeddings, we optimize the placement of points through an auxiliary loss function. Given graph distances {dG(Xi, Xj)}ij , our loss function of choice is
L(x) = ∑
1≤i≤j≤n
∣∣∣∣∣ ( dP(xi, xj)
dG(Xi, Xj)
)2 − 1 ∣∣∣∣∣ , (2) 2We write E for our Euclidean embedding space component to distinguish it from R, since our models of
hyperbolic and spherical geometry also use R as an ambient space.
Algorithm 1 R-SGD in products 1: Input: Loss function L : P → R 2: Initialize x(0) ∈ P randomly 3: for t = 0, . . . , T − 1 do 4: h← ∇L(x(t)) 5: for i = 1, . . . ,m do 6: vi ← projSx(t)i (hi)
7: for i = m+ 1, . . . ,m+ n do 8: vi ← projHx(t)i (hi)
9: vi ← Jvi 10: vm+n+1 ← hm+n+1 11: for i = 1, . . . ,m+ n+ 1 do 12: x(t+1)i ← Expx(t)i (vi) 13: return x(T )
G
Gtree Gcycle
Figure 2: Left: Riemannian SGD decomposes per component. Subscripts i index components in the product. Right: Ring of trees graph G. Neither hyperbolic nor spherical space is suitable for G, but the product H× S captures it with low distortion. Note the decomposition into tree and cycle.
which captures the average distortion. (2) depends on hyperbolic distance dH (for which the gradient is unstable) only through the square d2H , which is continuously differentiable (Sala et al., 2018).
In any Riemannian manifold, a loss function can be optimized through standard Riemannian optimization methods such as RSGD (Bonnabel, 2013) and RSVRG (Zhang et al., 2016). We write down the full RSGD specialized to our product spaces in Algorithm 1. This proceeds by first computing the Euclidean gradient ∇L(x) with respect to the ambient space of the embedding (Step 4), and then converting it to the Riemannian gradient by applying the Riemannian correction (multiply by the inverse of the metric tensor g−1P ). This overall strategy has been detailed in previous work in the hyperboloid model (Nickel & Kiela, 2018; Wilson & Leimeister, 2018), and the same calculations apply to our hyperbolic components.
Since gP is block diagonal on a product manifold, it suffices to apply the correction and perform the gradient step in each component Mi independently. In the spherical and hyperboloid models, which have smaller dimension than the ambient space, this is performed by first projecting the gradient vector h onto the tangent space TxM via projSx (h) = h− 〈h, x〉x (Step 6) and proj H x (h) = h+ 〈h, x〉∗x (Step 8). In the hyperboloid model, a final rescaling by the inverse of the metric J is needed (Step 9). This is not required in the spherical model since it inherits the same metric from the ambient Euclidean space.
Learning the Curvature There exists a spherical model for every curvature K > 0 (for example, the sphere SdK of radius K−1/2) and a hyperbolic model for every K < 0 (the hyperboloid Hd−K). We jointly optimize the curvature Ki of every non-Euclidean factor Mi along with the embeddings.
The idea is that distances on the spherical and hyperboloid models of arbitrary curvature can be emulated through distances on the standard models S,H of curvature 1. For example, given p, q on the sphere S1/R2 of radius R, then d(p, q) = R · dS1(p/R, q/R) where p/R, q/R lie on the unit sphere. Therefore the radius R, which is monotone in the curvature K, can be treated as a parameter as well, so that we can optimize K and implicitly represent points lying on the manifold of curvature K, while explicitly only needing to store and optimize points in the standard model of curvature 1 via Algorithm 1. The hyperboloid model is analogous. Moreover, the loss (2) depends only on squared distances on the product manifold, which are simple functions of distances in the components through (1), so we can optimize the curvature of each factor in P .

heading: 3.2 ESTIMATING THE SIGNATURE
text: To choose the signature of an appropriate space P corresponding to given data, we again turn to curvature. We use the sectional curvature, a finer-grained notion defined over all two-dimensional subspaces passing through a point. Unlike coarser notions like scalar curvature, this is not constant in a product of basic spaces. Given linearly independent u, v ∈ TpM spanning a two-dimensional subspace U , the sectional curvature Kp(u, v) or Kp(U) is defined as the Gaussian curvature of the surface Exp(U) ⊆ M . Intuitively, this captures the rate that geodesics on the surface emanating from p spread apart, which relates to volume growth. In Appendix C.2, we show that the sectional curvature of P interpolates between the sectional curvatures of the factors, enabling us to better capture a wider range of structures in our embeddings:
Lemma 1. Let M = M1 ×M2 where Mi has constant curvature Ki. For any u, v ∈ TpM , if K1,K2 are both non-negative, the sectional curvature satisfies K(u, v) ∈ [0,max{K1,K2}]. If K1,K2 are both non-positive, the sectional curvature satisfies K(u, v) ∈ [min{K1,K2}, 0]. If Ki < 0 and Kj > 0 for i 6= j, then K(u, v) ∈ [Ki,Kj ].
Our estimation technique employs a triangle comparison theorem following from Toponogov’s theorem and the law of cosines, which characterizes sectional curvature through the behavior of small triangles (note that a triangle determines a 2-dimensional submanifold). Let abc be a geodesic triangle in manifold (or metric space) M and m be the (geodesic) midpoint of bc, and consider the quantity
ξM (a, b, c) := dM (a,m) 2 + dM (b, c) 2/4− ( dM (a, b) 2 + dM (a, c) 2 ) /2. (3)
This is non-negative (resp. non-positive) when the curvature is non-negative (resp. non-positive). Note that consequently the equality case occurs exactly when the curvature is 0, and equation 3 becomes the parallelogram law of Euclidean geometry (Figure 3).
Analogous to sectional curvature, which is a function of a point p and two directions x, y from p, in an undirected graph G we define an analog for every node m and two neighbors b, c. Given a reference node a we set: ξG(m; b, c; a) = 12dG(a,m)ξG(a, b, c). This is exactly the expression from equation 3, normalized suitably so as to yield the correct scaling for trees and cycles. Our curvature estimation is then a simple average ξG(m; b, c) = 1|V |−1 ∑ a 6=m ξG(m; b, c; a).
Importantly, ξG recovers the right curvature for graph atoms such as lines, cycles, and trees (Appendix C.2, Lemma 4,5), and the correct sign for other special discrete objects like polyhedra (Thurston, 1998). The curvature is zero for lines, positive for cycles, and negative for trees.
For a generic graph G, we use this to generate a potential product manifold to embed in. An empirical sectional curvature of G is estimated via Algorithm 3, which is based off the homogeneity of product manifolds (i.e. isometries act transitively), implying that it suffices to analyze the curvature at a random point. In particular, we moment-match the distributions of sectional curvature through uniformly random 2-planes in the graph and in the manifold through Algorithms 3,2 (Appendix C.2).

heading: 3.3 MEANS IN THE PRODUCT MANIFOLD
text: A critical operation on manifolds is that of taking the mean; it is necessary for many downstream applications, including, for example, analogy tasks with word embeddings, for clustering, and for
centering before applying PCA. Even in simple settings like the circle S1, defining a mean is nontrivial. A classic approach is to take the Euclidean mean (in E2) of the points and to project back onto S1—but this operation fails in the case where the points are uniformly spaced on S1. A further roadblock is the varying curvature of P . Fortunately, we can exploit the decomposability of the distance on P , reducing the challenge to breaking symmetries in the component spaces. To do so, we introduce the following Karcher-style weighted mean. Let T = {p1, p2, . . . , pn} be a set of points in P and w1, . . . , wn be positive weights satisfying ∑n i=1 wi = 1. Then the mean µ(T ) is
argminp∈P ∑n i=1 wid 2 P(p, pi). In special cases, this matches commonly used means (the centroid in the Euclidean case Ed, the spherical average for S2 in Buss & Fillmore (2001)). We further note that when wi ≥ 0, the squared-distance components above are individually convex: this is trivial in the Euclidean term, holds in the hyperbolic case (cf. Theorem 4.1 (Bishop & O’Neill, 1969)), and holds in the spherical case under certain restrictions, e.g., when the points in T lie entirely in one hemisphere of Sr (Buss & Fillmore, 2001). Moreover, in this case, peforming the optimization on the mean with gradient descent via the exponential map offers linear rate convergence:
Lemma 2. Let P be a product of model spaces of total dimension r, T = {p1, . . . , pn} points in P and w1, . . . , wn weights satisfying wi ≥ 0 and ∑n i=1 wi = 1. Moreover, let the components of the points in P , pi|Sj restricted to each spherical component space Sj fall in one hemisphere of Sj . Then, Riemannian gradient descent recovers the mean µ(T ) within distance in timeO(nr log −1).
This is a global result; with weaker assumptions, we can derive local results; for example, in the case where some of the wi are negative, which is useful for analogy operations.
In summary, we offer the following key takeaways of our development:
• Product manifolds of model spaces capture heterogeneous curvature while providing tractable optimization,
• Each component’s curvature can be learned empirically through a reparametrization, • A signature for the product can be found by matching discrete notions of curvature on
graphs with sectional curvature on manifolds,
• There exists an easily-computed formulation of mean with theoretical guarantees.

heading: 4 EXPERIMENTS
text: We evaluate the proposed approach, comparing the representation quality of synthetic graphs and real datasets among different embedding spaces by measuring the reconstruction fidelity (through average distortion and mAP). We expect that mixed product spaces perform better for nonhomogeneous data. We consider the curvature of graphs, reporting the curvatures learned through optimization as well as the theoretical allocation from Section 3.2. Beyond reconstruction, we evaluate the intrinsic performance of product space embeddings in a skip-gram word embedding model, by defining tasks with generic manifold operations such as means.

heading: 4.1 GRAPH RECONSTRUCTION
text: Datasets We examine synthetic datasets—trees, cycles, the ring of trees shown in Figure 1, confirming that each matches its theoretically optimal embedding space. We then compare on several real-world datasets with describable structure, including the USCA312 dataset of distances between North American cities (Burkardt); a tree-like graph of computer science Ph.D. advisor-advisee relationships (De Nooy et al., 2011) reported in previous hyperbolics work (Sala et al., 2018); a powergrid distribution network with backbone structure (Watts & Strogatz, 1998); and a dense social network from Facebook (McAuley & Leskovec, 2012). For the former two graphs with well-defined structure, we expect optimal embeddings in spaces of positive and negative curvature, respectively. We hypothesize that the backbone network embeds well into simple products of hyperbolic and spherical spaces as in Figure 2, and the dense graph also benefits from a mixture of spaces.
Approaches We minimize the loss (2) using Algorithm 1. We fix a total dimension d and consider the most natural ways to construct product manifolds of the given dimension, through iteratively
doubling the number of factors. These models include the products consisting of only a constantcurvature base space, ranging to various combinations of Sd/22 ,H d/2 2 comprising factors of dimension 2.3 For a given signature, the curvatures are initialized to the appropriate value in {−1, 0, 1} and then learned using the technique in Section 3.1. We additionally compare to the outputs of Algorithms 2,3 for heuristically selecting a combination of spaces in which to embed these datasets.
Quality We focus on the average distortion—which our loss function (2) optimizes—as our main metric for reconstruction, and additionally report the mAP metric for the unweighted graphs. As expected, for the synthetic graphs (tree, cycle, ring of trees), the matching geometries (hyperbolic, spherical, product of hyperbolic and spherical) yield the best distortion (Table 1). Next, we report in Table 2 the quality of embedding different graphs across a variety of allocations of spaces, fixing total dimension d = 10 following previous work (Nickel & Kiela, 2018). We confirm that the structure of each graph informs the best allocation of spaces. In particular, the cities graph—which has intrinsic structure close to S2—embeds well into any space with a spherical component, and the treelike Ph.D.s graph embeds well into hyperbolic products. We emphasize that even for such datasets that theoretically match a single constant-curvature space, the products thereof perform no worse. In general, the product construction achieves high quality reconstruction: the traditional Euclidean approach is often well below several other signatures. We additionally report the learned curvatures associated with the optimal signature, finding that the resulting curvatures are non-uniform even for products of identical spaces (cf. Ph.D.s). Finally, Table 3 reports the signature estimations of Algorithms 2, 3 for the unweighted graphs. Among the signatures over two components, the estimated curvature signs agree with best distortion results from Table 2.

heading: 4.2 WORD EMBEDDINGS
text: To investigate the performance of product space embeddings in applications requiring the underlying manifold structure, we learned word embeddings and evaluated them on benchmark datasets for word similarity and analogy. In particular, we extend results on hyperbolic skip-gram embeddings from Leimeister & Wilson (2018) (LW), who found that hyperbolic embeddings perform favorably against Euclidean word vectors in low dimensions (d = 5, 20), but less so in higher dimensions (d = 50, 100). Building on these results, we hypothesize that in high dimensions, a product of multiple smaller-dimension hyperbolic spaces will substantially improve performance.
Setup We use the standard skip-gram model (Mikolov et al., 2013) and extend the loss function to a generic objective suitable for arbitrary manifolds, which is a variant of the objective proposed by LW. Concretely, given a word u and target w, with label y = 1 if w is a context word for u and y = 0 if it is a negative sample, the model is P (y|w, u) = σ ( (−1)1−y(− cosh(d(αu, γw)) + θ) ) .
Training followed the setup of LW, building on the fastText skip-gram implementation. Euclidean results are reported directly from fastText. Aside from choice of model, the training setup including hyperparameters (window size, negative samples, etc.) is identical to LW for all models.
Word Similarity We measure the Spearman rank correlation ρ between our scores and annotated ratings on the word similarity datasets WS-353 (Finkelstein et al., 2001), Simlex-999 (Hill et al.,
3Note that S1 and H1 are metrically equivalent to R, so these are not considered.
2015) and MEN (Bruni et al., 2014). The results are in Table 4. Notably, we find that hyperbolic word embeddings are consistently competitive with or better than the Euclidean embeddings, and the improvement increases with more factors in the product. This suggests that word embeddings implicitly contain multiple distinct but smaller hierarchies rather than forming a single larger one.
Analogies In manifolds, there is no exact analog of the “word arithmetic” of conventional word embeddings arising from vector space structure. However, analogies can still be defined via intrinsic product manifold operations. In particular, note that the loss function depends on the embeddings solely through their pairwise distances. We thus define analogies a : b :: c : d by matching the distances d2(a, b) = d2(c, d) and d2(a, c) = d2(b, d) through constructing an analog of the parallelogram, by geodesically reflecting a through the geodesic midpoint (i.e. mean) m of b, c. Note that this defines both the loss function and the intrinsic tasks purely in terms of distances and manifold operations. Hence, unlike traditional word embeddings, this formulation is generic to any space.
Our evaluation, shown in Table 5, uses the standard Google word analogy benchmark (Mikolov et al., 2013). We observe a 22% accuracy improvement over single-space hyperbolic embeddings in 50 dimensions and similar improvements over a single hyperbolic space in 100 dimensions. As with similarity, accuracy on the analogy task consistently improves as the number of factors increases.

heading: 5 CONCLUSION
text: Product spaces enable improved representations by better matching the geometry of the embedding space to the structure of the data. We introduced a tractable Riemannian product manifold class that combines Euclidean, spherical, and hyperbolic spaces. We showed how to learn embeddings and curvatures, estimate the product signature, and defined a tractable formulation of mean. We hope that our techniques encourage further research on non-Euclidean embedding spaces.

heading: ACKNOWLEDGMENTS
text: We gratefully acknowledge the support of DARPA under Nos. FA87501720095 (D3M) and FA86501827865 (SDH), NIH under No. N000141712266 (Mobilize), NSF under Nos. CCF1763315 (Beyond Sparsity) and CCF1563078 (Volume to Velocity), ONR under No. N000141712266 (Unifying Weak Supervision), the Moore Foundation, NXP, Xilinx, LETI-CEA, Intel, Google, NEC, Toshiba, TSMC, ARM, Hitachi, BASF, Accenture, Ericsson, Qualcomm, Analog Devices, the Okawa Foundation, and American Family Insurance, and members of the Stanford DAWN project: Intel, Microsoft, Teradata, Facebook, Google, Ant Financial, NEC, SAP, and VMWare. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views, policies, or endorsements, either expressed or implied, of DARPA, NIH, ONR, or the U.S. Government.

heading: A GLOSSARY OF SYMBOLS
text: We provide a glossary of commonly-used terms in our paper.

heading: B RELATED WORK
text: Hyperbolic space has recently been proposed as an alternative to Euclidean space to learn embeddings in cases where there is a (possibly latent) hierarchical structure. In fact, many types of data (from various domains) such as social networks, word frequencies, metabolic-mass relationships, and phylogenetic trees of DNA sequences exhibit a non-Euclidean latent structure, as shown in Bronstein et al. (2017).
Initial works on hyperbolic embeddings include Nickel & Kiela (2017) and Chamberlain et al. (2017). In Chamberlain et al. (2017), neural graph embeddings are performed in hyperbolic space and used to classify the vertices of complex networks. A similar application is link prediction in Nickel & Kiela (2017) for the lexical database WordNet; this work also measured predicted lexical entailment on the HyperLex benchmark dataset. The follow-up work Nickel & Kiela (2018) performs optimizations in the hyperboloid (i.e. Lorentz) model instead of the Poincaré model.
Tay et al. (2018) proposed a neural ranking based question answering (Q/A) system in hyperbolic space that outperformed many state-of-the-art models using fewer parameters compared to competitor learning models. Ganea et al. (2018a) proposed hyperbolic embeddings of entailment relations, described by directed acyclic graphs by applying hyperbolic cones as a heuristic and showed improvements over baselines in terms of representational capacity and generalization. Sala et al. (2018) developed a combinatorial construction for efficiently embedding trees and tree-like graphs without optimization, studied the fundamental tradeoffs of hyperbolic embeddings, and explored PCA-like algorithms in hyperbolic space.
Unlike Euclidean space, most Riemannian manifolds are not vector spaces, and thus even basic operations such as vector addition, vector translation and matrix multiplication do not have universal interpretations. In more complex geometries, closed form expressions for basic objects like distances, geodesics, and parallel transport do not exist. As a result, standard machine learning or deep learning tools, such as convolutional neural networks, long short term memory networks (LSTMs), logistic regression, support vector machines, and attention mechanisms, do not have exact correspondences in these complex geometries.
A pair of recent approaches seek to formulate standard machine learning methods in hyperbolic space. Gulcehre et al. (2018) introduces a hyperbolic version of the attention mechanism using the hyperboloid model. This work shows improvements in terms of generalization on several downstream applications including neural machine translation, learning on graphs and visual question answering tasks, while having compact neural representations. Ganea et al. (2018b) formulates basic machine learning tools in hyperbolic space including multinomial logistic regression, feed-forward and recurrent neural networks like gated recurrent units and LSTMs in order to embed sequential data and perform classification in hyperbolic space. They demonstrate empirical improvements on textual entailment and noisy-prefix recognition tasks using hyperbolic sentence embeddings. Cho et al. (2018) introduced a hyperbolic formulation for support vector machine classifiers and demonstrated performance improvements for multi-class prediction tasks on real-world complex networks as well as simulated datasets.
Zipf’s law states that word-frequency distributions obey a power law, which defines a hierarchy based on semantic specificities. Concretely, semantically general words that occur in a wider range of contexts are closer to the root of the hierarchy while rarer words are further down in the hierarchy. In order to capture the latent hierarchy in the natural language, there has been several proposals for training word embeddings in hyperbolic space. Dhingra et al. (2018) trains word embeddings using the algorithm from Nickel & Kiela (2017). They show that resulting hyperbolic word embeddings perform better on inferring lexical entailment relation than Euclidean embeddings trained with skip-gram model which is a standard method for training word embeddings, initially proposed by Mikolov et al. (2013). Leimeister & Wilson (2018) formulated the skip-gram loss function in hyperboloid model of hyperbolic space and evaluated on the standard the intrinsic evaluation tasks for word embeddings such as similarity and analogy in hyperbolic space.
Finally, the popularity of hyperbolic embeddings has stimulated interest in descent methods suitable for hyperbolic space optimization. In addition to tools like Bonnabel (2013) and Zhang et al. (2016), Zhang & Sra (2016) offers convergence rate analysis for a variety of algorithms and settings for Hadamard manifolds. Enokida et al. (2018) proposes an explicit update rule along geodesics in a hyperbolic space with a theoretical guarantee on convergence, and Zhang & Sra (2018) introduces an accelerated Riemannian gradient methods.
Our work also touches on previous work on maximum distance scaling (MDS) and PCA-like algorithms in hyperbolic, spherical, and more general manifolds. MDS-like algorithms in hyperbolic space are developed for visualization in Walter (2004) and Lamping & Rao (1994). Embeddings into spherical or into hyperbolic space with a PCA-like loss function were developed in Wilson et al. (2014). General forms of PCA include Geodesic PCA (Huckemann et al., 2010) and principal geodesics analysis (PGA) (Fletcher et al., 2004). A very general study of PCA-like algorithms is found in Pennec (2018).

heading: C MANIFOLD CONCEPTS AND PROOFS
text: Below, we include proofs of our results and further discuss manifold notions such as curvature.
C.1 MEANS IN PRODUCT SPACES
We begin with Lemma 2, restated below for convenience. Lemma 2. Let P be a product of model spaces of total dimension r, T = {p1, . . . , pn} points in P and w1, . . . , wn weights satisfying wi ≥ 0 and ∑n i=1 wi = 1. Moreover, let the components of the points in P , pi|Sj restricted to each spherical component space Sj fall in one hemisphere of Sj . Then, Riemannian gradient descent recovers the mean µ(T ) within distance in timeO(nr log −1).
Proof. Consider the squared distance d2(p, q) for p, q ∈M for a manifold M . Fix q. We denote the Hessian in p by Hp,M (q). Then, we have the following expressions for the Hessian of the squared distance of a sphere, derived in Pennec
Hp,Sr (q) = 2uu T + 2
θ cos θ
sin θ (Ir − ppT − uut),
where Ir is the identity matrix, θ = acos(p · q) is the distance dSr (p, q) and u = (Ir − ppT )q/ sin θ. In Pennec, it is shown that the eigenvectors of Hp,Sr (q) are 0, 1, and θ cot(θ); thus the Hessian is bounded and if θ ∈ [0, π/2], it is also positive definite (PD). For hyperbolic space (under the hyperboloid model), the Hessian is
Hp,Hr (q) = 2uu TJ + 2θ coth θ(J + ppT − uuT )J.
Here θ = acosh(−〈p, q〉∗), J is the matrix associated with the Minkowski inner product, i.e., 〈p, q〉∗ = pTJq, and u = logp(q)/θ. The log here refers to the logarithmic map. That is, if q = expp(v), then v = logp(q). Moreover, exact expressions for the eigenvalues of Hp,Hr (q) in terms of θ imply that it is always bounded and PD.
The Hessian for Euclidean space is Hp,Er (q) = 2Ir, which is also PD.
Now we can express the Hessian of the weighted mean. We write Hp,P for the Hessian of the weighted variance ∑n i=1 wid 2 P(p, pi) (recall that µ(p1, . . . , pn) = argminp ∑n i=1 wid 2 P(p, pi)). We have, by the decomposability of the distance, that
n∑ i=1 wid 2 P(p, pi) = s∑ j=1 n∑ i=1 wid 2 sj (p, pi) + h∑ j=1 n∑ i=1 wid 2 hj (p, pi) + n∑ i=1 wid 2 E(p, pi).
Taking the Hessian,
Hp,P = s∑ j=1 n∑ i=1 wiHp,Ssj (pi) + h∑ j=1 n∑ i=1 wiHp,Hhj (pi) + 2nIe.
Now, by assumption, the spherical components for our points in each of the spheres, pi|Sj , fall within one hemisphere, and we may initialize our gradient descent (that is, our p0) within this hemisphere. Then, the angle θ in each of the spherical distances is in [0, π/2], so that the corresponding Hessians are PD.
Since each term in the sum is PD and the weights satisfy wi ≥ 0, with at least one positive weight, Hp,P is also PD. Moreover, these Hessians are bounded. Then we apply Theorem 4.2 (Chap. 7.4) in Udriste (1994)), which shows linear rate convergence, as desired.
C.2 CURVATURE ESTIMATION
We discuss the notions of curvature relevant to our product manifold in more depth. We start with a high-level overview of various definitions of curvature. Afterwards, we introduce the formal definitions for curvature and apply them to the product construction.
Definitions of Curvature There are multiple notions of curvature, with varying granularity. Some of these notions are suitable for working with manifolds abstractly (without reference to an ambient space, that is, intrinsic). Others, in particular older definitions pre-dating the development of
the formal mechanisms underpinning differential geometry, require the use of the ambient space. Gauss defined the first intrinsic notion of curvature, Gaussian curvature. It is the product of the principal curvatures, which can be thought of as the smallest and largest curvature in different directions.4Below we consider several such notions.
Scalar curvature is a single value associated with a point p ∈ M and intuitively relates to the area of geodesic balls. Negative curvature means volumes grow faster than in Euclidean space, positive means volumes grow slower.
A more fine-grained notion of curvature is that of sectional curvature: it varies over all “sheets” passing through p. Note that curvature is inherently a notion of two-dimensional surfaces, and the sectional curvature fully captures the most general notion of curvature (the Riemannian curvature tensor). More formally, for every two dimensional subspace U of the tangent space TpM , the sectional curvature K(U) is equal to the Gaussian curvature of the sheet Expp(U). Intuitively, it measures how far apart two geodesics emanating from p diverge. In positively curved spaces like the sphere, they diverge more slowly than in flat Euclidean space.
The Ricci curvature of a tangent vector v at p is the average of the sectional curvature K(U) over all planes U containing v. Geometrically the Ricci curvature measures how much the volume of a small cone around direction v compares to the corresponding Euclidean cone. Positive curvature implies smaller volumes, and negative implies larger. Note that this is natural from the way geodesics bend in various curvatures. The scalar curvature is in fact defined as an average over the Ricci curvature, giving the intuitive relation between scalar curvature and volume. It is thus also an average over the sectional curvature.
Discrete Analogs of Curvature Discrete data such as graphs do not have manifold structure. The goal of curvature analogs such as ξ is to provide a discrete analog of curvature which satisfies similar properties to curvature; we use this to facilitate choosing an appropriate Riemannian manifold to embed discrete data into. In this work, we focus on the sectional curvature, but discrete versions of other curvatures have been proposed such as the the Forman-Ricci (Weber et al., 2017) and OllivierRicci (Ollivier, 2009) curvatures.
The input to the discrete curvature estimation from Section 3.2 is analogous to other discrete curvature analogs. For example, the Ricci curvature is defined for a point p and a tangent vector u, and the coarse Ricci curvature is defined for a node p and neighbor x (Ollivier, 2011). Similarly, the sectional curvature is defined for a point and two tangent vectors, and ξ is defined for a a node and two neighbors.
Sectional Curvature in Product Spaces Now we are ready to tackle the question of curvature in our proposed product space. Let M be our Riemannian manifold and X (M) be the set of vector fields on M . The curvature R of M assigns a function R(X,Y ) : X (M) → X (M) to each pair of vector fields (X,Y ) ∈ X × X . For a vector field Z in X (M), the function R(X,Y ) can be written
R(X,Y )Z = ∇Y∇XZ −∇X∇Y Z +∇[X,Y ]Z.
Here∇ is the Riemannian connection for the manifoldM , and [X,Y ] is the Lie bracket of the vector fields X,Y .
For convenience, we shall write the inner product 〈R(X,Y )Z, T 〉 as (X,Y, Z, T ); this is the Riemannian curvature tensor. Then, the sectional curvature is defined as follows. Let us take V to be a two-dimensional subspace of TpM and x, y ∈ V be linearly independent (so that they span V). Then, the sectional curvature at p for subspace V is
K(x, y) := (x, y, x, y)
‖x‖2‖y‖2 − 〈x, y〉2 . (4)
The model spaces S,H,E are the spaces of constant curvature, where K is constant for all points p and 2-subspaces V .
4The curvature of a curve can be found by considering the osculating circles which match it to second order.
For simplicity, suppose we are working with M =M1×M2; the approach extends easily for larger products. We write x = (x1, x2) for x ∈ TpM . Similarly, let R1, R2 be the curvatures and K1,K2 be the sectional curvatures of M1,M2 at p, respectively. Then the curvature tensor decomposes as
R(X,Y )Z = (R1(X1, Y1)Z1, R2(X2, Y2)Z2). (5)
Our goal is to evaluate the sectional curvature K((x1, x2), (y1, y2)) for the product manifold M . We show the following, re-stated for convenience: Lemma 1. Let M = M1 ×M2 where Mi has constant curvature Ki. For any u, v ∈ TpM , if K1,K2 are both non-negative, the sectional curvature satisfies K(u, v) ∈ [0,max{K1,K2}]. If K1,K2 are both non-positive, the sectional curvature satisfies K(u, v) ∈ [min{K1,K2}, 0]. If Ki < 0 and Kj > 0 for i 6= j, then K(u, v) ∈ [Ki,Kj ].
Proof. Let us start with the numerator of equation (4):
(x, y, x, y) = ((x1, x2), (y1, y2), (x1, x2), (y1, y2))
= 〈R((x1, x2), (y1, y2))((x1, x2)), (y1, y2)〉 = 〈(R1(x1, y1)x1), (R2(x2, y2)x2)〉(y1, y2)〉 = 〈R1(x1, y1)x1, y1〉+ 〈R2(x2, y2)x2, y2〉
Here, we used equation 5 in the third line.
Note that when x1, y1 are linearly independent, then 〈R1(x1, y1)x1, y1〉 = K1(‖x1‖2‖y1‖2 − 〈x1, y1〉2) by (4). Otherwise, this still holds since it is 0. So we can relate the above to K1,K2:
(x, y, x, y) = K1(‖x1‖2‖y1‖2 − 〈x1, y1〉2) +K2(‖x2‖2‖y2‖2 − 〈x2, y2〉2).
For convenience, we write αi = ‖xi‖2‖yi‖2 − 〈xi, yi〉2 for i = 1, 2. Then the numerator is simply K1α1 +K2α2. Next, we consider the denominator of (equation 4):
‖x‖2‖y‖2 − 〈x, y〉2 = ‖(x1, x2)‖2‖(y1, y2)‖2 − 〈(x1, x2), (y1, y2)〉2
= (‖x1‖2 + ‖x2‖2)(‖y1‖2 + ‖y2‖2)− (〈x1, y1〉+ 〈x2, y2〉) = α1 + α2 + ‖x1‖2‖y2‖2 + ‖x2‖2‖y1‖2
= α1 + α2 + β,
where we set β = ‖x1‖2‖y2‖2 + ‖x2‖2‖y1‖2. Thus, we have that
K((x1, x2), (y1, y2)) = α1K1
α1 + α2 + β + α2K2 α1 + α2 + β . (6)
Now, note that β > 0, since we assumed that x1, y1 and x2, y2 are linearly independent. By CauchySchwarz, αi ≥ 0. Then, if Ki ≥ 0, we have that (αiKi)/(α1 + α2 + β) ≤ (αiKi)/(α1 + α2), so that
0 ≤ K((x1, x2), (y1, y2)) ≤ α1
α1 + α2 K1 + α2 α1 + α2 K2. (7)
Thus, we relate the product sectional curvature to a convex combination of the factor sectional curvatures K1,K2. We have for non-negative K1,K2 (e.g., Euclidean and spherical spaces) that K((x1, x2), (y1, y2)) ∈ [0,max{K1,K2}]. A similar result holds for the non-positive (Euclidean and hyperbolic) case. The last case (one negative, one positive space) follows along the same lines.
Distribution ofK The range of curvatures from Lemma 1 can be easily extended to a more refined distributional analysis. In particular, consider sampling any point p and a random plane V ⊆ TpM . By homogeneity, we can equivalently fix p. The 2-subspaces of TpM ' Rd forms the Grassmannian manifold Gr(2, TpM). The uniform measure on this (i.e. invariant to multiplication by an orthogonal matrix) can be recovered from the Haar measure on the orthogonal group O(d), which
Algorithm 2 Sectional curvature distribution 1: Input: Dimensions d1, d2 2: a1 ← χ2(d1 − 1) 3: b1 ← χ2(d1 − 1) 4: t1 ← Beta((d1 − 1)/2, (d1 − 1)/2) 5: c1 ← a1/21 b 1/2 1 (2t1 − 1)
6: a2 ← χ2(d2 − 1) 7: b2 ← χ2(d2 − 1) 8: t2 ← Beta((d2 − 1)/2, (d2 − 1)/2) 9: c2 ← a1/22 b 1/2 2 (2t2 − 1)
10: α1 ← a1b1 − c21 11: α2 ← a2b2 − c22 12: β ← a1b2 + a2b1 13: return α1α1+α2+βK1 + α2 α1+α2+β K2
itself can be constructed by orthonormalizing independent random normal vectors. In particular, it suffices to consider V spanned by independent Gaussians x, y ∼ N (0, I). Furthermore, we do not actually need to sample d-dimensional vectors x, y to compute the relevant curvature in equation 6. It suffices to sample the quantitities 〈x1, y1〉, 〈x1, x1〉, 〈y1, y1〉 and 〈x2, y2〉, 〈x2, x2〉, 〈y2, y2〉 directly. Note that α := 〈x1, x1〉 and β := 〈y1, y1〉 are χ2-distributed, while 〈x1, y1〉 ∼ √ αβγ, where γ is distributed as the dot product of two uniformly random unit vectors. By rotational invariance, this is the same as the first coordinate of a random unit vector, which in turn is distributed as X21/(X 2 1 + · · · + X2d) for independent normal Xi, and therefore (γ + 1)/2 ∼ Beta((d− 1)/2, (d− 1)/2). Thus a random K(V) can be computed by sampling from well known distributions in constant time, via Algorithm 2.
Furthermore, without knowing K1,K2 a priori, an estimate for these curvatures can be found by matching the distribution of sectional curvature from Algorithm 2 to the empirical curvature computed from Algorithm 3. In particular, Algorithm 2 can be used to generate samples for α1α1+α2+β and α2α1+α2+β . The overall moments are then simple functions of K1,K2, and the sample moments of the above quantities, so that K1,K2 can then be found by matching moments.
Curvature Estimation We prove the facts we mentioned in the main body of the paper relating to the evaluation of ξ over fundamental pieces of graphs: lines, cycles, and trees.
Lemma 3. Suppose a lies on the same geodesic line as b,m, c; in other words, WLOG dG(a, b) ≤ dG(a, c) and suppose dG(a, c) = dG(a, b) + dG(b,m) + dG(m, c). Then ξ(m; b, c; a) = 0.
Lemma 4. Consider a cycle graph C with nodes b,m, c such that (m, b) and (m, c) are neighbors. Then for all a ∈ C, ξ(m; b, c; a) is either 0 or positive.
Proof. Without loss of generality, let the cycle have an even number of vertices n. Let k be the node diametrically opposite from m. Note that for any vertex a 6= n, a, b,m, c lie on a geodesic line, and therefore ξ(m; b, c; a) = 0. On the other hand,
ξ(m; b, c; a) = 1
2 · n/2 ((n 2 )2 + 1− 1 2 ( (n/2− 1)2 + (n/2− 1)2 )) = 1.
The case when n is odd is similar, where we find that two nodes a satisfy ξ(m; b, c; a) = n/(n− 1) and the rest are 0.
Lemma 5. Consider a tree graph T with nodes b,m, c such that (m, b) and (m, c) are neighbors. Then for all a ∈ T , ξ(m; b, c; a) is either 0 or negative.
Algorithm 3 Empirical estimation of sectional curvature distribution 1: Input: Graph G = (V,E) 2: m← Uniform(V ) 3: b← Uniform(N (m)) {N (v) is the neighbor set of v} 4: c← Uniform(N (m)) 5: a← Uniform(V ) 6: K ← ξ(m; b, c; a) 7: return K
Proof. Due to the tree structure, a is either geodesic with b,m, c, or a is connected to m with a path that does not pass through b or c. In the former case, ξ(m; b, c; a) = 0. In the latter case,
ξ(m; b, c; a) = 1
2d
( d2 + 1− (d+ 1)2 ) = −1,
where d = dG(a,m).
Given a graph, the distribution of ξ(m; b, c) over random “planes” (i.e. pairs of neighbors b, c) is easily calculable. This yields a distribution that can then be averaged over m to obtain an average sectional curvature distribution. To simplify this, we find the distribution via sampling (Algorithm 3) in the calculations for Table 3, before being fed into Algorithm 2 to estimate Ki.
As a corollary of Lemma 5, note that the ξ becomes more negative for trees of higher degree, matching the intuition that higher degree trees are more appropriate for hyperbolic space embeddings (Sala et al., 2018).
We additionally note that a line of work has studied discrete analogs of curvature for regular objects such as triangular planar tessellations (including polyhedra) (Thurston, 1998). For example, these notions assign positive curvature to regular polyhedra (the tetrahedron, octahedron, icosahedron), zero curvature to the flat planar tessellation, and positive curvature to the order-7 triangular tiling of the hyperbolic plane. It is easily checked that Algorithm 3 assigns the right curvature sign to each of these objects.
C.3 COMBINATORIAL CONSTRUCTIONS
The `1 and min-based distances are suitable for combinatorial constructions where we do not learn embeddings by optimizing a surrogate loss function, but rather by directly placing points in the product space, often via recursive procedures. Such constructions offer superior speed and other benefits. On the other hand,they are only available for certain classes of graphs. Additionally, since the constructions rely on the `1 and min distances, they do not take advantage of the Riemannian structure, and thus do not have the same applicability downstream.
We often exploit the combinatorial construction for trees from Sala et al. (2018) as a building block; it offers worst-case distortion5 1 + ε when embedding a tree into Hr for all r ≥ 2, where we can control ε.
Hanging Tree Construction Consider the class of graphs G = (V,E) where V = B ∪ T1 ∪ T2 . . . ∪ T|B|, so that B is a base set of nodes and for each node a ∈ B, there is a tree Ta connected to a (the hanging trees). We show how to use P with the `1 distance to reduce the cost of embedding G to that of embedding the subgraph induced by B.
We embed G into the product space P = P ′ ×Hr equipped with the `1 distance. Here, P ′ is some product manifold. We do the embedding in two steps:
5The worst-case distortion Dwc is a commonly-considered variant of distortion
Dwc(f) = maxu,v∈U :u6=v dV (f(u), f(v))/dU (u, v)
minu,v∈U :u6=v dV (f(u), f(v))/dU (u, v) .
The worst-case distortion is the ratio of the worst expansion and the worst contraction of distances; note that it is scale-invariant. Here, the best worst-case distortion is Dwc(f) = 1.
1. Embed the subgraph induced by B into P ′ by any method; let the resulting worst-case distortion be 1 + δ. Embed every node in Ti into the embedded image of node i,
2. Form the tree T by connecting each of the T1, . . . , T|B| to a single node (equivalent to crushing all the nodes in B into a single node), and embed T into Hr by using the combinatorial construction. Additionally, all of the nodes in B are embedded into the image of the single central node in Hr.
We can check the distortion. For nodes xa, yb in subtrees hanging off a, b ∈ B, the distance is dG(xa, yb) = dT (xa, yb)+dB(x, y). Since the distortion for the two embeddings are given by 1+δ and 1 + ε, it is easy to check that the overall distortion is at most max{1 + δ, 1 + ε}. As a concrete example, consider the ring of trees in Figure 1. Then, B = Cr, the cycle on r nodes. In this case, we can embed B into P ′ = S1. Let the nodes of B be indexed a1, . . . , ar. We embed ai into Ai = (cos( 2πid ), sin( 2πi d )). Then, for i < j,
dS(Ai, Aj) = acos(Ai ·Aj) = acos ( cos ( 2πi
d
) cos ( 2πj
d
) + sin ( 2πi
d
) sin ( 2πj
d )) = acos ( cos ( 2π(i− j)
d )) =
2π(|j − i|) d .
Thus indeed, the embedding has worst-case distortion 1. Thus, the overall distortion for the ring of trees is 1 + ε. Since we control ε, we can achieve arbitrarily good distortion for the ring of trees. The complexity of this algorithm is linear in the number of nodes, since embedding the trees and ring is linear time.
General Graph Construction Now we use the min distance space to construct an embedding of any graph G on r nodes with arbitrarily low distortion via the space P = H2 ×H2 × . . .×H2 with r − 1 copies. As we shall see, this construction is ideal (arbitrarily low distortion, any graph) other than requiring O(r) spaces.
Let the nodes of G be V = {a1, . . . , ar}. Now, for each ai, 1 ≤ i ≤ r − 1, form the minimum distance tree Ti rooted at ai. Then, embed Ti into the ith copy of H2 via the combinatorial construction. Then, for any nodes ai, aj ∈ V , the distance dG(ai, aj) is attained by dTi(ai, aj), or dTj (aj , ai) in the case i = r. Since at least one of Ti or Tj , say Ti, is embedded in H2 with distortion 1 + ε, if we make ε small enough, the smallest distance among the embedded copies is indeed that for Ti, so our overall distortion is still 1 + ε.
D VISUALIZATIONS AND INTERPRETABILITY
The combinatorial construction using the `1 distance (Section C.3) can embed the hanging tree graph arbitrarily well, unlike any single type of space. Unlike a single space, this also lends more interpretability to the embedding, as each component displays different qualitative aspects of the underlying graph structure. Figure 4 shows that this phenomenon does in fact happen empirically, even using the optimization approach over the `2 (Riemannian) instead of `1 distance.

heading: E EXPERIMENTAL DETAILS
text: We provide some additional details for our experimental setups.
Graph Reconstruction The optimization framework was implemented in PyTorch. The loss function (2) was optimized with SGD using minibatches of 65536 edges for the real-world datasets, and ran for 2000 epochs. For the Cities graph, the learning rate was chosen among
{0.001, 0.003, 0.01}. For the rest of the datasets, the learning rate was chosen from a grid search among {10, 30, 100, 300, 1000} for each method.6
Each point in the embedding is initialized randomly according to a uniform or Normal distribution in each coordinate with standard deviation 10−3. (In the hyperboloid and spherical models, all but the first coordinate is chosen randomly, and the first coordinate is a function of the rest.)
Table 2 uses only Algorithm 1, and initializes the curvatures to−1 for hyperbolic components and 1 for spherical components. These curvatures are learned using the method described in Section 3.1, and the “Best model” row reports the final curvatures of the best signature.
Word Embeddings Following LW, the input corpus is a 2013 dump of Wikipedia that has been preprocessed by lower casing and removing punctuation, and filtered to remove articles few page views. All other hyperparameters are chosen exactly as in as LW, including their numbers for Euclidean embeddings from fastText. The datasets used for similarity (WS-353, Simlex-999, MEN) and analogy (Google) are also identical to the previous setup.
6Note that the high LR stems from the particular choice of normalization for (2) in our implementation.

Review summaries:
This paper proposes a new method to embed a graph onto a product of spherical/Euclidean/hyperbolic manifolds. The key is to use sectional curvature estimations to determine proper signature, i.e., all component manifolds, and then optimize over these manifolds. The results are validated on various synthetic and real graphs. The proposed idea is new, nontrivial, and is well supported by experimental evidence.