Ultrahyperbolic Neural Networks
Authors: Marc T Law
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: differential geometry
pseudo-Riemannian manifolds
hyperbolic geometry
elliptic geometry
ultrahyperbolic geometry
optimization on manifolds
pseudo-Riemannian optimization
quotient manifolds
graph neural networks

Abstract: Riemannian space forms, such as the Euclidean space, sphere and hyperbolic space, are popular and powerful representation spaces in machine learning. For instance, hyperbolic geometry is appropriate to represent graphs without cycles and has been used to extend Graph Neural Networks. Recently, some pseudo-Riemannian space forms that generalize both hyperbolic and spherical geometries have been exploited to learn a specific type of nonparametric embedding called ultrahyperbolic. The lack of geodesic between every pair of ultrahyperbolic points makes the task of learning parametric models (e.g., neural networks) difficult. This paper introduces a method to learn parametric models in ultrahyperbolic space. We experimentally show the relevance of our approach in the tasks of graph and node classification. 

Utrahyperbolic Neural Networks
Marc T. Law
NVIDIA
Abstract
Riemannian space forms, such as the Euclidean space, sphere and hyperbolic space, are popular and powerful representation spaces in machine learning. For instance, hyperbolic geometry is appropriate to represent graphs without cycles and has been used to extend Graph Neural Networks. Recently, some meeudoRRemannial space forms that generalize both hyperbolic and spherical geometries have been exploited learn specific type of nonparametric embedding called ultrahyperbolic. The lack of geodesic between every pair of ultrahyperbolic points makes the task of learning parametric models (e.g., neural networks) difficult. This paper introduces a method to learn parametric models in ultrahyperbolic space. We experimentally show the relevance of our approach in the tasks of graph and node classification.
Introduction
Riemannian manifolds of constant curvature are the most common representation spaces in machine learning. They include the Euclidean space (of constant zero curvature). the d-sphere (of constant positive curvature) and the hyperbolic space (of constant negative curvature). The choice of geometry to represent data mainly depends on the kind of relationship that needs to be described. For instance, Gromov (10) showed the relevance of hyperbolic geometry represent trees (i.e., graphs without cycles). Since many hierarchies can be described as trees, hyperbolic representations have been used to represent hierarchical relationships (e.g., hypernymy between words [1)). Nonetheless, in many domains (e.g., social networks or protein structures), hierarchical graphs contain cycles.
In hyperbolic geometry, the considered manifold is not vector space and is not equipped with the
standard dot product. Therefore, most hyperbolic neural networks [5] g 18 27 represent the weights of their last layer in the tangent space of some reference point. That tangent space is equipped with positive definite metric tensor and the learned model can then be optimized with Riemannian gradient descent 41 In particular, since there exists geodesic between any pair of points, the parameters are often optimized by using parallel transport (also called parallel translation) or the logarithm map. The Riemannian gradients are then parallel translated to the reference tangent space in which the model parameters lie. We refer the reader to (23 for recent survey on hyperbolic neural networks.
Recently, Law & Stam [5] proposed ultrahyperollic embeddings. They type of embedding that lies on a useudo-Riemanniar manifold of constant nonzero curvature 2 21 30) Sceudo-Riemanniaa
manifolds (also called uimi-Riemnnnian manifolds) generalizations of Riemannian manifolds where the nondegenerate metric tensor is not constrained to be positive definite [16]. In particular, when the metric tensor is not positive definite (e.g.. when is indefinite). the negative of the (pseudo- Riemannian) gradient is not a descent direction [ Law & Stam [5] proposed an efficient method to calculate descent direction and learn ultrahyperbolic (nonparametric) embeddings. The main motivation of representing data on an ultrahyperbolic manifold is that it contains hyperbolic and spherical parts (see Fig. [ and supp. material for details). It can then describe relationships specific to hyperbolic and spherical geometries (e.g., to represent parts of a graph that are trees or cycles) and more flexible. Ultrahyperbolic embeddings were experimentally shown to be more appropriate than hyperbolic embeddings to represent hierarchical graphs with cycles on several datasets (15).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Figure 1: Geodesics of the pseudo- Seeudo-Riemannian quotient manifold Plu / / = embedded in R The point [x] of Pi is the pair {x, -x}- Any pair of points of PI. can be joined by geodesic of P1 " On the other hand, x and -z cannot be joined by an (unbroken) geodesic of st The length of the minimizing geodesic of Pl: joining [x] and [y] is the length of the minimizing geodesic of S joining x and -y (in blue). The length of the geodesic of Pl.1 joining [x] and [z] is the length of the geodesic of s. joining x and z (in red). See details in the supp. material.
221
Time- goodesic
Spaco-like goodesie
Nail grodesie
However, since there exist pairs of points on the ultrahyperbolic manifold considered in [5] that cannot be joined by an (unbroken) geodesic, gradients might not be parallel translated via a geodesic and the logarithm map joining two given points might not be defined. Directly extending hyperbolic neural networks [ 18 27 to ultrahyperbolic space is then problematic.
In this paper, propose method to learn ultrahyperbolic representations with neural networks. Unlike (15), we consider the pseudo-Riemaniin Riemannian quotient manifold defined such that every point x == = x.a T is equivalent to its antipodal point -x (-Zo..... -Ea) T In this way, for any other point y, there always exists at least one geodesic joining (x.y) or (-x, y). We provide sufficient conditions to minimize function defined on our quotient manifold. Since tangent vectors (hence gradients) of quotient manifolds are abstract objects, we explain how the function can be optimized with the horizontal lift operator. Our optimization framework is general, so we also introduce an extension to Graph Neural Networks (GNNs) [18] such that the activation representations at each layer of our GNN lie in ultrahyperbolic space. We then obtain deep ultrahyperbolic model to represent graphs given as input. We evaluate our approach in different graph classification tasks.
2 Pseudo-sphere and Quotient Manifold
We extend the ultrahyperbolic manifold described in [15] (denoted by SP:9) to a quotient manifold denoted by p. where (p.g) is the metric signature (see page 343 of (16)) of the pseudo-Riemannian manifold and 1/r² is its curvature. The motivation is that any pair of points of pp-a can be joined by least one geodesic, which allows us to optimize parametric models. We consider three pseudo- Riemannian manifolds pp- C Sp C Re+1.9 that we define below. We explain how pp.. generalizes elliptic and hyperbolic geometries in the special cases where q = 0 and p = 0, respectively.
Notation. We denote points on a smooth manifold M [66] by boldface Roman characters x E M. [x] : {x, - is a pair of antipodal points. T is the tangent space of M at and we write tangent vectors & E T&M in boldface Greek fonts. Rd is the d-dimensional Euclidean space equipped with the (positive definite) dot product ( defined as (x, y) := x y. I is the identity matrix. The inverse function of the cosine (resp. hyperbolic cosine) is denoted by cos (resp. cosh -1).
Ambient space RP+1.g, Our ambient space RI+L. is vector space of dimensionality d + 1 p- + q + 1e E N called pseudo-Euche Euclideen space (2 It equipped with the following scalar product (i.e., nondegenerate symmetric bilinear form) of signature (p 1,
Vx= = (ra. r.) y = Na)
(x, = Σ JzUh
Σ j=p+1
プソリ; = x_ - (1)
1=0
where the signature matrix G G-1 -Ipt1 is the (d + 1) x (d ++11 1) diagonal matrix with the first
p + 1 diagonal elements equal and the remaining q equal
1. Following general relativity literature and spacetime terminology (7]. Re+1, has p + space dimensions and time dimensions. Since it is vector space, we can identify its tangent space to the space itself by means of the natural isomorphism T RPPt. Ri I Finally, the Euclidean space IRd+1 is the special case of 1 which contains zero time dimension, and where G L++1,0 I.
Total space S..9. Our total space Sp.9 is pseudo-sphere of radius r > 0 embedded in RP+L4 It the following hypersurface:
SP-9 := fx E 1ptl.g (x,x), = r2]
(2)
2

---

It is equivalent to work with the ggeudo-hypeboolog Q7P2 := {x E R (x, x/p1 = and the pseudo-sphere Sp.9 as they are anti-isometric to each other (see supp. material). Moreover, the radius r > 0 plays role of scaling factor so we consider it to be 1 although it can be learned [5] 14] Finally, both x E S and its antipodal point x lie on Sp since (x, x)1 00 (-x. xx/g -x/x-
Quotient manifold p.... We consider as equivalence relation the two-element group } consist- ing of the identity map x + x and the antipodal map x + -x. This means that two points x E S and y E Sp are equivalent iff = x or = -x. We define the following projective space: 'pp9 S + -p
((x, -x x E S
Every point of Pp. is unordered pair that we denote by [x] == fx.-- -x). Since P.:. is projective space, every point [x] E pp- can be interpreted as the intersection of the pseudo-sphere Sp.9 with a line passing through the origin of Re+1.9, In some cases, it might be easier to interpret points of pp: as lines through the origin, and to study their properties when they intersect the pseudo-sphere. Each point [x] Pp-2 is also a submanifold of S and a discrete space.
In the following, we explain how PP- extends spherical geometry to elliptic geometry (i.c., when q 0), or naturally describes the hyperboloid model of hyperbolic geometry (i.e., when p 0).
Elliptic geometry (y- 0). In spherical geometry, points lie on the unit d-sphere S == S
(x E Rd+1; (x, = 1). The geometry of the projective d-space ==:== := S + 1 is called elliptic geometry 124 30). Geodesic distances of pd naturally account for the fact that they compare sets. Let dy: St x Sad - IR be the geodesic distance of S (i.e., spherical distance). The geodesic distance
between [x] E pd and [y] E pd is d., (xx], [y]) = min bely da b). We then have:
d byl) == min (d,((d y), d, (x = cos ((( = cos x)),
(4)
which is distance metric. The fact that the spherical geometry is antipodally symmetric (i.e., every point can be inverted w.r.t. the origin) leads to a duplication of geometric information (24). Identifying each pair of antipodal points to one point eliminates the antipodal duplication in spherical geometry.
The hyperboloid model of hyperbolic geometry is similar to the geometry of pf. (p q- g-dimensional manifold 5P.9 c R-- contains two separate sheets (i.e., two connected components) and is anti-isometric to the hyperboloid of two sheets 24.0. Pairs of antipodal points lying different sheets of $ are considered as a single point of pl Let x 5 and z E S be two points lying on the same sheet of S9.9, there exists no geodesic joining x and -z. Their geodesic distance with respect to $6.9 can then be considered to be dy(x, -2) = +o0, and we have:
0). The
min (d= z), } = dz(xx z) = cosh (((x, 2)₂) = cosh (1 cosh- which is similar to the hyperbolic distance metric of the hyperboloid model studied in (20]
([x], [z]) == min
g)
(5)
Ultrahypebbolic geometry (or indefinite elliptic geometry). In this paper, propose parametric model that learns representations lying on the quotient manifold PP:.. When both and q are positive, the metric tensor of PP-. is nondegenerate (see page 343 of [6]) and indefinite. This means that the Riemannnan but not Riemannian due to the lack of positive definiteness of the metric tensor. PP-- is also called an indefinite elliptic space (00 in the literature. We refer the reader to Chapters 11 and 12 of 30 or Chapter 7 of [21] for details. As an example, Fig. [ illuuttrates the manifold pl.1. Our main motivation for considering PP- is that it is more flexible than hyperbolic and elliptic geometries since contains hyperbolic and elliptic parts (i.e., time-like and space-like geodesics in Fig. []. This flexibility allows us to better represent graphs that are not entirely trees or
manifold is
cycles, but that contain tree-like or cycle subgraphs. We experimentally verify our intuition.
3 Optimization on Ultrahyperbolic Quotient Manifolds
Our ultrahyperbolic representations lie on the quotient manifold Pp.., In this section, we provide differential geometry tools to optimize some differentiable function f pp.. - R. To this end, we need the formulation of geodesics of Pp-.. In Section 3.1 we explain how to formulate tangent vectors of pPn- as a function of tangent vectors of Sy-9 via the horizontal lift operator. This operator allows us to formulate geodesics of Pp- as function of geodesics of Sp-9 in Section 3.2] In Section 3.3 we state the properties that the function ʃ has to satisfy due to the quotient nature of PP... In Section 3.4. we illustrate how to optimize a standard neural network. Our deep GNN that maps activation representations in ultrahyperbolic space at each layer is introduced in Section 4
3

---

3.1 Representing tangent vectors of pp-4 only by horizontal tangent vectors of Sp.9
It can be difficult to work numerically with the tangent space Pp of Pp- at [x] since [x] {x, -x} is an equivalence class. We now present some differential geometry tools to define tangent vectors of SP-9
function of tangent vectors of pp-., and vice versa. Their general definitions can be found in Chapter 7 of [21]. We also refer the reader to 4 for details on optimization on quotient manifolds. Our contribution in this subsection is that we give their formulation for Pp... We first give the formulation of tangent spaces of Sp-4 and then provide tools to identify tangent vectors of Pp.. These tools will be essential to construct geodesics of p4- and represent them via Sp.9.
The tangent space Tx Sp of SP.9 at x can be defined as: TxSp = (5 E Re+L.: : (5. x)g = 0}-
The canonical map (or natural map (21) S + pp-s is defined as: Vx E 8p99 (x)) == [x] = -x] Its differential at x is denoted by d Tx + [xx
The horizontal space Hx and the vertical space V/ at x E S are subspaces of T S defined
such that TxSp. Hxx + Vx is direct sum of linear spaces, and Vx the following kernel: V := ke)(d From Proposition 5.38 of [16]. we find ker(d = (xx)) = 0 because [x] is discrete space so xx] and its tangent spaces are O-dimensional. We then have Hx T Elements
of Hx are called horizontal vectors, and all the tangent vectors of S are horizontal.
The horizontal lift (see $29 of (29)
E Sp-9 of the tangent vector & Px is the unique horizontal vector denoted by Ex = (E) E Hx such that (Ex) = &. Since H1x = =Tx= T tangent vectors in P.- can be equivalently represented by
the lifty operator is bijective horizontal vectors in Hx. During optimization, we will exploit this bijection and consider only some specific horizontal space to represent and update the weights of our neural network. The fact that Hx = TxSP is convenient since it implies that any tangent vector in SxS can be represented in PxPPP. We can then construct geodesic of pp. from any geodesic of Sp.9 as discussed below.
3.2 Geodesic of PP:.,, exponential map and parallel transport
To optimize over Sp-9 and Q.PP. Gao et al. g and Law & Stam [B] define tools such as the geodesic, parallel transport, exponential map, logarithm map and the geodesic distance dy SP x SP-9 - IR (see formulations in the supp. material). Our contribution in this subsection is that extend all of the above differential geometry tools to pp. Their details can be found in the supp. material.
The geodesic T -x-E_ RR- + Sp of Sp-9 is the curve defined such that its initial point is Tx--E, (0) X E SP.9, its initial velocity is V x- (0) Ex E TxSp.9 and its acceleration is zero. When the initial conditions are clear from the context, we denote the geodesic by 7 and ignore its indices. Since every geodesic 7 of SP-9 satisfies 7/, (t) E H7(1). it is called horizontal and 7 == x 7
R - >pp- is a geodesic of pp.., By the chain rule, we have VI, 7 (1) = d (7(()))))))))))))))))) which implies Vt. lift (o) = (t)).. We then have Vt E IR, Mx - (t) = {7x (t),
(0))7_x-0 - - x (t)), and we find& &x = Exx to preserve the equivalence hetween antipodal points: - (1)
7 __x-E__ (t)-
Exponential and logarithm map. The exponential map of Pp-9 at [x] is the differentiable mapping
expxx Txx pp:9 - pp-9 defined such that expix (E) := 7xx-<(1) (1) = (Tx-2, (1), (11))_-x0 7 (1))-
We denote the exponential map of S4:4 at x by expx : TxS 1 Sp.9. It is defined as expx == 7x-xe_ (1), and we have exP)x((E) = [Expxx (5x)]. In practice, we select some reference point x and only work with the exponential map expx. The logarithm map is the inverse function of the exponential map (i.e., log,x: := exp,x) )) Their exact formulation can be found in the supp. material.
Parallel transport on SP.4, Given the minimizing (unbroken) geodesic 7 (i.e., minimizing the are length) from 700) to y 7(1, the parallel transport PÊay : TxSpp + TySp is
linear isometry such that Vε Exi (Exx 5x) = (P (PZxy(Ex), PT (5x)), (see page 66 of (21). The
parallel transport along 7 from x to y (where x and y satisfy (x, > - is:
(y. (x,y), +
pJ PRay(EE)
== Ex
(y +
(6)

---

Minimizing geodesic of p!... Our parallel transport on P depends on a minimizing geodesic whose are length (that we call geodesic distance d,,) from [x] =0)) [y] x(1) is:
V[x] E pp.9, [y] E p (1 (v]) cosh 1(1 (x if ا 21
cos- (1 (xp2))))
otherwise.
and we have dx(x,y) y) < d y) iff (x, > 0. See details in the supp. material.
The parallel transport P [x] on p can be horizontally lifted on Hy as discussed above:
P7 VE Tix lifty lifty (y 1
(2x)(Ex) (Ex) P (x
if y) if yx <
(8)
(x. y)g = 0, we have dx d x, y) and there exist two minimizing geodesics joining [x] and [y]. In practice, arbitrarily choose one of these two geodesics when (x.y) 0.
3.3 Optimized function f: Pp R
Our goal is to minimize some differentiable function f : PP-9 + R. We now describe the two properties that f has to satisfy. We first recall that every [x] E Pp- is a set of equivalent elements that should preserve invariance. To simplify explanations, we consider the function f S. + R defined such that J := f We then have Vx E S f(x) f((x)).
Property 1. Since x and -x are equivalent, the first property that f has to satisfy is f(()) = 7( -x).
Property Let Vx(x) := (0](x)/0mn 0xx)) T be the Euclidean gradient of / at x (rr ........,.. ra) T. The sseudo-Riemanmn gradient of f at x E Sp is Df(x) == T (V)((xx)
II (GVJ(x))) E Sx where [x) == (2.x] x is the orthogonal projection of z onto TxS (x.x),
Let Df((x)) E PPa be the eseudo-Riemanen gradient of at xx] Pp... By applying the chain rule, the second property that f has to satisfy is (Dft)()f((x)) = DJ(x) -DT(-x).
3.4 Optimization of parametric models
We now explain how to minimize some function f PP + R that takes as input the ultrahyperbolic representation returned by some parametric model (ea (e.g., a neural network with parameters 0) that we want to learn. We exploit the fact that, due to the properties of the (affine) Levi-Civita connection 66, [7 of Pa-a, the metric of the manifold pp- is preserved when we work with its langent spaces via the exponential map (see page 61 of (21)).
Forward pass. Let consider the positive pole p Or..,..., O)T E SP-9 defined such that only its first element r > 0 is nonzero. The horizontal space of can be defined as the following vector space Up Tp. = {0) Re-q The mapping yo X Hpp maps any input data æ E X' to Hp and the resulting horizontal vector is mapped to Sy-2 with the exponential map as follows:
expp (voo (x:) E SP.9, As mentioned above, working with the vector space H,p greatly simplifies computations and preserves the metric thanks to the Levi-Civita connection of pp...
Note that for standard neural networks that map R.d, the tangent space identified to the space itself by the natural isomorphism T.R z Rd so the network weights also implicitly lie in the tangent space. Our approach extends Euclidean neural networks to pp
Sp- R satisfies the properties mentioned in Section 3.3 By exploiting Eq. (8), the horizontal lift of the parallel translate of the gradient D.((x))
Backward pass. We assume that the function J
can be formulated as follows:
A liftp (PHm))))) - (DF(((((x)) PT P=xxp(-D((x)) otherwise.
if (x. p), 2 0
{
(9)
Descent direction. When the metric tensor of the manifold not positive definite, the manifold is not Riemannian and the negative of X xl.p is not descent direction (9. We show in the supp. material that the negative of x Hp is a descent direction that can be used to optimize the parameters of ye with standard descent algorithms. We illustrate one such example in Section 5.1
5

---

Complexity, Our optimizer exploits efficient closed-form expressions on Sp-i by considering or its antipodal point -x depending on its "geodesic distance" with the positive pole p. This geodesic distance depends only on the sign of (x. P).- which is also the sign of the first element of
(x, p), > 0 - 20 > 0). Our operators generalize tools used in hyperbolic space and are then as efficient as hyperbolic approaches.
(zo, ... xa)? ,.)) (i.e.. d=(x, p) < d7(-x, P) -
4 Ultrahyperbolic Graph Convolutional Network (GCN)
We now extend the hyperbolic graph neural networks introduced in 18 to P.
Graph Neural Networks. We first provide some background on Graph Neural Networks (GNNs) which can be interpreted as parametric models performing message passing between nodes of graph. We recall the formulation of Graph Convolutional Networks (GCNs) [3] and rewrite them in our formalism with quotient manifolds. Let = (V, E) be a undirected graph containing n = [ nodes and E edges. Its adjacency matrix is denoted by A E R"*= To account for self-loops. Liu et al. [18] consider the matrix A D D-1/2((A +
I)D 1/2 where D is the diagonal degree matrix
defined such that D = (A,g + L.y). The vector representation of node v at step k is denoted by h Rd, and h2 is given. W is matrix whose elements the trainable parameters of the k-th layer. The information in the Euclidean GCN propagates as: h o (Evez(e)) Auv W*h where [u)) is the set of in-neighbors of u E V (i.e., u and v are joined by an edge) and is nonlinear activation function such as the element-wise Rectified Linear Unit (ReLU) or its variants.
Ultrahy perroby GNN. Let us now consider that Vu, k; h E PR. Since PP: is not a vector space, the operation W* is not defined, and the activation function a has to be adapted. As in Section 3.4 we exploit properties of the Levi-Civita connection to work with the tangent spaces of pp-a via the exponential map and its inverse (i.e., logarithm map). The propagation is then extended to PP: by:
([- EXPP
)
h a
Σ vEZ(u)
Auo W liftp [10% (bt)
E PP-.,
(10)
where p = (r, .., T)T to single tangent space. As explained in Section[]] in practice, we use the horizontal lift operator so that the exponential and logarithm maps only consider the horizontal space Hp during optimization (see supp. material for details). The hyperbolic GNN (18) corresponds to the special case where Pp.- = Pf.. (i.e., p = 0). We now give the formulation of the activation function d.
T is the positive pole and we exploit the logarithm map to map points of pp:
Activation function via stereographic projection. For simplicity of exposition, we now consider that the radius of Sp-9 is r = 1. To enforce nonlinearity between the different layers of the hyperbolic graph neural network, Liu et al. [18] formulate their activation function the result of steoreographic projection onto the negative pole -p from the hyperboloid model to the Poincaré ball, followed by ReLU activation (in the Poincaré ball) and an inverse steoreographic projection from the Poincaré ball to the hyperboloid. We explain below how to generalize a to pseudo-spheres.
Let us note 1). The pole ap (e, O,.... 0)T is positive if = 1, and negative if = -1 Let us consider a point x (No, 21.......................... ,T) E Sp-9 with to > 0 (i.e., lying on the positive hemisphere). The stereographic projection of x onto ep is = (x) == 1 1-220 (#1, 02............. IT) If
To < O, we equivalently consider that a We (-x) - (x) instead of (x) due to the quotient nature of pp-a and to account for the fact that [x] is projected onto the pole of different hemisphere e = 11, or same hemisphere if & = 1. The inverse projection of (aI,..., ad) E RR is:
(E((( (a, a)g -1)
w
w- 1+ (a, a)g
E SP-9 where (a, a)g =
Σ j=p+1
oz.
(11)
2a
We formulate o ([x)) := | (ReL.U(w if zo 2 0. and a(x))
(ReLU
otherwise, where ReLU (or one of its variants such as LeakyRelu) is applied element-wiss only on the q time dimensions of the input vector, which avoids having zero denominator in Eq. (I]. As in [18] we consider = = -1. It is worth noting that Liu et al. [18] work with the upper sheet of the hyperboloid 01-00 which anti-isometric to S01. Their stereographic projection then contains only space dimensions. Their space dimensions correspond to our time dimensions due to anti- anti-isometry.

---

500
Ramammmmn quotiett manikid optinization
0.2
mamber of faction
member of faclion 34
13
400
poauto-Aemannian qustiett maniflld optimization
Poouto-Remmnniiee quotient manifld optimization
0.15
cdge connecting members of facton
edge connecting members of tactin
400
Ramaaniin quotient mantold optimization
quotlent optimiation Io 44)
0.1
edge connacting members difirrett factions
66111
350
0.05
1005
300
20
0.00
250
0.1
200
12
24
-0.15
23
2000
10000
18000
-0.25
22
iterationns
Figure 2: (left) Loss values of Eq. (12) as a function of the number of iterations for different values of p when P is d-imennsinnal. (right) Stereographic projection onto -p of representations lying on Pl and learned from Zachary's s karate club. Node colors define the faction joined by the members.
Table Evaluation scores for the different learned representations (mean + standard deviation)
Evaluation metric
pb. (Hyperbolic)
pia.
p4.0 (Elliptic)
(Euclidean)
Rank of first leader
1.6 1.0
2.5 0.7
1.2 + 0.4
1.3 + 0.7
1.2 0.4
2.5 = 0.8
second leader
6.9
2.7
top Spearman's 's
0.06 1: 0.45
0.36 0.22
0.62 1: 0.23
0.61 1 0.28
0.63 0.35
0.46 0.29
top Spearman's p
0.04 0.19
0.38 0.18
0.07
0.38 0.26
Training time (scconds)
340 =4
1
129 +
130
129 =
402 =
Experiments
We now evaluate our approach different classification tasks graphs. We first show that our optimization framework introduced Section 3.4 learns meaningful representations on a toy hierarchical graph with cycles. We then apply framework in standard classification tasks.
5.1 Last layer optimization on toy dataset
We evaluate our optimization framework by training a multi-layer perceptron (MLP) Po : Hpp whose set of parameters is called 6. As in [15], we test our approach on Zachary's karate club dataset (33] However, instead of learning embeddings, we train a parametric model.
Zachary's dataset is a social network graph that represents a karate club split in two factions due conflict between
leaders (the instructor and the administrator). It is undirected graph G = (V, E) which has node-set V = {w: } and edge-set E {Ex Jm where n 34 and m 78. Each node v; represents karate member and edge joins two nodes if the members are friends. The two leaders are and У34. We consider that each node v, is represented as distinct n-dimensional one-hot vector æ; X.
Problem. Following [1], our goal is to learn representations of nodes such that pairs of nodes joined by edge (i.e., in E) have smaller distance than pairs of nodes that not joined by an edge (i.e., not in E). Our problem is then to find the set of parameters that minimizes the problem:
min Σ
log
d(eo(tm)) where eo = (expp (<p((x:))
(12)
(E..))E
(Pa Wiy
and where Way == [(., u;)} U ( 06) & E). T 1 is fixed temperature value, and d denotes the geodesic distance of the manifold (e.g., Eq. ( for PP. The geodesic distance satisfies the two properties defined in Section 3.3 with respect each input and then be used for optimization.
Model. Our MI. sp : + Hp contains three hidden layers 10 hidden units each, with standard ReLU nonlincar activation function. In this toy experiment, our MLP is standard, with the only
7

---

exception that its last layer maps to the horizontal space Hp = {0} x RP-9 of the positive pole p. The output representation is then mapped with the exponential map as explained in Section 3.4
Optimizer. We use the optimizer introduced in Section to update f. By using the descent direction GAxx.I.p p for each sample [x,] = eo (.)), all the parameters of our standard MIP lie in some space equipped with a positive definite metric tensor. Standard backpropagation is then used to optimize
the parameters. As an illustration, we consider the 4-dimensional manifold Pf (i.c., p p++ q = 4) and show in Fig. (left) the loss values of Eq. ( as a function of the number of iterations for different
values of p E ( 4). The figure shows that the optimization framework in Section 3.4 decreases the loss value. Moreover, it is worth noting that the algorithm does not converge if - xx,l.p is used as a search direction (instead of G) when the metric tensor is not positive definite since (x...pp is not a descent direction (9. More details can be found in the supp. material.
Hierarchy extraction. We now evaluate the quality of the learned representations in the task of predicting the high-level nodes of the graph. Our evaluation protocol is similar to [15] the only difference is that we train neural network. We run 10 random initializations for each considered 4-dimensional manifold and report in Table [ the mean and standard deviation of the different evaluation metrics.
As in [5), following the idea that hyperbolic distances grow exponentially, we take the sum of distances 6, Σك= d((x,). [xy]) of node o, with all the other nodes an indicator of importance. We sort the different 51,- .i...., on in ascending order and report the rank of the two leaders (instructor and administrator, in no particular order) in the first two rows of Table [T The leaders tend to have smaller 6, score than low-level nodes with ultrahyperbolic distances, which means that high-level nodes tend to be closer to the rest of the nodes in ultrahyperbolic space.
We also measure the Spearman's 's rank correlation coefficient (28) between the 5 (or 10) most important nodes in the hierarchy and their corresponding ò; score. Once again, the order of the 6, scores is more correlated with the hierarchy level in ulrrahyerboolic space. Our experimental results are comparable with [15] although our nodes are represented on a quotient manifold and we learn parametric model. Fig. (right) illustrates our learned representations when the manifold is P.l...
Products of Riemannian space forms. In Table we compare the performance of models mapping representations to pseudo-Riemane Riemannian space forms (i.e., manifolds of constant curvature 21 30). Nonetheless, it was already noticed in the machine learning literature that products of Riemannian space forms (called mixed-curvature representationss) could outperform Riemannian space forms when the structure of the dataset is not tree-like 3 11.
It is worth noting that products of space forms are in general not space forms (except they are all flat). For this reason, we do not compare them to our manifold in the main article as we could similarly consider products of pseudo-spheres PPI-9 x Ppa. or even Ppr .u x 122-22 for evaluation.
Nonetheless, since our space form p contains hyperbolic and elliptic parts, we provide a detailed comparison with products of hyperbolic and spherical spaces in the supp. material. Such product manifolds perform better than hyperbolic and spherical spaces but slightly worse than the pseudo- Riemannian space form P....
Training times. We report in Table I the training times of our Pytorch 22 implementation to train 25,000 iterations on a machine equipped with 6-core Intel i7-7800X CPU and NVIDIA GeForce RTX 3090 GPU. All the representations lying on a non-flat manifold have comparable training times. Nonetheless, they are 25% slower than the Euclidean approach because they compute the pseudo-Riemannian gradient (which requires an orthogonal projection) and parallel transport.
5.2 Classification with ultrahyperbolic graph convolutional networks
The previous subsection analyzed our framework. We now evaluate it in standard classification tasks.
Node classification. We now evaluate the generalization performance of our GCN in the semi- supervised node classification task on three citation network datasets: Citeseer, Cora and Pubmed [26] They contain sparse ofg-of-wwe words feature vectors for each document and a list of citation links between documents. Each document is a node and has a class label. Each citation link is an undirected edge. Dataset statistics are reported in Table 2 During training, all the nodes and edges are preserved, but only 20 nodes per class are labeled, and 500 nodes are used for validation in total, the rest for test. We follow the experimental protocol of Appendix A of [18 and learn GCN with 2 hidden layers.
8

---

Table 2: Statistics of the citation network datasets.
Name
# Nodes
# Edges
# Classes
# Features
# training nodes per calegory
Citeseer
3,327
4,732
6
3,703
20
Cora
2,708
5,429
7
1,433
20
Pubmed
19,717
44,338
500
20
Table 3:
Test node classification accuracy with 4-dimensional manifolds
Dataset
R (standard GCN)
p (Hyperbolic)
PI.
p4.
(Elliptic)
Citeseer
44.5 = 5.9
46.7 + 1.8
51.8 + 2.6
50.3
51.4 = 3.2
47.2 2.6
Cora
53.5 = 4.3
56.2 + 3.1
63.2 + 3.3
63.9 3.1
64.7 + 5.3
61.4
Pubmed
66.9 2.3
71.5 2.9
73.1 + 0.6
72.8
71.2 = 2.7
71.0 2.7
Table 4: Statisties of the graph datasets used for the classification task
Name
# graphs
# classes
Avg. # nodes
Avg. # edges
Type of dataset
Collab
5,000
3
74.49
2457.78
Scientific collaboration dataset 32
D&D
1,178
2
284.32
715.66
Protein dataset 25
Enzymes
600
6
32.63
62.14
Protein dataset 25
Proteins
1,113
2
39.06
72.82
Protein dataset
Reddit- 1ulti-12
11,929
11
391.41
456.89
Social network dataset 32
Table 5: Graph classification accuracy in percents. d is the dimensionality of the manifold.
Method
(d 64)
88)
Enzymes
100)
100)
Euclidean (standard GCN)
81.88
1.76
76,93
7:21
43.83 10.3
75.46
3.88
45.65 1.76
Poincuré (byperholic)
80.92
1.99
75.89
8.53
44.15
8.43
73.64
4.64
45.84 1. 1.42
Lorentz (hyperbolic)
81.32 + 1.21
77.10 + 6.65
41.83 = 8.14
74.16 + 3.25
45.39 +: 1.53
perboliic
1.23
3.41
50.50 1
76.56
2,09
1.26
When the dimensionality of each layer is d = 600, all the Euclidean (i.c., standard), Hyperbolic and Ultrahyerboolic GCNs reach the same test accuracy because the model is overparameterized and quickly attains 100% accuracy on the training set. See details and scores in the supp. material.
Due to the problem mentioned above, trained GCNs whose dimensionality of each layer is d = 4 with 100 random initializations. The results reported in Table[]sshw the superiority of ultrahyprboolic representations in low-d low-dimensional space for node classification of hierarchical graphs with cycles. We also report results for = 10 in the supp. material. The conclusion is similar.
Graph classification. We also evaluate our approach on commonly used graph kernel benchmark datasets [2] whose statistics are reported in Table 4 The evaluation is done via 10-fold cross validation. We use the same protocol evaluation and splits in Appendix E of [8] and evaluate our approach in the same settings including same number GNN layers, optimizers, learning rate, and manifold dimensionality d reported in Table 5 The only difference is that the data is represented on PP- with p = in our case. The comparative performances are reported in Table 5 and show that ultrahyperbolic representations significantly improve performance datasets, which are protein datasets from (25). The gain is less significant on the other datasets but our approach is still competitive. It seems that the advantage of our approach over hyperbolic approaches more visible for protein structures than for social networks, at least in high-dimensional space. More details can be found in the supp. material.
the D&D and Enzymes
6 Conclusion, Limitations and Potential Societal Impacts
We have introduced neural networks that map data (quotient) pseudo Rieemaniaannn manifold of constant nonzero curvature, Our considered geometry generalizes both hyperbolic and elliptic geometries. is the first neural network that maps data to a non-Riimannian manifold to the best of our knowledge. Our framework is general and can be applied to many parametric models and tasks. We demonstrate this via graph convolutional networks and show improved performance compared to Euclidean and hyperbolic approaches to represent hierarchical graphs in different tasks.

---

Concurrently with this work, Xiong et al. [31] proposed an extension of graph convolutional net- works to the geeudo-hyeerblood Q. which is a pseudo Riemmmnian manifold of constant nonzero curvature anti-isometric to the pseudo-sphere Sp.9. One main difference is that, since there exist pairs of points of Og that cannot be joined by an unbroken geodesic, the optimization framework in [i does not exploit the intrinsic geometry of the manifold via its Levi-Civits connection. On the other hand, our approach uses pseudo-Riemannial Riemannian optimization tools that are intrinsic to P. The ablation study in [31] also suggests that graphs with more hierarchical structure are better represented when the manifold becomes more hyperbolic, and graphs with cyclic relationships are better represented when the manifold becomes more spherical.
Limitations. Our main contribution solid optimization framework that is well defined thanks to the use of standard differential geometry tools (e.g., canonical map and horizontal bundle) that we formulate for the quotient manifold pp... only requires the properties of the optimized function in Section 3.3 to be satisfied. This is for instance the case if points of pp:9 are compared with the geodesic distance in Eq. 7 We applied our framework on nine different datasets with (at least 10) different runs to validate our results. Our work lacks theoretical analysis similar to Gromov's 's work [00 in the case of graphs without cycles. However, the optimal geometry for graphs with cycles is still open problem, and hyperbolic geometry is used heuristically in this case. Our motivation is that ultrahyyerbolli manifolds are more general than hyperbolic and elliptic manifolds, they can then combine the strengths of the two induced geometries. We experimentally validate assumption in different tasks and leave the theoretical analysis for future work.
Potential societal impacts. Our contributions are mainly methodological although we apply our approach hierarchical graphs that could represent social networks. Improving accuracy on these datasets might facilitate the task of discovering leaders in social networks, which could have negative impact if not monitored. Nonetheless, we also show improvement on protein structures, this could have positive impacts on society and healthcare. We did not exploit any personally identifiable information. We used datasets that have been publicly available to the machine learning community for years. Our method to handle and process the data is standard in the graph community.
Acknowledgments and Funding Transparency Statement. I thank James Lucas, Rafid Mahmood, Haggai Maron and the anonymous reviewers for helpful feedback on early versions of this manuscript. This project was entirely funded by NVIDIA corporation while was working from home during the COVID-19 19 pandemic. am also grateful to the NeurlPS 2021 program committee for giving me free registration to the conference thanks to an Outstanding Reviewer Award.
References
[1] Pierre-Antoine Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
[2] Henri Anciaux. Minimal submanifolds in pseudo- Riemannian geometry. World Scientific, 2011.
[3] Gregor Bachmann, Gary Bécigneul, and Octavian Ganea. Constant curvature graph convolu- tional networks. In International Conference on Machine Learning, pages 486-496. PMLR, 2020.
[4] Nicolas Boumal. An introduction optimization on smooth manifolds. Available online, Nov 2020.
[5] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In Advances in neural information processing systems, pages 4868-4879, 2019.
[6] EB Christoffel. Ueber die transformation der homogenen differentialaussdricke zweiten grades. Journal für die reine und angewandte Mathematik, 70:46-70, 1869.
[7] Albert Einstein. Zur clektrodynamik bewegter körper. Annalen der physik, 322(10))891-921, 1905.
[8] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In
Advances in neural information processing systems, pages 5345-5355, 2018.
10

---

[9] Tingran Gao, Lek-Heng Lim, and Ke Ye. Semi-riemannian manifold optimization. arXiv preprint arXiv:1812.076433 2018.
[10] Mikhael Gromov.
Hyperbolic groups. In Essays group theory, pages 75-263. Springer, 1987.
[11] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature rep- resentations in product spaces. In International Conference on Learning Representations. 2018.
[12] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Benchmark data sets for graph kernels, 2016.
[13] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[14] Mare T. Law, Renjie Liao, Jake Snell, and Richard Zemel. Lorentzian distance learning for hyperbolic representations. In Proceedings of the 36th International Conference Machine Learning, pages
2019.
[15] Mare Law and Jos Stam. Ultrahyperbolic representation learning. In Advances in Neural Information Processing Systems, volume 33, pages 1668-1678, 2020.
[16] John M. Lee. Introduction to Smooth Manifolds, volume 218. Springer Science & Business Media, 2013.
[17] Tullio Levi-Civita. Nozioni di parallelismo in una varieta qualunque consequente specifi- cazione geometrica della curvature riemannia. Rendiconti del Circolo Matematico di Palermo, 42:173-205 1917.
[18] Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In Advances in Neural Information Processing Systems 32, pages 1228-8233 2019.
[19] Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. In Advances in neural information processing systems, pages 6338 0888-637,444 2017.
[20] Maximillan Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International Conference on Machine Learning, pages 3779-3788 2018.
[21] Barrett O' D'neill. Semi-Riemamnian geometry with applications to relativity, volume 103, Aca- demic press, 1983.
[22] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[23] Wei Peng. Tuomas Varanka, Abdelrahman Mostafa, Henglin Shi, and Guoying Zhao. Hyperbolic deep neural networks: A survey, arXiv preprint arXiv:2101.04566
[24] John Ratcliffe. Foundations of hyperbolic manifolds, volume 149. Springer Science & Business Media, 2006.
[25] Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, $21supp__1:D431-DAA.
2004.
[26] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3)993-93, 2008
[27] Ryohei Shimizu, Yusuke Mukuta, and Tatsuya Harada. Hyperbolic neural networks++. In International Conference Learning Representations, 2021.

---

[28] Charles Spearman. The proof and measurement of association between two things. The American journal of psychology. 1904.
[29] Loring Tu. Differential geometry: connections, curvature, and characteristic classes, volume 275. Springer, 2017.
[30] Joseph Albert Wolf. Spaces of constant curvature, volume 372. AMS Chelsea Publishing: An Imprint of the American Mathematical Society, Sixth Edition, 2011.
[31] Bo Xiong, Shichao Zhu, Nico Potyka, Shirui Pan, Chuan Zhou, and Steffen Staab. Semi- riemannian graph convolutional networks. arXiv preprint 3tt::2006.0313344 2021.
[32] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365-1374. ACM, 2015.
[33] Wayne Zachary. An information flow model for conflict and fission small groups. Journal of anthropological research, 33(4):452-47) 1977.
12


Reviews:
[{"review_id": "aYo0GQwPylz", "reviewer": "Reviewer_J8on", "summary": "This paper presents a (graph) neural network in ultrahyperbolic (semi-Riemannian) space that can be used to model hierarchical graphs with cycles. The motivation is that ultrahyperbolic manifold generalizes hyperbolic and spherical manifolds, thus providing inductive bias to those geometries. In order to avoid broken cases, the paper considers ultrahyperbolic quotient manifold such that every two points in the manifold can be connected by a geodesic. The method is evaluated in graph and node classification tasks. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Originality: \n1)\tIn general, extending neural networks to semi-Riemannian space is a new and valuable idea. However, the method used in this paper to solve the brokenness of geodesic is straightforward, even a little bit trivial and lack theoretical analysis. The idea is simply that, if points x and y cannot be geodesically connected, they connect the point x with the antipodal point -y. This method would potentially hurt the expressiveness of the ultrahyperbolic space in paper [1]. \n\n2)\tIn section 3.2, the author claimed that they first formulated parallel transport of the ultrahyperbolic space. However, the parallel transport of ultrahyperbolic space was first introduced in the paper [2] (see Section 4.2.1 and 4.2.2). The authors should clarify the contributions and cite the related works properly. \n\nQuality: \n1)\tThe authors try to solve the broken issues of ultrahyperbolic manifold by identifying each pair of antipodal points to one point, I was mainly concerned with the expressiveness of the induced space as it is no longer a standard pseudo-sphere. It is clear that the pseudo-sphere can generalize spherical and hyperbolic spaces well [1], but simply identifying each pair of antipodal points to one point would hurt the expressiveness of the space. The author used the quotient space, which does not satisfy a lot of properties of the pseudo-hyperboloid used in the paper [1]. Taking sphere as an example, why a point x and its antipodal point -x leads to duplications? these two points could be used to describe different nodes in a cycle of graph. It seems like the “quotient space” even cannot model a cycle graph well. Note that in a spherical space, point x and point -x can describe two antipodal nodes in a graph.  Instead, the quotient space can only model a half-cycle relationship, as it treats points x and -x equally. \n2)\tThe author showed some intuitions of the quotient manifold in Fig 1, where the space-like geodesic could be used to describe cycle, and the time-like geodesic could be used to describe trees, but if we treat each pair of antipodal points to one point, the geodesic cannot fully describe some relationships. (e.g. starting with point x, there is only a half-cycle passing x, but not a full cycle). \n3)\tIn line 83, the author also claimed that the quotient manifold is only a submanifold of pseudo-sphere, but it is not clear which submanifold it is. A submanifold can only express some sub-information of the original manifold. The author might need to clarify what information loss it led to.\n4)\tI would advocate the authors to provide more theoretical analysis w.r.t the method, and try to understand more on the expressiveness of the ultrahyperbolic quotient manifold. So far, it is unclear how the method works to model tree and cycles as the space used in this paper is not an ultrahyperbolic manifold anymore. \n\nClarity: the paper is well-written and well-organized, there are some minor points that need to be clarified. \n\n1)\tIn line 78, does the radius r only play a role of scaling factor? Assuming infinite precision, I think it is true, but in practice, I would imagine that changing the radius r would also influence the experiment results. In paper [3], the authors showed some improvements by learning the right curvatures. The author might also want to do some ablation study on this issue.\n2)\tThe toy experiments in section 5.1 follows mainly the experimental setting of paper [1], but show different results (the best performance is achieved by different time dimension), it would be better if the author can add more details to explain the results. \n\nSignificance: \n      The experiments lack some comparisons to some existing works. \n1)\tSince the proposed method is a little bit straightforward, and the theoretical contribution is not significant, I would suggest doing more experiments to compare the method with some more recent baselines, e.g. produce space [4], to showcase the advantages of the method. \n\n2)\tHow to determine the time dimension? Could you provide some insights on this? it would also be interesting to do some ablation study on the time dimensions if possible. Consider adding them into the appendix. \n\n[1] Law, M.T. and Stam, J., 2020. Ultrahyperbolic representation learning. NeurIPS 2020.\n[2] Gao, T., Lim, L.H. and Ye, K., 2018. Semi-Riemannian manifold optimization. arXiv preprint arXiv:1812.07643.\n[3] Chami, I., Ying, Z., Ré, C. and Leskovec, J., 2019. Hyperbolic graph convolutional neural networks. Advances in neural information processing systems, 32, pp.4868-4879.\n[4] Bachmann, G., Bécigneul, G. and Ganea, O., 2020, November. Constant curvature graph convolutional networks. In International Conference on Machine Learning (pp. 486-496). PMLR.\n\nPost Rebuttal:\n The authors give more intuitions to the expressiveness of the manifold (e.g.. to describe cyclic relationships), so I raised my score. But I still suggest the authors provide more theoretical analysis w.r.t the method.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "WJJmW6oTd_", "reviewer": "Reviewer_xWxM", "summary": "The paper focuses on data embedded in ultrahyperbolic spaces and proposes a method to learn this representation via neural networks. By imposing a quotient structure over the ultrahyperbolic space defined in Low and Stam 2020, the authors are able to define geodesics and thus to estimate the parameters of the learning model selected.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "The paper is overall well written. Section 2 is clear and well organized. \n\nMajor Comments:\n- Section 2: why is the quotient space a manifold? Are the authors excluding the axes? Because with the axes, the equivalence classes (orbits) do not have the same dimension, thus the action is not free and stating that the quotient space is a manifold because the total space is a manifold it is not straightforward.\n\n- Section 3: in quotient spaces, the horizontal lift is a good solution to work on the tangent space. However, the curvature of the space can create problem by using only a one step horizontal lift (see e.g. the procrustes algorithm for shapes or the Align All and compute algorithm for graphs). If I am not misunderstanding, some discussion about the single lift procedure should be added.\n\n- Section 5: if I have properly understood, the usage of the hyperbolic space to estimate the parameters allows a proper embedding of the network. If so, I would rather like to see the algorithm applied to a prediction of a graph task more than a classification task, where the output should be embedded into a suitable geoemtrical framework.\n\nAdditional comments:\n- To introduce complex geometrical framework to perform classification, a well written justification is necessary. It is not clear to me how much of all the introduced framework it is acctually needed to obtain a better performance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The conclusions and the limitations are well written.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "GRilTUgAz8M", "reviewer": "Reviewer_v58v", "summary": "This paper proposes graph neural networks for ultrahyperbolic space along with various ways to optimize them.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Strengths\n\n* The construction is technically sound.\n* The experiments show modest improvement across the board.\n\nWeaknesses\n\n* None of the constructions are particularly novel. In particular, they seem to be natural extensions of the same operations in regular hyperbolic space.\n* The main motivation for ultrahyperbolic manifolds seems to be to represent different parts of a graph that have different geometries. This is also the goal of the mixed curvature literature [1, 2, 3], but no discussion and experimental comparison is made with this prior work.\n* The experiments heavily rely on 3 canonical datasets (Citeseer cora and pubmed) but doesn't delve into the geometric properties of said datasets. Is there any reason why one would use ultrahyperbolic GCNs on these datasets?\n* While there is a general increase in performance, SOTA Euclidean methods are not compared against. This is especially important since the three datasets were shown to perform worse on hyperbolic graph models when compared against SOTA Euclidean methods.\n\nVerdict\n\nWhile the neural networks are well-constructed, nothing is particularly surprising or novel. Furthermore, the experiments do not compare against SOTA methods for both Euclidean and manifold-based graph methods and rely on 3 canonical datasets with no apparent geometric structure. As such, I lean reject.\n\n[1] Learning Mixed-Curvature Representations in Product Spaces, ICLR 2018\n[2] Mixed-curvature Variational Autoencoders, ICLR 2020\n[3] Constant Curvature Graph Convolutional Networks, ICML 2020\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The others adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6PiJC9kHl6g", "reviewer": "Reviewer_KvL5", "summary": "The paper proposes to learn ultrahyperbolic representations with neural networks. Unlike prior work in ultrahyperbolic representation learning, the paper proposes dealing with an ultrahyperbolic quotient manifold to attain geodesic completeness and enable optimization of parametric models that use this space as an intermediate representation. The optimization of ultrahyperbolic neural networks is then developed in the paper, and an extension to Graph Neural Networks (GNNs) is introduced. Afterwards, the approach is evaluated in various different graph classification tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Strengths\n\n1. Overall, I think the theory presented in this paper was fairly original and significant, as it enables learning neural networks with intermediate representations that are ultrahyperbolic; notably, this is a generalization of prior work, which limits intermediate representations to spaces of constant sectional curvature. I think that using a quotient manifold construction to attain geodesic completeness and enable optimization was a clever idea, and further, the other theory necessary for optimization (namely parallel transport on $\\mathcal{S}^{(p,q)}_r$ and the use of horizontal lifts) was clearly introduced and well-developed. Once these constructs were in place, the generalization of GCNs to ultrahyperbolic space was naturally given in Section 4. I think all throughout, the writing was clear and the construction was clean.\n\n2. The results in Table 3 on node classification in graph datasets show the benefit of ultrahyperbolic space in attaining considerably better results than both the standard GCN and the hyperbolic GCN; the margin of improvement exhibited by $\\mathcal{P}^{(0,4)}_1$ seems fairly significant.\n\nWeaknesses\n\n1. I find the results of Table 5 on graph classification to be unconvincing. The standard deviations on most numbers in the table are rather high, high enough that I'm not sure the claimed performance increase of an ultrahyperbolic space intermediate representation is statistically significant.\n\n2. On a more fundamental level, I am unconvinced that ultrahyperbolic space is necessary to glean the benefit of an intermediate representation that allows for both positive and negative curvature. For example, I would like to see a comparison against Constant Curvature Graph Convolutional Networks (CC-GCN) [a], which allow for an intermediate representation that is a product of spaces of constant curvature. A fair comparison would be for example, a mixed signature ultrahyperbolic model ($\\\\mathcal{P}^{(p,q)}_r$) against a CC-GCN model with a product-like intermediate representation, e.g. $H^{p+1} \\times S^q$. I would also like to see a discussion or analysis of the benefits of a product model (like CC-GCN) vs. a model that incorporates positive and negative curvatures into a single space, like the ultrahyperbolic GCN. I think this aspect is completely unaddressed as of right now.\n\nVerdict\n\nThe paper developed ultrahyperbolic neural networks, together with clearly presented original theory. I think the way the authors handled the manifold, i.e. turning it into a quotient to enable optimization, was clever, and the necessary operations for optimization (e.g. horizontal lift) were introduced in a principled way. Empirically, the benefit of the method is not entirely convincing. Although ultrahyperbolic space seems to give a considerable improvement in the setting of node classification (Table 3), this was not the case for graph classification (Table 5) where standard deviations are high enough that it is unclear to me if the margin of improvement is statistically significant. Moreover, the paper fails to address prior work [a] on GCNs that utilize a product of constant curvature spaces to extract additional structure, as opposed to using a single space with both positive and negative curvature (i.e. ultrahyperbolic space); in particular, an empirical comparison is missing, and a discussion/analysis of differences (in particular with respect to applying these models to graph tasks). Given that this is the case, I must recommend rejection (for the time being) and that the authors improve their paper by addressing this directly; however, I do emphasize that overall, the paper is very promising.\n\nReferences\n\n[a] Bachmann, G., B'ecigneul, G., & Ganea, O. (2020). Constant Curvature Graph Convolutional Networks. ICML.\n\n### Post-rebuttal Update\n\nGiven the thoroughness of the rebuttal and the pertinent strong results demonstrated, I've decided to update my score from a 5 to a 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has two subsections of the conclusion that address limitations and societal impacts. In particular, the paper admits the lack of a theoretical analysis (similar to what can be found in [7]) for graphs without cycles.", "review_text": "", "extra_scores": {"ethical_concerns": "This paper is reasonably theoretical in nature; I have no ethical concerns about its impact.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a lot of support for this paper, which proposes a mathematical elegant and convincing method for embedding graphs in non-Euclidean spaces, namely ultrahyperbolic spaces. The experiments - despite some caveats mentioned - provide sufficient evidence for the validity of the approach.
Decision: Accept (Spotlight)