# Metric Embedding via Shortest Path Decompositions

arXiv: https://arxiv.org/abs/1708.04073 · HTML: https://mlsanity.com/paper/1708.04073/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2017.

## Built on by (most cited first, 2 of 2)

- [Neural Spacetimes for DAG Representation Learning](https://mlsanity.com/paper/2408.13885/) (2024)
- [GLADformer: A Mixed Perspective for Graph-level Anomaly Detection](https://mlsanity.com/paper/2406.00734/) (2024)

## Abstract (arXiv)

We study the problem of embedding shortest-path metrics of weighted graphs into ℓp spaces. We introduce a new embedding technique based on low-depth decompositions of a graph via shortest paths. The notion of Shortest Path Decomposition depth is inductively defined: A (weighed) path graph has shortest path decomposition (SPD) depth 1. General graph has an SPD of depth k if it contains a shortest path whose deletion leads to a graph, each of whose components has SPD depth at most k-1. In this paper we give an O(k^minfrac1p,frac12)-distortion embedding for graphs of SPD depth at most k. This result is asymptotically tight for any fixed p>1, while for p=1 it is tight up to second order terms. As a corollary of this result, we show that graphs having pathwidth k embed into ℓp with distortion O(k^minfrac1p,frac12). For p=1, this improves over the best previous bound of Lee and Sidiropoulos that was exponential in k; moreover, for other values of p it gives the first embeddings whose distortion is independent of the graph size n. Furthermore, we use the fact that planar graphs have SPD depth O(log n) to give a new proof that any planar graph embeds into ℓ1 with distortion O(√log n). Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor.