Beyond Worst-Case Distortions Distance-Preserving Embeddings in Inhomogeneous Random Graphs

Jul 16, 2026

Upload by Noah

Graph machine learning seeks node representations that preserve structural information across local and global scales, especially shortest-path distances. Existing theoretical guarantees for distance-preserving embeddings rely on worst-case analyses and yield overly pessimistic dimension–distortion trade-offs that do not reflect typical large heterogeneous networks. This work studies landmark-based shortest-path approximation on inhomogeneous random graphs with type-dependent edge probabilities, producing tighter, structure-aware bounds for both local and component-wide averages and extending them via a metric-sandwiching framework for L2 kernel models, including heavy-tailed networks.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages53

Reading Time2 h 14 min

Abstract

Keywords

Introduction

Background on graph embeddings

Limitations of global functional preservation

Landmark-based distance embeddings

Motivation for sharper guarantees

arXiv :2607 . 10074v 1 [ cs .LG] 11 Jul 2026 Beyond Worst-Case Distortions: Distance-Preserving Embeddings in Inhomogeneous Random Graphs My Le [mle19@jh.edu](mle19@jh.edu) [Department of Applied Mathematics & Statistics](Department of Applied Mathematics & Statistics)[ ](Department of Applied Mathematics & Statistics)Johns Hopkins University Baltimore, MD 21218, USA Luana Ruiz [lrubini1@jh.edu](lrubini1@jh.edu) [Department of Applied Mathematics & Statistics](Department of Applied Mathematics & Statistics)[ ](Department of Applied Mathematics & Statistics)Johns Hopkins University Baltimore, MD 21218, USA Souvik Dhara [sdhara@gatech.edu](sdhara@gatech.edu) School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA 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 worstcase 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 (IHGs), 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, i.e. Ω 􀀀n1−ε log n 􀀁, than classical worst-case bounds, i.e. Ω 􀀐n 2(21εε) log n􀀑 for (1 − ε)-distortion and Ω 􀀐n 2ε log n􀀑 for (1 + ε)-distortion. 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 L2 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. Keywords: shortest path, distance-preserving embeddings, landmarks, graph spanners, inhomogeneous random graphs, heterogeneity, graph neural networks, transferability ©2026 My Le, Luana Ruiz, and Souvik Dhara. License: CC-BY 4.0, see [https://creativecommons.org/licenses/by/4.0/](https://creativecommons.org/licenses/by/4.0/) . Le, Ruiz, and Dhara 1 Introduction A central challenge in graph learning is to represent networked data in a form that faithfully captures its essential structural characteristics, including local connectivity patterns, mesoscopic organization, and global topology. A common strategy is to map nodes into lowdimensional metric spaces so that distances between embedded points reflect the graph’s original structure. These embeddings provide a compact and mathematically tractable representation of the network, enabling both statistical analysis and efficient computation at scale in a wide range of inference tasks, including node classification, link prediction, clustering, and routing (Hamilton et al. 2017b, Grover and Leskovec 2016, Belkin and Niyogi 2003) . Despite significant progress, node embedding techniques are primarily designed to

FAQs

What problem does the paper address in distance-preserving graph embeddings?

It targets the gap between worst-case theoretical distortion guarantees and the typically better behavior of distance preservation in large, heterogeneous networks, where shortest-path distances are often poorly captured.

How does the paper improve analysis for shortest-path approximation?

It analyzes landmark-based embeddings on inhomogeneous random graphs, leveraging type-dependent heterogeneity and neighborhood growth modeled by multi-type branching processes to obtain tighter dimension–distortion trade-offs.

What additional model extension is proposed beyond classical landmark methods?

It introduces a GNN-augmented variant that replaces exact shortest-path queries with neural surrogates, using the alignment between message passing and shortest-path dynamic programming to improve scalability and generalization.

Jul 16, 2026

Upload by Noah