Constant Curvature Graph Convolutional Networks
Authors: Gregor Bachmann
Gary Bécigneul
Octavian-Eugen Ganea
Venue:  (2020)
Keywords: graph convolutional neural networks
hyperbolic spaces
gyrvector spaces
riemannian manifolds
graph embeddings

Abstract:  Interest has been rising lately towards methods representing data in non-Euclidean spaces, e.g. hyperbolic or spherical. These geometries provide specific inductive biases useful for certain real-world data properties, e.g. scale-free or hierarchical graphs are best embedded in a hyperbolic space. However, the very popular class of  graph neural networks is currently limited to model data only via Euclidean node embeddings and associated vector space operations. In this work, we bridge this gap by proposing mathematically grounded generalizations of graph convolutional networks (GCN) to (products of) constant curvature spaces. We do this by i) extending the gyro-vector space theory from hyperbolic to spherical spaces, providing a unified and smooth view of the two geometries, ii) leveraging gyro-barycentric coordinates that generalize the classic Euclidean concept of the center of mass. Our class of models gives strict generalizations in the sense that they recover their Euclidean counterparts when the curvature goes to zero from either side. Empirically, our methods outperform different types of classic Euclidean GCNs in the tasks of node classification and minimizing distortion for symbolic data exhibiting non-Euclidean behavior, according to their discrete curvature. 

