Resumen Técnico: Weisfeiler–Leman es Incompleto en Grafos de Espectro Simple, por lo que Canonicalíceselos

Enunciado del Problema

Las Redes Neuronales en Grafos (GNN) se utilizan ampliamente para el aprendizaje en datos estructurados en grafos, sin embargo, su poder expresivo a menudo está limitado por la jerarquía de Weisfeiler–Leman (WL). Es un resultado conocido que la prueba de WL de dimensión $k$ ($k$-WL) no puede distinguir todos los grafos no isomorfos. No obstante, una clase específica de grafos —aquellos con un espectro simple (donde la matriz de adyacencia tiene valores propios distintos)— admite una prueba de isomorfismo en tiempo cúbico. A pesar de esta tratabilidad teórica, permaneció como una pregunta abierta si la jerarquía de WL, que limita superiormente la expresividad de muchas GNN, podía distinguir todos los grafos de espectro simple.

Además, aunque las codificaciones posicionales espectrales (por ejemplo, vectores propios del Laplaciano) se integran comúnmente en GNN para mejorar la expresividad, sufren de ambigüedades inherentes: ambigüedad de signo para espectros simples y ambigüedad de base para valores propios repetidos. Los métodos existentes para resolver estas ambigüedades (como SignNet, MAP y OAP) son demostrablemente incompletos en grafos de espectro simple, fallando en distinguir ciertos pares no isomorfos. Esta incompletitud limita la capacidad de las GNN espectrales para lograr aproximación universal en esta clase de grafos.

Metodología

1. Prueba de Incompletitud de WL en Espectros Simples

Los autores establecen primero que toda la jerarquía de WL es incompleta en grafos de espectro simple.

• Construcción: Utilizan la construcción de Cai–Fürer–Immerman (CFI), que genera pares de grafos no isomorfos indistinguibles por $k$-WL.
• Codificación: Dado que los grafos CFI estándar no poseen un espectro simple, los autores introducen un novedoso mecanismo de codificación integral. Mapean los patrones de adyacencia de CFI en una matriz ortogonal $\tilde{X}$ compuesta por entradas enteras.
• Formación de Multigrafos: Utilizando esta matriz ortogonal y una matriz diagonal de valores propios enteros distintos, construyen un par de multigrafos simétricos ($A_{G,0}$ y $A_{G,1}$) con espectros simples.
• Resultado: Demuestran que estos multigrafos de espectro simple construidos permanecen indistinguibles por la prueba $k$-WL, demostrando que ningún nivel de la jerarquía de WL puede resolver el problema de isomorfismo para esta clase, a pesar de que el problema sea resoluble en tiempo cúbico.

2. PRiSM: Una Canonicalización Completa

Para abordar las limitaciones de los métodos espectrales existentes, los autores proponen PRiSM (Particionar, Refinar, Resolver, Emparejar), un procedimiento de canonicalización demostrablemente completo para las descomposiciones espectrales de grafos de espectro simple.

• Entrada: Una matriz $U$ ortonormal por columnas de vectores propios.
• Grupo de Ambigüedad: El procedimiento maneja el grupo de ambigüedad $S_n \times \{-1, 1\}^k$ (permutaciones y cambios de signo).
• Cuatro Etapas:
  1. Partición: Los vértices se agrupan basándose en sus firmas invariantes de signo (valores absolutos de las entradas de los vectores propios).
  2. Refinamiento: Se aplica una variante espectral del procedimiento de refinamiento de colores de WL a la partición. Esto refina iterativamente las clases de vértices utilizando el multiconjunto de características de arista definidas por productos elemento a elemento de las entradas de los vectores propios ($U_v \odot U_u$) hasta que la partición se estabiliza.
  3. Resolver: La partición estable define un sistema de ecuaciones lineales sobre el campo $\mathbb{Z}_2$. El sistema impone que cada clase de partición contenga al menos una fila con entradas no negativas. Resolver este sistema determina los signos canónicos únicos para los vectores propios (hasta automorfismos del grafo).
  4. Emparejar: Una vez fijados los signos, las filas se ordenan lexicográficamente para resolver la ambigüedad de permutación, produciendo una matriz canónica única.
