Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs

1. Enunciado del Problema

Las Redes Neuronales de Grafos (GNN) actuales están fundamentalmente limitadas por su dependencia del vecindario como unidad primitiva de paso de mensajes.

• Cuello de botella de expresividad: El paso de mensajes estándar agrega información sobre los vecinos inmediatos, lo que restringe el poder expresivo de las GNN al del test de Weisfeiler–Lehman (WL). Esto limita su capacidad para distinguir grafos no isomorfos o capturar estructuras topológicas complejas (por ejemplo, ciclos, interacciones de orden superior).
• Soluciones ad hoc: Los intentos existentes de superar esto (por ejemplo, usando complejos simpliciales, motivos de subgrafos o vecindarios de $k$ saltos) a menudo dependen de definiciones hechas a mano o elecciones combinatorias en lugar de una base algebraica unificada.
• Desafío central: Existe una falta de un marco algebraico sistemático y principista que generalice los vecindarios a objetos estructurales más ricos, manteniendo al mismo tiempo la capacidad de implementarlos eficientemente en redes neuronales.

2. Metodología: El Marco GkGNN

Los autores proponen el marco de Redes Neuronales de Grafos de Grothendieck (GkGNN), que reemplaza los vecindarios con cubrimientos como los objetos fundamentales del paso de mensajes. Esto se logra mediante un formalismo algebraico riguroso.

A. Fundamentos Algebraicos

El marco establece una dualidad entre grafos y estructuras algebraicas utilizando monoides:

1. Subgrafos dirigidos como generadores: En lugar de solo nodos y aristas, el marco trata los subgrafos dirigidos (específicamente, caminos y sus composiciones) como los bloques de construcción.
2. Monoide de subgrafos dirigidos ($Mod(G)$): Se construye un monoide no conmutativo donde los elementos son composiciones de subgrafos dirigidos. La operación $\bullet$ representa la composición de caminos.
   • Insight clave: Las aristas dirigidas generan este monoide. Las estructuras complejas se construyen componiendo aristas en un orden específico (por ejemplo, $e_1 \bullet e_2 \neq e_2 \bullet e_1$).
3. Monoide de representaciones matriciales ($Mom(G)$): Se define un monoide correspondiente de matrices utilizando una operación binaria específica: $A \circ B = A + B + AB$.
4. El homomorfismo ($Tr$): Un componente crucial es el homomorfismo monoidal $Tr: Mod(G) \to Mom(G)$. Este mapa traduce composiciones algebraicas de subgrafos en operaciones matriciales.
   • Propiedad: $Tr(D_1 \bullet D_2) = Tr(D_1) \circ Tr(D_2)$.
   • Significado: Esto asegura que la estructura algebraica de las composiciones de caminos se preserve al moverse al dominio matricial, permitiendo análisis teórico e implementación práctica.

B. El concepto de "Cubrimientos"

Un cubrimiento se define como una colección finita de elementos de $Mod(G)$.

• A diferencia de un solo vecindario, un cubrimiento representa una familia de estrategias de paso de mensajes.
• Los vecindarios se recuperan como un caso especial (un tipo específico de cubrimiento).
• Los cubrimientos permiten definir esquemas de propagación que son sensibles a la topología global y a la direccionalidad de los caminos, no solo a la adyacencia local.

C. Redes Neuronales de Tamiz (SNN)

Para demostrar el marco, los autores introducen las Redes Neuronales de Tamiz (SNN), una instancia concreta de GkGNN:

• Construcción del tamiz: Inspirado en la teoría de categorías, la SNN construye "tamices" alrededor de cada nodo. Estos son capas de subgrafos dirigidos ($D_k(v)$) que se expanden hacia afuera, capturando caminos de profundidad creciente con direccionalidad específica.
• Co-tamices: También se construyen tamices en dirección inversa para capturar el flujo entrante.
• Operadores matriciales: El cubrimiento de tamices se transforma mediante $Tr$ en operadores matriciales (por ejemplo, $Image(v, k)$y$CoImage(v, \ell)$).
• Arquitectura: La SNN utiliza estos operadores para calcular una matriz de adyacencia ponderada que codifica caminos topológicos ricos. Esta matriz reemplaza a la matriz de adyacencia estándar en las GNN aguas abajo.
• Variantes:
  • Variante $\alpha$: Calcula puntuaciones pares basadas en las capacidades de los tamices de remitente/receptor.
  • Variante $\beta$: Agrega información global sumando sobre las imágenes/co-imágenes centradas en nodos.

