Resumen Técnico: Comprensión de los Codificaciones Posicionales Truncadas para Redes Neuronales de Grafos

Planteamiento del Problema

Las Redes Neuronales de Grafos (GNN), particularmente las Redes Neuronales de Paso de Mensajes (MPNN), están fundamentalmente limitadas en su capacidad para capturar información estructural global, una restricción formalizada por su equivalencia con la prueba 1-WL (Weisfeiler-Lehman). Para superar esto, los Transformers de Grafos (GT) y las GNN mejoradas utilizan Codificaciones Posicionales (PE) para inyectar información estructural. Dos familias dominantes de PE son las codificaciones espectrales (derivadas de los espacios propios del Laplaciano) y las codificaciones basadas en paseos (derivadas de las potencias de la matriz de adyacencia).

Teóricamente, las versiones completas de estas codificaciones (usando $\Omega(n)$ vectores propios o potencias de matrices) son equivalentes en poder expresivo, situándose entre las pruebas 1-WL y 3-WL. Sin embargo, computar estas codificaciones completas requiere una complejidad de tiempo y espacio de $O(n^3)$, lo cual es prohibitivo para aplicaciones del mundo real. En consecuencia, los profesionales recurren a variantes truncadas (por ejemplo, los primeros $k$ vectores propios o las primeras $k$ potencias de la matriz de adyacencia). Las propiedades teóricas, el poder expresivo y las fortalezas comparativas de estas PE truncadas permanecen mayormente inexploradas, creando una brecha entre las garantías teóricas y la implementación práctica.

Metodología

Los autores inician un estudio sistemático de las PE truncadas a través de análisis tanto teóricos como de validación empírica.

Marco Teórico

El artículo utiliza la jerarquía WL y sus variantes para caracterizar el poder expresivo de diferentes PE:

• Prueba $\psi$-WL: Una variante de la prueba WL donde los colores de los nodos se actualizan utilizando una codificación posicional relativa (RPE) $\psi$.
• Prueba Sparse-$\psi$-WL: Una extensión para MPNN donde $\psi$ se utiliza como características de arista.
• Familias Clave Analizadas:
  1. Proyecciones de Espacio Propio Truncadas ($k$-EP-WL): Usando las primeras $k$ proyecciones del espacio propio del Laplaciano.
  2. Codificaciones de Paseo Truncadas ($k$-Walk-WL): Usando las primeras $k$ potencias de la matriz de adyacencia.
  3. Resistencia Efectiva (Resistance-WL): Una distancia espectral específica (distancia 1-armónica).
  4. Distancias $k$-Armónicas: Una generalización de la resistencia efectiva definida como $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$.

Los autores construyen pares de grafos específicos (por ejemplo, productos de grafos de caminos y grafos completos, o ciclos frente a uniones disjuntas de ciclos) para demostrar la separabilidad o indistinguibilidad bajo diferentes PE truncadas y pruebas WL.

Evaluación Empírica

Los experimentos se realizaron en tres bancos de pruebas:

1. BREC: Un conjunto de datos diseñado para medir la "expresividad realizada" de las GNN mediante la prueba de su capacidad para distinguir grafos no isomorfos que van desde indistinguibles por 1-WL hasta 4-WL.
2. ZINC-12k: Un benchmark de regresión de grafos para la solubilidad molecular, utilizado para probar la hipótesis de que mezclar PE truncadas mejora el rendimiento.
3. ogbg-molhiv: Un benchmark de clasificación binaria para la inhibición del VIH.

Los autores evaluaron arquitecturas Graphormer-GD y MPNN (GINE) utilizando diversas combinaciones de PE truncadas, incluyendo familias individuales y mezclas de codificaciones espectrales, de paseos y $k$-armónicas.

Contribuciones Claves y Resultados

1. Divergencia del Poder Expresivo en Formas Truncadas

El artículo demuestra que, si bien las codificaciones espectrales y de paseos completas son equivalentes, sus formas truncadas son fundamentalmente diferentes:

