Resumen Técnico: Alineación de Grafos para la Evaluación de Redes Neuronales de Grafos y el Aprendizaje de Codificaciones Posicionales

Declaración del Problema

Las Redes Neuronales de Grafos (GNN) se utilizan ampliamente en diversos dominios como la química, la ciencia de materiales y las redes sociales. Sin embargo, evaluar su comprensión estructural sigue siendo un desafío. Los benchmarks existentes a menudo confunden las capacidades estructurales con el aprendizaje de características o dependen de tareas de optimización combinatoria (por ejemplo, SAT, TSP) que están ligadas a topologías de problemas específicos o modelos sintéticos como el Modelo de Bloques Estocásticos (SBM), lo que limita su generalizabilidad. Además, los métodos actuales tienen dificultades para proporcionar una métrica detallada para comparar modelos dentro de la misma clase de expresividad (por ejemplo, la clase 1-Weisfeiler-Lehman) o para cuantificar la expresividad estructural a través de diversas topologías de grafos presentes en aplicaciones del mundo real.

Los autores proponen abordar esta brecha introduciendo una metodología de evaluación basada en el Problema de Alineación de Grafos (también conocido como Emparejamiento de Grafos). Esta tarea consiste en alinear dos grafos sin etiquetas para maximizar el número de aristas superpuestas, un problema de optimización combinatoria que generaliza el isomorfismo de grafos.

Metodología

1. La Tarea de Alineación de Grafos

La tarea central se define como la búsqueda de una permutación $\pi^*$ entre dos grafos $G$ y $\tilde{G}$ con $N$ vértices que maximice la superposición de sus matrices de adyacencia:
$$\pi^* \in \arg \max_{\pi \in S_N} \sum_{i,j} A_{i,j} \tilde{A}_{\pi(i),\pi(j)}$$
Esto se plantea como una tarea de aprendizaje autosupervisado. Los autores emplean una arquitectura siamesa donde una GNN procesa ambos grafos para producir embeddings de nodos $X$ y $\tilde{X}$. Se calcula una matriz de similitud $\Sigma = X\tilde{X}^T$.

• Entrenamiento: El modelo minimiza la pérdida de entropía cruzada binaria entre la matriz de similitud predicha y la alineación de base (permutación plantada).
• Evaluación: El algoritmo húngaro resuelve el Problema de Asignación Lineal sobre $\Sigma$ para extraer la permutación predicha. El rendimiento se mide mediante el porcentaje de nodos correctamente mapeados.

2. Construcción del Conjunto de Datos

Para superar las limitaciones de los conjuntos de datos sintéticos anteriores (por ejemplo, grafos de Erdős-Rényi únicamente), los autores proponen un método para generar conjuntos de datos de Alineación de Grafos a partir de cualquier conjunto de datos de grafos existente (datasets base).

• Generación de Grafos Correlacionados: Para un grafo base $G$, se genera un grafo correlacionado $\tilde{G}$ añadiendo y eliminando aristas aleatoriamente basándose en un nivel de ruido $\eta$.
• Solución Plantada: Dado que la alineación óptima es conocida (la identidad o una permutación conocida antes del ruido), la verdad fundamental está disponible sin necesidad de resolver el problema NP-duro.
• Escalabilidad: Para grafos grandes (por ejemplo, OGBN-Arxiv), se utiliza un algoritmo de muestreo por Búsqueda en Anchura (BFS) para extraer subgrafos más pequeños que preserven la topología local, haciéndolos compatibles con las Redes Neuronales de Paso de Mensajes (MPNNs).
• Control de Dificultad: Al variar el nivel de ruido $\eta$ (del 4% al 30%), los autores crean una familia de conjuntos de datos con dificultad controlable, lo que permite una evaluación matizada.

3. Aprendizaje de Codificaciones Posicionales (GAPE)

Los autores aprovechan los embeddings de nodos aprendidos mediante la tarea de Alineación de Grafos como Codificaciones Posicionales de Alineación de Grafos (GAPE). Estos embeddings están destinados a servir como entradas estructurales para arquitecturas Transformer, las cuales carecen de acceso inherente a la estructura del grafo.

Contribuciones Clave

