Ultrahyperbolic Neural Networks
Year: 2022

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.

heading: 1 Introduction
text: 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 a 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 to 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 [19]). Nonetheless, in many domains (e.g., social networks or protein structures), hierarchical graphs contain cycles.
In hyperbolic geometry, the considered manifold is not a vector space and is not equipped with the standard dot product. Therefore, most hyperbolic neural networks [5, 8, 18, 27] represent the weights of their last layer in the tangent space of some reference point. That tangent space is equipped with a positive definite metric tensor and the learned model can then be optimized with Riemannian gradient descent [1, 4]. In particular, since there exists a 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 a recent survey on hyperbolic neural networks.
Recently, Law & Stam [15] proposed ultrahyperbolic embeddings. They are a type of embedding that lies on a pseudo-Riemannian manifold of constant nonzero curvature [2, 21, 30]. Pseudo-Riemannian manifolds (also called semi-Riemannian manifolds) are 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 it is indefinite), the negative of the (pseudoRiemannian) gradient is not a descent direction [9]. Law & Stam [15] proposed an efficient method to calculate a 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. 1 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 is 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 (NeurIPS 2021).
However, since there exist pairs of points on the ultrahyperbolic manifold considered in [15] 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 [5, 8, 18, 27] to ultrahyperbolic space is then problematic.
In this paper, we propose a method to learn ultrahyperbolic representations with neural networks. Unlike [15], we consider the pseudo-Riemannian quotient manifold defined such that every point x = (x0, . . . , xd)
> is equivalent to its antipodal point −x = (−x0, . . . ,−xd)>. 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 a 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 a deep ultrahyperbolic model to represent graphs given as input. We evaluate our approach in different graph classification tasks.

