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

Resumen Técnico: Paisajes de Instancias de Grafos

Planteamiento del Problema
La evaluación comparativa de algoritmos de ruta más corta se realiza tradicionalmente agregando métricas de rendimiento (por ejemplo, el tiempo de ejecución promedio) sobre conjuntos heterogéneos de instancias de grafos. Si bien esto es informativo, ofrece una visión limitada de cómo la estructura interna del espacio de instancias influye en el comportamiento algorítmico. Específicamente, no está claro si la similitud estructural entre las instancias de grafos —definida por sus parámetros de generación y características topológicas— se traduce necesariamente en una similitud de rendimiento algorítmico. Los estudios existentes suelen analizar las relaciones entre características y rendimiento de forma directa o se centran en instancias individuales, careciendo de una visión holística del "paisaje de instancias" y de cómo los cambios sistemáticos en la generación de grafos remodelan este espacio.

Metodología
Los autores adoptan una perspectiva de paisaje de instancias, tratando las instancias de grafos como puntos dentro de un espacio de características estructurales de bajo costo. La metodología consta de tres etapas principales:

1. Extracción de Características y Construcción del Paisaje: Se analizaron tres conjuntos de pruebas distintos:

   • Grafos de Erdős–Rényi ponderados: Generados con variaciones en el número de vértices ($|V| \in \{500, \dots, 10000\}$) y probabilidades de aristas ($p \in \{0.2, 0.3, 0.5\}$).
   • Grafos Geométricos Aleatorios (Wireless): Generados en un cuadrado unitario 2D con radios de conexión variables ($r \in \{0.2, 0.3, 0.5\}$) y conteos de vértices.
   • Redes viales del mundo real: Derivadas de OSMnx, que comprenden 25 grafos de ciudades europeas y 10 redes regionales de gran escala de EE. UU., estratificadas por cuartiles de número de nodos.

   Cada instancia fue mapeada a un vector de características de 17 dimensiones que comprende métricas estructurales (por ejemplo, conteos de vértices/aristas, densidad, estadísticas de grado, asortatividad y distribuciones de peso). Estas características fueron seleccionadas por su eficiencia computacional en relación con los algoritmos de ruta más corta.

2. Agrupamiento (Clustering) y Análisis de Robustez: Se aplicó un agrupamiento k-means no supervisado al espacio de características para identificar regiones de similitud estructural. El número óptimo de grupos ($k$) se determinó mediante el coeficiente de Silueta. Para evaluar la robustez de estas regiones del paisaje, los autores emplearon técnicas de selección de características (filtrado de baja varianza, poda basada en correlación y de información mutua) para generar conjuntos de características reducidos y compararon las estructuras de agrupamiento resultantes utilizando matrices de cobertura y similitud de coseno.

3. Correlación de Rendimiento: Se evaluaron cuatro solucionadores de ruta más corta representativos: Dijkstra (exacto no informado), Dijkstra Bidireccional, A* (exacto guiado por heurística) y DEQ (basado en cola de doble extremo). Para los grupos donde diferentes parámetros de generación resultaron en un 100% de superposición de instancias, se aplicaron pruebas estadísticas no paramétricas (Anderson–Darling y Kolmogorov–Smirnov) para comparar las distribuciones de tiempo de ejecución. Esto probó si la similitud estructural en el espacio de características implica similitud de rendimiento.

Resultos Clave

• Regiones Estructurales Estables: Los parámetros del generador inducen regiones estructurales estables en el espacio de características. Para las pruebas sintéticas (Aleatorias y Geométricas), combinaciones específicas de parámetros (por ejemplo, alta densidad o radios de conexión específicos) mapearon consistentemente a un solo grupo, haciendo que las variaciones en el tamaño del grafo fueran indistinguibles tras la normalización. Los grafos del mundo real mostraron una clara separación basada en la escala, con las redes regionales de EE. UU. formando grupos distintos de las redes urbanas europeas.
• Sensibilidad de la Selección de Características: La robustez del agrupamiento varió según el benchmark. Los grafos Geométricos exhibieron una alta estabilidad a través de diferentes subconjuntos de características, mientras que los grafos Aleatorios mostraron una mayor sensibilidad a la reducción de características, con algunos grupos fragmentándose o redistribuyéndose.
• Disociación de Estructura y Rendimiento: Un hallazgo central es que la similitud estructural no garantiza la similitud de rendimiento. Incluso cuando instancias de diferentes configuraciones de parámetros colapsaron en el mismo grupo (100% de cobertura), se observaron frecuentemente cambios significativos en las distribuciones de tiempo de ejecución.
  • Dependencia del Algoritmo: A* demostró la mayor estabilidad, mostrando diferencias de rendimiento no significativas en varios casos de variación estructural leve. En contraste, Dijkstra, Dijkstra Bidireccional y DEQ exhibieron consistentemente cambios de tiempo de ejecución estadísticamente significativos a través de las mismas regiones del paisaje.
  • Efectos de Escala: Las características estructurales elegidas no lograron capturar plenamente los efectos de escala que impulsan las diferencias de rendimiento, particularmente para las estrategias de búsqueda exhaustiva.
• Familias de Benchmarks Disjuntas: Al fusionar todos los conjuntos de pruebas, las instancias de fuentes Aleatorias, Geométricas y del Mundo Real ocuparon regiones ampliamente disjuntas en el embebido de baja dimensión (visualizado mediante t-SNE), lo que indica que estas familias poseen características estructurales fundamentalmente diferentes que no se traslapan.

Significancia y Reivindicaciones
El artículo afirma contribuir con una "comprensión fundamentada y consciente de la estructura" sobre el rendimiento de los algoritmos en problemas de grafos. Al ir más allá de los benchmarks agregados hacia una visión de paisaje de instancias, el estudio destaca tanto el potencial como los límites de utilizar características estructurales para la evaluación comparativa.

Los autores afirman modestamente que, si bien el análisis de paisajes puede identificar regiones de redundancia y separabilidad estructural, no puede predecir completamente el comportamiento algorítmico. Los resultados sugieren que las características estructurales de bajo costo actuales pueden omitir propiedades críticas relevantes para el algoritmo (como la topología fina o la jerarquía) que influyen en el tiempo de ejecución. En consecuencia, el artículo aboga por un enfoque más matizado para la selección de algoritmos y el diseño de benchmarks que reconozca la brecha entre la similitud estructural y la equivalencia de rendimiento. El estudio no pretende resolver el problema de la selección de algoritmos, sino que proporciona un marco para visualizar y analizar la complejidad del espacio de instancias, revelando que grafos "similares" en un espacio de características pueden comportarse de manera muy diferente bajo paradigmas de búsqueda específicos.