Resumen Técnico: Revisión de las GNN Pre-Propagación

1. Declaración del Problema

Las Redes Neuronales de Grafos Pre-Propagación (PP-GNNs) ofrecen una alternativa escalable a las GNN de Paso de Mensajes tradicionales (MP-GNNs) al desacoplar la propagación de características de la transformación. En las PP-GNNs, la difusión del grafo se realiza una sola vez como paso de preprocesamiento para generar características de múltiples saltos, permitiendo que la fase de entrenamiento subsiguiente utilice transformaciones densas y mini-loteables sin dependencias inter-nodo. Aunque este diseño mejora la eficiencia y se ajusta a los aceleradores de hardware modernos optimizados para el cálculo denso, las PP-GNNs presentan una brecha de rendimiento significativa en comparación con las MP-GNNs, particularmente en grafos heterofílicos (donde los nodos conectados a menudo tienen etiquetas diferentes).

Los autores identifican dos limitaciones de diseño principales que contribuyen a esta brecha:

1. Limitaciones del Operador de Difusión: Las PP-GNNs estándar dependen de operadores simples (por ejemplo, adyacencia normalizada, paseos aleatorios) que actúan como filtros paso bajo. Estos son subóptimos para grafos heterofílicos, que a menudo requieren componentes de mayor frecuencia o paso de banda. Además, las bases de difusión monomiales estándar (potencias de la matriz de difusión) suelen estar mal condicionadas y producen características altamente correlacionadas, limitando la calidad de la aproximación.
2. Propagación de Una Sola Vez: Las PP-GNNs propagan las características de entrada crudas solo una vez. A diferencia de las MP-GNNs, que intercalan iterativamente la propagación con transformaciones no lineales para refinar representaciones adaptadas a la tarea, las PP-GNNs no pueden actualizar las características propagadas basándose en estados ocultos evolutivos durante el entrenamiento.

2. Metodología

El artículo propone un conjunto de mejoras para cerrar la brecha de precisión preservando al mismo tiempo la eficiencia de entrenamiento de las PP-GNNs. El enfoque consta de tres componentes principales:

A. Operadores de Difusión Robustos

Para abordar las limitaciones de las bases de difusión estándar, los autores introducen dos bases de difusión ortogonales y mejor condicionadas para la etapa de preprocesamiento:

• Base de Polinomios de Jacobi: En lugar de utilizar monomios $\Phi^k$, los autores emplean polinomios de Jacobi $P_k^{(\alpha, \beta)}(\tilde{L})$, donde $\tilde{L}$ es un Laplaciano desplazado. Los parámetros $(\alpha, \beta)$ se calibran en un único paso de preprocesamiento ligero basado en la densidad espectral del grafo (utilizando momentos estocásticos de Chebyshev) para asignar resolución donde se concentra el espectro del grafo. Esto crea una base ortogonal que reduce la correlación de características.
• Base de Subespacio de Lanczos/Krylov: Para capturar el contenido espectral específico de cada canal, los autores construyen un subespacio de Krylov para cada canal de características utilizando la iteración de Lanczos. Esto genera un conjunto de vectores y valores de Ritz que forman un banco de difusión ortogonal y alineado con la señal. Este método descompone las características en componentes decorrelacionados, proporcionando un sistema de coordenadas más estable para la agregación bajo un presupuesto de saltos fijo.

B. Re-Propagación del Estado Oculto (HRP)

Para superar la limitación de "una sola vez", los autores introducen la Re-Propagación del Estado Oculto (HRP). Este mecanismo vuelve a acoplar la propagación de características con las representaciones aprendidas:

• Mecanismo: El entrenamiento se divide en múltiples etapas. Al final de cada etapa, se selecciona y desconecta la mejor representación oculta (antes de la proyección de salida final). Este estado oculto se vuelve a propagar a través del operador de difusión para generar un nuevo conjunto de características de múltiples saltos.
• Integración: Estas características ocultas re-propagadas se mezclan con las características precalculadas originales para formar la entrada de la siguiente etapa de entrenamiento.
• Distinción: Los autores contrastan explícitamente la HRP con la reutilización basada en etiquetas (por ejemplo, usar logits o etiquetas one-hot como características). Argumentan que re-propagar estados ocultos de alta dimensión transporta información relacional complementaria más allá de las probabilidades de clase, mientras que la propagación de etiquetas puede introducir atajos o ruido, especialmente en grafos heterofílicos.

C. Agregador de Saltos Basado en RNN

Como mejora opcional de eficiencia, los autores proponen reemplazar los agregadores de Atención Multi-Cabeza (MHA) (utilizados en modelos como HOGA) con una Red Neuronal Recurrente (RNN) para procesar la secuencia de características de saltos. Esto reduce la sobrecarga computacional y el uso de memoria manteniendo una precisión comparable.

3. Contribuciones Clave