• Espectral Truncada vs. 1-WL: Los autores muestran que las proyecciones de espacio propio truncadas ($k$-EP-WL) pueden ser más débiles que la prueba 1-WL. Específicamente, existen pares de grafos distinguibles por 1-WL pero indistinguibles por $k$-EP-WL para $k \in \Omega(n)$ (Teorema 4.1).
• Paseo Truncado vs. Espectral: Por el contrario, existen pares de grafos distinguibles por una sola proyección de espacio propio (1-EP-WL) pero indistinguibles por codificaciones de paseos de tamaño $\Omega(n)$ (Teorema 4.2).
• Implicación: Ninguna familia de PE truncada es estrictamente superior; capturan diferentes aspectos estructurales y pueden ser incomparables con la jerarquía WL estándar.

2. Limitaciones de la Resistencia Efectiva

El artículo analiza la Resistencia Efectiva (distancia 1-armónica) y encuentra que es una PE más débil que las proyecciones de espacio propio completas o las codificaciones de paseos en grafos ponderados.

• Teorema 4.3: Existen grafos ponderados indistinguibles por Resistance-WL pero distinguibles por Adjacency-WL (y, por tanto, 1-WL en grafos no ponderados).
• Corolario 4.1: Resistance-WL no codifica todo el espectro del grafo, refutando una conjetura previa.

3. Distancias $k$-Armónicas como un Puente

Los autores introducen las distancias $k$-armónicas como un puente natural entre las codificaciones espectrales y las polinómicas.

• Completitud: La concatenación de $\Theta(n)$ distancias $k$-armónicas produce una codificación equivalente en poder a las codificaciones espectrales o de paseos completas (Teorema 4.6).
• Poder Diferencial: Incluso dentro de la familia $k$-armónica, las codificaciones de tamaño fijo difieren. Por ejemplo, la distancia biarmónica (2-armónica) puede distinguir ciertos pares de árboles en un número constante de iteraciones, mientras que la resistencia efectiva (1-armónica) requiere $O(n)$ iteraciones (Teorema 4.7).
• Robustez: Sin embargo, si una distancia $k$-armónica distingue un par de grafos, la mayoría de las otras distancias $k$-armónicas también los distinguirán (Teorema 4.8).

4. Hallazgos Empíricos: El Poder de la Mezcla

• Resultados de BREC: Las distancias $k$-armónicas lograron resultados competitivos con codificaciones de canal único y baja sobrecarga, igualando a menudo el techo teórico para grafos entre 1-WL y 3-WL.
• Resultados de ZINC: El hallazgo más significativo es que mezclar PE de diferentes familias (por ejemplo, combinando paseos truncados y $k$-armónicos) supera a cualquier familia individual. Una mezcla de paseos truncados y $k$-armónicos logró el Error Absoluto Medio (MAE) más bajo en ZINC-12k, superando las líneas base de una sola familia.
• Eficiencia: El artículo señala que las distancias $k$-armónicas pueden aproximarse en $O(mk \cdot \text{poly}(\log n))$ tiempo utilizando solucionadores rápidos de Laplaciano y proyecciones de Johnson-Lindenstrauss, evitando el costo de $O(n^3)$ de la computación exacta.

Significado y Reivindicaciones

El artículo afirma iniciar el estudio teórico de las codificaciones posicionales truncadas, cambiando la perspectiva de verlas meramente como aproximaciones de codificaciones completas a verlas como un espacio de diseño distinto con propiedades expresivas únicas.

• Perspectiva Teórica: El trabajo demuestra que la truncación altera fundamentalmente la información capturada por las PE, haciéndolas incomparables con la jerarquía WL estándar en casos específicos.
• Guía Práctica: Los autores proponen una regla de oro: mezcle PE de diferentes familias cuando utilice codificaciones truncadas. Este enfoque captura pistas estructurales complementarias mientras controla los costos computacionales.
• Alcance Modesto: Los autores reconocen que, si bien el isomorfismo de grafos es un proxy principled, las tareas del mundo real involucran señales descendentes (centralidad, motivos) que pueden no alinearse estrictamente con las pruebas de isomorfismo. Por lo tanto, la contribución principal es establecer una base teórica y un punto de partida para un estudio empírico sistemático, en lugar de reclamar una solución universal para todas las tareas de aprendizaje de grafos.