At the IEEE Congress on Evolutionary Computation (IEEE CEC 2026), Maryam Gholami Shiri, together with Ivana Krminac, Marko Djukanović, Sašo Džeroski, Eva Tuba, and Tome Eftimov, presented the paper “Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance.”

The research investigates a fundamental question in graph algorithm analysis: Can the structural similarity of graph instances explain the performance of shortest-path algorithms?

To address this, the authors propose an instance-landscape approach that embeds graph instances into a structural feature space, enabling the analysis of algorithm behavior across regions of similar graph structure. The study considers three diverse graph families—weighted Erdős–Rényi graphs, random geometric (wireless) graphs, and real-world road networks—and evaluates four representative shortest-path algorithms.

The results reveal that structural similarity alone is not a reliable predictor of algorithmic performance. Although graph instances may appear similar in the structural feature space, significant differences in runtime can still emerge. These findings demonstrate both the value and the limitations of structure-aware benchmarking and highlight the need for richer methodologies that capture multiple factors influencing algorithm behavior.

The presented work contributes to a deeper understanding of graph benchmarking and provides a foundation for developing more informative, representative, and interpretable evaluation frameworks for shortest-path algorithms.