1. Adaptación de Bases de Difusión Robustas: El artículo adapta las bases de difusión de polinomios de Jacobi y subespacio de Krylov al régimen de preprocesamiento de PP-GNN. Estas bases mejoran el acondicionamiento de las características precalculadas y permiten respuestas espectrales más ricas bajo un presupuesto de saltos fijo.
2. Re-Propagación del Estado Oculto (HRP): Un mecanismo ligero que refina iterativamente las PP-GNNs re-propagando estados ocultos intermedios, cerrando efectivamente la brecha entre la propagación de una sola vez y el paso de mensajes iterativo sin sacrificar la escalabilidad.
3. Agregación Eficiente: Un agregador de saltos basado en RNN que sirve como alternativa computacionalmente más barata a la agregación basada en atención.
4. Validación Empírica: Experimentos extensos en 12 conjuntos de datos (6 heterofílicos, 6 homofílicos) y 4 arquitecturas base de PP-GNN (SIGN, HOGA, GAMLP, GARNN).

4. Resultados Experimentales

Los métodos propuestos se evaluaron en ambos benchmarks heterofílicos y homofílicos:

• Grafos Heterofílicos: En seis conjuntos de datos heterofílicos (incluyendo Roman-Empire, Minesweeper y Pokec), las PP-GNNs mejoradas redujeron significativamente la brecha de precisión con las MP-GNNs.
  • La mejora promedio de precisión de prueba sobre las PP-GNNs base fue de +2.18% en conjuntos de datos heterofílicos.
  • Los modelos mejorados superaron a fuertes líneas base de MP-GNN (por ejemplo, GraphSAGE, GAT) en 4 de 6 grafos heterofílicos.
  • En el conjunto de datos Roman-Empire, la brecha de precisión entre MP-GNNs y PP-GNNs se redujo de ~11% a una paridad casi total.
• Grafos Homofílicos: Las mejoras también se transfirieron a conjuntos de datos homofílicos (por ejemplo, Cora, Citeseer, OGBN-Arxiv), con una mejora promedio de +1.96%. Las PP-GNNs mejoradas superaron a las MP-GNNs en 3 de 6 conjuntos de datos homofílicos.
• Estudios de Ablación:
  • Los operadores de difusión robustos por sí solos proporcionaron una ganancia promedio de ~2.09% (validación) / 1.99% (prueba).
  • La HRP proporcionó una ganancia adicional de ~1.54% (validación) / 1.61% (prueba).
  • La HRP superó significativamente a las estrategias de entrada de etiquetas y propagación de etiquetas, particularmente en grafos heterofílicos donde la suavidad de las etiquetas es baja.
• Eficiencia:
  • El operador de Lanczos añade un costo comparable a unos pocos pasos de difusión estándar.
  • La HRP introduce un pequeño número de etapas (típicamente < 4, máximo 7), con la difusión de re-propagación representando solo ~2% del tiempo total de entrenamiento.
  • El agregador basado en RNN (GARNN) logró una precisión similar a HOGA pero con un tiempo de entrenamiento significativamente reducido (2.4s/época vs. 8.4s/época en Pokec).
  • En general, las PP-GNNs mejoradas logran una compensación favorable entre precisión y tiempo de ejecución, acercando a la familia PP-GNN a la frontera de Pareto de las MP-GNN.

5. Significado y Afirmaciones

El artículo afirma que el marco propuesto aborda con éxito las limitaciones de expresividad de las GNN Pre-Propagación sin recurrir a los cuellos de botella computacionales del paso de mensajes iterativo.

• Escalabilidad vs. Expresividad: El trabajo demuestra que las PP-GNNs no sacrifican inherentemente la expresividad por la escalabilidad; más bien, la brecha proviene de operadores de difusión subóptimos y la falta de refinamiento iterativo. Al utilizar bases de difusión robustas y HRP, las PP-GNNs pueden igualar o superar la precisión de las MP-GNNs mientras conservan su eficiencia de entrenamiento y capacidades de mini-lote.
• Aplicabilidad General: Aunque motivado por los desafíos de la heterofilia, se demuestra que los métodos son beneficiosos tanto en estructuras de grafos heterofílicos como homofílicos.
• Impacto Práctico: El enfoque ofrece una vía para desplegar GNNs altamente escalables en grafos a gran escala (por ejemplo, redes sociales, sistemas de recomendación) con un rendimiento competitivo frente a los modelos de paso de mensajes más avanzados, reduciendo potencialmente los costos computacionales y el consumo de energía para el aprendizaje de grafos a gran escala.

Los autores mantienen una postura modesta, señalando que, aunque los métodos mejoran el rendimiento, no introducen nuevas modalidades de datos ni previenen inherentemente los riesgos éticos downstream asociados con el aprendizaje de grafos (como la amplificación de sesgos), enfatizando la necesidad de prácticas responsables de ML en el despliegue.