Resumen Técnico: Red Neuronal de Grafos de Espectro Completo: Expresiva y Escalable

Enunciado del Problema

Las Redes Neuronales de Grafos (GNN) espectrales estándar parametrizan la propagación en grafos como filtrado Laplaciano. Si bien está establecido que las GNN espectrales pueden aproximar universalmente señales de nodos, su poder expresivo para distinguir grafos no isomorfos está estrictamente limitado por la prueba de Weisfeiler–Lehman de 1 dimensión (1-WL). Esta limitación refleja su incapacidad para aproximar universalmente señales de orden superior. Además, las GNN espectrales clásicas dependen de filtros espectrales diagonales (funciones de valores propios individuales), lo que restringe su capacidad para modelar interacciones complejas, particularmente en grafos heterofílicos donde los nodos adyacentes suelen poseer etiquetas diferentes. Los enfoques existentes para superar la 1-WL típicamente implican elevar el paso de mensajes a dominios de orden superior (por ejemplo, pares de nodos) en el dominio espacial, pero ha faltado un marco espectral escalable correspondiente.

Metodología

Los autores proponen FSPECGNN (Red Neuronal de Grafos de Espectro Completo), una generalización de segundo orden de las GNN espectrales clásicas. La metodología se basa en dos avances teóricos centrales:

1. Elevación del Dominio de la Señal: En lugar de filtrar señales de nodos $x \in \mathbb{R}^V$, FSPECGNN opera sobre señales de pares de nodos $\varepsilon \in \mathbb{R}^{V \times V}$. Esto eleva la señal del dominio de nodos al dominio de pares de nodos.
2. Filtrado Espectral Bivariado: El filtrado espectral clásico aplica una función univariada $g(\lambda)$ a los valores propios. FSPECGNN extiende esto a un filtro bivariado $g(\lambda_i, \lambda_j)$ sobre pares de valores propios.
   • La convolución de espectro completo se define como:
     $$G_\lambda *_{\mathcal{G}} \varepsilon = \sum_{i,j} g(\lambda_i, \lambda_j) u_i u_i^\top \varepsilon u_j u_j^\top$$
     donde $L = U\Lambda U^\top$ es la descomposición espectral del Laplaciano del grafo.
   • Esta formulación generaliza las GNN espectrales clásicas, las cuales se muestran como un caso especial diagonal de FSPECGNN (recuperado al restringir el filtro a la diagonal $g(\lambda_i, \lambda_i)$).

Implementación Escalable:
El cálculo directo en el dominio de pares de nodos ($n^2 \times n^2$) es intratable para grafos grandes. Para abordar esto, los autores proponen una implementación escalable utilizando descomposición tensorial de rango bajo:

• El filtro polinómico bivariado se aproxima mediante una suma de polinomios univariados separables: $P(L \otimes I, I \otimes L) \approx \sum_{r=1}^S f_r(L) \otimes h_r(L)$.
• Utilizando la propiedad $(A \otimes B)\text{vec}(\varepsilon) = \text{vec}(B\varepsilon A^\top)$, la convolución se calcula como $h(L) \varepsilon f(L)^\top$, evitando la construcción explícita del operador de dimensión $n^2$.
• La señal inicial de pares de nodos $\varepsilon$ se construye mediante una combinación aprendible de la identidad y una capa GAT ($I + \alpha \text{GAT}$), induciendo una mezcla fuera de la diagonal dependiente de las características.

Contribuciones Clave

1. Expresividad Teórica:

   • Aproximación Universal: Los autores demuestran que FSPECGNN lineal puede aproximar universalmente señales de pares de nodos unidimensionales (Teorema 3.4), extendiendo la universalidad de las GNN espectrales de nodos a pares de nodos.
   • Superioridad sobre la 1-WL: El artículo establece que FSPECGNN puede superar el límite superior de la 1-WL. Específicamente, bajo condiciones de espectro simple y coeficientes espectrales no nulos, FSPECGNN puede lograr una expresividad equivalente a Local 2-GNN (un modelo espacial de segundo orden), y potencialmente excederlo con polinomios bivariados específicos (Teorema 3.8).

2. Aprendizaje en Grafos Heterofílicos:

   • Los autores analizan la convolución óptima para la separación de clases en grafos heterofílicos. Demuestran que el operador óptimo requiere componentes fuera de la diagonal en la base espectral (Teorema 4.1) para suprimir las conexiones interclase.
   • Se prueba una limitación fundamental: las convoluciones espectrales clásicas (filtros diagonales) no pueden realizar este operador óptimo a menos que degeneren en un múltiplo escalar de la identidad (Teorema 4.2). FSPECGNN, al permitir interacciones espectrales fuera de la diagonal, puede realizar este operador óptimo.

3. Escalabilidad:

   • La aproximación de rango bajo propuesta reduce la complejidad computacional a $O(Kmd)$, comparable a las GNN espectrales polinómicas existentes, evitando al mismo tiempo el costo $O(n^3)$ de la descomposición espectral y la memoria $O(n^4)$ de las operaciones explícitas de pares de nodos.

Resultados Experimentales

El artículo evalúa FSPECGNN en tres tareas:

1. Clasificación de Nodos Heterofílicos:

   • Probado en ocho conjuntos de datos (por ejemplo, Texas, Wisconsin, Squirrel, Roman Empire).
   • Las variantes de FSPECGNN (utilizando bases de Chebyshev, ChebNetII y Bernstein) superaron consistentemente a las líneas base espectrales más avanzadas (ChebNet, GPRGNN, BernNet, etc.).
   • Los estudios de ablación confirmaron que eliminar las interacciones fuera de la diagonal o el "in-filter" degradó significativamente el rendimiento, validando la necesidad de modelar el acoplamiento entre espacios propios cruzados.

2. Conteo de Subestructuras (Validación de Expresividad):

   • Evaluado en benchmarks de conteo de homomorfismos y ciclos (acorazados).
   • FSPECGNN logró un rendimiento comparable a Local 2-GNN y Local 2-FGNN, confirmando la predicción teórica de que iguala la expresividad de los modelos espaciales de segundo orden.
   • Superó sustancialmente a las GNN invariantes espectrales y a las MPNN estándar en estas tareas.

3. Eficiencia:

   • FSPECGNN demostró un tiempo de ejecución significativamente menor (aproximadamente 5$\times$ más rápido) y un uso de memoria pico de GPU menor en comparación con las líneas base espaciales de segundo orden (Local 2-GNN, Local 2-FGNN, Subgraph GNN).

Significado y Afirmaciones

El artículo afirma que FSPECGNN proporciona un contraparte espectral principista a las GNN espaciales de orden superior. Su significado principal radica en cerrar la brecha entre los métodos espectrales y la expresividad de orden superior:

• Demuestra que la heterofilia es inherentemente un fenómeno de segundo orden que requiere componentes espectrales fuera de la diagonal, los cuales carecen estructuralmente las GNN espectrales clásicas.
• Ofrece una arquitectura escalable que retiene los beneficios teóricos del modelado de segundo orden (superar la 1-WL, aproximación universal en pares) sin los costos computacionales prohibitivos de los métodos espaciales explícitos de orden superior.
• El trabajo identifica una limitación fundamental de los filtros espectrales diagonales y propone un marco generalizable (extensible al orden $k$-ésimo) para superarla.