3. Contribuciones Clave

1. Generalización algebraica de vecindarios: El artículo introduce una extensión algebraica estricta de los vecindarios a cubrimientos, proporcionando una base principista para el paso de mensajes consciente de la topología.
2. El marco GkGNN: Una plataforma sistemática que formaliza los cubrimientos, estudia sus propiedades de invarianza y los traduce a representaciones matriciales mediante un homomorfismo monoidal.
3. Dualidad teórica: Demuestra que los grafos pueden caracterizarse hasta el isomorfismo por los monoides generados por sus cubrimientos, estableciendo una dualidad entre la estructura del grafo y la composición algebraica.
4. Redes Neuronales de Tamiz (SNN): Un modelo canónico de cubrimiento fijo que demuestra cómo elementos algebraicos expresivos pueden transformarse en operadores de paso de mensajes prácticos sin parámetros aprendibles en la fase de generación del cubrimiento.
5. Evaluación novedosa: Introduce una sonda de codificación topológica utilizando Propagación de Etiquetas (LP) de un paso para aislar y evaluar la información estructural codificada por el propio operador de propagación, independientemente de la dinámica de entrenamiento.

4. Resultados Experimentales

Los autores evaluaron la SNN en dos frentes principales:

A. Puntos de referencia de isomorfismo de grafos

La SNN se probó en conjuntos de datos conocidos por ser difíciles para las GNN estándar y el test WL:

• Grafos Regularmente Fuertes (SRG): La SNN logró una tasa de fallo del 0% en la distinción de grafos no isomorfos, mientras que 3-WL falla completamente en estos conjuntos de datos.
• Enlaces de Salto Circular (CSL): La SNN separó perfectamente todas las 10 clases de isomorfismo (100% de precisión).
• BREC Benchmark: La SNN logró una tasa de fallo del 0% en todas las categorías (Básico, Regular, Extensión, CFI), incluidos casos indistinguibles por 4-WL.
• Conclusión: La SNN supera significativamente los límites de expresividad de la jerarquía WL.

B. Sonda de codificación topológica (Propagación de Etiquetas)

Utilizando una Propagación de Etiquetas (LP) de un paso sin parámetros ($\alpha=1$) en varios conjuntos de datos (Cora, CiteSeer, ogbn-arxiv, Actor):

• Comparación: Los operadores derivados de la SNN se compararon con operadores de adyacencia polinómicos clásicos ($Ad, Ad^2, \dots$).
• Resultados: Los operadores de la SNN superaron consistentemente a las líneas base polinómicas clásicas, particularmente en el conjunto de datos Actor (un grafo heterofílico), donde la SNN alcanzó un 25,4% de precisión frente a ~19% para los métodos clásicos.
• Implicación: Esto confirma que la mejora proviene de la codificación topológica superior de los cubrimientos de tamiz, no de la optimización o la capacidad del modelo.

C. Clasificación de grafos

En conjuntos de datos TUD (NCI1, IMDB-B, IMDB-M, PROTEINS), la SNN logró resultados competitivos o de última generación en comparación con GNN de alto orden (PPGN, GSN) y kernels de grafos, demostrando su utilidad como paso de preprocesamiento para GNN estándar.

5. Significado e Impacto

• Cambio de paradigma: El artículo desafía el dogma de que los "vecindarios" son la unidad primitiva de las GNN, proponiendo los cubrimientos como una alternativa más general y poderosa.
• Rigor teórico: Al fundamentar el enfoque en la teoría de monoides y homomorfismos, el marco proporciona una base matemáticamente sólida para diseñar nuevos esquemas de paso de mensajes que estén garantizados para ser invariantes al isomorfismo.
• Más allá de WL: Ofrece una vía para romper la barrera de expresividad del test de Weisfeiler-Lehman sin recurrir a operaciones tensoriales de orden superior computacionalmente costosas, utilizando en su lugar composiciones de caminos estructuradas.
• Direcciones futuras: El marco abre la puerta a cubrimientos basados en aprendizaje (parametrizando la selección del cubrimiento) e integrar priores estructurales externos (por ejemplo, particiones de comunidades) directamente en el mecanismo de paso de mensajes.

En resumen, GkGNN proporciona una plataforma algebraica fundamental que unifica y extiende los conceptos existentes de GNN, demostrando que reemplazar los vecindarios con cubrimientos definidos algebraicamente conduce a una comprensión topológica significativamente más fuerte y capacidades de discriminación de grafos.