# Shortest path distance approximation using deep learning techniques

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2020.

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

- [Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings](https://mlsanity.com/paper/2211.15120/) (2022)
- [On the Learning and Learnability of Quasimetrics](https://mlsanity.com/paper/2206.15478/) (2022)
- [GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation](https://mlsanity.com/paper/2205.15217/) (2022)
- [An Empirical Survey and Benchmark of Learned Distance Indexes for Road Networks](https://mlsanity.com/paper/2602.04068/) (2026)
- [Deep Distance Sensitivity Oracles](https://mlsanity.com/paper/2211.02681/) (2022)
- [Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphs](https://mlsanity.com/paper/2504.08216/) (2025)

## Abstract (arXiv)

Computing shortest path distances between nodes lies at the heart of many graph algorithms and applications. Traditional exact methods such as breadth-first-search (BFS) do not scale up to contemporary, rapidly evolving today's massive networks. Therefore, it is required to find approximation methods to enable scalable graph processing with a significant speedup. In this paper, we utilize vector embeddings learnt by deep learning techniques to approximate the shortest paths distances in large graphs. We show that a feedforward neural network fed with embeddings can approximate distances with relatively low distortion error. The suggested method is evaluated on the Facebook, BlogCatalog, Youtube and Flickr social networks.