Graph Hierarchical Recurrence for Long-Range Generalization

Resumen Técnico: Recurrencia Jerárquica en Grafos para Generalización de Largo Alcance

Enunciado del Problema
Las Redes Neuronales de Grafos (GNN) y los Transformadores de Grafos (GT) se han consolidado como el estándar para el aprendizaje en grafos, sin embargo, enfrentan limitaciones fundamentales en tareas que requieren capturar correlaciones entre regiones distantes del grafo. Los modelos existentes padecen tres patologías principales:

1. Aplastamiento excesivo (Over-squashing): La compresión de un campo receptivo que crece exponencialmente en representaciones de nodos de tamaño fijo.
2. Suavizado excesivo (Over-smoothing): La convergencia de las características de los nodos hacia incrustaciones homogéneas e indistinguibles.
3. Desvanecimiento de gradientes: Dificultad en el entrenamiento de Redes Neuronales de Paso de Mensajes (MPNN) profundas, lo que obstaculiza el flujo de información a través de grandes distancias.

Aunque existen soluciones como el reencuadre de grafos (introducción de aristas artificiales) y los Transformadores de Grafos (uso de atención global), estas introducen nuevos problemas: el reencuadre distorsiona los sesgos inductivos topológicos, y los mecanismos de atención incurren en una complejidad computacional cuadrática, limitando la escalabilidad. Además, el artículo distingue entre generalización dentro del rango (propagación de información sobre distancias vistas durante el entrenamiento) y generalización fuera del rango (extrapolación a distancias más largas que las observadas). Los modelos actuales a menudo fallan en la generalización fuera del rango, degradándose rápidamente cuando las instancias de prueba involucran distancias de interacción que exceden el horizonte de entrenamiento.

Metodología: Recurrencia Jerárquica en Grafos (GHR)
Los autores proponen la Recurrencia Jerárquica en Grafos (GHR), un marco que combina el cálculo recurrente con representaciones de grafos multiescala para abordar la generalización de largo alcance y fuera del rango sin distorsionar la topología ni incurrir en complejidad cuadrática.

• Jerarquía de Dos Niveles: GHR opera en dos niveles: un grafo de bajo nivel ($G_L$) que representa la entrada original, y un grafo de alto nivel ($G_H$) obtenido mediante un mapa de agrupación (por ejemplo, Graclus o partición de bloques geométrica). El mapa de agrupación es 1-Lipschitz, asegurando que el diámetro de $G_H$ sea menor o igual que el de $G_L$, reduciendo así el número de pasos necesarios para abarcar el grafo.
• Esquema Recurrente Anidado: El núcleo de GHR es un paso recurrente global ($R_W$) que actualiza iterativamente los estados ocultos para ambos niveles. Este paso emplea un esquema recurrente de dos escalas temporales:
  • Flujo de Alto Nivel: Propaga información en el grafo agrupado y más grueso $G_H$ ($T_H$ pasos). Este flujo actúa como un "atajo" para la comunicación de largo alcance.
  • Flujo de Bajo Nivel: Propaga información en el grafo original $G_L$ ($T_L$ pasos).
  • Acoplamiento: Los flujos están estrechamente acoplados. El flujo de alto nivel guía al flujo de bajo nivel mediante desagrupación (difusión de características de alto nivel de vuelta a los nodos de bajo nivel), mientras que el flujo de bajo nivel informa al flujo de alto nivel mediante agrupación.
• Agnosticismo Arquitectónico: El marco es agnóstico a la función específica de paso de mensajes utilizada (por ejemplo, GINE, GCN, GAT, GatedGCN). Utiliza mapas lineales aprendibles para la codificación de entrada y RMSNorm para estabilizar las magnitudes de las características.
• Estrategia de Entrenamiento: El modelo se entrena utilizando Retropropagación a través del Tiempo (BPTT) con una pérdida temporalmente descontada. Este enfoque aplica la pérdida en cada paso recurrente, ponderando los pasos posteriores más pesadamente para prevenir el desvanecimiento de gradientes mientras permite un refinamiento progresivo.

Contribuciones Clave

1. Marco Novel: Introducción de GHR, una arquitectura recurrente de dos niveles que utiliza agrupación de grafos para crear una jerarquía con dos flujos de paso de mensajes, permitiendo una propagación eficiente de largo alcance mientras preserva el sesgo inductivo de la topología subyacente.
2. Generalización Fuera del Rango: Demostración de que GHR puede extrapolarse a distancias de interacción significativamente más largas que las observadas durante el entrenamiento, una capacidad donde fallan los modelos existentes basados en alimentación directa y atención.
3. Eficiencia de Parámetros: Validación de que GHR logra un rendimiento de vanguardia o competitivo utilizando del 1% al 10% de los parámetros entrenables de los modelos actuales de vanguardia.
4. Análisis de Ablación: Evidencia de que tanto la estructura jerárquica como el mecanismo recurrente son necesarios para la generalización fuera del rango; los modelos recurrentes planos fallan en la precisión dentro del rango, mientras que los modelos de alimentación directa profundos fallan fuera del rango.

Resultados Experimentales
Los autores evaluaron GHR en diversos benchmarks:

• Benchmark ECHO: GHR logró resultados de vanguardia en tareas algorítmicas (SSSP, Excentricidad, Diámetro) y resultados competitivos en tareas químicas (cargas basadas en DFT, energías moleculares), utilizando órdenes de magnitud menos parámetros que líneas base como GPS, GRIT y SWAN.
• Benchmark LRIM: En el Modelo de Ising de Largo Alcance, GHR igualó el rendimiento de la línea base en tareas de distribución interna y logró una extrapolación superior en cero-shot a tamaños de red más grandes (por ejemplo, entrenando en 16x16 y probando en 256x256), mientras que los modelos basados en atención sufrieron errores de memoria insuficiente o degradación del rendimiento.
• Grafos Geométricos Aleatorios (RGG): En experimentos controlados fuera del rango, GHR mantuvo un Error Absoluto Medio (MAE) cercano a cero en distancias de camino más corto de hasta 40 saltos cuando se entrenó solo con distancias de hasta 20 saltos. Por el contrario, las líneas base GIN y GPS profundas se degradaron linealmente más allá de su profundidad de entrenamiento.

Significado y Afirmaciones
El artículo afirma que GHR ofrece una dirección complementaria a la tendencia actual de escalar arquitecturas para crear modelos fundacionales de grafos. Los resultados sugieren que el aumento de la capacidad del modelo por sí solo no es suficiente para la generalización, particularmente para tareas fuera del rango. En cambio, los mecanismos arquitectónicos que apoyan el razonamiento jerárquico y la recurrencia son críticos.

Los autores posicionan a GHR como un método principiado para escalar la profundidad recurrente sin aumentar el tamaño del modelo, mitigando efectivamente el aplastamiento excesivo y el suavizado excesivo mientras se preserva la integridad topológica. Concluyen que combinar la recurrencia con representaciones jerárquicas es un camino prometedor hacia sistemas de aprendizaje en grafos escalables y generalizables, aunque señalan que extender la jerarquía más allá de dos niveles y caracterizar el poder expresivo de tales modelos siguen siendo direcciones abiertas para trabajo futuro.