Year: 2019

Abstract:
Recently, non-Euclidean spaces became popular for embedding structured data. However, determining suitable geometry and, in particular, curvature for a given dataset is still an open problem. In this paper, we define a notion of global graph curvature, specifically catered to the problem of embedding graphs, and analyze the problem of estimating this curvature using only graph-based characteristics (without actual embedding the graph). We show that optimal curvature essentially depends on the dimensionality of the embedding space and loss function one aims to minimize via embedding. We review existing notions of local curvature (e.g., Ollivier-Ricci curvature) and analyze their properties theoretically and empirically. In particular, we show that such curvatures are often unable to properly estimate the global one. We also make an important observation: larger dimensionality usually leads to less negative optimal curvature. We propose a new estimator of global graph curvature which, in contrast to the existing ones, reflects this property as it is dimension-specific. We demonstrate that for a given dimension the new estimator is able to distinguish between “hyperbolic” and “Euclidean” networks.

heading: 1 INTRODUCTION
text: Representation learning is an important tool for learning from structured data such as graphs or texts (Grover & Leskovec, 2016; Perozzi et al., 2014; Mikolov et al., 2013). State-of-the-art algorithms typically use Euclidean space for embedding. Recently, however, it was found that hyperbolic spaces demonstrate superior performance for various tasks (Nickel & Kiela, 2018; Sala et al., 2018), while in some cases spherical spaces can be useful (Liu et al., 2017). A key characteristic classifying the above-mentioned spaces is curvature, which is negative for hyperbolic spaces, zero for Euclidean and positive for spherical spaces. These findings, therefore, show that certain graphs are better represented in spaces with non-zero curvature. While some methods simply fix curvature (e.g., -1 for hyperbolic space) and then find the optimal embedding of the graph in the corresponding space (Nickel & Kiela, 2018), others try to learn the right curvature and embedding simultaneously (Gu et al., 2019).
In this paper, we analyze the problem of determining a graph curvature suitable for embedding without actual embedding the graph itself. The aim is to use some simple graph characteristics to understand whether it is reasonable to embed a graph into some non-Euclidean space and if yes, then which curvature to choose. Having such an estimator would save computational resources, since learning an embedding is computationally expensive and should be done for each space separately. More importantly, it can also save human resources by showing whether it is worth investing resources in the implementation of a more complex embedding algorithm.
We make an important first step in this direction by introducing a concept of global graph curvature, which depends on both the dimension and loss function used for the embedding. We consider two loss functions: distortion, which is widely used in embedding literature, and threshold-based loss (see Section 2), which is more suitable for some practical applications. We demonstrate, both theoretically and empirically, that these loss functions lead to fundamentally different graph curvatures. We also compare several estimators of the global curvature, in particular, the ones based on well-known Ollivier-Ricci and Forman-Ricci local graph curvatures. Our analysis shows that all these notions give curvatures that are far from the optimal curvature for embedding the graph (in particular, because they are dimension-independent). This raises the important question of how to properly estimate the best curvature for embedding graphs. We approach this problem by introduc-
ing a new curvature estimator which, in contrast to all existing ones, is dimension-specific. This estimator agrees with our theoretical results and is also able to distinguish between “hyperbolic” and “Euclidean” networks.
One important insight, which we gained based on both theoretical and empirical analysis, is the fact that the optimal curvature is usually smaller for smaller dimensions. In other words, a network which seems to be negatively curved (for some small dimension) usually becomes more neutral as dimensionality grows.
Finally, while in the current research we assume that the global graph curvature is constant, this concept can be extended in the future to cover, e.g., the product spaces from (Gu et al., 2019). We focused on the constant curvature since, first, such spaces are widely used in various applications (Tifrea et al., 2018) and, second, even for constant curvature we observed many non-trivial theoretical and empirical results. These results and insights can eventually be extrapolated to analyze curvature in other, more complicated spaces. To the best of our knowledge, the problem of analyzing different notions of curvature for embedding graphs (even in simple spaces) was not considered before, so we hope that more results will follow.

heading: 2 BACKGROUND AND RELATED WORK
text: Graph embeddings For an unweighted connected graph G = (V,E) equipped with the shortest path distance metric dG, a graph embedding f is a map f : V → U , where U is a metric space. We refer to Goyal & Ferrara (2018) for a survey of several graph embedding methods and their applications.
The goal of an embedding is to preserve some structural properties of a graph. Depending on an application, different loss/quality functions are used to measure the quality of a graph embedding. The most well-known is distortion:1
D(f) = 1( n 2 ) ∑ u 6=v |d(f(u), f(v))− dG(u, v)| dG(u, v) .
Distortion is a global metric, it takes into account all graph distances. However, in some practical applications, it may not be the best choice. For example, in recommendation tasks, we usually deal with a partially observed graph, so a huge graph distance between nodes in the observed part does not necessarily mean that the nodes are not connected in the full graph. Additionally, as discussed in Section 4.3.1, graph distances are hard to preserve: there are simple graphs on just 4 nodes that can be perfectly embedded only in a space of curvature −∞ for any dimension. Another measure, often used for embeddings, is Mean Average Precision (MAP), which, for a given node v, compares the distance-based ranking of other embedded nodes with the graphneighborhood-based ranking. In contrast to distortion, MAP is scale-invariant, as it cares only about the order. Since changing curvature is equivalent to changing scale, MAP is insensitive to curvature.2 However, in practical applications like recommendation systems, ranking scores are usually complemented by minimum score thresholds to have personalized sizes of top recommended items. This motivated us to consider another loss function, which is at the same time local and scale-dependent.
Let us define the following class of threshold-based loss functions. Given an embedding f of a graph G, we (re)construct a graphG′ in the following way: v and u are connected inG′ iff d(f(v), f(u)) ≤ 1. Then, any loss function which is based on the comparison of G and G′ is called thresholdbased. While all our theoretical results hold for any threshold-based loss function (see Section 4), in our experiments we measure and compare several functions of this type including, e.g., zeroone loss for the edge classification problem (whether a given node pair is connected or not), see Appendix E.2 for definitions and discussion. Such loss functions are natural in many applications (graph reconstruction, link prediction, recommendations).
1There are other definitions of distortion in the literature, see, e.g., (Sala et al., 2018). 2In other words, it is sufficient to consider only the curvatures -1, 0, 1, corresponding to hyperbolic, Euclidean and spherical spaces. Moreover, by considering a small enough region in hyperbolic or spherical space we get geometry similar to the Euclidean one, so for MAP it is important to distinguish only between -1 and 1.
Hyperbolic and Spherical Spaces For many years, Euclidean space was the primary choice for data embeddings (Goyal & Ferrara, 2018). However, it turned out that many observed datasets are well fitted into hyperbolic space (Krioukov et al., 2010). Nickel & Kiela (2017) have shown that such hyperbolic embeddings can improve state-of-the-art quality in several practical tasks, e.g., lexical entailment and link prediction. On the other hand, spherical spaces are also used for embeddings (Liu et al., 2017). Gu et al. (2019) goes even further by suggesting mixed spaces: product manifolds combining multiple copies of spherical, hyperbolic, and Euclidean spaces.
The main advantage of hyperbolic space is that it is “larger”: the volume of a ball grows exponentially with its radius. Hence, such spaces are well suited for tree-like structures. On the other hand, spherical spaces are suitable for embedding cycles (Gu et al., 2019). Spherical and hyperbolic spaces are parametrized by curvature c, which is positive for spherical space and negative for hyperbolic space. As c → 0, geometry of both these spaces becomes similar to the Euclidean one. We discuss some geometrical properties of these different spaces in Appendix A.

