Title: GLOBAL GRAPH CURVATURE

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.
Under review as a conference paper at ICLR 2020 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.
Graph embeddings For an unweighted connected graph G = (V, E) equipped with the shortest path distance metric d G , 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:
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 graph G in the following way: v and u are connected in G 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).

1. INTRODUCTION:

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-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.

3. LOCAL GRAPH CURVATURES:

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 graph G we consider the shortest path metric on G, denoted by d G , and let W G 1 denote the Wasserstein metric with respect to the metric space (G, d G ). Furthermore, for each node v we let m v denote the uniform probability measure on the neighbors of v, i.e., m v (u) = 1u∼v deg (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

EQUATION

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:

EQUATION

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

EQUATION

where ∆ uv is the number of triangles that contain the edge (u, v).

Based on the definitions, both Forman curvatures, especially F G (u, v), are expected to often be highly negative. Indeed, this is what we observe in Sections 4.3 and 5.

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

EQUATION

)

This resembles the formula above with m = v and the normalization constant 2d G (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

4. GLOBAL GRAPH CURVATURE:

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.

4.1. DEFINITION:

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 L opt (G, d, c) be the optimal loss for given d and c: L opt (G, d, c) = min f L(f ). Then, we define d-dimensional curvature of G in the following way:

EQUATION

Note that there may be several values of curvature c delivering the minimum of L opt (G, d, c) , in this case we say that C L d (G) consists of all such points.5 Below we analyze global curvatures based on distortion (C dist d (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 L opt (G, d, c) reaches its minimum on "perfect" embeddings, where we precisely reconstruct the graph G.

4.2. APPROXIMATIONS:

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 F G (u, v), F (G) = 1 |E| u∼v FG (u, v).

Average sectional curvature Let P 3 denote the number of paths of length 3 in G, then ξ(G) = 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.

1 P3 v∈V b<c:b,c∈N (v) ξ G (v; b, c).

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.

4.3. THEORETICAL ANALYSIS OF GLOBAL CURVATURE AND ITS APPROXIMATIONS:

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 S n:

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 S n 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

EQUATION

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 κ(S n ) = 0 and stars are not negatively curved according to Ollivier curvature.

Forman curvature If follows from Equation 2 and Equation 3 that F (S n ) = F (S n ) = 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 ξ(S n ) = -1.

Distortion-based curvature We prove the following theorem (the proof is in Appendix B.3). 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 S 3 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 S 3 as an induced subgraph. On the other hand, if c → -∞, we can spread all leaves of S n 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. C thr d (S n ) = (-∞, 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 1 2 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 T b WITH BRANCHING FACTOR b:

We consider a tree T b , 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 T b 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,

κ T b (u, v) = -2 1 -1 b+1 -1 b+1 = -2 + 4 b+1 . So, κ(T b ) = -2 + 4 b+1 , which is negative.

Forman curvature It is easy to see that we have

F (T b ) = F (T b ) = 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 et al., 2019) .

ξ(T ) ∈ [-1, 0] (Gu

Distortion-based curvature On the one hand, our result for S n implies that if a graph contains S 3 , 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 → -∞. 

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. 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, κ(K n ) = n-2

n-1 and it tends to 1 as n → ∞.

Forman curvature Simple computations yield:

F (K n ) = 6 -2n, F (K n ) = n, i.e.

, we get either highly positive or highly negative value.

Average sectional curvature It is easy to compute that ξ(K n ) = 1 8 .

Distortion-based curvature:

The following theorem analyzes

C dist d (K n ) if d = n -2 (see Ap- pendix B.4 for the proof). Theorem 4.4. C dist n-2 (K n ) = -∞, 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 C thr d (K n ) = R, since we can embed any complete graph perfectly by mapping all nodes to one point.

4.3.4. CYCLE GRAPH C n:

We consider a cycle C n with n ≥ 4. Ollivier curvature Let v ∼ u be two neighbors. Then it is easy to see that

W G 1 (m u , m v ) = 1 and hence κ G (u, v) = 0. Thus, κ(C n ) = 0. Forman curvature Similarly, it is easy to see that F (C n ) = F (C n ) = 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, ξ(C n ) = 1 n-3 for even n and ξ(C n ) = n (n-1)(n-3) for odd n.

Distortion-based curvature Here we have that

C dist d (C n ) = 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, C dist Ollivier curvature We prove the following lemma (the proof is in Appendix B.1). Lemma 4.5. κ(K l,m ) = 0.

Forman curvature F (K l,m ) = F (K l,m ) = 4 -l -m.

Average sectional curvature The following lemma holds (see Appendix B.2).

Lemma 4.6. ξ(K l,m ) = -(l-m) 2 +m+l-2 (m+l-2)(l+m-3) . In particular, if m = l we get ξ(K l,m ) = 1 2m-3 .

This lemma implies that for balanced complete bipartite graphs ξ(K l,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. Indeed, the result for K 2,2 follows from the corresponding result on cycle C 4 . Moreover, if for K l,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).

4.4. VOLUME-BASED APPROXIMATION:

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.

5. EXPERIMENTS:

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 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.

6. CONCLUSION:

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.

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:

c 2 = a 2 + b 2 -2 a b cos C .

In spherical space, the first law of cosines is:

cos c R = cos a R cos b R + sin a R sin b R cos C ,

and the second law of cosines is:

cos C = -cos A cos B + sin A sin B cos c R .

In hyperbolic space, we have

cosh c R = cosh a R cosh b R -sinh a R sinh b R cos C .

Equilateral triangle:

The following equalities follow from the corresponding laws of cosines, assuming that all sides (and angles) are equal.

For hyperbolic space:

EQUATION

)

For spherical space:

EQUATION

)

Area and volume of hypersphere Let S d (r) and V d (r) denote area of a hypersphere and volume of a ball of radius r in d-dimensional space.

In euclidean space,

S d (r) = d C d r d-1 , V d (r) = C d r d ,

where

C d = π d/2 Γ( d 2 + 1)

.

In spherical space, sphere of radius r is isometric to Euclidean sphere of radius R sin r R . Therefore, the area is

S d (r) = d C d R sin r R d-1 , V d (r) = d C d R d r 0 sin x R d-1 dx.

Similarly, in hyperbolic space,

S d (r) = d C d R sinh r R d-1 , V d (r) = d C d R d r 0 sinh x R d-1

dx.

B CURVATURE OF SIMPLE GRAPHS:

B.1 PROOF OF LEMMA 4.5 (OLLIVIER CURVATURE FOR BIPARTITE GRAPHS)

Let use denote the node sets in K l,m by U := {u 1 , . . . , u l } and V := {v 1 , . . . , v m }. We will prove that for any edge (u, v), W

EQUATION

(m u , m v ) = 1, which then implies that κ(K l,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

W G 1 (m u , m v ) = inf ρ v ∼v u ∼u d G (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

W G 1 (m u , m v ) = 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)| ≤ d G (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 K l,m 1 (m u , m v ) ≤ m i=1 l j=1 d G (v i , u j )ρ(v i , u j ) = 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 = d G (u, v). On the other hand, if u, u ∈ U then |f (u) -f (u )| = 0 ≤ 2 = d G (u, u

) and similar for v, v ∈ V . Thus we conclude that f is 1-Lipschitz. It now follows that

W K l,m 1 (m u , m v ) ≥ 1 m m i=1 f (v i ) - 1 l l j=1 f (u j ) = 1,

which completes the proof.

B.2 PROOF OF LEMMA 4.6 (AVERAGE SECTIONAL CURVATURE FOR BIPARTITE GRAPHS):

If v and a are in the same part of the bipartite graph, then

ξ K l,m (v; b, c; a) = 1, otherwise ξ K l,m (v; b, c; a) = -1. Therefore, if a belongs to the part of size l, sectional curvature is ξ K l,m (v; b, c) = l-m+1 l+m-3 , otherwise it is ξ K l,m (v; b, c) = m-l+1 l+m-3 .

As a result, by averaging over all triplets, we get

ξ(K l,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) .

B.3 PROOF OF THEOREM 4.1 (DISTORTION-BASED CURVATURE FOR STARS):

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

C dist d (S n ) = -∞.

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 v 1 , . . . , v n (n ≥ 3) be its neighbors.

Then, for any embedding f , we have

D(S n ) = 1 n+1 2   vi |d(f (v), f (v i )) -1| + vi =vj |d(f (v i ), f (v j )) -2| 2   = 1 n+1 2 1≤i1<i2<i3≤n   1≤j≤3 |d(f (v ij ), f (v)) -1| n-1 2 + 1≤j<k≤3 |d(f (v ij ), f (v i k )) -2| 2(n -2)   .

Let D min be the minimum value of the following weighted distortion of a star with 3 leaves:

EQUATION

Hence, it remains to find a lower bound on D min , i.e., a lower bound for a weighted distortion of S 3 with central node v and three leaves v 1 , v 2 , v 3 . 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, v 1 , v 2 .

D min ≥ |d(f (v 1 ), f (v 2 )) -2| + |d(f (v 1 ), f (v)) -1| + |d(f (v 2 ), f (v)) -1| (n -1)/2 . Denote d(f (v 1 ), f (v)) = x = 1 + ε, d(f (v 2 ), f (v)) = y = 1 + δ, d(f (v 1 ), f (v 2 )) = 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) = cosh x cosh y + sinh x 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

D min ≥ |z -2| + |x-1|+|y-1| (n-1)/2 = |ε + δ -ϕ| + |ε|+|δ| (n-1)/2

. This gives us a lower bound D min = Ω(1/n) in spherical and Euclidean spaces and

D min = Ω(min(R, 1)/n) = Ω 1 n max( √ -c,1)

in hyperbolic space. From this and Equation 9 the bound on D(S n ) follows.

Now, let us get an upper bound on optimal distortion D opt (S n ). To do this, we explicitly construct an embedding with sufficiently low distortion D(S n ).

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 sinh 2 1 R .

Note that for any two leaves v i and v j we have that d(f

(v i ), f (v j )) ≤ 2.

In particular, the closer two leaves are, the greater the difference 2 -d(f (v i ), f (v j )) is. Hence, the distance between adjacent leaves is the worst case and thus D opt (S n ) can be upper bounded as

D opt (S n ) ≤ n 2 2 n+1 2 2 -R • arccosh 1 -cos 2π n sinh 2 1 R + 1 = (n -1) 2(n + 1) 2 -R • arccosh 1 -cos 2π n sinh 2 1 R + 1

Note that 1-cos 2π n = Θ 1 n and sinh 2 1 R = Θ e 2/R . Then, arccosh Θ 1 n e 2/R + 1 behaves as 2e 2/R /n if 2/R log n and as 2 R -log n if 2/R log n. Therefore, we get

D opt (S n ) = O (R log n) = O log n √ -c .

B.4 PROOF OF THEOREM 4.4 (DISTORTION-BASED CURVATURE FOR COMPLETE GRAPHS):

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 .

Plugging this back into the formula for the radius R we obtain

R = 1 2 arcsin n 2(n-1)

, so that we have

C dist n-2 (K n ) = 4 arcsin n 2(n -1) 2 .

Finally, let us show that if c → -∞, then optimal distortion D opt (K n ) → 0. This result follows from the fact that D opt (S n ) → 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.

B.5 PROOF OF THEOREM 4.2 (THRESHOLD-BASED CURVATURE FOR STAR):

We show below that for any n, any dimension d and some curvature c there exists a perfect embedding. Therefore C dist d (S n ) 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 v 1 , . . . , v n can be described by their radii and angles. We know that the distance between v and any v i is at most 1 and the distance between any pair v i , v j is larger than one. Now we change curvature to c < c and keep hyperspherical coordinates the same. Then the distance between v and any v i does not change, while the distance between nodes v i , v j 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 S n , then we can easily construct an embedding of S n for n < n by removing some nodes. Now, let us construct a perfect embedding of S n 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 S n in a space of curvature C, but can embed in a space of any smaller curvature. We use Equation 7and let α = 2π n :

cosh 1 2R = 1 2 sin α 2 , R = 1 2 arccosh 1 2 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 ∼ arccosh n-1 2π ∼ log n, so we get C ∼ -4 log 2 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 .

B.6 PROOF OF THEOREM 4.3 (THRESHOLD-BASED CURVATURE FOR TREES):

As for S n , we prove that for T b 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 u l and u r on the same circle at distance 1 from the node u to the left and to the right, respectively. Let u, u l , z l and u, u r , z r form equilateral

м 𝑣 𝑢 𝑢 l 𝑢 r 𝑧 l 𝑧 r 𝑢 1 𝑢 2 𝑢 3 1 1 1 1 1 1

Figure 5 : Threshold-based embedding of trees 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 z l and z r . The children of u (u 1 , . . . , u b ) will be placed on the circular arc between z l and z r . As usual, we want u i and u i+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 u 1 , . . . , u b between z l and z r 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α = ∠u l vu. We know (the law of cosines and cos 2α = 1 -2 sin 2 α) that

EQUATION

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 sin 2 α b . Now we note that sin 2 α b ≥ sin 2 α b 2

for all b ≥ 1. Therefore, it is sufficient to have

EQUATION

Combining Equation 10and Equation 11, we obtain:

sinh r R ≥ b 2 • 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 R 2 ≤ 2 log b 2 arccosh cosh 1 cosh 1/2 -1 2 . 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 -2 -1.5 -1 -0.5 0 0.5 1 distortion curvature k = 0 k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 k = 9 k = 10

0.5 -2 -1.5 -1 -0.5 0 0.5 1 distortion curvature k = 0 k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 k = 9 k = 10

C COMBINATIONS OF SIMPLE GRAPHS:

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 k max (we fix k max = 3 in the experiments). We take a node v and for any k ≤ k max we compute the number of nodes N k (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 E k (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 = E k (v). Finally, we compute the curvature c k (v) such that the area of a hypersphere or radius k is equal to N k (v). (Lusseau et al., 2003) 62 159 Football (Newman & Girvan, 2004) 115 613 Political books (Newman, 2006) 105 441 Conflict (Ward et al., 2007) 127 253 Chicago (Eash et al., 1979) 822 821 CSPhDs (W. De Nooy & Batagelj, 2011) 1025 1043 Euroroad ( Šubelj & Bajec, 2011) 1039 1305 EuroSiS (Khokhar, 2015) 1272 6424 Power (Watts & Strogatz, 1998) 4941 6594 Facebook (Leskovec & Mcauley, 2012) 4039 88234

And our estimate for v is c(v) = min k≤kmax c k (v) (the worst-case curvature). To get a curvature of the whole graph, we take a median of all c k (v). (Similarly to other curvature estimators, one can consider a subsample of nodes instead of the whole node set to speed up the computation).

E EXPERIMENTS:

E.1 DATASETS 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 T 3,6 is a tree with branching factor 3 and depth 6.

E.2 THRESHOLD-BASED LOSS FUNCTIONS:

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[v i ∼ v j ] • I[d(f (v i )f (v j )) > 1] + (1 -I[v i ∼ v j ]) • I[d(f (v i ), f (v j )) ≤ 1]

which essentially measures how well the values

I[d(f (v i )f (v j )) > 1] approximate I[v i ∼ v j ].

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[v i ∼ v j ] • I[d(f (v i )f (v j )) > 1] 2 i,j I[v i ∼ v j ] + i,j (1 -I[v i ∼ v j ]) • I[d(f (v i ), f (v j )) ≤ 1] 2 i,j (1 -I[v i ∼ v j ]

) .

The recent study by Gö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[v i ∼ v j ] and

I[d(f (v i )f (v j )) > 1]

. So, we add the corresponding Pearson loss (one minus correlation coefficient) to our experiments (see (Gösgens et al., 2019) ).

E.3 EXPERIMENTAL SETUP:

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. 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[v i ∼ v j ] • I[d(f (v i )f (v j )) > 1] + (1 -I[v i ∼ v j ]) • I[d(f (v i ), f (v j )) ≤ 1].

This function is not differentiable, so we replace it by gradient descent friendly function which we call ReLuLoss:

i,j I[v i ∼ v j ]•ReLu(d(f (v i ), f (v j ))-(1-ε))+(1-I[v i ∼ v j ])•ReLu((1+ε)-d(f (v i ), f (v j )),

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 the embedding algorithm, in all experiments we fix epochs = 1000 and we also try several learning rates (usually from 0.01 to 10 4 ). 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).

Under review as a conference paper at ICLR 2020 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 

E.4 COMPARISON OF CURVATURES ON SYNTHETIC DATASETS:

See the results in Tables 4 and 5 .

E.5 EFFECT OF DIMENSION AND LOSS FUNCTION:

In this section, we visualize the dependence of the loss function on curvature (see Figures 8 9 10 11 12 13 14 15 16 17 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).

E.6 EMPIRICAL ANALYSIS OF VOLUME-BASED CURVATURE:

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 

:

There are other definitions of distortion in the literature, see, e.g.,(Sala et al.,

2018).2 In 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.

Note 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.

We 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.

Further we slightly abuse notation by writing that C L d (G) is a real value if such c is unique and a set of values otherwise.

https://github.com/HazyResearch/hyperbolics

Dimension 10 is not included for zero-one loss if for all curvatures a perfect embedding is possible.

https://github.com/HazyResearch/hyperbolics

https://github.com/saibalmars/GraphRicciCurvature

https://drive.google.com/open?id=12i5LD6yTyFRDrgkMJEencDAI0Au6Isrn

We 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.

The 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.

Figures and Tables:

Figure 1: Star S n

Assume that d and n are fixed. If c is bounded below by a constant, then D(S n ) is also bounded below by a constant. If c → -∞, then the optimal distortion D opt (S n ) = Θ 1 √ -c . Therefore, for any S n we have C dist d (S n ) = -∞.

curvature We prove the following theorem (see Appendix B.6). Theorem 4.3. C thr d (T b ) = (-∞, C) for some C = C(b, d), which increases with d and decreases with b. The following lower bound holds:

Figure 2: Complete graph K n

Figure 4: Complete bipartite graphs K n,n

) ≈ 0.004, which is illustrated in Figure 3 (left). Threshold-based curvature It is easy to see that C thr d (C n ) = (-∞, 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 K l,m W.l.o.g. we assume that l ≥ m ≥ 2 (the remaining cases are stars and are already considered).

Figure 6: Adding k edges to one node of a cycle on 10 nodes

Figure 7: Adding one (left) or two (right) dangling edges to k subsequent nodes of a cycle on 10 nodes

For computing Ollivier and Forman curvature we use the open source package by Ni et al. (2015). 9

Figure 8: Effect of curvature, Karate club dataset

Figure 9: Effect of curvature, Dolphins dataset

Compare curvature estimators, distortion

Table content: <table><tr><td/><td colspan="2">Ollivier</td><td colspan="2">Forman</td><td colspan="4">Avg. sectional Grad. descent</td></tr><tr><td>Dataset/dim</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td></tr><tr><td>Conflict / 2</td><td>-0.2</td><td colspan="5">0.229 -16.5 0.261 0.25 0.269</td><td>0.0</td><td>0.229</td></tr><tr><td>Conflict / 10</td><td>-0.2</td><td colspan="5">0.078 -16.5 0.243 0.25 0.173</td><td>0.0</td><td>0.085</td></tr><tr><td>Chicago / 2</td><td colspan="4">-0.19 0.225 -8.37 0.224</td><td>-0.6</td><td>0.178</td><td>0.0</td><td>0.277</td></tr><tr><td>Chicago / 10</td><td colspan="4">-0.19 0.045 -8.37 0.216</td><td>-0.6</td><td>0.024</td><td>0.0</td><td>0.080</td></tr><tr><td>CSPhDs / 2</td><td colspan="6">-0.28 0.152 -7.92 0.420 -0.26 0.172</td><td>0.0</td><td>0.209</td></tr><tr><td>CSPhDs / 10</td><td colspan="6">-0.28 0.085 -7.92 0.412 -0.26 0.208</td><td>0.0</td><td>0.056</td></tr><tr><td>Euroroad / 2</td><td colspan="6">-0.36 0.267 -1.95 0.452 0.027 0.384</td><td>0.0</td><td>0.147</td></tr><tr><td colspan="7">Euroroad / 10 -0.36 0.264 -1.95 0.445 0.03 0.370</td><td>0.0</td><td>0.052</td></tr><tr><td>EuroSiS / 2</td><td colspan="6">-0.17 0.247 -29.1 0.197 0.27 0.298</td><td>0.0</td><td>0.263</td></tr><tr><td>EuroSiS / 10</td><td colspan="6">-0.17 0.087 -29.1 0.187 0.26 0.202</td><td>0.0</td><td>0.096</td></tr><tr><td>Power / 2</td><td colspan="8">-0.35 0.287 -2.85 0.368 0.02 0.363 -1.88 0.372</td></tr><tr><td>Power / 10</td><td colspan="8">-0.35 0.278 -2.85 0.361 0.02 0.331 -1.0 0.400</td></tr><tr><td>Facebook / 2</td><td colspan="6">0.308 0.290 -44.7 0.327 0.153 0.240</td><td>0.0</td><td>0.238</td></tr><tr><td colspan="7">Facebook / 10 0.308 0.210 -44.7 0.323 0.153 0.084</td><td>0.0</td><td>0.072</td></tr></table>

Compare curvature estimators, zero-one loss The detailed description of our experimental setup is given in Appendix E.3, the datasets and their properties are listed in Appendix E.1.

Table content: <table><tr><td/><td colspan="2">Ollivier</td><td colspan="2">Forman</td><td colspan="4">Avg. sectional Grad. descent</td></tr><tr><td>Dataset</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td></tr><tr><td>Conflict / 2</td><td>-0.2</td><td colspan="6">0.032 -16.6 0.032 0.25 0.060 0.0</td><td>0.032</td></tr><tr><td>Conflict / 10</td><td>-0.2</td><td colspan="6">0.001 -16.6 0.025 0.25 10 -4 0.0</td><td>0.0</td></tr><tr><td>Chicago / 2</td><td colspan="4">-0.19 0.004 -8.37 0.005</td><td>-0.6</td><td colspan="2">0.004 0.0</td><td>0.002</td></tr><tr><td>CSPhDs / 2</td><td colspan="7">-0.28 0.002 -7.92 0.004 -0.26 0.002 0.0</td><td>0.002</td></tr><tr><td>Euroroad / 2</td><td colspan="7">-0.36 0.002 -1.95 0.004 0.027 0.005 0.0</td><td>0.002</td></tr><tr><td>EuroSiS / 2</td><td colspan="7">-0.17 0.009 -29.1 0.017 0.26 0.058 0.0</td><td>0.010</td></tr><tr><td>EuroSiS / 10</td><td colspan="7">-0.17 0.003 -29.1 0.012 0.26 0.003 0.0</td><td>0.007</td></tr><tr><td>Power / 2</td><td colspan="7">-0.35 0.002 -2.85 0.006 0.02 0.006 0.0</td><td>0.002</td></tr><tr><td>Facebook / 2</td><td colspan="7">0.308 0.058 -44.7 0.059 -11.2 0.040 0.0</td><td>0.019</td></tr><tr><td colspan="8">Facebook / 10 0.308 0.007 -44.7 0.050 0.15 0.007 0.0</td><td>0.013</td></tr><tr><td colspan="2">threshold-based loss functions.</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Dataset description

Table content: <table><tr><td>Dataset</td><td colspan="2">num. nodes num. edges</td></tr><tr><td>Karate club (Zachary, 1977)</td><td>34</td><td>78</td></tr><tr><td>Dolphins</td><td/><td/></tr></table>

Compare curvature estimators, distortion, synthetic datasets

Table content: <table><tr><td/><td colspan="2">Ollivier</td><td colspan="2">Forman</td><td colspan="4">Avg. sectional Grad. descent</td></tr><tr><td>Dataset/dim</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td></tr><tr><td>S 100 / 2</td><td>0.0</td><td colspan="3">0.334 -97.0 0.058</td><td>-1.0</td><td colspan="3">0.304 -1.45 0.289</td></tr><tr><td>S 100 / 10</td><td>0.0</td><td colspan="3">0.127 -97.0 0.014</td><td>-1.0</td><td>0.1</td><td colspan="2">-30.2 0.025</td></tr><tr><td>T 3,6 / 2</td><td colspan="4">-0.33 0.136 -2.0 0.254</td><td>-0.5</td><td colspan="3">0.174 -9.77 0.271</td></tr><tr><td>T 3,6 / 10</td><td colspan="4">-0.33 0.016 -2.0 0.243</td><td>-0.5</td><td>0.036</td><td>0.0</td><td>0.077</td></tr><tr><td>K 100 / 2</td><td colspan="8">0.99 0.348 100 0.841 0.125 0.342 -48.7 0.163</td></tr><tr><td>K 100 / 10</td><td colspan="8">0.99 0.134 100 0.841 0.125 0.124 -305 0.015</td></tr><tr><td>C 100 / 2</td><td>0.0</td><td>0.106</td><td>0.0</td><td colspan="3">0.106 0.01 0.257</td><td>0.0</td><td>0.106</td></tr><tr><td>C 100 / 10</td><td>0.0</td><td>0.106</td><td>0.0</td><td colspan="3">0.106 0.01 0.255</td><td>0.0</td><td>0.106</td></tr><tr><td>K 100,100 / 2</td><td>0.0</td><td colspan="5">0.372 -196 0.294 0.008 0.372</td><td>2.1</td><td>0.309</td></tr><tr><td>K 100,100 / 10</td><td>0.0</td><td colspan="6">0.301 -196 0.275 0.008 0.301 -139</td><td>0.27</td></tr></table>

Compare curvature estimators, zero-one loss, synthetic datasets

Table content: <table><tr><td/><td colspan="2">Ollivier</td><td colspan="2">Forman</td><td colspan="4">Avg. sectional Grad. descent</td></tr><tr><td>Dataset</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td><td>c</td><td>loss</td></tr><tr><td>S 100 / 2</td><td>0.0</td><td colspan="3">0.02 -97.0 0.004</td><td>-1.0</td><td>0.027</td><td>0.0</td><td>0.02</td></tr><tr><td>T 3,6 / 2</td><td colspan="4">-0.33 0.006 -2.0 0.005</td><td>-0.5</td><td>0.005</td><td>0.0</td><td>0.002</td></tr><tr><td>C 100 / 2</td><td>0.0</td><td>0.005</td><td>0.0</td><td colspan="5">0.005 0.01 0.009 0.16 0.012</td></tr><tr><td>K 100,100 / 2</td><td>0.0</td><td colspan="7">0.496 -196 0.492 0.008 0.496 -531 0.493</td></tr><tr><td>K 100,100 / 10</td><td>0.0</td><td colspan="7">0.489 -196 0.491 0.008 0.480 -124 0.490</td></tr></table>

Peer review (iclr2020):
Summary: 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. All of the notions of curvature, however, are defined for continuous spaces, and have to be matched in some sense to a discrete notion that applies to graphs beyond a particular class like trees. The authors study this setting, consider a variety of existing notions of curvature for graphs, introduce a notion of global curvature for the entire graph, and now to efficiently compute it. They also consider allowing these concepts to vary with the downstream task, as represented by the loss function. Pros, Cons, and Recommendation The study of the various proposed distances is fairly interesting, although it*s hard to say what the takeaway here is. I think the part I*m struggling with the most is the motivation. Why do we care about using a space of constant curvature? True, we do so when it*s appropriate---we embed trees into hyperbolic space. But when we have a more complicated and less regular graph, then compressing all of that curvature information into a scalar doesn*t seem like a good idea, and indeed that*s the point of the Gu et al work that*s being built on here: it mixes and matches various component spaces that each have constant curvature, but altogether have varying curvature. At the same time, I like the idea of studying a bunch of proposed measures and attempting to gain new insights. This is a pretty unusual paper for ICLR, since the experimental section is really barely there, and what*s most interesting are really these atomic insights. If the authors work on the motivation I would consider accepting it---for now I gave it weak accept. Comments: - The distinction between what the authors think of as *global* and *local* curvatures is confusing and should be explained further. From what I can see, the authors think of global as being a scalar, and local as being defined at each point; intuitively these seem like pretty bad labels. I would think of the *global* one as being coarse, and the *local* as being more refined, since it contains a lot more information. This is also related to the motivation: why stuff all of this information into one single scalar curvature? It forces you to take averages, while Gu et al defined a distribution over the local curvatures. If the idea is to simply use one space and not a product, there are in fact various spaces with non-constant curvature, e.g., the complex manifold CH^n. - Why do your need your graph to be unweighted at the very beginning of Section 2? On the other hand, you may want to define your graph to be connected for the distortion function to be well-defined. - The statement *1, graph distances are hard to preserve:...* isn*t really meaningful, since for the example in 4.3.1, it is possible to embed that graph arbitrarily well. That is, even if the distortion isn*t 0, it can be made as small as we desire. There are indeed graphs that are hard to embed (i.e., have lower bounds that do not go to 0) in reasonably tractable spaces, and the authors actually prove such a result, but the star graph is not one of these. - There*s various tricks that actually make some of these graphs very easy to embed. One example is K_n in 4.33. Instead of just embedding K_n, embed the star graph on n+1 nodes, and place a weight of 1/2 on each edge. Now every pair of (non-central) nodes is at distance exactly. 1, and this thing is embeddable into hyperbolic space, etc. Interestingly, this is actually predicted by the Gromov hyperbolicity (for K_n_ that the authors briefly mention. The reason I bring this up is that even if the authors* project is successful, simple graph transformations may induce much better embeddings. That*s fine, though, although it should be mentioned. - Can the authors write out what*s going on for the hyperbolic lower bound on D_min in the proof of Thm. 4.1?