1. Nueva Tarea de Evaluación: Introducción del Problema de Alineación de Grafos como un benchmark para GNNs, el cual generaliza la prueba de Weisfeiler-Lehman y permite la evaluación a través de diversas topologías (moleculares, sociales, aleatorias) sin modificar las estructuras de los grafos subyacentes.
2. Marco de Generación de Conjuntos de Datos: Una metodología integral para generar conjuntos de datos de Alineación de Grafos a partir de datasets base tanto sintéticos como del mundo real, permitiendo la creación de datasets con distintos niveles de dificultad.
3. Clasificación Empírica de Arquitecturas: Un benchmark sistemático de MPNNs ampliamente utilizadas (GCN, GIN, GatedGCN, GAT, GATv2) que demuestra que los modelos anisotrópicos superan consistentemente a los modelos isotrópicos (como GCN y GIN) en el análisis estructural, incluso en grafos homofílicos.
4. Nivel de Dificultad Óptimo: El descubrimiento de que existe un "nivel de ruido óptimo" donde la brecha de rendimiento entre modelos se maximiza, proporcionando clasificaciones estadísticamente significativas que son robustas a la elección de hiperparámetros y semillas aleatorias.
5. Codificaciones Posicionales (GAPE): Demostración de que los embeddings aprendidos mediante Alineación de Grafos sirven como codificaciones posicionales efectivas para Transformers, superando o igualando las codificaciones espectrales y basadas en paseos aleatorios en tareas de regresión molecular.
6. Reconstrucción de Grafos: Evidencia de que los embeddings GAPE comprimen la estructura del grafo de manera efectiva, permitiendo la reconstrucción de la matriz de adyacencia completa con aproximadamente un 98% de precisión utilizando un decodificador simple.
7. Herramientas de Código Abierto: Provisión de un paquete de Python para generar estos conjuntos de datos y evaluar nuevas arquitecturas.

Resultados

• Rendimiento de los Modelos: En experimentos a través de cinco datasets base (Erdős-Rényi, AQSOL, PCQM4Mv2, CoraFull, OGBN-Arxiv), las arquitecturas anisotrópicas (GatedGCN, GAT, GATv2) lograron una mayor precisión de alineación que las isotrópicas (GCN, GIN).
• Sensibilidad al Ruido: La brecha de rendimiento entre modelos fue insignificante en niveles de ruido muy bajos o muy altos. La brecha alcanzó su máximo en un nivel de ruido óptimo (por ejemplo, $\eta \approx 15\%$ para grafos moleculares), donde la significancia estadística fue mayor.
• Tareas de Avaloración (Downstream): Cuando se utilizaron como codificaciones posicionales para Transformers en regresión molecular (AQSOL, PCQM4Mv2), GAPE logró un Error Absoluto Medio (MAE) de vanguardia o competitivo comparado con las codificaciones de Laplacian, Random Walk y otras codificaciones espectrales. Específicamente, GAPE+RWPE obtuvo los mejores resultados en AQSOL y PCQM4Mv2.
• Reconstrucción: Un autoencoder con un codificador GAPE congelado logró más del 98% de precisión en la reconstrucción de la matriz de adyacencia, confirmando que los embeddings capturan la topología completa del grafo.
• Correlación: Se observó una fuerte correlación negativa ($r < -0.90$) entre la precisión de la Alineación de Grafos y el error de predicción de propiedades moleculares, lo que sugiere que la capacidad de alineación estructural es un cuello de botella primario para estas tareas.

Significado y Reivindicaciones

El artículo afirma proporcionar un marco robusto y detallado para evaluar la expresividad estructural de las GNN, independientemente de las características específicas de los nodos o aristas. Al aislar la comprensión estructural, el benchmark revela que los modelos anisotrópicos ofrecen una representación más rica de la topología del grafo que los modelos isotrópicos establecidos previamente.

Además, los autores argumentan que la tarea de Alineación de Grafos no es meramente un "rompecabezas", sino un objetivo de preentrenamiento fundamental. El hecho de que los embeddings aprendidos puedan utilizarse para una reconstrucción de alta precisión de grafos y mejoren significativamente el rendimiento de los Transformers en tareas posteriores sugiere que la tarea obliga al modelo a aprender una compresión de alta fidelidad de la estructura del grafo. Esto valida la utilidad del benchmark tanto para comparar arquitecturas como para generar representaciones útiles para aplicaciones del mundo real en química y ciencia de materiales.

El trabajo concluye que el benchmark de Alineación de Grafos ofrece un enfoque flexible y agnóstico al dominio para la evaluación de GNN, capaz de adaptarse a las características topológicas específicas de cualquier dominio de aplicación objetivo.