Spacetime Representation Learning
Authors: Marc T. Law
James Lucas
Venue: ICLR 2023 poster (2023)
Keywords: pseudo-Riemannian geometry
spacetimes
Lorentz geometry
Lorentzian causality theory
Lorentzian pre-length spaces
directed graphs

Abstract: Much of the data we encounter in the real world can be represented as directed graphs. In this work, we introduce a general family of representations for directed graphs through connected time-oriented Lorentz manifolds, called "spacetimes" in general relativity. Spacetimes intrinsically contain a causal structure that indicates whether or not there exists a causal or even chronological order between points of the manifold, called events. This chronological order allows us to naturally represent directed edges via imposing the correct ordering when the nodes are embedded as events in the spacetime. Previous work in machine learning only considers embeddings lying on the simplest Lorentz manifold or does not exploit the connection between Lorentzian pre-length spaces and directed graphs. We introduce a well-defined approach to map data onto a general family of spacetimes.  We empirically evaluate our framework in the tasks of hierarchy extraction of undirected graphs, directed link prediction and representation of directed graphs.

Published as a conference paper at ICLR 2023
SPACETIME REPRESENTATION LEARNING
Mare T. Law & James Lucas
NVIDIA
ABSTRACT
Much of the data we encounter in the real world can be represented as directed graphs. In this work, we introduce general family of representations for directed graphs through connected time-oriented Lorentz manifolds, called "spacetimes" in general relativity. Spacetimes intrinsically contain causal structure that indicates whether or not there exists a causal or even chronological order between points of the manifold, called events. This chronological order allows us to naturally represent directed edges via imposing the correct ordering when the nodes are embedded as events in the spacetime. Previous work in machine learning only considers embeddings lying on the simplest Lorentz manifold or does not exploit the connection between Lorentzian pre-length spaces and directed graphs We introduce a well-defined approach to map data onto a general family of spacetimes. We empirically evaluate framework in the tasks of hierarchy extraction of undirected graphs, directed link prediction and representation of directed graphs.
INTRODUCTION
Most of the machine learning literature has focused learning representations that lie Ric- mannian manifold such as the Euclidean space, the d-sphere (e.g.. fz-normalized representations) (Wang et al., 2017| Taaassi et al. 2019). hyperbolic geometry to represent graphs without cycles (Nickel & Kiela 2017). or a statistical manifold in information geometry (Amari 1998). Concepts of Euclidean geometry, such as distances, are naturally generalized to Riemannian geometry which remains easy to interpret. In contrast, recent approaches have considered learning representations that lie on a -ieemannan manifold extract hierarchies in graphs with cycles (Law & Stam
2020
Law 2021) or represent directed graphs (Clough & Evans 2017 Sim et al. 2021).
manifolds are generalizations of Riemannian manifolds where the constraint of positive definiteness of the nondegenerate metric tensor is relaxed. The machine learning literature on greudo-Riemanen manifolds can be divided into two categories. The first category focuses on how to optimize given function whose domain is a pseudo-Riemannias manifold and does not take
into account whether the manifold is time-oriented or not (Law Stam 2020 Law 202T). The
second category exploits the interpretation of specific family of pseudo Riemannian manifolds called "spacetimes" in general relativity (Clough & Evans 2017 Sim et al. 2021). More specifically, spacetimes are connected time-oriented Lorentz manifolds. They intrinsically contain causal structure that indicates whether or not there exists a causal order between points of the manifold, called events. This causal structure has been utilized to represent directed graphs where each node is an event and the existence of an arc (i.c.. directed edge) between two nodes depends on the causal character of the curves joining them (Bombelli al. 1987). In particular, Clough & Evans (017) consider learning representations via the Minkowski spacetime which is the simplest such manifold. On the other hand, Sim et al. (202T) use three types of spacetimes and propose an ad hoc method based on the sign of some time coordinate difference function to determine the orientation of edges. The sign of such function not always meaningful as it for instance alternates periodically when the manifold is non-chronological and does not generalize to all spacetimes. Moreover, the distance function that they optimize is constant when two points cannot be joined by a geodesic.
Contributions, We propose framework inspired by Lorentzian causality theory (Kronheimer & Penrose 1967 Minguzzi 2019), and in particulaa Lorentzian pre-length spaces (Kunzinger & Sämann 2018), to learn directed graph representations lying large family of spacetimes. To this end, we present tools to account for time-orientation and exploit distances specific to Lorentz geometry. In particular, we propose to restrict the existence of edges pairs of nodes whose representations lie in

---