• Extensión: Para grafos con valores propios repetidos (espectro no simple), PRiSM se extiende heurísticamente. Aplica el procedimiento base al bloque de espectro simple ($m=1$) y utiliza la descomposición QR y la selección de pivotes para resolver los espacios propios de orden superior ($m > 1$).

3. Garantías Teóricas

• Completitud: Se demuestra que PRiSM es una canonicalización válida, lo que significa que produce la misma salida para grafos isomorfos y salidas diferentes para grafos de espectro simple no isomorfos.
• Aproximación Universal: Al componer PRiSM con una red de conjuntos universal (por ejemplo, DeepSets o Transformers), el modelo resultante logra aproximación universal para cualquier función invariante bajo isomorfismo en grafos de espectro simple. Esto resuelve el problema abierto de lograr completitud para GNN espectrales en esta clase.

Resultados Clave

Hallazgos Teóricos

• Teorema 1: Para cada número natural $k$, existen multigrafos de espectro simple no isomorfos con $\Theta(k)$ nodos que no son distinguidos por el algoritmo $k$-WL. Esto implica que todas las familias de GNN alineadas con $k$-WL (incluyendo PPGN, $k$-GNNs y Graph Transformers) son incompletas en grafos de espectro simple.
• Teorema 2: PRiSM proporciona una canonicalización válida para descomposiciones espectrales de espectro simple.
• Teorema 3: Los modelos compuestos de PRiSM y redes de conjuntos universales logran aproximación universal en grafos de espectro simple.

Rendimiento Empírico

Los autores evaluaron PRiSM en tres puntos de referencia:

1. BREC Expressivity Benchmark: PRiSM superó a las canonicalizaciones competidoras (MAP, OAP) en la distinción de pares de grafos no isomorfos, particularmente en las categorías Regular y Extension. Distinguió correctamente 212/360 pares en comparación con 199/360 para MAP/OAP.
2. Predicción de Propiedades Moleculares (ZINC, OGB-Mol): PRiSM logró un rendimiento de vanguardia o empatado con el mejor en tareas de regresión molecular (ZINC) y clasificación (MOLTOX21, MOLPCBA) utilizando tanto las bases GatedGCN como PNA.
3. Backbones de Transformers (OGB, Alchemy): Cuando se utiliza como codificación posicional para Graph Transformers, PRiSM superó a todos los puntos de referencia (LPE, MAP, OAP) en los cuatro conjuntos de datos (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). Los autores atribuyen esto a que PRiSM proporciona un ordenamiento determinista de vértices además de vectores propios corregidos de signo, lo cual es crucial para los mecanismos de atención de los Transformers.

Significado y Afirmaciones

El artículo afirma resolver una brecha fundamental en la comprensión teórica de la expresividad de las GNN y los métodos espectrales:

1. Incompletitud de WL: Demuestra definitivamente que la jerarquía de WL, a pesar de su poder creciente, no puede distinguir todos los grafos de espectro simple, una clase donde el isomorfismo es teóricamente fácil.
2. Primera Canonicalización Completa: PRiSM se presenta como la primera canonicalización de signos demostrablemente completa para descomposiciones espectrales de espectro simple, superando las limitaciones de métodos anteriores como MAP y OAP que son incompletos en esta clase.
3. Aproximación Universal: El trabajo establece que las GNN espectrales pueden lograr aproximación universal en grafos de espectro simple si se emparejan con una canonicalización completa como PRiSM, justificando el uso de codificaciones posicionales Laplacianas canonicalizadas.
4. Utilidad Práctica: Empíricamente, el método demuestra que resolver las ambigüedades espectrales completamente conduce a mejoras tangibles en tareas posteriores, superando los enfoques existentes invariantes de signo y de canonicalización.

Los autores señalan limitaciones, específicamente que la garantía de completitud se aplica estrictamente a grafos de espectro simple (o multigrafos construidos en la prueba) y que el procedimiento de canonicalización es discontinuo, una propiedad que argumentan es matemáticamente inevitable para las canonicalizaciones completas de signos. También dejan la extensión de la prueba de incompletitud a grafos combinatorios simples (sin aristas múltiples) como trabajo futuro.