Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Resumen Técnico: Encadenamiento de GNNs 2-FWL para el Alineamiento Combinatorio de Grafos

Definición del Problema
El artículo aborda el Problema de Alineamiento de Grafos Combinatorios (GAP), que busca encontrar la correspondencia de nodos entre dos grafos no etiquetados ($G_A$ y $G_B$) que maximice el número de aristas comunes (nce). Formalmente, esto es equivalente a minimizar la norma de Frobenius $\|AP - PB\|_F^2$ sobre el conjunto de matrices de permutación $P$, o maximizar la forma cuadrática $\langle AP, PB \rangle$. Este problema es una instancia específica del Problema de Asignación Cuadrática (QAP), conocido por ser NP-duro.

Los autores se centran estrictamente en el entorno puramente estructural, donde los grafos no poseen características de nodo más allá de su topología. En este régimen, los enfoques existentes de Redes Neuronales de Grafos (GNN) han tenido dificultades para igualar el rendimiento de bases clásicas sólidas, específicamente el algoritmo Fast Approximate Quadratic (FAQ) [Vogelstein et al., 2015], que resuelve una relajación continua del QAP mediante optimización de Frank-Wolfe.

Metodología: Encadenamiento con Retroalimentación Discreta
La contribución central es un procedimiento de encadenamiento que entrena secuencialmente una serie de GNNs de tipo Folklore (GNNs 2-FWL) para generar matrices de similitud cada vez más precisas, las cuales sirven como inicializaciones para el algoritmo FAQ.

1. Bucle de Refinamiento Iterativo:

   • Paso 1 (Extracción de Características): Una GNN inicial ($f$) extrae características de los nodos a partir de las matrices de adyacencia y computa una matriz de similitud $S^{(0)}$.
   • Paso 2 (Decodificación y Clasificación): La matriz de similitud se decodifica en una permutación $\pi$ mediante un resolvedor de asignación lineal (Proyección). Crucialmente, el artículo introduce un paso de clasificación no diferenciable: los nodos se clasifican según su "calidad de alineamiento" (el número de aristas emparejadas por la permutación actual). Esto inyecta retroalimentación combinatoria discreta en el flujo de trabajo.
   • Paso 3 (Aprendizaje Mejorado por Clasificación): Una GNN subsecuente ($g^{(k)}$) toma la estructura del grafo y las clasificaciones de los nodos como entrada para computar una matriz de similitud mejorada $S^{(k)}$. Se espera que esta matriz sea más informativa que la anterior porque incorpora el conocimiento de qué nodos se están alineando bien actualmente.

2. Entrenamiento Secuencial:
   Debido a que el paso de clasificación es no diferenciable, las GNNs no pueden entrenarse de extremo a extremo (end-to-end). En su lugar, se entrenan secuencialmente:

   • Entrenar $f$ para minimizar la pérdida de entropía cruzada contra la permutación de verdad fundamental (ground-truth).
   • Fijar $f$, computar las clasificaciones en el conjunto de entrenamiento, y luego entrenar $g^{(1)}$ para minimizar la pérdida contra la verdad fundamental utilizando las nuevas clasificaciones.
   • Repetir para $g^{(2)}, \dots, g^{(L)}$.
     Cada red aprende a mejorar la calidad del alineamiento lograda por la red anterior en la cadena.

3. Inferencia con Bucle (Looping):
   En la inferencia, la red final entrenada $g^{(L)}$ puede aplicarse iterativamente (looping). Después de cada pasada, se genera una permutación candidata, y se conserva aquella con el mayor nce observado. Este "looping" actúa como un refinamiento heurístico sin necesidad de entrenamiento adicional.

4. Arquitectura (FGNN):
   Los autores emplean GNNs de tipo Folklore (FGNN), que operan sobre pares de nodos en lugar de nodos individuales. Esta arquitectura logra una expresividad 2-FWL (2-Folklore Weisfeiler-Leman). Esto es crítico porque las MPNN estándar están limitadas a una expresividad 1-WL y fallan al distinguir nodos en grafos regulares (donde todos los nodos tienen vecindarios locales idénticos), lo que conduce a matrices de similitud degeneradas.

Contribuciones Clave

• Procedimiento de Encadenamiento: Un nuevo paradigma de entrenamiento que cierra la brecha entre la optimización combinatoria discreta y el aprendizaje continuo de GNN mediante el uso de clasificaciones discretas como señales de retroalimentación.
• Mejores Inicializaciones para FAQ: El método aprende a proporcionar a FAQ matrices de similitud que son inicializaciones significativamente mejores que la relajación convexa estándar ($D_{cx}$), particularmente en instancias difíciles.
• Análisis de Expresividad: El artículo demuestra que la expresividad 2-FWL es necesaria para el entorno puramente estructural, ya que las MPNN basadas en 1-WL fallan en grafos regulares y grafos dispersos con alto ruido.
• Reevaluación de Bases (Baselines): Los autores argumentan que las comparaciones previas en la literatura a menudo subestiman a FAQ al inicializarlo con una matriz doblemente estocástica uniforme en lugar de la solución de la relajación convexa ($D_{cx}$). Cuando se inicializa adecuadamente, FAQ es una base mucho más fuerte de lo reportado anteriormente.

Resultados
El método fue evaluado en grafos aleatorios correlacionados sintéticos (Erdős–Rényi dispersos, Erdős–Rényi densos y grafos regulares) y tres benchmarks del mundo real (Yeast PPI, Coauthorship, Redes de carreteras).

• Grafos Erdős–Rényi Dispersos: Con un nivel de ruido de 0.25, el ChFGNN encadenado con post-procesamiento FAQ (ChFGNN FAQ) alcanzó un 85% de precisión, comparado con el 13% de FAQ inicializado desde la relajación convexa y esencialmente un 0% de los métodos GNN previos.
• Grafos Regulares: Este es un régimen donde los métodos estándar fallan por completo. La relajación convexa produce una solución degenerada (el baricentro) y las MPNN producen embeddings idénticos. El ChFGNN es el único método reportado que recupera un alineamiento no trivial, logrando un 56% de precisión con un nivel de ruido de 0.1, mientras que todos los demás métodos fallaron.
• Benchmarks del Mundo Real: En los conjuntos de datos del mundo real, los ChFGNNs mejoraron la base fortalecida de FAQ (FAQ inicializado desde $D_{cx}$) por aproximadamente un 2% en términos de nce en entornos de alto ruido.
• Eficiencia: Aunque el procedimiento de encadenamiento requiere entrenamiento basado en GPU, el paso de inferencia reduce significamente el número de iteraciones de Frank-Wolfe requeridas por FAQ en comparación con el uso directo de la relajación convexa, lo que indica una inicialización de mayor calidad.

Significancia y Reivindicaciones
El artículo sostiene que el refinamiento iterativo con retroalimentación combinatoria discreta es una dirección prometedora para problemas combinatorios con una interpretación natural de clasificación. Los autores no pretenden que su método se transfiera sin modificaciones a problemas de optimización combinatoria arbitrarios.

La significancia principal radica en demostrar que las representaciones aprendidas pueden mejorar el estado del arte de los resolvedores clásicos (FAQ) en el entorno puramente estructural, un dominio donde las GNN históricamente han tenido un bajo rendimiento. El trabajo destaca que el fallo de las GNN previas se debió en parte a una expresividad insuficiente (limitaciones de 1-WL) y en parte a la falta de un mecanismo para incorporar retroalimentación estructural discreta. Al encadenar GNNs 2-FWL, los autores superan con éxito estas barreras, logrando resultados de vanguardia en instancias difíciles de grafos dispersos y regulares.