heading: 2 Pseudo-sphere and Quotient Manifold
text: We extend the ultrahyperbolic manifold described in [15] (denoted by Sp,qr ) to a quotient manifold denoted by Pp,qr where (p, q) is the metric signature (see page 343 of [16]) of the pseudo-Riemannian manifold and 1/r2 is its curvature. The motivation is that any pair of points of Pp,qr can be joined by at least one geodesic, which allows us to optimize parametric models. We consider three pseudoRiemannian manifoldsPp,qr ⊂ Sp,qr ⊂ Rp+1,q that we define below. We explain howPp,qr generalizes elliptic and hyperbolic geometries in the special cases where q = 0 and p = 0, respectively.
Notation. We denote points on a smooth manifoldM [16] by boldface Roman characters x ∈M. [x] := {x,−x} is a pair of antipodal points. TxM is the tangent space ofM at x and we write tangent vectors ξ ∈ TxM 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−1 (resp. cosh−1).
Ambient space Rp+1,q . Our ambient space Rp+1,q is a vector space of dimensionality d + 1 = p+ q + 1 ∈ N called pseudo-Euclidean space [21]. It is equipped with the following scalar product (i.e., nondegenerate symmetric bilinear form) of signature (p+ 1, q):
∀x = (x0, . . . , xd)> , y = (y0, . . . , yd)> , 〈x,y〉q := p∑ i=0 xiyi − d∑ j=p+1 xjyj = x >Gy, (1)
where the signature matrix G = G−1 = Ip+1,q is the (d+ 1)× (d+ 1) diagonal matrix with the first p + 1 diagonal elements equal to 1 and the remaining q equal to −1. Following general relativity literature and spacetime terminology [7], Rp+1,q has p+ 1 space dimensions and q time dimensions. Since it is a vector space, we can identify its tangent space to the space itself by means of the natural isomorphism TxRp+1,q ≈ Rp+1,q. Finally, the Euclidean space Rd+1 is the special case of Rd+1,0 which contains zero time dimension, and where G = Id+1,0 = I.
Total space Sp,qr . Our total space Sp,qr is a pseudo-sphere of radius r > 0 embedded in Rp+1,q . It is the following hypersurface:
Sp,qr := { x ∈ Rp+1,q : 〈x,x〉q = r2 } , (2)
It is equivalent to work with the pseudo-hyperboloid Qq,pr := {x ∈ Rq,p+1 : 〈x,x〉p+1 = −r2} and the pseudo-sphere Sp,qr as they are anti-isometric to each other (see supp. material). Moreover, the radius r > 0 plays a role of scaling factor so we consider it to be 1 although it can be learned [5, 14]. Finally, both x ∈ Sp,qr and its antipodal point −x lie on Sp,qr since 〈x,x〉q = 〈−x,−x〉q . Quotient manifold Pp,qr . We consider as equivalence relation the two-element group {±1} consisting of the identity map x 7→ x and the antipodal map x 7→ −x. This means that two points x ∈ Sp,qr and y ∈ Sp,qr are equivalent iff y = x or y = −x. We define the following projective space: Pp,qr := Sp,qr /± 1 = Sp,qr /± I = {{x,−x} : x ∈ Sp,qr } . (3) Every point of Pp,qr is an unordered pair that we denote by [x] := {x,−x}. Since Pp,qr is a projective space, every point [x] ∈ Pp,qr can be interpreted as the intersection of the pseudo-sphere Sp,qr with a line passing through the origin of Rp+1,q . In some cases, it might be easier to interpret points of Pp,qr as lines through the origin, and to study their properties when they intersect the pseudo-sphere. Each point [x] ∈ Pp,qr is also a submanifold of Sp,qr and a discrete space. In the following, we explain how Pp,qr extends spherical geometry to elliptic geometry (i.e., when q = 0), or naturally describes the hyperboloid model of hyperbolic geometry (i.e., when p = 0).
Elliptic geometry (q = 0). In spherical geometry, points lie on the unit d-sphere Sd := Sd,01 = {x ∈ Rd+1 : 〈x,x〉 = 1}. The geometry of the projective d-space Pd := Sd/± 1 is called elliptic geometry [24, 30]. Geodesic distances of Pd naturally account for the fact that they compare sets. Let dγ : Sd × Sd → R be the geodesic distance of Sd (i.e., spherical distance). The geodesic distance between [x] ∈ Pd and [y] ∈ Pd is dγ([x], [y]) = mina∈[x],b∈[y] dγ(a,b). We then have: dγ([x], [y]) := min{dγ(x,y), dγ(−x,y)} = cos−1(|〈x,y〉|) = cos−1(|〈x,y〉q|), (4) which is a 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 P0,q1 (p = 0). The q-dimensional manifold S0,q1 ⊂ R1,q contains two separate sheets (i.e., two connected components) and is anti-isometric to the hyperboloid of two sheetsQq,01 . Pairs of antipodal points lying on different sheets of S0,q1 are considered as a single point of P 0,q 1 . Let x ∈ S 0,q 1 and z ∈ S 0,q 1 be two points lying on the same sheet of S0,q1 , there exists no geodesic joining x and −z. Their geodesic distance with respect to S0,q1 can then be considered to be dγ(x,−z) = +∞, and we have:
dγ([x], [z]) := min{dγ(x, z),+∞} = dγ(x, z) = cosh−1(〈x, z〉q) = cosh−1(|〈x, z〉q|), (5) which is similar to the hyperbolic distance metric of the hyperboloid model studied in [20].
Ultrahyperbolic geometry (or indefinite elliptic geometry). In this paper, we propose a parametric model that learns representations lying on the quotient manifold Pp,qr . When both p and q are positive, the metric tensor of Pp,qr is nondegenerate (see page 343 of [16]) and indefinite. This means that the manifold is pseudo-Riemannian but not Riemannian due to the lack of positive definiteness of the metric tensor. Pp,qr is also called an indefinite elliptic space [30] 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. 1 illustrates the manifold P1,11 . Our main motivation for considering Pp,qr is that it is more flexible than hyperbolic and elliptic geometries since it contains hyperbolic and elliptic parts (i.e., time-like and space-like geodesics in Fig. 1). This flexibility allows us to better represent graphs that are not entirely trees or cycles, but that contain tree-like or cycle subgraphs. We experimentally verify our intuition.

