Spacetime Representation Learning

Marc T. Law, James LucasICLR 2023 · OpenReview

Introduction

Much of the data we encounter in the real world—from citation networks to biological pathways—can be represented as directed graphs. However, most machine learning models represent data in Riemannian manifolds, such as Euclidean or hyperbolic space. While these geometries are excellent for capturing symmetric distances and undirected relationships, they inherently struggle with the "flow" or causal order of directed graphs.

This paper introduces a novel framework for representing directed graphs by embedding them into "spacetimes"—connected, time-oriented Lorentz manifolds. By leveraging the intrinsic causal structure of these geometries, the authors provide a mathematically rigorous approach to naturally model directed edges and hierarchies, outperforming traditional Euclidean and hyperbolic approaches in tasks like link prediction and hierarchy extraction.

The Challenge of Directed Graphs

Previous attempts to use pseudo-Riemannian manifolds (which allow for non-positive definite metrics) to model directed graphs were often limited to the simplest cases, such as flat Minkowski space, or relied on ad hoc methods to determine edge orientation. The core problem lies in finding a general framework that exploits the full "causal structure" of spacetimes to represent complex directed relationships, including those with cycles, without losing geometric rigor.

Methods: Lorentzian Causality as Graph Direction

The authors propose a framework inspired by Lorentzian causality theory from general relativity. The fundamental idea is that the "arrow of time" is a perfect mathematical analog for directed edges. If an event $A$ can causally affect an event $B$, a directed path exists between them.

Geodesics in de Sitter and anti-de Sitter spacetimes

Key components of their approach include:

  • Spacetimes as Embedding Spaces: The framework utilizes a variety of Lorentz manifolds, including Minkowski space, de Sitter space (positively curved), anti-de Sitter space (negatively curved), and Cylindrical Minkowski space.
  • Lorentzian Pre-length Spaces: Instead of standard symmetric distances, the model uses the concept of "chronological order" ($x \ll y$). An edge exists from node $A$ to node $B$ if the representation of $A$ chronologically precedes $B$ in the spacetime.
  • Squared Lorentzian Distance: The authors introduce a differentiable "squared Lorentzian distance" function ($\chi^2_V$) for optimization. Unlike standard distances, this function can be positive (for causal/time-like connections) or non-positive (for non-causal/space-like connections). This allows the model to actively "push" unrelated nodes into non-causal regions of the spacetime.
  • Convex Normal Neighborhoods: To ensure optimization is well-behaved, edge existence is restricted to pairs of nodes within a "local" neighborhood where geodesics are unique and well-defined.
  • Handling Cycles: By using non-chronological spacetimes like the Cylindrical Minkowski space, the model can represent directed cycles—a major hurdle for traditional Directed Acyclic Graph (DAG) embedding methods.

Key Insights and Results

The framework was evaluated on several diverse datasets, including DREAM5 Gene Regulatory Networks, Zachary’s Karate Club, the HEP-TH Citation Network, and a NIPS Co-authorship dataset.

The proposed methods significantly outperformed baselines in directed link prediction. Different "spacetime" curvatures provide different inductive biases for different graph structures. Furthermore, the Cylindrical Minkowski space proved particularly effective because its "wrapped" time dimension allows for directed cycles while maintaining a local sense of "future" and "past."

Link prediction performance on DREAM5 datasets

As shown in the results, the "Cylindrical Minkowski + equation 6" method achieved state-of-the-art performance. For example, in highly constrained 3D embeddings on the S. cerevisiae dataset, it achieved a 50.0% Average Precision (AP), compared to just 37.4% for previous spacetime methods and 33.0% for Euclidean baselines. The framework is remarkably powerful in these low-dimensional settings, where the geometric inductive bias does most of the heavy lifting.

Hierarchy Extraction

In social networks, the model successfully identified "leaders" (high-level nodes) by naturally placing them at the causal "extremes" of the spacetime. The squared Lorentzian distance proved much more effective at ranking node importance than standard arc-length metrics.

Limitations and Future Work

While highly effective, the framework has a few limitations to address in future research:

  • Hyperparameter Sensitivity: Performance depends on parameters like the "radius" of the space or the "circumference" of the cylinder, requiring careful tuning for different datasets.
  • Global vs. Local Structure: The reliance on convex normal neighborhoods aids optimization but limits the "reach" of a single node's causal influence. Balancing local precision with global graph structure remains an open challenge.
  • Scaling: Applying this to billion-scale graphs will likely require further optimization of the pseudo-Riemannian gradient steps.

Ultimately, mapping directed graphs to general relativity offers a rich, mathematically grounded path forward for representation learning. The authors suggest that exploring "warped product" manifolds—combining different types of spaces—could be a promising direction for embedding even more complex, heterogeneous data types.

Summary updated

Abstract

Much of the data we encounter in the real world can be represented as directed graphs. In this work, we introduce a general family of representations for directed graphs through connected time-oriented Lorentz manifolds, called "spacetimes" in general relativity. Spacetimes intrinsically contain a causal structure that indicates whether or not there exists a causal or even chronological order between points of the manifold, called events. This chronological order allows us to naturally represent directed edges via imposing the correct ordering when the nodes are embedded as events in the spacetime. Previous work in machine learning only considers embeddings lying on the simplest Lorentz manifold or does not exploit the connection between Lorentzian pre-length spaces and directed graphs. We introduce a well-defined approach to map data onto a general family of spacetimes. We empirically evaluate our framework in the tasks of hierarchy extraction of undirected graphs, directed link prediction and representation of directed graphs.
BibTeX
@inproceedings{law2023spacetime,
  author = {Marc T. Law and James Lucas},
  title = {{Spacetime Representation Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=qV_M_rhYajc},
}
Figure