Distance-Preserving Embeddings in Inhomogeneous Random Graphs
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...
| Authors | My Le, Luana Ruiz, Souvik Dhara |
|---|---|
| Primary category | cs.LG |
| Published | 11 July 2026 |
| Last updated at source | 11 July 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.