heading: 3 LOCAL GRAPH CURVATURES
text: While in this paper we analyze the global graph curvature, there are several local ones proposed in the literature. Many of them are based on the notion of sectional curvature and Ricci curvature defined for Riemannian manifolds. Intuitively, Ricci curvature controls whether the distance between small spheres is smaller or larger than the distance between the centers of the spheres. Ricci curvature is positive if small spheres are closer than their centers are. We refer to (Jost, 2009; O’neill, 1983) for more details on Ricci curvature.
Ollivier curvature Ollivier curvature translates the definition of Ricci curvature to graphs. Again, the idea is to compare the distance between two small balls with the distance between their centers. The distance between balls is defined by the well-known optimal transport distance (a.k.a. Wasserstein distance or earth-mover distance). Formally, for a graphG we consider the shortest path metric on G, denoted by dG, and let WG1 denote the Wasserstein metric with respect to the metric space (G, dG). Furthermore, for each node v we let mv denote the uniform probability measure on the neighbors of v, i.e., mv(u) = 1u∼vdeg(v) , where deg(v) denotes the degree of v. Then, the classic definition3 of Ollivier curvature between two neighboring nodes v ∼ u in G is defined as
κG(u, v) = 1−WG1 (mv,mu). (1)
We note that Ollivier curvature always belongs to the interval [−2, 1] (Jost & Liu, 2014).
Forman curvature Forman curvature (Sreejith et al., 2016) is based on the discretization of Ricci curvature proposed by Forman (2003). It is defined for a general weighted graph G, with both node and edge weights. When the graph G is not weighted, the definition becomes:
FG(u, v) = 4− (deg(v) + deg(u)). (2)
Forman was interested in a general discretization of curvature for Riemannian manifolds and his formula includes faces of any dimension. Although this can be translated to graphs (Weber et al., 2017), the formula becomes quite cumbersome. Therefore, in Equation 3 only 1-dimensional faces (edges) are included. One can extend this expression by including higher dimensional faces. This was considered in (Samal et al., 2018), where 2-dimensional faces on three nodes (triangles) were included. In the case of an unweighted graph, we then obtain
F̂G(u, v) = F (u, v) + 3∆uv = 4− deg(v)− deg(u) + 3∆uv, (3)
where ∆uv is the number of triangles that contain the edge (u, v).
Based on the definitions, both Forman curvatures, especially FG(u, v), are expected to often be highly negative. Indeed, this is what we observe in Sections 4.3 and 5.
3Note that Ollivier curvature is defined in much more generality in terms of metrics and random walks, see (Ollivier, 2009). Thus, different version on graphs can be considered. Equation 1 corresponds to the classical choices of graph distance and random walk on the graph.
Heuristic sectional curvature A different notion of curvature used by Gu et al. (2019) is based on the following geometric fact. Let abc be a geodesic triangle and let m be the (geodesic) midpoint of bc. Then the value d(a,m)2 + d(b,c) 2
4 − d(a,b)2+d(a,c)2
2 is equal to zero in euclidean space, is positive in spherical space and negative in hyperbolic space.
For graphs, let v be a node in G, b, c neighbors of v and a any other node. Then, we define
ξG(v; b, c; a) = 1
2dG(a, v)
( dG(a, v) 2 + dG(b, c) 2
4 − dG(a, b)
2 + dG(a, c) 2
2
) . (4)
This resembles the formula above with m = v and the normalization constant 2dG(v, a) is included to yield the right scalings for trees and cycles. To define the graph sectional curvature of a node v and its neighbors b, c, we average ξG(v; b, c; a) over all possible a: ξG(v; b, c) =
1 |V |−3 ∑ a∈G\{v,b,c} ξG(v; b, c; a). 4

heading: 4 GLOBAL GRAPH CURVATURE
text: The problem with these different notions of local graph curvature is that they cannot be easily used in practical applications, where data is usually embedded in a space of constant curvature. Hence, a global notion of curvature is needed. In this section, we propose a practice-driven definition of global graph curvature, discuss how to estimate this curvature based on local notions and compare all curvatures theoretically and empirically for several simple graphs.

heading: 4.1 DEFINITION
text: For a graph G, let f(G) be an embedding of this graph into a d-dimensional space of constant curvature c (spherical, Euclidean or hyperbolic). Assume that we are given a loss function L(f) for the embedding task (see Section 2). Now, let Lopt(G, d, c) be the optimal loss for given d and c: Lopt(G, d, c) = minf L(f). Then, we define d-dimensional curvature of G in the following way:
CLd (G) = arg min c Lopt(G, d, c) . (5)
Note that there may be several values of curvature c delivering the minimum of Lopt(G, d, c), in this case we say that CLd (G) consists of all such points. 5
Below we analyze global curvatures based on distortion (Cdistd (G)) and threshold-based (C thr d (G)) loss functions. In the latter case, in experiments, we measure zero-one loss, but our theoretical results apply to any threshold-based loss, since Lopt(G, d, c) reaches its minimum on “perfect” embeddings, where we precisely reconstruct the graph G.

heading: 4.2 APPROXIMATIONS
text: Let us discuss how local graph curvatures can be used to estimate the global one. In all cases, the standard practice is to average edge or sectional curvature over the graph. Ollivier curvature κ(G) = 1|E| ∑ u∼v κG(u, v). Forman curvature F (G) = 1|E| ∑ u∼v FG(u, v), F̂ (G) = 1|E| ∑ u∼v F̂G(u, v).
Average sectional curvature Let P3 denote the number of paths of length 3 in G, then ξ(G) = 1 P3 ∑ v∈V ∑ b<c:b,c∈N(v) ξG(v; b, c).
4We assume that a does not coincide with b or c, which do not affect the average much, but makes our results in Section 4.3 more succinct.
5Further we slightly abuse notation by writing that CLd (G) is a real value if such c is unique and a set of values otherwise.
It is important to note that all curvatures discussed above do not depend on neither dimension d nor loss function L. However, as we show below, global curvature defined in Section 4.1 significantly depends on them.
Let us also mention that there is a concept of Gromov’s hyperbolicity (Gromov, 1987), which is sometimes used to decide whether it is reasonable to embed a graph to a hyperbolic space. However, first, this estimator cannot be easily converted to curvature, and, second, it does not say anything about the sphericity of data.

