# Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 36 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Builds on (most cited first, 5 of 5)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks](https://mlsanity.com/paper/1611.01890/) (2016)
- [A Survey of Shortest-Path Algorithms](https://mlsanity.com/paper/1705.02044/) (2017)
- [A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem](https://mlsanity.com/paper/2410.12031/) (2024)
- [Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice](https://mlsanity.com/paper/1304.2576/) (2013)

## Abstract (arXiv)

Benchmarking shortest-path algorithms is commonly based on aggregate performance over heterogeneous graph sets, which limits insight into how different search paradigms react to instance structure. We adopt an instance-landscape view of graph benchmarking by embedding graphs into a low-cost structural feature space and clustering them into regions of similar structure. Three benchmark suites are studied: weighted ErdHos--R'enyi graphs, random geometric (wireless) graphs, and real-world road networks. We evaluate four representative shortest-path solvers spanning uninformed exact search (Dijkstra), bidirectional exact search (bidirectional Dijkstra), heuristic-guided exact search (A*), and deque-based strategies (DEQ). Clustering robustness is analyzed under multiple feature-selection schemes, and runtime distributions are compared across landscape regions using non-parametric tests. While generator parameters induce stable structural regions, we find that feature-space similarity does not necessarily imply performance similarity: significant runtime shifts are frequently observed even within the same landscape region. A merged-suite analysis further shows that different benchmark families occupy largely disjoint regions. These results highlight both the potential and the limits of structural landscapes for the structure-aware benchmarking of shortest-path algorithms.