  Theoretical results from discrete geometry suggest that normed spaces can
abstractly embed finite metric spaces with surprisingly low theoretical bounds
on distortion in low dimensions. In this paper, inspired by this theoretical
insight, we highlight normed spaces as a more flexible and computationally
efficient alternative to several popular Riemannian manifolds for learning
graph embeddings. Normed space embeddings significantly outperform several
popular manifolds on a large range of synthetic and real-world graph
reconstruction benchmark datasets while requiring significantly fewer
computational resources. We also empirically verify the superiority of normed
space embeddings on growing families of graphs associated with negative, zero,
and positive curvature, further reinforcing the flexibility of normed spaces in
capturing diverse graph structures as graph sizes increase. Lastly, we
demonstrate the utility of normed space embeddings on two applied graph
embedding tasks, namely, link prediction and recommender systems. Our work
highlights the potential of normed spaces for geometric graph representation
learning, raises new research questions, and offers a valuable tool for
experimental mathematics in the field of finite metric space embeddings. We
make our code and data publically available.
