Structural Graph Similarity Doesn't Predict Shortest-Path Performance, Study Finds

A team led by Maryam Gholami Shiri and colleagues from the Jožef Stefan Institute and University of Montenegro has published a paper that challenges a common assumption in algorithm benchmarking: that structurally similar graphs will yield similar performance for shortest-path algorithms. The study, accepted at the 2026 IEEE Congress on Evolutionary Computation, embeds graphs into a low-cost structural feature space and clusters them into regions of similar structure. They evaluated four representative shortest-path solvers – Dijkstra, bidirectional Dijkstra, A*, and deque-based (DEQ) strategies – across three benchmark suites: weighted Erdős–Rényi graphs, random geometric graphs (modeling wireless networks), and real-world road networks.

The key finding is that while generator parameters (e.g., edge probability, node distribution) create stable structural clusters, the runtime distributions within a single cluster frequently show statistically significant variation. This means two graphs with nearly identical structural features can lead to drastically different algorithm speeds. The researchers also found that different benchmark families (synthetic vs. real-world) occupy largely disjoint regions in the feature space, making cross-family comparison difficult. These results underscore both the potential and the limits of using structural landscapes for predicting algorithm performance, suggesting that more nuanced metrics or per-instance analysis may be needed for robust benchmarking.