Neural Spacetimes for DAG Representation Learning
Authors: Haitz Sáez de Ocáriz Borde
Anastasis Kratsios
Marc T. Law
Xiaowen Dong
Michael M. Bronstein
Venue: ICLR 2025 Poster (2025)
Keywords: Directed Graphs
Quasi-metrics
Primary area: learning on graphs and other geometries & topologies
TL;DR: A neural network approach to learn weighted Dyrected Acyclic Graphs (DAGs)

Abstract: We propose a class of trainable deep learning-based geometries called Neural SpaceTimes (NSTs), which can universally represent nodes in weighted Directed Acyclic Graphs (DAGs) as events in a spacetime manifold. While most works in the literature focus on undirected graph representation learning or causality embedding separately, our differentiable geometry can encode both graph edge weights in its spatial dimensions and causality in the form of edge directionality in its temporal dimensions. We use a product manifold that combines a quasi-metric (for space) and a partial order (for time). NSTs are implemented as three neural networks trained in an end-to-end manner: an embedding network, which learns to optimize the location of nodes as events in the spacetime manifold, and two other networks that optimize the space and time geometries in parallel, which we call a neural (quasi-)metric and a neural partial order, respectively. The latter two networks leverage recent ideas at the intersection of fractal geometry and deep learning to shape the geometry of the representation space in a data-driven fashion, unlike other works in the literature that use fixed spacetime manifolds such as Minkowski space or De Sitter space to embed DAGs. Our main theoretical guarantee is a universal embedding theorem, showing that any $k$-point DAG can be embedded into an NST with $1+\mathcal{O}(\log(k))$ distortion while exactly preserving its causal structure. The total number of parameters defining the NST is sub-cubic in $k$ and linear in the width of the DAG. If the DAG has a planar Hasse diagram, this is improved to $\mathcal{O}(\log(k) + 2)$ spatial and 2 temporal dimensions. We validate our framework computationally with synthetic weighted DAGs and real-world network embeddings; in both cases, the NSTs achieve lower embedding distortions than their counterparts using fixed spacetime geometries.

Published as a conference paper at ICLR 2025
NEURAL SPACETIMES FOR DAG REPRESENTATION LEARNING
Haitz Sáez de Ocáriz Borde University of Oxford
Anastasis Kratsios
McMaster University & Vector Institute
Mare T. Law NVIDIA
Xiaowen Dong University of Oxford
Michael Bronstein
University of Oxford & AITHYRA
ABSTRACT
We propose a class of trainable deep learning-base geometries called Neural SpaceTimes (NSTs), which can universally represent nodes in weighted Directed Acyclic Graphs (DAGs) as events in a spacetime manifold. While most works in the literature focus undirected graph representation learning causality embedding separately, our differentiable geometry can encode both graph edge weights in its spatial dimensions and causality in the form of edge directionality in its temporal dimensions. We use a product manifold that combines a quasi- metric (for space) and partial order (for time). NSTs are implemented as three neural networks trained in an end-to-end manner: an embedding network, which learns to optimize the location of nodes events in the spacetime manifold, and two other networks that optimize the space and time geometries in parallel, which we call a neural (quasi-)min )metric and a neural partial order, respectively. The latter two networks leverage recent ideas at the intersection of fractal geometry and deep learning to shape the geometry of the representation space in a data-driven fash- ion, unlike other works in the literature that use fixed spacetime manifolds such Minkowski space or De Sitter space to embed DAGs. Our main theoretical guar- antec is universal embedding theorem, showing that any k-point DAG can be embedded into an NST with + (log(k)) distortion while exactly preserving its causal structure. The total number of parameters defining the NST' is sub-cubic in k and linear in the width of the DAG. If the DAG has a planar Hasse diagram, this is improved (log(() 2) spatial and temporal dimensions. We validate our framework computationally with synthetic weighted DAGs and real-world net- work embeddings; both cases, the NSTs achieve lower embedding distortions than their counterparts using fixed spacetime geometries.
INTRODUCTION
Graphs are a ubiquitous mathematical abstraction used in practically every branch of science from the analysis of social networks (Robins et al. 2007) to economic stability (Hurd et al. 2016) and genomics (Marbach et al. 2012). The breadth of social and physical phenomena encoded by large graphs has motivated the machine learning community seek efficient representations (or embed- dings) of graphs in continuous spaces. Since the structure of graphs typically has properties differ- ent from Euclidean geometry (e.g., trees exhibit exponential volume growth), a significant effort has been made to identify non- -uc-ldiid geometries which can faithfully capture the structure of general graphs. Examples include hyperbolic embeddings of tree-like graphs (Ganea et al. 2018 (oonthaia & Gilbert 22200] Shimizu et al. 2021: Kratsios et al. 2023a b), spherical and toroidal embeddings of graphs with cycles (Schoenberg 1942] Guella et al. 2016 Giovanni et al. 2022b). embeddings of graphs with several of these characteristics into product Riemannian geometries (Borde et al.
2023a b) Giovanni et al, (202aa), combinations of constant curvature Riemannian manifolds (Lu
al. 2023) and manifolds with locally controllable Ricci curvature (Giovanni al. 2022b).
Email addresses: chri 67040ox uuk catisiiccmmmmmstee... adongerobotas ex. ac uk, mi chael bronsteinees ox ww..ac.ur uk
marcl @nvidiviiii

---

