Abstract
Traditional graph embedding methods often fail to capture directed cycles and non-transitive relationships because they rely on Riemannian geometries like Euclidean or hyperbolic space. This paper proposes a novel framework using pseudo-Riemannian manifolds—specifically Minkowski and anti-de Sitter spacetimes—with a cylindrical time dimension. By introducing a Triple Fermi-Dirac likelihood function, the authors demonstrate superior performance in representing complex directed structures while maintaining efficiency in low dimensions.
Introduction
Graph representation learning typically relies on the "inductive bias" of the underlying geometry. Euclidean space is suited for homophily, while hyperbolic space excels at representing hierarchies (Directed Acyclic Graphs). However, real-world networks, such as gene regulatory or social networks, often contain directed cycles and non-transitive relations (e.g., A links to B, B to C, but A does not link to C). Standard Riemannian geometries are mathematically biased toward transitivity, making it difficult to represent loops without collapsing nodes into the same embedding space. This research explores pseudo-Riemannian manifolds as a natural solution for modeling directionality and periodicity.
Methodology: Spacetime Geometries and Likelihood
The authors propose embedding graphs into Lorentzian spacetimes, specifically Minkowski and anti-de Sitter (AdS) manifolds. Unlike Riemannian spaces, these allow for "space-like" and "time-like" separations due to a metric that can be negative, zero, or positive.
To handle cycles, the model employs a cylindrical topology ($S^1 \times \mathbb{R}^N$), wrapping the time dimension into a circle. This allows a directed path to move forward in time and eventually return to its origin. Central to this approach is the Triple Fermi-Dirac (TFD) Likelihood function. Unlike symmetric distance functions, the TFD explicitly incorporates the time difference ($\Delta t$) between nodes.
As shown in the figure above, the parameter alpha controls the "sharpness" of the likelihood region. By adjusting this parameter, the model can tune its sensitivity to directionality and transitivity, effectively defining the "light cone" of probable connections in the embedding space.
Handling Transitivity and Cycles
A key insight of this work is the ability to disentangle similarity from direct linkage. In spacetime, nodes can be close in spatial coordinates but separated in time, allowing them to share context without necessitating an edge. This flexibility is crucial for modeling non-transitive relations.
The TFD function allows the model to "break" transitivity when needed. As illustrated in the figure above, the probability distributions shift for simple chains versus fully transitive graphs depending on the alpha value. This demonstrates the model's capacity to represent diverse graph topologies within the same geometric framework by simply tuning the likelihood parameters.
Experimental Results
The model was evaluated on synthetic (Duplication Divergence), biological (DREAM5), and lexical (WordNet) datasets:
- Cyclic Graphs: On the DREAM5 gene regulatory networks, pseudo-Riemannian models (Cylindrical Minkowski and AdS) significantly outperformed Euclidean and Hyperbolic baselines. On the Duplication Divergence task, Cylindrical Minkowski achieved ~65% Average Precision (AP), nearly doubling the ~39% achieved by Euclidean embeddings.
- Efficiency: Low-dimensional spacetime embeddings often outperformed higher-dimensional Riemannian counterparts, suggesting that the geometric structure is more important than raw parameter count.
- Hierarchies: Even on WordNet, a pure DAG where hyperbolic space usually reigns supreme, the Minkowski + TFD model remained highly competitive, matching state-of-the-art hyperbolic disk models.
Conclusion and Future Work
By moving to pseudo-Riemannian manifolds, the authors provide a robust framework for embedding complex directed graphs. The use of cylindrical topology and the TFD likelihood function allows for the natural representation of cycles and non-transitive relations. While optimization in these spaces is more complex due to the lack of a positive-definite metric, the performance gains in low dimensions are substantial. Future work may extend this "flow-based" representation to causal inference tasks in biological and social sciences.
Summary updated