heading: 4.3 THEORETICAL ANALYSIS OF GLOBAL CURVATURE AND ITS APPROXIMATIONS
text: To better understand the performance of the proposed approximations of global graph curvature, we shall consider several basic graphs and analyze their global curvature and approximations both theoretically and empirically. By studying these graphs we also hope to gain insights into how classic graph topologies influence the curvature of the space in which they can be properly embedded. For more complex graphs, e.g., for combinations of simple graphs studied in this section, it becomes extremely hard to prove rigorous theoretical results. However, the obtained intuitions work in such scenarios, as we illustrate and discuss in Appendix C. The experimental setup for our empirical illustrations is described in Appendix E.3.
4.3.1 STAR Sn
It is pointed out in numerous papers that trees are negatively curved. We analyze this theoretically and start with the simplest tree: one central node and n leaves. We denote this graph by Sn and assume that n ≥ 3.
Ollivier curvature Consider any tree graph T , let v, u be two neighbors. Then Proposition 2 in (Jost & Liu, 2014) states that
κT (u, v) = −2 (
1− 1 deg(v) − 1 deg(u)
)+ , (6)
where t+ = max{0, t}. In particular, if either deg(v) = 1 or deg(u) = 1, then κT (u, v) = 0. As a result, for a star we have κSn(u, v) = 0, so κ(Sn) = 0 and stars are not negatively curved according to Ollivier curvature.
Forman curvature If follows from Equation 2 and Equation 3 that F (Sn) = F̂ (Sn) = 3− n, so stars are highly negatively curved for large n according to Forman curvature.
Average sectional curvature Heuristic sectional curvature is defined for a node and its two neighbors. In case of a star we can only take a central node v and two neighboring ones b and c. For any other node a we obtain ξSn(v; b, c; a) = −1. Therefore, by averaging we obtain ξ(Sn) = −1.
Distortion-based curvature We prove the following theorem (the proof is in Appendix B.3).
Theorem 4.1. Assume that d and n are fixed. If c is bounded below by a constant, then D(Sn) is also bounded below by a constant. If c→ −∞, then the optimal distortion Dopt(Sn) = Θ ( 1√ −c ) . Therefore, for any Sn we have Cdistd (Sn) = −∞.
This result is illustrated in Figure 6 (left): distortion decreases as curvature becomes smaller. The intuition behind this result is the following: we cannot embed a star S3 with zero distortion into a space of any constant curvature and any dimension, because in case of zero distortion the central node v has to lie on the geodesics between all pairs of leaves, so all 4 nodes have to belong to one geodesics, which is impossible. Moreover, the same problem occurs if any graph G contains S3 as an induced subgraph. On the other hand, if c→ −∞, we can spread all leaves of Sn uniformly on a circle of radius 1 around the central node and distortion of such construction will tend to zero since the distance between the pairs of leaves will tend to 2 (triangles become thinner). Further we will see that if we minimize a threshold-based loss, then any tree can be perfectly embedded with d = 2.
Threshold-based curvature Here we have the following theorem (the proof is in Appendix B.5). Theorem 4.2. Cthrd (Sn) = (−∞, C) for some C = C(n, d), which increases with d and decreases
with n. In particular, for d = 2, if n < 6, then C = ( arccos cos 2πn
1−cos 2πn
)2 ; if n = 6, then C = 0; if
n > 6, then C = − (
2 arccosh 12 sin πn
)2 .
The result is illustrated in Figure 6 (right). Note that zero-one loss can be noisy, especially on small graphs, since it is threshold-based, i.e., discrete.
4.3.2 TREE Tb WITH BRANCHING FACTOR b
We consider a tree Tb, b ≥ 2. For symmetry, assume that the first node has b+ 1 children, while all other nodes have a parent and b children. Also, for Ollivier, Forman and threshold-based curvatures, we assume that the depth of Tb is infinite. In other cases, our statements hold for any finite tree T .
Ollivier curvature We can use Equation 6 and get, for any edge, κTb(u, v) = −2 (
1− 1b+1 − 1 b+1 ) = −2 + 4b+1 . So, κ(Tb) = −2 + 4 b+1 , which is negative.
Forman curvature It is easy to see that we have F (Tb) = F̂ (Tb) = 4− 2(b+ 1) = 2(1− b).
Average sectional curvature In contrast to Ollivier and Forman curvatures, heuristic sectional curvature is global, i.e., it depends on the whole graph, which has to be finite. Note that for any tree, to compute sectional curvature, we average 0 and -1. As a result, for any tree T we have ξ(T ) ∈ [−1, 0] (Gu et al., 2019).
Distortion-based curvature On the one hand, our result for Sn implies that if a graph contains S3, then it cannot be embedded with zero distortion in any space. One the other hand, Sarkar (2011) proves that if we scale all edges by a sufficiently large factor τ , then the obtained tree can be embedded to the hyperbolic plane with distortion at most 1 + ε with arbitrary small ε. Note that multiplying graph edges by τ is equivalent to changing curvature from 1 to τ2. As a result, Sarkar (2011) proves that we can achieve an arbitrary small distortion if c→ −∞. Hence,Cdistd (T ) = −∞ for any T .
Threshold-based curvature We prove the following theorem (see Appendix B.6). Theorem 4.3. Cthrd (Tb) = (−∞, C) for some C = C(b, d), which increases with d and decreases
with b. The following lower bound holds: C(b, 2) ≥ (
2 log b 2 arccosh cosh 1
cosh 1/2 −1
)2 .
Actually, the bound above holds for any tree whose branching is bounded by b. Interestingly, while it is often claimed that trees are intrinsically hyperbolic, to the best of our knowledge, we are the first to formally prove that trees can be perfectly embedded in a hyperbolic plane of some curvature.
4.3.3 COMPLETE GRAPH Kn
Ollivier curvature For any two nodes u and v, it follows from Example 1 in (Jost & Liu, 2014) that κKn(v, u) = n−2 n−1 . Thus, κ(Kn) = n−2 n−1 and it tends to 1 as n→∞.
Forman curvature Simple computations yield: F (Kn) = 6− 2n, F̂ (Kn) = n, i.e., we get either highly positive or highly negative value.
Average sectional curvature It is easy to compute that ξ(Kn) = 18 .
Distortion-based curvature The following theorem analyzes Cdistd (Kn) if d = n − 2 (see Appendix B.4 for the proof).
Theorem 4.4. Cdistn−2(Kn) = { −∞, 4 ( arcsin √ n
2(n−1)
)2} .
Note that the optimal curvature −∞ appears here since embedding of a complete graph can be reduced to embedding of a weighted star. This theorem is illustrated in Figure 2. For n = 4, d = 2 we expect to see the minimum at about 3.65, for n = 12, d = 2 we expect 2.76, which is indeed the case. For other parameters, we do not have theoretical results, however we see sudden drops in positive curvature. Finally, as expected, distortion decreases as curvature becomes small.
Threshold-based curvature Cthrd (Kn) = R, since we can embed any complete graph perfectly by mapping all nodes to one point.
4.3.4 CYCLE GRAPH Cn
We consider a cycle Cn with n ≥ 4.
Ollivier curvature Let v ∼ u be two neighbors. Then it is easy to see that WG1 (mu,mv) = 1 and hence κG(u, v) = 0. Thus, κ(Cn) = 0.
Forman curvature Similarly, it is easy to see that F (Cn) = F̂ (Cn) = 0.
Average sectional curvature If n is even, then ξCn(v; b, c; a) = 0 for all points except the one diametrically opposite to v for which we have ξCn(v; b, c; a) = 1. If n is odd, then for two points we have ξCn(v; b, c; a) = n 2(n−1) . As a result, ξ(Cn) = 1 n−3 for even n and ξ(Cn) = n (n−1)(n−3) for odd n. Distortion-based curvature Here we have that Cdistd (Cn) = ( 2π n )2 . Indeed, if we consider any three consequent nodes, then the middle one should lie on the geodetic between the other two. So, they all lie on a great circle (of length n) from which the result follows. In particular, Cdistd (C5) ≈ 1.58, Cdistd (C100) ≈ 0.004, which is illustrated in Figure 3 (left).
Threshold-based curvature It is easy to see that Cthrd (Cn) = (−∞, C) with some C > 0, which decreases with n and increases with d (see Figure 3, right). A simple lower bound for C is C ≥ ( 4π n )2 , since for such curvature we can embed all nodes into a great circle with distances 1/2 between the closest ones.
4.3.5 COMPLETE BIPARTITE GRAPH Kl,m
W.l.o.g. we assume that l ≥ m ≥ 2 (the remaining cases are stars and are already considered).
Ollivier curvature We prove the following lemma (the proof is in Appendix B.1). Lemma 4.5. κ(Kl,m) = 0.
Forman curvature F (Kl,m) = F̂ (Kl,m) = 4− l −m.
Average sectional curvature The following lemma holds (see Appendix B.2).
Lemma 4.6. ξ(Kl,m) = −(l−m) 2+m+l−2 (m+l−2)(l+m−3) . In particular, if m = l we get ξ(Kl,m) = 1 2m−3 .
This lemma implies that for balanced complete bipartite graphs ξ(Kl,m) is positive, but tends to zero as the graph grows.
Distortion-based curvature Figure 4 (left) shows the empirical behavior of distortion depending on curvature. We observe that for all graphs optimal curvature (for the considered range) is between 2 and 2.5, where distortion has a drop. The following proposition gives an intuition about why one could expect this.
Proposition 4.7. For any d, Cdistd (K2,2) = ( π 2 )2 ≈ 2.47 and K2,2 is the only complete bipartite graph (with at least two nodes in each part) for which zero distortion is achievable.
Indeed, the result for K2,2 follows from the corresponding result on cycle C4. Moreover, if for Kl,m we have l ≥ 3 and m ≥ 2, then for any two nodes in the part of size l there are at least 2 different geodesics of length 2 between them. Therefore, all such pairs lie at opposite poles of the hypersphere, which is impossible since l ≥ 3.
Threshold-based curvature Threshold-based embeddings to Euclidean spaces are well studied. In particular, it is know that for any graph G(V,E) a perfect threshold embedding exists for some d ≤ |V | (Maehara, 1984). However, undirected bipartite graphs are hard to embed in Euclidean space: the bound d = O(n) is known (Maehara, 1984). We empirically observe that they are similarly hard to embed to both spherical and hyperbolic spaces, as shown in Figure 4 (right). Empirically, these graphs are insensitive to curvature (given that it is not too large).

