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

Resumo Técnico: Paisagens de Instâncias de Grafos

Definição do Problema
A avaliação de algoritmos de caminho mínimo é tradicionalmente conduzida através da agregação de métricas de desempenho (ex: tempo de execução médio) sobre conjuntos heterogêneos de instâncias de grafos. Embora informativa, essa abordagem oferece uma visão limitada de como a estrutura interna do espaço de instâncias influencia o comportamento algorítmico. Especificamente, permanece incerto se a similaridade estrutural entre instâncias de grafos — definida por seus parâmetros de geração e características topológicas — necessariamente se traduz em similaridade de desempenho algorítmico. Estudos existentes frequentemente analisam relações entre características e desempenho diretamente ou focam em instâncias individuais, carecendo de uma visão holística da "paisagem de instâncias" e de como mudanças sistemáticas na geração de grafos remodelam esse espaço.

Metodologia
Os autores adotam uma perspectiva de paisagem de instâncias, tratando as instâncias de grafos como pontos dentro de um espaço de características estruturais de baixo custo. A metodologia envolve três estágios primários:

1. Extração de Características e Construção da Paisagem: Três suítes de benchmarks distintos foram analisadas:

   • Grafos de Erdős–Rényi ponderados: Gerados com contagens de vértices variáveis ($|V| \in \{500, \dots, 10000\}$) e probabilidades de aresta ($p \in \{0.2, 0.3, 0.5\}$).
   • Grafos Geométricos Aleatórios (Wireless): Gerados em um quadrado unitário 2D com raios de conexão variáveis ($r \in \{0.2, 0.3, 0.5\}$) e contagens de vértices.
   • Redes de estradas do mundo real: Derivadas do OSMnx, compreendendo 25 grafos de cidades europeias e 10 redes regionais dos EUA de grande escala, estratificadas por quartis de contagem de nós.

   Cada instância foi mapeada para um vetor de características de 17 dimensões composto por métricas estruturais (ex: contagens de vértices/arestas, densidade, estatísticas de grau, assortatividade e distribuições de peso). Essas características foram selecionadas por sua eficiência computacional em relação aos algoritmos de caminho mínimo.

2. Agrupamento e Análise de Robustez: O agrupamento não supervisionado k-means foi aplicado ao espaço de características para identificar regiões de similaridade estrutural. O número ideal de clusters ($k$) foi determinado usando o coeficiente de Silhueta. Para avaliar a robustez dessas regiões da paisagem, os autores empregaram técnicas de seleção de características (filtragem de baixa variância, poda baseada em correlação e informação mútua) para gerar conjuntos de características reduzidos e compararam as estruturas de agrupamento resultantes usando matrizes de cobertura e similaridade de cosseno.

3. Correlação de Desempenho: Quatro solvers de caminho mínimo representativos foram avaliados: Dijkstra (exato não informado), Dijkstra Bidirecional, A* (exato guiado por heurística) e DEQ (baseado em deque). Para clusters onde diferentes parâmetros de geração resultaram em 100% de sobreposição de instâncias, testes estatísticos não paramétricos (Anderson–Darling e Kolmogorov–Smirnov) foram aplicados para comparar as distribuições de tempo de execução. Isso testou se a similaridade estrutural no espaço de características implica similaridade de desempenho.

Principais Resultados

• Regiões Estruturais Estáveis: Parâmetros de geradores induzem regiões estruturais estáveis na paisagem de características. Para benchmarks sintéticos (Aleatórios e Geométricos), combinações específicas de parâmetros (ex: alta densidade ou raios de conexão específicos) mapeiam consistentemente para um único cluster, frequentemente tornando as variações no tamanho do grafo indistinguíveis após a normalização. Grafos do mundo real mostraram uma separação clara baseada em escala, com redes regionais dos EUA formando clusters distintos de redes urbanas europeias.
• Sensibilidade da Seleção de Características: A robustez do agrupamento variou conforme o benchmark. Grafos Geométricos exibiram alta estabilidade entre diferentes subconjuntos de características, enquanto os grafos Aleatórios mostraram maior sensibilidade à redução de características, com alguns clusters se fragmentando ou sendo redistribuídos.
• Dissociação de Estrutura e Desempenho: Um achado central é que a similaridade estrutural não garante similaridade de desempenho. Mesmo quando instâncias de diferentes configurações de parâmetros colapsaram em um mesmo cluster (100% de cobertura), mudanças significativas nas distribuições de tempo de execução foram frequentemente observadas.
  • Dependência de Algoritmo: O A* demonstrou a maior estabilidade, mostrando diferenças de desempenho não significativas em vários casos de variação estrutural leve. Em contraste, o Dijkstra, o Dijkstra Bidirecional e o DEQ exibiram consistentemente mudanças de tempo de execução estatisticamente significativas através das mesmas regiões da paisagem.
  • Efeitos de Escala: As características estruturais escolhidas falharam em capturar totalmente os efeitos de escala que impulsionam as diferenças de desempenho, particularmente para estratégias de busca exaustiva.
• Famílias de Benchmarks Disjuntas: Ao fundir todas as suítes de benchmarks, as instâncias de fontes Aleatórias, Geométricas e do Mundo Real ocuparam regiões amplamente disjuntas no mapeamento de baixa dimensão (visualizado via t-SNE), indicando que essas famílias possuem características estruturais fundamentalmente diferentes que não se sobrepõem.

Significância e Alegações
O artigo alega contribuir com uma "compreensão fundamentada e consciente da estrutura" do desempenho de algoritmos em problemas de grafos. Ao ir além dos benchmarks agregados para uma visão de paisagem de instâncias, o estudo destaca tanto o potencial quanto os limites do uso de características estruturais para benchmarking.

Os autores afirmam modestamente que, embora a análise de paisagem possa identificar regiões de redundância e separabilidade estrutural, ela não pode prever totalmente o comportamento algorítmico. Os resultados sugerem que as atuais características estruturais de baixo custo podem perder propriedades críticas relevantes ao algoritmo (como topologia fina ou hierarquia) que influenciam o tempo de execução. Consequentemente, o artigo argumenta por uma abordagem mais matizada de seleção de algoritmos e design de benchmarks que reconheça a lacuna entre similaridade estrutural e equivalência de desempenho. O estudo não pretende resolver o problema da seleção de algoritmos, mas sim fornecer um framework para visualizar e analisar a complexidade do espaço de instâncias, revelando que grafos "similares" em um espaço de características podem se comportar de maneira muito diferente sob paradigmas de busca específicos.