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

Technical Summary: Graph Instance Landscapes

Problem Statement
Benchmarking shortest-path algorithms is traditionally conducted by aggregating performance metrics (e.g., average runtime) over heterogeneous sets of graph instances. While informative, this approach offers limited insight into how the internal structure of the instance space influences algorithmic behavior. Specifically, it remains unclear whether structural similarity among graph instances—defined by their generation parameters and topological features—necessarily translates to similar algorithmic performance. Existing studies often analyze feature-performance relationships directly or focus on individual instances, lacking a holistic view of the "instance landscape" and how systematic changes in graph generation reshape this space.

Methodology
The authors adopt an instance-landscape perspective, treating graph instances as points within a low-cost structural feature space. The methodology involves three primary stages:

1. Feature Extraction and Landscape Construction: Three distinct benchmark suites were analyzed:

   • Weighted Erdős–Rényi graphs: Generated with varying vertex counts ($|V| \in \{500, \dots, 10000\}$) and edge probabilities ($p \in \{0.2, 0.3, 0.5\}$).
   • Random Geometric (Wireless) graphs: Generated in a 2D unit square with varying connection radii ($r \in \{0.2, 0.3, 0.5\}$) and vertex counts.
   • Real-world road networks: Derived from OSMnx, comprising 25 European city graphs and 10 large-scale US regional networks, stratified by node count quartiles.

   Each instance was mapped to a 17-dimensional feature vector comprising structural metrics (e.g., vertex/edge counts, density, degree statistics, assortativity, and weight distributions). These features were selected for their computational efficiency relative to shortest-path algorithms.

2. Clustering and Robustness Analysis: Unsupervised $k$-means clustering was applied to the feature space to identify regions of structural similarity. The optimal number of clusters ($k$) was determined using the Silhouette coefficient. To assess the robustness of these landscape regions, the authors employed feature selection techniques (low-variance filtering, correlation-based pruning, and mutual information) to generate reduced feature sets and compared the resulting cluster structures using coverage matrices and cosine similarity.

3. Performance Correlation: Four representative shortest-path solvers were evaluated: Dijkstra (uninformed exact), Bidirectional Dijkstra, A* (heuristic-guided exact), and DEQ (deque-based). For clusters where different generation parameters resulted in 100% instance overlap, non-parametric statistical tests (Anderson–Darling and Kolmogorov–Smirnov) were applied to compare runtime distributions. This tested whether structural similarity in the feature space implies performance similarity.

Key Results

• Stable Structural Regions: Generator parameters induce stable structural regions in the feature space. For synthetic benchmarks (Random and Geometric), specific parameter combinations (e.g., high density or specific connection radii) consistently mapped to single clusters, often rendering variations in graph size indistinguishable after normalization. Real-world graphs showed a clear separation based on scale, with US regional networks forming distinct clusters from European urban networks.
• Feature Selection Sensitivity: Clustering robustness varied by benchmark. Geometric graphs exhibited high stability across different feature subsets, whereas Random graphs showed greater sensitivity to feature reduction, with some clusters fragmenting or redistributing.
• Dissociation of Structure and Performance: A central finding is that structural similarity does not guarantee performance similarity. Even when instances from different parameter settings collapsed into the same cluster (100% coverage), significant shifts in runtime distributions were frequently observed.
  • Algorithm Dependence: A* demonstrated the greatest stability, showing non-significant performance differences in several cases of mild structural variation. In contrast, Dijkstra, Bidirectional Dijkstra, and DEQ consistently exhibited statistically significant runtime shifts across the same landscape regions.
  • Scale Effects: The chosen structural features failed to fully capture scale effects that drive performance differences, particularly for exhaustive search strategies.
• Disjoint Benchmark Families: When merging all benchmark suites, instances from Random, Geometric, and Real-world sources occupied largely disjoint regions in the low-dimensional embedding (visualized via t-SNE), indicating that these families possess fundamentally different structural characteristics that do not overlap.

Significance and Claims
The paper claims to contribute a "principled, structure-aware understanding" of algorithm performance on graph problems. By moving beyond aggregate benchmarks to an instance-landscape view, the study highlights both the potential and the limits of using structural features for benchmarking.

The authors modestly assert that while landscape analysis can identify regions of structural redundancy and separability, it cannot fully predict algorithmic behavior. The results suggest that current low-cost structural features may miss critical algorithm-relevant properties (such as fine-grained topology or hierarchy) that influence runtime. Consequently, the paper argues for a more nuanced approach to algorithm selection and benchmark design that acknowledges the gap between structural similarity and performance equivalence. The study does not claim to solve the algorithm selection problem but rather provides a framework to visualize and analyze the complexity of the instance space, revealing that "similar" graphs in a feature space can behave very differently under specific search paradigms.