heading: 4.4 VOLUME-BASED APPROXIMATION
text: Let us propose a new heuristic curvature estimator which is motivated by the intuition obtained in the previous section as well as by extensive literature arguing that the most important feature of a hyperbolic space is the fact that it has “more volume” in the neighborhood. Therefore, the natural idea is to estimate the volume we need for embedding nodes that are at distance at most k from a given one and then compute the curvature needed to get such volume. We compare the number of nodes at distance exactly k from a node (discounted using the number of edges between them) with the area of a hypersphere of radius k in a space of curvature c. The detailed description of the procedure is given in Appendix D. A nice feature of the proposed estimator is that it depends on dimension. Moreover, this dependence is natural: when d becomes larger, curvature becomes smaller in absolute value. As we show in the experiments on various datasets, a similar property is observed for the optimal curvature. Also, it turns out that for a given dimension the new estimator is able to distinguish well between negatively curved and neutral networks. However, despite the potential of this new estimator, the problem of proper global curvature estimation is still wide open.

heading: 5 EXPERIMENTS
text: In this section, we compare all discussed curvature estimators empirically. Our experiments are based on a publicly available implementation of graph embedding by Gu et al. (2019).6 The main advantage of this algorithm is that it works for any curvature: negative, positive or zero. We modified the implementation for our task: in particular, we added a regime responsible for minimizing
6https://github.com/HazyResearch/hyperbolics
threshold-based loss functions. The detailed description of our experimental setup is given in Appendix E.3, the datasets and their properties are listed in Appendix E.1.
The results of the comparison for distortion and zero-one loss are presented in Tables 1 and 2, respectively.7 We also added a method based on the gradient descent, proposed by Gu et al. (2019). This method is used here only as an illustration, since our aim is to compare estimators which do not do actual embedding. Also, the gradient descent algorithm uses the best space based on the value of the loss function, while all other curvature estimators do not use such information. We marked in bold both the global winner and the winner among all curvatures except the gradient descent one. The main goal of this experiment is to show that all known curvatures (Ollivier, Forman and average sectional) have unstable performance and even gradient descent method is not always the best (in both tables). Another important conclusion is that the optimal curvature depends on both dimension and loss function. We show more evidence for that in our extensive analysis in Appendix E.5, where we consider more datasets and more threshold-based loss functions. The experiments also confirm that networks which seems to be negatively curved (for some small dimension) become more neutral as dimensionality grows
In our experiments with the proposed volume-based estimator (see Appendix E.6), we noticed that it is able to predict well whether the hyperbolic space is needed for an embedding or Euclidean space is enough. However, the magnitude for the predicted curvature can be not optimal. Volume-based estimator also predicts that for large dimensions Euclidean space is often a good choice.

