TY - JOUR
T1 - Normed Spaces for Graph Embedding
AU - Taha, Diaaeldin
AU - Zhao, Wei
AU - Riestenberg, Maxwell J.
AU - Strube, Michael
N1 - We would like to extend our thanks to Anna Wienhard, Maria Beatrice Pozetti, Ullrich Koethe, Federico López, and Steve Trettel for many interesting conversations and valuable insights. We extend our sincere gratitude to the reviewers for their insightful comments and suggestions, which have significantly enhanced the quality of this paper. J.M. Riestenberg was supported by the RTG 2229 “Asymptotic Invariants and Limits of Groups and Spaces” and by the DFG under Project-ID 338644254 - SPP2026. Wei Zhao was supported by the Klaus Tschira Foundation and a Young Marsilius Fellowship at Heidelberg University
PY - 2024/5/28
Y1 - 2024/5/28
N2 - 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. Inspired by this theoretical insight, we highlight in this paper 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 publicly available
AB - 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. Inspired by this theoretical insight, we highlight in this paper 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 publicly available
UR - https://openreview.net/forum?id=4E2XLydJiv
M3 - Article
SN - 2835-8856
VL - 2024
JO - Transactions on Machine Learning Research
JF - Transactions on Machine Learning Research
IS - 5
M1 - 1984
ER -