Published as a conference paper at ICLR 2025
DAG
Feature Encoder
Space- Time--immeee Manifold
D.7 T.
Time exis
Figure I: A Neural Spacetime (NST) is a learnable triplet 8 = (E,D,T), where & BRN - R D+T a (feature) encoder network, D IR D+T IR D+T [0, oc) is learnable quasi-metric on RD and T :RD+T + RR' is learnable partial order on R Given an input Directed Acyclic Graph (DAG), optimizes the location of the nodes u, v, w as events in the spacetime manifold û, 0, w, while concurrently D and T learn the geometry of space and time themselves. The objective is to find a geometry that can faithfully represent, with minimal distortion, the metric geometry of the input DAG in space well its causal connectivity in time.
The Directed Graph Embedding Problem. The description of many real-world systems requires directed graphs, for example, gene regulatory networks (Marbach et al. 2012), flow networks (Deleu al. 2020), or graph metanetworks (Lim et al. 2024) to name a few. Directed graphs (or digraphs) play significant role in causal reasoning, where they are used to study the relationship between a cause and its effect in a complex system. These problems make use of representation spaces with causal structures, modeling the directional edges of a discrete graph as causal connections in a continuous representation space (Zheng et al.) 2018). However, most approaches in causal representation learning primarily focus capturing directional information while neglecting distance information. Recent works (Sim et al. |021 Law & Lucas 2023) have suggested that Lorentzian spacetimes from general relativity
al. 2022), stochastic processes (Backhoff-Veraguas
suitable repre- sentation spaces for directed graphs, as these geometries possess an arrow of time that provides them with causal structure (see Appendix A.S)) while also being capable of encoding distance. Instead of considering a single arrow of time, in this paper we propose to turn to richer causal structures with multiple time dimensions, allowing to model greater directional complexity.
Problem Formulation. Our goal is to learn a spacetime manifold representation where nodes in a DAG can be embedded events. This should be done while capturing edge directionality in the form of causal structure (which includes modelling lack of connectivity as anti-chains), as well as the edge weights in the original discrete structure: these are represented as temporal ordering and spatial distance in the continuous embedding space.
The Neural Spacetime Model. We propose a trainable geometry with enough temporal and spatial dimensions to encode a broad class of weighted DAGs. In particular, the Neural SpaceTime (NST) model utilizes MultiLayer Perceptron (MLP) encoder that maps graph node features to an inter- mediate Euclidean latent space, which is then fragmented into space and time and processed in parallel by neural metric network (inspired by the neural snowflake model from Borde Kratsios) (023)) and neural partial order. These embed nodes jointly as causally connected events in the continuous representation while respecting the one-hop distance (given by the DAG weights) and directionality of the original discrete graph structure, see Figure [ The spatial component of our model, which considers D spatial dimensions, leverages large-scale and asymptotic embedding ap- proaches relevant in coarse and hyperbolic geometry (Nowak) 2005 Eskenazis et al. 2019), well as the small-scale embedding-basse
approach of Borde & Kratsios (2023) inspired by fractal-type metric embeddings. These are often used to encode undirected graphs equipped with their (global) geodesic undirected distance (Bourgain 1986 Matoušek] 1999 Guptal 2000 Krauthgamer et al.,
2004 Neiman 2016 Elkin & Neiman 2021 Andoni et al.] 2018: Filtser 2020 Kratsios et al.,
2023a Abraham et al. 2022), which implies that their local distance information can also be em- bedded (Abraham et al. [007 Charikar et al., 2010). Note that the opposite not true: optimizing for the local geometry does not guarantee faithful representation of the global geometry (Ostrovska & Ostrovskii 2019). On the other hand, the temporal component of our trainable geometry param- eterizes order structure 5" multiple T' time dimensions. Thus, causality in our representation space simply means that a point r E R+T precedes another y E R R+T in the sense that x ST (which only considers order in time T, see Section 3). When T 1, geometry corresponds to using a Cauchy time function of the globally hyperbolic Lorentzian spacetimes to define a partial order (see Beem al. 1996 Page 65) or Burtscher & Gareia-Hevellng (2024)).
2

---

Published as a conference paper at ICLR 2025
Our contributions are: (1) We propose a tractable neural network architecture for spacetimes (with multiple time dimensions), ensuring that only valid geometries are learnable; hence, the term neural spacetimes (NSTs). Our approach decouples the representation into a product manifold, which mod- els )qutris)metrics and (partial) orders independently. (2) Our main theoretical result, Theorem I provides global embeddability guarantee showing that any (finite) poset be embedded into neural spacetime with a sufficient number of temporal and spatial dimensions. The embeddings are causal in time and asymptotically isometric in space. Furthermore, the neural spacetime model only requires (Ik²) parameters to globally embed a weighted DAG with k nodes. Theorem 2 shows that a broad class of posets can be embedded into a NST with at most two temporal dimensions. (3) We experimentally validate our model on synthetic metric DAG datasets, as well as real-world directed graphs that involve web hyperlink connections and gene expression networks, respectively.
2 PRELIMINARIES DIRECTED GRAPHS, POSETS, AND QUASI-METRICS
We now introduce the relevant notions of causal and spatial structure required to formulate our main results and our model. This section concludes by discussing the concept of spacetime embeddings, which represent DAGs in a continuous space encoding both their causal and spatial structure.
2.1 CAUSAL STRUCTURE
Directed Graphs. Consider weighted directed graph, GD = (Ep, V, WD). where EDD represents set of directed edges, V set of vertices, and WD the strength of the connections, respectively. We say that two vertices u, V E V are causally connected, denoted by & v, if there exists a sequence of directed edges, a path ((v,, ((n,;,++)) N-1 V with V1 u and VN = v. Notice that causal if u z v and The neighborhood (Mu) of a node E V is the set of nodes sharing an edge with w; i.e.N(N A(()) def. {v E V (u, v) E En or (v, u) E EDD. Every weighted directed graph GD = (FD, V, WD) naturally graph upon forgetting edge directions, meaning that it induces weighted undirected graph G = (E, V, W) where E Hu, w E EV: (u,v) E En or (v, u) E En} and where W is the symmetrization WD. W(u, v) del Du,, v), (v,
connectivity is a transitive relation; that "
then u * w, for each U, w E V.
Remark 1 (Feature Vectors and Nodes). In practice, e.g. in Graph Neural Network (GNN) (Scarselli el al. 2009) use-cases, one equips the nodes in the graph G = (En, V, WD) with set of feature vectors tee in R. We thus henceforth idenify the set of nodes V in any graph with a set of feature vectors in RN for some positive integer N. via the identification V E t+ Fo E R
Posets. A broad class of logical relations can be encoded as directed graphs. We consider the class of partially ordered sets (posets): the pair or tuple S). In particular, key characteristic of a poset is that for any two elements u and in the set the following properties are satisfied: reflexivity. Vu E V, u & u, antisymmetry, u & u A u x u - u Vi and transitivity, Vu, v, E V, u D AAAE w Every poset induces a DAG structure on the vertex set V.
B
w.
D
Example (From DAGs to Posets). Given the DAG Gp (En, V. WDW,), then we define the relation & vertices u, E V such that u & v if either u = 1 or there exists directed path from u to v in the graph. This relation estab- lishes (V. S) as a poset.
E
Figure 2: The red arrows illustrate the Hasse diagram (DAG) with directed edge set {(A, B), (B,C), (B, D), (D, E)}- Its corresponding poset is depicted using green arrows on the same vertex set (A, B, E). Our partial order is not a total order as there no red or green arrow between C' and E. Red arrows encode key DAG structure and green arrows encode all their possible compositions.
The antisymmetry condition is not satisfied by all digraphs, but only by certain types of digraphs such as DAGs, since it is incompatible with directed cycles of length greater than 1 (loops other than self-loops). Conversely, posets induce directed graphs. This identification is encoded through the Hasse diagram of a poset, see Example which is natural way to forget all composite relations in the poset by identify- ing the key basic skeleton relations encoding all its structure.
3

---

Published as a conference paper at ICLR 2025
The poset can then be recovered from its Hasse diagram by adding all compositions of edges and self-loops, see Figure 2
Example 2 (From Posets to DAGS: Hasse Diagrams), The Hasse diagram of poset (V; is
directed graph GD = [ED. V) with V def ED and Vu, v E V. (u, v) E ED iff 1) Eu S Te. 2) u + v and 3) there is no w
{u, of with zu S Iw S To (so Iu S Zy is a "minimal relation"
Our theoretical results in Section 3.1 focus on embedding guarantees for posets induced by DAGs, which are of interest in causal inference (Textor et al. 2016 Oates al. 2016), causal optimal trans- port on DAGs (Eckstein & Cheridito| 2023), which is particularly important in sequential decisions
making (Aceiato et al.| 2020) Backhoff- Veraguas et al. 2020; Xu al. 2020 Eckstein & Pammer
2024 Kršek& & Pammer [2024] Gunasingam & Wong 2024) and in robust finance (Bartl et al.] 2021 Acciato et al. [024)), ) in applied category theory (Fong & Spivak 2019) since any thin category is a
poset [Chandler] 2019), and in biology applications such as gene expressions (Marbach et al. 2012
2.2 SPATIAL STRUCTURE
Quasi-Metric Spaces. Although Riemannian manifolds have been employed to formalize non- Euclidean distances between points, their additional structural characteristies, such as smoothness and infinitesimal angles, present considerable constraints. This complexity often makes it challeng- ing to express the distance function for arbitrary Riemannian manifolds in closed-form. On the other hand, masi-mettic spaces isolate the pertinent properties of Riemannian distance functions without requiring any of their additional structures for graph embedding. A quasi-metric space is defined as set X equipped with distance function d X X + [0, oo) satisfying the following conditions for every Tus Tu. Tw E X: i) d( Fo) = 0 if and only if F. = Iu. ii) d(Iu, Te) = d(z,, Fw), iii) d(xru x..) S C(d(sa: (ww) + d(Zir,, r.)). for some constant C 2 1. Property (iii) is called the C-- relaxed triangle inequality. When C' 1, (X,d) d) is termed a metric space, and the C-relaxed triangle inequality becomes the standard triangle inequality. Quasi-metrics arise naturally when considering local embeddings since the triangle inequality is only required to hold locally, allowing for small neighborhoods of distinct points in a point metric space to be embedded independently from one another. Furthermore, these geometries share many of the important properties of metric spaces, e.g. the Arzela- Assola theorem holds (Xia) 2009). Moreover, if property (i) is removed, such that several points may be indistinguishable by their distance information, then we say that d is a pseudo- quasi-metric (Kim) 1968 Künzi (992). This naturally occurs when additional time dimensions used to encode causality, but distance is ignored.
Example 3. Every weighted graph G = (E, W) induces a metric space (V,da); e.g. using the shortest path (graph geodesic) distance de. defined for each v E V by
dc(u,v) def inf
Σ (VnnVnn-)) :3 : (11 =2,12) ... UNN-LIN=D)ER
(I)
One could define the inf of the empty set to be max W(u, v) + 1 (instead of co, which is unsuitable for learning and emhedding). However, following the spacetime representation literature, we are only interested in learning the distance between causally connected nodes (Section 3.2). We emphasize that only simple weighted digraphs are considered here, meaning that we do not allow for self- and each ordered pair of nodes has at most one edge between them. As later discussed in Section Dectionn3.]]e and Section NSTs can model causal connectivity in one direction (but no undirected edges), as well as lack of causal connectivity between events (anti-chains).
2.3 SPACETIME EMBEDDINGS
We will work in a class of objects with the causal structure of DAGs/posets and the distance structure of weighted undirected graphs. We formalize this class of causal metric spaces follows.
Definition (Causal (Quasi-)Metric Space). A triple (X, d, S) such that (X, d) is a (quasi-)metrid space and (X,S) x) is a poset, is called causal (quasi-Jmetric space.
Having defined meaningful class of causal metric spaces, we now formalize what it means to approximately create a copy of a causal metric space into another. The goal is to begin with a com- plicated discrete structure, such as DAG, and embed it into a well-behaved continuous structure.
Definition 2 (Spacetime Embedding). Let (X, d, S") and (Y,p. p. S²) be causal (quasi- metric spaces. map J X - y is spacetime embedding if there are constants D. 2 1 and c > 0
4

---

Published as a conference paper at ICLR 2025
such that for each 21, X
(i) Causal Embedding: 21 <² 22 & f(z))= 2 f(22)
2 Mit)eetric Embedding: (((f(z)).
S (2) f
The constant D called the distortion, and is the scale of the spacetime embedding, spacetime embedding X > for which D
is called isocausal.
is the minimal possible distortion This is because D < 1 is impossible and D yields an equality between the rescaled target metric op and the original metric d; i.e. cp(f(x1) f(x2)) = d( (22 for all 21, E X.
Remark 2 (Optimal Distortion). Note that D
Our spacetime embeddings are illustrated Figure 3 We encode causality using the notion of an order embedding from order theory (Davey & Priestley 2002). also used in general relativity (Kro-)
nheimer & Penrose 1967; Sorkin [991] Reid [203;; Henson 2009) Benincasa & Dowker 2010).
jointly with the notion of a metric embedding
to theoretical computation science (Gupta & Gupta et al. 2004) and representation learning (Sonthalia Gilbert.
Hambrusch 1992 Gupta 1999
2020).
B
(a) Spatial Embedding: the ohjective to repli- cate the distance between nodes, counted in min- imal number of hops, with the Euclidean distance on R In the neural spacetime, however, the dis- will be non- oon-Buclidean.
(h) Temporal Embedding: the goal of the causal embedding is to match the directions in the em- bedded graph (direction of red arrows) to the or- der in R with the product order (direction of gray arrows).
Spacetime Embeddings (Definition 2: We illustrate a spacetime embedding the directed graph in Figure into I= Rº² x IR² with 2-space dimensions and time dimensions. Notice that the spatial component of the spacetime embedding not a causal embedding and vice versa.
Figure 3:
3 NEURAL SPACETIMES
Let N E N_ be the dimensionality of the feature vectors Lu, T. E RN associated with nodes u, E V, where V represents the set of nodes the DAG GD = (Ep, V, W).. Fix a space dimension D E N4 and a time dimension T N+. A neural spacetime (NST) is learnable triplet S DE T), where R + P+T is an encoder network, e.g. an MLP,
RD+ x D-
[0, oo) is learnable quasi-metric on R and T D+T + R² is learnable partial order on RT. We implement D and T as two neural networks that process the spatial and temporal dimensions of encoded feature vectors &,, ft def. E(zw), E D+T in parallel.
The encoder network, R + P+T maps the original node feature vectors the input graph the dimensions of space and time used by the NST representation. We employ this mapping as an intermediate Euclidean space upon which to learn the quasi-metric and partial order. The model learns allocate relevant information each dimension through gradient descent, rather than attempting to manually specify which of the original node feature dimensions should correspond to space and time.
To define D, which will be implemented using a variation of the original neural snowflake (see equa- tion 10 from Appendix A.3)). The original neural snowflake, and our upgrade thereof, employs two neural networks: the first represents the metric space as vectorial data in IR and the second perturbs the Fuclidean distance thereon. Together, any finite metric space may perfectly (isometrically) embedded in this manner, whereas only one of the networks alone is not enough; e.g. expander graphs cannot isometrically embedded into any low-dimensional Euclidean space (Kratsios et al. 2023a Proposition 13).
'The symbol D) is also used in other parts of the text to denote the spatial dimensionality of the NST. We stick D here since it standard in the metric embedding literature, but the should not be confused.
5

---

Published as a conference paper at ICLR 2025
We consider the following activation function, J., The activation I,, depends two trainable pa- rameters 8, | > 0. In the spirit of the fractalesque structure of neural snowflakes, s controls whether small-scale distances should be expanded contracted relative to the distance on R.P. Similarly, l controls the large-scale distances of points and dictates whether those should be expanded or con- tracted. See Appendix C.T for extended discussion.
Definition 3 (Neural (Quasi-)Metria Activation). For any s, I >
0, we define the neural (quasi-) metric activation to be the map Ss R - R given for each x E IR by
(x) del. sgg(()) |x1*
if a < 1
sgg(x) |a|'
if
2 2 1
where the sign function sgn returns for a 0 fl x < O.
If s = I then (.) = s1 |r|* and one recovers the key component of the snowflake activation function of Borde & Kratsios (2023) used in the majority of the proofs of its metric embedding guarantees. Note that and l are not required to be coupled in any way.
A neural (quasi-Jmetric is a map D RRT x RD+T +
[0, oo) with iterative representation:
D(uu, 2.) def.
del
Woo (uy-1);
Wy (u--1) for j -.
(3)
sp
(iD)I:D so.ja
(f.)).ll
for each fu, & E IR D+T where the depth parameter J E N.. where the 80, 1a....,,871 4, > 0, and denotes component-wise composition (i.e. the function is applied element-wise, which standard in Deep Learning), weight matrices W,- ID (an invertible positive matrix, Appendix A.2 for j < and W, E (0, Ix all of which have positive entries, and where the absolute value is also applied component-wiss wise. Note that (.)I.D extracts the first D dimensions of the input vector.
Moreover, seek an ordering S on RP+7 so that o e in the poset if and only if their respective embeddings &. and it are ordered in the feature space via S. Our class of trainable orders are parameterized with the following type of neural networks, which we call neural partial orders. Consider a map T D+T + R admitting the iterative representation
T(a.) zj: Ej (1.......)) Vjoay,s, oLR (2j-1)+b5-
(B.)D+1.D4T: (4)
where LR stands for LeakyReLU and o for function composition, with the depth parameter J N₂. weight matrices V; E IF. and bias terms by E R². Also, note that T(œ.) E RT. whereas when applying the subscript T($u). E I. the operation returns the entry of the coordinate embedding at dimension t. At each layer of T we use the (single trainable parameter, = / in equation activation 3, > 0. Moreover, we would like to highlight that D takes both &.. & E R D+T as input to compute distances, whereas T processes inputs independently. Hence, given any such T we define the partial order SJ RD+T given, for each &.. & R by
tu
to T(au): S T(2.),, Vt = = 1, ......,,Z. DTT.
(5)
The next proposition shows that S" always defines a partial order on the time dimensions of D+T for any T. This is formalized by noting that, for any D E N_, the quotient space IR DDD / under the equivalence relation x ~ ã + 21:D = 1 is isomorphic (as a vector space) to RT, Thus, there is no loss in generality in assuming that D = 0.
Proposition 1 (Neural Spacetimes Always Implement Partial Orders). IFT E N4, D = O, and T D+T + ITT admits a representation as equation then SJ is a partial order on IR D+T
See Page 21 for proof.
Just as the neural snowflakes of Borde & Kratsios (023). neural (quasi-)metrics implements a quasi- metric on the spatial dimension Re' in RDFT (ignoring the time dimensions used only to encode causality). A key difference between the two is that our formulation allows for the weighting or discovery of the importance of each spatial dimension, as well as the rescaling of each spatial di- mension individually. Thus, our model in equation 3] enables greater flexibility it departs further from the somewhat Euclidean structure of [orde & Kratsios (202)), which is based on warping a precomputed Fuclidean distance.

---

Published as a conference paper at ICLR 2025
Remark 3 (Comparing Neural Snowflakes to Neural (Quasi metrics in NSTs.). Neural (quasi- Imetrics generalize the non- -on-Euclidean metrics studied in Gozlan (2010 Proposition 1.2) and imple- mented as part of the neural snowflake model in Borde & Kratsios (2023).
This can be of interest in learning theory since it was shown in Gozlan (2010) that these types of distances exhibit favourable concentration of measure properties when measured in 1-Wasserstein distance from optimal transport. The connection to learning occurs due to the technique of [Amit]
al. (2022); Hou et al. (2023); Benitez et al./ (2023); Kratsios al. (2024) whereby one may obtain uniform generalization bounds for Hölder learners through concentration of measure results.
Proposition 2 (A Neural (Quasi- (Quasi-)Metric is a quasi metii on the spatial dimensions). Any D with representation in equation 3 is a quasi-metric on RRD If each W is orthogonal and O < 83, 1 S then DD is metric on RR, Furthermore, T E N4, then 'D is pseudo-quee metric on IR D4T. See page for proof.
3.1 EMBEDDING GUARANTRES
We now present our main theoretical result which is the (global) embedding guarantees for NSTs. Definition 4 (Width). Let (P: <) be a poset. A AS= S P is called an anti-chain if for each u, u E S neither u * nor v * u. The width of (P, is the maximal cardinality of any anti-chain in P.
Note that to model anti-chains with our framework, more than one time dimension needed. This allows our model to represent lack of causal connectivity between nodes that do not share directed path between them in the graph. The result below uses the notion of doubling constant and metric space dimension from fractal geometry, see Appendix A.
Theorem (Universal Spacetime Embeddings). Fix W,N E N., K > O, and let (P,d, S) be a finite causal metric space with doubling constant K, width W, and P del {xy LoEV S CRN. There exists a D E Olog K)), an MLP E IN - RDW, T : RD+W + R with representa- tion equation 4 and D RD+ x RRD+ + [0, x0) with representation equation such that for each In E EP
(i) Order Embedding: I, < xe and only (()) S E(zv).
(ii) Metric Embedding: (oo) S D(E((u)) {xx.) I (Iog((K))) ((),
Moreover, setting D = k, (ii) can be improved to isocausal embedding, i.e. d(zu, U.) ((E(r)), (xx)). In either case, the number of non-zero parameters determining the neural space- time triplet S = (E, is Ö(D + W + +=//" See Seelpage 25 proof.
Theorem guarantees that one never needs more than W time dimension and # P space dimen- sions to have (perfect) isocausal spacetime embedding. However, note that W + (log(# P)) spacetime dimensions are guaranteed to provide an embedding with a very small distortion, which is likely good enough for most practical problems. Theorem [[ extremal, in the sense that it holds for all causal metric spaces. One may, therefore, ask: How much can the result be improved for causal metric spaces with favourable properties?
In analogy with the Minkowski spacetime representations in Law & Lucas (202)). which can ac- commodate directed line graphs, we now investigate when few (at most two) time dimensions are enough to guarantee a causal embedding for a poset. Using Baker et al. (1970). we first characterized posets which admit a spacetime embedding with two time dimensions via their Hasse diagrams.
Proposition 3 (When two time dimensions are not enough). the Hasse diagram of a posel (P. (P.S) not a planar graph. then there is no spacetime embedding E P + BD+W, WWW.W. DD-- X I D++ + [0, 20), T RR DW + R.W with W = 1, See page for proof.
We now improve both the temporal and spatial guarantees of the spacetime embedding in Theo- rem I for the posets characterized by the preceding proposition. To leverage the planar structure of the Hasse diagrams of these posets and thus enhance the spatial component of our spacetime em- beddings, we instead equip any such poset (P. x) with the metric du, defined as the graph geodesic distance on the undirected Hasse diagram of (P.S).
"Since any W, must have only non-negative entries, then if W, is additionally orthogonal, it must be a permutation matrix.
W here is used for time dimensions and not edge weigths.
7

---

Published as a conference paper at ICLR 2025
Theorem 2 (Low-Distortion Spacetime Embeddings in Time Dimensions). Fix k, N.NN- E NN, and let (P, S. du) is k-point poset whose Hasse diagram for (P.S) is planar, P C RN.. There is a ReLU MLP 3 RN + (log(()))+ D (1ogg(()))++ x [o(loghh)++2 + (0) with representa-
tion equation 3 and T (k)) + R² as in equation 4 satisfying: for each Bus Zo E P
(i) Causality: Zu + Te if and only if (x.)) IJ ((xv),
(ūi) Low-Distortion: du (Ta; v.)) S (EE,), (I,)),(( S (0(lo((k3)) (Nu;
The number of parameters in S is O(15/2 log(N) log (k² diam((, ddn)). Proof on pmpee 26
Our training procedure (Section 3.2) focuses on embedding the local structure of directed graphs and is supported by our theoretical guarantees that NSTs are expressive enough to encode the global structure of weighted DAGS. By focusing on local embeddings, trained to embed very large directed graphs, since local distance information is readily available, but global distance information is generally expensive to compute. Interestingly.
neural spacetime model can be
Remark 4 (Local vs. Global NST.). The global and local embeddability of directionaa information equivalent in our case due to the transitivity properties of DAGs and our representation spaces.
For completeness, we compare neural spacetimes to hyperbolic representation in Appendix A.6
3.2 COMPUTATIONAL IMPLEMENTATION
In this section, we provide a discussion on how to bridge the theoretical embedding guarantees presented earlier into computationally tractable model that can be optimized via gradient descent. Further details are provided in Appendix C
Representing graph edge directionality as a partial order in the embedding manifold. Given a weighted directed graph GD = (ED, V, W),, let Tu, Te E R- be the feature vectors associated with the nodes u, V V. which we want to embed as events in these features and maps them to an embedding in the manifold. The edge set En induces a binary non-symmetric adjaceney matrix A. In our case, GD is not any digraph but DAG, hence if Auv 1 = Ara = O. Both entries can only be equal when they are O, Auv = Avn. = O. In the latter case, the nodes may either be causally disconnected, or causally connected but not neighbors. If the input graph does not satisfy these properties our spacetime embedding parametrized by the NST will not be able to faithfully embed the input graph in terms of its edge directionality.
spacetime: S takes as input
Representing graph edge weights as distances in the embedding manifold. Likewise, WD in- duces a distance matrix D with entries Dav being the causal distance between events u, v. Al- though theoretically this could be computed as the shortest path graph geodesic distance for two causality connected and distant u and e (similar to equation [ but for weighted directed graphs, see Appendix D.I), in practice we only optimize for the one-hop neighborhood. In particular, if u = + Due O, if u & a A u E N(u) A u & v + Duv > O. The distance D... is ig- nored otherwise, that is, we do not model the distance between nodes in the original graph that are causally connected but outside the one-hop neighborhood of each other nor do we model the dis- tance between events that are not causality connected (anti-chains). This is in line with the literature on graph construction via Lorentzian pre-length spaces (Law & Lucas 2023). In the case of NSTs, it is achieved using the connectivity Ave as mask in the loss function.
Local geometry optimization and global geometry implications. Note that although we optimize for the one-hop neighborhood of each node only, transivity of the causal connectivity of nodes across hops will be satisfied by definition of the partial order (Remark 4 Additionally, although the partial order between anti-chains is not directly optimized, as the number of time dimensions increases, it is increasingly probable that <T will not be satisfied for nodes not causally connected, as desired. Conversely, there is no guarantee that when directly evaluating the distance between causally connected nodes using 'D we will obtain the graph geodesic distance between nodes. In summary, if Tuu Ty. Zo E N are feature vectors for nodes u, n, w E V, and fu, Lo, Pno E RD+T their & encodings in the intermediate Euclidean space used by the NST, if (ā, ST k,) A (ft, S7 ).w)) = Ru <T Rw. On the other hand, in general D( 2.) + D(E,, F.) = Duo + D Dows and provided that this particular path corresponds to the graph geodesic Duv Dew = do (u, w), but D(E,, ..)) + D(i,, ) + D(i,, The latter inequality is acceptable and not required to faithfully encode the graph edge weights.
Training and Loss Function. Let us use the matrix X E R M to denote the collection of feature vectors for M |V] nodes associated with the DAG, Gp. The NST minimizes the following loss:
8

---

Published as a conference paper at ICLR 2025
Table 1: DAG embedding results. Embedding dimension D= 10.
Metric
Emhedding Dim
Distortion (average :
Max Distortion
Directionality
1.09 1: 0.24
3.18
1.0
||x y0 log(1 + ||x
y1l)
1,02 0.06
1.51
1.0
1.00 0,03
1.24
Seural Spacetmee
1.16 0.45
6.21
1.0
||x y11 log(1 + ||x yll)%.
1.02 0.07
1.75
10
1.00 +: 0.04
1.47
1.0
1.51
1 exp To
-11x==11-11
1.11 + 0144
8.92
1.0
1.01 0.05
1.31
2
2.86 +: 5.22
72.66
0.99
||x 1o + ||x yll)%,a
1,70 2.77
71.09
10
1.21 1,33
38.58
0.99
6.77 133.68
1669.85
0.99
||x 1/1 [og(1 + ||x v
1.70 + 5.21
77.03
0.99
1.19 1.09
25.18
0.99
11.37 1 114.8
1876.54
0.98
1 exp T=
-(1xx-y1-1)
2.49 + 8.72
198.04
0.98
2.49
00
0.99
||x 111 1og(1 + ||x v
-4.33 I. 816.47
10235.71
0.99
288. 1: 9794497
324027.
0.99
9,40 + 2226.84
63968.22 21
0.99
DD
||x Ing(1 + ||x yll)
174.69 + 3637.32
115851 888
0.99
-10.66 739.7I
-183,71 9600.71
39648.66
0.94
1 exp -11x-x11-11 x-
83.04 4313.82
97524.21
0.4
418.26 1 6399.80
150543.73
0.9
LGD (X def. Σ
Σ 0=01
Luv (S(#u) I.): (Auvs Duv)),
(6)
where T. extracts the row feature vector for from matrix X. The goal is to learn appropriate embeddings so that nodes connected by directed edges are represented as causally connected events in the time dimensions of the manifold, and respect the distance Dav induced by the graph weights in
the space dimensions. To do so, we can further divide the loss function into a (causal) distance loss,
CD and a causality loss, C We remind the reader of the definition Lu. 2. BBTT_ Hence the loss can be partitioned into:
def. E(xw), (zx,
def. CD (D(iu; No), (Aum, Duv)) - C (T(iu); T(xx), Aun.. Lux
We dissect the two loss terms. The distance loss for pair of nodes is the mean squared error (MSE) loss between the predicted and ground truth distance, with masking given by the adjacency matrix:
CD
MSE (D(tu, Duv).
(8)
On the other hand, the causality loss (with respect to the one-hop neighborhood) is
T
c
A Lo
Σ SteepSigmoid(T ((())))((()))))))) T(āx):))
(9)
where Lg is function that takes input the expression above and StecpSigmoid(z)) 10e (we omit some details here for simplicity, see Appendix C.3 for details). The loss for two causally connected events u < v in the first neighborhood of each other (Aue = 1) is minimized when &n SJ H. is satisfied (equation 5. If the time coordinates of f., associated with the event all greater than those of d., for u, then all SteepSigmoid activation functions will return x 0.
EXPERIMENTAL RESULTS
Synthetic Weighted DAG Embedding. We generate DAGs (see Appendix D.2 embedded in the 2D plane with associated local distances between nodes given by several metries. We measure the embedding capabilities of NSTs compared to closed-form spacetimes such the Minkowski and De Sitter spaces in Law & Lucas (2023). Although we do not optimize the geometries in the case of the baselines, do use neural network encoder to map points events in the manifolds. We quantify both the average and maximum metric distortion (the ratio between true and predicted distances) following Kratsios et al. (2023b), well as the accuracy of the time embedding. As be

---

Published as a conference paper at ICLR 2025
Table 2: Embedding results for real-world web page hyperlink and gene regulatory networks.
Noural Spacetime
Minkowski
De Sitter
Max Distortion
Max Distortion
Max Distortion
Embeed. Dim
Directioality
Directonality
Directionality
Distortio
Distortion
Distortion
Dataset
2
1.00
D.07
1.31
0.93
1,07
+ 0.70
9.43
0.94
-55
83 + 800145
3950 X98
0.92
Cornell
1.00
0.04
1.08
0.91
1.00
+ 0.00
1.01
0.94
-30.00
= 239.79
203,16
0.94
10
100
0004
1.08
0.94
100 0100
1.00
0.44
0.80 + 176.26
1543.07
0.95
L01
0.30
2.27
0.89
112 1.73
3127
0.90
-0.29 2 51,42
818.10
0.90
Texas
0:01
0.90
1.00
1.0
42.03 795.51
13939 25
0.90
10
1.00
0.00
1.00
0.90
1.01 1: 0.00
1.05
0.90
2.00 + 70.35
1107.00
0.50
1000
0.30
1.07
0.89
5.07
4: 66.99
1410.03
0.90
2.06 2 63.46
1291.31
0.89
Wisconsin
0.89
1.00
0.04
1.19
10.5 27.91
114.24
10
1.00
0.04
1.20
0.89
1.13 + 0.69
16.28
0.90
0.14 4: 213.94
2862 19
0.89
100
0.47
18:34
1.00
105.22
E 85
21228.72
0.9
-53.50 = 1866 6M
56626.97 97
0.92
silico
0.09
1.73
1,00
0.25 54.57
1315.76
0.95
-468
81 = 33021,14
65289 22
0.92
10
100
0.05
1.32
1.00
1.00 = 0.05
3.89
0399
-129.13
= 9625.30
261531.59 59
0.93
2
L.2
0.45
15:37
1.00
-4.55
149.61
438.34
0.97
34.65
2637 75550
119047 23
0.91
E, coli
0.06
2.62
1.00
1.00 = 0.01
1.08
0.98
-2.00
3291,81
130800 59
0.91
10
1000
0.05
L.17
1.00
1.00 +: 0.01
1.11
0.99
-8.20 1 94.57
65296
0.91
D:34
10.18
1.00
-2.18 17537
13121
55.16
1900019
16027X
S. cerevisine
1.00
0.07
1.63
1.00
1.04 da 2:25
63.17
0.98
22.60
=: 1175.67
63086.55
0.90
10
1.00
0.05
1.57
1,00
1.DI +: 0.02
1.39
0.99
-121.17
+ 7550.16
84724.25
0.91
in Table D we are always able to embed edge directionality (0 for no edges embedded correctly, 1 for all edges embedded correctly). In terms of metric distortion, as the embedding dimension increases, both average and maximum distortion decrease. NSTs are particularly good at retraining low distortions in dow-dimellional embedding spaces. See Table 9 more results.
Real-World Network Embedding. We test our approach on real-world networks. In Table 2 we present results for the Comell, Texas, and Wisconsin (WebKB) datasets (Rozemberczki et al.) 2021). which are based on webpages represented as nodes and directed hyperlinks between them. All the nodes have bag-of-word features that we use as input of the neural spacetime encoder. The neural partial order encodes the hyperlink directionality between websites, and the neural (quasi-)metric learns the connectivity strength as the cosine similarity between connected webpage features. We achieve very low distortions, showcasing the embedding capabilities of our network. Note that, from a metric learning perspective, real-world datasets are generally less challenging than the metrics presented in [ which we chose to be particularly unconventional on purpose. In terms of the time embedding, we manage to mostly encode directionality; however, these datasets are not pure DAGs since they contain some directed cycles, so it is not possible to embed them perfectly. We also work with real-world gene regulatory network datasets (Marbach al. 2012) in line with spacetime representation learning literature (Law & Lucas 2023) Sim et al. (021). We achieve good spatial and causal embeddings for the In silico, Escherichia coli, and Saccharomyces cerevisiae datasets, see Table 2 Experimental details and hyperparameters for all setups can be found in Appendix D Additionally, we present tree (spatial only) embedding experiments comparing neural snowflakes to neural (quasi-)metrics in NSTs, as well as hyperbolic neural networks (HNNs), in Appendix D.]
5 CONCLUSION
We have introduced the concept of neural spacetimes, a computational framework utilizing neural networks construct spacetime geometries with multiple time dimensions for DAG representa- tion learning. We decouple our representation into a product manifold of space, equipped with a quasi-metric, and time, which captures causality via partial order. We propose techniques to build, optimize, and stabilize artificial neural networks with fractalesque activation functions, ensuring the learnability of valid geometries. Our main theoretical contributions include global embeddability guarantee for posets into neural spacetimes, with embeddings being causal in time and asymptot- ically isometric in space. We demonstrate the efficacy of our approach through experiments on synthetic metric DAG embedding datasets and real-world directed graphs, showcasing its superior- ity over existing spacetime representation learning methods with fixed closed-form geometries.
Limitations. Our guarantees are restricted to embeddings for DAGS rather than arbitrary digraphs. We also find that, from an optimization perspective, it is easier to optimize the geometry locally rather than globally. This limitation is computational; as the number of nodes in the DAG grows, it becomes increasingly challenging to compute the ground truth shortest- path geodesic distance and the global causal structure between nodes, which are used as ground truth for training. However, all our theoretical guarantees apply both globally and locally. Additionally, the local transitivity of causal connectivity will implicitly hold globally, even when performing local optimization only.
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
We believe that the potential societal consequences are minimal and do not require specific high- lighting at this time. We commit to ongoing awareness of the broader implications of our work and will remain vigilant in assessing any future societal impacts that may emerge our theoretical framework applied practical settings.
ACKNOWLEDGMENTS
The authors thank James Lucas and the anonymous reviewers for helpful feedback on early versions of this manuscript. M. Bronstein acknowledges this research is partially supported by the EPSRC Turing AI World-Leading Research Fellowship No. EP/X040062/1 and the EPSRC AI Hub on Mathematical Foundations of Intelligence: An "Erlangen Programme" for AI No. EP/Y028872/1. X. Dong acknowledges support from the Oxford-Man Institute of Quantitative Finance and the EP- SRC (EP/T023333/1). A. Kratsios acknowledges financial support from an NSERC Discovery Grant No. RGPIN-2023-04482 and No. DGECR-2023-00230.
REFERENCES
Ittai Abraham, Yair Bartal, and Ofer Neiman. Local embeddings of metric spaces. In Proceedings of the thirty-ninth annual ACM Symposium on Theory of Computing, pp. 631-640, 2007.
Ittai Abraham, Amoll Filtser, Anupam Gupta, and Ofer Neiman. Metric embedding via shortest path decompositions. SIAM Journal on Computing, 51(2):99-331, 2022.
Beatrice Acciaio, Julio Backhoff- Backhoff-Veraguas, and Anastasiia Zalashko. Causal optimal transport and its links to enlargement of filtrations and continuous-time stochastic optimization. Stochastic Processes and their Applications, (30(5):2918-9955) 2020.
Beatrice Acciaio, Anastasis Kratsios, and Gudmund Pammer. Designing universal causal deep learn- ing models: The geometric (hyper) transformer. Mathematical Finance, 34(2):671-735, 2024.
Ron Amit, Baruch Epstein, Shay Moran, and Ron Meir. Integral probability metrics pac-bayes bounds. Advances in Neural Information Processing Systems, 35:3123-3136,, 2022.
Alexandr Andoni, Assaf Naor, and Ofer Neiman. Snowflake universality of wasserstein spaces, Ann. Sci. Éc. Norm. Supér 516)):657-700, 2018
Julio Backhoff-Veraguas, Daniel Bartl, Mathias Beiglböck, and Manu Eder. All adapted topologies are equal. Probability Theory and Related Fields, 178:1125-1172 2020.
Kirby A. Baker, Peter C. Fishburn, and Fred S. Roberts. A new characterization of partial orders of dimension two. Ann. New York Acad. Sci., 175:23-24 22,2,,44,111 1970. ISSN 0077-8923,11499-66
Daniel Bartl, Mathias Beiglböck, and Gudmund Pammer. The wasserstein space of stochastic pro- cesses, arXiv preprint arXiv:2104, 142455 2021.
John Beem, Paul E Ehrlich, and Kevin L Easley. Global lorentzian geometry. Routledge, 1996.
Dionigi MT Benincasa and Fay Dowker. Scalar curvature of causal set. Physical review letters, 104(18):181301 2010.
J Benitez, Takashi Furuya, Florian Faucher, Anastasis Kratsios, Xavier Tricoche, and Maarten V de Hoop. equation. arXiv preprint arXiv:2301. 1559, 2023.
risk bounds for neural operators with applications to the helmholtz
Haitz Sáez de Ocáriz Borde and Anastasis Kratsios. Neural snowflakes: Universal latent graph inference via trainable latent geometries. In The Twelfth International Conference on Learning Representations, 2023.
11

---

Published as a conference paper at ICLR 2025
Haitz Sáez de Ocáriz Borde, Alvaro Arroyo, Ismael Morales López, Ingmar Posner, and Xi- aowen Dong. Neural latent geometry search: Product manifold inference via gromov-hausdorf:- hausdooffff informed bayesian optimization. In Seirrt- Conference on Neural Information Processing Systems, 2023a. URL /tttps://openeeeee
d=Gi 5638d7 60.
Haitz Sáez de Ocáriz Borde, Anees Kazi, Federico Barbero, and Pietro Lio. Latent graph inference using product manifolds, In The Eleventh International Conference on Learning Representations, 2023b. URL httpp://ppppeeeeeeeeets/ net.:/wwweeeeeeeeee www.:trrtteoeeeeeo/eo/oa id=
B7n Rqz
Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel Math., 56(2): 222 230, 1986. ISSN 0021-2172. doi: 10.1007/BFF22666225 htttt:tt:://de //dii. org/1C. I0C7/B80276111
Annegret Burtscher and Leonardo Gaveia-Heveling. Time functions lorentzian length spaces, In Annales Henri Poincaré, pp. 1-40. Springer, 2024.
Alex Chandler. On Thin Posets and Categorification. ProQuest LLC, Ann Arbor, MI, 2019. ISBN 178-1392-60821-0. Thesis (Ph.D.)-North Carolina State University.
Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Local global tradeoffs in metric embeddings. SIAM Journal on Computing, 396))224872251,, 2010.
B. A. Davey and H. A. Priestley. Introduction lattices and order. Cambridge University Press, New York, second edition, 2002. ISBN 0-511-85117 doi: 10.1017/CB0978051 1809088. URL
https://do:: /ttp:///000.11110001111111011110
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Neural Information Processing Systems, 2016.
URL httphhtpt//ppppt wtw.pppisssmmmmiissccsseocoe crtpaa.rrrrrroorr.1.10000000000.
Tristan Deleu, António Góis, Chris Chinenye Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow net- works. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022. URL https:
//openreview htt.://wwwe...oooommmmdeeeeeeeee
R. Dilworth. decomposition theorem for partially ordered sets. Ann. of Math. (2), 51:161- 166, 1950. ISSN 0003-486X. doi: 10,2307/1969503. URL http:::t///// wor.o.oorr/...... 0tgg/1..20077 23077 1969503
Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, Cambridge, 2009. ISBN 978-0-521- 88427-3. doi: 10. 00.10177C8809780511111177/ TRL/nttps:///ci-orr libaccess...... lib. Incmaster.c ca /tt.://..01111/00077111115111111
Anna Dyubina and Iosif Polterovich. Explicit constructions of universal R-trees and asymptotic geometry of hyperbolic spaces. Bull. London Math. Soc., 33(6):727-734, 2001. ISSN 0024-
6093,1469-21200 doi: 10. 00111228004499000848, URL 1112/ $0024609301008440
Stephan Eckstein and Patrick Cheridito. Optimal transport and wasserstein distances for causal models. arXiv preprint arXiv:2303. 14085, 2023.
Stephan Eckstein and Gudmund Pammer. Computational methods for adapted optimal transport. The Annals of Applied Probability, 34(LA))675-113, 2024.
Michael Elkin and Ofer Neiman. Near isometric terminal embeddings for doubling metrics. Algo- rithmica, 83(11):3319-333 3337,, 2021.
Alexandros Eskenazis, Manor Mendel, and Assaf Naor. Nonpositive curvature is not coarsely uni- versal. Inventiones mathematicae, 217:833-886. 2019.
Stefan Felsner, Vijay Raghavan, and Jeremy Spinrad. Recognition algorithms for orders of small width and graphs of small Dilworth number. Order, 20(4):351-64, 2003. ISSN 0167-8094,1577 9273. doi: 10. 1O23//:ODDDEE.... WWW.RRDE..000044009990999990 9b..4................... URL / B: ORDE. 0000034 09944499999999999 fbb
12

---

Published as a conference paper at ICLR 2025
Arnold Filtser. A face cover perspective to e' embeddings of planar graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1945-1954 SIAM, 2020.
Robert W. Floyd. Algorithm 97: Shortest path.
Commun. ACM, 5(6):44, jun 1962. ISSN
0001-0782. doi: 10.1145/367766.366
URL htt.:tpee//oo...ooo/00...1151/52
368168
Brendan Fong and David I. Spivak. An invitation to applied category theory, Cambridge Uni- versity Press, Cambridge, 2019. ISBN 978-1-108-71182-11 978- 978-1-108-48229-5. 9781 108668804. URL in compositionality.
doi: 10.1017/ Seven sketches
Octavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks, 2018.
Robert Geroch. Domain of dependence. Journal of Mathematical Physics, 11(2):437-44,, 1970.
S Gershgorin. Uber die abgrenzung der eigenwerte einer matrix. lzw. Akad. Nauk. USSR. Oid. Fiz-Mat. Nauk, 7:749-754, 1931.
Francesco Di Giovanni, Giulia Luise, and Michael Bronstein. curvature-aware graph embedding, 2022a.
Heterogeneous manifolds for
Francesco Di Giovanni, Giulia Luise, and Michael M. Bronstein. Heterogeneous manifolds for curvature-aware graph embedding. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022b.
Lee-Ad Gottlieb and Robert Krauthgamer. Proximity algorithms for nearly doubling spaces. SIAM Journal on Discrete Mathematics, 2754):175-1176) 2013.
Nathael Gozlan. Poincaré inequalities and dimension free concentration of measure. Ann. Inst.
Henri Poincaré Probab. Stat., 46(3):708-739, 2010. ISSN 0246-0203,1778-7011
Guella, V. A. Menegatto, and A. Peron. extension of theorem of Schoenberg to products of spheres. Banach J. Math. Anal., 10(4):671-685, 2016.
Madhu Gunasingam and Ting-Kam Leonard Wong. Adapted optimal transport between gaussian processes in discrete time. arXiv preprint arXiv:2404.06625 2024.
A. Gupta. Embedding tree metrics into low-dimensional Euclidean spaces. Discrete Comput. Geom., 24(1):105-116, 2000.
Ajay K Gupta and Susanne Hambrusch. Load balanced tree embeddings. Parallel computing, 18 (6):595-614, 1992.
Anupam Gupta. Embedding tree metrics into low dimensional euclidean spaces. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 694-700, 1999.
Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, trees and 11 -embeddding of graphs. Combinatorica, 24(2):233-26) 2004.
Sariel Har-Peled and Manor Mendel. Fast construction of nets in low dimensional metrics, and their applications. In Proceedings of the twenty-first annual symposium on Computational geometry, pp. 150-158, 2005.
Joe Henson. The causal set approach to quantum gravity. Approaches to quantum gravity: Toward new understanding of space, time and matter, pp. 393-413,, 2009.
Songyan Hou, Parnian Kassraie, Anastasis Kratsios, Andreas Krause, and Jonas Rothfuss. Instance- dependent generalization bounds via optimal transport. Journal of Machine Learning Research, 24:1-50, 2023.
Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs, 2021. URL
httpps:/eaa wwwpiiioorrg/aaa www.//gg/ss..... 2205 00687
13

---

Published as a conference paper at ICLR 2025
Thomas R Hurd et al. Contagion!: Systemic Risk in Financial Networks, volume 42. Springer, 2016.
Yong-Woo Woon Kim. Pseudo quasi metric spaces. Proceedings of the Japan Academy, 44(10):1009 1012, 1968.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017. URL https:
//openreview.. wttp://oorumiiidsaataaaaa...
Anastasis Kratsios, Valentin Debarnot, and Ivan Dokmanić. Small transformers compute universal metric embeddings. J. Mach. Learn. Res., 24:Paper No. [170], 48, 2023a. ISSN 153--4435,1533-
7928.
Anastasis Kratsios, Ruiyang Hong, and Haitz Sáez de Ocáriz Borde. Capacity bounds for hyperbolic neural network representations of latent tree structures. arXiv preprint arXiv:2308. 09250, 2023b.
Anastasis Kratsios, A Martina Neuman, and Gudmund Pammer. Tighter generalization bounds on digital computers via discrete optimal transport. arXiv preprint vrXiv:2402.05576. 2024.
R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: a new embedding method for finite metrics. Geom, Funct. Anal., (5(())839--3) 858, 2005.
Robert Krauthgamer, James R Lee, Manor Mendel, and Assaf Naor. Measured descent: A new em- bedding method for finite metrics. In 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 434 443. IEEE, 2004.
Erwin Kronheimer and Roger Penrose. On the structure of causal spaces. Mathematical Pro- ceedings of the Cambridge Philosophical Society, volume 63-2, pp. 481 4-11. Cambridge Univer- sity Press, 1967.
Daniel Kršek and Gudmund Pammer. General duality and dual attainment for adapted transport. arXiv preprint arXiv:2401.11958 2024.
H Künzi. Complete quasi-pseudo-metricc spaces. Acta Mathematica Hungarica, 59(1-2):1211166 1992.
Mare Law. Ultrahyperbolic neural networks. Advances in Neural Information Processing Systems, 2021.
Mare T. Law and James Lucas. Spacetime representation learning. In The Eleventh International Conference on Learning Representations, 2023, URUhttts:://penneeetttt ///////eeeew..eee///eeoeeeeeee
[d=gV_r MoVMMrrhajo
Marc T Law and Jos Stam. Ultrahyperbolic representation learning. Advances in Neural Information Processing Systems, 2020.
Enrico Le Donne, Tapio Rajala, and Erik Walsberg. Isometric embeddings of snowflakes into dinie-admennional Banach spaces. Proc. Amer. Math. Soc., 146(2):685 693, 2018. ISSN 0002- 9939, 9939,1088-44 1088-088822 doi: 10. 00.1090/pro/113778 URL httph:ttp///cc...mm doi wtt.::/....................0....
13778
Derek Lim, Haggai Maron, Mare T. Law, Jonathan Lorraine, and James Lucas. Graph metanetworks for processing diverse neural architectures. In The Twelfth International Conference on Learning Representations, 2024. URL https:://// ptttps://pperrevviee
net/ http://fommmmmommoikpppa..aa
Yuan Lu, Haitz Sáez de Ocáriz Borde, and Pietro Lio. AMES: differentiable embedding space selection framework for latent graph inference. In NeurlPS 2023 Workshop on Symmetry and Ge-
ometry in Neural Representations, 2023. URL httpp::/ htttss://ppenzeveew.co net wtwp://wwwwweeteeeeueeuueeeeeeee fortmiirddiid
t t.TrggTnjjr
Hiroshi Machara. Euclidean embeddings of finite metric spaces. Discrete Mathematics, 313(23): 2848-2856, 2013.
14

---

Published as a conference paper at ICLR 2025
Daniel Marbach, James Costello, Robert Küffner, Nicole Vega, Robert Prill, Diogo Camacho, Kyle Allison, Andrej Aderhold, Richard Bonneau, Yukun Chen, James Collins. Francesca Cordero, Martin Crane, Frank Dondelinger. Mathias Drton, Roberto Esposito, Rina Foygel, Alberto de la Fuente, Jan Gertheiss, and Ralf Zimmer. Wisdom of crowds for robust gene network inference. Nature Methods, 9:796-804, 07 2012. doi: 10. 10.1033/mmeth.200 2016.
Jiří Matoušek. On embedding trees into uniformly convex Banach spaces. Israel J. Math. 114:221- 237. 1999. ISSN 0021-2172.1155-885777 -811. 0xg/10.1007/B80275555
doi: 10.1000/BBF02885579 URL https: //doi.
Assaf Naor and Ofer Neiman. Assouad's 's theorem with dimension independent of the snowflaking. Rev. Mat. Iberoam., 28(4):1123-1142 2012. ISSN 0213--233,,233--6666 doi: 10.4171/RMI/ 706.
110 4171/RM RMT /706
Ofer Neiman. Low dimensional embeddings of doubling metrics. Theory of Computing Systems, 58: 133-152, 2016.
Piotr W. Nowak. Coarse embeddings of metric spaces into Banach spaces. Proc. Amer. Math. Soc., 133(9):2589-2599) 2005. ISSN 8002-9939,10885 1088-668......
Chris J Oates, Jim Q Smith, and Sach Mukherjee. Estimating causal structure using conditional dag models. Journal of Machine Learning Research, 17(54):1-23, 2016.
Sofiya Ostrovska and Mikhail I Ostrovskii. On embeddings of locally finite metric spaces into 1p. Journal of Mathematical Analysis and Applications, 474(1):666 673166666636,66 2019.
Satish Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the Fifteenth Annual Symposium Computational Geometry (Miami Beach, FL, 1999), pp. 300-306. ACM, New York, 1999. doi: 10. 10.1145/304893.304998 URL https:
//doi. org/ 10. 45/3044933343 304 983
David Reid. Manifold dimension of a causal set: Tests in conformally flat spacetimes. Physical Review D, 67(2):22403, 2003.
Garry Robins, Tom Snijders, Peng Wang, Mark Handcock, and Philippa Pattison. Recent devel- opments in exponential random graph (p*) models for social networks. Social networks, 29(2): 192-215, 2007.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
Rik Sarkar. Low distortion delaunay embedding of trees hyperbolic plane. In International symposium graph drawing, pp. 355 336-366. Springer, 2011.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009. doi: 10.1 200.. 200.205500.0005655....
I. J. Schoenberg. Positive definite functions on spheres. Duke Math. J., 9:96-108, 1942.
Stephen Semmes. On the nonexistence of bilipschitz parameterizations and geometric problems about a so-weights. Revista Matematica Iberoamericana, 12(2):337-410, 1996.
Ryohei Shimizu, YUSUKE Mukuta, and Tatsuya Harada. Hyperbolic neural networks++. In In- ternational Conference on Learning Representations, 2021. URL httt:ps:///peereiiieee
Aaron Sim, Maciej Wiatrak, Angus Brayne, Páidí Creed, and Saee Paliwal. Directed graph embed- dings in pseudo-riemannian manifolds. In International Conference on Machine Learning, 2021. URL https:://aappa www.ppiiseenmnnsseecceecc htt.:///.........oooooa33333331.
Rishi Sonthalia and Anna Gilbert. Tree! am no tree! i am a low dimensional hyperbolic embedding. Advances in Neural Information Processing Systems, 33:845-856, 2020.
15

---

Published as a conference paper at ICLR 2025
Rafael D Sorkin. Spacetime and causal sets. Relativity and gravitation: Classical and quantum, pp- 150-173, 1991.
Johannes Textor, Benito Van der Zander, Mark Gilthorpe, Maciej Liškiewicz, and George TH Elli- son. Robust causal inference using directed acyclic graphs: the package 'dagitty.. International journal of epidemiology, 4586):1887-189, 2016.
Jeremy T Tyson and Jang-Mei Wu. Characterizations of snowflake metric spaces. Annales Fennici Mathematici, 30(2):31--336, 2005.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018. URL/atttss:/opeereeiii de
Qinglan Xia. The geodesic problem in quasimetric spaces. J. Geom. Anal.. 19(2)452-479,
2009. ISSN 1050-6926.
URL https: /tttps:/doi-orrg doi: 10.1007/s 120000//22222000--999900000 C08 9065-4
1 Libaccess. 1 1ib. www.mter........................ ca 10000000000 10000000022000
Tianlin Xu, Li Kevin Wenliang, Michael Munn, and Beatrice Acciaio. Cot-gan: Generating sequen- tial data via causal optimal transport. Advances neural information processing systems, 33: 8798-8809, 2020.
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. DAGs with NO TEARS: Con- tinuous Optimization for Structure Learning. In Advances in Neural Information Processing Sys- tems, 2018
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11 11168-11176, 2021.
16

---

Published as a conference paper at ICLR 2025
A ADDITIONAL BACKGROUND
In this section, we discuss relevant background on the dimension of metric space and invertible matrices, which are used as part of our proofs in Appendix B We also review the original neural snowflake model, -ieudd-ne manifolds, Lorentzian manifolds, and spacetimes in physics. Additionally, we provide an extended discussion on past literature spacetime representation learn ing in the context of machine learning, and compare neural spacetimes to hyperbolic spaces.
A.1 DIMENSION AND SIZE OF METRIC SPACES
The doubling constant in fractal geometry quantifies the complexity of a metric space by indicating how many smaller balls are needed cover a larger ball. is related to the Assouad dimension and other fractal dimensions. A small doubling constant suggests low fractal dimension, while large constant indicates a higher fractal dimension. This constant helps analyze self-similarity in fractals by providing scale- inverinvariaant description of the space.
Our quantitative results use the following fractal notion of dimension/size
metric space.
Definition 5 (Doubling Constant). The doubling constant K Z of metric space (X, d) is the smallest integer k 2 1 for which the following holds: for every center E X and each radius r >> O, every (open) ball (xx,r)
def. {u X d(x, u) < r} can be covered at most (open) balls of radius r /2; i.e., there exist I1,..., IK E X such that B(x, r) S U B(z,, r/2).
By this definition, K is the smallest possible value of & that satisfies the covering condition for all X and all > 0. Note that every finite metric space, such as every weighted graph with the shortest path/geodesic distance, has finite doubling constant. example, if X finite and has at least two points, then K >
The size of a metric space can also be quantified by its diameter and its separation. These respec- tively quantify the maximal and minimal distances between points therein.
Definition 6 (Diameter). Let (X, d) be metric space. The diameter of (X, d) is defined to be diam X, d) def supx,aex d)r,
Definition 7 (Separation). Let (X, d) be a metric space. If X has at-least two points, then its separation is defined be sep(X, d) del inf in 248 d(x, otherwise sep(X, d) del
A.2 INVERTIBLE POSITIVE MATRICES
We employ square matrices that both invertible and have positive entries for constructing neural quasi-metric. These matrices guarantee that our snowflake produces trainable quasi-metrics, allowing the implemented distance function to distinguish between points (i.e., identify when two vectors are equal).
Definition 8 (Invertible Positive Matrices 1t. Let D E N4. ADX x D matrix W is invertible and positive if it can be represented as
W AID + W
where X > O, W is arbitrary D x D matrix, and denotes entrywise absolute value applied to the matrix W. The set of all such D x D invertible positive matrices W is denoted by 1t
In Appendix B we demonstrate that all matrices D are invertible and preserve [0, oo) under matrix multiplication
A.3 NEURAL SNOWELAKES
Neural spacetimes build on the neural snowflake model for weighted undirected graph embedding. Here, describe the original construction in Borde & Kratsios 2023
Neural Snowflakes. Neural snowflakes leverage quasi-metric spaces and implement a learnable
adaptive geometry || Eelly
def. f(1 Bxll), where S.. f. DRD In particular, it is map
17

---

Published as a conference paper at ICLR 2025
f: f0 + 10, 00), with iterative representation
f()) = /jj 1+tpl
Jj Bj Wagshh (A)
for -,...,
(10)
Ug
where for j = I....,JJ. J. Aj a dj x dj-1 matrix, Bj is a d, x dy-matrix, and C is a 3 x matrix all of which have non-negative weights and at least one non-zero weight. Furthermore, for j = =;,..., JJ.0- < Oj I 1,0 1.0%. by I 1, di...., d, E N4. and dg = =1 d,. Also, E R. Note that p controls the relaxation of the triangle inequality (C 2²) and that for p f O, the neural snowflake is a quasi-metric. The input to the neural snow flakee denoted as u, represents the Euclidean distance between &. and f... This value serves as an intermediate representation within the neural snowflake, which is subsequently warped. In principle, u need not be the Euclidean distance. In the original neural snowflake implementation, Va.b
>> [0, oc) is a tensorized trainable activation function which sends any vector u E RR, for some K N+. to the K matrix (aa,((u) whose htth row is
(ba,(uu) del. (1 e---l-lull |ux/" log(1 |ux (mx)))),
(11)
with 0 < and 0 < < being trainable. Such construction provides universal graph embed- ding guarantees for weighted undirected graphs (Borde Kratsios) 2023). In this work, we will generalize this learnable adaptive geometry formulation to directed graphs borrowing ideas from spacetimes and pseudo- pseudo-Riemande Riemannian manifolds.
A.4 PSECDO-RIEMANNIA MANIFOLDS AND LORENTZIAN SPACETIMES
Next, discuss Sneudo-Riemannice manifolds and spacetimes, from which we draw inspiration for our neural spacetime construction (Section 3 Our framework generalizes neural snowflakes and their weighted undirected graph embedding properties to also incorporate causal connectivity and graph directionality. In other words, they implement an isocausal trainable embedding.
manifolds are a generalization of Riemannian manifolds where the metric tensor is not constrained to be positive definite. A d-dimensional pseudo-Riemannian manifold is smooth manifold M equipped with a pseudo-Riemannian metric g. Formally, a pseudo- Riemanniin metric tensor is smooth, symmetric, non non-degenerate bilinear form (called a scalar product) defined on the tangent bundle TM (disjoint union of all tangent spaces). The metric tensor each point E M is denoted by 9r- The metric assigns to each tangent space T,M signature (+, t..... +). In particular, the tangent space T, T,M admits an orthonormal basis (el, 02,.... ea) that satisfiss Wi {1....,d} ,d, Ip (e,, e,) = +1. If gp (e,, e,) = 1 for all i, then M is a Riemannian manifold, its metric tensor is positive definite, and its metric signature is (+, +)).
(p(e,,
Lorentzian manifolds are subset of sseudo-Riemanniaa manifolds with a specific metric signa- ture, typically denoted as (-,+, +,..,,, or (+: ,,,.,,-) In our case, we define distances between causally connected events to be positive, and hence adopt the second sign convention. With this convention, a nonzero tangent vector v of Lorentzian manifold is called causal it satisfies gp (p(v,v) 0, and it is called chronological if (V, v) O.
Spacetimes.
The definition of a spacetime in general relativity varies depending on the author. Spacetimes
subset of Lorentzian manifolds often defined that they are equipped with causal structure (Law & Lucas 2023). Some spacetimes are called globally hyperbolic (Geroch) 1970). Global hyperbolicity ensures that the spacetime possesses well-defined causal structure, meaning there are no closed timelike curves (CTCs) and every inextendible causal curve intersects every Cauchy surface (a spacelike haclkeeeyyppe hypersurface that slices through the entire manifold exactly once). This property allows for the deterministic evolution of physical fields and particles forward in time. In mathematical terms, if there exists smooth vector field V on M such that 9p (V(p), V(p) > for all M, then the Lorentzian manifold is called a spacetime and it contains causal struc- ture. 4-dimensional spacetimes with signature +,,++ or (+, -, -, -,,------- physical world in general relativity. Spacetimes can exhibit various geometries, from flat Minkowski spacetime (used in special relativity) to curved spacetimes that account for gravitational effects pre- dicted by Einstein's 's field equations. In summary, spacetime often refers Lorentzian manifold that additionally satisfies certain physical and causal conditions. We refer the reader to Beem et al. (996)) for details.
are used to model the
18

---

Published as a conference paper at ICLR 2025
Relation to Neural Spacetimes. Neural Spacetimes adaptive geometry aiming to leam, in a differentiable manner, a suitable embedding in which nodes in a DAG can be represented as causally connected events. Although Neural Spacetimes (Section B draw inspiration from the con- cepts above-separating space and time into different dimensions and capturing causal connectivity between events strictly speaking, Neural Spacetimes utilize higher time dimensions (T > 1) than classical spacetimes used to model the physical world. Moreover, they also incorporate a quasi- metric to model distance in the space dimensions, which relaxes the smoothness and other require- ments inherent to pseudo- Riemannian metrics.
A.5 RELATED WORK ON SPACETIME REPRESENTATION LEARNING
Related work in the machine learning literature that considers ggeudo-Riemanee manifolds with multiple time dimensions includes ultrahyeeboolic representations (Law & Stam 2020 Law 202T).
Ultraypeebolicc geometry is a generalization of the hyperbolic and elliptic geometries to pseudo- Riemannian manifolds. However, the works Law & Stam (2020); Law (2021) mostly focus on the optimization of such representations, they only consider undirected graphs and do not consider partial ordering.
Spacetime representation learning (Law & Lucas 2023) considers Lorentzian spacetimes (i.e. with one time dimension) to represent directed graphs, Following the formalism in Appendix [A.4 with metric signature (+, ...... -), and noting z. the logarithmic map of T. at Zu. they consider that there exists an edge from u to v iff 9r., (F,, t) > 0 and 0 < Ix., (TaTee TaTe) < <E where t is an arbitrary tangent vector that defines the future direction and e >> 0 is hyperparameter that defines the maximal length of the geodesic from Tu to T. to draw a directed edge. The hyperpa- rameter & allows them to avoid connecting u all the descendants of v. Their work is limited to the optimization of embeddings (i.e. not neural networks). We draw inspiration from Law & Lucas) (2023) but consider multiple time dimensions in framework that is easy optimize for neural networks. Our local geometry optimization framework also allows us to ignore the hyperparameter e, which necessary when there is only one time dimension. In our case causality is controlled by the multi-dimensional neural partial order S instead.
Also, note that all the previous works discussed above require selecting an appropriate manifold to model the embedding space priori. Our work, on the other hand, not only optimizes the location of points in space but also the manifold itself. In other words, our framework models a trainable geometry.
A.6 HYPERBOLIC SPACES AS COMPARED TO NEURAL SPACETIME EMBEDDINGS
Hyperbolic geometry has been shown to be relevant for describing undirected graphs without cycles, which are called trees. Indeed, in Sarkar (011). it was shown that these trees can be algorithmically embedded into hyperbolic space with low distortion. Additionally, Ganea et al. (2018) constructed class of hyperbolic neural networks (HNNs) which can exploit trees represented in these spaces, and Kratsios al. (203b)) demonstrated that finite trees can indeed be embedded with arbitrarily low distortion. However, in Borde et al. (2023a). it was shown that an isometric embedding is not possi- ble, except "infinity" in the hyperbolic boundary of such a space Dyubina & Polterovich (2001) (which lies outside the manifold itself). The issue arises because hyperbolic space is a Riemannian manifold, and thus, it is incompatible with the branches in the tree itself.
This is not the case for the fractal geometry implemented by the neural spacetime and neural snowflake of Borde & Kratsios (2023). Indeed, in (Maehara) 2013] Theorem 3.6), it was shown that any finite tree can be isometrically embedded in Fuclidean space IRd, for d large enough, but with the "snowflaked" Fuclidean distance between any two points xr y E Rdd given by || yll* where 1/2. Since neural spacetime and neural snowflake can implement such fractal geome- tries, they are better suited to the geometry of trees.
In this paper, we propose framework to represent DAGs that do not contain directed cycles. How- ever, the underlying undirected graph of DAG can contain cycles. This is for example the case for the DAG containing four nodes {v4 ).4 that satisfy only the following partial orders: 1/1 5 12 & Ma and 24 & 1/3 & V4, without causality relation between 122 and 1/3 The underlying undirected graph an undirected cycle v1, 12, u4, V33 V1, which is not appropriate for hyperbolic geometry.
19

---

Published as a conference paper at ICLR 2025
B PROOFS
B.I PROPERTIES OF NEURAL SPACETIMES
Proof of Proposition Fix T N4 and set D 0. Let T RDT Rd be mapping with representation equation 4 We define the relation
T(x); S T(y): for each I..., We now show that T a partial order on P+T by verifying the three required properties.
y if and only if
Reflexivity: For any E IR D+T we have T(x): S T(x); for every t = ....., T. Thus, I S Antisymmetry: Suppose v, y E DDT satisfy
and y 2 x.
Then, for every t = 1,,,..., T,
T(x); S TV(), and T(y) T(x)s
which implies that T(x), = T(y), for all t. Since each matrix Vj E I is injective (as noted in equation [12), and both the leaky ReLU function and the affine shifts injective, the composition is injective. Therefore, T(x) = TTy) implies that x y.
Transitivity: Let 2. U, D+T be such that
5 Then, for every -,..... T. we have
y and y V²²². 2.
T(x) TTy) and T(d) S T(2)s-
By the transitivity of the standard order on R, follows that T(x), S T()), for all t. Hence, 2.
Since S7 is reflexive, antisymmetric, and transitive, it is partial order on R+T
Proof of Proposition 2
Comment: The main challenge in this proof is showing that 'D separates points in IR.;; that is, for any x. y TRD we have D(x, y) 0 if and only x x== ==== y. Note that in the main text takes as input the spatial coordinates of the Euclidean embeddings Zus Pr BDTT instead, but avoid this notation here for simplicity.
Symmetry of D: The map D is symmetric since
(o (x) so. (w)) = (10.0.10 (1) - so (z)
meaning that the map u + is symmetric. Consequentially, D is symmetric.
Non-Negativity D:
Since each of the matrices Wi...., W, have non-negative entries then they map [0, oc) to itself. To see this note that for any d, E N, if u E [0, oo) W E RdxD and (W) 2 for each i= 1...., D and k- = =1... 1...., d then: for .,..., D we have that
(Wu); Σ Weyur 2
Thus, D(x, y) 2 for each x, E R...
Case I: D Separates Points if 0: Suppose that T 0; otherwise we will show that D does not separate points.
It is sufficient to show the result for J with the general case following directly by recursion. Consider the map D D+T x DDT + [0, oo) with iterative representation given equation
ie.. for each x, y R D+T RD
D(s, y) def.
WJ (uz):
20

---

Published as a conference paper at ICLR 2025
Uj def Way (u--1)
for = 1, ,,....,J
def. 0 to (x) so.to (t))
Ug
where, we recall equation applied pointwise)
2 which states that for each 8, and a E IR (the activation function
(2)
def.
(g)(()) |a]*
if a 1
[sgn(2) (x) |x|
if c 2
Since W1 = AID + [W] and some matrix W E PxD D. then, the entries of W are non-negative and for j ...... we have that
D (W1).,+ = X+ Σ
W
Σ J=1
W Z
Σ W.yl R.
(12)
where, we emphasize that the strictness of the first inequality is due to the positivity of X. Thus, the Gershgorin circle theorem, see Gershgorin (193I), implies that the eigenvalues of W, belong to the set A₁ C C defined by
B2 B2((W)) R.))
1=1
21 S r). Since the computation in equation 12 showed that R; < (W, for each = 1..... D then 0 & A₁. Thus, W is invertible.
where, for E C and 2 O we define B2 {z E C:
Consequentially, RR= u + Wia RP is injective.
For any specification of s, > 0 the (componentwise) map ..1 R + (o.)(u))) RD injective as it is componentwise monotone increasing. the notation of equation Since un = if and only if æ y then the map
RD x e (z, - W1 + E IR
is equal to the zero vector if and only if I y. Since W2 [0, o0) then D(z, y) 2 0: thus, D(r, y) = 0 if and only if x = y. We have just shown that D point-separating (i.e. D(r, y) if and only if x y) and in the process have that D is positive (i.e. D(r,y) 2 0). That is, D separates points in D.
Case H: Pseudo-Metrie for Positive Time Dimensions if T 0:
If instead T E N_, then let Or denote the zero vector in R and v, E RDD with x * y. Then, D((Or, +)) (0r,y)) O. Thus, D does not separate points whenever T > 0. Note that from computational perspective, we account for this using masking during training, see Section 3.2 and
Appendix C
Relaxed Triangle Inequality:
remains show that a relaxed triangle inequality holds. Again, we consider the case when 0, with the general case following identically up to more cumbersome notation. Let E R using the notation of equation for O...., J define the constant
1,0) Note that, 3, = 0 whenever both 8, and 1j < 1 and it equals to (max(s)) 45} - 1) otherwise. Further, note that R; = I, > 1, then 3, = sj 1.
Bg max(max
By definition of the operator norm of each matrix W2 we have that: for 1,....J
||uس|| S [[W || (uy-1)
(13)
By Xia 2009
Example 2.2): for each j = 1,..., . we have that
||o (ug-1) 2 ||u
(14)
Upon combining the bounds in equation 13 and equation 14 for each j = 1....,, we arrive at
J D(a, v) < II
(1W5llop 2 ||uol|
2//3
II [[5lllp
||ual|-
(15)
j=1
21

---

Published as a conference paper at ICLR 2025
Again using Xia 2009
Example 2.2) we have that
1/2
Iooll
ao (o -o (wx))
1/2
(2
| -wil)*
(16)
1m
1/2
=2
Σ
[ - yol2
1=1
- |
y|l-
Upon combining the estimates in equation 13 with those in equation T6 we find that
D(x, v) 52 9
II j=1
|uoll
<2 3
II j=1
|[Wlllo
20 ||a:
vll
(17)
=2 Bj
II j=1
[W5
||00 1-0-v1l- vll.
(18)
Finally, notice that if for each j ......JJ the matrix W, is orthogonal and sy. S
then equation 18 becomes || y|l; in which case D is metric. This concludes the proof.
B.2 EMBEDDING RESULTS
We will routinely use the following ordering.
Definition (Product Order). Let T E N4. The product, or coonlinate, order S* on IRT is defined for each w, y IRT by
S y + Is
for all t =l.t=......
Equivalently, x Sx if = 11 Lnssu (We use S to refer to the ordering given by the neural partial order specifically).
A key step in main results is the ability of neural spacetimes encode the product order in time and snowflake metrics in space. This is quantified by the following helper lemma.
Lemma 1 (An Implementation Lemma for Neural Spacetimes). Let a > 0, S p < oc, and T. D E N+. Then, there exist maps T D+T R² and D P++ RD+T + 10, oc), with respective representations equation and equation such that for all x, E D+T
(i) Implementation of Product Ordering:
(x)D+I.D+T S (y)D4I-D-T T(x) T(y) for t D+ 1........ DTT
iii) Implementation of Snowflake of the e metric:
D(x.y) [1(x).D (y)..D
Furthermore, the parametric complexity T and D are given by:
(a) Depth: (Tpth(T) = 1 and (cpth(D) =
(b) Width: Width(T) and Width(D) D
(c) No. Non-zero Parameters: No. Param + 2 and No. Par(D) 2(3 D).
22

---

Published as a conference paper at ICLR 2025
Proof of Lemma 7 In what follows we use, for any i N+, let I denotes the i i identity matrix, let O, denote the zero vector in IR', and we use 1 to denote the identity map on RR.
Step 1 Implementation of the Product Order
Observe that the product ordering (Definition 9 and the ordering equation coincide if T(x) (+)D+1:D+T for all E D-T, Consider the map T: :+7 RT defined for any x E R P4T by
(19) of the form of equation and by construction T(x) ID+1:D+T for x E RD+T By construction, T has: depth I, width T, and T + non-zero parameters (the identity matrix diagonal entries plus 8 and I).
7(x)= IT (z)D+I++4 Or
Step 2 Implementation of the a-Snowflake of the ( P--uusi-Metric
Fix 2, set 80 = lo det.
p, W, = In. and 82 = 12 det a/p, In def We E RIxD with (W2); for each i = 1,.... D. Therefore,
81 1, det.
uo de
(z:) o,,1 de IDD (uo) (| - -y:l") yil")..
(102 -oe--vi) vil)
(20)
1
0a/p.//p (inu)) =
Σ
xr - vil?) = [1(x) - (v)..
Consequentially, the map D(x, y) and satisfies: for each x. y E D+T
def.
u2 with 02 defined by equation 20 is of the form of equation
D(r, = ( (z) L.D -
Observe that D has depth 2, width and 3 D D 2(3 + D) non-zero parameters.
The following is
technical version of Theorem [ which prove here it implies the version found the main text of our manuscript. Note that so far we have used v, E RD+T for Tu By E N to denote the original node features of two
proofs and derivations. Next, given nodes u and v. Recall the identification E v + Fy E R from Section 2.1 x. used thus far would correspond to the encoded node features (,
Theorem 3 (Universal Spacetime Embeddings). Fix W, N, k E N.. K > O, and let (P, d) be k-point causal metric space with doubling constant K, width W, and feature encoding P PE C TRN. There exists a D E (og(( K)),, T W, an MLP E : TRN - RDT T RD+T IRT with representation equation and D DRT DDT + [0, oo) with repre- sentation equation such that: for each Rus Zv E
(i) Order Embedding: Ia & xv and only Exx) S E(zv),
(ii) Metric Embedding: d(xus S D(E(Tu)) E(x.)) s Ollog( K)5) T.))
Furthermore, there is some D S k such that (ii) can be improved
x.)) ((((s,),
In either case, we have the following parametric complexity estimates:
(i) Geometric Complexity: Together, D and T are defined by total of
D+T+8
non-zero parameters.
(ii) Encoding Complexity: E depends
k2 diamn(P scp( (,, d)
o 5// D log(N) log
non-zero parameters.
23

---

Published as a conference paper at ICLR 2025
Consequentially, together, D, T, and & depend at-most total of k² diam(P,d) ))
o o D+ 2 D log(N) log
scp(P.d)
non-zero parameters.
Proof of Theorem 7 L E (1/2, and E (0, 1], both of which will be fixed retroactively.
Step Causal Embedding:
By Dilworth 1950, Theorem 1.1), (P.5) has width W only if there exists order embedding Ex - 1) )x). Since the inclusion of (10, 1] x*) into (TR x) trivially defines
an order embedding, then g()) def E (P.S) " xx* is an order embedding.
Step 2 (Case I)- Metric Embedding- Now-Distortion Case: By Naor and Neiman's Assouad embedding theorem, as formulated in (Naor & Neiman 2012 Theorem 1.2), there exists absolute constant > 0 such that for each 1/2
and <
there exists bi bi-Lipschitz embedding g(3) (P, d' -0) + (R 11-11111) satisfying: for each Ru: Zo E
d' (Ian Re) & (xx) g( (rx)ll2 S <c ))g(K)
148
(1-a(zu; Fe)
(21)
1
wherd D E O(log(K)/0) /6). Equivalently, for each zur Ty E
d(En; Ne) S E (xr.) ((2)
(x.) 1(1-)
S c/(0=a)
log(()
i-a doFu, (22)
1-
Step 2 (Case III Metric Embedding Isometric Case:
Since (P, d) is such that P is finite, i.e. h #P then. implies that setting def: >(k - 1)/2 del.
loga(1 + 1/( - 1))/2 E (0, 1] (with the case where a only being achieved when is a
singleton) there exists some D N+ and E(2) P Rd such that: for each Tus Tu P
d(z,; 11 (xx) g(2) (x.))l2.
(23)
Since D dim (ppan(((r))aaaa S #P k and since all D dimensional linear of R subspaces are isometrically isomorphic to D-dimensional Euclidean space; then there ex- ists some linear surjection T' RDD + IR which restricts to a bijective isomorphism from (oan(E( to RD (both equipped with Euclidean metries). Then, the composite map g(2) del T' g(2) (P,da) (IR", || II) is an isometric embedding. Consequentially: for each Ta, To E P we have that
d(En, (xx)) g02) (x.))l
(24)
and we emphasize that D < k.
Step 3 Interpolation:
Define the "spacetime embedding" E: + + DDW by: for each P
{xx)) dt (E (())
(25)
We memorize/interpolate & using Kratssoss et al. 2023a Lemma 20); thus, there exists ReLU
MI.P & V TRD+W satisfying: for each 2.. P we have that
{(zw) (x:w)
(26)
Furthermore, Kratsios et al. defining &
2023a Lemma 20) guarantees that number of trainable parameters
o 2 log(N) log (R2 (sppec((,.d))
NNoe that 5 a in notation Naor & Neiman 2012).
TThe isometric embeddability into Fuclidean snowflake characterizes finite metric spaces; see (L. Donne 2018 Corollary 2.2).
24

---

Published as a conference paper at ICLR 2025
where similarly to Krauthgamer et al. 2005) the aspect ratio of the finite metric space (P.d) is defined by
max d(Eu, No)
def. diam (P, d) sep(P,d) d)
aspect(P, (P.d) def.
min E.PP a #u.oo d(Eur Kip)
Thus, the number of non-zero parameters determining & is at-most
h2 diam(P.d)
sep(P.d) )
o D log(N) log
Furthermore, by equation 22 (in case I) and by definition of &, have that: for each Iu, Ty E P
[og(K)
116
d(Eu, R.) S I| (sru) - x ((x,) 1/00aa)) s cl((1-o)
I-a
d(Fu, Fo)
(27)
Iu S Zv E(ra) <" E(xu).
(28)
Retroactively set ē 1/4 E (0, 1] and a del 3/4 E (1/2,1). Then, equation 27 and equation become
28
d(Ia, Fe) S π o ((x)) á T ro0(2)))
1(1-a) < (1024 log(K))) Ie)
(29)
Tu S Fu + ((..) ST E(x,).
(30)
In case II, instead, equation 24 implies that: for each u, v E V
d(zn, No) = || E(r.) - I {xx))ll
(31)
2u S xo + E(xw) ST E(x,).
(32)
Step 4 Encoding Product Order in time and snowflake in space as (T,D)
In either case, since I D+W is equipped with the product order its last W (temporal) dimen- sions and the 1/(1 a) (resp. Lnow-skk of the Euclidean (l2) metric on its first (spatial)
dimension, then the conditions for Lemma 1 are met. Applying Lemma concludes the proof. L
Proof of Proposition 3 Set W E (1.2) 2} and D P N.. By definition, of the order on D-WW given in Lemma (i), spacetime embedding & P D+W exists if and only if o o E P R is an order embedding into (RW <x) where <* is the product order and R (x:) (x:) === E W2 is the canonical projection. By Baker et al.
1970 Theorem 6.1) order embedding of (P. into (R², <x) exists and only if (P, 3) has a planar Hasse diagram.
Proof of Theorem Step 1- Time Embedding
Since the Hasse diagram of (P, 3) has been assumed to be planar, then (Baker et al. 1970 Theorem 6.1) implies that there exists an other embedding
((1) (P.S) (R²
Step 2 Spatial Embedding
Since have assumed that the Hasse diagram of (P, S) is planar, then we may instead use (Rao) 1999 Theorem 9) to deduce that there exists D E N4 and injective map g(2) P RDD such that: for each Fa Ty E P
du (Zu, S (c.) (l2) (x.))l2 S (xw,
(33)
Vlo((k)
where > 0 is an absolute constant. Resealing g(2) by a factor of ev log(kk), and multiplying across equation 33 by ev (oog(k), we find that: for each Fuy P
du (n(,,, S ([ - ((2) (s ( $ Tog(() du (F),
(
(34)
25

---

Published as a conference paper at ICLR 2025
Furthermore, by remark at the beginning of (Rao 1999 Section 4) by the def
lemma, as formulated in (Dubhashi Panconesi 2009 Theorem 2.1), one may take = # P an in- cur an additional factor of /olog that is find that: for each u, 8
(b), for an absolute constant > 0, in the distortion equation 34
du (Ta We) < (E.) - -(9))) (zu))l2 S C log(k) du( To);
(35)
where C oē > 0. Set and recall that || 1/2 - || I Colog(k)] 1/2 on (C(())()) for any Ö 0. Thus, equation 35 implies that: for each Ius In P we have
du( Fo) S (2)) - -x < C" log())) (z(,
(36)
where C² def. CC > and _
Step 3 Interpolation Embedding
Pick some x* IR D42 \. [U (P)) Since P R then consider the map & RRN RD2
defined for each RN by
{(x) (x)) (x))
i E P if & P.
We memorize/interpolate & using (Kratsios et 2023a Lemma 20) over the finite set P. Whenee, there exists ReLU MLP & IR + R D satisfying: for each Za E P
{(x.) = E(xu).
(37)
Again, as in the proof of Theorem trainable parameters defining & is
[ Kratsios al. 2023a Lemma 20) guarantees that number of
o 1132 D' log(N) log (k² (P))))
where, in this case, aspect ratio of the finite metric space (P, dh) is defined by
a.E (T) aSpect dn) min., i. Hz. (H( v.)
def. diam (P,dH)
diam du),
sep(P,1)
where we used the fact that the minimal edge weights between adjacent distance nodes are equal to in an unweighted graph. Consequentially, the number of non-zero parameters determining & is
( log(N) log (k² dian((. dri)).
Step 4 Encoding Product Order in time and snowflake in space as (T,D)
Since R D+2 is equipped with the product order its last two (time) dimensions and the def 1/a- snowflake of the Euclidean (e2) metric on its first D (space) dimension, then the conditions for Lemma are met. Applying Lemma[]]cncllune the proof.
C COMPUTATIONAL IMPLEMENTATION OF NEURAL SPACETIMES
In this appendix, we provide an extended discussion and additional details regarding the computa- tional implementation of neural spacetimes. First, we explain what makes an activation function fractalesque, followed by analysis of the behavior of our proposed activation function for neural (quasi-)metrics and neural partial orders. Moreover, we provide an algorithmic description of the en- tire pipeline, extend the discussion on causality loss enforcement and time embeddings. and propose optimization strategies at both the local and global geometry levels. Additionally, we explore po- tential classical algorithms for computing the optimal embedding dimensions, weight initialization strategies for the networks, and the algorithmic differences between neural snowflakes and neural (quasi-)metrics
26

---

Published as a conference paper at ICLR 2025
C.I WHAT MAKES AN ACTIVATION FUNCTION FRACTALESQUE?
The terminology snowflake arises as follows, Consider the activation function or R - R given by (a) |ar] and set 14g(4)) lo)(3). Then, da y) def. a( v/) defines metric on IR and the metric space (R, da) is isometric to the (von) Koch snowflake fractal (Figure 4 X' C R² endowed
with the distance obtained by restriction of the Euclidean distance R to X. Here, is chosen such that (X, da) has positive and finite a-Hauudorff measure.
(a)
Figure 4: Koch snowflake with increasing number of refinement iterations from left to right.
Indeed, for any general a (0, one can show that d, defines metric on with the property that any line segment has infinite length, see Semmees (1996). Thus, intuitively, the snowflake space (R, d contains infinitely more space to place points while also maintaining similar geometry to the Euclidean line; see e.g. (Acciaio et al.) 20244 Lemma 7.1). See Tyson & Wu (2005) for an intrinsic characterization of metric spaces which arise snowflakes subset of (possibly multidimensional) Euclidean space.
More generally, consider continuous activation function o R. Since continuous and [0, 1] is compact then a admits modulus of continuity [0, oo) - R on [0, 1]; i.e. for each x, E
avv) S w[[ vl). (axx)
(38)
We think of being fractaleqqe it sub-Hölder and non-Lipschitz near That is, there an E (0, 1) (note that < 1) and some L O, such that the right-hand side of equation 38 can be bounded above as
[x(x) oty) I w(x vl) L - yl%
(39)
Thus, if the upper-bound in equation 39 holds for an activation function a,, e.g. our snowflake acti- vation function defined in equation 11 then the Euclidean distance between points in the image of the componentwise application of a are comparable to those the snowflaked space (R [19); making it fractalesque.
C.1.1 THE ACTIVATION FUNCTION IN EQUATION
In this work, we leverage fractalesque activation functions, which exhibit different training dynamics from typical activation functions used in artificial neural networks. We aim visualize this type of activations and to gain an intuitive understanding of their nature.
Neural spacetimes leverage the following equation:
def. (sgn(x) |x]*
if
ssgn (x) |x]
if I
1,
where the sign function sgn returns for > 0 and -1 for < 0. Both neural (quasi-)metrics and neural partial orders neural spacetimes implement variations of this expression.
We visualize the activation using different values for and | in Figure 5a As we see from the plot, the function is antisymmetric about the y-axis, monotonically increasing, and behaves the magnitude of the input. The network can learn to optimize and [ alongside linear projection weights, which can route inputs to different regions of the function, to model different scales independently.
differently depending
27

---

Published as a conference paper at ICLR 2025
(a) Neural (quasi-)mi mmttrc activation function used for spatial embeddings (b) Neural (quasi- >eetric activation (equation 2
function derivative.
(c) Activation function used by neural (d) Activation function used by neural partial order without LeakyReLU.
partial order (equation 4
Figure 5: NST activation visualizations.
In Figure 5b plot finite difference approximation of its derivative. The derivative rapidly in- creases for absolute values of the input near 0 for exponents < 1, meaning it has very high second derivative around these values. This can indirectly destabilize training. Moreover, the absolute value of the derivative itself is also large. This can easily make training unstable as well, especially if we compose this function with itself over multiple layers; when computing backpropagation using the chain rule, the gradients can easily explode.
In the case of the neural partial order, we implement a variation of the activation which is not able to distinguish between small and large scales since = l. Although this would be theoretically enough, and corresponds to the activation in Figure we empirically found to be slow at training. Instead, compose the fractalesque activation with LeakyReLU (refer back to equation which we find aids optimization and accelerates learning. As we can see in Figure 5d this results in a clear difference in the behavior of the function the negative and positive axes of the input. By changing the exponential coefficient, which is learned by gradient descent, the network can substantially alter the behavior of the activation. As before, for exponential coefficients smaller than 1, this activation can lead to instabilities for small input values. For we recover LeakyReLU.
Based on these observation restrict all activations learn and coefficients greater than only. These allows us to use fractalesque activations while restristing the functions to behave more similarly to activations used the literature such as ReLU, LeakyReLU SiLU functions.
C.2 ALGGRRITHMIC DESCRIPTION
We complement the mathematical descriptions of neural spacetimes in Section with the following algorithm summaries. As discussed in the main text, let N N., be the dimensionality of the feature vectors T,, Te E V associated with nodes u, v E V, where represents the set nodes of the digraph GD (ED, V, WD). Fix space dimension D) N4 and time dimension T' e N neural spacetime a learnable triplet S = (E, D. T), where:
..RN + R++ is an encoder network (MLP), DD: D+T P o0) is learnable quasi-metric on D and
. .T:RD4T R is learnable partial order T
28

---

Published as a conference paper at ICLR 2025
In particular, we implement D and T two distinct artificial neural networks inspired by neural snowflakes, which process the space and time dimensions encoded feature vectors L., &y. def. ((zu), PP7 in parallel.
Algorithm 1: Neural (quasi-)metric. D
Require: Pay &o
D Two Encoded Node Features Vectors Distance
return Suu
ug ao I:D Jsaid
For j = to J
Uj - Wyg (uj-1)
end Suv f UJ
Algorithm 2: Neural Partial Order, T
Require: ia
D Encoded Node Feature Vector Temporal Encoding
return fu 20 +- (#u)D+1:D4T
For j =
2 V, LeakyRel.U by
end
tu 1-22 2J
Algorithm 3: Neural Spacetime, S (E, D)
(Forward Pass)
Require: Tu,
Two Node Features Vectors
return Suv: buu
Distance and Temporal Encodings
Lu. Po ((I)),((Io)
Enconde Feature Vectors
Suv f- ((2u,, Lt)
> Compute Distance Apply Temporal Encoding
tu t- (
C.3 CAUSALITY LOSS AND TIME EMBEDDING
introduced the procedure used to optimize neural spacetime model. The metric embedding in space is relatively simple an analogous to previous works (Borde & Kratsios,
In Section 3.2
2023
Kratsios al. 2023b). In this appendix expand the computational approach used for embedding causality and optimizing the time embedding.
The causality loss is given in the main text by:
c Au Li (teepSigmoid(T(@.)) -T(E))))
with SteepSigmoid(z) Ite- (the value 10 was found experimentally, making the function too steep can lead to training instabilities). and where Lg slightly modifies the expression (equation 40):
Σ SteepSigmoid(((a.)) - T(
For the sake of understanding, let focus the equation above first.
SteepSigmood(()) - 4 -c.
29

---

Published as a conference paper at ICLR 2025
In particular, SteepSigmoid(z) tends to faster than Sigmoid(z)
(see Figure 6). In
asymptotic notation:
SteepSigmoid(z) 0.
lim
Sigmoid(x)
Importantly, SteepSigmoid (T(u)) ((t)): OV (T -
0 even
[T (fa): - -ē ) is small. As discussed in Section 3.2 the loss for two causally connected events & in the first neighborhood of each other (Auv 1) is minimized when E. x² f, satís-
fied (equation 5)
In our mathematical formulation, the exact magnitude of the negative difference is not important. At first glance, a more straightforward way of imposing this condition is to use ReLU activation functions instead. However, these are discontinuous and lead unstable training. which we verified experimentally. Hence, we want continuous function that is easy to optimize and reaches zero quickly as the partial order is satisfied. Remember that we are optimizing the distance loss for the spatial component of the spacetime embedding and the time embedding using the causality loss simultaneously. computation trying to make the difference between partial embeddings more negative for reason and, as a consequence, failing to further optimize the metric distortion the embedding when we have already satisfied causality.
the causality loss does not reach zero quickly enough, we will be wasting
Finally, to ensure that the causality loss provides good gradients while being zero as soon as the partial order is satisfied we the following expression, which converged to empirically and that satisfies all our requirements:
c def.
Ano SteepSigmoid(((@.)) T((o)))) (1 TotalCorrecc),
(40)
where the second term is not differentiable but makes the loss zero when all the directed edges have been correctly embedded. To compute this we can indeed use the ReLU function:
Σ PM Damay
Aus -1
(E ReLU T())) =0)
TotalCorrect
def.
Epl
where the expression in the enumerator counts how many times the function evaluates to zero for connected nodes.
1.3
Agric
Figure 6: Comparison between (standard) Sigmoid and SteepSigmoid function.
30

---

Published as a conference paper at ICLR 2025
C.4 How TO THEORETICALLY ENFORCE THE GLOBAL CAUSAL GEOMETRY
In Section 3.2 we discuss that for practical purposes, we only focus on encoding local geometry. which in optimizes the causal geometry of the neural spacetime implicitly for causally con- nected events due to transitivity. For anti-chaing the no causality condition will be satisfied with high probability, especially as the number of time dimensions increases. For completeness, here we provide a loss function to enforce the global causal geometry of DAGs if the causal connectivity in the input geometry was easily computable. Note that for large graphs, this becomes very computa- tionally expensive since need to verify that for anti-chains, there is no path between those two given nodes.
T - + Buv (min ReLUU(= -7
del.
A'e
Check: No Causality
Check: Causality
(41)
((udengtu) with entries Bue for two events and v, which can be deduced from A' and where > is margin. A in this case is not the adjacency matrix, but a mask which is for causally connected nodes or events. Note that here unlike in the main text we are not restricting causality to the first hop. Also, B is symmetric: Bu
where B
Bru-
The loss above enforces causal connectivity and lack of causal connectivity. Both t. ft and G. it. must be satisfied by our representation for anti-chains. T > is required, otherwise it is not possible to avoid causality in at least one direction. In the simplest case, when = and & E (2) the following must be satisfied if we associate 2., with and f., with T(Ee), >> T(ww),, and Tir)t, > T(ā.)t,. or (ft));, > ((uu)tz and T (āw),, > ((E)),, To satisfy the no causality condition when T > 2, as long one of the time dimensions breaks S7 in equation it suffices. e would be included in this hypothetical optimization objective to avoid the collapse of the encoder network to single embedding. Lastly, would like to highlight that this causality loss should be optimized alongside a distance loss based on the graph geodesic distance instead of the local distance. Although this is theoretical exercise, in practice it may be best to substitute ReLU with SteepSigmoid for optimization purposes as in Section
C.5 POTENTIAL CLASSICAL ALGORITHMS TO COMPUTE SPACE AND TIME DIMENSIONS
Theorem M shows that the number of time dimensions should be at least equal to the width of the poset being embedded by the NST. In theory, the width of a poset could be computed in polynomial time (Felsner et al. 2003). Furthermore, for posets with a width of less than 4, there are algorithms with a runtime of On log(n)) (sub-quadratic time) that can detect if the poset has a width of at most 4. Nevertheless this theoretical results become impractical for large graphs. Similarly, Theorem D shows that the required number of spatial dimensions needed to obtain faithful low- distortion metric embedding of the graph underlying poset is determined by its doubling constant. is known that an exact computation of this doubling dimension is generally NP-hard Gottlieb & Krauthgameri (213)) Alternatives algorithms to obtain accurate upper bounds (up to an absolute constant factor) are also discussed in the literature (Har-Peled Mendel 2005), but these are in general impractical for large DAGs.
C.6 WEIGHT INITIALIZATION AND HANDLING THE ABSENCE OF NORMALIZATION
Weight initialization is important to avoid initial network predictions from shrinking exploding. Networks with fractalesque activations are particularly susceptible to this problem, as they use acti- vations with exponential coefficients. This is not such a prevalent issue if we use the well-established ReLU activation or its variants (ELU, RecakyReUU, etc.), since this activations only zero out part of the axis and leave the rest of the transformation linear.
In the original neural snowflake model (equation 10.. the matrices A, B, and C' are initialized with weights sampled from uniform distribution spanning from 0 to 1. which are then normalized according to the dimensions of each matrix. Specifically, for matrix A, the weights are drawn from distribution ranging between 0 and 1/(dAıdA2) where dAi represents the number of rows and
31

---

Published as a conference paper at ICLR 2025
d represents the number of columns of matrix A. We follow the same approach initialize W in equation 3 While better initialization alternatives may be possible, it was noted previously in (Borde & Kratssos 2023) that drawing the weights from normal Gaussian or using Xavier initialization can lead to instabilities and exploding numbers in the forward pass. We also observe that this initialization technique is important avoid the metric prediction becoming either too small too large when making the network deeper since we cannot naively apply normalization layers inside our parametric representation of the metric. Additionally, we find that neural (quasi-)metrics are better than the original neural snowflakes in maintaining the same order of magnitude in its distance prediction as the number of layers is increased.
C.7 NEURAL SNOWFLAKES VS NEURAL (QURRIC)METRICS
Next, we discuss similarities and differences between the original neural snowflake and neural (quasi-)metrics. We first provide an algorithmic description of neural snowflakes, which can be used to compare against that presented in Appendix C.2 for the neural (quasi-)metric model.
Algorithm 4: Neural Snowflake
Require: Tay Fi
Two Node Features Vectors D Distance similarity measure
return 8ij Ug - [ tz l|2
> Euclidean Distance
For j = 1 to J
D. Linear Projection Snowflake Activation P Linear Projections
Σg tūūj1 -1
Uj t B,
end
8ig t J H+pp
> Quasi-metric
Embedding Experiments. In terms of experiments, generally, we find that neural (quasi-)metrics have a smoother optimization landscape. They tend to converge faster for a low number epochs, and in the case of snowftakes, those reported in Appendix I of (Borde & Kratsios] (023). As shown in Section D.I] the neural (qutsi-)metric construction performs better tree embedding. What observed is that if trained for a sufficient duration, snowflakes will eventually find a good local minimum. On the other hand, our new model seems more reliable in terms of optimization and achieves better performance for lower epochs.
experimentally observed sudden drops in MSE loss, similar to
11 and b are in principle presented as learnable compo- nents via gradient descent. However, in practice exponents can be unstable to optimize via back- prop (Borde& & Kratsios 2023). The original neural snowflake fixes b issues. Nevertheless note that p. which controls the quasi-metric in Equation I0 indeed optimized. Optimizing exponents closer the final computations of the network is in general more stable. We hypothesize that this could be due to the fact that there are less chain-rule multiplications, reducing the likelihood of gradient explosion. We observe similar behaviour for neural (eeasss)metriss,, note that our activation function relies on learning the exponents (equation 2}. In general we find that can learn the exponents for all layers in this configuration. But we also experimented with trying to approximate fractal metrics and observed that under some extreme cases it may be better only optimize the exponents of the last layer for stability.
Optimizing exponents. In Equation
avoid optimization
D EXPERIMENTAL DETAILS
In this appendix we expand on the experimental procedure used to obtain the results presented in the main text in Section 4 Additionally, we present more validation experiments, including undirected tree embeddings, synthetic DAG embeddings with different metrics and varying levels of connectivity, and large DAG citation network embeddings.
32

---

Published as a conference paper at ICLR 2025
D.1 UNDIRECTED TREE EMBEDDING
Overview of Results for Preliminary Undirected Embeddings. Before proceeding to DAGs, fol- lowing Kratsios et al. (2023b). we first test the spatial component of the NST model, on embedding trees and compare it to Fuclidean embeddings implemented by an MLPP and to hyperbolic embed- dings via HNNs Ganea et al.] (2018). We use the same training procedure as in Kratsios et al.] (2023b) and perform experiments for both binary and ternary trees. In the case of the snowflake geometry, inputs are mapped using an MLP, and the metric induced by the tree structure is learned by a neural (quasi-)metric with layers operating on the embedding space dimensionality. We measure dis- tortion as the ratio between true and predicted distances. Consistent with the theoretical results (uupta 2000), we find that in general, the difference average distortion between metric spaces is not as pronounced as the maximum distortion since most metric spaces are "treelike" on average. Indeed, we find that our proposed model better restricts the maximum distortion and that it is able to achieve average distortion of 1.00 even with an embedding space of dimension 2 only. For completeness we also test the neural snowflake model in the same task, which although it is able to minimize the MSE loss, the (max) distortion is very high. Additional discussion comparing neural snowflakes and neural (quasi-Jmetrics metrics can be found in Appendix C.7
Table 3: Tree Embedding distortion leveraging Euclidean, Hyperbolic, Neural Snowflake and Neural (Quasi-)metric spaces.
Tree Type
Embedding dim
Geumelry
Avg Distortion
dev Distortion
Max Distortion
MSE
Fuclidean
1.66
1224.17
26.27
Hyperbolic
1.04
L.ll
402.52
12.76
Neural (Quasi- Metrie
1.00
0.23
3.09
10.09
Snowilake
1.01
3.01
2261.35
9,47
Binary
Euclideun
1,15
0.68
159.74
10.19
Hyperbolic
1.00
0.17
11.03
4.14
Neural (Quasi-)
1.00
0.19
3.87
4.88
Snowilake
1.00
0.65
539.71
5,92
Euclidean
1.69
3.17
602.96
11.55
Hyperbolic
1.09
1.23
135.81
5,55
Neural (Quusi-)Mett
1.00
0.20
6.33
3.34
Snowlllake
4017.99
Temary
Euclideun
I,17
0.82
185.73
4.82
Hyperholic
1.00
0.15
16.56
1.37
Neural (Quasi-)Metric Metric
1.00
0.16
4.19
1.72
Snowilake
1.00
0.47
237.88
2.15
Experimental Procedure for Undirected Tree Embeddings. Neural spacetimes provide guaran- tees in terms of global and local embeddings. In general, from a computational perspective, local embedding is more tractable. However, in these particular preliminary experiments for metric em- bedding, similar to (Kratsios et al. 2003b), we embed the full undirected tree geometry. The distance between any two nodes u, U E simplifies the usual shortest path distance on an unweighted graph
dr(u, = inf (i [u, (1 u E
(42)
Using the expression above, we compute the tree induced graph geodesic between nodes. We work with both binary and ternary trees with edge weights being equal to To find all-pairs shortest path lengths we use Floyd's algorithm (Floyd) 1962). Note that Floyd's 's's algorithm has running time complexity of ((VV)) and running space O(V This makes it not scalable for large graphs.
The networks receive the and yn. coordinates of the graph nodes in R22 and are tasked with map- ping them to a new embedding space which must preserve the distance. An algorithm is employed to generate input coordinates, mimicking force-directed layout of the tree. In this simulation, edges act as springs, drawing nodes closer, while nodes behave as objects with repelling forces, similar to anti-gravity effects. This process continues iteratively until the positions reach equilibrium. The algorithm can be replicated using the NetworkX library and the spring layout for the graph.
The networks need to find an appropriate way to gauge the distance. We adjust the network parame- ters by computing the Mean Squared Error (MSE) loss, which compares the actual distance between nodes given by the tree topology, dine: to the distance predicted by the network mappings, dprea:
33

---

Published as a conference paper at ICLR 2025
Loss = MSE(ddus dpeed).
For the Multi-Layer Perceptron (MLP) baseline, the predicted distance is calculated as:
Aped MM, Uv) MLP Be)ll2,
where (Ius Vu) and (Ie, yo) represent the coordinates in IR? synthetically generated tree. On the other hand, for the HNN, utilize the hyperbolic distance between embeddings with fixed curvature -1:
Apred = d-1 (HNNN Uu), (NN(
In the case of HNNs, we employ the hyperboloid model, incorporating an exponential map at the pole to map the representations to hyperbolic space, detailed in [Borde al. (2023b). Notably, we do not even need any hyperbolic biases to discern the performance disparity between MLP and HNN models (Kratsios et al. 2023b).
Note that the previous two basclines, the geometry of the space is effectively fixed, and we only optimize the location of the node embeddings in the manifold. In the case of neural snowflakes, the metric also parametric and optimized via gradient descent. This means that we change both the location of events in the manifold and the geometry of the manifold itself during optimization. Following (Borde & Kratsios 2023), the neural (quasi-)metric model also leverages the encoder & which is implemented as MLP (same as the Euclidean baseline). The predicted distance
dpred dNqM (MLP(E. yu). ML).MLP(a. MLP Bu)),
where dvQM is parametrized by neural (quasi- )eetrcc network. Importantly, feature vectors passed independently to the metric learning network (unlike (Borde & Kratsios) 2023) where an intermediate Fuclidean distance representation is fed instead).
In terms of hyperparameters, we generate trees with 1000 nodes and embed them into features of dimensionality and 4 in different experiments. We employ batch size of 10,000 learn the distances, train for 10 epochs with learning rate of 3 x 10-3 and Adam optimizer, and apply max gradient final projection layer to the embedding dimension. The neural (quasi-)metrie has a total of 4 layers, with hidden layer dimension equal to the event embedding dimensions, that either 2 or and the last layer projects the representation to scalar, i.e., the predicted distance. We use the same configuration for the snowflakes.
of 1. All encoders have total of 10 hidden layers with 100 neurons and
D.2 METRIC DAG EMBEDDING
In this appendix, provide additional details the synthetic weighted DAG embedding exper- iments described in Section 4 focusing on local embedding. Similar to the previous setup, the networks receive the Tu and yu coordinates of the graph nodes in R² and are tasked with map- ping these coordinates to a new embedding space that preserves both the distance and directionality of the generated DAG. We train the embedding following Section 3.2 As discussed the main text, we optimize the spacetime embedding by running gradient descent based on both a distance and a causality loss. The procedure used to train the neural (quasi-)mad metric in terms of the spatial embedding is identical to that described in Appendix D.I
We use the Graphviz dot layout algorithm to generate the input coordinates, positioning the nodes from top to bottom according to the directionality of the DAG. This process can be replicated using the Net workor library. Additionally, the coordinates are normalized to lie between and 1. The DAG is constructed from random graph where each node has 0.9 probability of being connected to other nodes, defining the directionality and connectivity of the DAG (see Figure 77. The metric distance is then calculated based on the spatial coordinates of the nodes after they have been embedded in the plane. The specific distance functions used in the experiments are listed in Table I and are based on (Borde & Kratsios 2023).
34

---

Published as a conference paper at ICLR 2025
In terms of hyperparameters,
generate DAGs with 50 nodes and embed them into spacetimes of D = T = 2, 2, 10. The 50 nodes induce 502 possible distances. We do not apply mini- batching optimize all of them at the same time. We train for 5,000 epochs with a learning rate of 10 using the AdamW optimizer, and apply a max gradient norm of 1. The initial encoders have a total of 10 hidden layers with 100 neurons each and final projection layer to the embedding dimension D + T', The neural (quasi-)un metti- and the neural partial order have total of 4 layers, each with hidden layer dimension of 10.
Figure 7: Example DAG with 10 nodes and using the first metric in Table
D.2.1 VARYING GRAPH CONNECTIVITY
We conduct additional experiments to analyze the effect of graph topology on the embedding results. Specifically, we fix the synthetic metric | log(1 (1+ -|x-yll)).. and experiment with graphs having varying connection probabilities, which control the sparsity of the random DAGs, i.e., their connectivity. Across all geometries, we observe that as the DAG becomes more sparsified, its direc- tionality is captured less accurately. However, it also becomes easier to achieve lower distortion, as expected, due to the reduction in the number of edges to encode, see Table
Table 4: Embedding results for arxiv citation network.
Neural Spacetime
Minkowski
Sitler
Distortion
Max Distortion
Distortion
Embed. Dim
Directionality
Directionalitt
Directionalitt
Distortion
Distortion
Distortion
Connectivity
+
1.00
+:
72.66
0.99
0.99
90%
1.02 1. 0.06
1.51
1.00
1,70
2.77
71.09
0.99
4.33 1. 816.47
10,255
0.99
1.21 32
1.33
35.38
0.99
9,7447
324,027.5
1.14 1: 0.42
3.94
1.00
3.35
1 10.44
215.65
1.00
238.02
5.432.33
13,879.30
0.99
50%
1.01
3 0.07
1.38
1.00
1.27
0.82
12.45
1.00
-12.61
3 2,253.31
43,124.22
0.9
10
1.00
1 0.18
1.06
1.00
1.02
1 0.19
4.03
1.00
-33.3
1: 1,600.69
18,756.20
0.99
1.00
+ 0.30
2.65
0.98
1.01
+ 2.41
15.96
0.93
-1.18
19.43
69.29
0.92
10%
1.00
1 0.01
1.01
1.00
1.00
1 0.02
1.03
0.96
1,09
14.32
130.62
0.91
10
1.00
1 0.00
1.00
0.98
1.00 1 0.02
178
0.96
2.39 20.30
176.00
0.9
D.3 HEAL-WORLE NETWORK EMBEDDING
WebKB datasets. In these datasets (Rozemberczki et al. 2021), nodes represent web pages, while edges denote hyperlinks between them. Each node's s features are given by the bag-of-words repre- sentation of its web page. We summarize the datasets in Table
As discussed the main text in Section 4 these datasets are not pure DAGs. As a preprocessing step, remove self-loops. However, we do not remove cycles, nor do we further process edge directionality. This explains why in Table T it is not possible to get perfect embedding in time. The local metric between nodes is computed the cosine similarity between the node feature em- beddings (since the datasets do not have edge weights). Note that here we do not embed graphs in the plane; already have bag-of-words features that be passed the encoder, unlike in the
35

---

Published as a conference paper at ICLR 2025
Table 5: Statistics of WebKB datasets
Name
#nodes
fedges
Coreell
Texas 183
298
Wisconsio 251
515
synthetic DAG experiments, In terms of training, the procedure is the same as in Appendix D.2 and using a learning rate of 10-4
Table 6: Statistics of Dream5 datasets
Name
#nodes
#edges
In silico
1.565
4,012
Escherichia coli
1,811
2,066
Saccharomyces cerevisine
1994
3,940
Dream5 datasets. The Dream5 datasets (Marbach et al. 2012) were originally introduced as part of the Network Inference Challenge, where participants were provided with four microarray compendia and tasked with deducing the structure of the underlying transcriptional (gene) regulatory networks. Each compendium encompasses numerous microarray experiments, spanning various genetic, drug, and environmental alterations (or simulations thereof, in the of the in-silico network). In this work, instead of focusing on network structure prediction, we test our neural spacetime algorithm in the context of graph embedding, following the spacetime representation literature (Law & Lucas 2023] (Sim et al. 2022). We embed the graph topology in I² using Graphviz dot layout and compute the strength between the connections based on the cosine similarity, since the original networks do not have weights. In T we record the number of nodes and edges for each dataset. Note that these are not pure DAGS either (but it is possible embed over 99% of the directed edges correctly, see Table 10h. For training, we follow Appendix D.2 with learning rate 10-4
Ogbn-arxiv Large Citation Graph Embedding. Given that the previous graphs are relatively small, we conduct an additional experiment the ogbn-arxiv dataset (Hu et al. 2021), which is orders of magnitude larger (see Table 7 We use similar procedure as before: we remove self- loops to avoid returning similarity scores of 1.0 and also remove edges between nodes whose feature vectors have a cosine similarity score greater than 0.99. In this particular dataset, we found that some nodes had almost identical features, which, due numerical truncation when computing the distance between nodes, resulted a distance zero and led to numerical instabilities. This resulted 269 rejected edges out of 1, 1,166,243, or 0.02%.
Table 7: Statistics of Ogbn-aroa arxiv dataset
Name
#nodes
#edges
Azxiv
1,166,243
We train all models for 40 epochs, using the AdamW optimizer with learning rate of 10- and batch size of 10,000. We report the results in Table g below. Once again, we observe that, under the same training conditions, NSTs superior embedding compared to their fixed geometry counterparts. However, we observe a degradation in performance compared to previous experiments with smaller graphs. Additionally, note that do not modify the parameter count of the neural networks.
Table 8: Embedding results for arxiv citation network.
Neunal Spacetime
Minkowski
De Sitter
Embod. Diu
Max Distortion
Directionalit
Distortion
Directionality
Max Distor tion
Directionality
Distortion
Distortion
Distortion
Dataset Arxiv
1.88 4.37
1,031.11
0.80
4.64
7,322.96
1,811,888.55
0.83
-133.12
16.142.16
1,845,115.5
0.77
36

---

Published as a conference paper at ICLR 2025
D.4 ADDITIONAL RESULTS
In this appendix, we provide extended tables of the results presented in the main text.
Table 9: DAG embedding results. Embedding dimension D = 7 2, 4, 10.
Neurall Spacelime
Emhodding Dim
(average stand dev)
Max Distortion
Directionality
1.13 + 0.37
5.82
1.0
yll log(1 vil)
1,02 0.06
1.34
1.0
1,16 + 045
6.21
1.0
y1 log(1 vil)
1,02 0.07
1.75
1.0
1.53 4 1225
14.20
1.0
10:55
1.00 2 0005
1.63
1.51 + 1:18
13.55
1.0
exp T
1.11
1.01 0.05
1.31
1.0
1,60 +: 1.42
17.07
1,0
1- Itlx-y
1.00 + 0.05
1.44
1.0
Minkowski
Metric
Embledling Dim
Distortion (average d: stand dev)
Max Distortion
Directionality
2,86 5.22
72.66
0.99
- y11 log(1 + Ixx - v
1.70
71.09
0.99
10
1.21 + 1:33
33.58
0.99
6.77 133.68
1669.88
0.99
- yl1a log(1 + ||x v
1.19 d: 1:09
25.18
0.99
21.89 : 739J05
18753,37
0.99
1.17 4: 1.25
37,42
0.99
11,37 + 114:38
1876.34
0.8
-(xx-y--1) exp loxlx-y1
2.49
1.18 3: 2:49
82.67
0.99
20.65 + 292.90
$471,07
0.96
2883
1.13 1 0.1
28.45
0.99
Dr Simee
Metric
Embeddling Dim
Distortion (average stand dev)
Max Distortion
Directionalit
||x - + |xx y
-4.33 +: 816.47
18235.21 21
0.99
288.17 3 9794.97
324027.3
0.99
[xx y110 log(1
||x y
174.69 1: 3637.32
11585188
0.99
10
-10.06 4: 739.71
8997.62
0.99
4418.15
20
0.9
10
-333.23 +: 8701.18
1300
0.94
-183.71 9600.7
39664866
exp -
83.04 4313.82
97524.2
0.94
10
418.26 1 659938
1501593.23
0.91
-542 39 22088.97
114291,45
0.94
00
00
0.94
0.91
37

---

Published as a conference paper at ICLR 2025
Table 10: Embedding results for real-world web page hyperlink graph datasets and gene regulatory networks.
Neural Spacetioe
Dataset
Embedding Dim
Distortion (avg. sdev.)
Max Distortion
Directionality
2
1.00 = 0.07
1.31
0.93
Cornell
4
1.00 0.04
1.08
0.94
0.04
1.08
0.94
1.01 0.10
2.27
0.89
Texas
1,00 0.01
1.05
0.90
10
1.00 0.00
1.00
(1900
2
1.00 0.10
1.67
0.89
Wisconsin
4
1.00 -. 0.04
1.16
0.89
10
1.00 0.04
1.20
0.89
1.06 0.47
18.54
1.00
silico
1.00 0.09
1.73
10
1.00 0.05
1.32
1.00
2
1.02 0.45
15.37
1.00
Escherichia coli
4
1.00 0.06
2.62
1.00
10
1.00 - 0.05
1.17
1.00
1.05 = 0.34
10.18
1.00
Saceharomyces cerevisiae
1.00 +0.07
1.63
1.00
1.002 0.05
1.57
Mirkowski
Dataset
Embedding Dim
Distortion (avg.
sdev.)
Distortion
Directionality
2
1.07 0.70
9.43
0.94
Comell
1:00 - 0.00
1.0l
0.94
10
1.00 0.00
1.00
0.94
2
1.12 = 1.73
31.27
0.90
Texas
1.00
0.90
0.011
5.07 65.99
1410.03
0.90
Wisconsin
4
1.00 0.04
1.19
0.90
10
1.13 0.69
16,28
0.90
2
105.42 1: 4671.85
209248.72
0.94
In silico
4
0.25 + 54.37
1313.76
0.93
1.00 0.05
3.69
0.99
2
-4.25 149.61
438.34
0.97
Escherichia coli
1.00 0.01
1.08
0.98
10
1,00 0.01
1.01
0.99
2
-2.38 173.57
151.43
0.91
Saccharomyces cerevisiae
1.04 2.25
63.17
0.98
10
1.01 = 0.02
1.39
0.99
De Sitter
Dataset
Embedding Dim
Distortion (avg.
sdev.)
Max Distortion
Directionality
2
-55.83
890.45
3950.88
0.92
Comell
-20.60 249.49
403.46
0.94
10
0.80
126.26
1543.07
0.93
2
-0.29 = 84.42
818.10
0.90
Texas
4
42.03 1. 795.51
13939.25 23
0.90
10
2.60 1: 70.33
1107.60
0.0
2.06 + 63.46
1291.31
0.89
Wisconsin
-0.78 = 27.91
114.24
0.90
10
0.04 215.94
2862.19
0.89
-63.59 1866.69
56626.97
0.92
In silico
4
466.81
33021.14
65289.22 22
01.2
10
-129.13 9623,30
261531 ,99
0.93
2
34.65 = 2637.50
119047,23
0.91
Escherichia coli
4
-2.00 =: 3294.81
130509.59
0.91
-8.26 94,37
652.96
0.91
55.36 3960.09
160278.39
Saccharomyces cerevisiae
-28.60 T175.67
63086.54
(1.90
10
-121.17 7550.16
84724.25
0.91
38

---

Published as a conference paper at ICLR 2025
D.5 FURTHER CLARIFICATIONS ON EXPERIMENTS USING NEURAL SPACETIME EMBEDDINGS COMPARED TO
BASELINES
In this section, we aim to provide additional intuition to the reader on how NSTs compare to the fixed-geometry embedding baselines and why we expect them to perform better.
For all experiments, we use a feature encoder that maps the graph node features to the relevant man- ifold. We assume that the output of the feature encoder is in Euclidean space in all cases. We then proceed according to the specific geometry. This approach aligns with previous works such as neu- ral snowflakes (Borde & Kratsios 2023) and other studies product manifold embeddings (Borde) et al. 2023b).
Intuitively, one understand the problem two-step process, which in practice is learned jointly via end-to-end gradient descent. In the first step, the encoder learns to position the graph nodes in space-that is, it learns to map the original node features to coordinates in the manifold. In the second step, the distance between points on the manifold is evaluated, either based on a given metric when the geometry is fixed or by learning the geometry (the metric itself) in a data-driven fashion.
In the cases of Minkowski and De Sitter space, the geometry is not learned but given. More specif- ically, Minkowski space, we use the feature outputs of the Euclidean feature encoder, apply a change in the metric tensor, and recognize that one coordinate has a different signature. In this particular case, we do not require an exponential map since the space is flat. For De Sitter space, the situation is similar: only the positioning of points in the manifold is optimized via gradient descent, while the geometry remains fixed. In terms of implementation and metric calculation, De Sitter space is a curved manifold, making computations more complicated than for Minkowski space. We use an embedding approach that avoids exponential maps: we map points into De Sitter hyperboloid in a higher-dimension geometric operations we utilize include normalizing spatial components, computing the De Sitter inner product, and handling both timelike and spacelike separations. Additionally, we would like to highlight that, although the authors in (Law & Lucas] (202)) also use Minkowski and De Sit- ter spaces, our baselines are more powerful. This is because we employ a neural network feature encoder to optimize the placement of node embeddings within the manifold
Minkowski space and compute geodesic distances there. The
NSTs are intrinsically different in that their geometry is not fixed but rather random at initializa- tion and parametrized by neural network that always outputs ggeudo-qussimmetee by construc- tion. The specific pseudo-quasi-mene metric generates is learned during optimization based on the input graph. Hence, in this case, both the position of the points on the manifold and the geometry of the manifold itself are learned jointly via gradient descent. For NSTs, we do not need exponential maps either since the construction is based warping norm. During optimization, the inputs are the graph node features, and the targets are both the distances between nodes (induced by the graph ge- ometry) and the causality structure (given by the edge directions). Since neural spacetimes are able to reshape the geometry of the embedding space as a function of the data, they are inherently more flexible and they are able to embed DAGs with less distortion (the best possible value for distortion is 1).
D.6 DOWNSTREAM APPLICATION TESTING: NODE CLASSIFICAITION ON EMBEDDED HETEROPHILIC GRAPHS
Lastly, we evaluate the downstream performance of encoding approach in transductive node classification for heterophilic graphs, specifically using the Cornell, Texas, and Wisconsin datasets. It is important to note that this is not a standard application of NSTs, as their original design aims to embed DAGs with minimal distortion. NSTs typically use the feature encoder network as an ini- tial intermediate mapping to latent space, which then utilized by the learnable quasi- qutri-metric and learnable partial order to encode distance and directionality respectively. While the neural quasi- metric takes two node feature vectors as input and outputs scalar distance value (making it un- suitable as direct input for a downstream node classification task), the neural partial order operates pointwise and returns a feature vector. Therefore, we adopt the following approach. First, we train the complete NST model to encode the original graph into the continuous geometry, simultaneously optimizing all three networks composing the NST, 3, D, and T. Once trained, we use the frozen feature encoder and neural partial order as pretrained featurizers to encode the original node features from the dataset at hand. These transformed features are then fed into a downstream network that is trained node-wise classifier. That is, the new node features for the graphs become:
39

---

Published as a conference paper at ICLR 2025
Ze = =2 (Ro)1:D to:
where i. = Exx,), to = T(x))
(43)
where we have augmented the original features with NST-based features optimized according to the graph topology. In the equation above zn corresponds to the original features for node v, and T are the frozen feature encoder and partial order, which were originally optimized alongside D. As in the main text, the subscript in (1.) means that we utilize the first D spatial dimensions from the feature vector, and we use for concatenation. We use pre-trained checkpoints with D T 10.
We display the downstream results in Table I1 below. We experiment with different down- stream classifiers, including MLPs, GCNs (Kipf & Welling 2017). GAT's (Veličković et al. 2018),
CPGNN-MLE (Zhu et al., 2021). and CPGNN-Chebe (Zhu et al. 202T, Defferrard et al. 2016).
Note that CPGNN is not just network but also framework for training on heterophilic graphs It employs an estimator network, such as an MLP or a Chebyshev polynomial-base prediction. The CPGNN method incorporates estimator pretraining and utilizes a compatibility ma- trix, which is initialized using the training node labels and the training mask. This matrix is further refined using the Karkhomm-Knopp algorithm for initialization. Furthermore, the compatibility ma- trix is regularized during training through an additional loss term on top of the cross-entropy loss. We reimplement all baselines and test them on the Cornell, Texas, and Wisconsin datasets using 10-fold splits, based on the masks provided in PyTorch Geometric. Following (Zhu et al.) (20IT) we use weight decay of x 10-4 for all networks and pretrain the estimators in CPGNN-MLP and CPGNN-Cheby for 100 steps. All our downstream classifiers use two layers with a ReLU activation function and are trained with learning rate of 0.01 for 400 steps using Adam W. We experiment with varying hidden dimensions- 10, 20, 30, and 64-the last of which is the hidden dimension used by the baselines in (Zhu et al. 2021). In our experiments, we study the effect of adding geometric node features based on the NST encoding to downstream classifiers. We find that the MLP classifier achieves the best downstream performance when augmented with NST features, particularly for the Texas and Wisconsin datasets. For Cornell, the best downstream performance achieved by the MLP without NST features, which attains 71% accuracy with a hidden dimension of 64. The coun- terpart augmented with NST features achieves 70% accuracy, making the difference not particularly significant. Overall, in Cornell, we observe that adding NST features is especially beneficial for smaller classifiers with fewer hidden dimensions.
model, for
These experiments confirm that the NST has learned meaningful features that can be used by down- stream classifiers. However, we invite future research in this direction, as this paper primarily fo- cuses on embeddings, and this appendix is only initial exploration of the applicability of NSTs to downstream tasks.
Table 11: Node classification results for heterophilic graphs, including the test accuracy mean and standard deviation. / denotes that the input features the downstream classifier consist of the original graph input features plus the NST features ,, = xv || (R.)1.D || f.. In contrast, X indicates that only N. is passed into the model.
Datasel
Hidden
Features
GAT
CPGNN-MLP
CPGNN-CheNNor
/
0.09
0.48 = 0.05
0.05
0.51 0.05
19
x
0.40 4: 0.12
0,45 0.06
0.48 = 0.07
0.47 0.10
0.46 = 0.11
Comeell
20
20
/
X
0.56 0.11
0.61 0.09
0.45 0.06
0.44 0.09
0.49 1 0.08
0.49 0:00
0,31 1 0.05
0.43 011
041 0.07
0.50 = 0.30
2112
0.50 0.10
7
0.70 0.07
0.45 0.09
0.30
-.00
0.50
1 0.8
0.32 0.07
64
x
0.71 1 0.07
0.45 0.07
0.50
1 0.00
0.40 0.10
0.40 1:000010 0.11
0.58
0.08
0.56
0.09
0.61 005
0.02 0.08
X
0:41
2: 0.08
0.50
0.07
0.63 0.10
0.67 0.10
Toxas
201
20
7
x
0.57 + 0.10
00G4 2 0007
0.49 4 0.07
- 0:17
0.50 = 0.30
0.54 = 0.06
0.61 0.100
0361 +
0.61 = 0.30
061 = 0000
30
0.72 0.08
0.08
0.52 4 0.09
0.61 0.06
0.6 0.06
0.07
0.53
0.100
0.61 0.30
64
0.74 1 0.008
0.55 0.07
0.54 1 0.06
Mal 1000
0188 0107
04
LOON 2: 000
0,45
2 0.07
0.47 = 0.00
0.37 0:100
033 = 0.11
10
0013
0.05
0.48 0.00
0.05
0.51 0.08
X
0.45 0.D8
0.46
0.61
0.58
Wisconin
20
20
7
X
0.76 + 0:10
0.70 0:09
0.44
0.30 0.06
1 0.06
0.48 - 0.05
0.49 = 0.08
0.50
0.60
0:10
2 0.0
0 0.005
0.32 = 0.11
30
7
0.78 2 0006
1.49 1106
0.47 = (.00
0300 60X
0333 0.11
301
0.07
0.49 = 0.0
0.03
0.7 0004
0.81 0.05
0.51 0.10
0.12
0.53 0.13
64
x
0,76 1. 0.08
0.45 0.07
0.49 1 0.06
0.57 0.04
0.7 0.07
40


Reviews:
[{"review_id": "ZsDb2kjNwR", "reviewer": "Reviewer_vRyg", "summary": "This paper presents Neural SpaceTimes (NSTs), a class of trainable geometries that can encode nodes of weighted Directed Acyclic Graphs (DAGs) into a spacetime manifold. NSTs are designed to capture both spatial and causal (temporal) information by using a product manifold combining spatial quasi-metrics with temporal partial orders to represent graph weights and directionality. Besides, theoretical analysis of the universal embedding theorem shows that NSTs can learn low-distortion embeddings for any DAG. Some experiments are also conducted to validate the effectiveness of NSTs.", "questions": "1. How do NSTs perform in real-world learning tasks evaluated by well-established metrics (e.g., accuracy, NMI, and F1, ROC-AUC)?\n2. How do NSTs perform when compared with conventional GNNs in real-world learning tasks?\n3. Do NSTs still perform robustly in massive graphs?\n4. How do NSTs perform when compared with GNNs tackling heterophily?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The problem tackled in this paper, i.e., representation learning in DAGs, is challenging and significant in the graph machine learning community.\n2. Theoretical guarantees of the proposed approach are provided in the manuscript.", "weaknesses": "Despite the merits of the paper, I have the following concerns.\n1. Most results presented in this paper pertain to distortion and directionality, which demonstrate that NSTs perform robustly when evaluated by these two measures. However, there are no concrete results showing the performance of NSTs in real-world learning tasks, e.g., (semi-supervised/unsupervised) node classification, link prediction, and graph classification in synthetic DAGs, real-world DAGs (e.g., web page hyperlink graphs and citation graphs), and spatiotemporal graphs (e.g., encrypted transaction graphs). Authors are suggested to conduct some previously mentioned learning tasks and investigate how NSTs perform.\n2. Some test datasets used in the experiments are always considered by those graph neural networks tackling graph heterophily (e.g., CPGNN). Compared with these graph neural networks tackling graph heterophily, how do NSTs perform in real-world tasks?\n3. Most test datasets considered in this paper are also used to test conventional graph neural networks, e.g., GCN, GAT, GraphSAGE, and Graph Transformer. The authors should compare NSTs with conventional graph neural networks in real-world learning tasks (as mentioned in point 1).\n4. The test datasets used in this paper are relatively small. How do NSTs perform in larger datasets? The authors can consider using datasets from OGBN, and other large datasets.", "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": "", "extra_scores": {}}, {"review_id": "BnN6o2WHk3", "reviewer": "Reviewer_Crpy", "summary": "The paper sets forth a new neural network architecture capable of learning the embedding of a DAG into a pseudo-Riemannian manifold, which encodes both the spatial and temporal distance between nodes of the DAG in a continuous way. Some conditions (along with proof) are given which guarantee that the embedding is faithful.\n\nThe network itself is composed of three separate networks, namely, an initial latent space embedding $\\mathcal{E}: \\mathbb{R}^N \\rightarrow \\mathbb{R}^{D+T}$, a modified neural snowflake $\\mathcal{D}: \\mathbb{R}^{D+T} \\times \\mathbb{R}^{D+T} \\rightarrow [0, \\infty)$ which is the quasi-metric on the manifold, and a partial order $\\mathcal{T}: \\mathbb{R}^{D+T} \\rightarrow \\mathbb{R}^T$ which encodes the causal relationships in the DAG. These latter two networks are trained parallel to each other and are optimized with respect to an aggregated loss function $\\mathcal{L} = \\mathcal{L}^{\\mathcal{D}} + \\mathcal{L}^{\\mathcal{T}}$.\n\nEmpirical results are given over several datasets, some synthetic with a complex pseudo-metric and others real-world webpage hyperlink DAGs. The results are favorable of the new architecture compared to those of Minkowski and De Sitter space embeddings, showing that the new architecture shows little distortion in the learned quasi-metric and almost always preserves the causal relationships among nodes in the DAGs.", "questions": "1) In the latent space embedding, is there any guarantee that $\\mathcal{E}$ maps feature vectors in such a way that the resulting embedding can be partitioned into spatial and temporal components? E.g., you embed features from $\\mathbb{R}^N$ into $\\mathbb{R}^{D+T}$ and later separate the embedding by slicing the results ($1:D$ and $D+1:D+T$) for use in the recursions of $\\mathcal{D}$ and $\\mathcal{T}$. Therefore, my question is, how do you guarantee that spatial information ends up only in the first $D$ dimensions, and temporal in the last $T$ dimensions?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper offers originality within its domain by constructing a novel architecture capable of embedding a DAG into a pseudo-Riemannian manifold which has several spatial and temporal components. In particular, adding the capability of embedding a given DAG into more than one temporal component is a novel contribution and allows the network to represent and preserve more complex causal structure from the DAG. Furthermore, the authors modify the neural snowflake model for use as a learnable quasi-metric.\n\nThe quality of the paper is also very good given that the authors cited several relevant related works and gave ample justification in the form of mathematical proof for their many propositions and theorems, thus adding to the already existing clarity of the paper.\n\nI believe this paper makes a significant contribution to the field by adding the ability to represent discrete structures in a continuous fashion with very little approximation error, thus presenting a new and powerful tool to various application domains.", "weaknesses": "The paper would benefit from further experimentation, e.g., showcasing the results of the network to various distributions of DAGs and being explicit about any potential weaknesses. It would be nice to know where this architecture breaks down or how. robust it is to perturbations in the assumptions.\n\nThe language in lines 420-422 becomes imprecise and can lead to confusion. I would suggest sticking to a single convention here when using variables in a description. Similarly when the switch is made from using $T$ to using $W$, it's not clear why this is done and can lead to confusion.\n\nAlso, there seems to be a type on line 215 that would make a significant difference. The elements $x_1, x_2 \\in \\mathcal{X}$ cannot be compared using the metric from $\\mathcal{Y}$. I assume you meant to say $\\rho(f(x_1), f(x_2))$ not $\\rho(x_1, x_2)$.", "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": "", "extra_scores": {}}, {"review_id": "DJlFhGVlsA", "reviewer": "Reviewer_uYUp", "summary": "The paper proposes Neural SpaceTimes (NSTs), a framework for embedding directed acyclic graphs (DGAs) in continuous geometries which can encode both edge weights and directionality. Unlike previous methods that use fixed spacetime manifolds, NSTs learn the geometry itself through three neural networks -- an embedding network for mapping nodes to coordinates, a neural quasi-metric network for encoding distances in space dimensions, and a neural partial order network for encoding causality in time dimensions. The authors provide theoretical guarantees showing that NSTs can universally embed any k-point DAG with low distortion while preserving its causal structure. Experiments on both synthetic and real-world directed graphs demonstrate that NSTs achieve lower embedding distortions compared to baseline methods using fixed geometries like Minkowski or de Sitter spaces.", "questions": "1. How does the framework scale to very large graphs? The current larges experiment uses ~200 k nodes, but many real-world networks could be larger.\n2. The local vs. global geometry optimization tradeoff warrants deeper analysis -- could hierarchical or multi-scale approaches help bridge this gap while maintaining computational tractability? \n3. While the paper shows NST can encode both local distances and causality, how well does it preserve higher-order DAG properties like path lengths between distant nodes or branching structures? This could be particularly relevant for applications like computational workflow graphs or neural architecture search where these properties are important.\n4. For DAGs with hierarchical structure (like computational graphs or dependency trees), how does the learned geometry reflect this hierarchy? Additional analysis of how NSTs capture hierarchical relationships would strengthen the practical applications.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-organized with clear problem statement , goal (Section 1), and the proposed solution (Section 3).\n* The theoretical framework in Section 3 decouples spatial and temporal components while maintaining their interaction through the embedding network. \n* The theoretical development in Section 3.1 establishes embedding guarantees through Theorem 1, showing NSTs can universally embed k-point DAGs.\n* The experimental validation in Section 4 demonstrates clear improvements over baselines, particularly for low-dimensional embeddings where NSTs maintain average distortion near 1.0 while other methods show much higher distortion.\n* The practical applicability is well explained through the analysis of real-world networks in Table 2.", "weaknesses": "* In Section 3.1, while the paper proves existence of neural sapcetime embeddings with low distortion, it provides limited practical guidence on selecting the number of temporal dimension. This could be important for complex DAGs where the minimal sufficient dimension is not immediately clear.\n* The optimization approach in Section 3.2 focuses on preserving local structure during training. While the authors provide theoretical guarantees about global structure preservation, the empirical validation concentrates mainly on local metrics.", "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": "", "extra_scores": {}}, {"review_id": "4q8BHTIP8z", "reviewer": "Reviewer_icVJ", "summary": "This paper proposes a framework of quasimetric embeddings using spacetime as the embedding manifold.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The method seems well-motivated to me. In particular, the decomposition makes sense as a space for DAG-like data, and the paper proposes a nice way of doing so with neural networks.\n2. The empirical results seem promising, as the method seems to be able near perfectly embed many common DAG graph datasets.", "weaknesses": "While the paper seems to be mostly complete to me, several concerning aspects about the experiments did not sit right with me.\n\n1. The empirical results have some concerning aspects about them. In particular, the Minkowski embedding is able to largely get to near the same final distortion on both the real world graph datasets. Since the proposed method uses neural networks as well as node features (at least for the real-world data) while the previous methods do not (as is my understanding from skimming the Law and Lucas paper), this suggests that the difference provided by the proposed method is not very large with respect to the required additional effort or that the test tasks are too simple.\n2. While the distortion is near perfect, the downstream effects of using these embeddings is never studied. In particular, some GNN-type experiments would be greatly appreciated.", "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": "", "extra_scores": {}}, {"review_id": "FbyQDFaYeN", "reviewer": "Reviewer_spGj", "summary": "The authors introduce a novel architecture, Neural SpaceTimes (NSTs), which represents nodes in Directed Acyclic Graphs (DAGs) as events in a trainable spacetime manifold. This framework innovatively unifies spatial distances and causal directionality into a single representation space, designed to improve upon fixed spacetime geometries typically used in graph embedding. The authors implement this system through three neural networks: an embedding network, a neural quasi-metric, and a neural partial order network.", "questions": "Q1. In line 215 about the metric embedding, what is $\\rho(x_1,x_2)$? Since $\\rho$ is defined on $\\mathcal{Y}$, how can $\\rho$ compute on $\\mathcal{X}$?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1. NSTs' combination of quasi-metric spaces for spatial information and partial orders for causal information presents an elegant and flexible solution to representing DAGs.\n\nS2. The authors provide a robust theoretical foundation. \n\nS3. The experimental results on synthetic and real-world DAG datasets indicate the NST’s capability to achieve lower embedding distortions.", "weaknesses": "W1. Could authors provide more explanations about the experimental results? How is NST compared to closed-form spacetimes such as the Minkowski? Why the NST is better than the closed-from spacetimes? Besides, comparison with more baselines can be more convincing. \n\nW2. It would be good to see a time complexity analysis for the proposed NST.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)