heading: 6 CONCLUSION
text: In this paper, we introduced a concept of global graph curvature motivated by the practical task of embedding graphs. This curvature depends on the loss function and dimension of a space. To get an intuition about how global graph curvature behaves, we theoretically and empirically analyzed it for several simple graphs. We compared (theoretically and empirically) the global graph curvature and several approximations based on well-known local graph curvatures and showed that they essentially differ. We demonstrated that dimensionality and the choice of a loss function fundamentally affect the global curvature and, in particular, when dimension is larger the optimal curvature usually becomes less negative, which agrees with our theoretical analysis. We also proposed a simple dimension-specific estimator which decides whether it is reasonable to embed into a negatively curved space. Our work shows that the problem of finding the rights space for graph embedding is interesting and non-trivial and we hope our results will encourage further research on global graph curvature.
7Dimension 10 is not included for zero-one loss if for all curvatures a perfect embedding is possible.

heading: A GEOMETRICAL PROPERTIES OF SPACES OF CONSTANT CURVATURE
text: In this section, we recall some useful equalities which will be used throughout the proofs.
In all proofs, we use notation R, where R = 1√ c in spherical space (corresponds to the radius of a sphere) and in the hyperbolic case (c < 0)R = 1√−c can be considered as a scaling factor compared to the space of curvature 1.
Law of cosines Let us consider a triangle with angles A,B,C and the lengths of opposite sides a, b, c, respectively.
In Euclidean, space we have: c2 = a2 + b2 − 2 a b cosC .
In spherical space, the first law of cosines is:
cos c
R = cos
a R cos b R + sin a R sin b R cosC ,
and the second law of cosines is:
cosC = − cosA cosB + sinA sinB cos c R .
In hyperbolic space, we have
cosh c
R = cosh
a R cosh b R − sinh a R sinh b R cosC .

heading: Equilateral triangle
text: The following equalities follow from the corresponding laws of cosines, assuming that all sides (and angles) are equal.
For hyperbolic space:
cosh a
2R =
1
2 sin A2 . (7)
For spherical space:
cos a
R =
cosA
1− cosA . (8)
Area and volume of hypersphere Let Sd(r) and Vd(r) denote area of a hypersphere and volume of a ball of radius r in d-dimensional space.
In euclidean space, Sd(r) = dCd r d−1,
Vd(r) = Cd r d,
where
Cd = πd/2
Γ(d2 + 1) .
In spherical space, sphere of radius r is isometric to Euclidean sphere of radius R sin rR . Therefore, the area is
Sd(r) = dCd
( R sin r
R
)d−1 ,
Vd(r) = dCdR d ∫ r 0 ( sin x R )d−1 dx.
Similarly, in hyperbolic space,
Sd(r) = dCd
( R sinh r
R
)d−1 ,
Vd(r) = dCdR d ∫ r 0 ( sinh x R )d−1 dx.

heading: B CURVATURE OF SIMPLE GRAPHS

