Global graph curvature
Authors: Liudmila Prokhorenkova
Egor Samosvat
Pim van der Hoorn
Venue:  (2020)
Keywords: graph curvature
graph embedding
hyperbolic space
distortion
Ollivier curvature
Forman 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 graph embedding). We show that optimal curvature essentially depends on dimensionality of the embedding space and loss function one aims to minimize via embedding. We review the 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. Hence, we propose a new estimator of global graph curvature specifically designed for zero-one loss function.

Under review as a conference paper at ICLR 2020
GLOBAL GRAPH CURVATURE
Anonymous authors
Paper under double-blind review
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 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 essen- tially depends on the dimensionality of the embedding space and loss function one aims to minimize via embedding. We review existing notions of local cur- vature (e.g., Ollivier-Rieci curvature) and analyze their properties theoretically and empirically. In particular, properly estimate the global one. We also make an important observation: larger dimensionality usually leads to less negative optimal curvature. We propose new estimator of global graph curvature which, in contrast to the existing ones, reflects this property as it is dimension-speeifie. We demonstrate that for a given dimension the new estimator is able to distinguish between "hyperbolic" and "Eu- clidean" networks.
show that such curvatures are often unable
INTRODUCTION
Representation learning is an important tool for learning from structured data such as graphs or texts (Grover & Leskoved 2016) Perozzi et 2014 Mikolov al. 2013). State-of-the-art algo- rithms typically use Euclidean space for embedding. Recently, however, it was found that hyperbolic spaces demonstrate superior performance for various tasks (Nickel& & Kiela 2018 [alaa al. 2018), while in some cases spherical spaces can be useful (Liu et 2017). A key characteristic classifying the above-mentionel spaces is curvature, which is negative for hyperbolic spaces, zero for Fuclidean and positive for spherical spaces. These findings, therefore, show that certain graphs are better rep- resented in spaces with non-zero curvature. While some methods simply fix curvature (c.g..-l -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 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 understand whether it is reasonable to embed a graph into some non-Fuctidean space and if yes, then which curvature choose. Having such an estimator would save computational resources, since learning an embedding is computationally expensive and should be done for each space sepa- rately. More importantly, can also save human resources by showing whether it worth investing resources in the implementation of a more complex embedding algorithm.
some simple graph characteristics to
We make an important first step in this direction by introducing a concept of global graph curva- ture, 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 curva- tures. We also compare several estimators of the global curvature, in particular, the ones based on well-known Ollivier-Rices and Forman-Riee 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-ing penensiioniddeeeddenne This raises the important question of how to properly estimate the best curvature for embedding graphs. We approach this problem by introduc-

---

Under review as a conference paper at ICLR 2020
ing new curvature estimator which, in contrast to all existing ones, is dimension-specifi. 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 thcoretical and empirical analysis, is the fact that the optimal curvature is usually smaller for smaller dimensions. In other words, 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 cover, e-g., the product spaces from (Gu al., 2019). We focused on the constant curvature since, first, such spaces are widely used in various applica- tions (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 an- alyze curvature other, more complicated spaces. To the best our knowledge, the problem of analyzing different notions of curvature for embedding graphs (even in simple spaces) was not con- sidered before, so we hope that more results will follow.
BACKGROUND AND RELATED WORK
Graph embeddings For an unweighted connected graph G E) equipped with the shortest path distance metric de, graph embedding I is map f V - U. where U is 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 graph embedding. The most well-known distortion (d(S(u), (()) do(u, do(u,v)
D()
Distortion global metrie, 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 Section 4. graph distances are hard to preserve: there are simple graphs on just nodes that can be perfectly embedded only in space of curvature -oo for any dimension.
Another measure, often used for embeddings, Mean Average Precision (MAP), which, for a given node v, compares the distance-batt based ranking of other embedded nodes with the graph- neighborhood-basee ranking. 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 curvature However, in practical applications like recommendation systems, ranking scores are usually com- plemented 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 define the following class of threshold-based loss functions. Given an embedding / of graph G, we (re)construct graph G' in the following way: e and u are connected G' iff (()) < 1. Then, any loss function which is based on the comparison of G' and G' is called threshold- based. 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., zero- one loss for the edge classification problem (whether given node pair is connected or not), see Appendix E.2 for definitions and discussion. Such loss functions are natural many applications (graph reconstruction, link prediction, recommendations).
1 'Thrre are other definitions of distortion in the literature, see, e.g., Sala 2018
'In other words, it is sufficient to consider only the curvatures -1, 0. 1. corresponding to hyperbolic, Eu- clidean and spherical spaces. Moreover, by considering a small enough region in hyperbolic or spherical space we get geometry similar the Faclidean one, for MAP is important distinguish only between -1 and
2

---

Under review as a conference paper at ICLR 2020
For many years, Euclidean space was the primary choice for 2018 However, it turned out that many observed datasets well fitted into hyperbolic space (Krioukov al.] 2010). Nickel & Kiela (2017) have shown that such hyperbolic embeddings can improve state-of-the-at quality in several practical tasks, e.g.. lexical entailment and link prediction. On the other hand, spherical spaces are also used for emhed- dings (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.
Hyperbolic and Spherical Spaces data embeddings (Goyal & Ferrara
The main advantage of hyperbolic space is that it is "larger": the volume of ball grows exponen- tially with its radius. Hence, such spaces are well suited for tree-like structures. On the other hand, spherical spaces are suitable for embedding eycles (Gu et (2119). 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
3 LOCAL GRAPH CURVATURES
While 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 de- fined 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 cur- vature is positive if small spheres are closer than their centers are. We refer to (Jost) 2009 O neilll for more details on Ricci curvature.
1983
Ollivier curvature Ollivier curvature translates the definition of Ricci curvature 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. Wasser- stein distance or earth- muvtr distance). Formally, for graph G' we consider the shortest path metric on G. denoted by dg. and let W/C denote the Wasserstein metric with respect to the metric space (G, (G) Furthermore, for each node v we let m. denote the uniform probability measure on the neighbors of v. i.e., (u) deg(o) definition of Ollivier curvature between two neighboring nodes v ~ u G' is defined as
Lase, where deg(v) denotes the degree of c. Then, the classic
ka(u, v) = 1 W (m,, m.).
(1)
We note that Ollivier curvature always belongs to the interval [-2, 1] (Jott & Liu 2014
Forman curvature Forman curvature (Sreejith al. 2016) based on the discretization of Ricci curvature proposed by Forman (2003). is defined for general weighted graph G, with both node and edge weights. When the graph G not weighted, the definition becomes:
Fa(u, v) = (deg(u) deg(u)).
Forman was interested in 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 (Samal et al. 2018), where 2-dimensional faces on three nodes (triangles) were included. In the case of an unweighted graph, we then obtain
Fo(u, v) F(u, v) 34. = 4 -eg(p) deg(u) + 3Auer
where Age the number of triangles that contain the edge (u. v).
Based on the definitions, both Forman curvatures, especially Fe (u, v), are expected to often be highly negative. Indeed, this is what we observe in Sections and
NNot that Ollivier curvature is defined in much more generality in terms of metrics and random walks, see (Ollivier 2009). Thus, different version graphs can he considered. Equation corresponds to the classical choices of graph distance and random walk the graph.
3

---

Under review as a conference paper at ICLR 2020
Heuristic sectional curvature A different notion of curvature used by Gu et al. (2019) is based on the following geometric fact. Let abc be geodesic triangle and let m be the (geodesic) midpoint of be. Then the value d((a, m)2 + d(b.e)² d(a.b)* +a(a.c)" equal to zero in euclidean space, positive in spherical space and negative in hyperbolic space.
For graphs, let be node in G, b, neighbors of and any other node. Then, define
Ea(e;b c:) 2do(a, v)) dolb,c)² dalaa,b²= dd((a,))))
1
(4)
4
This resembles the formula above with m = v and the normalization constant (d a) is in- cluded to yield the right scalings for trees and cycles. To define the graph sectional curvature of a node u and its neighbors b.c. we average (o((; b, aaa) over all possible a: ba(u; = MV-3 LaEGs(o,d. (o(u;
GLOBAL GRAPH CURVATURE
The problem with these different notions local graph curvature is that they cannot be easily used in practical applications, where data is usually embedded in space of constant curvature. Hence, a global notion of curvature needed. 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 S(G) be an embedding of this graph into a d-dimensional space of constant curvature (spherical, Euclidean or hyperbolic). Assume that are given loss function L(f) for the embedding task (see Section 2 Now, let Lope( (G, d, c) the optimal loss for given and c: Topp (G, d) miny I(f)- Then, define d-dimensional curvature of G in the following way:
C (G) = arg min Lopt (G,d, d.
(5)
Note that there may be several values of curvature e delivering the minimum of Lope d, c). in this case we say that C (G) consists of all such points
Below we analyze global curvatures based on distortion (Cdist and threshold-based (C (G)) loss functions. In the latter case, in experiments, results apply to any threshold-basee loss, since Lopt (G, d, c) reaches its minimum on "perfect" embeddings, where preciscly reconstruct the graph G.
measure zero-one loss, but our theoretical
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 x(G)
Σ kG(u, v).
Forman curvature F(G)=
Σ Folu, vo, F(.
1 Σ folu,v)
E
Average sectional curvature Ps Σ Σ b.
Let P3 denote the number of paths of length 3 in G, then E(G)
VV b<ceb.eN(v))
WW that does coincide with which do affect the average much hut makes results in Section 4.3 more succinet. Further we slightly abuse notation by writing that C3 (G) is real value if such is unique and set of values atherwise.
4

---

Under review as a conference paper at ICLR 2020
n=2,0=2 --2---2
033
100,
033
200 boc
0.75
0.25
0.2
0.1
0.55
0.5
-2
-15
0.5 0.5
3.5
-15
0.5
0.5
1.5
Figure 1: Star S.,
It is important to note that all curvatures discussed above do not depend on neither dimension nor loss function However, as we show below, global curvature defined in Section 4.1 significantly depends on them.
Let us also mention that there is concept Gromov's hyperbolicity (Gromov) 1987). which is sometimes used to decide whether it is reasonable to embed a graph to 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 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, we illustrate and discuss in Appendix 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 negatively curved. We analyze this theoretically and start with the simplest tree: one central node and n leaves. We denote this graph by S, and assume that 3.
Ollivier curvature Consider any tree graph T, let v, a be two neighbors. Then Proposition in (Jost & Liu 2014) states that
NT (u, v) =2 -2(1--1 deg(v) deg( (u)
(6)
where /+ = max max(0, t). particular, either deg(v)= = or deg(u) (u) = 1, then (u, v) = 0. As result, for star we have Kss (u, v) so x(S)) 0 and stars are negatively curved according to Ollivier curvature.
Forman curvature If follows from Equation and Equation 3 that F(S,)) = F(S)) = n, stars are highly negatively curved for large n according Forman curvature.
Average sectional curvature Heuristic sectional curvature is defined for node and its two neigh- bors. In case of a star we can only take central node and two neighboring ones and c. For any other node a we obtain Es., b, -1. Therefore, by averaging we obtain ((S.)) -1.
Distortion- curvature
We prove the following theorem (the proof is in Appendix B.3
5

---

Under review as a conference paper at ICLR 2020
Theorem 4.1. Assume that d and are fixed. If is bounded below by constant, then D(S,)) is also bounded below by constant. If - -C, then the optimal distortion D (Sp) θ Therefore, for any Sn. we have Cdiet(S... -00.
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 has to lie on the geodesics between all pairs of leaves, so all nodes have belong 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 -> - oC, we can spread all leaves of S, uniformly on circle of radius 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 that if minimize threshold-basee loss, then any tree be perfectly embedded with d =22 2.
Threshold- -based curvature Here we have the following theorem (the proof is in Appendix B.5 Theorem 4.2. Cttir (Sn) = (-00, for some C C(n, d). which increases with and decreases with n. In particular, for 2, if < 6, then C = (arccos 1-cos
cos 37
"L ) if 6, then C 0: if
> 6, then C = 2raccosh sin
1
The result is illustrated in Figure (right), Note that zero-one loss can be noisy, especially on small graphs, since it is hareshold-basede i.c., discrete.
4.3.2 TREE To WITH BRANCHING FACTOR b
We consider a tree Ty, b 2 2. For symmetry, assume that the first node has b + children, while all other nodes have parent and b children. Also, for Ollivier, Forman and threshold based curvatures, assume that the depth of Tú is infinite. In other cases, statements hold for any finite tree T.
Ollivier curvature We can use
Equation 6 and get, for any edge. KTs (u, 611 = - 541 So, <TT))
=
= 2 + 641, which is negative.
b+1
Forman curvature is easy that we have F(T.)) ((T))
2(b + 2(1 b).
Average sectional curvature In contrast to Ollivier and Forman curvatures, heuristic sectional curvature global, i.e., depends on the whole graph, which has to be finite. Note that for any tree, to compute sectional curvature, we average O and -1. As a result, for any tree T we have <(T) E [-1,0] (Gu al., 2019).
Distortion- based curvature On the one hand, our result for Sn implies that if 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 e. Note that multiplying graph edges by is equivalent to changing curvature from 1 to 72. As result, Sarkar 2201 proves that we can achieve an arbitrary small distortion if c + -c.. Hence, Cdist -00 any T.
Threshold haareshodd-baed curvature We prove the following theorem (see Appendix B.6
Theorem 4.3. Cujr (Th) C) for some C' = C(b, d), which increases with and decreases
with b. The following lower bound holds: C(b,2) N
log b
2 arocosh cosh 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 formally prove that trees can be perfectly embedded in hyperbolic plane of some curvature.

---

Under review as a conference paper at ICLR 2020
n n=4,0
4,00
n 5, =
5, d 10
destrtion
0.25
n 100,
100
10
0.2
0.15
0.1
0.05
curvature
Figure Complete graph K
0-5.0=
0.35
000.0=2
n- 100
0.3
8. 105, d
2010
02
0.55
cuvatarz
carvoture
Figure 3: Cycle graph Cn
4.3.3 COMPLETE GRAPH K₁,
Ollivier curvature For any two nodes and v, it follows from Example 1 in Jost & Liu 2014) that KK, (v, u) n-I Thus, x(Kn) = x-1
n-2
n-2 and it tends to as - 20.
Forman curvature Simple computations yield: F(Kn) 6-2n, highly positive or highly negative value.
2n, F(Kx) n. i.e. get either
Average sectional curvature
It is easy to compute that E(K,,) =
Distortion-based based curvature pendix B.4 for the proof).
The following theorem analyzes Cidist (K₂) if (see Ap-
Theorem 4.4. (Kn))
={
00, aarssin
2
Note that the optimal curvature -O appears here since embedding of a complete graph can be reduced embedding weighted star. This theorem is illustrated in Figure For n 4, we expect to see the minimum at about 3.65, for 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 curvature becomes small.
Thrreshold-based curvature by mapping all nodes to one point.
CHA)(Kn)) R. since embed any complete graph perfectly
4.3.4 CYCLE GRAPH Cn
We consider cycle Cn with 4.

---

Under review as a conference paper at ICLR 2020
n=5,0=2
n- 5,d
0335
186, d
0.31
200-00e boo
0.25
0.78
0.2
0.23
0.13
03
50
005
1-000..0
0.88
2
-15
0.5
155
2.5
Figure 4: Complete bipartite graphs K
Ollivier curvature Let ~ u two neighbors. Then it is easy to see that W (ma, m.) = and hence Ku v) = 0. Thus, x(C,)= O.
Forman curvature Similarly, it is easy see that F(C,) P(C,)) =0.
Average sectional curvature If n is even, then {c,, (v; b, = 0 for all points except the one If n is odd, then for two points
diametrically opposite for which have {c., (1; b, we have &c,, (w; b, c; a) 2(n-1)- As a result, {(Cn) n-3 for even and g(C,) for odd n.
[)(m
Distortion- based curvature Here we have that (C,) (2x) Indeed, 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, Cdiat (Cs) RJ 1.58, Cysat (C10o) ss 0.004, which is illustrated Figure (left..
Threshold-based curvature is easy to see that Cu (C,) = (-oc, C) with some C > 0, which decreases with n and increases with d (see Figure right). A simple lower bound for C' is C P 4x) 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 Kt.m
W.l.o.g. we assume that / 2 2 2 (the remaining cases are stars and are already considered).
Ollivier curvature We prove the following lemma (the proof is in Appendix B.I Lemma 4.5. <(Ki,m) O.
Forman curvature F(Kim) (Ki,) = m.
Average sectional curvature
The following lemma holds (see Appendix B.2).
Lemma 4.6. {(Ki,m)
-II-)) -1-m)+++tl22 4m+t-2 In particular, m. = we get E( (Kimm)= 2m-3- 1m+1-2)(44m--
1
This lemma implies that for balanced complete bipartite graphs {(Ki,m) positive, but tends to zero as the graph grows.
Distortion-based curvature Figure (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, (K2,)) (g)) x 2.47 and K2 is the only complete bipartite graph (with at least two nodes each part) for which distortion is achievable.
8

---

Under review as a conference paper at ICLR 2020
Table 1: Compare curvature estimators, distortion sectional loss
Ollivier
Forman loss
Avg.
Grad. descent
Dataset/dim
loss
loss
Conflict /
-0.2
0.229
-16.5
0.261
0.25
0.269
0.0
0.229
Conflict / 10
-0.2
0.078
-6..5
0.243
0.25
0.173
0.0
0.085
Chicago
-0.19
0.225
-8.37
0.224
-0.6
0.178
0.0
0.277
Chicago 10
-0.19
0.045
-8.37
0,216
-0.6
0.024
0.0
0.080
CSPhDs /
-0.28
0.152
-7.92
0,420
-0.26
0.172
0.0
0.209
CSPhDs 10
-0.28
0.085
-7.92
0,412
-0.26
0.208
0.0
0.056
Euroroad /
-0.36
0.267
-195
0.452
0.027
0.384
0.0
0.147
Euroroad 10
-0.36
0.264
-195
0.445
0.03
0.370
0.0
0.052
EuroSiS /
-0.17
0.247
29.1
0.197
0.27
0.298
0.0
0.263
EuroSiS 10
-0.17
0.087
-29.1
0.187
0.26
0.202
0.0
0.096
Power
-0.35
0.287
-2885
0.368
0.02
0.363
-1.88
0.372
Power / 10
-0.35
0.278
-285
0.361
0.02
0.331
-1.0
0.400
Facebook 2
0.308
0.290
-44.7
0.327
0.153
0.240
0.0
0.238
Facebook / 10
0.308
0.210
-44.7
0.323
0.153
0.084
0.0
0.072
Indeed, the result for K2.2 follows from the corresponding result on cycle C4. Moreover, if for Ki. we have 3 and m 2 2, then for any nodes in the part of size there least different geodesics of length 2 between them. Therefore, all such pairs lie at opposite poles of the hypersphere, which impossible since 3.
Threshold- 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 S |V] (Maehara 1984). However, undirected bipartite graphs are hard to embed in Euclidean space: the bound similarly hard to embed to both spherical and hyperbolic spaces, as shown in Figure (right.. Em-
(nn is known (Maehara 1984). We empirically observe that they are
pirically, these graphs are insensitive to curvature (given that it is not too large).
4.4 VOLUME VOLUME-BASED BASED APPROXIMATION
Let us propose 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 hyperbolic space is the fact that 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 given one and then compute the eurvature needed to get such volume. We compare the number of nodes at distance exactly k from node (discounted using the number of edges between them) with the area of a hypersphere of radius 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 becomes larger, curvature becomes smaller in absolute value. As we show in the experiments observed for the optimal curvature. Also, it turns out that for given dimension the new estimator able 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.
various datasets, similar property is
5 EXPERIMENTS
In this section, we compare all discussed curvature estimators empirically. Our experiments are based publicly available implementation of graph embedding by Gu et al. (019 The main advantage of this algorithm is that it works for any curvature: negative, positive or zero. We mod- ified the implementation for our task: in particular, we added regime responsible for minimizing

---

Under review as a conference paper at ICLR 2020
Table 2: Compare eurvature estimators, 7ero-one loss
Ollivier
Forman
Avg. sectional loss
Grad. descent
Dataset
loss
loss
loss
Conflict / 2
-0.2
0.032
-16.6
0.032
0.25
0.060
0.0
0.032
Conflict / 10
-0.2
0.001
-16.6
0.025
0.25
10-4
0.0
0.0
Chicago /
-0.19
0.004
-8.37
0.005
-0.6
0.004
0.0
0.002
CSPhDs /
-0.28
0.002
-7.92
0.004
-0.26
0.002
0.0
0.002
Euroroad 2
-0.36
0.002
-1.95
0.004
0.027
0.005
0.0
0.002
EuroSiS/ /
-0.17
0.009
-29.1
0.017
0.26
0.058
0.0
0.010
EuroSiS I0
-0.17
0.003
-29.1
0.012
0.26
0.003
0.0
0.007
Power /
-0.35
0.002
-2.85
0.006
0.02
0.006
0.0
0.002
Facebook / 2
0.308
0.058
-44.7
0.059
-11.2
0.040
0.0
0.019
Facebook / 10
0.308
0.007
-44.7
0.050
0.15
0.007
0.0
0.013
threshold-based loss functions. The detailed description of our experimental setup is given in Ap- pendix E.3 the datasets and their properties listed in Appendix E.1
The results of the comparison for distortion and zero-one loss are presented in Tables I and respectively( 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 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 [..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 polume-based estimator (see Appendix E.6), we noticed that able to predict well whether the hyperbolic space is needed for embedding Euclidean space enough. However, the magnitude for the predicted curvature can be not optimal. Volume-base estimator also predicts that for large dimensions Euclidean space is often good choice.
CONCLUSION
In this paper, we introduced a concept of global graph curvature motivated by the practical task of embedding graphs. This curvature depends the loss function and dimension of 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 curva- ture and several approximations based on well-known local graph curvatures and showed that they essentially differ. We demonstrated that dimensionality and the choice of loss function fundamen- tally 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 sim- ple dimension-speccio curved space. Our work shows that the problem of finding the rights space for graph embedding is interesting and non-trivial and we hope results will encourage further research global graph curvature.
estimator which decides whether it is reasonable to embed into negatively
Dimensioo 10 not included for zero-one loss if for all curvatures perfect embedding is possible.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
R Eash, K Chon, Y Lee, and D Boyce. Equilibrium traffic assignment on aggregated highway network for sketch planning. Transportation Research, 13:243-257, 1979.
Robin Forman. Bochner's method for cell complexes and combinatorial ricci curvature. Discrete
and Computational Geometry, 29(3):323-374 2003. doi: 10.1007/000544400-44443xx
Martijn Gösgens, Liudmila Prokhorenkova, and Alexey Tikhonov. Systematic analysis of cluster similarity indices: Towards bias-free cluster validation. arXiv:1911.0473, 2019.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applicationn, and performance: A survey. Knowledge-Bi Booweedge-Based Based Systems, 151:78 94, 2018. doi: kww.::/j..ooss.2118...0.
Mikhael Gromov. Hyperbolic groups. In Essays in group theory, pp. 75-263. Springer, 1987.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature repre- sentations in product spaces. ICLR, 2019. URL httpss//rrenrerreee.ntt///at
HoxeWhCcF7
Jürgen Jost. Geometry and physics. Springer Science Business Media, 2009, doi: 10.1007/ 978-3-642-00541111
Jürgen Jost and Shiping Liu. Olliviers ricci curvature, local clustering and curvature-diment inequalities graphs. Discrete & Computational Geometry, 51(2):300-322, 2014. doi: 10.
1007/500454-013-9555588
Devangana Khokhar. Gephi cookbook. Packt Publishing Ltd, 2015.
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010.
Jure Leskovec and Julian J Mcauley, Learning to discover social circles in ego networks. In Advances in neural information processing systems, pp. 539-547, 2012.
Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. Sphereface: Deep hypersphere embedding for face recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 212-220, 2017.
David Lusseau, Karsten Schneider, Oliver Boisseau, Patti Haase, Elisabeth Slooten, and Steve M Dawson. The bottlenose dolphin community of doubtful sound features large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 54(4):396 2003.
Hiroshi Machara. Space graphs and sphericity. Discrete Applied Mathematics, 7(1::55-64, 1984.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp. 3111-3119 2013.
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):5577-852) 2006.
Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113 2004.
Chien-Chun Ni, Yu- Yao Lin, Jie Gao, Xianfeng David Gu, and Emil Saucan. Ricci curvature of the internet topology. In 2015 JEEE Conference on Computer Commmiccatinns (INFOCOM), pp- 2758-2766. IEEE, 2015.
11

---

Under review as a conference paper at ICLR 2020
Maximillian Nickel and Douwe
Kiela.
Poincaré embeddings for learning hier-
archical representations. In Advances tems, pp.
in
neural information processing sys-
URL http::/papers.eee nips cc/paper/ 7213 poincare- pooincare-mmeddiin for-s-oo--00 ht
2017.
pdf
Maximiliin Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International Conference on Machine Learning, pp. 3776-3785, 2018.
URL htt.tttts://aaatttt org/ abs/1806. 03417.
Yann Ollivier. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis, 256(3):810-88) 864, feb 2009. doi: ff.10166..fa.2200.111.. 100....00...000
Barrett O' O'neill. Semi-Riemannian geometry with applications relativity, volume 103. Academic press, 1983.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoffs for hyperbolic embeddings. International Conference on Machine Learning, pp. 4457-4466, 2018.
Arcejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost. Comparative analysis of two discretizations of ricci curvature for complex networks. Scientific reports, 8(1): 8650, 2018. doi: 10.1038/s41598-11 598-01 -0000-00033.
Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, pp. 355-366. Springer. 2011.
RP Sreejith, Karthikeyan Mohanraj, Jürgen Jost, Emil Saucan, and Areejit Samal. Forman curva- ture for complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2016(6); 063206, 2016. doi: 10.1088/1742-555 014831/77422444/2200060066666
Lovro Subelj and Marko Bajec. Robust network community detection using balanced propagation. The European Physical Journal 81(3):33-332, 2011.
Alexandru Tifrea, Gary Bécigneul, and Octavian-Eugee Ganea. Poincaré glove: Hyperbolic word embeddings. arXiv preprint 1rXiv:1810.065: 1810.06546, 2018.
A. Mrvar W. De Nooy and V. Batagelj. Exploratory social network analysis with pajek. Cambridge University Press, 2011.
Michael D Ward, Randolph M Siverson, and Xun Cao. Disputes, democracies, and dependencies: A recxamination of the kantian peace. American Journal Political Science, 51(3))583-60) 2007.
DJ Watts and SH Strogatz. Collective dynamics of small-world networks. nature, 393: 440-442.
View Article, 1998.
Melanie Weber, Emil Saucan, and Jrgen Jost. Coarse geometry of evolving networks. Journal of Complex Networks, 6(5):706-732, 11 2017. ISSN 2051-1329. doi: 10. 10.1093/commee/cnx449.
Wayne W Zachary, An information flow model for conflict and fission in small groups. Journal of anthropological research, 33(4):452-473, 1977.
A GEOMETRICAL PROPERTIES OF SPACES OF CONSTANT CURVATURE
In this section, we recall some useful equalities which will be used throughout the proofs. In all proofs, sphere) and in the hyperbolic case (c 0) R can be considered as scaling factor compared to the space of curvature 1.
notation R. where R /22 in spherical space (corresponds the radius of
12

---

Under review as a conference paper at ICLR 2020
Law of cosines Let consider triangle with angles A, B, C and the lengths of opposite sides a, b, c, respectively.
In Euclidean, space we have:
c² = a² + bos C.
In spherical space, the first law of cosines is:
b
+ sin
sin cos C
R R
R
R
and the second law of cosines is:
cos cos A cos B + sin A Asin cos
R
In hyperbolic space, we have
cosh cosh
c a
cosh sinh a R
b sinh cos C.
R
R
R
R
Equilateral triangle
The following equalities follow from the corresponding laws of cosines, assuming that all sides (and angles) are equal.
For hyperbolic space:
a
1
cosh
2R
2 sin
For spherical space:
CO8 A
(8)
R
1 cos A
Area and volume of hypersphere Let Sa(r) and Va(r) denote area of hypersphere and volume of a ball of radius r d-dimensional space.
In euclidean space,
Sa(r) = d
Va(r) = Card,
where
d/2
C2 r'22 + 1)
In spherical space, sphere of radius r is isometric to Euclidean sphere of radius Rsin z. Therefore, the area is
Sa(r) = dCa (Rsin r)d=
Va(r) = &C2 ("(sin
2 dx.
d-1
R
Similarly, in hyperbolic space,
Sa(r) dCa (Rsinh
m)d1
d-1
R
Va(r) d CC Rd S
I. d-1 (sinh
dr.
R
13

---

Under review as a conference paper at ICLR 2020
B CURVATURE OF SIMPLE GRAPHS
B.1 PROOF OF LEMMA 4.5 (OLLIVIER CURVATURE FOR BIPARTITE GR GRAPHS)
Let use denote the node sets in Ktm by U = {ui Uu...... wi and (V1...., Um We will prove that for any edge (u, v), WT Ki," (mu. my) = 1, which then implies that x(K,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 (mi m.) = inf ΣΣ d'll',"))ppl e' mas
where the infimum is taken over all joint probability measures on the product of the neighborhoods of o and u, while on the other hand
WF (mas m.) sup
Σ v'mu
deg(u)
deg(u) w'mu
where the supremum is taken over all 1-Lipschitz functions, i.c [f(u) f(v)) (u, v).
Note that for any u E U, v E the joint neighborhood V x U. First we establish an upper bound by considering the product joint probability density on V x U
p(x,)) v) ml
It then follows that
m
W.i,. Kt.m (may m.)
dalus, u, u))p((,,
i=
For the lower bound we define the function
f(=) = [2 if EV,
1 E
Observe that if U and E V then (s( [(=) = = da(u, On the other hand, if
w. u' E U then [f(w) - J(u')
= 0 < = (u, u²) and similar for v, v E V. Thus we conclude
that f is I-Lipschitz. It now follows that
w- (may m.)
1 Σ
f(v.)
1 1aa)
((g))=
m
which completes the proof.
B.2 PROOF LEMMA 4.6 (AVERAGE SECTIONAL CURVATURE FOR BIPARTITE GRAPHS)
If u and are in the same part of the bipartite graph, then ÉKi, b, 1, otherwise Ex,,.. (u; b, a) -1 Therefore, if belongs to the part of size I, sectional curvature is ÉK,... (v;b, c) i-m+1 otherwise it is &ki... bv; m-I+1 As result, by averaging
all triplets, we get
(1(m)
l m 1 + m
+ m (1) m 1111+1
-(1 - m)² + m
((Krm)
((5) + ml))
1+ m m-
(m + 2)(1 m
B.3 PROOF OF THEOREM 4.1 DDSTORRTION-BSER CURVATURE FOR STARS)
The general idea is the following: we take any curvature and prove lower bound distortion (for any given dimension d). Then, we obtain an upper bound on optimal distortion which tends to zero -00, which gives the claimed result Csiet (S.) -o.
14

---

Under review as a conference paper at ICLR 2020
First, let analyze the lower bound on distortion. Recall that distortion of graph is the average distortion over all pairs of nodes. Let v be the central node and U1..... Un (n 2 3) be its neighbors. Then, for any embedding f. we have
D(S))=
1 (xt2)
Σ d(f(v). 1/+
Σ
d(f(u.).f(,,) -
((f(ve)), -1
(d(f(oi)), -
Σ
(2+1) IS Siiiii
("z)
2(n 2)
sisa
1Ejckg3
Let Dinn be the minimum value of the following weighted distortion of a star with 3 leaves:
[d((u)); -
Dmin -min
Σ
Σ 1sicks3
[d(f(1)) 2/.
- (n-1)/4
15i53
then
(n 1)D
D(S,) 2 2(n () D Dmnn
(9)
6(n +
Hence, it remains to find lower bound on Dmin. i.c., a lower bound for a weighted distortion of S3 with central node and three leaves 11 12, V3. If we consider three angles the node then least one of them is a S 2T/ 2T/3,, /3, so we can get lower bound by only considering this triangle, which is, w.l.o.g., formed by c, U1, U2-
Dmnn 2 (d(f(v1). f(r2)) 2 d(f(va), + (d(f(2)) f(v)) -1
(n 1)/2
d(f(v)). = = 1+ d(f(v)), f(22)) 2 + 8 8- P with some E, 5 and some o > 0 (from triangle inequality). Assume that E < 1/2 and |6] < 1/2 (otherwise the lower bound is trivial). Now we use the law of cosines to get a lower bound on yp. We consider Euclidean and hyperbolic spaces separately and note that the bound obtained in Euclidean space also holds in spherical spaces (with any c).
Denote f()) = =
In Euclidean space, using triangle inequality, get +p + y spherical spaces yp is bounded below by a constant.
0. So, in Fuclidean and
In hyperbolic space the law of cosines gives (recall that R --)):
cosh cosh y/ sinh sinh y
cosh R
cosa,
R
R
R R
from which, using cosh(x + v) = cosh cosh + sinh a sinh
get
cosh I + cosh z = sinh x sinh y/
(1 + cos
R
R
R
R
If R oc, then, similarly Euclidean case, we get & + y = 1((1).
On the other hand, Rt + O, we get y = I(R). Note that Dmin 2 |z 2| + (1-1//2
Is + 8 - sp +
|e|+|6| 1)/2 This gives us lower bound Dmin Q(1/n) in spherical and Euclidean
spaces and D Dmnn 11min(R, 1)/n) = Ω max mmxx(/=a)) in hyperbolic space. From this and Equation the bound (SS,) follows.
Now, let us get an upper bound on optimal distortion Dopt (Sx). To do this, we explicitly construct an embedding with sufficiently low distortion D(S.).
Let U be the central node, then we spread all other nodes uniformly on a 2-dimensional circle of radius 1 centred v. The smallest angle between two points is 27/n. Therefore, from the law of cosines, the distance between leaves is at least with
= + (1 cos
2T -
cosh R
sinh
n
R
15

---

Under review as a conference paper at ICLR 2020
Note that for any two leaves U, and v we have that (o;), f(z)) I 2. In particular, the closer two leaves are, the greater the difference - d(f(v)), f(r,)) is. Hence, the distance between adjacent leaves is the worst and thus Dope (S,,) can be upper bounded
((1-
2T
1 R
Dopt (Sa) - 2 (
R arccosh
cos
sinh? +
n
(n 1)
2TT ((1- -ososs
1
+ +1
2 R arccosh
sinh?
2(n + 1)
n
Note that 1 - cos 2x = θ (t) and sinh (#) = θ (E2/1t). Then, arecosh (0 ( + 1) behaves
222/ 2/2 < log and as logn if 2/ > log Therefore, we get
log
Dopt (S.) ( n) =
(V=o
B.4 PROOF OF THEOREM 4.4 [DISTORTION-BASE) CURVATURE FOR COMPLETE GRAPHS)
If d 2, then we are given (n simmll,,,, which can be embedded into n 2-dimensional spherical space. Indeed, the radius of circumscribed hypersphere for the (n 1)-simplex with side length is known to be R a be equal to one, we need to choose a accordingly:
Since we want the spherical distance between all points to
a sin
1 R
for a=
2
2R
Here corresponds to the angle giving the are length 1, while the condition on sin relates a and a since a the angle in a triangle with side lengths a,, R, R. This implies that
2R arcsin
1,
2R
and solving this equation for a yields
2n
1
(n 1) aresin 2(n-1) 1)
Plugging this back into the formula for the radius R we obtain
R arcsin / 2(n-1]
so that have
Cilist (Kn) =
( arcsin
n2
2(n
xX, then optimal distortion Dopt (K₂) 0. This result follows from the fact that D Dopr (S,) + 0, because to embed a clique, it is sufficient to embed star on n + node with edge lengths 1/2 and then remove the central node.
Finally, let show that if
B.5 PROOF OF THEOREM (THRESHOLD--AAE BASSED CURVATURE FOR STAR)
We show below that for any n, any dimension d and some curvature there exists perfect embed- ding. Therefore Cdfsst (S,) consists of curvatures for which such perfect embedding exists.
First, let us note that if there exists perfect embedding f for some curvature then there exists a perfect embedding for any curvature < c. Indeed, w.l.ogg, we assume that the central node u mapped to the origin of hyperspherical coordinate system and other points . Un can be described by their radii and angles. We know that the distance between e and any e; is at most and the distance between any pair U; Uy is larger than one. Now change curvature to d' and
16

---

Under review as a conference paper at ICLR 2020
keep hyperspherical coordinates the same. Then the distance between and any Us does not change, while the distance between nodes V4, By increases.
Now, it is casy to that C' increases with d: if there exists embedding to some dimension d, then, obviously, the same embedding works for > Further, decreases with n since if there exists embedding of S,, then we easily construct embedding of S,, for n' by removing some nodes.
Now, let construct perfect embedding of S,, and estimate the required curvature. Recall that in a perfect embedding all leaves have to be inside the ball of radius around the central node v and also the distance between any two leaves has to be larger than one.
is easy to see that we managed to spread n points inside the ball of radius with distances more than between them, then can move each point along the radius up distance from 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 > 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 have distance exactly between the closest leaves. In this case we cannot embed Sn in space of curvature C, but can embed in a space of any smaller curvature. We use Equation 7 and let a 2x.
1
1
cosh
2R
sin o
R = 2 arccosh
2sin 2
1 2 sin
C = 2 arccosh
Note that if n is large, then sin @ sin n-1
Then, arccosh 2sin
arccosh
n-1 2x
log n,
n-
so we get C log n.
Now, let us consider n < 6. Obviously, for n we have C = O.
6, then >> O. We use Equation g
C0S
COS
R
1 - COS
COS a
C
arccos
COS C
B.6 PROOF OF THEORRE 4.3
TTURESHOLD-BBSEED CURVATURE FOR TREES)
As for Sn, we prove that for T. a perfect embedding exists for and some curvature 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 guarantee that an embedding exists. For this, we provide the following construction (see Figure 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 and consider circle of radius I around this node. We spread b neighbors uniformly around this node. For our construction to work, we need all distances between these nodes to be larger than 1. Now, some step of the algorithm, assume that we have all nodes at level placed at some circle centered at v and distances between the nodes at level are larger than 1. Our aim is then to find positions for all nodes at level +++ 1.
Let us take any node at (-th level. Consider two points uy and u, on the same circle at distance from the node the left and the right, respectively. Let u, ur 2j and u, uy 2, form equilateral
17

---

triangles (with sides equal 1). Then we let the points at / + 1-th level be spread on the circle centred at t and passing through 2 and 2y. The children of u (u),..,, 46) will be placed on the circular are between 2 and 2,. As usual, we want u, and U++1 to be at distance least from each other. Moreover, they have to be at distance at least 1 from children of other nodes. Also, note that placing ......: Up between 2, and 2, guarantees that these nodes are closer than to their parent node but at the same time at a distance larger than 1 from all other nodes at I-th level. Also, all Under review as a conference paper at ICLR 2020
141 14g 7/
24]
34r
V
Figure 5: "hhrehold-basee embedding of trees
points at I-th level are far enough from points at + 2-th level.
It remains to find maximum curvature such that the required conditions are satisfied. Let and r' be radii circles at (-th and / + 1-th levels and let 2a = Lupo. We know (the law of cosines and cos 2a = 1 2 sin? 2 a) that
1 R
cosh
+ sinh sin a. R
(10)
And the only condition need for the whole procedure work is that we have enough space the circular are for placing b nodes there:
cosh
+ 2sinh
sin?
R
R
Now we note that sin"
sin b
for all b 2 1. Therefore, sufficient to have
1
< 1 2snh r' sin a
cosh
(11)
R
R
62
Combining Equation T0 and Equation 11 we obtain:
sinh
2 b
sinh r
R
R²
To achieve this, it is sufficient to have:
r'
R > 2 2oog b,
< 2 log
remains to find the lower bound for 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 I to the next one. In this case, r = 1 and
r' = 2 arccosh cosh 1
cosh 1/2
So, we have
2
log b 2 arccosh cosh cosh 1/2
-C
R2
18

---

Under review as a conference paper at ICLR 2020
0:5
0.2
-15
-0.5
0.5
Figure 6: Adding it edges node of a cycle 10 nodes
344
0.5
0:45
035
041
0.3
0.5
doatb1
0.25
04
0.1
585
0.5
-0.5
Da voture
carvouuee
Figure 7: Adding one (left) or two (right) dangling edges to subsequent nodes cycle on 10 nodes
C COMBINATIONS OF SIMPLE GRAPHS
In this section, order to get additional intuition, we illustrate how combining several simple sub- graphs 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 negative, while for other is positive.
Indeed, for trees (and, in particular, stars) the optimal curvature 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, observe such expected behavior for two illustrative examples shown in Figures and 7 In Figure we take a cycle length 10 and iteratively add edges to one its nodes, i.c., we create 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 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.
star
D VOLUME-BASED CURVATURE APPROXIMATION
In this section, describe the proposed curvature approximation. An input parameter of this esti- mator is the maximum neighborhood size kmaz (we fix kmaz = 3 in the experiments). We take node and for any A: kmaz compute the number of nodes N&(v) 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 F&(1)) be the number of non-edges between the pairs of nodes at distance k. Then, we say that N (v) such that (Ni(()) (x)v) Finally, compute the curvature (v) such that the area of hypersphere radius k is equal to (g).).
distance exactly k from
19

---

Under review as a conference paper at ICLR 2020
Table 3: Dataset description
Dataset
num. nodes
num. edges
Karate club
Zachary
1977
34
78
Dolphins
(Lusseau al. 20033
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 [Subelj & Bajec
2011)
1039
1305
EuroSiS [hokhar] (hoKhar]22II] 2015
1272
6424
Power (Watts & Strogatz 1998
4941
6594
Facebook (Leskovec & Mcauley 2012
4039
88234
And our estimate for is c(v) min& Sk (v()) (the worst-case curvature). To get curvature of the whole graph, we take a median of all cs (v). (Similarly to other curvature estimators, one can consider a subsample of nodes instead of the whole node to speed up the computation).
E EXPERIMENTS
E. 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 correspond already filtered dataset). Synthetic The dataset T3,6 is a tree with branching factor 3 and depth 6.
datasets are described in Section 4.3
E.2 THRESHOLD--AA BASEDD LOSS FUNCTIONS
While our theoretical results in Section Thold 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/ ~ oy] ((((()))(())) I]+ 1/v uzl) [dd(f(u), f(1))) 1]
which essentially measures how well the values [(d(f(t))f(;)) 1] approximate I[; Uzl- 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 to consider balanced accuracy instead of accuracy, which leads to balanced zero-one loss:
Eis lv, mz]- [((((())(())) > 1] E., (1 [0, ~ v,l) (v.) S
2 2 [0: ~ Uz]
2 > , [l: ~ vz))
The recent study by Gösgens et al. 2019) analyses the problem of bias discussed above in de- tail. 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 [[e vy] and [[d[(()))(rr)) > 1]. So, we add the corresponding Pearson loss (one minus correlation coeffi- cient) to our experiments (see Goöggens al. 2019)).
E.3 EXPERIMENTAL SETUP
Our experiments are based on publicly available implementation of graph embedding by Gu et al. 2019 The main advantage of this algorithm that works for any curvature: negative, positive
or zero.
20

---

Under review as a conference paper at ICLR 2020
Table 4: Compare eurvature estimators, distortion, synthetic datasets
Ollivier
Forman
Avg.
sectional loss
Grad. descent
Dataset/dim
loss
loss
c
loss
S /
0.0
0.334
-97.0
0.058
-1.0
0.304
-1.45
0.289
S100 10
0.0
0.127
-97.0
0.014
-1.0
0.1
-30.2
0.025
T3.6 /
-0.33
0.136
-2.0
0.254
-0.5
0.174
-9.77
0.271
T..6 / 10
-0.33
0.016
-2.0
0.243
-0.5
0.036
0.0
0.077
1100 /
0.99
0.348
100
0.841
0.125
0.342
-48.7
0.163
K 100 / 10
0.99
0.134
100
0.841
0.125
0.124
-305
0.015
Co00 /2
0.0
0.106
0.0
0.106
0.01
0.257
0.0
0.106
Co00 / 10
0.0
0.106
0.0
0.106
0.01
0.255
0.0
0.106
1000,000 /
0.0
0.372
-19
0.294
0.008
0.372
2.1
0.309
K 100, 10
0.0
0.301
-196
0.275
0.008
0.301
-139
0.27
Table 5: Compare curvature estimators, zero-one loss, synthetic datasets
Ollivier
Forman
Avg.
sectional loss
Grad. descent
Dataset
loss
c
loss
c
c
loss
100 /2
0.0
0.02
-97.0
0.004
-1.0
0.027
0.0
0.02
T3,6 2
-0.33
0.006
-2.0
0.005
-0.5
0.005
0.0
0.002
C100 2
0.0
0.005
0.0
0.005
0.01
0.009
0.16
0.012
K 1000,100 2
0.0
0.496
-196
0.492
0.008
0.496
-531
0.493
K 1100,100 10
0.0
0.489
-196
0.491
0.008
0.480
-124
0.490
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
E1e -.l-(((((())()))))))))) + (1 I[ ~ 1,1) [[) s
This function is not differentiable, so we replace it by gradient descent friendly function which we call ReLuLoss:
Σ 1u 1z] (e)lu(((((())
[[u, v,l)
where ReLu(z)) max(0,xx,e 0.001. In our experiments we observed that such loss function outperforms other analogues (e.g., MSE and sigmoid-base smoothing) since speeds up the con- vergence. To adapt to various threshold-basse loss functions, we also reserve several iterations to gradient steps based on the corresponding sigmoid-bane smoothing.
Note that in experiments we use only the more advanced Forman curvature G(G). For computing Ollivier and Forman curvature we use the open source package by Ni et al. (2015)
For the embedding algorithm, in all experiments we fix epochs 1000 and we also try several learning rates (usually from 0.01 to 10'). We noticed that learning rate significantly affect the per- formance 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 inproves the embedding into Euclidean spaces (otherwise there is a peak in distortion at 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 curvature which minimizes loss function. (It can be also thought as though we focus on graph reconstruction task).
https:: hhtp://ggtttt..ecc com/ bal mars Pears/Graphin wararaphiiiaao caicurrture
21

---

Under review as a conference paper at ICLR 2020
10
0.33
200 bol
0.9
0.2
088
087
0.33
0.83
085
0.3
0.11
-2
1.5
3.5
0.5
-1.5
3.5
2
10
balvned aon-eerr bes
0:15
0.35
0.2
0.55
0.3
0451
0.5
Figure 8: Effect of curvature, Karate club dataset
To plot all the figures 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 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-basee loss function, for less trivial graphs the optimal curvature depends on the particular choice [1
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, c.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-basee losses, we focus 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 given loss function we care about distortion. shows the estimated values of curvature
"https:// /rive..ieee//.
We note that the curves corresponding to threshold-basee losses are noisy, especially for small datasets, since such loss functions discrete and multimodal, they harder optimize. To smooth the results, added several tricks the optimizer and also choose the optimum emhedding based several random restarts algorithm. Although the results are still noisy, general trends are usually clearly seen.
12e value 0.1 appears due to technical reason: in spherical space of large curvature there can be no points distance limit considered curvatures.
22

---

Under review as a conference paper at ICLR 2020
0.43
03
200-0eels
0.75
0.2
607
043
089
-15
-0.5
11.
-15
455
0..
carvdtuc
10
0.3
0.04
0.25
0.12
0.94
-1.
-0.5
D.5
-1.5
-2
-0.5
0.5
Figure 9: Effect of curvature, Dolphins dataset
10
0.3
0.25
0.89
02
0.77
0.35
0.65
1.5
-3.
0.5
-1.5
4.5
0.5
0.15
0.28
0.215
0.25
0.31
0.22
-15
-2.5
115
-15
-0.5
0.5
Figure 10: Effect curvature, Football dataset
23

---

Under review as a conference paper at ICLR 2020
04
4- 10
0.81
0.12
0.1
200-00e
0.3
0.2
0.8
0.15
0.03
-15
-0.5
10.5
-1.
-55
0..
10
0.22
0.4
0.88
0.35
0.66
0.1
5.25
0.22
0.3
-1.5
-0.5
DUS
-1.5
-0.5
10.5
Figure 11: Effect of curvature, Political books dataset
045
10
10
0.15
0.20
0.33
0.12
0.3
0.3
0.8
02
0.6
0.1
0.1
0.02
4.5
435
0.5
-15
4.5
0.5
0.7
10
0.78
0.5
0.53
0.22
0-43
0.35
0.18
0.3
0.03
32
-1.5
-2.5
13.5
-1.5
-0.5
10.5
Figure 12: Effect of curvature, Conflict dataset
24

---

Under review as a conference paper at ICLR 2020
10-0 10
10
0.5
34
049
066
-15
-2
40.
-15
-35
1..
0.35
popsoi
0.49
04
0.
0:15
065
6-2
-15
-1
40.5
0.5
-1.5
-1
-0.5
20.5
Figure 13: Effect curvature, Chicago dataset
-0
10
0.15
24
0.21
0.12
0.3
0.8
0.3
0.6
0.1
0.1
0.22
1.8
4.6
0..
0.2
0.2
0.4
0.5
038
1.5
4.
0.5
0/9
0.4
Llnnaa 200
0.25
04
8/15
6--2
-15
-2
415
055
-1.5
-0.5
20.5
Figure 14: Effect of curvature, CSPhDs dataset
25

---

Under review as a conference paper at ICLR 2020
10
10
0.66
06
0.54
200-00elos
0.12
0.3
000
03
0.8
0.94
0.
0.02
-15
-2
405
0.5
-15
-0.5
1..5
Lal 20000oooeeeooo boo
0.6
0.25
0.5
0.2
04
-15
-3
40.5
0.5
-1.5
-3
-0.5
20.5
Figure 15: Effect of curvature, Euroroad dataset
0.15
4
10
0:15
0.1
0.12
0.35
0.3
0.25
0.2
0.9
0.15
0.2
X-M M4-e-
0.62
4.5
-3.
0.5
-1.5
4.5
0.5
0.8
0.78
0.7
0.5
0.22
0.55
0:45
0/18
0.03
-1.5
-2.5
13.5
-1.5
-2
-0.5
18.5
Figure 16: Effect of curvature, EuroSiS dataset
26

---

Under review as a conference paper at ICLR 2020
0.14
100 koa
0.8
53
0.04
Divoture
0.44
0.47
836
0.30
0.94
balandd
0.3
0.6
0.1
10
carvattue
Figure 17: Effect of curvature, Power dataset
zurveture
Figure 18: Effect of curvature, Facebook dataset, distortion loss
27

---

Under review as a conference paper at ICLR 2020
Table 6: Volume-based curvature
Dataset
d
10
Karate club
-6.7
0.1
Dolphins
-3.3
0.1
Football
-2.1
0.1
Political books
-1.6
0.1
Conflict
-1.8
0.1
Chicago
0.1
0.1
CSPhDs
0.07
0.1
Euroroad
0.1
0.1
EuroSiS
-3.7
0.1
Power
0.1
0.1
Facebook
-11
0.1
One can see that for in many cases significantly negative curvature is predicted which is in- deed confirmed by our experiments, shown in Figures 18 (distortion loss). Non-negative curvature predicted for Chicago, CSPhDs, Euroroad and Power and indeed for these datasets the optimal curvature is close with the experiment well. So, in these cases it is not reasonable to embed networks to a hyperbolic space.
In contrast, for d 10 negative curvature never predicted, which agrees
28


Reviews:
[{"review_id": "rkei-QhAKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a novel notion named glocal graph curvature, which offers a solution to determine the optimal curvature for embedding. In particular, the global graph curvature depends on both dimension and loss function used for the network embedding. Besides, the authors studied the existing local curvatures and show that the existing graph curvatures may not be able to properly capture the global graph structure curvature. Extensive results demonstrate the statements proposed in the paper. In general, I like the paper due to its nice presentation, interesting view of graph curvature, and solid theoretical analysis. However, I am not familiar with graph curvature. All I can say is the approach is intuitively appealing, the text is well written and easy to follow, even for an outsider. I do not know any related works or what to expect from the results. I could not find anything wrong with this paper, but also do not have any intelligent questions to ask. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlybsupKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThis 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.\n\nAll 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.\n\n\nPros, Cons, and Recommendation\n\nThe 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.\n\nAt 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.\n\n\n\nComments:\n- 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.\n\nIf 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.\n\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.\n\n- 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.\n\n- 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.\n\nThe 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.\n\n- Can the authors write out what's going on for the hyperbolic lower bound on D_min in the  proof of Thm. 4.1?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxYwVfw9S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of embedding graphs into continuous spaces.  The emphasis is on determining the correct dimension and curvature to minimize distortion or a threshold loss of the embedding.\n\nPros:\nThe problem is clearly stated and easy to understand.\nThe limitations of the three local curvatures are shown empirically and theoretically\n\nCons:\nExperiments seem inconclusive, with no discussion of the results\nProposed global curvature characterizes the optimal embedding parameters but not a different, efficiently calculable discrete curvature to approximate them\nAnalysis of particular graph families doesn’t necessarily inform what to expect from embedding large graph data\n\nOverall, I lean towards rejecting this paper.  The problem does seem an important one, but it seems the main contribution of this paper is comparing the local curvatures against an oracle for determining optimal curvature in embedding space, without putting forward an alternative method.\n\nQuestions:\nWhy is it reasonable to take these curvature metrics and use them directly as the curvature of the ambient space at all?  Especially given that Ollivier curvature belongs to a small interval and Forman curvature is always negative.\n\nDoes any of the graph family analysis carry over to more general graphs?  For example, assuming some priors about the appearance of these families as subgraphs, or the observed features of real networks in [1]?\n\n[1] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Gharamani. Kronecker graphs: an approach to modeling networks. arXiv:0812.4905v1, 2008.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of embedding graphs into continuous spaces.  The authors focus on determining the correct dimension and curvature to minimize distortion or a threshold loss of the embedding. The authors  consider a variety of existing notions of curvature for graphs, introduce a notion of global curvature for the entire graph, and how to efficiently compute it.

Reviewers were positive about the problem under study, but agreed that the current manuscript somewhat lacks a clear contribution. They also pointed out that the goal of using a global notion of curvature should be better motivated. For these reasons, the AC recommends rejection at this time. 
Decision: Reject