Pseudo-Riemannian Graph Convolutional Networks
Authors: Bo Xiong
Shichao Zhu
Nico Potyka
Shirui Pan
Chuan Zhou
Steffen Staab
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Convolutional Networks
Graph Embeddings
Non-Euclidean Embeddings

Abstract: Graph Convolutional Networks (GCNs) are powerful frameworks for learning embeddings of graph-structured data. GCNs are traditionally studied through the lens of Euclidean geometry. Recent works find that non-Euclidean Riemannian manifolds provide specific inductive biases for embedding hierarchical or spherical data. However, they cannot align well with data of mixed graph topologies. We consider a larger class of pseudo-Riemannian manifolds that generalize hyperboloid and sphere. We develop new geodesic tools that allow for extending neural network operations into geodesically disconnected pseudo-Riemannian manifolds. As a consequence, we derive a pseudo-Riemannian GCN that models data in pseudo-Riemannian manifolds of constant nonzero curvature in the context of graph neural networks. Our method provides a geometric inductive bias that is sufficiently flexible to model mixed heterogeneous topologies like hierarchical graphs with cycles. We demonstrate the representational capabilities of this method by applying it to the tasks of graph reconstruction, node classification, and link prediction on a series of standard graphs with mixed topologies. Empirical results demonstrate that our method outperforms Riemannian counterparts when embedding graphs of complex topologies. 

Pseudo-Riemannian Graph Convolutional Networks
Bo Xiong University of Stuttarrt Stuttgart, Germany
Shichao Zhu" IIE Chinese Academy of Sciences Beijing, China
Nico Potyka Imperial College London London, United Kingdom
Shirui Pan Griffith University
Chuan Zhou
Steffen Staab University of Stuttgart
AMSS, Chinese Academy of Sciences Beijing, China
Queensland, Australia
University of Southampton Stuttgart, Germany
Abstract
Graph convolutional networks (GCNs) are powerful frameworks for learning em- beddings of graph-structured data. GCNs are traditionally studied through the lens of Euclidean geometry. Recent works find that non-Euclidean Riemannian man- ifolds provide specific inductive biases for embedding hicrarchical spherical data. However, they cannot align well with data of mixed graph topologies. We consider a larger class of eseudo-Riemannin boloid and sphere. We develop new geodesic tools that allow for extending neu- ral network operations into geodesically disconnected neuuo-Riemanniaa mani- folds. As consequence, we derive in meeudo-Riemannian manifolds constant nonzero curvature the context of graph neural networks. Our method provides geometric inductive bias that is sufficiently flexible to model mixed heterogeneous topologies like hierarchi- cal graphs with cycles. We demonstrate the representational capabilities of this method by applying it to the tasks graph reconstruction, node classification and link prediction results demonstrate that our method outperforms Riemannian counterparts when embedding graphs of complex topologies.
manifolds that generalize hyper-
Riemmnnin GCN that models data
series of standard graphs with mixed topologies. Empirical
Introduction
Learning from graph-structured data is pivotal task in machine learning, for which graph con- volutional networks (GCNs) 2 B 4 have emerged as powerful graph representation learning techniques. GCNs exploit both features and structural properties in graphs, which makes them well- suited for a wide range of applications. For this purpose, graphs are usually embedded in Riemannian manifolds equipped with positive definite metric. Euclidean geometry is special case of Rieman- nian manifolds constant zero curvature that can be understood intuitively and has well-defined operations. However, the representation power of Euclidean space is limited (5), especially when embedding complex graphs exhibiting hierarchical structures [6]. Non- Euclidean Riemannian man- ifolds of constant curvatures provide alternative to accommodate specific graph topologies. For example, hyperbolic manifold of constant negative curvature has exponentially growing volume and well suited represent hierarchical structures such tree-like graphs 77
I0]
[1. Similarly,
spherical manifold of constant positive curvature suitable for embedding spherical data in vari- including graphs with cycles. Some recent works [T5.
fields [12
13 [4]
16 17
[
[9] have
extended GCNs to such non-Euclidean manifolds and have shown substantial improvements.
"Equal contribution. Correspondence to bo..ioog max.iinn@ivs.uuni-iiiii wnrsssuuiissun stuttgart.de
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

X
X1
X1
X2
X3
X2
X2
X3
(a) |xo| <1
(b) |xol =
(c) |xol >
Figure The different submanifolds of a four-dimensional pseudo hyporbboyerboooid of curvature -1 with two time dimensions. By fixing one time dimension .o. the induced submanifolds include (a) an one-sheet hyperboloid, (b) the double cone, and (c) two-sheet hyperboloid.
The topologies in real-world graphs 5 however, usually exhibit highly heterogeneous topological structures, which are best represented by different geometrical curvatures. A globally homogeneous geometry lacks the flcxibility for modeling complex graphs (20]. Instead of using a single manifold, product manifolds 21 combining multiple Riemannian manifolds have shown advantages when embedding graphs of mixed topologies. However, the curvature distribution of product manifolds is the same each point, which limits the capability of embedding topologically heterogeneous graphs. Furthermore, Riemannian manifolds are equipped with positive definite metric disallowing for the faithful representation of the negative
input similarities (2
Going beyond Riemannian manifolds, Soaudo-Riemannian manifolds equipped with indefinite met- rics constitute a larger class of geometries, vature do not only generalize the hyperbolic and spherical manifolds, but also contain their subman- ifolds (Cf. Fig. I thus providing inductive biases specific to these geometries. geometry with constant zero curvature (i.e. Lorentzian spacetime) was applied to manifold learn- ing for preserving local information of non-metric data (5) and embedding directed acyclic graph [23). To model complex graphs containing both hierarchies and cycles, Beeudd--immannian man- ifolds with constant nonzero curvature have recently been applied into graph embeddings using non con-parametric learning [24 25 26 but the representation power of these works is not on par with the Riemannian counterparts yet, mostly because the absence of geodesic tools to extend neural network operations into Semudo-Riemaaniaa geometry.
manifolds of constant nonzero cur-
Riemmmnnna
In this paper, we take the first step extend GCNs into pseudo- Riemannian manifolds foregoing the geometry for GCNs is requirement to have positive definite metric. Exploiting -aaunninnmnnnnnn geometry. There exist non-trivial because of the geodesical disconnectedness broken points that cannot be smoothly connected by a geodesic, leaving necessary geodesic tools un- defined. To deal with it, we develop novel geodesic tools that empower manipulating representations in geodesically disconnected pseudo- Riemmaniin manifolds. We make it by finding diffeomorphic manifolds that provide alternative geodesic operations that smoothly avoid broken cases. Subse- quently, we generalize GCNs to learn representations of complex graphs in pseudo-Riemannian geometry by defining corresponding operations such as linear transformation and tangential ag- gregation. Different from previous works, the initial features of GCN could be fully defined in the Euclidean space. Thanks to the diffcomorphic operation that is bijective and differentiable, the stan- dard gradient descent algorithm can be exploited to perform optimization.
To summarize, our main contributions are as follows: We present neural network opera- tions in Secudo-Riemannian manifolds with novel geodesic tools, to stimulate the applications of neudo-Riemanne geometry in geometric deep learning. 2) We present principled framework, Sheudo-Riemannn GCN, which generalizes GCNs into Aseudo-Riemanee definite metries, providing more flexible inductive biases to accommodate complex graphs with mixed topologies. 3) Extensive evaluations on three standard tasks demonstrate that our model outperforms baselines that operate in Riemannian manifolds. Source code is open available at https://github.com// hotpr//bb.oomiiiooooooooooGGGG
manifolds with in-

---

2 Preliminaries
2.1 Pseudo-Riemannian manifolds
A Speudo-Riemannial manifold [27] (M,g) g) is a smooth manifold M equipped with a nondegen- erate and indefinite metric tensor g. Nondegeneracy means that for a given & E TxM, for any TT we have (x = 0, then 5 = 0. The metric tensor g induces a scalar product on the langen! space TxM for each point E .M such that yx T x Tx-M- - IR, where the tangent space TxM can be seen as the first order local approximation of M around point x. The elements of TxM are called tangent vectors. Indefinity means that the metric tensor could be of arbitrary signs. A principal special case is the Riemannian geometry, where the metric tensor is positive definite (i.e. & 0).
vV E Tx KxM, (E. E)
Pseudo-hyperroooid By analogy with hyperboloid and sphere in Euclidean space. Pseudo- hyperboloids are defined as the submanifolds in the ambient pseudo-Euclidean space Rs.++1 with the dimensionality of s + t + that uses the scalar product as Vx, y R=++1 (x,y): y)+ Ei= T3ys + Ej KyJjj. The scalar product induces a norm ||x||² (x, x), that can be used to define
O3 = [x= T1, ... ,.,-,) g ||x|| = _). where is nonzero real number parameter of curvature. 23 is called pseudo-sphere when B 0 and pseudo-hyperboloid when 3 < 0. Since 23 is interchangeable with
we consider the pseudo houub-hyperbololidd here. Following the terminology of special relativity, a point in Q can be interpreted as an event [5], where the first + dimensions are time dimensions and the last s dimensions are space dimensions. Hyperbolic IH and spherical S manifolds can be defined as the special cases of pscudo-hyperboloids by setting all time dimensions except one to be zero and set- ting all space dimensions to be zero, respectively, i.e. H3 = 2 S = 2
2.2 Geodesic tools of pseudo-hyyeerboloi
Geodesic A generalization of straight-line the Euclidean space a manifold is called the geodesic 15] 28 Formally, a geodesic is defined as a constant speed curve 7 : + 7(T) E
M, 00, 1] joining two points x. E M that minimizes the length, where the length of curve is given by [17) fJ v /l (l
dt. The geodesic holds that x arg min, L(y), such that 70) = x, r11 = y. and ||
1. By the means of the geodesic, the distance between x.y E 2 is defined as the are length of geodesic 7(T).
Exponential and logarithmic maps The connections between manifolds and langent space are established by the differentiable exponential map and logarithmic map. The exponential map at x is defined as expx ( = (1), which gives a way project a vector & T a exp (E) M on the manifold. The logarithmic map logx :M- - T is defined as the inverse of the exponential map (i.c. log, = expx )). Note that since 2² is geodesically complete manifold, the domain of
the exponential map D, is hence defined on the entire tangent space, i.c. D. = Tx 2 However, as we will explain later, the logarithmic map (y) is only defined when there exists a length- minimizing geodesic between x, y E Oz More details can be found in the Appendix
Geodesical connectedness A eseudo-Riemantnn manifold M is connected iff any two points of M can be joined by a piecewise (broken) geodesic with each piece being a smooth geodesic. The manifold is geodesically connected (or g-comnected) iff any two points can be smoothly connected by a geodesic, where the two points are called g g-connected, otherwise called g- g-discommected. Differ- ent from Riemannian manifolds in which the geodesical completeness implies the g- g-connectedness Hlopf-Rinow theorem (29). pseudo- hyperbbood is geodesically complete but not g-connected manifold where there exist points that cannot be smoothly connected by a geodesic [BO]. For- mally, in the pseudo-hyperboloid, two points x, E 2 are g-connected iff (x,y): |/].
The set of g-connected points of x Q is denoted its normal neighborhood Ux
3

