AI summaryⓘ
The authors study how to create graph embeddings that keep distances between nodes accurate, focusing on typical large networks rather than worst-case scenarios. They analyze landmark-based methods on random graphs with varying connection probabilities and show these can better balance embedding size and distortion. Their analysis covers a wide range of network types, including those with complex structures like power-law distributions. They also develop a new approach using graph neural networks to approximate shortest paths more efficiently, which generalizes well from small synthetic graphs to large real ones. This method matches or even improves upon traditional exact landmark-based embeddings while being less computationally demanding.
graph machine learninggraph embeddingsshortest pathlandmark-based embeddingsinhomogeneous random graphsgraph neural networks (GNN)distortion boundspower-law networksgraph spannersmessage passing
Abstract
Graph machine learning provides powerful tools for understanding complex networks and learning meaningful node representations. A central challenge, however, is designing embeddings with minimal distortion of both local and global functionals, such as shortest path lengths. Prior distortion guarantees for distance-preserving embeddings are worst-case in nature, producing overly pessimistic bounds that fail to capture the structure of typical large-scale networks. To address this, we analyze shortest-path approximation via landmark-based embeddings on inhomogeneous random graphs, a general model with type-dependent edge probabilities. By retaining shortest paths to a small set of reference nodes called landmarks, landmark-based methods effectively function as virtual graph spanners, where structural heterogeneity and controlled neighborhood expansion modeled via multi-type branching processes enable significantly tighter dimension-distortion trade-offs than classical worst-case bounds. We extend these guarantees to global, component-wide averages and unify the analysis across finite-type and continuous latent spaces through a novel metric sandwiching framework, establishing universal distortion bounds for general $L^2$ kernel models, including heavy-tailed and power-law networks. Finally, we introduce a GNN-augmented variant that replaces rigid, computationally expensive exact shortest-path queries with flexible, structure-aware neural surrogates. By leveraging the inherent alignment between graph neural message-passing and the dynamic programming principles of shortest-path algorithms, our approach demonstrates that models trained on small-scale random graphs learn to extract universal distance-preserving features, achieving robust generalization to large-scale, real-world networks that match or exceed the fidelity of classical, exact landmark-based embeddings.