Las redes neuronales de grafos (GNN) son una clase de redes neuronales artificiales diseñadas para operar sobre datos estructurados en grafos, donde las entradas consisten en nodos (vértices) y aristas (conexiones) que pueden carecer de un orden canónico. A diferencia de las redes neuronales estándar que asumen entradas ordenadas de tamaño fijo, las GNN están construidas para manejar grafos de tamaños y topologías variables, lo que las hace adecuadas para dominios como la química molecular, el análisis de redes sociales y la optimización combinatoria. La innovación central de las GNN reside en su uso de paso de mensajes por pares, donde cada nodo actualiza iterativamente su representación agregando información de sus vecinos, lo que permite a la red capturar patrones estructurales locales y dependencias.
Las GNN están típicamente diseñadas para ser equivariantes a permutaciones, lo que significa que reordenar los nodos en el grafo de entrada resulta en un reordenamiento correspondiente de las representaciones de nodos producidas por la red. Para tareas de predicción a nivel de grafo, como predecir una propiedad de una molécula completa, las GNN emplean una función de lectura invariante a permutaciones que agrega las representaciones de los nodos en una salida de tamaño fijo, asegurando que el resultado no se vea afectado por el orden de los nodos. Esta propiedad es esencial porque los grafos no tienen un orden natural de nodos, y la salida de la red debe ser consistente independientemente de cómo se represente el grafo.
Desarrollo Histórico
El concepto de las GNN surgió de trabajos anteriores sobre redes neuronales para datos estructurados, con ideas fundacionales que se remontan a la década de 1990. Los primeros enfoques, como las redes neuronales recursivas aplicadas a grafos acíclicos dirigidos, sentaron las bases para procesar estructuras similares a grafos. Sin embargo, la formulación moderna de las GNN, basada en el paso de mensajes y la equivariancia a permutaciones, ganó prominencia en la década de 2010 con el auge del aprendizaje profundo. Investigadores de instituciones como MIT CSAIL y Stanford AI Lab contribuyeron al desarrollo de arquitecturas que pudieran manejar grafos arbitrarios, lo que llevó al establecimiento de las GNN como un subcampo distinto dentro del aprendizaje automático.
A finales de la década de 2010, las GNN se habían convertido en una herramienta estándar en el aprendizaje profundo, con numerosas variantes propuestas para mejorar su poder expresivo y escalabilidad. El artículo de posición de 2022 "Weisfeiler and Leman Go Neural" y trabajos similares formalizaron la relación entre las GNN y las pruebas de isomorfismo de grafos, aclarando sus limitaciones teóricas e inspirando investigaciones hacia arquitecturas más potentes.
Arquitectura
La arquitectura de una GNN genérica implementa varias capas fundamentales que trabajan juntas para procesar entradas estructuradas en grafos. Estas capas incluyen capas equivariantes a permutaciones, capas de agrupación local y capas de agrupación global, cada una sirviendo a un propósito distinto en la transformación de la representación del grafo.
Las capas equivariantes a permutaciones son el núcleo de las GNN, implementadas mediante paso de mensajes por pares entre los nodos del grafo. En una capa de paso de mensajes, cada nodo actualiza su representación agregando mensajes recibidos de sus vecinos inmediatos. Este proceso aumenta el campo receptivo de la GNN en un salto por capa, permitiendo a la red incorporar información de vecindarios progresivamente más grandes. La operación de paso de mensajes puede expresarse formalmente como una función que toma características de nodos, características de vecinos y características de aristas como entradas, y produce una representación de nodo actualizada.
Las capas de agrupación local reducen el grafo mediante submuestreo, disminuyendo el número de nodos mientras preservan información estructural importante. Esto es análogo a las capas de agrupación en las redes neuronales convolucionales (CNN) y ayuda a aumentar el campo receptivo de la GNN. Ejemplos comunes incluyen la agrupación de k-vecinos más cercanos, la agrupación top-k y la agrupación por autoatención, cada una seleccionando un subconjunto de nodos a retener basado en diferentes criterios.
Las capas de agrupación global, también conocidas como capas de lectura, proporcionan una representación de tamaño fijo de todo el grafo. Estas capas deben ser invariantes a permutaciones, lo que significa que cualquier permutación de los nodos y aristas del grafo no altera la salida final. Las operaciones de suma, media y máximo elemento a elemento son opciones típicas para la agrupación global, agregando representaciones de nodos en un solo vector que puede usarse para predicciones a nivel de grafo.
Capas de Paso de Mensajes
Las capas de paso de mensajes son el componente definitorio de las GNN, implementando transformaciones equivariantes a permutaciones a través de un proceso conocido como redes neuronales de paso de mensajes (MPNN). Dado un grafo G = (V, E) con un conjunto de nodos V y un conjunto de aristas E, cada nodo u en V tiene características asociadas x_u, y cada arista (u, v) en E tiene características e_uv. El vecindario de un nodo u, denotado N_u, consiste en todos los nodos v tales que (u, v) es una arista en E.
Una capa MPNN actualiza la representación de cada nodo u usando una función de paso de mensajes. La capa calcula mensajes de cada vecino v a u, donde el mensaje es una función de las características del nodo fuente, las características del nodo objetivo y las características de la arista. Estos mensajes se agregan usando una operación invariante a permutaciones, como suma, media o máximo, y luego se combinan con las características propias del nodo a través de una función de actualización diferenciable, típicamente una red neuronal. Este proceso puede repetirse para múltiples capas, permitiendo que la información se propague a través del grafo.
El diseño de las funciones de paso de mensajes varía entre diferentes arquitecturas de GNN. Algunas usan transformaciones lineales simples, mientras que otras emplean mecanismos de atención más complejos o unidades recurrentes con compuertas. La elección de la operación de agregación también afecta el poder expresivo de la red y su capacidad para capturar diferentes tipos de información estructural.
Poder Expresivo y Limitaciones
Las GNN estándar de paso de mensajes son, como máximo, tan expresivas como la prueba de isomorfismo de grafos de Weisfeiler-Lehman, un algoritmo clásico para determinar si dos grafos son isomorfos. Esto significa que existen estructuras de grafos distintas que no pueden ser distinguidas por las GNN estándar, ya que pueden producir representaciones idénticas para grafos no isomorfos. Esta limitación surge de la naturaleza local del paso de mensajes, que se basa en agregar información de vecinos inmediatos y puede fallar en capturar patrones estructurales globales.
Para superar estas limitaciones, los investigadores han propuesto GNN más potentes que operan en geometrías de dimensiones superiores, como complejos simpliciales o hipergrafos, que pueden codificar interacciones de orden superior más allá de las aristas por pares. A partir de 2022, si las arquitecturas futuras superarán completamente el primitivo de paso de mensajes sigue siendo una pregunta de investigación abierta, con trabajos en curso explorando paradigmas alternativos como los transformadores de grafos y las redes neuronales equivariantes.
Aplicaciones
Las GNN han encontrado aplicaciones en una amplia gama de dominios, aprovechando su capacidad para procesar datos estructurados en grafos. En biología molecular y química, las moléculas se representan como grafos con nodos para átomos y aristas para enlaces químicos, a menudo incluyendo propiedades químicas conocidas como características. Las tareas a nivel de grafo incluyen predecir la eficacia de una molécula para una aplicación médica específica, como eliminar la bacteria E. coli, o estimar propiedades físicas y químicas como la solubilidad y la toxicidad. Esto convierte a las GNN en herramientas valiosas en el diseño de fármacos y la ciencia de materiales.
En el procesamiento del lenguaje natural, las GNN pueden aplicarse a árboles de dependencia sintáctica o grafos de roles semánticos, capturando relaciones entre palabras en una oración. También se utilizan en el análisis de redes sociales para modelar interacciones de usuarios, detectar comunidades y predecir enlaces. Las redes de citas, donde los nodos representan artículos y las aristas representan citas, son otra aplicación común, permitiendo tareas como la clasificación y recomendación de artículos.
Las GNN también son relevantes en física, donde pueden modelar interacciones de partículas o simular sistemas dinámicos, y en problemas de optimización combinatoria NP-difíciles, donde pueden aprender heurísticas para tareas como el coloreado de grafos o los problemas del viajante. La versatilidad de las GNN ha llevado a su adopción tanto en la investigación académica como en aplicaciones industriales.
Relación con Otras Arquitecturas de Redes Neuronales
En el contexto más amplio del aprendizaje profundo geométrico, ciertas arquitecturas de redes neuronales existentes pueden interpretarse como GNN operando sobre grafos definidos adecuadamente. Una capa de red neuronal convolucional (CNN), comúnmente utilizada en visión por computadora, puede considerarse una GNN aplicada a grafos cuyos nodos son píxeles, con aristas conectando solo píxeles adyacentes. Esta perspectiva resalta los principios compartidos de conectividad local y agregación de características entre las CNN y las GNN.
De manera similar, una capa de transformador, ampliamente utilizada en el procesamiento del lenguaje natural y en grandes modelos de lenguaje, puede verse como una GNN aplicada a grafos completos cuyos nodos son palabras o tokens en un pasaje de texto. En esta interpretación, el mecanismo de atención en los transformadores actúa como una forma de paso de mensajes, donde cada token agrega información de todos los demás tokens. Esta conexión ha inspirado investigaciones hacia la unificación de estas arquitecturas y la aplicación de conocimientos de las GNN para mejorar los modelos basados en transformadores.
Bibliotecas de Software y Herramientas
Se han desarrollado varias bibliotecas de código abierto para facilitar la implementación y el despliegue de las GNN. PyTorch Geometric, construido sobre el marco PyTorch, proporciona un conjunto completo de herramientas para el procesamiento de datos de grafos y capas de paso de mensajes. TensorFlow GNN ofrece funcionalidad similar dentro del ecosistema TensorFlow. La Deep Graph Library (DGL) es una biblioteca independiente del marco que soporta múltiples backends, incluyendo PyTorch, TensorFlow y Apache MXNet. Para usuarios de Google JAX, jraph proporciona una biblioteca ligera para redes neuronales de grafos. En el lenguaje de programación Julia, GraphNeuralNetworks.jl y GeometricFlux.jl ofrecen implementaciones de GNN construidas sobre el marco de aprendizaje automático Flux.
Estas bibliotecas han reducido la barrera de entrada para investigadores y profesionales, permitiendo la creación rápida de prototipos y la experimentación con varias arquitecturas de GNN. Incluyen implementaciones de capas estándar de paso de mensajes, operaciones de agrupación y utilidades para cargar y procesar conjuntos de datos de grafos, haciendo que las GNN sean accesibles a una amplia audiencia.
Direcciones Futuras
La investigación sobre las GNN continúa evolucionando, con áreas activas de investigación que incluyen la mejora del poder expresivo, la escalabilidad a grafos grandes y la robustez ante datos ruidosos o incompletos. El desarrollo de transformadores de grafos, que combinan mecanismos de atención con la estructura del grafo, representa una dirección prometedora para capturar dependencias de largo alcance. Además, hay un interés creciente en aplicar las GNN a grafos dinámicos, donde los nodos y aristas cambian con el tiempo, y a grafos heterogéneos con múltiples tipos de nodos y aristas.
A partir de principios de la década de 2020, las GNN se han convertido en un componente estándar del kit de herramientas del aprendizaje automático, con contribuciones continuas de instituciones académicas y laboratorios de investigación industrial. La comprensión teórica de sus capacidades y limitaciones continúa profundizándose, guiando el diseño de arquitecturas de próxima generación que puedan abordar problemas basados en grafos cada vez más complejos.