Graph Neural Networks/es

Article
Topic area	deep-learning
Prerequisites	Neural Network, Graph Theory

Resumen

Una red neuronal sobre grafos (GNN) es una clase de red neuronal diseñada para operar sobre datos estructurados en forma de grafo, donde las entradas consisten en nodos conectados por aristas en lugar de mallas regulares o secuencias. A diferencia de las arquitecturas convolucionales o recurrentes, que aprovechan la topología regular de imágenes o texto, las GNN aprenden representaciones que respetan patrones de conectividad arbitrarios y permanecen invariantes ante permutaciones del orden de los nodos. Se han convertido en la herramienta estándar para problemas en los que la estructura relacional es informativa, incluyendo la predicción de propiedades moleculares, el análisis de redes sociales, los sistemas de recomendación, la previsión de tráfico y el razonamiento sobre grafos de conocimiento. La idea unificadora detrás de casi todas las variantes modernas de GNN es el paso de mensajes: cada nodo actualiza iterativamente su representación agregando información de sus vecinos, lo que permite que las características locales se propaguen a través del grafo y produzcan incrustaciones que capturan tanto los atributos de los nodos como el contexto estructural.

Intuición y motivación

Un grafo $ G = (V, E) $ consiste en un conjunto de nodos $ V $, aristas $ E \subseteq V \times V $, y características opcionales asociadas a cada nodo y arista. Muchos sistemas del mundo real son naturalmente relacionales: átomos en una molécula, usuarios en una red social, intersecciones en un mapa de carreteras, o entidades en un grafo de conocimiento. Aplicar un perceptrón multicapa estándar a tales datos requiere aplanar el grafo en un vector de tamaño fijo, lo que descarta la conectividad. Aplicar una red neuronal convolucional requiere una malla regular, de la que carecen los grafos. Una GNN sortea ambos problemas calculando las incrustaciones de los nodos como una función de la vecindad local de cada nodo, y luego componiendo capas de modo que cada capa adicional expande el campo receptivo en un salto.

Dos propiedades hacen que esto funcione en la práctica. Primero, la equivarianza por permutación: reordenar los índices de los nodos reordena las salidas de la misma manera pero no cambia sus valores, lo cual es la simetría correcta para conjuntos no ordenados de vecinos. Segundo, la localidad: la actualización de un nodo depende únicamente de sus vecinos inmediatos, por lo que los mismos parámetros pueden reutilizarse en todo el grafo independientemente de su tamaño. Juntas, estas propiedades dotan a las GNN de un fuerte sesgo inductivo para datos relacionales, de manera análoga a como la equivarianza por traslación dota a las CNN de un fuerte sesgo para imágenes.

Formulación de paso de mensajes

La abstracción dominante es el marco de red neuronal de paso de mensajes (MPNN). Sea $ h_v^{(l)} $ la incrustación del nodo $ v $ en la capa $ l $, y $ \mathcal{N}(v) $ sus vecinos. Una sola capa aplica tres pasos:

$ {\displaystyle m_v^{(l+1)} = \mathrm{AGG}^{(l)}\big(\{h_u^{(l)} : u \in \mathcal{N}(v)\}\big)} $

$ {\displaystyle h_v^{(l+1)} = \mathrm{UPD}^{(l)}\big(h_v^{(l)}, m_v^{(l+1)}\big)} $

La función de agregación $ \mathrm{AGG} $ debe ser invariante por permutación; las opciones típicas son suma, media, máximo o suma ponderada por atención. La función de actualización $ \mathrm{UPD} $ es habitualmente un pequeño MLP o una unidad con compuertas. Tras $ L $ capas, cada incrustación de nodo incorpora información de su vecindad de $ L $ saltos. Para tareas a nivel de grafo, una lectura final agrupa todas las incrustaciones de nodos en un único vector, a menudo mediante suma, media o un agrupamiento por atención aprendido.

Arquitecturas comunes

Las Redes Convolucionales sobre Grafos (GCN) definen una capa como una normalización simétrica de la matriz de adyacencia seguida de una transformación lineal y una no linealidad:

$ {\displaystyle H^{(l+1)} = \sigma\!\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H^{(l)} W^{(l)}\right)} $

donde $ \tilde{A} = A + I $ incluye autobucles, $ \tilde{D} $ es su matriz de grados, y $ \sigma $ es una no linealidad como ReLU. La GCN es esencialmente un agregador por media con ponderación basada en grado, derivado como una aproximación de primer orden de la convolución espectral sobre grafos.

GraphSAGE reemplaza la agregación sobre el vecindario completo por una muestra de tamaño fijo, permitiendo el aprendizaje inductivo en grafos demasiado grandes para caber en memoria y sobre nodos no vistos previamente.

Las Redes de Atención sobre Grafos (GAT) asignan pesos aprendibles a cada vecino mediante un mecanismo de atención, de modo que los vecinos informativos contribuyan más que los no informativos:

$ {\displaystyle \alpha_{vu} = \mathrm{softmax}_u\!\left(\mathrm{LeakyReLU}\big(a^\top [W h_v \,\|\, W h_u]\big)\right)} $

Las Redes de Isomorfismo de Grafos (GIN) usan agregación por suma con una actualización mediante un MLP inyectivo, y demuestran igualar el poder discriminativo de la prueba de isomorfismo de grafos de Weisfeiler-Leman, la mayor expresividad alcanzable por las GNN estándar de paso de mensajes.

Entrenamiento e inferencia

Las GNN se entrenan con optimizadores estándar basados en gradiente como Adam usando funciones de pérdida específicas para cada tarea: entropía cruzada para clasificación de nodos, error cuadrático medio para regresión, y pérdidas contrastivas o de margen para predicción de enlaces. Tres regímenes de tareas son comunes:

• A nivel de nodo: predecir una etiqueta para cada nodo (p. ej., categoría en una red de citas). Es típico un escenario semi-supervisado con pocos nodos etiquetados.
• A nivel de arista: predecir si dos nodos deberían estar conectados, utilizado en recomendación y completado de grafos de conocimiento.
• A nivel de grafo: predecir una propiedad del grafo completo, como la toxicidad o solubilidad molecular.

Escalar a grafos grandes requiere cuidado. El entrenamiento por lotes completos almacena todas las incrustaciones de nodos en memoria, lo que es inviable más allá de unos pocos millones de nodos. Las alternativas comunes incluyen el muestreo de vecinos (al estilo GraphSAGE), el muestreo de subgrafos (Cluster-GCN, GraphSAINT), y cachés históricas de incrustaciones que cambian obsolescencia por memoria. En tiempo de inferencia, las GNN son inductivas cuando la arquitectura parametriza una función de las características locales y no de las identidades de los nodos, lo que permite su aplicación a grafos no vistos.

Expresividad y limitaciones

Una GNN estándar de paso de mensajes es, a lo sumo, tan poderosa como la prueba 1-Weisfeiler-Leman para distinguir grafos, lo que significa que existen grafos no isomorfos que ninguna MPNN puede distinguir. Esto motiva variantes de orden superior como las GNN $ k $-WL, las GNN sobre subgrafos que aumentan las características de los nodos con identificadores estructurales, y los transformers equivariantes sobre grafos.

Dos patologías bien conocidas afectan a las GNN profundas:

• Sobresuavizado: a medida que aumenta la profundidad, la agregación repetida lleva las incrustaciones de los nodos hacia valores indistinguibles, deteriorando la exactitud. Las conexiones residuales, la normalización y los regularizadores al estilo PairNorm mitigan esto pero no lo resuelven por completo.
• Sobrecompresión: la información proveniente de nodos distantes se comprime a través de cuellos de botella estrechos, por lo que las dependencias de largo alcance son difíciles de capturar en grafos con conjuntos de cuello de botella pequeños. El recableado de grafos y los transformers sobre grafos intentan abordar esto añadiendo aristas de atajo o reemplazando el paso de mensajes local por atención global.

Las GNN también heredan los inconvenientes habituales del aprendizaje profundo: sensibilidad al desplazamiento de distribución, dependencia de características de nodos de calidad, y robustez limitada frente a perturbaciones adversarias de la estructura del grafo.

Comparaciones con otros modelos

Comparadas con las redes neuronales convolucionales, las GNN generalizan la operación de convolución a dominios irregulares; una CNN puede verse como una GNN sobre un grafo en malla regular con filtros invariantes por traslación. Comparadas con las redes neuronales recurrentes, las GNN operan sobre conjuntos de vecinos en lugar de secuencias ordenadas, pero el paso de mensajes iterado puede desenrollarse en una computación recurrente. El Transformer está estrechamente relacionado: la autoatención es equivalente a una GNN que opera sobre un grafo completamente conectado, y arquitecturas recientes de Transformer sobre grafos combinan el paso de mensajes local con atención global más codificaciones posicionales estructurales para capturar tanto el sesgo inductivo como las dependencias de largo alcance.

Aplicaciones

Las GNN han producido resultados de última generación en dominios donde la estructura importa más que las características absolutas. En química y ciencia de materiales predicen propiedades moleculares, aceleran cálculos de teoría del funcional de la densidad, y proponen rutas de síntesis. En el descubrimiento de fármacos puntúan afinidades de unión y filtran moléculas candidatas. En recomendación, modelan grafos de interacción usuario-elemento a escala de producción. En física han aprendido simuladores de dinámica de partículas y fluidos. En el análisis de código razonan sobre árboles de sintaxis abstracta y grafos de flujo de datos. La versatilidad de la abstracción de paso de mensajes, combinada con la prevalencia de los datos relacionales, ha convertido a las GNN en una herramienta central del aprendizaje automático moderno.