Research from the AutoLearn-SI team was presented at IEEE CEC 2026 by Maryam Gholami Shiri (member of our department), co-authored with Ivana Krminac, Marko Djukanovic, Sašo Džeroski, Eva Tuba, and Tome Eftimov.

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

The study investigates whether the structural similarity of graph instances accounts for the performance of shortest-path algorithms.

An instance-landscape framework was introduced to benchmark shortest-path algorithms by embedding graph instances into a structural feature space and analyzing algorithmic behavior across structurally similar regions. The evaluation covered four representative shortest-path algorithms across weighted Erdős–Rényi graphs, random geometric (wireless) graphs, and real-world road networks.

The findings indicate that structural similarity does not consistently correlate with similar algorithmic performance. Substantial runtime variations occurred even within identical structural landscape regions, demonstrating both the utility and the limitations of structure-aware benchmarking.

This study offers new insights into graph benchmarking and underscores the necessity of considering factors beyond structural characteristics when designing representative benchmark suites for shortest-path algorithms.