---

{ye 23 (x,y), < } For g-disconnected points x, Oz.. there does not exist tan-
gent vector & such that (E), which implies that its inverse log (-) is only defined in the normal neighborhood of x. nutshell, the geodesic tools for the g-disconnected cases are not well-defined, making it impossible to define corresponding vector operations.
3
Pseudo-Riemaniial GCNs
In this section, we first describe how to tackle the g-disconnectedness in -ieemmnniemnnninn mani- folds. Then we present the pseudo-Rise Riemannian GCNs based on the proposed geodesic tools.
3.1 Diffeomorphic geodesic tools
One standard way to tackle the g-disconnectedness in differential geometry is to introduce diffeo- morphic manifolds in which the operations well-defined. A diffeomorphic manifold can be de- rived from diffcomorphism, defined as follows.
Definition (Diffeomorphism (27). Given two manifolds M and M', smooth map vb M + M' is called diffeomorphism if vo is bijective and its inverse 1/=1 is smooth as well. If diffeomorphism between M and M' exists, we call them diffeomorphic and write M MM..
For gpeudo-Riemaninn hyperboloid into the product manifolds of an unit sphere and the Euclidean space.
manifolds, the following diffeomorphism 24 decomposes pseudo-
Theorem 1 (Theorem 4.1 in (24)) For any point x E 23²², there exists a diffeomorphism sb O3 $ RR that maps x into the product manifolds of an unit sphere and the Euclidean space.
The diffeomorphism is given in the Appendix D.I. In light of this, we introduce a new diffeomor- phism that maps x to the product manifolds of sphere with curvature 11/3 and the Euclidean space. Theorem 2. For any point into the product manifolds of a sphere and the Euclidean space (proof in the Appendix D.2).
2 there exists diffeomorphism v : 2 + St_ x R that maps
Compared with Theorem ! this diffeomorphism preserves the curvatures in the diffeomorphic com- ponents, making it satisfy some geometric properties, c.g. the mapped point X; E 3 still lies on the making moving the tangent vectors from the pseudo-hype hypuudoooporoo surface of the manifold easy as we explained later. We call v as the spherical projection. to the diffeomorphic
Exponential and logarithmic maps. Considering that pseudo-hyperboloid 23 is g- discomeetedd, we propose to transfer the logmap and expmap into the diffeomorphic manifold 3 O + S x R", since the product manifold Shg x R is g-connected. To map tangent vectors between tangent space of O and S' x R², we exploit pushforward that induce linear approximation of smooth maps on tangent spaces.
Definition 2 (Pushforward). Suppose that vé -M- + M' is a smooth map, then the differential of ubz díb at point is linear map from the tangent space of M to the langent space of M' at (x). Namely, dub TT.M - M'
Intuitively, pushforward can be used to push tangent vectors on T.O.² forward to tangent vectors on S St x R Based on this, the new logmap and its inverse expmap can be defined by Eq. d
logez (x) - - (logss, xRx (x)),, exPo: (E) + (expss XR= (x))))
where v-() is the spherical projection and s --) the inverse. The mapping of tangent vectors is achieved by pushforward operations. The operations logs: XR- (-) and expst XB- (.) in the product manifolds can be defined as the concatenation of corresponding operations in different components.
loggr xR (x') = logs:
(x() || (x'), exps XR= (E) = expst (E:) expre (E.), (2)
where || denotes the concatenation, x' = v/s(x) consists of spherical features x E SLg and Eu-
clidean features x, E I E the tangent vector induced by x on O'
We choose points where space dimension 0 as the reference points due to the following property.

---

Theorem 3. For any reference point x =
(1)
6
E 233² with space dimension s O, the induced
tangent space of 2aa² is equal to the tangent space of its diffeomorphic manifod St x R2, namely, (S'S x Rd) Tx Lzz (proof in the Appendix D.3
The intuition of proof is that if space dimension s 0. the pushforward (differential) function just influences time dimension, for which the mapping is just an identity function (see Appendix D.2.. In this way, although we transfer logmap and expmap to the diffeomorphic manifold S'L x
RR" the diffeomorphic operations (-) and expx (-) are still bijective functions from the pseudo- hyperboloid to the tangent space of the manifold itself. Hence, our final operations are actually still Note that such property only holds when our Theorem 2 is applied and the special reference points with space dimension 0 are chosen.
defined in the tangent space of the
By leveraging the new logmap and expmap, we further formulate the diffeomorphic version of tan- gential operations as follows.
Tangential operations.
For function f : R + Rd", the pseudo-hyperboloid version f : 2
og with s + dnddd s +t' d' can be defined by the means of log 18 (-) and exp Eq.
(0) = expx (s (1oR2 ())):
(3)
where x is the reference point. Note that this function is a morphism (i.e. g)) = 10 go) and direction preserving (i.e. (-) fine -yeudo-hyperboloid version of vector operations such like scalar multiplication, matrix-vector multiplication, tangential aggregation and point- wise non- non-linearity and so on.
o
(())(I)(())) [1) making it a natural way to de-
Parallel transport. Parallel transport the generalization of Euclidean translation into manifolds.
Formally, for any two points x and y connected by geodesic, parallel transport P (E) TxMM- - Ty.M is an isomorphism between two tangent spaces by moving one tangent vector Ç T.MM with tangent direction & E T.MM to another tangent space Ty.M. The parallel transport in pseudo- hyperboloid can be defined as the combination of Riemannian parallel transport [3I. However, the parallel transport has not been defined when there does not exist a geodesic between and y. i.e. the tangent vector Ç induced by x can not be transported to the tangent space of points outside of the normal neighborhood Ux. Intuitively, the normal neighborhoods satisfy the following property.
Theorem 4. For any point x E L'g'. the union of the normal neighborhood of x and the normal neighborhood of its antipodal point- -x cover the entire manifold. Namely, Ux U O² (proof in the Appendix D.4.
This theorem ensures that if a point y & Ux. its antipodal point -y E Uxx Besides, MyM is parallel to T-y.. Hence, P Xx can be alternatively defined as P x for broken points. This result is addition, such as bias translation, detailed in section 3.2
crucial to define the
Broken geodesic distance. By the means of geodesic, the induced distance between x and y in pscudo-hyperboloid is defined as the are length of geodesic 7(T). given by (x.,)
/ (Ilogg(>))] [I] For broken cases in which log,(y is not defined, one approach is to use approx- imation like 2 Different from that, define following closed-form distance, given by Eq.
{ y), π / + dx, -y), if xf ||| Dx(x,))
if (x, y), < [8]
(4)
The intuition is that when x,y E 232h are g-disconnected, we consider the distance as dx, y) (x, -x) +
(x, -y) + d-y, Since dx, -x) = d (-) / 1 is a constant and d, (-x,y) = dx y), the distance between broken points can be calcu- lated as dx,xx. y) = (x,
d, y- or
To clarify theoretical contributions, our Theorem is nessasary for our Theorem S while Theorem g is nessasary for transforming the GCN operations directly into the tangent space of the pseudo- hyperboloid. Besides, we are the first to formulate the diffcomorphic expmap, logmap and tangential
5

---

operations of port and geodesic distance are discussed in the literature 24 3TI However, we re-formulate parallel transport with Theorem to avoid broken issues and propose new distance measure using the broken geodesic (Eq which different from the approximated distance in 24
to avoid broken cases. The theoretical properties of parallel trans-
3.2 Model architecture
GCNs can be interpreted as performing neighborhood aggregation after a linear transformation on node features of each layer. We present pseudo-Riemannian GCNs (Q-GCN) by deriving corre- sponding operations with the developed geodesic tools in the 23¹
Feature initialization. We first map the features from Euclidean space to pseudo-hypeeboloid, considering that the input features of nodes usually live in Euclidean space. Following the feature transformation from Euclidean space to pseudo-hyyerboloid in [24]. we initialize the node features by performing a differentiable mapping yp
IR4+1 x IR + 2/3 that can be implemented by a i.e. vp 1b-1 toooo th The intuition is that we first map Sy x R via v-(). and then map them into the 2 via (.), where the mapping functions are given by Eq.
double projection the Euclidean features into diffeomorphic manifolds
24 based on Theorem 2
(VIST
V
y 1+++
(xx)
& (2)
VIa v
u
(5)
where (t,s)) E Og with t E IR and E IR. z= vu, R
E R with E St and
Tangential aggregation. The linear combination of neighborhood features is lifted to the tangent space, which is an intrinsic operation in differential manifolds [2 [6] Specifically, Q-GCN aggre- gates neighbours' embeddings in the tangent space of the reference point o before passing through tangential activation function, and then projects the updated representation back to the manifold. Formally, at each layer f, the updated features of each node are defined as Eq. 66)
(0(
h
exPo
Be+1
(o(
Σ
logo
-e Be (w"
Or h
St b¹)
(EN(
where o-)) is the activation function, 3e and Be+1 are two layer-wise curvatures, M(i) denotes the one-hop neighborhoods of node i, and the &, + denote two basic operations, i.e. tangential transformation and bias translation, respectively.
Tangential transformation. We perform Euclidean transformations on the tangent space by lever- aging the expmap and logmap in Eq. M. Specifically, we first project the hidden feature into the tangent space of south pole o = [|3, 0, ..., 0] using logmap and then perform Euclidean matrix multiplication. Afterwards, the transformed features are mapped back to the manifold using expmap.
$ Formally, each layer f, the tangential transformation is given by & expo (W' logo (h')), where @ denotes the heuudo-yyeerboood tangential multiplication, and W 12 xd denotes the layer-wise learnable matrix in Euclidean space.
Bias translation. It is noteworthy that simply stacking multiple layers of the tangential trans- formation would collapse the composition [32 115,, i.c. exp....(W'' log (exp) (W*0 log (x))) e W1 ... x log((x)) which means that these multiplications can simply be per- formed in Euclidean space except the first logmap and last expmap. To avoid model collapsing we perform bias translation after the tangential transformation. By the means of pseudo-hyperboloid parallel transpori, the bias translation can be performed by parallel transporting a tangent vector b' E To to the tangent space of the point of interest. Finally, the transported tangent vector is mapped back to the manifold with expmap. Considering that exp(-) is only defined at point E Q3 with the space dimension x, O, we perform the original exp (-) at the point of interest. The bias translation is formally given by:
expy (p" Po-pnr (b)),
(o, K(), < [8] if (f k)) 2
h T
b'
expx he (pa (po-- (b)-)

---

where h' = W @0 @ denotes the
addition. For the broken cases where is not defined. In this case, parallel transport be to the
(o, h/)/ 2 |3), the parallel transport p a-
tangent space of the antipodal point - h", and then perform exp to map it back to the manifold.
Note that the case (o.h") h²), = [3] occurs if and only if h = -o, in which case pd o (b²) =
Po. (b') = -.b.
3.3 Model training
Having introduced all the building blocks, Q-GCN stacks multiple iseudo-Riemanen GCN layers and the final embeddings at the last layer can then be used to perform downstream tasks. For graph reconstruction, the objective is to map all nodes into a low- low-dimensional space such that the con- nected nodes are closer than unconnected nodes. Following 2
we minimize the loss function
((O)= = (uuije log
Ewercce e d(u."') under the set of connected relations 'D in the graph, where
E()) = v) & D. # u is the set of negative examples for node u, d(.) is the distance function defined in Eq. 44) For node classification, we map the output of the last layer of Q-GCN to the tangent space, and then perform Fuclidean multinomial logistic regression. For link predic- tion, we utilize the Fermi-Dirac decoder g compute probability scores for edges, formally given by P(eae E E)0) =(=(ax)))P)/44.T1 where and t are hyperparameters, d(u, v) is the distance function in the embedding space. We then train Q-GCN by minimizing the cross-entropy loss using negative sampling.
Optimization. Although the model is built in Oz the trainable parameters are all defined in Eu- clidean space through the diffeomorphic mappings. Following the standard tangential optimization strategy [2), the parameters can be optimized via Euclidean optimization by applying layer-wise diffeomorphic expmap and logmap. One optional strategy is to use dedicated optimization like [24]. which we left for our future work.
Complexity analysis. The time complexity is the same as a vanilla GCN given by O(IV dd +|E(d"), where V| and [E] are the number of nodes and edges, and d' are the dimension of input and hidden features. The computation can be parallelized across all nodes. Similar to other non- -uclldeid GCNs the mapping from manifolds to the tangent space consume additional computation resources, compared with Euclidean GCNs, which is within the acceptable limits.
32
3
17
4
Experiments
We evaluate the effectiveness of Q-GCN on graph reconstruction, node classification and link pre- diction. Firstly, we study the geometric properties of the used datasets including the graph sectional curvature [20 and the 5-hyperbolicity 7. Fig. in the Appendix shows the histograms of sectional curvature and the mean sectional curvature for all datasets. It can be seen that all datasets have both positive and negative sectional curvatures, showeasing that graphs contain mixed graph topologies. To further analyze the degree of the hierarchy, we apply d-hyperbolicity to identify the tree-likeness, as shown in Table g in the Appendix. We conjecture that the datasets with pos- itive graph sectional curvature or larger 9-hyperbolicity should be suitable for with a smaller time dimension, while datasets with negative graph sectional curvature or smaller 5-hyperbolicity should be aligned well with reeudo-hyperboloid with larger time dimension.
4.1 Graph reconstruction
Datasets and baselines. We benchmark graph reconstruction four real-world graphs including
1) Web-Edu Bii a web network consisting of the .edu domain; 2) Power [55 a power grid dis-
tribution network with backbone structure; 3) fho-Worm [6) worms gene network; 4) Facebook
37]: a dense social network from Facebook. We compare our method with Euclidean GCN [2] hy- perbolic GCN (HGCN)
32 spherical GCN, and product manifold GCNs (s-GCN) (3 with three
signatures (i.e. H x H H x S and 5 x So) Besides, five variants of our model are implemented
with different time dimension in [1, 3, 5, 7, 10] for comparison.
7

---

Table 2: ROC AUC (%) for Link Prediction (LP) and F1 score for Node Classification (NC).
Dataset
Airport 1.0
Pubmed 3.5
CiteSeer 4.5
Cor 11.0
6-hyperbolicity
Method
LP
NC
LP
NC
LP
NC
LP
NC
GCN
89.24=0.21
81.54+0.60
91.31=1.68
19,30=0.00
85,48=1.75
72.27+0.64
88. 88.52=0.85
81,90=0.41
GAT
90,35=0.8 30
81.5540.533
87 87.45+0.00
78. 3.00000000
87.2440.00
71.1040.00
85.73=0.01
83.0540.08
SAGE
89,86=0.52
82.79=0.17
90.70=0.07
30=300009
90.71=0.20
69,20+0.U0
87,52=0.22
74.90=0.07
SGC
89.80=0.34 34
80.6910.23
90.5440.07
78. 60=0.00
89.6140.23
71.6040.03
89.42s0.11
81,6020.43
HGCN (EI")
96.0320.26
90,57400.36
96.0820.21
80.50a1.25
96.31..0.1
68 63.9010..3
91.6220.33
79.90 I8
x-GCN (E11)
96.35=0.62
87.92:1.33
96.60+0.32
37.962
95.34=0.16
73.25+0.51
94.0420.34
79 00000
K-GCN (8
00.38+0.32
81 94+0.58
94, 04.8440.13
78 80=0.49
95.79+6024
72.13+0.51
93.20=0048
81,08+ 1.5
6: GCN (HI* 8*)
93.10:0.49
81, 81.93+0.45
94.8940.11 19
79. 79.20
93,4440.31
73.0540.59
92.22a0.48
79.30
Q-GCN (2
96.30=0:22
89,72=0.52
95 422222
80.50=0.26
94. 94.76+1.49
70.67
93. 03.1420.30
80,37=0.20
Q.GCN (Q)42)
94.37=0.44
84,40+0.35
96.86+0.31
81 1,55
94.78+0.11
73.43+00.5
90.41=0.57
81.62+0.21
Q-GCN (Quaa)
92.5340.17
82.38&1153
96.2040.34
80.9420.45
94.5440.16
74.1341.41
93.5620.18
79,9140.42
(Q
90.03=0.12
81.14+1.12
94.30=1.09
40:0.39
94.80100.08
72.22:0:47
94.1720.38
83.10.0.35 90,81
Q-GCN (QI-13)
89.07=0.58
81 31.24+0.34
94.66+0. 18
78. 18.11+1.35 38
97.01=0.30
73.19=1.55
83.72+0.43
QCGCN (Qh.1)
89.01=0.61
80.9140.65
94,4940.28
77.90=0.80
96.21:10.88
72.5440.27
95.16&1.25
82.51+0.32
Experimental settings. Following (20 [24] [33, we use one-hot embed- dings initial node features. To avoid the time dimensions being O, we uni- formly perturb each dimension with a small random value in the interval [-,, where e 0.02 in practice. In addition, the same 10-dimensional embedding and hidden layers are used for all baselines to ensure fair comparison. The learning rate is set 0.01, the learning rate of curvature is set to 0.0001. Q-GCN is implemented with the Adam optimizer. We repeat the experiments 10 times via different random seeds influencing weight initialization and data batching.
Table I: The graph reconstruction results in mAP (%), top three results are highlighted. Standard deviations rela- tively small (in range (0, 1.2 x 10 ?D and are omitted.
Model
Web-Edu
Power
Bio-Worm
Facebook
Curvature
-0.6
-0.3
0.0
0.1
GCN (B!
83.66
86.61
90.19
81.73
HGCN (HH10)
88.33
93.80
93.12
83.40
GCN (810)
82.72
92.73
88.98
81.04
k- x-GCN (HH H²)
89.21
94.40
94.00
84,94
x-GCN (85 )
86.70
94.58
90.36
84.56
K-GCN (HI x 8²)
87.96
95.82
94.74
87.73
Q-GCN (Q".)
87.03
94.35
92.83
81.60
Q-GCN (QT.3)
99.67
100.00
97.23
87.74
Q-GCN (Q%))
98.49
100.00
95.75
87.03
Q-GCN (Qa.7)
97.31
95.08
90.14
91.75
Q-GCN (Q).1))
82.57
94,20
88.67
83.81
Results. Table the mean av- erage precision (mAP) 200 results of graph reconstruction on four datasets. It shows that Q-GCN achieves the best performance across all benchmarks compared with both Riemannian space and product manifolds. We observe that by setting proper signatures, the product spaces perform bet- ter than a single geometry. It is consistent with our statement that the expression power of a single view geometry is limited. Specifically, all the top three results are achieved by Q-GCN, with one exception on Power where HD x S achieved the third-best performance. More precisely, for datasets that have smaller graph sectional curvature like Web-Edu, Power and Bio-Worm. Q7.3 perform the best, while Q3.7 perform the best Facebook with positive sectional curvature. We conjecture that the number of time dimensions controls the geometry of the pseudo-hypen hyperoolddprb....... We find that the graphs with more hierarchical structures are inclined to be embedded with fewer time dimensions. By analyzing the sectional curvature in Fig. 4 we find that this makes sense as the mean sectional curvature of Power, Bio- Wormnet and Web-Edu Edu negative while it is negative for Facebook. Such results give us an intuition to determine the best time dimension based on the geometric properties of graphs.
4.2 Node elassification and link prediction
Datasets and baselines. We consider four benchmark datasets: Airport, Pubmed, Citeseer and Cora, where Airport is airline networks, Pubmed, Citeseer and Cora are three citation networks. We observe that the graph sectional curvatures of the four datasets are consistently negative without significant differences in Fig. hence we report the additional š-hyperbolicity for comparison in Table 2 GCN 2, GAT 3. SAGE [& and SGC are used as Euclidean GCN counterparts. For non-Euclidean GCN basclines, we compare HGCN
32 and K- KCGCN B with its three variants as
8

---

Table 3: F1 score for node classification of MLP, HNN Table 4: The running time (sec) of graph and Q-NN on Pubmed, Citeseer and Cora.
construction on Web-Edu and Facebook.
Method
Pubmed
CiteSeer
Cora
Manifolds
Web-Edu
Facebook
MLP
72.30=0.30
60.22+0.42
$5.8040.88
GCN (E.
2284
$456
HNN
74.60=0.40
59.9240.87
59.60=0.09
Prod-GCN (IH x S*)
4336
10338
Q-NN (Q1s.1)
74.31=0.33
59.33+0.35
60.38:0.56
Q-GCN (Q%1)
2769
6981
N-NN (Q14.2)
76.26#0.31
64.33+0.35
62.77+0.30
Q-GCN (Q?:3)
3363
6303
N- (Q
75.85+0.79
63.65+0.57
59.04
Q-GCN (Q%.9)
3620
7142
O-NN (4
74,4420.68
60.48+0.29
63. 63.85+0.22
Q-GCN (Q*.7)
3685
7512
O-NN (QI.15)
73.44=0.28
60.33+0.40
64.85+0.24
Q-GCN (Q119)
3532
7980
O-NN (Q".1))
73.31=0.17
61.05+0.22
63.9640.41
Q-GCN (Q"11)
2778
7037
explained before. For Q-GCN, we empirically set the time dimension as [1, 3, 14, 15, 16 as six variants since these settings best reflect the geometric properties of hyperbolic and spherical space, respectively.
Experimental settings. For node classification, we use the same dataset split as [39 for citation datasets, where 20 nodes per class are used for training. and 500 nodes are used for validation and 1000 nodes are used for testing. For Airport, we split the dataset into 70/15/ 15. For link prediction, the edges are split into 85/5/ 7/110 10 percent for training, validation and testing for all datasets. To ensure a fair comparison, we set the same 16-dimension hidden embedding, 0.01 initial learning rate and 0.0001 learning rate for curvature. The optimal regularization with weight decay, dropout rate, the number of layers and activation functions are obtained by grid search for each method. We report the mean accuracy over 10 random seeds influencing weight initialization and batching sequence.
Results. Table shows the averaged ROC AUC for link prediction, and F1 score for node classifi- cation. As we can see from the t-hyerbboicctty. Airport and Pubmed are more hierarchical than Cite- Seer and Cora. For Airport and Pubmed with dominating hierarchical properties (lower 5), Q-GCNs with fewer time dimensions achieve the results on par with hyperbolic space based methods such as HGCN 32) x-GCN (HHT While for CiteSeer and Cora with less tree-like properties (higher 6), Q-GCNs achieve the state-of-the-arr results, showcasing the flexibility of our model embed complex graphs with different curvatures. More specifically, Q-GCN with more time dimensions consistently performs best on Cora. While for CiteSeer, albeit Q-GCN achieves the best results, the corresponding best variants are not consistent both tasks.
4.3 Parameter sensitivity and analysis
Time dimension. We study the influence of time dimension for graph reconstruction by setting vary- ing number of time dimensions under the condition of 8 / 10. Fig. 2 shows that the time dimension I acts knob for controlling the geometric prop- erties of 2% The best performance are achieved by neither hyperboloid (t 1) nor sphere cases (t = 10), showcasing the advantages of Q3 rep- resenting graphs of mixed topologies. It shows that on Web-Edu, Power and Bio-Worm with smaller mean sectional curvature, after the optimal value is reached a lower I, the performance decrease as increases. While on Facebook with larger (positive) mean sectional curvature, as t rises, the effect grad- ually increases until it reaches a peak at higher t. is consistent with our hypothesis that graphs with more hierarchical structure are inclined to be embedded in 2 with smaller t, while cyclical data aligned well with larger The results give us intuition to determine the best time dimension based on the geometric properties of graphs.
The mAP MAP ranking score
100
95
90
Power
Bio- Worm
85
Web-Edu
Facebook
80
2
3
5
6
9 10
Time dimension (t)
Figure The mAP of graph reconstruction with varying number of time dimensions.

---

(a) Spherical projection
(b) Hyperbolic projection (3D)
(c) Hyperbolic projection (disk)
Visualization of the learned embeddings for link prediction on Pubmed (left) and Cora (right), where the colors denote the class of nodes. We apply (a) spherical projection, (b) hyperbolic
Figure 3:
projection (3D) and (c) hyperbolic projection (Poincaré disk) on the learned embeddings of Q-GCN visualize various views of the learned embeddings.
Q-NN VS Q-GCN. We also introduce Q-NN, a generalization of MLP into pseudo-Riemannian manifold, defined as multiple layers of fxx = の (W @ x Φ b). where σ is the tangential activation. Table 3 shows that Q-NN with appropriate time dimension outperforms MLP and HNN on node classification, showcasing the expression power of pseedo- hyperboooy........... Furthermore, com- pared with the results of Q-GCN in Table 2 Q-GCN performs better than Q-NN, suggesting that the benefits of the neighborhood aggregation equipped with the proposed GCN operations.
Computation efficiency. We compare the running time of Q-GCN, GCN and Prod-GCN per epoch. Table 4 shows that Q-GCN achieves higher efficiency than Prod-GCN (H x $9). This is mainly owing to that the component TR our diffeomorphie manifold (S x R) runs faster than non-Fuclidean components in H S The additional running time mainly comes from the mapping operations and the projection from the time dimensions to S. The running time grows when increasing the number of time dimensions. Overall, albeit slower than Euclidean GCN, the running time of all variants of Q-GCN is smaller than the twice of time in Euclidean GCN, which is within the acceptable limits.
Visualization. To visualize the embeddings learned by Q-GCN, we use UMAP tool I to project the learned embeddings for Link Prediction on Pubmed and Cora into oow-dimensional spherical and hyperbolic spaces. The projections include spherical projection into 3D sphere, hyperbolic projec- tion into 3D plane, and 2D Poincaré disk. As shown in Fig- 3 (a.b), for Pubmed with more hyperbolic structures, the class separability is more significant in hyperbolic projection than that is in spherical projection. While the corresponding result is opposite for less tree-like Cora. Furthermore, Fig. B provides a more clear insight of the hierarchy. It shows that there are more hub nodes near the origin of Poincaré disk Pubmed than in Cora, showcasing the dominating tree-likeness of Pubmed.
Conclusion
In this paper, we generalize GCNs to pseudo-Riemannian manifolds of constant nonzero curvature with elegant theories diffeomorphic geometry tools. The proposed Q-GCN have the flexibility to fit complex graphs with mixed curvatures and have shown promising results on graph reconstruction. node classification and link prediction. One limitation might be the choice of time dimension, we provide some insights to decide the best time dimension but this could still be improved, which we left for our future work. The developed geodesic tools are application-agnot extended to more deep learning methods. We foresee our work would shed light on the direction of non-Fuclldean geometric deep learning.
and could be
Acknowledgments
The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS- IS) for supporting Bo Xiong. Bo Xiong was funded by the European Union's 's Horizon 2020 research and innovation programme under the Marie Sktodowska-Curf grant agreement No: 860801. Nico Potyka was partially funded by DFG projects Evowipe/COFFEE. Shirui Pan was supported in part by ARC Future Fellowship (FT210100097). This work was funded by Deutsche Forschungs- gemeinschaft (DFG, German Research Foundation) under Germanys' Excellence Strategy-EXC 2075-390740016 (Sim'Tech).
10

---

References
[1] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. Yoshua Bengio and Yann LeCun, editors, 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[2] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[3] Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, In 6th International Conference on Learning Rep- resentations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[4] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q- Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learn- ing. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6861-6871. PMLR 2019.
[5] Ke Sun, Jun Wang, Alexandros Kalousis, and Stéphane Marchand-Maillet. Space-time lo- cal embeddings. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 100-108, 2015.
[6] Marián Boguñá, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, and M Ángeles Serrano. Network geometry. Nature Reviews Physics, pages 1-22, 2021.
[7] Mikhael Gromov. Hyperbolic groups. Essays in group theory, pages 75-263. Springer, 1987.
[8] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Bo- guná. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010.
[9] Bo Xiong, Michael Cochez, Mojtaba Nayyeri. and Steffen Staab. Hyperbolic embedding ference for structured multi-label prediction. Advances in Neural Information Processing Sys- tems, 2022.
[10] Menglin Yang, Zhihao Li, Min Zhou, Jiahong Liu, and Irwin King. Hicf: Hyperbolic in- formative collaborative filtering. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2212-2221, 2022.
[11] Menglin Yang, Min Zhou, Jiahong Liu, Defu Lian, and Irwin King. Href: Enhancing col- laborative filtering via hyperbolic geometric regularization. In Proceedings of the ACM Web Conference 2022, pages 2462-24222222 2471, 2022.
[12] Richard Wilson, Edwin Hancock, Elžbieta Pekalska, and Robert PW Duin. Spherical and hyperbolic embeddings of data. IEEE transactions pattern analysis and machine intelli- gence, 36(1 1):2255 2014.
[13] Yu Meng, Jiaxin Huang, Guangyuan Wang, Chao Zhang, Honglei Zhuang, Lance M. Kaplan, and Jiawei Han. Spherical text embedding. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence A'Alché- Emily B. Fox, and Roman Garnett. editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2206-8215, 2019.
[14] Michaël Defferrard, Nathanaël Perraudin, Tomasz Kacprzak, and Raphael Sgier. Deepsphere: towards an equivariant graph-based spherical cnn. ICLR 2019 Workshop on Representation Learning Graphs and Manifolds, 2019.
[15] Octavian-Fugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Advances in neural information processing systems, pages 5350-5360, 2018.
11

---

[16] Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buch Emily B. Fox, and Ro- man Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Confer- ence on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages
2019.
[17] Shichao Zhu, Shirui Pan, Chuan Zhou, Jia Wu, Yanan Cao, and Bin Wang. Graph geometry interaction learning. In Advances in Neural Information Processing Systems, 2020.
[18] Yiding Zhang, Xiao Wang, Chuan Shi, Nian Liu, and Guojie Song. Lorentzian graph convolu- tional networks. In International World Wide Web Conference Committee, 2021.
[19] Jindou Dai, Yuwei Wu, Zhi Gao, and Yunde Jia. tional network. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 154-163, 2021.
peperbolii-to-yyerrboll graph convolu-
[20] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature repre- sentations in product spaces. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[21] Ondrej Skopek, Setavian-Eugert Ganea, and Gary Bécigneul. Mixed-curvature variational autoencoders. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[22] Julian Laub and Klaus-Roberr Müller. Feature discovery in non-metric pairwise data. The Journal of Machine Learning Research, 5:801-818, 2004.
[23] James Clough and Tim Evans. Embedding graphs in lorentzian spacetime. PloS one, 12(1 (2(11):c117330 2017.
[24] Mare T. Law and Jos Stam. Ultrahyperbolic representation learning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Informa- tion Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[25] Aaron Sim, Maciej Wiatrak, Angus Brayne, Páidí Creed, and Saee Paliwal. Directed graph embeddings in pseudo-riemannian manifolds. Thirty-eighth International Conference on Ma- chine Learning, 2021.
[26] Bo Xiong, Shichao Zhu, Mojtaba Nayyeri, Chengjin Xu, Shirui Pan, Chuan Zhou, and Steffen Staab. Ultrahyperoolic knowledge graph embeddings. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
[27] Barrett O' neill. remi-riemannian geometry with applications to relativity. Academic pres, 103, 1983.
[28] Thomas James Willmore. An introduction to differential geometry. Courier Corporation, 2013.
[29] Daniel Spiegel. The hopf-rinow theorem. Notes available online, 2016.
[30] Fabio Giannoni, Paolo Piccione, and Rosella Sampalmieri. On the geodesical connectedness for class of semi-riemannian manifolds. Journal of mathematical analysis and applications, 252(():444 2000.
[31] Tingran Gao, Hen-Heng Lim, and Ke Ye. Semi-riemannian manifold optimization. CORR, 2018.
[32] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolu- tional neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Alhéé-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages
2019.
[33] Gregor Bachmann, Gary Bécigneul, and Octavian Ganea. Constant curvature graph convolu- tional networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 486-496. PMLR, 2020.
[34] David Gleich, Leonid Zhukov, and Pavel Berkhin. Fast parallel pagerank: A linear system approach. Yahoo! Research Technical Report YRI-2004-038, available via hup:/fresearch. yahoo. http:ppbbiccatooo//--0000000000 pdf. 13:22, 2004.
12

---

[35] Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world woallllooooonndorrssss. networks. nature, 393(66844:444-4445 1998.
[36] Ara Cho, Junha Shin, Sohyun Hwang, Chanyoung Kim. Hongseok Shim, Hyojin Kim, Han- hae Kim. and Insuk Lee. Wormnet v3: network-assister hypothesis- caenorhabditis elegans. Nucleic acids research, 42(W 1):W7--W82, 2014.
server for [37] Julian J. McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kil- ian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th An- nual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages
2012.
[38] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034, 2017.
[39] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learn- ing with graph embeddings. In Maria-Florina Balcan and Kilian Q. Weinberger. editors. Pro- ceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 40-48. JMLR.org. 2016
[40] Maximilian Nickel and Douwe Kicla. Poincaré embeddings for learning hierarchical repre- sentations. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 6338 6347, 2017.
[41] Bhuwan Dhingra, Christopher Shallue, Mohammad Norouzi, Andrew Dai, and George Dahl. Embedding text in hyperbolic spaces. In Proceedings of the Twelfth Workshop on Graph- Based Methods for Natural Language Processing (TextGraphs-12) pages 59-69, New Or- leans, Louisiana, USA, 2018. Association for Computational Linguistics.
[42] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Multi-relational poincaré graph embeddings. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox. and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 4465-4475. 2019.
[43] Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan K. Reddy. Self-supervised hyperboloid representations from logical queries over knowledge graphs. In WWW, pages 1373-1384. ACM / IW3C2, 2021.
[44] Tim R. Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M. Tomezak. Hy- perspherical variational auto-encoders. In Amir Globerson and Ricardo Silva, editors, Pro- ceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pages 856-865, AUAI Press, 2018
[45] Jiacheng Xu and Greg Durrett. Spherical latent spaces for stable variational autoencoders. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4503-4513, Brussels, Belgium, 2018. Association for Computational Linguisties.
[46] Zhen Han, Peng Chen, Yumpu Ma, and Volker Tresp. DyERNIE: Dynamic Evolution of Rie- mannian Manifold Embeddings for Temporal Knowledge Graph Completion. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7301-7316, Online, 2020. Association for Computational Linguistics.
[47] Mare Law. Ultrahyperbolic neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[48] H Anciaux. Minimal submanifolds in rieudo-riemannian geometry. World Scientific, 2011.
[49] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference
13

---

on Machine Learning, ICML 2018, Stockholmsmüssan Stockholm, Sweden, July 10-15. 2018, volume 80 of Proceedings of Machine Learning Research, pages 5449-5458. PMLR, 2018.
[50] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1725-1735. PMLR, 2020.
[51] Yulong Pei, Tianjin Huang, Werner van lpenburg, and Mykola Pechenizkiy. Resgen: Attention- based deep residual modeling for anomaly detection on attributed networks. CoRR, 2020.
14


Reviews:
[{"review_id": "lKBh4F5I1aK", "reviewer": "Reviewer_Pmuy", "summary": "This paper proposes a non-Euclidean GCN based on pseudo-Riemannian geometry. The major idea is to generalise GCN operations including feature transformation and neighbourhood aggregation into pseudo-Riemannian manifolds. Different from Riemannian manifolds such as sphere and hyperboloid, the main challenge is the broken geodesic issue (i.e., there exists broken geodesic for which standard operations are not well defined). The authors propose to use “diffeomorphism operations” to define basic operations like linear transformation and aggregation. Experiment results on three graph learning benchmarks show significant improvements. ", "questions": "1.Is it possible to directly perform aggregation in the pseudo-hyperboloid, like using  Frechet mean to simplify the aggregations as done by Y. Zhang, et al. 2021.?\n2.The authors use tangent space optimization. Is there any guarantee for doing so? \n\n[1] Y. Zhang, et al. Lorentzian Graph Convolutional Networks. 2021.", "limitations": "Yes, the authors have highlighted the limitations of their work in the Broder Impact section", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1.The authors extended GCN into pseudo-Riemannian manifolds (more specifically, pseudo-hyperboloid) with non-positive definite metric. The motivation is inspired by Marc T. Law, et al. 2020. However, different from Marc T. Law, et al. 2020, the authors propose to generalize the neural network operations into the pseudo-hyperbolic space.\n2. The proposed operations and tools seem technical solid. The main non-trivial part is that there exists broken geodesic for which standard manifold operations like expmap and logmap cannot be defined.  The authors propose to map the operations into diffeomorphic manifolds that are easy to operate. The proposed tools might be useful for generalizing other neural models to pseudo-hyperboloid like generative models.\n3.Evaluation results on three graph learning tasks are strong enough to show the benefits of the proposed method on embedding graphs, especially when the graphs have mixed curvature.\nWeaknesses\nThere are a few minor issues that could be fixed during the rebuttal \n1. The authors should give enough details of the baselines and explain why choosing them\n2. For a given dataset, how to decide the proper settings of time dimension and why choosing those time dimensions (2,4,8,…) in the evaluation is not clear enough\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dBOvgbuzEz", "reviewer": "Reviewer_qApk", "summary": "The authors extend existing Graph Convolutional Networks (GCNs) on non-Euclidean Riemannian manifolds to a larger class of pseudo-Riemannian manifolds which generalizes hyperboloid and sphere. They extend neural network operations into geodesically disconnected pseudo-Riemann manifolds by developing some new geodesic tools, and derive a pseudo-Riemannian GCN (Q-GCN) which models data in pseudo-Riemannian manifolds of constant nonzero curvature. This method provides a geometric inductive bias that captures heterogeneous topologies. The representational capabilities are examined through experiments on graph reconstruction, node classification and link prediction tasks. The empirical results show that the proposed method outperforms Euclidean GCNs and non-Euclidean GCN counterparts with an acceptable increase in time complexity.", "questions": "Please refer to the weakness above.", "limitations": "The authors have adequately addressed the limitations of the proposed method, such as higher computational costs, and the results on graphs with dominating hierarchical properties.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The work is original: there has not been any existing works about GCNs on pseudo-Riemannian manifolds. \n- The presentation of the paper is clear. \n- The paper includes adequate theoretical derivations on how the geodesic tools are developed, and empirical results to support that the proposed Q-GCN accommodates topologically heterogeneous graphs well, and outperforms other existing methods, either with Euclidean GCNs or non-Euclidean GCNs, on most of the datasets.\n\nWeaknesses:\n- It would be better to include some visualizations either for illustrating the theoretical part or presenting the experimental results.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V-hcYSIes1f", "reviewer": "Reviewer_vzK2", "summary": "To unify the successes of hyperbolic graph convolutional networks (GCN) in modeling hierarchical structures and spherical manifolds in modeling cycles,\nthe authors generate a diffeomorphism $\\psi$ from pseudo-hyperboloids ( $Q_\\beta^{(s,t)}$ with $t+1$ time dimensions and $s$ spatial dimensions) into product manifolds of a sphere and Euclidean space. The special form of this diffeomorphism allows them to formulate expMap, logMap, parallel transport operations and geodesics to avoid broken cases (using antipodal points). The resulting Q-GCNs have learnable layer-wise parameters in Euclidean space and can be used for both graph reconstruction (GR) and link prediction (LP) / node classification (NC) tasks. Q-GCNs outperform competitors such as $\\kappa$-GCN's and HGCN's on these tasks on a majority of the datasets (Tables 1 and 2). The authors also conduct a thorough parameter sensitivity analysis and computation time analysis (Tables 5 and 4).\n", "questions": "The authors mention at the end of the Optimization section that dedicated optimization like [21] would be considered in future work.\nWhat advantage would dedicated optimization provide ?\n\nPlease note the questions inherent in Weaknesses 1 and 2 above.\n", "limitations": "\nThe authors mention that improvements might be necessary for automatically choosing time dimensions of Q-GCNs in Sec. 5\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. As summarized above, the approach is motivated quite well both from an intuitive and from a theoretical viewpoint.\n2. Q-GCNs outperform competitors such as $\\kappa$-GCN's and HGCN's on GR or LP/NC tasks on a majority of the datasets (Tables 1 and 2)\n3. The authors also conduct a thorough parameter sensitivity analysis and computation time analysis (Tables 5 and 4).\n4. Q-NNs, another variant introduced using the authors' theoretical analysis, outperforms MLPs on NC tasks in Table 3.\n\nWeaknesses\n\n1. Some of the theorems reported by the authors are quite technical and require significant background on pseudo-Riemannian manifolds. But it is not clear how novel these results would be considered in those fields. For instance, is the proof for theorem 2 is significantly novel w.r.t. the proof of theorem 1 in [21] ? It is also not clear why the discontinuous operation in (4) doesn't sacrifice the diffeomorphic property. It's possible parallel transport doesn't require the continuity property, but this isn't explicitly pointed out.\n\n2. The authors do not provide pseudo-code for their training and inference algorithms either in the main body of the paper or in the Appendix.\nSo it is not entirely obvious to a reader when exactly the antipodal operation described after Theorem 4 or in the bias translation subsection of Sec. 3.2 is applied, although this can be inferred from (6).\n\n3. Error bars are reported in tables 2 and 3, but not in table 1.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Okk7GWHuvvA", "reviewer": "Reviewer_zhRd", "summary": "The authors extended the graph convolutional networks to the graph representation into pseudo Riemannian geometry. Pseudo-Riemannian geometry was introduced as a possible embedding space for hierarchical graphs and graphs with cycles. As the space is equipped with metric, geodesic, exp and log map, the authors extend the graph convolutional neural network model to such framework. The model performance is showcased on both graph reconstruction data, link prediction and node classification.", "questions": "Introduction: For a reader without a strong knowledge on graph embedding, it is not very clear the motivation of the work. Why such complex embedding is required for graph embedding? Authors should help the reader understanding the literature gap they are trying to fill, maybe adding a simple example in a sentence.\n14 what does it means graphs with different curvature? The curvature of the embedding space? In geometry, the curvature is a property of the metric. This sentence is not so clear as the reader might be more familiar with the metric curvature rather than the graph curvature. Notice that this is an important point to be clarified throughout the paper.\n29-30 I don’t understand why the authors cite these examples. Is the spherical embedding another embedding for graphs? If so should be better explained as it is the only other example of non-Euclidean data type for which Neural Networks have been extended.\n\nSection 3 The theory described in Section 3 strongly relies on [21]. I think the novelty should be better enlighten and justified. Is the Theorem 2 needed to extend the GNN? Why?\n\nSubsection 3.2: Tangential Transformation. I don’t understand a tangential approximation in a point should be a good approximation of the data. Especially in the example with positive curved spaces, the tangent space centered in a point could be a bad approximation of your data if there is no ensurance of data concentration. A better justification should be provided.\n\nExperiments: How do the authors justify a 100% mean Average Precision in Table 1?\n", "limitations": "The paper is complex and extend the GNN to a pseudo-Riemannian embedding of Graphs. As the geometrical embedding is fully described by [21], the paper should be better framed to justify which geometrical tools are necessary to extend GNN and why this complex framework is needed compared to more intuitive GNN on the Euclidean embedding or Hyperbolic embedding of graphs.", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors focus on an important topic which is the extension of the neural network models to a geometrical framework beyond the Euclidean space or any other Smooth Manifold. Geometrical setting is well introduced and the geometrical tools are well described. They showcase the model in three important tasks related to graph analysis.\nThe main strengths are: (1) the attention to a careful geometrical embedding of the data (2) a well-structured paper (3) complete experiments.\nThe main weakness is lack of novelty compare to [21] and the complexity of the framework, which it is not well justified throughout the paper. \n\nThe authors are extending the GNN to the pseudo-Riemannian setting, but the geometrical tools seem to be the one already introduced in [21].  If the main difference is the spherical mapping described in Th. 2, I don't understand why a map preserving the curvature should be preferable to a map with the same properties but with a flat curvature image (which is easier to handle). \nIn Section 4, the authors describe how to extend the GNN to the framework by mapping node features (in the Euclidean setting) to the described embedding and then mapping them again into the tangent space (which is flat by definition). Is it a geometrical virtuosism or a necessity? In addition, there is a tangent space approximation centered in the south pole described in section 3.2. The tangent space approximation is a bad approximation of positively curved spaces if there is no ensurance about how the data are concentrated. This step is vague and unclear to me.\nLastly, there should be a stronger justification to the introduction of such complex (and parametric -see time dependence) setting. As there are many different embedding graphs procedure, which are the strenghts of such embedding? This should be better enlightened in both the introduction and the experiments, as not all the reader might be familiar with such embedding.\n\n[21] Law and Stam (2020) Ultra hyperbolic Representation Learning.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept