Graph Neural Networks are Heuristics

Resumen Técnico: Las Redes Neuronales de Grafos son Heurísticas

Definición del Problema
El artículo aborda el Problema del Viajante de Comercio Euclídeo (TSP), un problema de optimización combinatoria canónico donde el objetivo es encontrar el ciclo hamiltoniano más corto a través de un conjunto de $n$ ciudades. Los autores desafían el paradigma prevalente donde las Redes Neuronales de Grafos (GNN) sirven meramente como auxiliares —proporcionando puntuaciones, guiando la búsqueda o imitando algoritmos de solvers clásicos—. En su lugar, el artículo postula que una GNN puede funcionar como una heurística aprendida e independiente. El desafío específico es construir un recorrido completo en una sola pasada hacia adelante (forward pass) sin depender de la decodificación autorregresiva, recompensas de aprendizaje por refuerzo, procedimientos de búsqueda explícitos (como la búsqueda de haz/beam search) o mejora local post-hoc (como el 2-opt).

Metodología
El método propuesto es un marco de GNN no autorregresivo y no supervisado que aprende a resolver instancias de TSP directamente desde la estructura geométrica del problema.

1. Objetivo y Formulación:
   El TSP se formula como la minimización de la traza del producto entre la matriz de distancias $D$ y una matriz de permutación $P$ transformada por una matriz de desplazamiento cíclico $V$. Para permitir la optimización basada en gradientes de extremo a extremo, la permutación discreta $P$ se relaja a una matriz de permutación suave $T$ utilizando la relajación Gumbel-Sinkhorn durante el entrenamiento. La función de pérdida es simplemente la longitud esperada del recorrido: $L_{TSP} = \langle D, TVT^\top \rangle$. En la inferencia, la permutación suave se convierte en una permutación rígida utilizando el algoritmo húngaro.

2. Extracción de Características con Conciencia de Simetría:
   Para asegurar que el modelo respete las simetrías del grupo euclídeo (invariancia/equivariancia de permutación y traslación), los autores introducen un extractor de características determinista.

• Invariancia de Traslación: Las coordenadas de las ciudades se centran restando la media.
• Marco Canónico: Se construye un marco ortonormal utilizando los autovectores de la matriz de covarianza empírica de los puntos centrados. Esto elimina las ambigüedades de rotación y reflexión.
• Codificación Armónica: Los puntos se proyectan sobre este marco canónico para derivar coordenadas polares intrínsecas ($r, \theta$). La información angular se codifica mediante $M$ armónicos de Fourier ($\sin(m\theta), \cos(m\theta)$), proporcionando a la GNN pistas estructurales invariantes a la rotación.

3. Arquitectura de la Red:
   El modelo central es una Red Neuronal de Grafos de Atención de Dispersión (SCT-GNN). Combina representaciones basadas en difusión (usando operadores de grafo derivados de potencias de una matriz de paseo aleatorio suavizada) con mecanismos de atención aprendibles que mezclan adaptativamente las características a través de diferentes escalas de difusión. La red es permutación-equivariante por construcción.

4. Estrategias de Ensamble para la Diversidad:
   Para generar diversidad de soluciones sin entrenar múltiples modelos o realizar una búsqueda iterativa, el artículo emplea dos mecanismos dentro de una misma trayectoria de entrenamiento:

• Dropout de Monte Carlo (MC): El dropout se aplica durante la inferencia. Al realizar múltiples pasadas estocásticas hacia adelante con diferentes máscaras de dropout, el modelo genera recorridos diversos a partir de una única instancia entrenada.
• Ensamblado de Instantáneas (Snapshot Ensembling): Se guardan múltiples puntos de control (checkpoints) en diferentes épocas durante una única ejecución de entrenamiento. Estas instantáneas, que representan puntos distintos en el paisaje de optimización, se utilizan conjuntamente en la inferencia. El mejor recorrido entre las instantáneas es el seleccionado.

Contribuciones Clave

• GNNs como Heurísticas Independientes: El artículo demuestra que una GNN puede ser una heurística completa, produciendo un recorrido válido en una sola pasada hacia adelante sin búsqueda auxiliar o refinamiento.
• Aprendizaje No Supervisado: El modelo no requiere soluciones óptimas de verdad fundamental (ground-truth) ni recompensas de aprendizaje por refuerzo; aprende únicamente minimizando el objetivo de la longitud del recorrido.
• Aprendizaje de Estructura Global: Al eliminar los mecanismos ávidos (greedy) locales y confiar en un objetivo de ciclo hamiltoniano global, el modelo aprende restricciones combinatorias no locales que las reglas de decisión puramente locales (como el vecino más cercano) pasan por alto.
• Eficiencia: El método logra una inferencia a escala de milisegundos en GPUs, ofreciendo una relación calidad-eficiencia favorable en comparación con las heurísticas clásicas y otros enfoques basados en aprendizaje que dependen de la decodificación autorregresiva o la búsqueda.

Resultados
Los experimentos se realizaron en instancias de TSP con $n=100, 200$ y $500$ nodos extraídos de una distribución euclídea uniforme.

• Rendimiento vs. Greedy: El modelo supera consistentemente al baseline de Vecino Más Cercano (NN) Greedy. Para el TSP100, la longitud media del recorrido mejoró de 9.67 (Greedy) a 8.18 (GNN Determinista).
• Rendimiento vs. Heurísticas Clásicas: El método supera significativamente a la heurística de Christofides en instancias pequeñas (TSP100, TSP200) y iguala a esta en TSP500, pero con tiempos de inferencia órdenes de magnitud menores en GPUs.
• Rendimiento vs. Baselines Basados en Aprendizaje: Comparado con los baselines de Aprendizaje por Refuerzo (RL) y Aprendizaje Supervisado (SL) (ej. GAT, GCN), el método propuesto logra brechas de optimalidad competitivas o superiores (ej. brecha del 4.39% en TSP100 frente al 2.48% de un fuerte baseline de RL con búsqueda de haz) siendo significativamente más rápido debido a que evita la decodificación autorregresiva y la búsqueda de haz.
• Efectos de Ensamblado: Tanto el dropout de MC como el ensamblado de instantáneas reducen aún más la brecha de optimalidad. La combinación de ambas estrategias produjo los mejores resultados (brecha del 4.39% en TSP100, 8.25% en TSP200, 12.11% en TSP500) manteniendo los tiempos de inferencia en el régimen de milisegundos (hasta ~82ms para el ensamble combinado en TSP500).

Significado y Reivindicaciones
El artículo sostiene que las heurísticas no necesitan ser reglas diseñadas a mano o procedimientos de búsqueda, sino que pueden emerger directamente del aprendizaje de la estructura del problema. Al formular el TSP como un aprendizaje directo de permutación con un objetivo de ciclo hamiltoniano diferenciable, los autores muestran que las GNN pueden interiorizar las restricciones combinatorias globales. El significado radica en el cambio de paradigma de la optimización combinatoria: las restricciones estructurales y los modelos generativos pueden reemplazar la búsqueda explícita como base para resolver problemas intratables. Los resultados sugieren que las "heurísticas aprendidas" pueden rivalizar o incluso superar a los métodos clásicos de ingeniería tanto en calidad de solución como en eficiencia computacional, particularmente cuando el costo de la búsqueda es prohibitivo. El trabajo posiciona a las GNN no supervisadas como una nueva clase de heurísticas rápidas y aprendidas para la optimización combinatoria.