Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphs
This provides a scalable and transferable method for graph representation learning, addressing a known bottleneck in capturing global functions like distances.
The paper tackles the problem of learning node representations that capture global graph distances, showing that landmark-based embeddings require lower dimensions for random graphs than worst-case graphs and demonstrating that GNN-based approximations generalize well to real-world networks.
Learning node representations is a fundamental problem in graph machine learning. While existing embedding methods effectively preserve local similarity measures, they often fail to capture global functions like graph distances. Inspired by Bourgain's seminal work on Hilbert space embeddings of metric spaces (1985), we study the performance of local distance-preserving node embeddings. Known as landmark-based algorithms, these embeddings approximate pairwise distances by computing shortest paths from a small subset of reference nodes called landmarks. Our main theoretical contribution shows that random graphs, such as Erdos-Renyi random graphs, require lower dimensions in landmark-based embeddings compared to worst-case graphs. Empirically, we demonstrate that the GNN-based approximations for the distances to landmarks generalize well to larger real-world networks, offering a scalable and transferable alternative for graph representation learning.