Directed Graph Embeddings in Pseudo-Riemannian Manifolds
Aaron Sim, Maciej L Wiatrak, Angus Brayne, Paidi Creed, Saee Paliwal
Abstract
The inductive biases of graph representation learning algorithms are often encoded in the background geometry of their embedding space. In this paper, we show that general directed graphs can be effectively represented by an embedding model that combines three components: a pseudo-Riemannian metric structure, a non-trivial global topology, and a unique likelihood function that explicitly incorporates a preferred direction in embedding space. We demonstrate the representational capabilities of this method by applying it to the task of link prediction on a series of synthetic and real directed graphs from natural language applications and biology. In particular, we show that low-dimensional cylindrical Minkowski and anti-de Sitter spacetimes can produce equal or better graph representations than curved Riemannian manifolds of higher dimensions.
BibTeX
@InProceedings{pmlr-v139-sim21a,
title = {Directed Graph Embeddings in Pseudo-Riemannian Manifolds},
author = {Sim, Aaron and Wiatrak, Maciej L and Brayne, Angus and Creed, Paidi and Paliwal, Saee},
booktitle = {Proceedings of the 38th International Conference on Machine Learning},
pages = {9681--9690},
year = {2021},
editor = {Meila, Marina and Zhang, Tong},
volume = {139},
series = {Proceedings of Machine Learning Research},
month = {18--24 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v139/sim21a/sim21a.pdf},
url = {https://proceedings.mlr.press/v139/sim21a.html},
abstract = {The inductive biases of graph representation learning algorithms are often encoded in the background geometry of their embedding space. In this paper, we show that general directed graphs can be effectively represented by an embedding model that combines three components: a pseudo-Riemannian metric structure, a non-trivial global topology, and a unique likelihood function that explicitly incorporates a preferred direction in embedding space. We demonstrate the representational capabilities of this method by applying it to the task of link prediction on a series of synthetic and real directed graphs from natural language applications and biology. In particular, we show that low-dimensional cylindrical Minkowski and anti-de Sitter spacetimes can produce equal or better graph representations than curved Riemannian manifolds of higher dimensions.}
}