Under review as a conference paper at ICLR 2020
CONSTANT CURVATURE GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Interest has been rising lately towards methods representing data in non- Euclidean spaces, e.g. hyperbolic spherical, that provide specific inductive biases useful for certain real-world data properties, e.g. scale-free, hierarchical or cyclical. However, the popular graph neural networks are currently limited in modeling data only via Euclidean geometry and associated vector space operations. Here, we bridge this gap by proposing mathematically grounded generalizations of graph convolutional networks (GCN) to (products of) constant curvature spaces, We do this by i) introducing a unified formalism that can interpolate smoothly between all geometries of constant curvature, ii) leveraging berycerrccettric coordinates that generalize the classic Euclidean concept of the center of mass. Our class models smoothly recover their Euclidean counterparts when the curvature goes zero from either side. Empirically, we outperform Euclidean GCNs in the tasks of node classification and distortion minimization for symbolic data exhibiting non-Euce -unluuciddnn behavior, according to their discrete curvature.
INTRODUCTION
Graph Convolutional Networks. The success of convolutional networks and deep learning for image data has inspired generalizations for graphs for which sharing parameters is consistent with the graph geometry. Bruna et al. (0014): Hennlf et al. (2015) are the pioneers of spectral graph convolutional neural networks in the graph Fourier space using localized spectral filters on graphs. However, in order to reduce the graph-dependency-
the Laplacian eigenmodes, Defferrard et al. (2016) approximate the convolutional filters using Chebyshev polynomials leveraging a result of Ham- mond al. (20TT. The resulting method (diseussed in appendix A is computationally efficient and superior in terms of accuracy and complexity. Further, Kipf & Welling (2017) simplify this approach by considering first-order polynomials approximations obtaining high scalability. The proposed graph convolutional networks (GCN) is interpolating node embeddings via symmetrically normalized adjacency matrix, while this weight sharing can be understood as an efficient diffusion-lif regularizer. Recent works extend GCNs to achieve state of the art results for link prediction (Zhang & Chen 2018), graph classification (Hamilton et al. 2017 Xu et al. 2018) and node classification (Klicpera al. 2019 Veličković et al. 2018).
Euclidean geometry in ML. In machine learning (ML), data is most often represented Eu- clidean space for various reasons. First, some data intrinsically Euclidean, such as positions in 3D space in classical mechanics, Second, intuition is easier in such spaces, as they possess an appealing vectorial structure allowing basic arithmetic and rich theory of linear algebra. Finally, lot of quantities of interest such as distances and inner-products are known in closed-form formulae and can be computed very efficiently on the existing hardware. These operations are the basic building blocks for most of today's 's popular machine learning models. Thus. the powerful simplicity and efficiency of Fuclidean geometry has led to numerous methods achieving state-of-the-an on tasks as diverse as machine translation (Bahdanau et al. 2014 Vaswani et al., 2017), speech recognition (Graves et al.) 2013), image classification (He et al. 2016 or recommender systems (He et al. 2017).
Riemannian ML. In spite of this success, certain types of data (e.g. hierarchical, scale-fre free or spherical data) have been shown to be better represented by non-E -on-Eucldden geometries (Defferrard al. 2019 Bronstein al. 2017 Nickel & Kiela 2017 Gu al. 2019), leading in particular the

---

Under review as a conference paper at ICLR 2020
rich theories of manifold learning (Roweis& & Saul 2000: Tenenbaum al. 2000) and information geometry (Amari & Nagaoka 2007). The mathematical framework in vigor to manipulate non- Euclidean geometries known as Riemannian geometry (Spivak 1979h. Although its theory leads to many strong and elegant results, some of its basic quantities such as the distance function d(., )) are in general not available in closed-form, which be prohibitive many computational methods.
Representational Advantages of Geometries of Constant Curvature. An interesting trade-off between general Riemannian manifolds and the Euclidean space is given by manifolds of constant sectional curvature. They define together what are called hyperbolic (negative curvature), elliptic (positive curvature) and Euclidean (zero curvature) geometries. As discussed below and in appendix [ Euclidean spaces have limitations and suffer from large distortion when embedding certain types of data such as trees, c.g. fig. [ In these cases, the hyperbolic and spherical spaces have representational advantages providing better inductive bias for the respective data.
The hyperbolic space can be intuitively understood as continuous tree: the volume of ball grows exponen- tially with its radius, similarly as how the number nodes in binary tree grows exponentially with its depth. Its tree-likeness properties have long been studied mathemati- cally (Gromov 1987, [Hamann 2017 [Ungar] 20088 and it was proven to better embed complex networks (Krioukov al. 22100), scale-free graphs and hierarchical data com-
pared to the Euclidean geometry (Cho et al. 2019; Sala
al.) 2018: Ganea al. 2018b; Gu al. [019] Nickel
& Kiela, (2118 Tifrea et al. 2019). Several impor- tant tools methods found their hyperbolic counterparts, such as variational autoencoders (Mathieu et al. [2019] Ovinnikov 2019). attention mechanisms (Gulcehre al, 2018), matrix multiplications, recurrent units and multino- mial logistic regression (Ganea et al. 2018a).
Figure 1: Euclidean space quickly "runs out of space" when fitting exponentially volume growing data such as trees. The embedding distance between red the green node keeps decreasing as the number of tree nodes increases, meaning that the graph distance (shortest path length) is longer accurately represented. Details appendix
Similarly, spherical geometry provides benefits for mod- eling spherical or cyclical data (Defferrard et al. 2019)]
Matousek] 2013] Davidson et al.] 2018 Xu & Durrett
2018 Gu et al. 2019 Grattarola et al. 2018 Wilson et al.
2014
Computational Efficiency of Constant Curvature Spaces (CCS). CCS are some of the few
Riemannian manifolds possess closed-form formulae for geometric quantities of interest in computational methods, i.e. distance, geodesics, exponential map, parallel transport and their gradients. We also leverage here the closed expressions for weighted centroids.
"Linear Algebra" of CCS: Gyrovector Spaces. In order study the geometry of constant nega- tive curvature in analogy with the Euclidean geometry, Ungar 1999 2005 2008 2016) proposed the elegant non-associative algebraic formalism of gyrovector spaces. Recently, Ganea al. (2018a) have linked this framework to the Riemannian geometry of the space, also generalizing the building blocks for non -unclidldnnn deep learning models operating with hyperbolic data representations.
However, it remains unclear how to extend in principled manner the connection between Riemannian geometry and gyrovector space operations for spaces of constant positive curvature (spherical). By leveraging Euler's s formula and complex analysis, we present to our knowledge the first unified gyro framework that smoothly interpolates between geometries of constant curvatures irrespective their signs. This is possible when working with the Poincaré ball and stereographic spherical projection models of respectively hyperbolic and spherical spaces.
How should one adapt graph neural networks to non-flat geometries of constant curvature?
In this work, propose constant curvature GCNs model En-llidddd data. Node embeddings lie in spaces constant curvature or product of those instead of a Euclidean space, thus leveraging both the representational power of these geometries and the effectiveness of GCNs.
Concurrent to our work, Chami et al. (2019): Liu et al. (0099) propose hyperbolic graph neural networks using tangent space aggregation.
2

---

Under review as a conference paper at ICLR 2020
Figure 2: Geodesics in the Poincaré disk (left) and the stereographic projection of the sphere (right).
2 THE GEOMETRY OF CONSTANT CURVATURE SPACES
Riemannian Geometry. A manifold M of dimension d is a generalization to higher dimensions of the notion of surface, and is space that locally looks like Rd. At each point E M, M can be associated a tangent space M, which a vector space dimension that can be understood as a first order approximation of M around A riemannian metric g is given by an inner-product 9x( (-.-) at each tangent space M, varying smoothly with x. A given defines the geometry of M, because it can be used define the distance between X and y as the infimum of the lengths of smooth paths y [o, 1] + M from x to y, where the length is defined as {(>) := f' (5()) Under certain assumptions, given g also defines curvalure each point.
Unifying all curvatures n. There exist several models of respectively constant positive and negative curvatures. For positive curvature, we choose the stereographic projection of the sphere, while for negative curvature we choose the Poincaré model which is the stereographic projection of the Lorentz model. As explained below, this choice allows to generalize the gyrovector space framework and unify spaces of both positive and negative curvature x into a single model which we call the s-stereographie model.
The k-stereographic model. For curvature K R and a dimension 2 2, is defined as 5t = fx E R x < 1} equipped with its Riemannian metric gx = (I+^ ix]pa== =: (I
Note in particular that when x: 2 0, st is R while when x < 0 it is the open ball of radius 1/V-k. Gyrovector spaces & Riemannian geometry. As discussed in section [ the gyrovector space formalism used to generalize vector spaces the Poincaré model hyperbolic geometry (Ungar 2005; 2008). In addition, important quantities from Riemannian geometry can be rewritten in terms of the Möbius vector addition and scalar-vector multiplication (Ganea et al. 2018a). We here extend gyrovector spaces to the x-stereographic model, i.e. allowing positive curvature.
For >> 0 and any point st we will denote by X the unique point of the sphere of radius k in Id++1 whose stereographic projection is x. As detailed in appendix C.2.2 it is given by
X (A + 1))-
For x. y E st, define the k-addition, in the s-etrooggaaphic model by:
(1 2nx |y )x (1 x||x| By
st
2xx y + x² x
y
The k-addition is defined in all the cases except for spherical geometry and x = y (1) as stated by the following theorem proved in Appendix C
Theorem 1 (Definiteness of k-addition). We have k > 0 and x (/())yy11?
2xx* y + x x
if and only if
For E R and x stg (and tan, ||x||| < kà m 0), the k-scaling in the x-stereographic model is given by:
tan, (s lan
|x|]
std
[x]
where tan, equals km tan if k and (-x) tanh if x O. This formalism yields simple closed-forms for various quantities including the distance function inherited from the Riemannian manifold (std, )) the exp and log maps, and geodesics, shown by the following theorem.
3

---

Under review as a conference paper at ICLR 2020
Theorem 2 (Extending gyrovector spaces to positive curvature). For x, sth # y, v + 0.
(and -y/(<|ly>])) if K. > 0}, the distance function is given b
yx. = 2|x=| tan x 0x yll,
(4)
the unit-speed geodesic from y is unique and given by 7x--y @x @N @x
(5)
and finally the expomential and logarithmic maps are described as:
(x) x(Bx (Lan, [k|) X
2/x= 2 |v]l (y)
Gr y
lan
|X-x,,
( y
(6)
"We write- x @ y for (-x) + y and not - -xx + y).
Proof sketch:
The case
already taken care of by (Ganea al. 2018a). For O, we provide detailed proof in Appendix C.2.2] The exponential map and unit-speed geodesics are obtained using the Egregium theorem and the known formulas the standard spherical model. The distance then follows
from the formula d,, (x,y) y) =
| log which holds in any Riemannian manifold.
Around x O. One notably observes that choosing x yields all corresponding Fuclidean quantities, which guarantees continuous interpolation between x- s-stereographic models of different curvatures, via Euler's 's formula tan(z) -i tanh(ix) where := v-1. But is this interpolation differentiable with respect to A? It is shown by the following theorem, proved in Appendix C.2.3
Theorem (Smoothness std w.r.t. K. around O), Let v * 0 and x. E Rd, such that y (and x * (xl|l) if > 0). Quantities in Eqs. (45 are well-defined for |s| < 1/ min([|x (ixxx/2,1lxlx [ly)??), iee. for is small enough. Their first order derivatives at O and 0 exist and equal. Moreover, for the distance have:
dn (x) = 2||x yll 2x (|x - 11x--113//
(7)
Note that for x 2 0, this tells that infinitesimal change of curvature from zero to small negative, i.e. towards 0-, while keeping x, fixed, has the effect of increasing their distance.
As consequence, have unified formalism that interpolates smoothly between all three ge- ometries of constant curvature.
K-GNNS
We start by introducing the methods upon which we build. We present our models for spaces of constant sectional curvature, in the x-stereographic model. However, the generalization to cartesian products of such spaces (Gu et al. 2019) follows naturally from these tools.
3.1 GRAPH CONVOLUTIONAL NETWORKS
The problem of node classification on graph has long been tackled with explicit regularization using the graph Laplacian (Weston et al. 2012). Namely, for directed graph with adjacency matrix A, by adding the following term to the loss: Σi, fx)))((x;) f(x,)11 2 f(x) Lf)(), where
L = D A A is the (unnormalized) graph Laplacian, Dü := En A& defines the (diagonal) degree matrix, f contains the trainable parameters of the model and X (a/)s, the node features of the model. Such a regularization is expected to improve generalization if connected nodes in the graph tend to share labels; node with feature vector x; is represented f(x:) in Fuclidean space.
4

---

Under review as a conference paper at ICLR 2020
With the aim obtain more scalable models, Defferrard et al. (2016); Kipf & Welling (011)) propose
to make this regularization implicit by incorporating it into what they call graph convolutional networks (GCN), which they motivate first order approximation of spectral graph convolutions, yielding the following scalable layer architecture (detailed in appendix
H ((++1) (D AD #HOO
(8)
where Á = + has added self-comnections, D.: = Ex As defines its diagonal degree matrix, o is a non- non-linearity such as sigmoid, tanh or RcLU = max(0 -), and W(() and H are the parameter and activation matrices of layer é respectively, with H X the input feature matrix.
3.2 TOoLS FOR K-GCN
Learning parametrized function fo that respects hyperbolic geometry has been studied in (Ganea al., 2018a): neural layers and hyperbolic softmax. We generalize their definitions into the n-stereographic model, unifying operations in positive and negative curvature. We explain how curvature introduces fundamental difference between left and right matrix multiplications, depicting the Möbius matrix multiplication of (Ganea et al. 2018ab right multiplication, independent for each embedding. We then introduce a left multiplication by extension of gyromidpoints which ties the embeddings, which is essential for graph neural networks.
3.3 K- ---RRIIIT--AARRE RRIGIT-MATTLE--MMIPPLLAAAATO
d-dimensional embeddings in sty and let W Rdxe denote a weight matrix. Let us first understand what right matrix multiplication is in Euclidean space: the Euclidean right multiplication can be written row-wise as (XW): X. W. Hence each d-dimensional Euclidean embedding is modified independently by right matrix multiplication. A natural adaptation of this operation the x-stereographic model yields the following definition.
Let X Rexd denote matrix whose
Definition 1. Given matrix X E Raxd holding x-stereographic embeddings in its rows and weights W Raxe, the brighh-matriixmmliilliiaaat defined row-wise as
(I(XX)): tan, ((Ix.xI))
(XW):
W): expo (logg (X)W):.)
ttan
|X..0
[[(W):
where expi and logã denote the exponential and logarithmic map in the k-stereographic model.
This definition is in perfect agreement with the hyperbolic scalar multiplication for x < 0, which can also be written as 60, x = exp, (r (x)). This operation is known to have desirable properties such as associativity (Ganea et al., 2018a).
3.4
K- TEW-MMATRIX--ULPPPIIAATITIE AS A MIDPOINT EXTENSION
For graph neural networks we also need the notion of message passing among neighboring nodes, i.e. operation that combines / aggregates the respective embeddings together. In Euclidean space such an operation given by the left multiplication of the embeddings matrix with the (preprocessed) adjacency A: H(++1) = a (Az()) where z = H (!)) Let us consider this left multiplication. For A gnxn, the matrix product given row-wise by:
(AX): A. X1.
X...
This means that the new representation of node is obtained by calculating the linear combination of all the other node embeddings, weighted by the i-th row of A. An adaptation to the k-stereographic model hence requires notion of weighted linear combination. We propose such an operation in st by performing k-scaling of gyromidpoint whose definition is reminded below. Indeed, in Euclidean space, the weighted linear combination ax ax By can re- written as (a+ +++8)mmm(x y; or, (3) with Euclidean midpoint mz(x, y; 0, == .. x + a.gy.. y. This motivates generalizing the above operation ste as follows.
5

---

Under review as a conference paper at ICLR 2020
Figure 3: Left: Euclidean Linear combination ax + 9y. Middle: Poincaré gyromidpoints (red dots) of two points for different weights on the left and Poincaré gyromidpoints in hyperbolic triangle on the right with two equal and one free weight. Right: Möbius gyromidpoint in the Poincaré model defined by (Ungar 2008) and alternativlly here in eq. (10).
Definition 2. Given matrix X E guxd holding k-stereographic embeddings in its rows and weights A [Raxn, the x-lef-maarix-mmliiiicccaai is defined row-wise as
(A R X):
Σ Aig) Aig) 0x mx
X An Ain).
(9)
The k--scaling motivated by the fact that d,e (0, Ox x) = (0, for all R. x E st We remind that the gyromidpoint is defined when &. S 0 in the x-stereographic model (Ungar 2010
a a5 1xx))
(x1
X,i 01; an)
Øx
Σ
x,
(10)
with X 2 +x|1x|| Whenever x > 0, we have to further require the following condition:
Eas(1 - 1) 00
(11)
For two points, calculate that (Ag 1) (Xg 1) is equivalent to <: x||x|] ||yl| 1, which
holds particular whenever x yy/(w//lll1? See fig. 3 for illustrations of gyromidpoints.
Our operation E, satisfies interesting properties, proved in Appendix C.2.4
Theorem 4 (Neuter element & aiscalar-ssocciativity). We have I, X, X X. and for r E R.
xx (A E X = (rA) B X.
The matrix A. In most graph neural networks, the matrix A is intented to be preprocessed adja- cency matrix, iee. renormalized by the diagonal degreee matrix D Σx A.k- This normalization is often taken either (i) to the left: D (ii) symmetric: D- ADD or (ii) to the right: AD- Note that the latter case makes the matrix right-stochastic which a property that is preserved by matrix product and exponentiation. For this case, prove the following result in Appendix C.2.5 C.2.5
Theorem 5 (s-left-multiplicatio by right-stochastic matrices is intrinsic). If A. B right- stochastic, & is a isometry of st and X, Y are two matrices holding k--stereographic embeddings:
Vi, dx ((A 8 (X)):. (B H ((Y))..) d., & X):. (B8, Y):.).
(12)
The above result means that A can easily be preprocessed as make its c-leff-multiplice intrinsic to the metric space (st d,)). At this point, one could wonder: does there exist other ways to take weighted centroids on Riemannian manifold? We comment two plausible alternatives.
M stochssto if for all E, Mij

---

Under review as a conference paper at ICLR 2020
Fréchet/Karcher means. They are obtained arg minx E, (xd,( x,) note that although they are also intrinsic, they usually require solving an optimization problem which can be prohibitively expensive, especially when one requires gradients to flow through the solution moreover, for the space sty, it is known that the minimizer is unique if and only if x 2 0.
Tangential aggregations. They are defined by lifting the points in a chosen tangent space via the logarithmic map, performing a linear combination and then projecting back via the exponential map, and were in particular used in the recent works of Chami et al. (2019) and Liu et al. (2019). The below theorem describes that for the s-stereographic model, this operation is also intrinsic, Lee. commutes with isometries. We prove it in Appendix C.2.6
Theorem 6 (Tangential aggregation is intrinsic). Define the langential aggregation of ,,,...,,,, st w.E. weights (aihsisn al point E stx (for X; + </(x=||x if 0) by:
Xn. E
n
tg (x1 .. Xa; an, an) = expx
Σ
a log logg
(13)
For any isometry & of st we have
(fo(x)) = (xx;)((x);:
(14)
3.5 LOGITS
Finally, we need the logit and softmax layer, neccessity for any classification task. We here the model of (Ganea et al. 2018a), which was obtained a principled manner for the case negative curvature. We leave for future work the adaptation of their analysis to positive curvature and use in our experiments the straightforwardly adaptated formula to positive curvature, which we detail appendix D
3.6 R-GCN
We are now ready to introduce our s-stereographic GCN (Kipf & Welling 2017)
denoted by K-GCN
Assume we are given a graph with node level features G = (V, A, X) where X E Rxd with each row X. E st and adjacency A Rexx, We first perform a preprocessing step by mapping the Euclidean features to stğ via the projection X + (2/[l | [max),, where | Imax denotes the maximal Euclidean norm among all stereographic embeddings in X. For 1 {0, (O..... L 2), the (I +++ 1)-th layer of k-GCN is given by:
H = 0
80, A 8
H Ox W())),
(15)
where ()) X, o 3r (x) expo (o (x)) is the Möbius version (Ganea al. 2018a of
pointwise non-linearity a and À D AD - The final layer a k-logit layer (appendix D
(L) ()) softmax (A logit, (H((-1), w(w-1))
(16)
where (L-11) contains the parameters a and of the k-logiiss layer. A very important property of R-GCN is that its architecture recovers the Euclidean GCN when we let curvature go to zero:
K-GCN K 00 GCN.
4 EXPERIMENTS
We evaluate the architectures introduced in the previous sections the tasks of node classification and minimizing embedding distortion for several synthetic as well as real datasets. We detail the training setup and model architecture choices to appendix B
To be pronounced "kappa" GCN; the greek letter x being commonly used denote sectional curvature
7

---

Under review as a conference paper at ICLR 2020
Model
Tree
Toroidal Graph
Spherical Graph
GCN (Linear)
0.045
0.0607
0.0415
GCN (ReLU)
0.0502
0.0603
0.0409
0.0029
0.272
0.267
0.473
0.0485
0.0337
HP X HC-GCN
0.0048
0.112
0.152
S
-CCN
0.51
0.0464
0.0359
(H²)
GCN
0.025
0.084
0.062
GCN
0.312
0.0481
0.0378
Table 1: Minimum achieved average distortion of the different models. HH and S denote hyperbolic and spherical models respectively.
Figure 4: Histogram of Curvatures from "Deviation of Parallogram Law"
Minimizing Distortion Our first goal is evaluate the graph embeddings learned by GCN mod- els on the representation task of fitting the graph metric in the embedding space. We desire to minimize
the average distortion, i.e. defined similarly in (Gu et al. 2019: / Ex, ((
((axxa))) -1
where d(x;, x,) is the distance between the embeddings of nodes i and j. while do(1,)) is their graph distance (shortest path length).
We create three synthetic datasets that best reflect the different geometries of interest: i) "Tree"": balanced tree of depth 5 and branching factor consisting of 1365 nodes and 1364 edges. ii) "Torus": We sample points (nodes) from the (planar) torus, i.e. from the unit connected square; two nodes are connected by an edge iff their toroidal distance (the warped distance) smaller than a fixed R 0.01; this gives 1000 nodes and 30626 edges. iii) "Spherical Graph": sample points (nodes) from S?, connecting nodes iff their distance smaller than 0.2, leading to 1000 nodes and 17640 edges.
For the GCN models, use 1-hot initial node features. We and 10. The non- -uclliiide models do not use additional non-loonanne lineariiiiiie between layers. All euclidean parameters updated using the ADAM optimizer with learning rate 0.01. Curvatures are learned using (stochastic) gradient descent and learning rate of 0.0001. All models are trained for 10000 epochs and report the minimal achieved distortion. The results shown in table reveal the benefit of our models. One can notice that estimated curvatures correspond to our geometric knowledge about these specific datasets.
GCN layers with dimensions 16
4.1 NODE CLASSIFICATION
We consider the popular node classification datasets Citeseer (Sen et al. 2008), Cora-ML (McCallum al. 2000) and Pubmed (Namata al. 2012). Node labels correspond the particular subfield the published document is associated with. Dataset statistics and splitting details are deferred to the appendix B due the lack of space.
Curvature Estimations of Datasets To understand how far are the real graphs of the above datasets from the Euclidean geometry, we first estimate the graph curvature of the four studied datasets using the deviation from the Parallelogram Law (Gu et al. 2019) detailed in appendix F Curvature histograms are shown in fig. 4 can be noticed that the datasets are mostly non- -on-Euclidean, thus offering good motivation apply our constant-curvauree GCN architectures.
8

---

Under review as a conference paper at ICLR 2020
Model
Citeseer
LL
Pubmed
MS Academic
GCN (ReLU)
75.7 # 0.36
83.31 = 0.36
79.05 0.52
92.14 = 0.25
GCN (Linear)
76.28
0.30
83.81 # 0.35
78.94 = 0.50
92.3 0.21
HI44-GCN
76.29 +: 0.3
83.6 0.34
79.01 + 0.58
92.06=0.22
76.18 1 0.37
83.97 1: 0.31
79.04 1: 0.5
92.110.31
Prod-GCN
75.91 1 0.34
82.9 1 0.6
78.7 0.53
91.9 1 0.40
Table 2: Node classification: Average accuracy across 10 splits with estimated uncertainties at 95 percent confidence level via bootstrapping on our datasplits. H and & denote hyperbolic (Poincaré ball model) and spherical (stereographic projection) models respectively.
Training Details We trained the Euclidean models with the hyperparameters chosen as reported hidden layer of size 64, dropout the
in (Kliepera al. 2019). Namely, for GCN embeddings and the adjacency of rate 0.5 as well as I/-regularization for the weights of the first layer with À 0.02. Only for Cora-ML had adjust the regularization factor À to 0.002 to ensure similar scores as achieved in (Klicpera et al. 2019).
All -uclldenn models use biased-L2 regularization with 10 and X = 2e 2. Euclidean models used L2 regularization with the same parameter X. We used a combination of dropout and dropconnect for the Euclidenn models. All models have the same number of parameters. We use 2 GCN layers, hidden dimension 64. Product models split hidden dimension into [32, 32] and also input features equally. Non-Euclidean models do not use additional non-linearities. Euclidean parameters use a learning rate of 0.01 for all models using ADAM. The curvatures are learned using gradient descent with learning rate of 0.01. We show the values of the learned curvatures in appendix B We use early stopping: first train for a maximum of 2000 epochs, then we check every 200 epochs for improvement in the validation cross entropy loss; that is not observed, we stop.
Node classification results. These are shown in table 2 competitive with the two Euclidean GCN considered (with or without non- non-lincarities), showcasing the benefit of our proposed architecture.
can be seen that our models are
CONCLUSION
In this paper, we introduced natural extension of graph convolutional networks to the stereographic models of both positive and negative curvatures a unified manner. We show how this choice of models permits to smoothly interpolate between positive and negative curvature, allowing the curvature of the model to trained independent an initial sign choice. We hope that our models will open new exciting directions into non -uc-Eucidd graph neural networks.
REFERENCES
Sami Abu-E -ou-EE--Be El-Haija, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification. International Workshop on Mining and Learning with Graphs (MIG),, 2018
Shun-ichi Amari and Hiroshi Nagaoka. Methods of information geometry, volume 191. American Mathematical Soc., 2007.
Dzmitry Bahdanau. Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint MXXiv:1409.047. 2014.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 2017.

---

Under review as a conference paper at ICLR 2020
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally con- nected networks on graphs. In International Conference on Learning Representations (ICLR2014), CBLS, April 2014, pp. opep-oopere 2014.
Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. arXiv preprini urXiv:1910. 12933,, 2019.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. ICLR, 2018.
Hyunghoon Cho, Benjamin DeMeo, Jian Peng, and Bonnie Berger. Large-margin classification in hyperbolic space. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1832-1840, 2019.
Tim Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M. Tomezak. Hyperspherical Variational Eatto-Encdders Uncertainty in Artificial Intelligence (UAI), 856- 865, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Michaël Defferrard, Nathanaël Perraudin, Tomasz Kacprzak, and Raphael Sgier. Deepsphere: towards an equivariant graph-based spherical cnn. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. /tLp:t/s::// http://aavvvvv.. org abtp///../999..... 05144
Michel Deza and Monique Laurent. Geometry of Cuts and Metries. Springer, Vol. 15, 1996.
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Advances in neural information processing systems, pp. 5345-5355, 1355,20115 2018a.
Octavian- Eugen Ganea, Gary Beeigneul, and Thomas Hofmann. for learning hierarchical embeddings. In International Conference Machine Learning, pp- 1641, 2018b.
Hyperbolic entailment cones
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. Proceedings of the International Conference on Machine Learning, 2017.
Daniele Grattarola, Daniele Zambon, Cesare Alippi, and Lorenzo Livi. Learning graph embeddings on constan--crrvtuure manifolds for change detection in graph streams. stat, 1050:16, 2018.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing. pp. 6645-6649. IEEE, 2013.
Mikhael Gromov. Hyperbolic groups. In Essays in group theory, pp. 75-263. Springer, 1987.
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning in product spaces. Proceedings of the International Conference on Learning Representations, 2019.
representations
Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, et Hyperbolic attention networks. Proceedings of the International Conference on Learning Representattinss, 2018.
Matthias Hamann. On the tree-likeness of hyperbolic spaces. Mathemutical Proceedings of the Cambridge Philosophical Society, pp. 1-17, 2017. doi: 10.1017/50305004 17000238.
Matthias Hamann. On the tree-likeness of hyperbolic spaces. Mathematical Proceedings of the Cambridge Philo- sophical Society, pp. 117, 2017.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Representation Learning Large Graphs. Advances in Neural Information Processing Systems, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 1092):12--150, 2011.
10

---

Under review as a conference paper at ICLR 2020
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web, pp. 173-182, International World Wide Web Conferences Steering Committee, 2017.
Mikael Henaff, Joan Bruma, and Yann LeCun. Deep convolutional networks on graph-structure data. arXiv preprint arXiv: 556600163, 2015.
Diederik P. Kingma and Jimmy Ba. ADAM: A method for stochastic optimization. ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: graph neural networks meet personalized pagerank. International Conference on Learning Representa- lions, 2019.
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. arXiv preprint arXiv:19I0. 1910.1282, 2019.
Emile Mathieu, Charline Le Lan, Chris J Maddison, Ryota Tomioka, and Yee Whye Teh. Hierarchical representations with poincar 'e variational auto-encoders. arXiv preprint arXiv:1901.06033 2019.
Jiri Matousek. Lecture notes metric embeddings. 2013.
Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven Active Surveying for Collective Classification. International Workshop on Mining and Learning with Graphs (MLG), 2012.
Maximilian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. International Conference on Machine Learning. 2018.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. In Advances in Neural Information Processing Systems, pp. 6341-63500 2017.
Ivan Ovinnikov. Poincar 'e wasserstein autoencoder. arXiv preprint 1rXiv:1901.01427, 2019.. 2019.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding.
science, 290(5500):2323-- 2326, 2000.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoff's for hyperbolic embeddings. International Conference on Machine Learning, pp. 4457-4466, 2018.
Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. International Symposium Graph Drawing, pp- 355-366. Springer,, 2011.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lisa Getoor, Brian Gallagher, and T. Eliassi-Rad. Collective Classification in Network Data. Al Magazine, 29(3):93-106, 2008
Michael Spivak. A comprehensive introduction to differential geometry. volume four. 1979.
Joshua B Tenenbaum, Vin De Silva, and John C LLngford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):211-22222 2000.
Alexandru Tifrea, Gary Bécigneul, and Dotavvan-EEugn Ganea. Poincaré glove: Hyperbolic word embeddings. Proceedings of the International Conference Learning Representations, 2019.
11

---

Under review as a conference paper at ICLR 2020
Abraham Ungar. Barycentric Calculus in Euclidean and Hyperbolic Geometry. World Scientific, ISBN 9789814304931, 2010.
Abraham A Ungar. The hyperbolic pythagorean theorem in the poincaré disc model of hyperbolic geometry. The American mathematical monthly, 106(8):55--733 1999.
Abraham A Ungar. Analytic hyperbolic geometry: Mathematical foundations and applications. World Scientific, 2005.
Abraham Albert Ungar. A gyrovector space approach to hyperbolic geometry. Synthesis Lectures Mathematics and Statistics, 1(1):1-194, 2008.
Abraham Albert Ungar. Analytic Hyperbolic Geomelry in N Dimensions: An Introduction. CRC Press, 2014.
Abraham Albert Ungar. Novel tools to determine hyperbolic triangle centers. In Essays in Mathemat- ics and its Applications, pp. 563-666366 Springer, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances in neural information processing systems, pp. 1998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In Neural Networks: Tricks of the Trade, pp. 639-655, Springer, 2012.
Richard C Wilson, Edwin Hancock, Elăbieta Pekalska, and Robert PW Duin. Spherical and hyperbolic embeddings of data. IEEE transactions pattern analysis and machine intelligence, 36(11):2255-2)) 2269, 2014.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey graph neural networks. arXiv preprint arXiv: 2019.
Jiacheng Xu and Greg Durrett. Spherical latent spaces for stable variational autoencoders. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 4503-4513, 2018
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, 2018.
12

---

Under review as a conference paper at ICLR 2020
A GCN A BRIEF SURVEY
A.1 CONVOLUTIONAL. NEURAL NETWORKS ON GRAPHS
One of the pioneering works on neural networks in non nuc-luulid domains was done by (Defferrard et al. 2016). Their idea was to extend convolutional neural networks for graphs using tools from graph signal processing.
Given graph G = (V. where A is the adjacency matrix and V is set of nodes, we define signal on the nodes of graph be a vector x E R" where z; is the value of the signal at node i. Consider the diagonalization of the symmetrized graph Laplacian L UAU"", where The eigenbasis U allows to define the graph Fourier transform x = U E RR.. In order to define a convolution for graphs, we shift from the vertex domain the Fourier domain:
diag(A (A....... An).
G y U ((U*x) (U"y))
Note that x = U x and y = Y y are the graph Fourier representations and we use the element-wise product @ since convolutions become products in the Fourier domain. The left multiplication with U maps the Fourier representation back to a vertex representation. As consequence, signal x filtered by go becomes y Ugo (A)(AU where ge diag(O) with 8 E R" constitutes a filter with all parameters free to vary. In order to avoid the resulting complexity (n), (Defferrard et al. 2016) replace the non-parametric filter by polynomial filter:
go (A)
Σ O4A
where E IR resulting a complexity O(K). Filtering a signal is unfortunately still expensive since y Uge (A) 2 requires the multiplication with the Fourier basis U, thus resulting in complexity On?)). As a consequence, (Defferrard et al., 2016) circumvent this problem by choosing the Chebyshev polynomials Ta as polynomial basis, (A) Σk= (ATx((A where À = 2A - I.
Amus
As consequence, the filter operation becomes y Σx=o k= (L)xx where Anuus
2L I. This
led to a K-localized filter since it depended on the K'thh power of the Laplacian. The recursive nature of these polynomials allows for an efficient filtering of complexity to an computationally appealing definition of convolution for graphs. The model can also be built in an analogous way to CNNs, by stacking multiple convolutional layers, each layer followed by a non-linearity.
(E), thus leading
A.2 GRAPH CONVOL.TIONNAL NETWORKS
Kippf & Welling 2017) extended the work of (Defferrard ct al. 2016) and inspired many follow-up
architectures (Chen et al. 2018 Hamilton al. 2017 7 A Hajja et al. 2018 Wu et al. 2019). The core idea of (Kipf & Welling 2017) is to limit each filter to 1-hop neighbours by setting leading to a convolution that is linear in the Laplacian L:
ge x f,x + L,
They further assume Amar Rs 2, resulting the expression
* x 0,x - 0, D AD AD- 1x
To additionally alleviate overfitting, Kipf Welling 2017) constrain the parameters as 9g 00 0, leading to the convolution formula
9o 0 D AD- 1
Since I D $ AD-
has its eigenvalues in the range [0, 2), they further employ a reparametrization trick to stop their model from suffering from numerical instabilities:
go x - AD bx
where Ā A + and D.g =E À.g.
13

---

Under review as a conference paper at ICLR 2020
Rewriting the architecture for multiple features X E Rexd and parameters c R xd2 instead of X E IR and E R, gives
= = xe Raxd
The final model consists of multiple stacks of convolutions, interleaved by non-linearity a: H = a (D - (
where H X and θ E Ruxds,
The final output H(K) Raxdx represents the embedding of each node as h, Hi E Rdx and can be used to perform node classification:
= softmax
((()) E Rrxx..
where W E 1RdxXL, with L denoting the number of classes.
In order to illustrate how embeddings of neighbouring nodes interact, it is easier to view the architec- ture on the node level. Denote by (i) the neighbours of node i. One can write the embedding of node i at layer as follows:
(R) h
h
(++1)
O
Σ
VIGINN JEN.U()
Notice that there is no dependence of the weight matrices ( on the node i, in fact the same parameters shared across all nodes.
In order to obtain the new embedding h (k+1) of node i, we average over all embeddings of the neighbouring nodes. This Message Passing mechanism gives rise to very broad class of graph neural networks (Kipf & Welling 2017] Veličković et al. 2018 Hamilton et al. 2017 Gilmer et al.
2017 Chen al. 2018 Klicpera al. 2019 Abu-El-Haija al. (0018).
To be more precise, GCN falls into the more general category of models the form
(k+1) AGGREGATE () (fh) : E N(();
2 (1++1 COMBINE (1. 2; (k+1); ((k))
hg
Models of the above form are deemed Message Passing Graph Neural Networks and many choices for AGGREGATE and COMBINE have been suggested in the literature (Kipf & Welling 2017)
Hamilton et al. 2017 Chen et al. 2018)
B GRAPH EMBEDDINGS IN NON-EUCLIDEAN GEOMETRIES
In this section we will motivate non Son-Euclidean embeddings of graphs and show why the underlying geometry of the embedding space can be very beneficial for its representation. We first introduce measure of how well graph is represented by some embedding f - X, i + f()):
Definition 3. Given an embedding f + X, i i f(i) of a graph G = (V, A) in some metric such that
space X, we call f D-embedding for D N if there exists
r-da(i.)) < (x (()) < D.r de(i,j)
The infimum over all such D is called the distortion of f-
The r in the definition of distortion allows for scaling of all distances. Note further that perfect embedding is achieved when D = 1.
B. TREES AND HYPERBOLIC SPACE
Trees are graphs that do not allow for a cycle, in other words there is no node i V for which there exists path starting from i and returning back without passing through any node twice. The
14

---

Under review as a conference paper at ICLR 2020
Figure 5: Euclidean embeddings trees different depths. All the four most inner circles are identical. Ideal node embeddings should match in distance the graph metric, e.g. the distance between the pink and green nodes should the same as their shortest path length. Notice how we quickly run out of space, c.g. the pink and green nodes get closer opposed to farther. This issue is resolved when embedding trees in hyperbolic spaces.
number of nodes increases exponentially with the depth of the tree. This is property that prohibits Euclidean space from representing space". Consider the trees depicted in fig. []] Here the yellow nodes represent the roots of each tree. Notice how rapidly we struggle find appropriate places for nodes in the embedding space because their number increases just too fast.
accurately. What intuitively happens that "we run out of
Moreover, graph distances get extremely distorted towards the leaves of the tree. Take for instance the green and the pink node. In graph distance they are very far apart as one has to travel up all the way to the root node and back to the border. In Euclidean space however, they are very closely embedded in Le-sense, hence introducing a big error in the embedding.
This problem can be very nicely illustrated by the following theorem:
Theorem 7. Consider the tree K1,3 (also called 3-star) consisting of a root node with three children. Then every embedding [II....,IA]] with I; E R achieves at least distortion 2 for any k E IN.
73
Proof. We will prove this statement by using special case of the called Poincaré-type inequali- ties (Deza Laurent 1996):
For any .......br by e R with Σt= b, and points 21,..., 2i E R holds that
b,byllz, 1, 50
Consider now an embedding of the tree 21...., where represents the root node. Choosing 6 -3 and 6; for فf 1 leads to the inequality
||ا x3| + ||ح - 2=112 + ||>3 2a < 3| - r2l12 + 3| - xall2 3||21 - xall?
The left-hand side of this inequality in terms of the graph distance is
do(23)²² + (2, (3 4)2 = 2 + 2 + 2 =
and the right-hand side is
3 dc 2)2 3 (1. +3 (1, 3
12 As result, we always have that the distortion is nower-bounder by V
2
Euclidean space thus already fails to capture the geometric structure of a very simple tree. This problem can be remedied by replacing the underlying Euclidean space by hyperbolic space.
Consider again the distance function the Poincaré model, for simplicity with
||
y/1
dp(ar, y) = cosh -1
1 +
[1
1|
15

---

Under review as a conference paper at ICLR 2020
Assume that the tree is embedded in the same way in fig. 5 just restricted to lie in the disk of radius 1 = 1. Notice that as soon as points move closer to the boundary [|æl + 1), the fraction V2
explodes and the resulting distance goes to infinity. As result, the further you move points to the border, the more their distance increases, exactly nodes on different branches are more distant to each other the further down they are in the tree. We can express this advantage in geometry in terms of distortion:
Theorem 8. There exists an embedding 2 F4 P2 for K1,3 achieving distortion + e f 0 arbitrary small.
Proof. Since the Poincaré distance is invariant under Möbius translations we can again assume that T1 = 0. Let us place the other nodes on a circle of radius Their distance to the root is now given as
d>(;;; 0) cosh -1 (1 ||,111 |.;||
cosh -1 (1 (1+2 1-
r²
By invariance of the distance under centered rotations we can assume w.l.o.g. x2 = (r:0). We further embed
Z3 = (r cos( sin( (zT) = --- v3
34 (r x) rin((
=(-% 2' v3 r)
This procedure gives:
3r 2: - (
/ 112
3r
dr(22, xz) cosh
1+2
cosh
++2
(1-
22
If we let the points now move to the border of the disk we observe that
cosh -1 (1+ 2 3p2 (1-13)
-11
2
cosh
1 + 2 2-
But this means in turn that we can achieve distortion + e for arbitrary small. QED.
The tree- likeliness of hyperbolic space has been investigated on deeper mathematical level. (Sararr 201T) show that similar statement as in theorem 8 holds for all weighted or unweighted trees. The
interested reader is referred to (Hamann 2017 Sarkar 2011 for a more in-depth treatment of the subject.
Cycles are the subclasses graphs that are not allowed in a tree. They consist of one path that reconnects the first and the last node: (Vi,..., Ony 01). Again there is very simple example of cycle, hinting at the limits Euclidean space incurs when trying to preserve the geometry of these objects (Matousek 2013).
Theorem 9. Consider the cycle G (V, of length four. Then any embedding (z1,...,,Ia) Jy & achieves at least distortion 22.
I.) where
Proof. Denote by æ1, 22, 33, I4 the embeddings Euclidean space where I1, 43 and æ2, 24 are the pairs without edge. Again using the Poincaré-type inequality with by by and by bu -1 leads to the short diagonal theorem (Matousek) 2013):
||| - xal + ||-e r= < ||| - x222² + || xall² + ||: - sall2 + || x: ||
The left hand side of this inequality in terms of the graph distance is dc, + do 4)2
2 2 and the right hand side is 1 + 12 + 1 + 1 4. Therefore any embedding has to shorten one diagonal by least factor v2.
16

---

Under review as a conference paper at ICLR 2020
It turns out that in spherical space, this problem be solved perfectly in one dimension for any cycle.
Theorem 10. Given cycle G = (V, F.) of length n, there exists an embedding ;
Fn
achieving distortion
Proof. We model the dimension spherical space as the circle St, Placing the points at angles 2 and using the arclength on the circle as the distance measure leads to an embedding of distortion 1 as all pairwise distances are perfectly preserved.
Notice that could also the exact embedding in the two dimensional stereographic projection model with c= and we would also obtain distortion 1. The difference to the Poincaré disk that spherical space is finite and the border does correspond infinitely distant points. We therefore have no since we do not have to pass to a limit.
C SPHERICAL SPACE AND ITS GYROSTRUCTURE
Contrarily to hyperbolic geometry, spherical geometry not only violation with the fifth postulate of Euclid but also with the first. Notice that, shortest paths are not unique as for antipodal (oppositely situated) points, we have infinitely many geodesies connecting the two. Hence the first axiom does not hold. Notice that the third postulate holds as stated it but it is sometimes also phrased as: "A circle of any center and radius can be constructed". Due to the finiteness of space we cannot have arbitrary large circles and hence phrased that way, the third postulate would not hold. Finally, we replace the fifth postulate by:
Given any straight line / and point not on I, there exists no shortest line passing through but never intersecting!.
The standard model of spherical geometry suffers from the fact that its underlying space depends directly the curvature through hard constraint -x(x, x) = 1 (similarly to the Lorentz model of hyperbolic geometry). Indeed, when + 0, the domain diverges to a sphere of infinite radius which well defined.
For hyperbolic geometry. we could circumvent the problem by moving to the Poincaré model, which the stereographic projection of the Lorentz model, relaxing the hard constraint to an inequality. A similar solution is also possible for the spherical model.
C.I STEREOGRAPHIC PROJECTION MODEL OF THE SPHERE
In the following construct model in perfect duality to the construction of the Poincaré model. Fix the south pole (0, +z) of the sphere of curvature 0, i.e. of radius R -- 22 The stereographic projection is the map:
Φ : S
R
1 VEX X1.
with the inverse given by
8m SR.
+ x'=
\Sx,
(25 -1)
where we define Xę -
Again we take the image of the sphere St under the extended projection (,0....,, -,)) = 0. leading to the stereographic model of the sphere. The metric tensor transforms as:
2 8zg
17

---

Under review as a conference paper at ICLR 2020
C.2 GYROVECTOR SPACE IN THE STEREOGRAPHIC MODEL
C.2.1 PROOF OF THEOREM I
Using Cauchy-Schwarae inequality, we have A := 1=11- 1 2xx + +
y
2 - 2/x² ||||||||||+
x²1 ||||||| = (1 |+|||>|||)>) 2 O. Since equality in the Cauchy-Sethi -Schwarz inequality only
reached for colinear vectors, we have that A = 0 is equivalent to K > 0 and x ll
C.2.2 PROOF OF THEOREM 2
Let us start by proving that for x E R" and v E TR" the exponential map is given by
X (cos,, (A (vl) VFX [M sin, (A& x + Jे sin, (A Ii
exp
(17)
1+ (x+ - 1) cos (v VRASx"
| sin, (*]l|v]))
Indeed, take a unit speed geodesic "xx (t) starting from x with direction v. Notice that the unit speed geodesic on the sphere starting from x' E 3"-1 is given by Txx, (t) = x' cos (t) + yr sin, (t)v'. By the Egregium theorem, know that (())x.vtt) is again unit speed geodesic in the sphere (x* J/ (Ax
where $-1 x x'
1)). -1)-1) Hence (()) is of the form of I for some x' and
v'. We can determine those by
x = Φ (-(() Φ (x)
(*xx,
VR (1 -1)
1
v' (0(0) aΦ (y)
(0){(())) (0))(0)
Notice that Vx = =x(2))² x and we thus get
-2x -2x(A)) vx AEv
~VR(2g33
We can obtain %x.v again by inverting back by calculating (x. (t) = 4 x .v (t)). resulting in (1) (X (ts).() (t) VR(AX)2x sin, (t))x J X sin (t)v
1 (>g 1) co8 (t) /n((2 (x(22)xx 2x7 sin, (t)
Denoting gx (v. v) = =||v|12AG we have that exp 7x, Vegiveji
(VoX(v, vv) which concludes
the proof of the above formula of the exponential map. One then notices that it can be re-written in terms of the k-addition. The formula for the logarithmic map is easily checked by verifying that is indeed the inverse of the exponential map. Finally, the distance formula is obtained via the well-known identity d, (x. y) logx (y) ll where ||v||x = (v.
Note that as expected, (v) ~ x + converging to the Euclidean exponential map.
C.2.3 PROOF OF THEOREM 3
We first compute a Taylor development of the k-addition w.r. around zero:
(1 - 2xxT y (1
x +x y
(18)
1 - +
= [(1 2nxx"y y - (1 + y
(19)
= (1 2nx y -
2 0(k2)
(20)
= (1 x)|y|13)x 2 O(k))
(21)
= + y + + (((²))
(22)
18

---

Under review as a conference paper at ICLR 2020
We then notice that using the Taylor of | l12, given by ||x + vl12 ||||| + (x. + (11v1))) for
v + O, we get
|xx xx yll = |x + y + NO x y |y x + 2(x y)y, + x) +
(23)
= x + y + x x y)
x + +
(24)
Finally Taylor developments of tan (1s| u) and |x| tan (1) w.r.t A around 0 for fixed yield
For x - 0*, (an = - - ( u)
(25)
= + w²/ (k
(26)
u KU 13+0
(27)
For - 0 (Ix (-x) tanh tanh((-x))
(28)
= =(-k) - (-
(29)
= =u + ku / 0
(30)
The left and right derivatives match, hence even though + |x| 2 is not differentiable k the function >> tan, (1s Au) is. similar analysis yields the same conclusion for k: | tan (n)
yielding
For -0 0, [x]] |x|- Lan '(u) = u /3 O(²)).
(31)
Since composition of differentiable functions differentiable, we consequently obtain that &x. exp", log" and dx are differentiable functions of K. under the assumptions on x, v stated in Finally, the Taylor development of d, follows by composition of Taylor developments:
Theorem 3
dn yx, 2||x=|| 1 Lan,"" (II(-x) @x yll)
=[[[|x yll <(--<( y)|| -yl (x/3) - yll + 0(k)) + O(x²)
-2(||x y + y)]
y) -11 (x/3)]|x-yll + 0(x3)
=2||x yll 2x ((x" y) x - -y11 + ||x - /111/3 + (13))
C.2.4 PROOF THEOREM
If A In then for all i we have E3 Ai 1. hence
(I, X X)i
8x
Σ
Siz Six (A -1) 1)x3
(32)
2
1
X
0x
(M% - 1) Xi
(33)
2
&N
(2 8x xx)
(34)
X;
(35)
(X):..
(36)
For associativity, we first note that the gyromidpoint is unchanged by scalar rescaling of A. The
property then follows by scalar associativity of the k-scaling.
C.2.5 PROOF OF THEOREM 5
It is proved in (Ungar 2005) that the gyromidpoint commutes with isometries. The exact same proof holds for positive curvature, with the same algebraic manipulations. Moreover, when the matrix A is stght-stochastte, for each row, the sum over columns gives 1, hence operation E, reduces to gyromidpoint. As a consequence, our H commutes with isometries in this case. Since isometries preserve distance, we have proved the theorem.
19

---

Under review as a conference paper at ICLR 2020
C.2.6 PROOF OF THEOREM
We begin our proof by stating the left-cancellation law:
(xx (-x 4xx y) y
(37)
and the following simple identity stating that orthogonal maps commute with x-addition
Rx @ Ry R(x ex y), VR E O(d)
(38)
Next, generalize the gyro operator from Möbius gyrovector spaces defined in Ungar 2008
gyr [1, vjw == - -u the v) (x (u tx (v Bx w))
(39)
Note that this definition applies only for u, v, w st for which the x-addition is defined (see theorem Dp. Following Ungar (2008), we have an alternative formulation (verifiable via computer algebra):
gyr(u, vjw + Au + Bv
(40)
where the quantities A, B, have the following closed-form expressions:
A = - x² (u, w)llv|/ <<V, w) + 2x (u, v) (v. w),
(41)
B = (== (Vlll)/lull++x( w)
(42)
D 2x v) + +
(43)
We then have the following relations:
Lemma 11. For all u, v, w E sty for which the k-addition is defined we have the following relations: i) gyration is a linear map, ii) u Ox gyr (z, u @x v), iv) ||gyriu, v] v|wl| ||w]]
gyr(u, v)(v @xx u), fii) -(z 0x u) +x (z 3R v)
Proof. The proof is similar with the for negative curvature given in Ungar (2088. The fact that gyration is a linear map can be easily verified from its definition. For the second part, we have
-gyriu, v](ve..)) u) gyr|u, ( = - @D (u (ve, (V-@@vOO))))))
(u v) (44)
where the first equality is trivial consequence of the fact that gyration is linear map, while the last equality is the consequence of cancelllelll law.
The third part follows easily from the definition of the gyration and the left-cancellation law. The fourth part can be checked using the alternate form in eq. (40).
We now follow Ungar 2014) and describe all isometries of st spaces: Theorem 12. Any isometry & of ste can be uniquely written as:
((x)= Dr Rx, where st R E ((d)
(45)
The proof is exactly the same in theorems 3.19 and 3.20 of Ungar 2014). so we will skip it.
We can now prove the main theorem. Let d(x) = 2 θ Rx be any isometry of ste, where E (d)
is an orthogonal matrix. Let us denote by v Σi= ag log (x,). Then, using lemma II and the formula of the log map from theorem one obtains the following identity:
X 1500
as log (0(x:)))
=
gyr/z, Rx
(46)
20

---

Under review as a conference paper at ICLR 2020
and, thus, using the formula of the exp map from theorem 2 we obtain:
(x)()) (10(x;)); (a.)) o(x) 0x gyr|z. (x|R(
( (x ex))
(47)
Using eq. (39) we get that
gyrlz, RxjRw = -Ø(x) BN (z BN (Rx 3x Rw)), Vw E st
(48)
giving the desired
t0 (ol = BN (exp2(v) (tox((xx): (ai)))
(49)
D LOGITS
The final element missing in the k-GCN is the logit layer, necessity for any classification task. We
here use the formulation of (Ganea al. 2018a). Denote by {1...., ...,,,K K} the possible labels and let
ag E Rd, by E R and The output of feed forward neural network for classification tasks is usually of the form
ply x softmax((au, x) by)
In order to generalize this expression to hyperbolic space, the authors of GGanea et al. 201 2018a) realized that the term in the softmax can rewritten
(ac,
x) by sign( (ak x) bw)l |axx|d(xxx, Har,)))
where Ha.b (x E Rd (x, a) b 0} {x e R2 (-p + x. a) 0} Ha.p with p Rd.
As first step, they define the hyperbolic hyperplane as
A {x E st o a) = 0}
where now a E Tpst and p E st They then proceed proving the following formula:
2 -v 3. x, a>
dx, Happ)
V-K sinh-
(50)
(1 + x|| - p 3x x a|l
Using this equation, they able to obtain the following expression for the logit layer:
||aullpe sinh-' ( (1+ P Ox x|13)
(
2V-K( (-
Pk 4r an)
ply k|x) softmax
(51)
V-K
where as E Tost RRd x st and Ps E st Combining all these operations leads to the definition of a hyperbolic feed forward neural network. Notice that the weight matrices W and the normal vectors a, live in Euclidean space and hence can optimized by standard methods such as ADAM (Kingma & Bal 2015).
For positive curvature k > 0 we use in our experiments the following formula for the softmax layer:
||ae|lpx V
sin -1 ( 2 2 Pk Br x, ax)
ply = k//) softmax
(52)
(1+ x|| Pk + x
x ag
which is inspired from the formula sin((z) = sinh(ix) where := V However, we leave for future work the rigorous proof that the distance geodesic hyperplanes in the positive curvature setting is given by this formula.
E MORE EXPERIMENTAL DETAILS
We here present training details for the node classification experiments.
We closely follow the training and evaluation scheme from previous work, e.g. (Klicpera et al. 2019). We split the data into training, early stopping, validation and test set. Namely we first split the dataset into a known subset of size Tikoown and an unknown subset consisting of the rest of the nodes. For
21

---

Under review as a conference paper at ICLR 2020
Dataset
Type
Classes
Features
Nodes
Edges
Label rate
Avg sp
Citeseer
Citation
6
3703
2110
3668
0.036
9.31
Cora-ML
Citation
2879
2810
7981
0.047
5.27
Pubmed
Citation
500
19717
44324
0.003
6.34
MS-Academic
Co-author
15
6805
18333
81894
0.0016
5.34
Table Summary statistics for the four datasets, where sp denotes shortest path.
cisseer Degriss Hatogrittogmm
cora mmi Degriso
PIMM
546
422
400
303
300
355
100
322
30
15
16
40
Doggns
Degros
p.fomeed Reggree-lltttpammm
MS-Aradiemiz Deg tee oeertamm
1750
1500
2000
4000
500
Figure 6: Histogram of node degrees
7kkoow 1500 except for MS Academics, where use 7enoown 5000. The known subset is further split into a training set consisting of 20 data points per label, an early stopping set of size 500 and validation set of the remaining nodes. Notice that the whole structure of the graph and all the node features are used in an unsupervised fashion since the embedding of training node might for instance depend the embedding of a node from the validation set. But when calculating the loss, we only provide supervision with the training data.
all the graphs
The unknown subset serves as the data and is only used for the final evaluation of the model. Hyperparameter-tune teringunng is performed on the validation set. We further use early stopping in all the experiments.
We stop training as soon as the early stopping cross entropy loss has not decreased in the last Rpatience 200 epochs as soon as we have reached Amaas 2000 epochs. The model chosen is the one with the highest accuracy score on the early stopping set. For the final evaluation we test the model 10 different data splits and report mean accuracy and bootstrapped confidence intervals. We use the described setup for both the Euclidean and non-Euclinn non-Euclidean models to ensure a fair comparison.
Learned curvatures
Citeseer:
Hyp GCN: Trained curvature, average curvature over all runs: -1.057 +00.3 Sphr GCN: Trained curvature, average curvature over all runs: 0.951 +-0.019
Prod GCN:
Trained curvatures, average curvatures: [1.331, -0.91]
Cora
Hyp GCN: Trained curvature, average curvature: -1.127 +00.111
Sphr GCN: Trained curvature, average curvature: 0.857+-0.013
22

---

Under review as a conference paper at ICLR 2020
Prod GCN:
Trained curvature, average curvature: [-1.03, -100]]
Pubmed:
Hyp GCN: Trained curvature, average curvature: 1.123 +- 0.01
Sphr GCN: Trained curvature, average curvature: 0.896 0.008
Prod GCN: Not training curvature, fixed to [-1,-1]
Ms-Academic
Hyp GCN: Trained curvature, average curvature: 1.26 0.09
Sphr GCN: Trained curvature, average curvature: 0.8 +- 0.07
Prod GCN: Not training curvature, fixed [-]
F
GRAPH CURVATURE ESTIMATION ALGORITHM
We used the following procedure estimate the curvature of dataset developed by Gu al. (2019)
1. Fix node E G and sample two neighbouring nodes b G uniformly. Further sample an additional reference node c E G uniformly (again avoiding m = c).
2. Calculate ()m; a, b; c) = Ida[a. (de m) + (2.
d2 (a.b) d3
3. Reiterate the above sampling Ylster times and obtain an average curvature at node m..
4. Do this procedure for every node G.
23


Reviews:
[{"review_id": "rJxr_fmNFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 builds a new graph convolutional network (GCN) based on hyperbolic representations of the graph nodes: all latent representations of the nodes are points on Poincare disks. The authors adapted the Hyperbolic Neural Networks by Ganea et al. (2018) into the Kipf & Welling's (2016) version of GCN. Specifically, the authors variated the right matrix multiplication in GCN with Ganea et al.'s Mobius matrix-vector multiplication (that can be regarded as a transformation between two Poincare disks). Moreover, as a non-trivial adaptation, the author defined the left matrix multiplication in GCN (that can be regarded as a weighted linear combination of several points on the same Poincare disk) with Ungar's (2010) weighted barycenter, which is from computational geometry but not the machine learning community. The resulting method is tested on a toy problem and semi-supervised node classification of commonly used datasets, showing the possibility of improvement.\n\nThis is a practical contribution but not a theoretical contribution, as there is no main theorem (or equivalent statements), and the main novelty is on using Ungar's (2010) weighted barycenter to perform neighborhood features aggregations. There are some general discussions on how to adapt gyrovector space theory into spherical spaces. This is interesting but no formal results are presented.\n\nI vote for rejection for four major weaknesses explained as follows.\n\n(1) The experimental results cannot show the usefulness of the proposed GCN. The results on real datasets are similar to the regular GCN. As the authors themselves remarked, \"it can be seen that our models sometimes outperform the two Euclidean GCN\". The experimental settings, e.g. how the train:test datasets are split, and hyperparameter settings, are not clearly given.\n\n(2) The method is not well motivated. The motivation, based on the writing, is that constant curvature spaces are more general where the computation is easy to handle. This is too general and not enough as a motivation. After reading, the reviewer cannot understand why the user should bother to use hyperbolic representations that are more complex to compute in GCNs, given that the experimental results are roughly the same.\n\n(3) A large body of graph neural network literature is omitted. The authors start from a very high-level description of machine learning in constant curvature spaces. Such high-level introductions require more comprehensive literatures to support. In the first mentioning of Graph Neural Networks, the authors only cited Kipf & Welling's GCN. This is misleading. For example, the original GNN, ChebNet, etc. that leads to GCN can be mentioned. The reviewer recommends the authors to read some literature review of the topic of GCN and re-organize the references, and use search engines to have a better view on the state of the art of (hyperbolic) geometric theories and graph convolutional networks. This is a thriving area that requires a careful literature review.\n\n(4) The writing quality is not satisfactory. Here are a few examples: The ICLR citation style needs to use sometimes \\citep. The authors instead used \\cite everywhere, making the paper hard to read. The authors are suggested to use unified notations to denote vectors/matrices (e.g. all bold). The introduction can start at a lower level (such as flat/hyperbolic neural networks). Section 3.4, as the main technical innovation, can be extended and includes some demonstrations.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1eQwEeRYS", "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": "In this paper, the authors address representation learning in non-Euclidean spaces.  The authors are motivated by constant curvature geometries, that can  provide a useful trade-off between Euclidean representations and Riemannian manifolds, i.e. arriving at more suitable representations than possible in the Euclidean space, while not sacrifising closed-form formulae for estimating distances, gradients and so on.  \n\nThe authors point out that an extension of the gyrovector space formalization to spaces of constant positive curvature (spherical) is required, and with the corresponding formalization for hyperbolic spaces, one can arrive at a unified formalism that can interpolate smoothly between all geometries of constant curvature.  The authors propose to do so by replacing  the curvature while flipping the sign in the standard Poincare model.  This is a strong point reagarding this work, as it seems that no such unification has been attempted in the past (although simply replacing the curvature in the Poincare model seems a bit too straightforward to not have been attempted, it seems to be the case).   \n\nThe authors also provide extensive supplementary material (around 20 pages) with detailed derivations and descriptions of experiments.  This also makes me wonder if this paper is more suitable for a journal - both in terms of the extensive supplementary material (e.g., curvature sampling algorithm and other details can be found only in supplementary), as well as the more rigorous review process that a journal paper goes through.  \n\nIn the main paper, only proof of concept experiments are provided (one experiment), that nevertheless show competitive performance under varying settings.  However, it seems to me that such contributions in the rising field of geometric deep learning, where several challenges are yet to be overcome, can be beneficial for future research. \n\nSince in the supplementary experiments also, it seems that curvature does have small variance in the results, how would the authors assess the robustness of the curvature sampling method with respect to the results?  ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "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": "B1lrh6UpYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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:\nThe authors propose using non-Euclidean spaces for GCNs. This is inspired by the recent work into non-Euclidean, and especially hyperbolic, embeddings. A few papers have recently tried to go past embeddings into building non-Euclidean models, requiring the lifting of standard operations in Euclidean space to non-Euclidean settings. This has been done in particular in hyperbolic space, but some datasets benefit from more complex spaces. The authors combine the mixed-curvature product formalism that uses products of Euclidean, hyperbolic, and spherical spaces for embeddings, but use these for GCN operations. \n\nDoing this requires, in particular, developing a reasonable way to perform these operations in spherical space (since Euclidean is trivial and hyperbolic has been recently worked on). The authors do a nice lifting via complex operations, and both the hyperbolic and spherical spaces can devolve into the flat Euclidean space when their curvature goes to 0. The authors implement these GCNs, train the curvatures, and demonstrate performance improvements over Euclidean only versions on node classification on benchmark datasets. They also give a fairly nice introduction to all of these ideas in an extended appendix.\n\n\nStrengths, Weaknesses, Recommendation:\nThis paper is reasonably interesting---it joins an effort to produce non-Euclidean models in a tractable way, which is fairly challenging, but could have a good impact. On the plus side, it's great that the authors added the nice development for the spherical operations, since that will come in handy for many models. The experiments are also good. On the downside, everything here is an extension of existing work, and the body of the paper is hard to read (though this may be inevitable, there's a lot of background to go over here). Overall I recommend accepting it; I think it's a solid contribution.\n\n\n\nComments:\n- I don't understand why the authors say that their space \"interpolates smoothly\" just because the limit in the curvature is the same from the left and right side. For example, the absolute value function has the same limit from the left and the right at 0, but it's not differentiable there. Is it actually true that if we take the derivatives of the piecewise hyperbolic/spherical distance function that it's differentiable at c=0? \n\n- There are a couple of recent papers that also consider hyperbolic GCNs, and in fact use  similar ideas for the aggregation and update steps (i.e., same lift to hyperbolic space). However, these were recently NeurIPS papers, and the text is not yet out, so I don't think this should affect the authors' independent work (and also the product part is new). I do recommend that the authors compare against those results in a future update of this work. The papers are \"Hyperbolic Graph Convolutional Neural Networks\" by Chami et al and Hyperbolic Graph Neural Networks by Liu et al.\n\n- One thing that I didn't see discussed by the authors is that there are subtle difference between hyperbolic and spherical spaces. For example, the weighted midpoint of Def. 3.2 doesn't immediately extend to spherical space (or at least won't be unique). As an example, consider S^2 and the mean of two antipodal points on it---there's many choices for the midpoint. You probably have to limit the operation to a half-sphere (there's some ideas for this in Gu et al).\n\n- For the synthetic tree, why is the number of edges 2(|V|-1) rather than |V|-1?\n\n- Are the curvatures the same for each layer for the GCNs? This is an interesting point to discuss (some of the NeurIPS papers I mentioned train the curvature for each layer). Also, how do you select the number of factors of each type? \n\n- Minor, but some of these citations can be updated. The \"De Sa\" et al 2018 arxiv citation is really Sala et al and is an ICML '18 paper. Similarly, Gulcehre et al is a 2019 ICLR paper, and so on. It's always good to get these right.\n\n- Is there any actual empirical importance from recovering the Euclidean case exactly for 0 curvature? The reason I ask is that my experience is that the hyperboloid is typically easier to work with.\n\n- One useful thing to point out in B.3.3 is that in general, it need not be a diffeomorphism for all of M for any manifold, which leads to non-uniqueness. In differential geometry, the \"cut locus\" is the region beyond which there is this non-uniqueness.\n\n- In the appendix, the statement \"Sarkar (2011) show that a similar statement as in Theorem 2 holds for a very general class of trees\" is confusing to me. The \"general class\", as far as I know, is actually *all* trees, weighted or unweighted. ", "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": {}}]

Author rebuttal:

Meta-review: This paper proposes using non-Euclidean spaces for GCNs, leveraging the gyrovector space formalism. The model allows products of constant curvature, both positive and negative, generalizing hyperbolic embeddings. 

Reviewers got mixed impressions on this paper. Whereas some found its methodology compelling and its empirical evaluation satisfactory, it was generally perceived that this paper will greatly benefit from another round of reviewing. In particular, the authors should improve readability of the main text and provide a more thorough discussion on related recent (and concurrent) work. 
Decision: Reject