heading: B.1 PROOF OF LEMMA 4.5 (OLLIVIER CURVATURE FOR BIPARTITE GRAPHS)
text: Let use denote the node sets in Kl,m by U := {u1, . . . , ul} and V := {v1, . . . , vm}. We will prove that for any edge (u, v), WKl,m1 (mu,mv) = 1, which then implies that κ(Kl,m) = 0. For this we use the dual representation for the Wasserstein distance, see Ollivier (2009) for more details. This states that on the one hand
WG1 (mu,mv) = inf ρ ∑ v′∼v ∑ u′∼u dG(v ′, u′)ρ(v′, u′),
where the infimum is taken over all joint probability measures on the product of the neighborhoods of v and u, while on the other hand
WG1 (mu,mv) = sup f
( 1
deg(v) ∑ v′∼v f(v′)− 1 deg(u) ∑ u′∼u f(u′)
) ,
where the supremum is taken over all 1-Lipschitz functions, i.e |f(u)− f(v)| ≤ dG(u, v). Note that for any u ∈ U, v ∈ V the joint neighborhood is V ×U . First we establish an upper bound by considering the product joint probability density on V × U
ρ(x, y) = 1
ml .
It then follows that
W Kl,m 1 (mu,mv) ≤ m∑ i=1 l∑ j=1 dG(vi, uj)ρ(vi, uj) = 1.
For the lower bound we define the function
f(z) = { 2 if z ∈ V, 1 if z ∈ U.
Observe that if u ∈ U and v ∈ V then |f(u) − f(z)| = 1 = dG(u, v). On the other hand, if u, u′ ∈ U then |f(u) − f(u′)| = 0 ≤ 2 = dG(u, u′) and similar for v, v′ ∈ V . Thus we conclude that f is 1-Lipschitz. It now follows that
W Kl,m 1 (mu,mv) ≥
1
m m∑ i=1 f(vi)− 1 l l∑ j=1 f(uj) = 1,
which completes the proof.

heading: B.2 PROOF OF LEMMA 4.6 (AVERAGE SECTIONAL CURVATURE FOR BIPARTITE GRAPHS)
text: If v and a are in the same part of the bipartite graph, then ξKl,m(v; b, c; a) = 1, otherwise ξKl,m(v; b, c; a) = −1. Therefore, if a belongs to the part of size l, sectional curvature is ξKl,m(v; b, c) = l−m+1 l+m−3 , otherwise it is ξKl,m(v; b, c) = m−l+1 l+m−3 . As a result, by averaging over all triplets, we get
ξ(Kl,m) = 1 l ( m 2 ) +m ( l 2 ) (l(m 2 ) l −m+ 1 l +m− 3 +m ( l 2 ) m− l + 1 l +m− 3 ) = −(l −m)2 +m+ l − 2 (m+ l − 2)(l +m− 3) .

heading: B.3 PROOF OF THEOREM 4.1 (DISTORTION-BASED CURVATURE FOR STARS)
text: The general idea is the following: we take any curvature c and prove a lower bound on distortion (for any given dimension d). Then, we obtain an upper bound on optimal distortion which tends to zero as c→ −∞, which gives the claimed result Cdistd (Sn) = −∞.
First, let us analyze the lower bound on distortion. Recall that distortion of a graph is the average distortion over all pairs of nodes. Let v be the central node and v1, . . . , vn (n ≥ 3) be its neighbors. Then, for any embedding f , we have
D(Sn) = 1( n+1 2
) ∑
vi |d(f(v), f(vi))− 1|+ ∑ vi 6=vj |d(f(vi), f(vj))− 2| 2  =
1( n+1 2 ) ∑ 1≤i1<i2<i3≤n  ∑ 1≤j≤3 |d(f(vij ), f(v))− 1|( n−1 2 ) + ∑ 1≤j<k≤3 |d(f(vij ), f(vik))− 2| 2(n− 2)  . Let Dmin be the minimum value of the following weighted distortion of a star with 3 leaves:
Dmin = min f ∑ 1≤j≤3 |d(f(vj), f(v))− 1| (n− 1)/4 + ∑ 1≤j<k≤3 |d(f(vj), f(vk))− 2|,
then
D(Sn) ≥ ( n 3 ) 2(n− 2) ( n+1 2 )Dmin = (n− 1)Dmin 6(n+ 1) . (9)
Hence, it remains to find a lower bound on Dmin, i.e., a lower bound for a weighted distortion of S3 with central node v and three leaves v1, v2, v3. If we consider three angles at the node v, then at least one of them is α ≤ 2π/3, so we can get a lower bound by only considering this triangle, which is, w.l.o.g., formed by v, v1, v2.
Dmin ≥ |d(f(v1), f(v2))− 2|+ |d(f(v1), f(v))− 1|+ |d(f(v2), f(v))− 1|
(n− 1)/2 .
Denote d(f(v1), f(v)) = x = 1 + ε, d(f(v2), f(v)) = y = 1 + δ, d(f(v1), f(v2)) = z = 2 + ε+ δ−ϕ with some ε, δ and some ϕ > 0 (from triangle inequality). Assume that |ε| < 1/2 and |δ| < 1/2 (otherwise the lower bound is trivial). Now we use the law of cosines to get a lower bound on ϕ. We consider Euclidean and hyperbolic spaces separately and note that the bound obtained in Euclidean space also holds in spherical spaces (with any c).
In Euclidean space, using triangle inequality, we get ϕ = x + y − z > 0. So, in Euclidean and spherical spaces ϕ is bounded below by a constant.
In hyperbolic space the law of cosines gives (recall that R = 1√−c ):
cosh z
R = cosh
x R cosh y R − sinh x R sinh y R cosα,
from which, using cosh(x+ y) = coshx cosh y + sinhx sinh y, we get
cosh x+ y R − cosh z R = sinh x R sinh y R (1 + cosα).
If R→∞, then, similarly to Euclidean case, we get ϕ = x+ y − z = Ω(1).
On the other hand, if R → 0, we get ϕ = Ω(R). Note that Dmin ≥ |z − 2| + |x−1|+|y−1|(n−1)/2 = |ε + δ − ϕ| + |ε|+|δ|(n−1)/2 . This gives us a lower bound Dmin = Ω(1/n) in spherical and Euclidean
spaces and Dmin = Ω(min(R, 1)/n) = Ω (
1
nmax( √ −c,1)
) in hyperbolic space. From this and
Equation 9 the bound on D(Sn) follows.
Now, let us get an upper bound on optimal distortion Dopt(Sn). To do this, we explicitly construct an embedding with sufficiently low distortion D(Sn).
Let v be the central node, then we spread all other nodes uniformly on a 2-dimensional circle of radius 1 centred at v. The smallest angle between two points is 2π/n. Therefore, from the law of cosines, the distance between leaves is at least k with
cosh k
R = 1 +
( 1− cos 2π
n
) sinh2 1
R .
Note that for any two leaves vi and vj we have that d(f(vi), f(vj)) ≤ 2. In particular, the closer two leaves are, the greater the difference 2 − d(f(vi), f(vj)) is. Hence, the distance between adjacent leaves is the worst case and thus Dopt(Sn) can be upper bounded as
Dopt(Sn) ≤ ( n 2 ) 2 ( n+1 2 ) (2−R · arccosh((1− cos 2π n ) sinh2 1 R + 1 )) =
(n− 1) 2(n+ 1)
( 2−R · arccosh (( 1− cos 2π
n
) sinh2 1
R + 1 )) Note that 1−cos 2πn = Θ ( 1 n ) and sinh2 ( 1 R ) = Θ ( e2/R ) . Then, arccosh ( Θ ( 1 ne 2/R ) + 1 )
behaves as √
2e2/R/n if 2/R log n and as 2R − log n if 2/R log n. Therefore, we get
Dopt(Sn) = O (R log n) = O ( log n√ −c ) .

heading: B.4 PROOF OF THEOREM 4.4 (DISTORTION-BASED CURVATURE FOR COMPLETE GRAPHS)
text: If d = n− 2, then we are given a (n− 1)-simplex, which can be embedded into n− 2-dimensional spherical space. Indeed, the radius of circumscribed hypersphere for the (n− 1)-simplex with side length a is known to be R = a √ n−1 2n . Since we want the spherical distance between all points to be equal to one, we need to choose a accordingly:
sin α
2 =
a
2R for α =
1 R .
Here α corresponds to the angle giving the arc length 1, while the condition on sin α2 relates α and a since α is the angle in a triangle with side lengths α,R,R. This implies that
2R arcsin a
2R = 1,
and solving this equation for a yields
a =
√ 2n
(n− 1) 1 2 arcsin √
n 2(n−1)
.
Plugging this back into the formula for the radius R we obtain
R = 1 2 arcsin √
n 2(n−1)
,
so that we have
Cdistn−2(Kn) = 4
( arcsin √ n
2(n− 1)
)2 .
Finally, let us show that if c → −∞, then optimal distortion Dopt(Kn) → 0. This result follows from the fact that Dopt(Sn)→ 0, because to embed a clique, it is sufficient to embed a star on n+ 1 node with edge lengths 1/2 and then remove the central node.

heading: B.5 PROOF OF THEOREM 4.2 (THRESHOLD-BASED CURVATURE FOR STAR)
text: We show below that for any n, any dimension d and some curvature c there exists a perfect embedding. Therefore Cdistd (Sn) consists of curvatures for which such perfect embedding exists.
First, let us note that if there exists a perfect embedding f for some curvature c, then there exists a perfect embedding for any curvature c′ < c. Indeed, w.l.o.g., we assume that the central node v is mapped to the origin of a hyperspherical coordinate system and other points v1, . . . , vn can be described by their radii and angles. We know that the distance between v and any vi is at most 1 and the distance between any pair vi, vj is larger than one. Now we change curvature to c′ < c and
keep hyperspherical coordinates the same. Then the distance between v and any vi does not change, while the distance between nodes vi, vj increases.
Now, it is easy to see that C increases with d: if there exists an embedding to some dimension d, then, obviously, the same embedding works for d′ > d. Further, C decreases with n since if there exists embedding of Sn, then we can easily construct an embedding of Sn′ for n′ < n by removing some nodes.
Now, let us construct a perfect embedding of Sn and estimate the required curvature. Recall that in a perfect embedding all leaves have to be inside the ball of radius 1 around the central node v and also the distance between any two leaves has to be larger than one.
It is easy to see that if we managed to spread n points inside the ball of radius 1 with distances more than 1 between them, then we can move each point along the radius up to distance 1 from v preserving this property. Therefore, it is sufficient to spread all points on a hypersphere.
Let us first consider d = 2. In this case we can find an explicit analytic expression for C. This will be an upper bound for any d > 2.
First, assume that n > 6. In this case we have to consider only hyperbolic space, since n neighbors would not fit to a circle of radius 1 in neither spherical or Euclidean spaces.
We will find such largest curvature C which allows to have distance exactly 1 between the closest leaves. In this case we cannot embed Sn in a space of curvature C, but can embed in a space of any smaller curvature. We use Equation 7 and let α = 2πn :
cosh 1
2R =
1
2 sin α2 ,
R = 1
2 arccosh 12 sin α2 ,
C = − ( 2 arccosh 1
2 sin α2
)2 .
Note that if n is large, then sin α2 = sin π n−1 ∼ π n−1 . Then, arccosh 1 2 sin α2 ∼ arccoshn−12π ∼ log n, so we get C ∼ −4 log2 n. Now, let us consider n ≤ 6. Obviously, for n = 6 we have C = 0. If n < 6, then C > 0. We use Equation 8:
cos 1
R =
cosα
1− cosα ,
C = ( arccos cosα
1− cosα
)2 .

heading: B.6 PROOF OF THEOREM 4.3 (THRESHOLD-BASED CURVATURE FOR TREES)
text: As for Sn, we prove that for Tb a perfect embedding exists for d = 2 and some curvature c. Then, similarly to the previous section, it is clear that C increases with b and decreases with n.
For the lower bound on C, we have to guarantee that an embedding exists. For this, we provide the following construction (see Figure 5 for an illustration). (Below we assume that the curvature is large enough for our construction to work, then we estimate the required curvature.) First, we take the node v and consider a circle of radius 1 around this node. We spread b+ 1 neighbors uniformly around this node. For our construction to work, we need all distances between these nodes to be larger than 1. Now, at some step of the algorithm, assume that we have all nodes at level l placed at some circle centered at v and all distances between the nodes at level l are larger than 1. Our aim is then to find positions for all nodes at level l + 1.
Let us take any node at l-th level. Consider two points ul and ur on the same circle at distance 1 from the node u to the left and to the right, respectively. Let u, ul, zl and u, ur, zr form equilateral
triangles (with sides equal to 1). Then we let the points at l + 1-th level to be spread on the circle centred at v and passing through zl and zr. The children of u (u1, . . . , ub) will be placed on the circular arc between zl and zr. As usual, we want ui and ui+1 to be at distance at least 1 from each other. Moreover, they have to be at distance at least 1 from children of other nodes. Also, note that placing u1, . . . , ub between zl and zr guarantees that these nodes are closer than 1 to their parent node u but at the same time at a distance larger than 1 from all other nodes at l-th level. Also, all points at l-th level are far enough from points at l + 2-th level.
It remains to find a maximum curvature such that the required conditions are satisfied. Let r and r′ be radii of circles at l-th and l + 1-th levels and let 2α = ∠ulvu. We know (the law of cosines and cos 2α = 1− 2 sin2 α) that
cosh 1
R = 1 + 2 sinh
r R sin2 α . (10)
And the only condition we need for the whole procedure to work is that we have enough space on the circular arc for placing b nodes there:
cosh 1 R ≤ 1 + 2 sinh r
′
R sin2
α b .
Now we note that sin2 αb ≥ sin2 α b2 for all b ≥ 1. Therefore, it is sufficient to have
cosh 1 R ≤ 1 + 2 sinh r
′
R · sin
2 α
b2 . (11)
Combining Equation 10 and Equation 11, we obtain:
sinh r′
R ≥ b2 · sinh r R .
To achieve this, it is sufficient to have:
r′ − r R ≥ 2 log b,
R ≤ r ′ − r
2 log b .
It remains to find the lower bound for r′ − r and it is easy to see that r′ − r decreases with r. Therefore, it is sufficient to consider only the second step of the construction procedure, when we move from the circle of radius 1 to the next one. In this case, r = 1 and
r′ = 2 arccosh cosh 1
cosh 1/2 .
So, we have
−C = 1 R2 ≤
( 2 log b
2 arccosh cosh 1cosh 1/2 − 1
)2 .

heading: C COMBINATIONS OF SIMPLE GRAPHS
text: In this section, in order to get additional intuition, we illustrate how combining several simple subgraphs may affect the optimal curvature. We choose distortion for this illustrative example, since for this loss we theoretically obtained non-trivial results: for some simple graphs the optimal curvature is negative, while for other it is positive.
Indeed, for trees (and, in particular, stars) the optimal curvature is minus infinity and for cycles the optimal curvature is positive. Our intuition is that combining stars and cycles in one graph would give optimal curvature located between the curvatures of these simple graph.
Indeed, we observe such expected behavior for two illustrative examples shown in Figures 6 and 7. In Figure 6 we take a cycle of length 10 and iteratively add edges to one of its nodes, i.e., we create a star on one node. In Figure 7 we take the same cycle and add small stars sequentially to several of its nodes: in the left figure we just add one dangling edge for each node (i.e., create a star subgraph on 4 nodes), in the right figure we add two edges. In all cases, the optimal curvature drifts from a positive one for a cycle to negative values. This drift is more pronounced In Figure 6, where we create just one (relatively) large star.
D VOLUME-BASED CURVATURE APPROXIMATION
In this section, we describe the proposed curvature approximation. An input parameter of this estimator is the maximum neighborhood size kmax (we fix kmax = 3 in the experiments). We take a node v and for any k ≤ kmax we compute the number of nodes Nk(v) at distance exactly k from it. Then, we discount this value using the number of edges between the nodes. This captures our intuition that we need enough space to place the neighbors, but the connected neighbors are not required to be far away from each other. Formally, let Ek(v) be the number of non-edges between the pairs of nodes at distance k. Then, we say that N ′k(v) is such that ( N ′k(v) 2 ) = Ek(v). Finally, we compute the curvature ck(v) such that the area of a hypersphere or radius k is equal to N ′k(v).
And our estimate for v is c(v) = mink≤kmax ck(v) (the worst-case curvature). To get a curvature of the whole graph, we take a median of all ck(v). (Similarly to other curvature estimators, one can consider a subsample of nodes instead of the whole node set to speed up the computation).

heading: E EXPERIMENTS

heading: E.1 DATASETS
text: Datasets used in our experiments are listed in Table 3. In all cases, we take only the giant connected component (numbers of nodes and edges in Table 3 correspond to already filtered dataset). Synthetic datasets are described in Section 4.3. The dataset T3,6 is a tree with branching factor 3 and depth 6.

heading: E.2 THRESHOLD-BASED LOSS FUNCTIONS
text: While our theoretical results in Section 4 hold for any threshold-based loss function, we noticed that for less trivial datasets, where the perfect embedding is impossible, the choice of the loss function becomes important. In most of the experiments we use zero-one loss function:
1( n 2 ) ∑ i,j I[vi ∼ vj ] · I[d(f(vi)f(vj)) > 1] + (1− I[vi ∼ vj ]) · I[d(f(vi), f(vj)) ≤ 1]
which essentially measures how well the values I[d(f(vi)f(vj)) > 1] approximate I[vi ∼ vj ]. However, due to the fact that the real-world graphs are usually sparse, optimizing zero-one loss may lead to algorithms biased towards sparse embeddings. A standard solution to this is to consider balanced accuracy instead of accuracy, which leads to balanced zero-one loss:∑
i,j I[vi ∼ vj ] · I[d(f(vi)f(vj)) > 1] 2 ∑ i,j I[vi ∼ vj ] +
∑ i,j(1− I[vi ∼ vj ]) · I[d(f(vi), f(vj)) ≤ 1]
2 ∑ i,j(1− I[vi ∼ vj ])
.
The recent study by Gösgens et al. (2019) analyses the problem of bias discussed above in detail. It formally defines and analyzes a constant baseline requirement and shows that it is satisfied, in particular, by Pearson correlation coefficient between the vectors consisting of I[vi ∼ vj ] and I[d(f(vi)f(vj)) > 1]. So, we add the corresponding Pearson loss (one minus correlation coefficient) to our experiments (see (Gösgens et al., 2019)).

heading: E.3 EXPERIMENTAL SETUP
text: Our experiments are based on a publicly available implementation of graph embedding by Gu et al. (2019).8 The main advantage of this algorithm is that it works for any curvature: negative, positive or zero.
8https://github.com/HazyResearch/hyperbolics
We modified the implementation for our task: in particular, we added a regime responsible for minimizing threshold-based loss functions. E.g., zero-one loss is proportional to∑
i,j
I[vi ∼ vj ] · I[d(f(vi)f(vj)) > 1] + (1− I[vi ∼ vj ]) · I[d(f(vi), f(vj)) ≤ 1].
This function is not differentiable, so we replace it by gradient descent friendly function which we call ReLuLoss:∑ i,j I[vi ∼ vj ]·ReLu(d(f(vi), f(vj))−(1−ε))+(1−I[vi ∼ vj ])·ReLu((1+ε)−d(f(vi), f(vj)),
where ReLu(x) = max(0, x), ε = 0.001. In our experiments we observed that such loss function outperforms other analogues (e.g., MSE and sigmoid-based smoothing) since it speeds up the convergence. To adapt to various threshold-based loss functions, we also reserve several iterations to gradient steps based on the corresponding sigmoid-based smoothing.
Note that in experiments we use only the more advanced Forman curvature F̂ (G). For computing Ollivier and Forman curvature we use the open source package by Ni et al. (2015).9
For the embedding algorithm, in all experiments we fix epochs = 1000 and we also try several learning rates (usually from 0.01 to 104). We noticed that learning rate significantly affect the performance of the learning algorithm and also the optimal learning rate is usually smaller for smaller datasets and it is larger for spaces of negative curvature. We also use the option use adagrad = True since we noticed that it inproves the embedding into Euclidean spaces (otherwise there is a peak in distortion at c = 0).
Let us emphasize that in our experiments we do not care about overfitting, because we do not analyze the embedding algorithm, our aim is to find a curvature which minimizes loss function. (It can be also thought of as though we focus on graph reconstruction task).
9https://github.com/saibalmars/GraphRicciCurvature
To plot all the figures we try curvatures in some range (usually between -2 and 1) with step size 0.1.
Our code is publicly available.10

heading: E.4 COMPARISON OF CURVATURES ON SYNTHETIC DATASETS
text: See the results in Tables 4 and 5.

heading: E.5 EFFECT OF DIMENSION AND LOSS FUNCTION
text: In this section, we visualize the dependence of the loss function on curvature (see Figures 8-18). In particular, we demonstrate that the optimal curvature significantly depends on both loss function and dimension. More precisely, while our theoretical results hold for any threshold-based loss function, for less trivial graphs the optimal curvature depends on the particular choice.11
The obtained results support our intuition (based on theoretical results) that while hyperbolic space helps in many cases for small dimensions, it becomes less pronounced in larger dimensions. This is most clearly seen for distortion loss (see, e.g., Karate club, Football, CSPhDs, Euroroad, EuroSiS, Power).

heading: E.6 EMPIRICAL ANALYSIS OF VOLUME-BASED CURVATURE
text: As discussed in the previous section, optimizing distortion leads to more stable results than threshold-based losses, so we focus on this loss here. It turns out that the proposed volume-based estimator is able to reflect well whether it is reasonable to embed a network to a hyperbolic space for a given loss function if we care about distortion. Table 6 shows the estimated values of a curvature.12
10https://drive.google.com/open?id=12i5LD6yTyFRDrgkMJEencDAI0Au6Isrn 11We note that the curves corresponding to threshold-based losses are noisy, especially for small datasets, since such loss functions are discrete and multimodal, so they are harder to optimize. To smooth the results, we added several tricks to the optimizer and also choose the optimum embedding based on several random restarts of the algorithm. Although the results are still noisy, the general trends are usually clearly seen.
12The value 0.1 appears due to a technical reason: in spherical space of large curvature there can be no points at distance k, so we limit considered curvatures.
One can see that for d = 2 in many cases significantly negative curvature is predicted which is indeed confirmed by our experiments, shown in Figures 8-18 (distortion loss). Non-negative curvature is predicted for Chicago, CSPhDs, Euroroad and Power and indeed for these datasets the optimal curvature is close to zero. In contrast, for d = 10 negative curvature is never predicted, which agrees with the experiment well. So, in these cases it is not reasonable to embed networks to a hyperbolic space.

Review summaries:
This paper is about curvature as a general concept for embeddings and ML applications. The origin of this idea is that various researchers have studied embedding graphs into non-Euclidean spaces. Euclidean space is flat (it has zero curvature), while non-Euclidean spaces have different curvature; e.g., hyperbolic space has a constant negative curvature. It was noted that trees don't embed well into flat space, while they embed arbitrarily well into hyperbolic space.