heading: 3 Optimization on Ultrahyperbolic Quotient Manifolds
text: Our ultrahyperbolic representations lie on the quotient manifold Pp,qr . In this section, we provide differential geometry tools to optimize some differentiable function f : Pp,qr → R. To this end, we need the formulation of geodesics of Pp,qr . In Section 3.1, we explain how to formulate tangent vectors of Pp,qr as a function of tangent vectors of Sp,qr via the horizontal lift operator. This operator allows us to formulate geodesics of Pp,qr as a function of geodesics of Sp,qr in Section 3.2. In Section 3.3, we state the properties that the function f has to satisfy due to the quotient nature of Pp,qr . 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.1 Representing tangent vectors of Pp,qr only by horizontal tangent vectors of Sp,qr
It can be difficult to work numerically with the tangent space T[x]Pp,qr of Pp,qr at [x] since [x] = {x,−x} is an equivalence class. We now present some differential geometry tools to define tangent vectors of Sp,qr as a function of tangent vectors of Pp,qr , 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,qr . We first give the formulation of tangent spaces of Sp,qr and then provide tools to identify tangent vectors of Pp,qr . These tools will be essential to construct geodesics of Pp,qr and represent them via Sp,qr . The tangent space TxSp,qr of Sp,qr at x can be defined as: TxSp,qr := {ξ ∈ Rp+1,q : 〈ξ,x〉q = 0}. The canonical map (or natural map [21]) π : Sp,qr → Pp,qr is defined as: ∀x ∈ Sp,qr , π(x) := [x] = {x,−x}. Its differential at x is denoted by dπx : TxSp,qr → T[x]Pp,qr . The horizontal space Hx and the vertical space Vx at x ∈ Sp,qr are subspaces of TxSp,qr defined such that TxSp,qr = Hx ⊕ Vx is a direct sum of linear spaces, and Vx is the following kernel: Vx := ker(dπx). From Proposition 5.38 of [16], we find ker(dπx) = Tx([x]) = 0 because [x] is a discrete space so [x] and its tangent spaces are 0-dimensional. We then haveHx = TxSp,qr . Elements ofHx are called horizontal vectors, and all the tangent vectors of Sp,qr are horizontal. The horizontal lift (see §29 of [29]) at x ∈ Sp,qr of the tangent vector ξ ∈ T[x]Pp,qr is the unique horizontal vector denoted by ξx = liftx(ξ) ∈ Hx such that dπx(ξx) = ξ. Since Hx = TxSp,qr , the liftx operator is bijective so tangent vectors in T[x]Pp,qr can be equivalently represented by horizontal vectors inHx. 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,qr is convenient since it implies that any tangent vector in TxSp,qr can be represented in T[x]Pp,qr . We can then construct a geodesic of Pp,qr from any geodesic of Sp,qr as discussed below.
3.2 Geodesic of Pp,qr , exponential map and parallel transport
To optimize over Sp,qr andQq,pr , Gao et al. [9] and Law & Stam [15] define tools such as the geodesic, parallel transport, exponential map, logarithm map and the geodesic distance dγ : Sp,qr × Sp,qr → R (see formulations in the supp. material). Our contribution in this subsection is that we extend all of the above differential geometry tools to Pp,qr . Their details can be found in the supp. material. The geodesic γx→ξx : R→ S p,q r of Sp,qr is the curve defined such that its initial point is γx→ξx(0) = x ∈ Sp,qr , its initial velocity is γ′x→ξx(0) = ξx ∈ TxS p,q r and its acceleration is zero. When the initial conditions are clear from the context, we denote the geodesic by γ and ignore its indices. Since every geodesic γ of Sp,qr satisfies ∀t, γ′(t) ∈ Hγ(t), it is called horizontal and γ := π ◦ γ : R→ Pp,qr is a geodesic of Pp,qr . By the chain rule, we have ∀t, γ′(t) = dπγ(t)(γ′(t)), which implies ∀t, liftγ(t)(γ′(t)) = γ′(t). We then have ∀t ∈ R, γ[x]→ξ(t) = {γx→ξx(t), γ−x→ξ−x(t)}, and we find ξx = −ξ−x to preserve the equivalence between antipodal points: γx→ξx(t) = −γ−x→ξ−x(t).
Exponential and logarithm map. The exponential map of Pp,qr at [x] is the differentiable mapping exp[x] : T[x]Pp,qr → Pp,qr defined such that exp[x](ξ) := γ[x]→ξ(1) = {γx→ξx(1), γ−x→ξ−x(1)}.
We denote the exponential map of Sp,qr at x by expx : TxSp,qr → Sp,qr . It is defined as expx(ξx) := γx→ξx(1), and we have exp[x](ξ) = [expx(ξx)]. 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 −1 [x] ). Their exact formulation can be found in the supp. material.
Parallel transport on Sp,qr . Given the minimizing (unbroken) geodesic γ (i.e., minimizing the arc length) from x = γ(0) to y = γ(1), the parallel transport P γxyy : TxSp,qr → TySp,qr is a linear isometry such that ∀ξx, ζx, 〈ξx, ζx〉q = 〈P γxyy(ξx), P γxyy(ζx)〉q (see page 66 of [21]). The parallel transport along γ from x to y (where x and y satisfy 〈x,y〉q > −r2) is:
P γxyy(ξx) := ξx − 〈y, ξx〉q 〈x,y〉q + r2 (y + x) (6)
Minimizing geodesic of Pp,qr . Our parallel transport on Pp,qr depends on a minimizing geodesic γ whose arc length (that we call geodesic distance dγ) from [x] = γ(0) to [y] = γ(1) is:
∀[x] ∈ Pp,qr , [y] ∈ Pp,qr , dγ([x], [y]) =
{ r cosh−1(| 〈x,y〉qr2 |) if | 〈x,y〉q r2 | ≥ 1
r cos−1 (| 〈x,y〉qr2 |) otherwise. (7)
and we have dγ(x,y) < dγ(−x,y) iff 〈x,y〉q > 0. See details in the supp. material. The parallel transport P γ[x]y[y] on P p,q r can be horizontally lifted onHy as discussed above:
∀ξ ∈ T[x]Pp,qr , lifty(P γ [x]y[y](ξ)) = { P γxyy(ξx) if 〈x,y〉q > 0 P γ−xyy(ξ−x) if 〈x,y〉q < 0.
(8)
If 〈x,y〉q = 0, we have dγ(x,y) = dγ(−x,y) and there exist two minimizing geodesics joining [x] and [y]. In practice, we arbitrarily choose one of these two geodesics when 〈x,y〉q = 0.
3.3 Optimized function f : Pp,qr → R
Our goal is to minimize some differentiable function f : Pp,qr → R. We now describe the two properties that f has to satisfy. We first recall that every [x] ∈ Pp,qr is a set of equivalent elements that should preserve invariance. To simplify explanations, we consider the function f : Sp,qr → R defined such that f := f ◦ π. We then have ∀x ∈ Sp,qr , f(x) = f([x]).
Property 1. Since x and −x are equivalent, the first property that f has to satisfy is f(x) = f(−x).
Property 2. Let ∇f(x) := (∂f(x)/∂x0, . . . , ∂f(x)/∂xd)> be the Euclidean gradient of f at x = (x0, . . . , xd) >. The pseudo-Riemannian gradient of f at x ∈ Sp,qr is Df(x) := Πx(G −1∇f(x)) = Πx(G∇f(x)) ∈ TxSp,qr where Πx(z) := z− 〈z,x〉q 〈x,x〉q x is the orthogonal projection of z onto TxS p,q r .
Let Df([x]) ∈ T[x]Pp,qr be the pseudo-Riemannian gradient of f at [x] ∈ Pp,qr . By applying the chain rule, the second property that f has to satisfy is liftx(Df([x])) = Df(x) = −Df(−x).

heading: 3.4 Optimization of parametric models
text: We now explain how to minimize some function f : Pp,qr → R that takes as input the ultrahyperbolic representation returned by some parametric model ϕθ (e.g., a neural network with parameters θ) that we want to learn. We exploit the fact that, due to the properties of the (affine) Levi-Civita connection [6, 17] of Pp,qr , the metric of the manifold Pp,qr is preserved when we work with its tangent spaces via the exponential map (see page 61 of [21]).
Forward pass. Let us consider the positive pole p = (r, 0, . . . , 0)> ∈ Sp,qr defined such that only its first element r > 0 is nonzero. The horizontal space of p can be defined as the following vector space Hp = TpSp,qr = {0} × Rp,q. The mapping ϕθ : X → Hp maps any input data x ∈ X to Hp and the resulting horizontal vector is mapped to Sp,qr with the exponential map as follows: x := expp (ϕθ(x)) ∈ Sp,qr . As mentioned above, working with the vector spaceHp greatly simplifies computations and preserves the metric thanks to the Levi-Civita connection of Pp,qr .
Note that for standard neural networks that map to Rd, the tangent space is identified to the space itself by the natural isomorphism TxRd ≈ Rd so the network weights also implicitly lie in the tangent space. Our approach extends Euclidean neural networks to Pp,qr .
Backward pass. We assume that the function f : Sp,qr → R satisfies the properties mentioned in Section 3.3. By exploiting Eq. (8), the horizontal lift of the parallel translate of the gradient Df([x]) can be formulated as follows:
λ[x],p := liftp ( P γ[x]y[p](Df([x])) ) = { P γxyp(Df(x)) if 〈x,p〉q ≥ 0 P γ−xyp(−Df(x)) otherwise.
(9)
Descent direction. When the metric tensor of the manifold is not positive definite, the manifold is not Riemannian and the negative of λ[x],p is not a descent direction [9]. We show in the supp. material that the negative of Gλ[x],p ∈ Hp is a descent direction that can be used to optimize the parameters of ϕθ with standard descent algorithms. We illustrate one such example in Section 5.1.
Complexity. Our optimizer exploits efficient closed-form expressions on Sp,qr by considering x 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〉q, which is also the sign of the first element of x = (x0, . . . , xd)
> (i.e., , dγ(x,p) < dγ(−x,p) ⇐⇒ 〈x,p〉q > 0 ⇐⇒ x0 > 0). Our operators generalize tools used in hyperbolic space and are then as efficient as hyperbolic approaches.

heading: 4 Ultrahyperbolic Graph Convolutional Network (GCN)
text: We now extend the hyperbolic graph neural networks introduced in [18] to Pp,qr . 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 a graph. We recall the formulation of Graph Convolutional Networks (GCNs) [13] and rewrite them in our formalism with quotient manifolds. Let G = (V,E) be a undirected graph containing n = |V | nodes and m = |E| edges. Its adjacency matrix is denoted by A ∈ Rn×n. To account for self-loops, Liu et al. [18] consider the matrix Ã = D−1/2(A + I)D−1/2 where D is the diagonal degree matrix defined such that Dii = ∑ j(Aij + Iij). The vector representation of node v at step k is denoted by hkv ∈ Rd, and h0v is given. Wk is a matrix whose elements are the trainable parameters of the k-th layer. The information in the Euclidean GCN propagates as: hk+1u = σ (∑ v∈I(u) ÃuvW khkv
) where I(u) is the set of in-neighbors of u ∈ V (i.e., u and v are joined by an edge) and σ is a nonlinear activation function such as the element-wise Rectified Linear Unit (ReLU) or its variants.
Ultrahyperbolic GNN. Let us now consider that ∀v, k,hkv ∈ Pp,qr . Since Pp,qr is not a vector space, the operation Wkhkv is not defined, and the activation function σ 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,qr via the exponential map and its inverse (i.e., logarithm map). The propagation is then extended to Pp,qr by:
hk+1u := σ expp( ∑ v∈I(u) ÃuvW k liftp ( log[p](h k v) )) ∈ Pp,qr , (10)
where p = (r, 0, . . . , 0)> is the positive pole and we exploit the logarithm map to map points of Pp,qr to a single tangent space. As explained in Section 3, in practice, we use the horizontal lift operator so that the exponential and logarithm maps only consider the horizontal spaceHp during optimization (see supp. material for details). The hyperbolic GNN [18] corresponds to the special case where Pp,qr = P 0,q 1 (i.e., p = 0). We now give the formulation of the activation function σ.
Activation function via stereographic projection. For simplicity of exposition, we now consider that the radius of Sp,qr is r = 1. To enforce nonlinearity between the different layers of the hyperbolic graph neural network, Liu et al. [18] formulate their activation function as the result of a steoreographic projection onto the negative pole −p from the hyperboloid model to the Poincaré ball, followed by a ReLU activation (in the Poincaré ball) and an inverse steoreographic projection from the Poincaré ball to the hyperboloid. We explain below how to generalize σ to pseudo-spheres.
Let us note ε ∈ {−1, 1}. The pole εp = (ε, 0, . . . , 0)> is positive if ε = 1, and negative if ε = −1. Let us consider a point x = (x0, x1, . . . , xd)> ∈ Sp,q1 with x0 > 0 (i.e., lying on the positive hemisphere). The stereographic projection of x onto εp is a = ωε(x) := 11−εx0 (x1, x2, . . . , xd)
>. If x0 < 0, we equivalently consider that a = ωε(−x) = −ω−ε(x) instead of ωε(x) due to the quotient nature of Pp,qr and to account for the fact that [x] is projected onto the pole of different hemisphere if ε = −1, or same hemisphere if ε = 1. The inverse projection of a = (a1, . . . , ad)> ∈ Rp,q is:
ω−1ε (a) := 1
1 + 〈a,a〉q
( ε(〈a,a〉q − 1)
2a
) ∈ Sp,q1 where 〈a,a〉q := p∑ i=1 a2i − d∑ j=p+1 a2j . (11)
We formulate σ([x]) := [ω−1ε (ReLU(ωε(x)))] if x0 ≥ 0, and σ([x]) := [ω−1ε (ReLU(ωε(−x)))] otherwise, where ReLU (or one of its variants such as LeakyRelu) is applied element-wise only on the q time dimensions of the input vector, which avoids having a zero denominator in Eq. (11). As in [18], we consider ε = −1. It is worth noting that Liu et al. [18] work with the upper sheet of the hyperboloid Qq,01 which is anti-isometric to S 0,q 1 . Their stereographic projection then contains only space dimensions. Their space dimensions correspond to our time dimensions due to anti-isometry.

heading: 5 Experiments
text: We now evaluate our approach on different classification tasks on graphs. We first show that our optimization framework introduced in Section 3.4 learns meaningful representations on a toy hierarchical graph with cycles. We then apply our framework in standard classification tasks.

heading: 5.1 Last layer optimization on a toy dataset
text: We evaluate our optimization framework by training a multi-layer perceptron (MLP) ϕθ : X → Hp whose set of parameters is called θ. 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 to a conflict between two leaders (the instructor and the administrator). It is an undirected graph G = (V,E) which has node-set V = {vi}ni=1 and edge-set E = {ek}mk=1 where n = 34 and m = 78. Each node vi represents a karate member and an edge joins two nodes if the two members are friends. The two leaders are v1 and v34. We consider that each node vi is represented as a distinct n-dimensional one-hot vector xi ∈ X . Problem. Following [15], our goal is to learn representations of nodes such that pairs of nodes joined by an edge (i.e., in E) have smaller distance than pairs of nodes that are 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 θ ∑ (vi,vj)∈E − log e −d(%θ(xi),%θ(xj))/τ∑
(va,vb)∈ Wij
e−d(%θ(xa),%θ(xb))/τ where %θ(xi) := [expp (ϕθ(xi))] (12)
and whereWij := {(vi, vj)}∪{(va, vb) /∈ E}, τ = 10−2 is a fixed temperature value, and d denotes the geodesic distance of the manifold (e.g., Eq. (7) for Pp,qr ). The geodesic distance satisfies the two properties defined in Section 3.3 with respect to each input and can then be used for optimization.
Model. Our MLP ϕθ : X → Hp contains three hidden layers of 104 hidden units each, with standard ReLU as nonlinear activation function. In this toy experiment, our MLP is standard, with the only
exception that its last layer maps to the horizontal space Hp = {0} × Rp,q 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 3.4 to update θ. By using the descent direction −Gλ[xi],p for each sample [xi] = %θ(xi), all the parameters of our standard MLP 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 Pp,q1 (i.e., p+ q = 4) and show in Fig. 2 (left) the loss values of Eq. (12) as a function of the number of iterations for different values of p ∈ {0, . . . , 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 −λ[xi],p is used as a search direction (instead of −Gλ[xi],p) when the metric tensor is not positive definite since −λ[xi],p 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 a neural network. We run 10 random initializations for each considered 4-dimensional manifold and report in Table 1 the mean and standard deviation of the different evaluation metrics.
As in [15], following the idea that hyperbolic distances grow exponentially, we take the sum of distances δi = ∑n j=1 d([xi], [xj ]) of a node vi with all the other nodes as an indicator of importance. We sort the different δ1, . . . , δn 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 1. The leaders tend to have smaller δi 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 rank correlation coefficient [28] between the 5 (or 10) most important nodes in the hierarchy and their corresponding δi score. Once again, the order of the δi scores is more correlated with the hierarchy level in ultrahyperbolic space. Our experimental results are comparable with [15] although our nodes are represented on a quotient manifold and we learn a parametric model. Fig. 2 (right) illustrates our learned representations when the manifold is P1,11 . Products of Riemannian space forms. In Table 1, we compare the performance of models mapping representations to pseudo-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 representations) 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 if 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 Pp1,q1r1 × P p2,q2 r2 or even P p1,q1 r1 × R p2,q2 for evaluation.
Nonetheless, since our space form Pp,qr 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 pseudoRiemannian space form Pp,qr . Training times. We report in Table 1 the training times of our Pytorch [22] implementation to train 25,000 iterations on a machine equipped with a 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.

heading: 5.2 Classification with ultrahyperbolic graph convolutional networks
text: 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 semisupervised node classification task on three citation network datasets: Citeseer, Cora and Pubmed [26]. They contain sparse bag-of-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 a GCN with 2 hidden layers.
When the dimensionality of each layer is d = 600, all the Euclidean (i.e., standard), Hyperbolic and Ultrahyperbolic 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, we trained GCNs whose dimensionality of each layer is d = 4 with 100 random initializations. The results reported in Table 3 show the superiority of ultrahyperbolic representations in low-dimensional space for node classification of hierarchical graphs with cycles. We also report results for d = 10 in the supp. material. The conclusion is similar.
Graph classification. We also evaluate our approach on commonly used graph kernel benchmark datasets [12] whose statistics are reported in Table 4. The evaluation is done via 10-fold cross validation. We use the same protocol evaluation and splits as in Appendix E of [18] and evaluate our approach in the same settings including same number of GNN layers, optimizers, learning rate, and manifold dimensionality d reported in Table 5. The only difference is that the data is represented on Pp,qr with p = 1 in our case. The comparative performances are reported in Table 5 and show that ultrahyperbolic representations significantly improve performance on the D&D and Enzymes 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 is more visible for protein structures than for social networks, at least in high-dimensional space. More details can be found in the supp. material.

heading: 6 Conclusion, Limitations and Potential Societal Impacts
text: We have introduced neural networks that map data to a (quotient) pseudo-Riemannian manifold of constant nonzero curvature. Our considered geometry generalizes both hyperbolic and elliptic geometries. It is the first neural network that maps data to a non-Riemannian 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 networks to the pseudo-hyperboloid Qq,pr which is a pseudo-Riemannian manifold of constant nonzero curvature anti-isometric to the pseudo-sphere Sp,qr . One main difference is that, since there exist pairs of points of Qq,pr that cannot be joined by an unbroken geodesic, the optimization framework in [31] does not exploit the intrinsic geometry of the manifold via its Levi-Civita connection. On the other hand, our approach uses pseudo-Riemannian optimization tools that are intrinsic to Pp,qr . 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 is a 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,qr . It 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,qr 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 a theoretical analysis similar to Gromov’s work [10] in the case of graphs without cycles. However, the optimal geometry for graphs with cycles is still an open problem, and hyperbolic geometry is used heuristically in this case. Our motivation is that ultrahyperbolic manifolds are more general than hyperbolic and elliptic manifolds, they can then combine the strengths of the two induced geometries. We experimentally validate our 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 to 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 I was working from home during the COVID-19 pandemic. I am also grateful to the NeurIPS 2021 program committee for giving me free registration to the conference thanks to an Outstanding Reviewer Award.

Review summaries:
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. 

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.