Published as a conference paper at ICLR 2023
Time-like geodesic
Space like geodesic
R
I2
Space-like geodesic
Time-like geodesic
Null geodesic
Null geodesic
(T(r)
HP
Figure 1: Geodesics of the de Sitter space (1() (left) and of the anti-de Sitter space (1) (right).
an open globally hyperbolic convex normal neighborhood. Such a neighborhood can be defined for any spacetime (see Theorem 2.7 Minguzzi (2019) and admits simple distance and time separation functions whose sign determines the direction of edges. We experimentally show that spacetimes can extract hierarchies in social networks better than standard approaches. Our framework also outperforms existing methods in link prediction on graphs with directed cycles.
2
SPACETIME DIFFERENTIAL GEOMETRY
We introduce some differential geometry background about spacetimes. Spacetimes have been widely studied, and we refer the reader to Hawking Ellis (173); [hlenbeck (1975) O Neill (995): Beem
et al. 1996);; Wolf (2011); Gourgoulhon (2016). Chapter 5-8 & 14 of O'Neil (1883).
Manifold. d-dimensional pseudo Rieemmnnn manifold (M,g) is smooth manifold such that every point x E .M has a d-dimensional tangent space T&M whose metric tensor Ix M x TxM - R is a nondegenerate symmetric bilinear form (called a scalar product). Nondegeneracy means that Vv E TxM,, 3bx (u, v) 0 = O. When the context is clear and to simplify the notation, we write (..-) == Ix (x(ss)) to define the metric tensor at x. We also write M instead of (M,g). We write points x E M of the manifold in bold serif font, and tangent vectors u E T&M in bold sans-serif font when we want to distinguish them from points.
Lorentz manifold. Every tangent space M of a d-dimensional neeudo-Riemannian manifold M admits an orthonormal basis (ei,..., ex} that satisfies Vi, (e,, e;) = +1 and A + j. (e; eÿ) = 0. The index < d of M is the number of vectors e; that satisfy (e., e,) Riemannian and its metric tensor is positive definite (i.e., Vx E M,, vu E T&M, (u, u) 2 0 and (u, u)
-1 If 0, M is
0). If 1, M is Lorentz manifold and T&M is Lorentz vector space.
Future timecone. A nonzero tangent vector is called timelike (or chronological), null, spacelike or non-spacelike (or causal) if (u, u) is negative, zero, positive or nonpositive, respectively. The type into which u falls is called its causal character. If u = 0, then is spacelike. Every Lorentz tangent space contains two timecones. Some timelike tangent vector E T&M can arbitrarily be used to define the future timecone as the following set: C+ (t) == (v E M (v, v) < 0, (t. v) < 0} whereas -t defines the past timecone Cx (t) == C-(-)) t). Two timelike tangent vectors u and v are in the same timecone iff (u, v) < 0. They belong to different timecones if uu
continuous vector field X function that assigns to each point x M tangent vector of M at x denoted by X (x) E M. X and -X are timelike if Vx E M, (X (x)) < O. A Lorentz manifold is time-orientable iff there exists a timelike vector field. If M is assigned such timelike vector field X, it is time-oriented by X. In this case, non-spacelike tangent vectors u at each point x can be divided into two separate classes: future- directed if (X (x), u) O. and past-directed if (X(x), u) O.
Time-orienaability and time-orientation.
curve Tx-u I + M where C R is defined such that its initial point is (0) = x and its initial velocity is (0) = E M.M. We denote by y when its initial conditions clear from
2

---

Published as a conference paper at ICLR 2023
the context. If its acceleration is zero, then it is called geodesic. The curve is called timelike, null or spacelike if its velocity on the whole domain I is timelike, null or spacelike, respectively. It is called future-directed (or future- poluurii if its velocity is future-directed (and causal) I.
Completeness. The manifolds that we consider in this paper are geodesically complete (i.e., R), and the exponential map expx M - M of M at x is defined as expx (u) -xx-ul (1) where
7x-u is a geodesic. The maximal normal neighborhood
x is the maximal subset Lx C M where
the logarithmic map logx :- expx* 1 Ux - M is diffeomorphism, it satisfies Ux =- {y E . (()) = y.. To simplify the notation, we also write xy := 1ogx(y where y E Ux. Ux is
expx (expx (y)) conver if vy Ux. there exists a unique geodesic totally contained Ux from x y.
We now present some pseudo- Riemmannannnn manifolds that will be relevant. Their differential geometry tools (e.g.. exponential/lgaritmmii map and parallel transport) are provided in Appendix
Eecuid-E space Rd The flat d-dimensional ascudo-Riemannien manifold of index is denoted by R. In particular, Rg is the Euclidean space and R is the Minkowski space (or Minkowski spacetime). Since it is vector space, we can identify its tangent space to the space itself by means of the natural isomorphism Ry Tx Rg. By is equipped with the following scalar product:
0
d-v
Vx= = (.CI-....,,,..))) y (UI-......, yd (x, ==
Σ i=1-v
Z +
Σ JH
(I)
The maximal normal neighhorhood for all E Ry is Ux Ry In special relativity, the first elements of x E IRy are called time coordinates and the other ones are called space coordinates.
The pseudo-sphere (r) of radius 0 is called the de Sitter space when 1 and defined as:
()) = (x E R (x, x), r2).
It is not time-orientable if d - v/ is odd, and Uxx = fy E (r)) (x, y), > 2
The pseudo-hyperbolic space H. (r)) called the anti-de Sitter space when v 1 and defined as: (r) == (x Rd+1 (x, x) = =-
The anti-de Sitter space is time-orientable for all d, and Ux = (y E Hr(r): : (x, y)+41 <r²).
The cylindrical Minkowski space (C) R is quotient set defined such that R and y E Iy are equivalent (i.e., x~y) iff vi > 0, y/ = I; and Ek E Z, yo 2o + &C where C > 0 is cireumference hyperparameter. See page 148 O'Neill (1983) for other types of Lorentz cylinders. We have Ux ly- = (yo...., v.) E R yo E (wo C/2, xo + C/2)).
3 SPACETIME GRAPH REPRESENTATION
A spacetime is a connected time-oriented Lorentz manifold M whose points are called events. Informally, fime-oriented is often weakened to time-orientable, and Hawking & Ellis (1973) ignore the úime-orientabiiity criterion to define spacetimes although it is required to study their causal structure. Our main contribution represent graphs. In the following, we always assume that M is spacetime unless stated otherwise. finite directed graph can be given the structure of Lorentzian pre-length space (Kunzinger & Sämann 2018). To define our graphs, we then choose special type of Lorentzian pre-length space that is easy to optimize. We now provide and follow the definitions of Kunzinger Sämann (2018).
exploit this causal structure via Lorentzian pre-length spaces to
Causal space. Let X' be set with reflexive and transitive relation and < a transitive relation contained in & (i.e., &SS, so X < y = x S y). Then (X, <, S) called causal space. This definition is more general than the one given in the seminal work of Kronheimer & Penrose (9977).
Following general relativity, the event x E .M causally (resp. chronologically) precedes the event y M, and we write < (resp. x & y) iff there exists a future-directed causal (resp. timelike) curve from x to y. This condition might be difficult to verify in general. However, if y is in a convex normal neighborhood of denoted by V2 C Ug (and we always assume in the following that x E Vx), we have x < y (resp. x < y) iff there exists a nonconstant future-directed causal (resp. timelike) geodesic from to y (see Proposition 4.5.1 of (Hawking & Ellis 1973)). We note
3

---

Published as a conference paper at ICLR 2023
S = x y. Any open subset W S .M of spacetime is a spacetime in its right, and the intrinsic causal relations of W imply the corresponding ones in M. In the case where W S . is convex open set, the intrinsic causality of W is as simple as that of Minkowski space (see page 403 of Neill ). Moreover, both (M, <, S and (W, <, S)
are causal spaces.
Lorentzian pre-length space. Let (XX, كك be causal space and d metric X. Let X' x X' + [0, oo] be a lower semicontinuous map (w.rt. the metric topology induced by d) that satisfies the reverse triangle inequality: Vx, y, z E X with x S y S Tx 2) 2 T(x,)) + 7(y,2) z). Suppose that 7 yx 0 if x 1 and
(x, 7(x, > O iff x < y. Then (X' d, S, <, T is a Lorentzian pre-length space and T called the time separation function. See details about in Section 3.3
3.1 GRAPH CONSTRUCTION VIA LORENTZIAN PRE-LENGTH SPACES
We now explain our methodological contribution, which is the construction of directed graphs from the properties mentioned above. Let us define a directed graph G = (V, E) where V {u; Vi=1 is the node set and E is the set of arcs. Our goal is to represent each node ey by a point x; M so that there exists an arc from 0% to Vy (i.e., (vg, v2) E E) only if x; < Xj. We propose to consider subgraphs G, (V, Ex) defined such that E = - E.. Each subgraph G3 is given by the structure of the Lorentzian pre-length space (Vx, d, S. &, T) where Vx, S Ux, is an open subset of the maximal normal neighborhood 2x More precisely, we consider the chronological future I+(x;; Vxx) := [y E Vx_= X; < } of the point x; relative to some given set Vx, S Uxx (see page 402 O'elll 1983)), 1), and we draw an are from e to Uj iff x; E EIT (x,, Vx.). Assuming Vx. is a convex normal neighborhood and x, E Vx,, we have X, E I+ (Xi, Vx,) only if x,x} is defined and future-directed timelike (see Proposition 4. of Beem et al. (9966).
Our framework produces a subgraph G = Di_1 G2 of the graph & described by the chronological relations of M, and the causal relations between events depend on the choice of M. It is worth noting that for any spacetime, chronological order is transitive (i.e.. X; < x, and x, < Xx = x; < X (i.e., X E I (x,, M)). see Chapter 3.2 of Beem et al. (1966) 0; is then connected by an are to all the successors of by in G. We avoid this degenerate case by drawing an from e; 2y in G iff Xk Ex,, ). The choice of M and Vx, S M for all i is then crucial to construct G C g.
Existence of directed cycles. Our framework can represent graphs with directed cycles only if . is
non-chronological (i.e., there exists at least one closed timelike curve: Fx E M,, x < x, see Fig. T.
which is the case if M is the anti-de Sitter space (r) or the Cylindrical Minkowski space L (C).
Spacetimes that do not contain closed timelike curves are called chronological (i.c., dx E M, < x)
and can represent only Directed Acyclic Graphs (DAGs) in our framework. Some chronological spacetimes such as (r) (when d 2 3 is odd) or R are called globally hyperbolic and satisfy: x y = x and y can be joined by a (longest) causal geodesic that is not necessarily unique (see page 66 of Beem et al. (1996). Nonetheless, if M is (r()) or IRd, we also have y E I (x, M) iff y E Ux and xy is future-directed timelike (see page 411 of (O" Neill 1983) for details on conditions). Although DAGs do not contain directed cycles, they can contain undirected cycles.
For simplicity, we consider that Vx C Ux is the convex normal neighborhood of x that contains points y such that the arc length d, of the geodesic 7 from x 7()) to y >(1) is smaller than some arbitrary threshold E (0, oo] and can be formulated as d (x,y) == v (xy, x We have:
It (x, Vx)= = {y E Ux
-s² =
< 0, xy E C (t)),
(4)
where C+ (t) is the future timecone parametrized by some arbitrary timelike tangent vector t E T.MM The motivation is to choose or learn E small enough that is not connected to undesired successors of Vy. However, in most of our experiments we simply consider that Vx = Uyx (see Section C.4).
3.2 EXAMPLES OF SPACETIMES
We first illustrate how to represent directed graphs with the simplest spacetime, which is the (flat) Minkowski space [R. It is used in special relativity which is special case of the general relativity of a spacetime isometric to RR.. It is also the geometry induced on each fixed tangent space of an arbitrary Lorentz manifold. It was used in Clough & Evans] (017) to represent DAGs due to its global hyperbolicity and the fact that any pair of points of Ry can be joined by a geodesic. is worth noting that the Hopf-Rinow theorem does not hold for non-Riemannian manifolds such as spacetimes.
4

---

Published as a conference paper at ICLR 2023
Therefore for many spacetimes, there exist pairs of points that cannot be joined by geodesic even if the spacetime is geodesically complete. Working with convex normal neighborhoods Vx. allows us to constrain chronological order between points only via timelike geodesics explained in Section 3.1
Minkowski spacetime RT. We recall that Vv, Ry R TuRy Its geodesic " : R - R is Xx--y(1 (t) == =x+ ty. The exponential map is xxpx == x x y and its inverse is xý : y R is time-oriented by the vector field 0/0zu (e.g., Vx. Y, 7(x.y) y) := yu- and we should in theory define -(xy) == 0 if x A y to properly follow the definition of Lorentzian pre-length spaces but we ignore this criterion during training for optimization purpose). Let us define t ==
(yo mo)
(y: x2 and 3 == (xy, xy) (1v x0)² + i== (y: x.)?
According to equation we have y E I+ (x, Vx) iff xy is future-directed timelike (i.e., , < 0 and (xy, t) < 0, equivalently a 0) and d (x, is smaller than (i.e., -E² < ()).
There might exist a path but no are between x < y (i.e.. y E It (x.M) I (x, Vx) iff (xy, t) < and 8 < e There exists no path between x and y (i.e., * y and y K x) iff B 2 0.
de Sitter spacetime S4 (r). The original de Sitter spacetime (r) is not time-orientable (see Corollary 11.2.6 of Wolf (2011) However, when d 2 3, V 0 and d - v is even, (r) is orientable and time-orientable, the projective space (r)) + used in Law 2021 is orientable but not time- orientable (see page 247 o'ill (1983). ). We assume in the following that conditions hold so that (r) is a spacetime and we refer the reader to the appendix for details.
For any pair of points and xy is timelike iff (x.y) > r². Let : (O.... rrr)² (r) denote the positive pole, and I Tr + Tx (r) denote the parallel transport from (r) to (r) Since the parallel transport preserves the causal character of any tangent vector we can define the future timecone C+ (xý) with respect to the timelike tangent vector == (1,0...... 0) E TT) as follows:
(r)) and y E (t()), xý is defined iff y Uxx (i.e., (xx -,²),
Lemma 3.1. Assuming xý is timelike, xý is future-directed iff (t) E at (x²) i is defined (i.e., p E Ux), and Ix (t) E (xy) otherwise (i.e. -p E Uz). See proof in Appendix C.1.2
The anti-de Sitter spacetime Hr) and its projective version (r) = (r) = 1 are non- chronological and satisfy x << + < x, which is convenient to represent graphs with directed cycles. Sim et al. (2021) use HH to represent directed graphs but also promote ares (i.e., causal relation) between pairs of nodes that are not connected by any geodesic, which makes their problem hard to optimize.
this work, we only consider the existence of ares if there exists a timelike geodesic in the convex normal neighborhood Vx joining two events. See Appendix
[ for details.
A warped product a manifold (M1 x M2. 91 ① f92) denoted by Mi X M2 where (M1191)) (M2. 92) and f M, -> (0, oc) is smooth function called the warping function (e.g.. f- 1). Let M = B x y F be a Lorentz warped product where B is Lorentz and F. is a complete Riemannian manifold. MM is time-orientable iff B is (see page 417 of (O'Neil Neill 1983)). .M satisfies the chronology. causality or strong causality iff B does. Our framework can then be extended to warped products.
3.3 LORENTZIAN DISTANCE AND LORENTZIAN LENGTH SPACES
The Lorentzian distance indicates chronological order (hence causality) between events when it is positive, satisfies the reverse triangle inequality and its squared function of class C2 on a normal neighborhood. These properties make it ideal for optimization. and it can be used as time separation function. We refer the reader to Chapter of Beem et al. (1996) and Section 5 of Minguzzii (2019).
Proposition 4.5.3 of Haawinng& & Ellis (173)): V S Ux- If x and y can be joined by a causal curve in Vx. the longest such curve is the unique causal geodesic in Vx from x to y. This is in contrast with Riemannian geometry where the (spacelike) geodesic corresponds to the shortest curve joining points. Since Vx is a convex normal neighborhood,
Let x and y lie in a convex normal neighborhood
we can define the arc length of such a curve by xv(x,y) := = V- (xy. xý) 2 O. If < y, Xv(x, y) is called the Lorentzian distance from x to y on Vx. it corresponds to the elapsed proper time between the events x and (i.e., as measured by a clock along the geodesic xx- (Gourgoulhon 2016). If we define T := Xv. then (Vx, d, S, <, r) is called a Lorentzian length space. In this paper, we consider the squared Lorentzian distance which is defined as y I TI(xx V2) = x2 (x,,) = (xý, xy)
5

---

Published as a conference paper at ICLR 2023
In the literature (Hawking & Ellis, 1973, Beem et al. 1996), the (squared) Lorentzian distance is defined such that x5(x.y) y) = if and y are not joined by a causal curve due to lack of causality. When evaluating learned representations (i.e., at test time), therefore consider that x (x. y) 0 if this is the case. However, during training and for optimization purpose, we propose to consider:
(xy, xy)
if M-M- = Rd
Ifx x y and y & x, xx(
{
2 y)x 12)
if M (r)
(5)
-(1 y) y)++1 -P
if = (r()..
This makes the function x3 differentiable everywhere (except when (x. (x.y)o44 0+1 Of M (r)).
equal to - -xxy,xy) > 0 if xy is timelike, and non- non-positive otherwise. Xy is defined for any pair of points yx by using extrinsic geometry, whether xý is defined not (see details in Section C.3
4 RELATED WORK
Exploiting spacetimes to represent directed graphs was proposed by CCough & Evans (2117) to extend MultiDimensional Scaling (MDS) (Kruskal 1964) to the simplest spacetime RR. As in standard MDS, a target distance matrix between nodes is given as input and the goal of the method is to find the vector representations of nodes that return the best approximation of the target distance matrix when using the squared Lorentzian distance as the dissimilarity function. However, as discussed in Section 3.3 it is difficult to define target distances between pairs of nodes that are not connected. Moreover, the formulation in (Clough & Evans (017) considers only Ry and does not account for future or past-direction between pairs of nodes during training. We solve this problem in Section 3.2 by enforcing future timelike geodesics to have their length smaller than some threshold e E (0, ooj.
Sim et al. (02T)) extended Clough & Evans (017)) to the anti-de Sitter space and Lorentz cylinder. Although our motivation is similar, contributions methodological, rely on the intuitions of Lorentzian pre-length spaces, and provide an casier interpretation of the Iearned representations as we explain below. First, /Sim et al. (202T) do not address clearly the case when there is no geodesic between pairs of points, and their optimization framework leads to a distance loss term with a zero gradient in this case, which is difficult to optimize. Moreover, their prediction of an between a pair of nodes is determined via a Triple Fermi-Dirac (TFD) probability function that accounts for the distance between the nodes, the time coordinate difference At and its opposite value At (i.e.. TFD accounts for both the chronological future and past of given node). In contrast, we restrict the representation of nodes connected by an are to belong to I (x, Vx) where V an open convex normal neighborhood, which is simple to interpret and optimize. In general, the Lorentzian distance function from x to y on M defined to be infinite if M is non-chronological and there exists closed timelike curve joining x and y. Moreover, the Hopf-Rinow theorem does not hold for spacetimes. Working with convex normal neighborhoods allows us to restrict the existence of ares between nodes to the existence of geodesics joining events. The definition of time separation functions also becomes straightforward and we use their sign to determine the direction of an edge. Our framework shares similarities with Sim et al. (2021) when M R Vx because Rf is globally hyperbolic. Otherwise, we do not formulate our time separation function in the same way and we create arcs differently. Further comparisons with (Sim et al. 22021) are provided in Appendix F
The negative of the pseudo-Riente Riemannian gradient is generally not a descent direction. We then use the optimization tools introduced in Gao et al. (0118): Law & Stam (2020): Law (2021) described in Appendix to learn our representations. Our approach could be extended to time-oriented pseudo- Riemannian manifolds of index if there exists future-directer timelike curve joining them. Lemma 3.1 that exploits parallel transport can for instance be generalized to timelike tangent vectors ti..... t, to define different types of arcs.
(see pages 240-242 of (0 (e'leill 1983)) ). We also have < y
Some Riemannian approaches (Bordes et al. 2013 Ganea et al. 2018 Vilnis et al. 2018) have been used to represent DAGs. Ganea et al. (2018) consider entailment relations where x & y means that y is a subconcept of x by constructing cones for each node representation in hyperbolic geometry. The DAGs they consider are directed trees and their underlying undirected graphs are trees (i.e., graphs without cycles). We propose to consider the chronological future and past that are intrinsic to our manifolds and have been studied for decades to define the causal structure. For instance, it is known that causal relations induce partially ordered sets (called causal sets) on causal spacetimes and can then represent DAGs (Bombelli et al. 1987). Our framework can represent DAGs that are not directed trees (see example in Appendix G.1 and is not limited to DAGS (see examples in Appendix G.2)

---

Published as a conference paper at ICLR 2023
Table 1: Link prediction for directed graphs. Median average precision (AP) percentages across 20
random initializations on a held-out test set.
Dataset
DREAM S. cerevisiae
DREAMS in silico
Manifold dimensionality d'
10
50
100
10
50
100
Euclideun FD
33.0
34.2
40.2
44.5
49.0
29.4
32.9
39.7
39.8
34.8
Hyperboloid + FD
29.2
37.9
46.5
48.8
47.9
28.8
46.8
50.8
50.9
52.5
Minkowski
52.7
54.0
57.7
58.0
Anti de-Sitter TFD
37.2
41.3
44.9
47.5
49.4
38.1
45.2
51.9
55.6
56.0
Cylindrical Minkowski + TFD
37.4
42.7
46.8
53.4
54.6
41.0
48.4
56.3
58.9
61.0
Cylindrical Minkowaki ki + equationn 6
50.0
52.5
55.2
56.2
55.7
52.5
56.5
59.8
60.4
60.8
de Sitter equation
55.3
55.4
EXPERIMENTS
We show how our framework can represent graphs with directed cycles and predict links effectively in Section 5.1 We also show how the causal interpretation of our model can be used to represent hierarchical graphs with cycles in Section 5.2 We provide experiments DAGs in Appendix D.I
5.1 LINK PREDICTION ON GRAPHS WITH DIRECTED CYCLES
We now consider the link prediction task on the Saccharomyces cerevisiae, in silico and Escherichia coli DREAM5 datasets (Marbach et al. 2012) (see values of hyperparameters, results on Escherichia coli with standard deviations and more discussion in Appendix D.2]. We follow the experimental protocol Sim et al. (202T) by considering only the positive-regulatory nodes from the networks mentioned above while omitting the gene-expression data itself. Each network is randomly split into train and test sets, following 85/15 splits, and part of the training is used for validation.
Sim et al. 2021 use the Minkowski space R.d the anti de-Sitter space (r), and the Cylindrical Minkowski space [C) Both (r) and (C) are non-chronological and then represent graphs with directed cycles. (Sim et al. (2021) design a probability function that they call Triple Fermi-Dirac (TFD) specifically for their Cylindrical Minkowski space.
Instead, we propose to define the chronological future I+ (x, Vx) of E L((C) such that if xý is timelike, we have y E I+ (x, Vx) if 3k e Z. yo + kC E (Iu, Ty + C/2). Similarly, the chronological past I (x, Vx) is defined such that if xy is timelike, we have E I [xx, Vx) if 3k E Z, yo &C' (Ig C/2, zo). In detail, we define the time separation function for Lf(C) as follows: 7xx. == (((90- zo ς) mod C)- 9) [- )) where we use the modulo operation for real values which can be written follows: mod == Following our spacetime interpretation, we propose to learn our representations by optimizing:
L8I. and [-] is the floor function.
min {x&EM)
Σ (EL,)))E
log( log(F(x;,x))
Σ (M.N))
log(1 F(x,, xb))
temperature hyperparameters. ) is the sigmoid function. We refer to Section C.2 and C.3 for the formulations of the time separation function 7 and the squared Lorentzian distance x respectively. This promotes future-directed timelike geodesics only between nodes connected by an are. We report in Table the Average Precision scores of our method (i.e., using equation 6 that outperforms baselines reported in (Sim et al.) (202T). The non-chronological cylindrical Minkowski space obtains a higher performance gap oow-dimesiional space. This suggests it accounts for directed cycles better than chronological spacetimes. On the other hand, the gap is reduced in higher dimension except on Escherichia coli where the gap increases (see Table
where F(x; Xy) (x,(xxxxx,,,, x,)) ob (xx,, 01,
m > is an exponent, and (x) := 1/(1 + e-/0)
5.2 HIERARCHY EXTRACTION ON SOCIAL NETWORK DATASET
Pseudo-Riemannin manifolds were introduced in the machine learning literature extract hierarchies in graphs with cycles (Law Stam 2020). Spacetimes are a special family of pseudo-Riece Riemannian manifolds whose time- orienttttnttionn was not taken into account in Law & Stam (2020). In this paper, we found that spacetimes are able to consistently outperform other pseudo-Riece Riemannian manifold approaches by exploiting the causality interpretation implicit in the squared Lorentzian distance.
7

---

Published as a conference paper at ICLR 2023
Table 2: Evaluation scores for the different learned representations (mean + standard deviation).
J the lower the metric, the better. 1 the larger the metric (in absolute value), the better.
Manifold
Problem
d(x,y)
Rank of 1st leader (4)
Rank of 2nd leader (4)
Top (
Top 1
(Baclidean)
equation
d. (x,
11.4
14.0 + 2.4
-0.17 + 0.70
-0.19
E (i))) (hypesbolic)
equation
(x.Y)
0.12
P (elliptic)
equation
(x.y)
7.5 1 0.5
9.1
1.2
-0.59 1 0.03
-0.38 1: 0.08
(r)
equation
d. [x.
2.2 1.3
6.4 0.1:2 2.2
0.28 = 0.26
0.33 0.20
(rr
equation
(x.
0.3
2.8 2 1.3
0.60 + 0.23
0.82 0.16
R (Buclideaa)
equation
(x.
9.4 1.3
11.0 1 0.5
-0.00 1 0.15
-0.38 1. 0.10
P (r) (hyperholic)
equation
dx.xxy)
4.3 1.311
6.1 1.1
0.05 +: 0.39
0.02 0.15
(r) telliptic)
equation
(x.
4.3
5.9
0.09 + 0.38
0.11 0.22
equation
(x.
equation
d., (x.)))
1.0
4.3
0.46
0.61 1 0.14
(de Sitter)
equation
x (x.y)
1.5
4.1 2.0
0.41 0.59
0.38 0.22
(r())
equation
X57 (x,
1.1
2.7 0.8
0.56 = 0.29
0.85 0.07
R (Buclidean)
equation
()
4.6
6.7
0.45
0.19
P (r) (hyperholic)
equation
d., (x.
2.5
3.8
0.36 = 0.22
0.38 0.11
P (r) telliptic)
equation
().
2.5
3.6 0.7
0.46 0.29
0.38 + 0.26
P1 (r)
equation
(x.
1.2
2.7
0.62 0.23
E
equation
(x.
0.72
P
equation
d. (x.y)
1.2
4.4
0.63 1 0.35
0.63 1. 0.16
PT(r)
equation
(x.
1.2
3.0
0.56 + 0.34
0.77 2 0.13
(Minkowski)
equation
X (x)
11
2.6
equation
Xy (x)
1.3 0.5
2,5 1
0.75 1: 0.20
0.90 11 0.07
R (Minkowski)
equation
Xy (x)
1.0 0.0
2.3 0.5
0.70 + 0.17
0.80 0.11
P (r)
equation
X (x.))
1.3 0.5
2.4
0.69 + 0.29
0.90 + 0.07
(r) (de Sitter
equation
Xi (x.y)
0.3
21
= 0.15
0.05
(Minkowski)
equation
(x.
1.
(r)
equation
(x)))
1.1
2.4
0.78 + 0.13
0.91 + 0.07
Graph dataset. We consider an undirected graph G (V, where V { is the node set and E is the edge set such that (Uy, )) E E indicates that v; and 8y are connected by edge. Zachary's karate club dataset (Zachary 1977) is social network of n = 34 members the karate club, each represented by node The club was split in two factions due to a conflict between the instructor (node U1) and the administrator (node Us4) that are the two most important members (i.e., leaders) of the dataset. The other members had to decide between joining the new club created by en or stay with U34- Two nodes are joined by an edge (vt, Uz) E E if the members are friends.
In the original ultrahyperbolic approaches (Law & Stam 2020 Law 2021). each node v; is repre- sented by point x; E M on some pseudo-Riin Riemannian manifold M. The goal is to learn embeddings 1n so that pairs of nodes joined by an edge (2), Uy) E are closer each other than pairs of nodes not joined by an edge. To this end, the embeddings are learned in Law & Stam (0200) Law (202T) by minimizing the following problem:
d(x;,x)(00
min EX
Σ (MLR))E
log e d(x,xxx,)/
Σ (Va, E
d(xu.xo)/0
where the dissimilarity function d(x,, x,) the are length (x,, == / (x,x,, x,x,) of geodesic joining and x,. If M is Riemannian, d, is the Riemannian distance. In this paper, propose instead to consider in equation 7 that d is the squared Lorentzian distance X2 defined in Section 3.3 where Ux is the (convex) maximal normal neighborhood of M.
We also propose to simply enforce the embeddings of U; and v to be joined by timelike geodesic iff (vg, vy) E. Since G is an undirected graph, the future- or past-direction not provided so do not constrain the future-direction of the geodesics during training. Our problem formulation is then:
min
Σ Tg (d(x,, xb)) +
Σ σ8 (-d(x;,x,))
(8)
(X.EM)
(ELEE)E
where À 0 is regularization parameter and set d(x,, x2 xx) The main goal of ) E E to be joined by a timelike geodesic and pairs (Va, vb) $ E. be joined by spacelike geodesic since there is causality between them.
equation is to enforce pairs of nodes u,)
8

---

Published as a conference paper at ICLR 2023
Faction
Faction 34
(trme)
Xa (ttime))
65-
$5
200
24
X1 (spsace)
-10 -05
0.0
0.3
Figure 2: (left) Coordinates of 2-dimensional embeddings x (Zo, x1) learned with equa- tion when M = 13.. (right) Coordinates of the first three coordinates embeddings x = (2o, T1, T2, U3) learned with equation g when M (r)) In Lorentz geometry, timelike geodesic joining two points is the longest timelike curve in a given convex normal neighborhood. This translates in the high-level nodes U1 and 1444 being the furthest from the rest of the nodes. The ground truth edges are plotted in yellow and the node color corresponds to the joined faction. small number of spacelike edges visible (those edges more than 45 degrees from vertical).
Evaluation metrics. We report in Table the results obtained when optimizing equation or equation using different dissimilarity functions. At test time, a score 8, =Ø d(x, x,) summing pairwise distances is assigned each node eú and used
indicator of importance in the hierarchical graph. Following Section 3.3 when the dissimilarity function is the are length d., (resp. squared Lorentzian distance )²). we sort the scores ......,8, 8n is ascending (resp. descending) order and report the ranks of the two leaders 21 and U, (in particular order) in the first two columns of Table 2 averaged over 10 different initializations. We also report in Table the Spearmans rank correlation coefficient y (Spearman) 1904) between the ordered o;
and the order of the 5 and 10 most important nodes which are 34, 1, 33, 3, 2, 32, 24, 4, 9, 14 (in that order, see Law & Stam (2020)).
Results. In general, the squared Lorentzian distance x2 returns better performance than the are length d,, Moreover, the optimization problem in equation 8Jenfrriigg timelike geodesics between connected nodes (i.e., causality) and spacelike geodesics between unconnected nodes (i.e., non- causality) extracts the most important nodes in low-dimensional spacetimes more effectively. The predicted p also shows higher rank correlation with x² It is worth noting that hyperbolic geometry was shown relevant to represent graphs without cycles (Gromov 1987) ) but our hierarchical graph contains cycles, which explains why geometries other than hyperbolic may be more relevant. The performance gap with non Non-Riemannian baselines (Law & Stam 2020 Law 2021 can be explained by the fact that those baselines compare the are lengths of different types of geodesics (i.c., timelike spacelike) that are not necessarily comparable. On the other hand, framework sets non-causal distances to zero at test time, and compares only the lengths of causal geodesics. Figureeillunne iillustrates spacetime diagrams of the learned representations for IR] and (r). The most important nodes tend to be further away from the other nodes with respect to the Lorentzian distance. Most ground truth edges are timelike geodesics and belong the chronological past or future of an edge representation.
We report in Appendix D.3 the same kind of hierarchy extraction experiment on a dataset that describes co-authorship information from papers published at NIPS from 1988 2003 (Globerson et al. 2007). The number of nodes/authors is [V = 2715 and the number of edges is [ 4733.
CONCLUSION
We have proposed general framework to represent data, and in particular nodes of a directed graph, in spacetime. Compared to previous work, our framework is properly endowed with the structure large family
of Lorentzian pre-length space, which makes it easy to optimize and applicable of spacetimes. In the case of hierarchical undirected graphs, we show that we can enforee causality between nodes connected by edge extract the most important nodes in the hierarchy.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Yuval Atzmon, Gal Chechik and Haggai Maron for helpful discussions during the initial phase of this project. We also thank Aaron Sim for sharing his source code, Rafid Mahmood, Jos Stam and the anonymous reviewers for valuable feedback on early versions of the manuscript.
REFERENCES
Shun-ichi Amari. Natural gradient works efficiently in learning. Neural Computation, 10())251-276.
1998. doi: 10. (2.166/0997669800077777777
John K Beem, Paul E Ehrlich, and Kevin L Easley. Global lorentzian geometry. Routledge, 1996.
Luca Bombelli, Joohan Lee, David Meyer, and Rafael Sorkin. Space-time as a causal set. Physical review letters, 59(5);521, 1987.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
James R Clough and Tim S Evans. Embedding graphs in lorentzian spacetime. PloS one, 12(11): c0187301, 2017.
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hi- erarchical embeddings. In International Conference on Machine Learning (ICML), pp. 1646-1666 1655. PMLR, 2018.
Tingran Gao, Lek-Heng Lim, and Ke Ye. Semi-riemannian manifold optimization. arXiv preprint arXiv:1812.00643, 2018.
Johannes Gehrke, Paul Ginsparg, and Jon Kleinberg. Overview of the 2003 kdd cup. Acm Sigkdd Explorations Newsletter, 5(2):149-13) 151,1411111,,., 2003.
Amir Globerson, Gal Chechik, Fernando Pereira, and Naftali Tishby. Euclidean Embedding of Co-occurrence Data. The Journal of Machine Learning Research, 8:2265-2295, 2007.
Eric Gourgoulhon. Geometry and physics of black holes. Institut d' Astroohhysiqqu de Paris, France, 2016. URL/ttps:://Lut /ttp://ttee..........popp./////r obsgga...t/..tttiieeegooooooooo.
Mikhael Gromov. Hyperbolic groups. In Essays in group theory, pp. 75-263. Springer, 1987.
Stephen Hawking and George Francis Rayner Ellis. The large scale structure of space-time,
volume 1. Cambridge university press, 1973.
laroslav Ispolatov, Pavel L. Krapivsky, and Anton Yuryev. Duplication--divrggnne model of protein interaction network. Physical review E, 71(6):06111,, 2005.
Erwin Kronheimer and Roger Penrose. On the structure of causal spaces. In Mathematical Pro- ceedings of the Cambridge Philosophical Society, volume 63, pp. 481-501. Cambridge University Press, 1967.
Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to nonmetric hypothesis. Psychometrika, 29(1):1-27, 1964.
Michael Kunzinger and Clemens Sämann. Lorentzian length spaces. Annals of Global Analysis and Geometry, 54(3):399-447, 2018.
Mare T Law. Ultrahpperbolic neural networks. Advances in Neural Information Processing Systems, 2021.
Mare T Law and Jos Stam. Ultrahyperbolic representation learning. Advances in Neural Information Processing Systems, 2020.
10

---

Published as a conference paper at ICLR 2023
Daniel Marbach, James C Costello, Robert Küffher, Nicole M Vega, Robert J Prill, Diogo M Camacho, Kyle R Allison, Manolis Kellis, James Collins, and Gustavo Stolovitzky. Wisdom of crowds for robust gene network inference. Nature methods, 9 804, 2012.
Ettore Minguzzi. Lorentzian causality theory. Living reviews in relativity, 22(1):1-202, 2019.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. In Advances in neural information processing systems, pp. 6338 (0,,6637,20000
Barrett O'Neill. Semi-Riemannian geometry with applications to relativity, volume 103. Academic press, 1983.
Barrett O' O'Neill. The geometry of Kerr black holes. Courier Corporation, 1995.
Aaron Sim, Maciej Wiatrak, Angus Brayne, Paidí Creed, and Sace Paliwal. Directed graph embed- dings in pseudo-riemannian manifolds. International Conference on Machine Learning (ICML), 2021.
Charles Spearman. The proof and measurement of association between two things. The American journal of psychology, 1904.
Makarand Tapaswi, Marc Law, and Sanja Fidler. Video face clustering with unknown number of clusters. In The IEEE International Conference Computer Vision (ICCV), October 2019.
K. Uhlenbeck. morse theory for geodesics on lorentz manifold. Topology, 14(1):69-90, 90, 1975.
Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. In Annual Meeting of the Association for Computational Linguistics (ACL), 2018.
Feng Wang, Xiang Xiang, Jian Cheng, and Alan Loddon Yuille. Normface: L. hypersphere embedding for face verification. In Proceedings of the 25th ACM international conference Multimedia, pp. 1041-1049, 2017.
Joseph Albert Wolf. Spaces of constant curvature, volume 372. AMS Chelsea Publishing: An Imprint of the American Mathematical Society, Sixth Edition, 2011.
Wayne W. Zachary. An information flow model for conflict and fission in small groups Journal of anthropological research, 33(4):452-473, 1977.

---

Published as a conference paper at ICLR 2023
A
SUMMARY OF SUPPLEMENTARY MATERIAL
The supplementary material is structured as follows:
gives the differential geometry tools that are general to Reeudo-Riemanninn manifolds of constant curvature (called space forms).
Section [
gives the differential geometry tools that are specific to our spacetimes such as the time separation function and the squared Lorentzian distance.
Section C
Section
D
presents additional results and further experimental details.
Section an extended related work section.
Section gives the details of the optimizers we use.
Section gives examples of directed graphs described with our model.
B DIFFERENTIAL GEOMETRY OF PSEUDO-RIEMANNIAN SPACE FORMS
We provide the necessary differential geometry tools to work on the pseudo-Euclidean space Rd the
pseudo-sphere (r) and the pseudo-hyperboloid (r). Most of them are explained in (Law 2021
Law & Stam 2020). We refer the reader to (Hawking & Ellis 1973 O Neill 1983, Wolf 2011).
B.1
SPACE
We recall that Vv, R Tx Rd Its geodesic 7x- IR Rd 7x->(()) x The exponential map at is defined expx (y) x
y and its inverse is xý = expx (y) y x.
Moreover, Vx E R y RR the parallel transport P TARS Ty Ry can be defined as the identity function due to the isomorphism Ry x TRR Ty R. See page 67 of O'Nell 1983).
B.2 PSEUDO-SPHERE (r)
We give here the differential geometry tools specific to the pseudo-sphie sphere which is defined as the following hypersurface: (r) = x E Rd+1, (x, x)v r²) The tangent space (r) of (r
at x can be defined as: T (r) = {u E Rd+1. (u, x), = 0}. In the case of the pseudo-sphere, we have Yu E (r), VV Tx 9x (x(u, v) (u, v) (u. v)u.
Geodesic. The geodesic Yx- R (r) satisfying (0) = x and (0) = u E (r)
formulated for all E I:: Kuulll
sin
(v (uau).)
if (u, u),
(x)) =
x + tu cosh (VTlu
if (u, u) = 0
(9)
X
Viuuu)..
sinh
[ (u,u)y
u
if (u, u) <0
Exponential map. The exponential map expx (x))(r) - (r), (u) 7x (1). We then have:
(r) is defined such that Yu E
cos
+
Viu..). sin (uuu))
if (u, u)v > 0 if (u, u), = 0
eu)x =
x
+
(10)
cosh
<((.u)>>
sinh
if (u, u), < 0
Logarithmic map. The logarithmic map logx is the inverse of the exponential map expx on a normal
neighborhood of (r) denoted by Ux ty (d() (x,y)) -1. it formulated:
areeos
(y (x,)) if (x.), #2 E (-1,1)
Vy Ux, x²= :1oox
X y (x
if (x.y) =1
(11)
if (x
[x,y |2
12

---

Published as a conference paper at ICLR 2023
where arecos is the inverse of the cosine function, and arccosh is the inverse of the hyperbolic cosine function. One can verify from equation 10 and equation 11 that xy is timelike (i.e., (xy. xy) < 0) iff y), > r².
Geodesic "distance". As explained in Law & Stam 2020) and Chapter 5 of O'Neiill 1983). when the logarithmic map exists for some Seeudo-Riemannial manifold M, the arc length of the geodesic -x-xx from M to y M corresponds the radius function: Vlyx(xy,.. xy) where Ix : M x M >
IR is the metric tensor at x and xy lygx(y) is the logarithmic map. The
geodesic distance d (r) x (r) + R is then:
arccosh r arccos
if (x,yle 1 (x pd E (-1111
d (x. = V
(12)
(x
d, not a "distance metric" but a symmetric premetrie: it satisfies (i) dx y) = d (y. 2 0 and (ii) d, (x, 0.
In O Neil 1983). the "minimizing geodesic" is defined by its are length and then also corresponds to the geodesic distance mentioned above.
Given the minimizing geodesic y connecting x to y. the parallel transport T (r) - T T
is a linear isometry such that Yu, v, v) = (u), r (v) (.). The parallel transport along from
x = (0) to y = ((1) (where x and y satisfy (x, y)v 2
(y, 4)v
(u) = u
(x, + p2 (y + x)
(13)
Theorem B.1 (Diffeomorphism (Wolf 2011)). There exists diffeomorphism up (r) - R x
(r) Let us note x-
E (T)r with t E R' and Rd- Let us note z =
E
8)
R" (r) where (r). The mapping vb and its inverse 1 can be formulated:
(x(x)=
and
3 (12411112 0/1
(14)
|ET
where [1-1| is the standard Euclidean norm (i.e., ||||| = Vs Ts).
B.3 HYPUROO-Y (r)
We recall the differential geometry tools (from Laww & Stam 2020 specific to the pseudo-
hyperboloid which is defined as the set: (r)r) {x Bott (x,x)++1 -r2). The tangent
(u. ()xx)u11 = 0). In the case of HH (r), we have Yu E (r), VV E (r), Ix (u, v) = (u, v) = v)+v)
space Tx (r) of (r) at x can be defined as: T (r) = {u E RR+1
Geodesic. The geodesic 7x-u IR + (r) satisfying 7x (0) and ) (0) E (e) formulated for all E IR:
cos
Av Tua
+ Vikuuuo41l
sin ( [ u
if (u, u) if (),u),+1 = 0
(t)+u(t)=
x + lu cosh
(v (V((u)))r1
x
(u,u)+41
sinh
(v [t.u)
u
if (u,u)+41 > 0
(15)
Exponential map. The exponential map expx TxHd(() (r)(r) is defined such that Yu (H) (r)),.pp)p))) (u) = (1). We then have:
ViRu,alutal x +
v Viuuu sin (Miuanso4s)
cos
if (u, u)u41 < 0
expx(u)= = x + u cosh [Vlkuu)oool
if (u, u) = 0
sinh (Vluuiiu
x +
/ V
(u, u > 0
(16)
13

---

Published as a conference paper at ICLR 2023
Logarithmic map. The logarithmic map logx is defined as the inverse of the exponential map expx
on normal neighborhood of x E (r) denoted by Ux = {y E Hy)r) (x-))=+1 formulated:
1). It is
arccosh (- ( y (x. x
if (x
x -1
(nisiiats y2-1
Vy E Ux xÿ = 1y)
if (xylott = -1
X
arccos (للم )a
y (
if |xylo11 E (-11,)
(17)
One can verify that a nonconstant geodesic from x to y is timelike iff (x, E (-p², - or = =xx. Geodesic "distance". The geodesic distance d., (r) Hi)r) R then:
yx V 1+11 arccosh (- (x,y)u41 if (x-y)u+ I --1
arccos ( (x,y) if (x.) E (-1,1)
(18)
Parallel transport HHT (r). The parallel transport connecting (r) y (r) is:
(y, u)
(u) = (x,y)++1 (y +)) where (x. < p²
(19)
Theorem B.2 (Diffeomorphism (Wolf 2011)) There exists diffeomorphism v (r) ()(r) x
(r) with t E IR++ and E IRd-". Let us note = (r(r) x Rd-v where u (r) and v E bRd-v. The mapping sp and its inverse w can be formulated:
Rd-V Let us note x
E
v(x) = ||+|| and (z)
u
(20)
The anti-de Sitter spacetime (r) is non-chronological and satisfies x < convenient represent graphs with directed eycles. It was used in Sim al. (202T) to represent directed graphs. Nonetheless, it is worth noting that the problem formulation of 'Sim et al. (2021)
y < x, which
for (r) also promotes ares (i.e., causal relation) between pairs of nodes that are not connected by any geodesic, which makes their problem hard to optimize. Following general relativity, we only consider the existence of arcs if there exists a timelike geodesic in Vx joining two events x and y. See Appendix C for details.
B.4 PROJECTIVE SPACE (r)
The manifold p = Hr((r/ + used in Law 1021
is time-orientable for all 2 (see page for details about (r) = (r) +
214 O'ill 1983
We refer the reader LLaw
2021
C FUTURE DIRECTION, TIME SEPARATION FUNCTION AND LORENTZIAN DISTANCE
C.1 FUTURE DIRECTION
We discuss in this section how to constrain future direction for our spacetimes.
C. MINKOWSKI SPACE
The explanation can be found in Section 3.2 when M = Rd. We recall that we defined: t =
(1,0,0,0) x
(x) and - (yo mo) + E x;)2..
If a is negative, then xy is timelike (i.c., (xy xy 0) and xý E C (t). By definition, xý is then future-directed timelike.
14

---

Published as a conference paper at ICLR 2023
C.1.2 DE SITTER SPACE
We provide the proof of Lemma 3.1 which is written: when M = ( and xý is timelike, xÿ is future-directed iff Tp(t) E C (xy) if Tp is defined (i.e., E Uxx, and I (t()) E (xy) otherwise (i.e., - Uz).
We first recall a property from page 146 of (O'Neill 1983): ; If M is Lorentz manifold, if piecewise smooth curve a timelike, this means not only that a'(t) timelike, but each break t, of a:
(a'(t)), al (l < 0.
(21)
Here the first vector derives from a al(t-11,t)) ty] and the second from a [[41) Thus a' does not switch timecones at the break.
Let note the poles p (O.... -.) T (f), -p 00.......--)' (r(r) and (1.0...,0) .0 where E (r) and t E T- (r) We also note x (To, .,,...., za) E (
0,
If xa (-r, show below that equation 21 can be satisfied by defining such that a(to) = atti) x. alt2) -p. a (to) t, a' at) (t),), a (tt) - (t), (t2) t. For completeness, we also have vt E (T,, = (t) and VA E [2t, = ra(f) (t).
Let arbitrarily consider that (r) defines the future direction of the manifold. For all E (r) that satisfies (x. p)1 > -p² (i.e., p E Uxx, note (t) the parallel translate of t E T (r) to (r). As explained Appendix B.1.2 of Law 2021 formulated:
(t) = (x.p) (D + x) +
(x,t);
ræa + 22 (p + x)
30
(22)
We know from page 66 of (OiNeill 1983 that parallel transport (also called paraliel translation) is linear isometry that satisfies:
Wv Vu (T), We T,S,(r), (u.v) = (T = (T(()),
(23)
and = 12 (T)( This implies
(t) E C (u) + IT( E (t)
(24)
Similarly, if (x, p)1 - (i.e., -p Ux), have r rx (u) TTP(U) (t).
Let us assume that x satisfies both p Ul (i.e.. (x.p)1 p\1 > -2) and -p E Ux (ie., (x,p), < <²²),
this is equivalent to x satisfying Fa E (-r,r).
If v. E (-r,r). r). then (t) Ct (u), 1x (t) E C (u) + (1) 1 p (t))
0. By definition.
we have:
1x (t) :=
(x, PP) + +
(x, t)
(-p +
=
-TA + p2
50
(-p +x)
(25)
(T)(t), P
(t)) (())), = =-1 rTd + 22 -FXd + r2
20
-2
0
(26)
(aa + r)( Fd + r)
We have shown that (t( and (t) have the same future direction by showing that (T) (t)); < 0. A (piecewise) smooth curve that preserves causality can then be found by using (t)() or (t)
C.1.3 ANTI-DE SITTER SPACE
When M = (r), xy is future-directed iff ( E (x)) if is defined (i.c., p E U2), and I (=p(-t) E (x²) otherwise (i.e., p (bx). The proof is similar to the one in Section C.1.2
Let note the poles p (r.0, Or....... ...,, T)T Hr)()), -p (-r,0,.... O)T E [i((()) and
10, O). where t E (r) and t E T T-plil(()) (r). Let x = (x T0, E (r)))).
We recall that p E Ue iff (x, p)2 < x² (i.c., x- > -r) and -p E Ur iff (x, -p)2 < (i.e., 1-1 r). We define such that .- E (-r,)) (i.e., p E Ux and -p Uk).
15

---

Published as a conference paper at ICLR 2023
Let us note Ix (t) the parallel translate of (r) to (r) As explained in AppendixB.3
of (Law 202 I) it formulated:
(t) ==
(x, P/2 - r2 (p= x) = - -T--1
(x, 2
30
+ x)
(27)
We show below that (t( and _ pp(-t (-t) have the same future direction by showing that (t) (-t)2 (1 < O.
(x, t
F p=pp (-t)) : -t
(-p xx) = --
(-p +X)
(28)
(x, -p/2 p2
rØ-
p2
FD
30
(tt() (-t)2 (((t)) 1+
2
(29)
- - 72
-T- 7
7
x
p² x
2x
O.
(30)
equation 30 negative because we have by definition of HT - 1 implies z 2 2 x²1 > O, and the denominator positive because defined x_ (-r,r).
-
27 -73, which
C.2 TIME SEPARATION FUNCTION
We give the formulations we use for the time separation function 7(x. y) that is positive if is in the chronological future of x. There is no unique way to define it. We assume here that 1.
Globally hyperbolic spacetimes. If the spacetime M is globally hyperbolic, there exists a Cauchy time function e : .M- - R (i.e., for any E R. the set Σ, = {y M c(y) f} is a Cauchy hypersurface) that can be used to define r y)) == c(y) c(x) since satisfies the reverse triangle inequality T rxx, z) 7xx y) + Ty, z) when x S y z. With this formulation, actually satisfies Txx,2) z) yx Tyy,z) when S S.
In theory, to have a Lorentzian pre-length space, one could define t such that is 0 i L y. but this not easy to optimize in practice so we ignore this constraint for optimization purpose.
C.2.1 MINKOWSKI SPACE R(
If M = RR then we arbitrarily define:
r(X.y) == xxy. t) = -xy, xxyt): t) = 9o Zo
(31)
where t == (1, O... 0)T T defines the future timecone C+ (t). worth noting that the function
Rd + R defined such that Vx (wo.... ............. xa-1) E 184 c(x) 20 is Cauchy time function.
C.2.2 DE SITTER SPACE (r())
Following our discussion in Section C.1.2 and using the formulation of the parallel transport in equation 22 we can formulate the time function as:
(T xy t) T xx t),
if (x. p). 2 otherwise.
7(x, y) =
(32)
where v = 1. One limitation of equation 32 is that assumes that xÿ is defined, which might not be the case (if y Uxy).
From the discussion in Chapter 5.2 and Figure 16 (i) of (Hawking & Elbs 1973) that uses Cartesian coordinates to formulate space coordinates the pseudo-sphere, the function (r()) IR defined such that Vx = (fo,-... I.a) o(x) = 2o is a Cauchy time function. One can then also simply define:
((x, y) = To-
(33)
In practice, found that using equation 33 returns better performance than equation 32 in the experiments Section D.I We then also use it for the experiment of Section 3.I See Section D.2 for details.
16

---

Published as a conference paper at ICLR 2023
C.2.3 ANTI-DE SITTER SPACE (r)
When > O, (r) is con-chronological and satisfies x < y = y < X, which is convenient to represent graphs with directed cycles. There exists unture-directer timelike geodesic from x to only if xý timelike or y 1x
Following our discussion in Section 1.1.3 and using the formulation of the parallel transport in equation 27 we can formulate the time function as:
(xy t y(x,y) = - ( xx t)41
if (x. S
(34)
otherwise.
C.2.4 PROJECTIVE VERSION OF THE ANTI-DE SITTER SPACE (r())
We recall that each point [P (r) is an unordered pair (-x x, x} E (r()) where x E (r). By using
the formulation of the parallel transport in equation 27
and assuming
1, we can then define:
Te
t)
if (x, p)11 S and (x, v+1
(xy t
t)
if (x, P) 0 and x, S 0
-(1-x,x,, (-y,)))
(T
t)ut1
if (x, p) S and (x, y) >
Px
-t)+1
if (x, p) and (x,
(35)
Let us assume that p (r, 0, .... 0) We can choose x such that x-1
that (x, p12 5
O is satisfied, and we can also choose y so that (x, S O is satisfied. We can define t (0, 1,....... 0) (r). we define u (u-1, uo, ..... 1d-11 (x(xx) then equation 35 can be rewritten:
7(( ((-x,x),,) yy,
(36)
Another possibility is to the following time separation function:
7(1 x(1-x,x) x(-xx,x),1xx (-y, =
(37)
i=1
which is positive only if xý is future-directed timelike.
C.2.5 CYLINDRICAL MINKOWSKI SPACE IC((C)
As we explain in the main paper, propose define the chronological future I+ (x, Vxx) of
x E (C) such that xý is timelike, we have y T* Vx) if 3 E Z, yo + +CC E (ro, vo + C/2). Similarly, the chronological past I (x, Vx) is defined such that if xy is timelike, we have y I (x, Vx) if 3k E Z, + kC' E (Io C/2,2o).
We define the time separation function for (C) as follows:
r(x.y)= = ((000200) To +
C 2
mod c)
-
C
C C
El
(38)
2'2
where we use the modulo operation for real values which can be written as follows: a mod b =
b 1 and I-] the floor function.
C.3 SQUARED LORENTZIAN DISTANCE
We give the formulation of the squared Lorentzian distance for the different spacetimes that we use in the main paper depending on the nature of M:
If M Rd. xx :- -
= (30
x0)²
Σ x2)2. (39)
(yj
1=1
17

---

Published as a conference paper at ICLR 2023
-xyy,x = 22 arccosh2 2( y((x,)) 22)
if (2.y) 2 otherwise.
If IMM=S((r)) (x,x,)) =
(40)
- (xý, xy = 22 arccos?
[x.))aa] p²
if اx otherwise.
E1-1,1]
M = PM(r) xxxxx
p
(41)
(x,, y/2l
C mod C If MM= xx.x) = (1100 Io
-)
d-1
Σ [y zz)²²
(42)
2
The above equations are equal 0 when x is equivalent to y, which the case y = x in general, or if y =x when M = (r), or if ~ x when M = LÍ(C". Otherwise, the equations are positive iff there exists at least one timelike geodesic from x to y. If the timelike geodesic from x to y + is uniquely defined in lxx we call it xy, and these equations are positive whether xý is future-directed timelike or past-directed timelike.
Squared (Lorentzian) distance in Sim et al. 22221) Sim et al. (2021) acknowledge that there exists no geodesic from y if M (T) and م Therefore, they consider that their squared Lorentzian distance is equal to x² in this case keep their function smooth. This promotes causality between x and y. However, constraining future-direction between x and y when (x,2)2 > becomes problematic without the explicit formulation of a timelike curve. This is why they formulate their time function based on a different criterion than ours that uses parallel transport (see Section C.2) Moreover, the fact that their distance function becomes constant in this case makes it difficult to optimize as the gradient is zero. Instead, we propose to use the manifold M = (r( which can represent the same types of relationships between points (r) since IP (r) contains elliptic and hyperbolic parts (Law 2021), and any pair of points of (r) can be joined by a geodesic.
C.4 ABOUT THE CHOICE OF EQUATION
We explain here why our formulation of equation 4is is general and can be extended to other spacetimes.
As explained in Theorem 2.7 of Minguzzi (2019), an open globally hyperbolic convex normal neighborhood Vx can be defined for any point x E M where .M is spacetime. As we mention in Section 3 any open subset of spacetime is spacetime. Therefore, Vx is a spacetime that can be chosen to be globally hyperbolic. We recall that a globally hyperbolic spacetime is strongly causal, and that the chronological future I (x, Vx) is the set of points y E Vx that satisfy x < y (i.e., there exists timelike curve from x to y).
Since we define Vx to be a convex normal neighborhood, we know from Proposition 4.5.3 of Hawking & Ellis (1973) that any pair of its points x,y that satisfy < y be joined by unique future- directed timelike geodesic "x-xx, which is also the unique longest curve joining x to y. Since Xx-xx is future-directed timelike, it satisfies (xy, xy) < 0 and (x), t) < 0 (i.c., xý E C (t)) where the timelike tangent vector t T&M defines the future direction of M. Moreover, the
length of the geodesic 7x--xý from to y / (xy, xy). and is called its Lorentzian distance.
From Theorem 5.6 and Lemma 5.7 of Minguzzi (2019), there exists strongly causal open set containing x such that its Lorentzian distance with any other point y in that set has its Lorentzian distance (xxxy, x upper bounded by some constant > O. We can then define that open set to be the convex normal neighborhood Vxx and can choose 0 such that all the points y E Vx that satisfy x < y also satisfy =2² < xy) O.
Since Vx is subset of the maximal normal neighborhood Ux. then obtain exactly the definition of equation which is: I+ (x, Vx) = (y E Ux : -ea < (xy. xÿ) < 0, xý E (t)).
In our experiments, we consider that V> Uz. When M is the Minkowski space Rf or the de Sitter space (r), we then have E = +o but we describe some case where e might be finite in Section 3.2 Similarly, we have e rT/22 when M (r), and C/2 when M = (C).
18

---

Published as a conference paper at ICLR 2023
Table 3: Preservation of chronological order between pairs of articles with one citing the other.
V
R
R
(r())
(((())
(f(r)
equation 31
equation
31
equation
31
equation
35
equation
35
equation
35
200
93.7%
94.0% 91.8%
94.2% 92.0%
73.3% 72.2%
73.7% 72.4%
74.9% 72.3%
1000
91.5%
V
(r)
(r)
((()))
(r))
(((r)
()()r)
equation 32
equation 32
equation 32
equation 33
equation 33
equation 33
200
93.8%
93.8% 89.2%
93.7% 89.5%
94.4% 92.8%
94.9% 93.4%
94.9%
1000
89.1%
93.6%
D ADDITIONAL EXPERIMENTS AND EXPERIMENTAL DETAILS
We now report additional experiments and provide experimental details,
Setup. We ran all our experiments on a single desktop with 64 GB of RAM, 6-core Intel i7-7800X CPU and NVIDIA GeForce RTX 3090 GPU.
D.1 CHRONOLOGICAL ORDER IN DIRECTED GRAPHS
Our goal in this subsection is to represent directed graph with spacetimes. As in Clough & Evans (201)). we select the 200 and 1000 most cited papers in the Arxiv High-energy physics theory (HEP-TH) citation network (Gehrke al. 2003). HEP-TH is originally dataset of 27, 770 papers (each represented by node) with 352, 807 edges. The graph contains an arc from to 0j if paper i cites paper j.
When selecting the 200 or 1000 most cited papers, the graph is not a Directed Acyclic Graph (DAG) as there exist pairs of papers that cite each other. We ignore these pairs of ares. To simplify the notation, we write < U/ either if there exists path from to By. or the exists an are from v, to by but not from 22 to n (i.e., there can exist longer path from vy to v;). We also write va & 0s if there exists no path from to or from vs to va (i.e., &
E va).
We optimize the problem:
min (XLEM)
Σ del (xa(xx, +
Σ (av, (-xi(xx,, + 002 (-T x;))) (x,,x)))) K0
(43)
where (x) == 1/(1+ is the sigmoid function, 01, 02 0 are temperature parameters, is
a regularization parameter and 7(x. y) is a time separation function that is positive (resp. negative) y is in the chronological future (resp. past) of x. For instance, if M R then arbitrarily define T (x, = (xy, = Ty. where t = (1, 0) defines the future timecone Ct (t).
temperature hyperparameter values are 0 0g and we fix the radius to r r==1 1. We run our experiments for 10 iterations with step size of 10 6 by using the optimization
In this experiment,
tools of (Law 2021 Law & Stam 2020). The regularization parameter À is set to A
E where TT
|E] the number of pairs that satisty U; Ug and |E
the number of pairs that satisfy va * ob.
We report in Table 3ow well the learned representations manage to preserve chronological order when we select the [V]= [-]=2000 200 or 1000 most cited papers. For instance if M Rd we report the percentage of pairs of nodes v/- < Uty represented by x, and x, that satisfy (x,X,, < 0. The chronological manifolds Rd and (r) manage to predict chronological order better than the non- chronological manifold (r). This suggests that chronological spacetimes are more appropriate to represent graphs that are almost DAGs. The time separation function in equation 33 returns better performance than equation 32 we then use in the rest of our experiments.
Figure 3 iillustrates the embeddings learned when M RJ. Article representations tend to satisfy the chronological order along the time coordinate.
19

---

Published as a conference paper at ICLR 2023
40
200106048
200007018
199905111
30
199806074
20
199803031
19703030
199701025
10
Xo(time)
199612080
199607201
199605150
199603003
196002052
-10
199602022
199510086
-20
199507048
199504047
199309145
-30
199409089
199211021
199208027
-00
-20
-10
10 20
(space)
Figure 3: 2-dimensional representations of the Arxiv High-energy physics theory (HEP-TH) citation network (Gehrke al. 2003) when V 200 and M R.? The first four characters of the labels correspond to the year of submission on Arxiv, and the following two characters are the month of publication. For instance, the label "199208027" corresponds to the article submitted August 1992 available at: http:://aa..vvor//ab//s/ss/ http://ww..rrraaa///eeee//////// 90000//22222277 Similarly, "199409089" the article available ltttps:/ /
org abs hhtp://abbbbee-hhhhhheaaa th/ and submitted in September 1994. The embeddings more less follow the chronological order (along the time axis) which the articles were submitted to Arxiv.
20

---

Published as a conference paper at ICLR 2023
D.2 DIRECTED LINK PREDICTION
In this section, we provide details about the experiments in Section 5.1
We report in Table 4 the link prediction scores the Succharomyces cerevisiae, in silico and Escherichia coli DREAM5 datasets (Marbach et al., 2012). Following the evaluation protocol of (Sim al. 2021). we report the median standard deviation across 20 random initialization. We use the same training and test splits as (Sim et al. 2021).
We the following hyperparameters on the DREAM5 datasets define equation 6
if M = (r),, r 1, 0, = 0.15, exponent m = 1, 02 0.03, learning rate 10-5, number of epochs 2000.
if M = LÍ(C), C. = 8, 01 = 0.15, 02 = 0.03, exponent m 1, learning rate = 10 10-3, number of epochs 2000.
if M = Rd, 01 = 0.15, 02 0.03, exponent m = 1, learning rate = 10-3, number of epochs 2000.
When d = 10, 50 or 100, (r) is not time-oriented (see explanation in Section 3.2 We report the scores obtained in these dimensionalities to be fair with baselines.
We also reran the experiments of Minkowski + TFD on the Escherichia coli DREAM 5 dataset.
is worth noting that the DREAM5 datasets contain relatively small number of cycles:
The Saccharomyces cerevisiae DREAM 5 dataset contains nodes that are part of at least one directed cycle (0.5% of 1,994 nodes) and 19 edges that are part of least one directed cycle (0.5% of 3,940).
The Escherichia coli DREAM dataset contains 18 nodes that are part of at least one directed cycle (1.7% of 1,081 nodes) and 23 edges that are part of at least one directed cycle (1.1% of 2,066).
The in silico DREAM 5 dataset contains 28 nodes that are part of least one directed cycle (1.8% of 1,565 nodes) and 39 edges that are part of at least one directed cycle (1.0% of 4,012).
The choice of specific manifold acts as some inductive bias. When the manifold chosen to be chronological, the created graph does not necessarily contain directed cycles but allows their existence. On the other hand, chronological manifolds are more appropriate for Directed Acyelic Graphs as they ensure that the created graph does not contain directed cycles. From our results, it seems that the (nonchronological) Cylindrical Minkowski spacetime obtains much better performance in the low-dimeen fow-dimensional case as its lack of causality allows some flexibility that is less beneficial in the high- high-dimensional case.
Sim et al. (2021) also use the synthetic 2005), but their dataset contains only 100 edges and 1,026 edges. We generated a bigger version of Dupdiv that contains 1,000 edges and 26.649 edges (22,651 for
dataset (Ispolatov et al.
and 3,998 for test)
following the same setup. More precisely. 748 nodes (74.8%) are part of at least one directed cycle and 22,409 edges are part of at least one directed cycle (84.1 1% of 26,649). Sim et al. (2021) obtain their best performance on their Dupdiv dataset with the Cylindrical Minkowski + Triple Fermi-Dirac larger dataset with Cylindrical Minkowski + equation 6 The results
(TFD). We compare reported in Table 4 and show a consistent gain of 2% mean Average Precision by using a proper time separation function.
We use the following hyperparameters for Dupdiv: M = IRd, 0₁ = 0.4, 0g = 0.07, exponent
m 0.5, learning rate 0.02, number of epochs 500.
21

---

Published as a conference paper at ICLR 2023
Table 4:
Link prediction for directed graphs. Median average precision (AP) percentages across 20 random initializations on a held-out test set.
Dataset
DREAM Saccharomyces cerevisiae
Manifold dimensionality d
3
5
10
50
100
Euclidean + FD
33.0 + 2.7
34.2
+ 2.8
40.2
+ 3.3
44.5
+ 3.5
49.0 + 2.0
Hyperboloid FD
29.2 + 2.5
37.9 + 1.3
46.5 + 1.6
48.8 + 1.4
47.9 17.9-1 +.2 1.2
Minkowski TFD
34.7
2.2
38.6
+
46,4 3.1
52.7
3.0
54.0 2.5
Anti de-Sitter + TFD
37.2
3.2
41.3
1.5
44.9
3.1
49.4
Cylindrical Minkowski + TFD
37.4 2: 3.2
42.7
2. 2.3
3.5 46.8
2.2
54.6 1:6::1111
Minkowski + equation
47.6 1.1
51.3 1.5
54.4
54.7 2.0
54.8
1.3
Cylindrical Minkowski equation 6
50.0 + 1.7
52.5 + 1.4
55,2 + 1.5
56.2 + 1.4
55.7 = 1.7
de Sitter + equation
44.8 2.1
51.6 1
1.6
55.6 1 1.3
S5.3 1 1.4
55.4 T 1.4
Dataset
DREAMS in silico
Manifold dimensionality d
3
5
10
50
100
Euclidean + FD
29.4
2.1
32.9
+ 2.5
39.7 + 1.8
39.8 + 1.6
34.8 + 1.1
Hyperboloid FD
28.8 + 5.5
46.8
4.6
50.8
7.4
50.9 40.9115 1.5
5 1.5
Minkowski TFD
36.3
2.3
4.1
+.00
2.87
58.0
Anti de-Sitter + TFD
4.8
2.3
5.2
4.2
56.0
Cylindrical Minkowski + TFD
41.0 1:001:3 3.6
48.4
56.3 8.4
58.9
61.0 1.9
Minkowski + equation 6
48.4
1.2
49.4 1.1
51.6 1.2
5811
58.8 1.1
Cylindrical Minkowski equation 6
52.5 + 1.9
56.5 + 1.6
59.8 + 1.5
60.4 + 1.5
60.8 = 1.3
de Sitter equation
48.5
1.9
57.4 1.5
62.0 + 1.4
60.6 + 1.6
61.1 = 1.4
Dataset
DREAMS Escherichia coli
Manifold dimensionality d
3
5
10
50
100
Euclidean + FD
33.0 + 3.9
34,2 3.4
40.2 + 4.3
44.5 + 2.6
49.0 3.2
Hyperboloid FD
43.4 + 4.1
4.3
52.7 + 1.9
53.6 1.4
50.6 0.7
Minkowski TFD
43.8 2.0
50.9
57.7
2.3
5..
Anti de-Sitter + TFD
42.7
2.6
61.8
4.8
63.0
Cylindrical Minkowski + TFD
50.3 + 3.3
56.8 1: 3.4
62.3 1.3
65.8 3.4
63.2 + 2.4
Minkowski + equation o
55.9 2.1
57.2 1.8
58.1
58.8 1 1.1
59.1 1.2
Cylindrical Minkowski + equation 6
60.9 + 1.8
64.0 - 2.4
67.5 - 2.3
70.1 + 1.4
70.4 = 2.1
de Sitter equation 6
58.1 2.8
62.4 + 2.3
62.7
+ 1.5
63.4 + 1.3
62.1 = 1.6
Dataset
Duplication Diverrgene (1000 edges)
Manifold dimensionality d
3
5
10
50
100
Cylindrical Minkowski + TFD
55.5 + 0.6
64.7 + 1.3
69.8 + 1.4
70.2 + 1.0
70.7 - 0.8
Cylindrical Minkowski equation
58.7 1.3
66.9 = 1.1
1.1
1.2
72.1 = 1.0
D.3 HIERARCHY EXTRACTION
For both equation 7 and equation 8 0 10- and train the model for 105h itera- tions/epochs. In equation & the regularization parameter is set | [
where |E| is the number of pairs that satisfy (v,, D3) E E' and | is the number of pairs that satisfy (va, vb) & E.
We report scores for the NIPS dataset in Table We report the Spearmans rank correlation coefficient (Spearman) 1904) for all the authors (left), the authors with at least 10 coauthors (middle) and authors with at least 20 coauthors (right). Spacetimes return better performance for the subset of authors with at least 10 coauthors.
22

---

Published as a conference paper at ICLR 2023
Table Evaluation scores for the different learned representations (mean + standard deviation). the lower the metric, the better. 1 the larger the metric, the better.
Manifold
Problem
d(x,y)
Whole dataset p (t)
top ey 2 10 p (1)
Top #s 2 20 (t)
R
equation
d (x. y)
0.469
0.512
0.217
(r)
equation
d, (x.
0.460
0,490
0.292
Pa(r)
equation
0.629
0.552
0.316
P((r)
equation
d,, (x.y)
0.667
0.493
0.307
equation
(x.
0.625
0.441
0.227
Pa(r)
equation
(x.
0.437
0.493
0.387
(r))
equation 8
(x, y)
0.369
0,536
0.663
RJ
equation
X (x, y)
0.524
0.668
0.484
Pi(r)
equation
xx,
0.538
0.326
0.143
(r)
equation
8
(x, y)
0.373
0.498
0.618
R
equation
(x, y)
0.478
0.678
0.543
Pf(r)
equation
xx.
0.576
0.455
0.219
Xo
-2.0
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
26
10
2
19
22
24
28
2
1
2
34
34
0
33
39
32
-1
24
2222
15
11
16
14
10
-2
26
Figure 4: Coordinates of embeddings x-x,x]= (1) C R learned with equation
23

---

Published as a conference paper at ICLR 2023
Faction Faction
Xo(time)
0.5
24
13
27
23
29
15
31
20
30
-1.0
-1.5
-1.0
0.0
1.5
(1(space)
34
Xo (imme)
33
25
2
29
30
26
110
11
8
33
8
20 12
18
31
24
-1
-2
110
-0.5 0.0
0.5
1.0
1.5
2.0
X
1
(To learned with equa- tion when M = R, (bottom) Coordinates of the first three coordinates of embeddings L1. 23) learned with equation when M (r)) In Lorentz geometry, time- like geodesic joining two points the longest timelike curve in a given convex normal neighborhood. This translates in the high-level nodes U1 and 634 being the furthest from the of the nodes. The ground truth edges are plotted in yellow and the node color corresponds to the joined faction. A small number of spacelike edges visible (those edges more than 45 degrees from vertical).
Figure 5: (top) Coordinates of 2-dimensional embeddings
24

---

Published as a conference paper at ICLR 2023
E EXTENDED RELATED WORK
To help explain the contributions of our work relative to prior art, we use this section to provide a more detailed comparison of our contributions to that Sfm al. (202I).
Sim et al. (2021) extended Clough & Evans (0117) to the anti-de Sitter space and Lorentz cylinder. Although our motivation similar, our contributions are methodological, rely on simpler use of the intuitions of general relativity and Lorentzian pre-length spaces, and provide an easier interpretation of the learned representations as we explain below. First. [Sim et al. (2021) do not address clearly the case when there is no geodesic between pairs of points, and their optimization framework leads to a distance loss term with a zero gradient in this case, which make it difficult to optimize. Moreover, in [Sim et al. (202T). the prediction of an are between pair of nodes is determined via Triple Termi-Dirac (TFD) probability function that accounts for the squared (Lorentzian) distance between the nodes, the time coordinate difference At and its opposite value At. In other words, TFD accounts for both the chronological future and past (with different weights) of a given node. The major methodological difference with (Sim et al. (202T) is that we restrict the representation of nodes connected by an are to belong to Z+(x, Vx) where Vx is a convex normal neighborhood. Although subtle, this difference makes the optimization and interpretation of results easier.
In general, the Lorentzian distance function from x to y on M is defined to be infinite (i.e., (xM y) +00) if .M is non-chronological and there exists a closed timelike curve joining x and y. Moreover, the Hopf-Rinow theorem does not hold for spacetimes. We propose to work with convex normal neighborhoods, which allows us restrict the existence of ares between nodes to the existence of geodesics joining events. Our distance function Xv is called a local distance function (see Definition 4.25 of [Beem al. (1996)) when its domain restricted a convex normal neighborhood. Moreover, Xv is continuous and differentiable on V> x I+ (x, Vx) (see Lemma 4.26 of Beem al. 1996)). In some cases, might be easier to optimize its squared function X3 which is of class C Dx V/x (see Theorem 2.6 of Minguzzi (2019). It is worth noting that Vx can be defined to be globally hyperbolic for any spacetime (see Theorem 2.7 of Minguzzi (2019). This means that V~ admits Cauchy time function that can be used to define time separation function (see explanation in Section
whose sign defines the direction of edges. Our framework shares 2021 when M R Vx because Rf is globally hyperbolic and any pair of points of Rę can be joined by geodesic. However, the way we define the time separation restrict it be calculated on the maximal convex normal neighborhood. We construct T so that it is positive if x, E I (x, Vx) and negative if Xy E I (x, Vx). We then enforce 7 to be positive if we want an are from e; to uy. The fact that we work only with an open convex set instead of the whole manifold M is crucial because Xy can belong to both the chronological future I (x,, M) == {y E M : x; < y) and past I (xi I == (y E M y < } if the M is non-chronologie requires that the sign of At is not as informative, as in (Sim et al. (202T). Our approach allows us to determine the direction of the are joining ii and 1y only via the sign of
similarities with Sim et al.
(instead of using the same A/) is different when M = [C((C) because
Using the entire manifold
We also define a general way of optimizing via the parallel transport (see Appendix C.2) instead of working only with Cartesian coordinates, which is not meaningful for some spacetimes such as (r)... Moreover, since we restrict our Lorentzian distances to be calculated in the convex normal neighborhood Vx, we also have the nice interpretation that the Lorentzian distance corresponds the length of the longest causal curve joining points.
One other contribution is the connection of our work with the theory of Lorentzian pen-length spaces (Kunzinger & Sämann 2018) which does not require notions of differential geometry to be understood and can be applied to discrete topologiaal spaces (see Example 2.16 of Kunzinger & Sämann (2018)) The framework proposed by (Sim et al. (202I) is not a Lorentzian pre-length space due to their formulation of their time coordinate difference function that does not satisfy the properties of time separation function (especially when M is non-chronological.
25

---

Published as a conference paper at ICLR 2023
Algorithm Pseudo-Riemannia optimization
input: differentiable function .M R to be minimized, some initial value of E M
I: while not converge do
2: Calculate V fx)
iic. Vx((x) is the Euclidean gradient of at in the Euclidean ambient space X IIx (GIIx(GV/(x))
4: x 4- ( (-x)
D where v) >> 0 is a step size
5:
end while
F OPTIMIZATION
The optimizers that we use in the main paper for the different spacetimes can all be optimized as described in Algorithm| [1] The goal is to minimize some function f M IR by using differential geometry tools described in (Gao et al.) 2018 Law 2021 Law & Stam 2020).
Vx(x) is the Euclidean gradient of f at x, (z) is the orthogonal projection of an arbitrary vector z onto M, and G an involutory matrix (i.e., G G). We consider in the following that the step size 1j > is fixed and given. We give details for the different spacetimes that we consider in the main paper.
F.1 MINKOWSKI SPACETIME R
This optimizer explained in (Gao al. 2018 When M R4 IIx is the identity function. G the diagonal matrix with the first diagonal element equal to -1 and the remaining ones equal to 1. expx (y) x y. Algorithm corresponds to the standard Euclidean gradient descent because f(x in this case.
F.2 CYLINDRICAL MINKOWSKI SPACETIME (C)
We recall that (C) = |
/~, / (i.e., x-y)) iff Vi 0, yt x, and 3k E E. you To + kC where C' > 0 is circumference hyperparameter.
quotient set defined such that x E Ef and y E Rf are equivalent
When M Lf(C), we use the same optimizer in Section F.1
Although it is optional, we also reproject the time coordinate of x = (Io...., Id-1) at the end of
2 ? where we use the modulo operation for real values which can be written as follows: a mod == a - b- [g.. and [-] is the floor
each iteration as follows: zo + ((Ir) G) mod C) )) E | C C
function. If the initial value of zo is not in |- C )), this projects x to an equivalent point.
2
F.3 DE SITTER SPACE (r)
This optimizer
introduced in (Law & Stam 2020). We recall that ()( {x R (x, x)1 = =2). the diagonal matrix with the first diagonal element equal to -1 and the remaining ones equal to 1. We have: (z) := (2.x)
(2.x)) The exponential map is defined in
[x.]
equation 10
F.4 ANTI-DE SITTER SPACE (T)
We recall that H)(()) == {x IR5+ (x, - G is the diagonal matrix with the first two
diagonal elements equal to 1 and the remaining ones equal 1. We have: Txx (x.x]2
(x.x)2 x
+ (x.x) x. The exponential map defined in equation
F.5 PROJECTIVE VERSION OF THE ANTI-DE SITTER SPACE (((r)
The neural network optimizer is given in (Law 2021). Otherwise, the embedding optimizer is the same as Section F.4. The main difference is how the points are compared to calculate the distance and time separation function.
26

---

Published as a conference paper at ICLR 2023
G EXAMPLES OF GRAPHS
Since our general framework fairly abstract, we give some explicit examples of directed graphs with without cycles that can be described by our framework.
G.1 DIRECTED ACYCLIC GRAPHS (DAGs)
1/2
03
U5
06
Figure 6: DAG containing an undirected cycle.
We first consider a directed acyclic graph that consists of an undirected cycle (Figure 6 The DAG G = (V, F.) is defined as {(11, ea), (12, v4). (u2, us), (13, us), (V1, 16), (13, va)}. One can see that G is not a directed tree since the undirected path U1, U4, U2 Us 13, vG, V1 is cyclic.
{or)==1 and the set of ares E
We recall that if .M is globally hyperbolic, M is also chronological and can then only describe DAGS with our framework. Let us give an example where M = R2+1 or M = (r( C IR with d 3 and 0 (e.g.,
1). Both Rd+1 and (r) are globally hyperbolic. Let consider any value 0, a r + and 22 22. We take the embeddings: x1 (0,r, 0, 0) X2
(0, 0, r, 0) X3 = (0,0,0,r) X4 = (b,a,a,0))
= (b, a,,,,.00 a) X6 = (b. a, 0,
When M $ (r), know from Section B.2 that x,X; is timelike (i.e., (x,x) x,
iff (xi, x,)1 > y². By using the time separation function in equation 33 and assuming x,X; is timelike, we only need to compare the first coordinate of x; and Xj to determine the direction of the edge between 2 and Ey..
The case M R similar except that X:X; = Xj x; is timelike iff (x.x), X(Xi) O.
One can verify that Vi (vi, vz)= E E > E Ux: and the tangent vector x;X; is future-directed timelike.
G.2 GRAPHS WITH DIRECTED CYCLES
G.2.1 MINKOWSKI CYLINDER L((C)
U1
1/
1/2
Figure 7: simple directed cycle.
We now illustrate simple example of graph with directed cycle that can be drawn with (C( (Figure 7). The graph G (V, E) is defined as V = {or)a_ and E = {(v1, 02). (12, Us), (Es, 01) which is graph with directed cycle.
Let us consider that C = 3 and d = 2. The maximal normal neighborhood of every point E R4 is Ux= {y- = (yo. v/-1) E T.. Yo E (an 1.5, vp + 1.5)]. We also consider that Vx = Ux.
Since (C) is quotient set, its points are equivalence classes. We consider three equivalence classes [x,] : {(i + 3k, 0) E 2) where E (1,2,3) and we define x; : (i, () 12. In other words, the five points
(0, XI in IR actually correspond to three points in (C) due to the equivalence relation (i.e., Xy Xy and X4 X1). We can then compare those three equivalence classes by comparing x; with x;-1 and x;+1 only. One can verify that E 2, 3). we have x;+1 E Uxx,, X E I (x"(x; (x, ). and x, Ux.- However, also have x;-1 $ I ZT,,,, (x,,) We then obtain the graph illustrated in Figure
(1,
(2 X3 (3 X4 (4, 0)
27

---

Published as a conference paper at ICLR 2023
G.2.2 PROJECTIVE VERSION OF THE ANTI-DE SITTER SPACE (((r)
V1
1/
1/
V/3
Figure A graph with directed cycles.
We now consider the graph G = (V, E) defined as V {r) and E {(11, u4), (12, 11), (13, v1), (03. 02), (V,, U2), (vi, 1z)}. This a graph with directed cycles (e.g., 01 + + v2 + see Figure ().
We recall that every point of (r() can written as the unordered pair {-x, x) where x e HT((r) C RR++1 Taking d 2, the maximal normal neighborhood of every point { {-x, x} can written [[-xx) yf y E (r),,, xx 0}.
Let us consider = 1,6 = -0 = = --,,a= -- -
-
3 We construct the four follow-
ing points: X1 p = (r. 0, .x (r o1,
(r E2, e) X1 (r gx.
To define the future direction, we consider the timelike tangent vector = 1,0) E (r)).
In our framework, there exists an edge between X; and x, iff (xx, x,)21 E (0, r?). The direction of the edge is determined by using Section C.2.4
28


Reviews:
[{"review_id": "ZnVCg0KziI", "reviewer": "Reviewer_bMme", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies embedding of directed graphs into Lorentzian spacetimes.  The idea is very natural as such spacetimes have causal structure, and a pair of points can be embedded with timelike separation if there is an edge and spacelike if there is not.  It was proposed by Clough and Evans (2017) and studied by Sim et al (2021) and others.  The present work generalizes this in various ways: use spacetimes other than Minkowski which can have closed timelike curves and thus represent graphs with directed cycles, and exclude part of the future lightcone to represent nontransitive graphs.  Probably the most significant improvement over previous models is the use of a time separation function in the objective function to distinguish link orientations.  Several experiments are done to choose hyperparameters (spacetime topology, dimension, norm) and provide proof of principle.  It is found that a cylindrical Minkowski space is better than Minkowski space for low dimensional embeddings.", "summary_of_the_review": "Not a bad work but without sufficient novelty or depth to meet the standards of this conference.", "strength_and_weaknesses": "Strengths: ideas are simple and have some interest, presentation is relatively clear for a reader with a background in the relevant geometry.  Known results on spacetimes developed in the study of general relativity are brought into the discussion.\n\nWeaknesses: the results are incremental, especially compared to Sim et al (2021).  The new ideas are not explored in any depth.  The experiments do not go farther than proof of principle.  Comparison with other work outside of this very specific direction is weak, for example no mention is made of the very popular and standard methods for embedding directed graphs such as TransE (Bordes et al 2013).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "W-ICihsEui1", "reviewer": "Reviewer_WSKC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "As for data represented as a directed graph, in order to explore the causal structure within the manifold,  the authors introduce a general family of representations based on time-oriented Lorentz manifolds.", "summary_of_the_review": "The paper proposes the model with clear motivation and describes the proposed model clearly. Meanwhile, the experimental results show the proposed model is effective. So it is suited for ICLR.", "strength_and_weaknesses": "Strength of the paper: \n1. Inspired by the Lorentzian causality theory,  the paper proposes a general framework for directed graph representation learning based on pseudo-Riemannian manifolds. \n2. The authors make a comprehensive summary of related work and the motivation is clear.\n3. Sufficient experiments are conducted to evaluate the effectiveness of the proposed model on related graph datasets.\n4. Additive tools are presented to account for time orientation and exploit distances specific to Lorentz geometry.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TnHjybpwMwW", "reviewer": "Reviewer_SZRp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a novel data representation framework, namely, the spacetime graph. Both theoretical and experimental analyses are provided to show the effectiveness and superiority of the proposed framework.", "summary_of_the_review": "The proposed spacetime graph framework is interesting and novel to me. But currently, the writing and organization of the paper could be improved for better readability.", "strength_and_weaknesses": "- Strengths:\n    1. The authors present the definition of basic concepts in spacetime differential geometry with detailed explanations of the mathematical notations, which helps the readers to better understand the paper.\n    2. Experiments on commonly-used graph learning benchmarks show the superiority of the proposed spacetime graph.\n- Weakness:\n    1. I feel that this work focuses more on the construction of a spacetime graph instead of the representation learning (especially learning) on it.\n    2. The method is not presented clearly enough. It simply refers to several previous works and theories for many crucial steps in the proposed method, without enough explanations.\n    3. Are the assumptions of Eq. 4 mild enough for the generality of the proposed framework?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "K7Sxf4V7cv1", "reviewer": "Reviewer_cPyY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a framework inspired by Laurentzian audacity theory like learn directed graph representation. This framework is evaluted in different tasks and show how this framework can represent graphs with directed cycles.", "summary_of_the_review": "The proposed spacetime graph framework is interesting. But the writing and organization of the paper make very difficult to understand the novelty and the contributions of the paper. ", "strength_and_weaknesses": "Strength\n- The experiments results  show the superiority of the proposed spacetime graph.\n- Using  Lorentz manifolds in the context of the paper is very interesting. \n\n Weaknesses\n\n- I am familliar with Riemannian geometry but I found this paper difficult to read. The writing and organization of the paper could be improved for better readability.\n- The results are incremental, especially compared to Sim et al (2021). \n- The authors should explain in more details their contributions instead of explications  of basic differential geometry. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster