Redes Neuronales de Grafos: Una Introducción Amigable

Los grafos están en todas partes; los objetos del mundo real a menudo se definen en términos de sus conexiones con otras cosas. Un conjunto de objetos y las conexiones entre ellos se expresan naturalmente como un grafo. Los investigadores han desarrollado redes neuronales que operan con datos de grafos (llamadas redes neuronales de grafos o GNN) durante más de una década. Los desarrollos recientes han aumentado sus capacidades y poder expresivo. Estamos comenzando a ver aplicaciones prácticas en áreas como el descubrimiento de antibióticos, simulaciones de física, detección de noticias falsas, predicción del tráfico y sistemas de recomendación.

¿Qué son las Redes Neuronales de Grafos (GNN)?

Este artículo explora y explica las redes neuronales de grafos modernas. Lo dividimos en cuatro partes. Primero, vemos qué tipo de datos se expresan más naturalmente como un grafo y algunos ejemplos comunes. Segundo, exploramos qué diferencia a los grafos de otros tipos de datos y algunas de las elecciones especializadas que debemos hacer cuando los usamos. Tercero, construimos una GNN moderna, recorriendo cada una de las partes del modelo, comenzando con innovaciones históricas de modelado en el campo. Pasamos gradualmente de una implementación básica a un modelo GNN de última generación. Cuarto y último, proporcionamos un espacio de pruebas GNN donde puedes experimentar con una tarea y un conjunto de datos del mundo real para construir una intuición más sólida de cómo cada componente de un modelo GNN contribuye a las predicciones que realiza.

¿Qué es un Grafo?

Para empezar, establezcamos qué es un grafo. Un grafo representa las relaciones (aristas) entre una colección de entidades (nodos). Para describir aún más cada nodo, arista o el grafo completo, podemos almacenar información en cada una de estas piezas del grafo. Además, podemos especializar los grafos asociando direccionalidad a las aristas (dirigidas, no dirigidas).

Dónde encontrar grafos

Probablemente ya estés familiarizado con algunos tipos de datos de grafos, como las redes sociales. Sin embargo, los grafos son una representación de datos extremadamente poderosa y general. Mostraremos dos tipos de datos que quizás no creas que se puedan modelar como grafos: imágenes y texto.

Imágenes como grafos

Normalmente pensamos en las imágenes como cuadrículas rectangulares con canales de imagen, representándolas como matrices (por ejemplo, 244x244x3 flotantes). Otra forma de pensar en las imágenes es como grafos con estructura regular, donde cada píxel representa un nodo y está conectado a través de una arista a los píxeles adyacentes.

Texto como grafos

Podemos digitalizar el texto asociando índices a cada carácter, palabra o token, y representando el texto como una secuencia de estos índices. Esto crea un grafo dirigido simple, donde cada carácter o índice es un nodo y está conectado a través de una arista al nodo que lo sigue.

Datos con valores de grafos en el mundo real

Moléculas como grafos. Las moléculas son los bloques de construcción de la materia y están formadas por átomos y electrones en el espacio 3D. Todas las partículas interactúan, pero cuando un par de átomos están unidos a una distancia estable entre sí, decimos que comparten un enlace covalente. Es una abstracción muy conveniente y común describir este objeto 3D como un grafo, donde los nodos son átomos y las aristas son enlaces covalentes.

Redes sociales como grafos. Podemos construir un grafo que represente grupos de personas modelando a los individuos como nodos y sus relaciones como aristas.

Redes de citas como grafos. Los científicos citan rutinariamente el trabajo de otros científicos cuando publican artículos. Podemos visualizar estas redes de citas como un grafo, donde cada artículo es un nodo y cada arista dirigida es una cita entre un artículo y otro.

Otros ejemplos. Los modelos de aprendizaje automático, el código de programación y las ecuaciones matemáticas también se pueden expresar como grafos, donde las variables son nodos y las aristas son operaciones que tienen estas variables como entrada y salida.

Tipos de problemas con datos estructurados en grafos

Hay tres tipos generales de tareas de predicción en grafos: nivel de grafo, nivel de nodo y nivel de arista.

Tarea a nivel de grafo

En una tarea a nivel de grafo, nuestro objetivo es predecir la propiedad de un grafo completo. Por ejemplo, para una molécula representada como un grafo, podríamos querer predecir cómo huele o si se unirá a un receptor implicado en una enfermedad.

Tarea a nivel de nodo

Las tareas a nivel de nodo se ocupan de predecir la identidad o el rol de cada nodo dentro de un grafo. Un ejemplo clásico de un problema de predicción a nivel de nodo es el club de karate de Zach. El conjunto de datos es un único grafo de red social formado por individuos que han jurado lealtad a uno de los dos clubes de karate después de una disputa política.

Tarea a nivel de arista

El problema de predicción restante en los grafos es la predicción de aristas. Un ejemplo de inferencia a nivel de arista está en la comprensión de escenas de imágenes. Más allá de identificar objetos en una imagen, los modelos de aprendizaje profundo se pueden usar para predecir la relación entre ellos. Podemos expresar esto como una clasificación a nivel de arista: dados los nodos que representan los objetos en la imagen, deseamos predecir cuáles de estos nodos comparten una arista o cuál es el valor de esa arista.

Los desafíos de usar grafos en el aprendizaje automático

Entonces, ¿cómo resolvemos estas diferentes tareas de grafos con redes neuronales? El primer paso es pensar en cómo representaremos los grafos para que sean compatibles con las redes neuronales.

Redes Neuronales de Grafos (GNN)

Ahora que la descripción del grafo está en un formato de matriz que es invariante a la permutación, describiremos el uso de redes neuronales de grafos (GNN) para resolver tareas de predicción de grafos. Una GNN es una transformación optimizable en todos los atributos del grafo (nodos, aristas, contexto global) que preserva las simetrías del grafo (invarianzas de permutación). Vamos a construir GNN usando el marco de «red neuronal de paso de mensajes» propuesto por Gilmer et al. usando los esquemas de arquitectura de Graph Nets introducidos por Battaglia et al. Las GNN adoptan una arquitectura «grafo de entrada, grafo de salida», lo que significa que estos tipos de modelos aceptan un grafo como entrada, con información cargada en sus nodos, aristas y contexto global, y transforman progresivamente estas incrustaciones, sin cambiar la conectividad del grafo de entrada.

La GNN más simple

Con la representación numérica de grafos que hemos construido anteriormente (con vectores en lugar de escalares), ahora estamos listos para construir una GNN. Comenzaremos con la arquitectura GNN más simple, una en la que aprendemos nuevas incrustaciones para todos los atributos del grafo (nodos, aristas, global), pero donde aún no usamos la conectividad del grafo.

Pasar mensajes entre partes del grafo

Podemos hacer predicciones más sofisticadas utilizando la agrupación dentro de la capa GNN para que nuestras incrustaciones aprendidas sean conscientes de la conectividad del grafo. Podemos hacer esto usando el paso de mensajes, donde los nodos o aristas vecinos intercambian información e influyen en las incrustaciones actualizadas de los demás.

Aprendizaje de representaciones de aristas

Nuestro conjunto de datos no siempre contiene todos los tipos de información (nodo, arista y contexto global). Cuando queremos hacer una predicción en los nodos, pero nuestro conjunto de datos solo tiene información de aristas, mostramos anteriormente cómo usar la agrupación para enrutar información de las aristas a los nodos, pero solo en el paso final de predicción del modelo. Podemos compartir información entre nodos y aristas dentro de la capa GNN utilizando el paso de mensajes.

Agregar representaciones globales

Hay un defecto en las redes que hemos descrito hasta ahora: los nodos que están muy lejos el uno del otro en el grafo pueden no ser capaces de transferir información eficientemente entre sí, incluso si aplicamos el paso de mensajes varias veces. Una solución es usar la representación global de un grafo (U), que a veces se llama nodo maestro o vector de contexto. Este vector de contexto global está conectado a todos los demás nodos y aristas de la red y puede actuar como un puente entre ellos para pasar información, creando una representación más rica y compleja del grafo de la que se podría haber aprendido de otra manera.

Espacio de pruebas GNN

Hemos descrito una amplia gama de componentes GNN aquí, pero ¿cómo difieren realmente en la práctica? Este espacio de pruebas GNN te permite ver cómo estos diferentes componentes y arquitecturas contribuyen a la capacidad de una GNN para aprender una tarea real.

Algunas lecciones de diseño empírico de GNN

Al explorar las opciones de arquitectura anteriores, es posible que hayas encontrado que algunos modelos tienen un mejor rendimiento que otros. ¿Hay algunas opciones de diseño GNN claras que nos darán un mejor rendimiento? Por ejemplo, ¿los modelos GNN más profundos tienen un mejor rendimiento que los más superficiales? o ¿hay una opción clara entre las funciones de agregación? Las respuestas dependerán de los datos.

En detalle

Otros tipos de grafos (multigrafos, hipergrafos, hipernodos, grafos jerárquicos)

Si bien solo describimos grafos con información vectorizada para cada atributo, las estructuras de grafos son más flexibles y pueden acomodar otros tipos de información. Afortunadamente, el marco de paso de mensajes es lo suficientemente flexible como para que, a menudo, adaptar las GNN a estructuras de grafos más complejas se trate de definir cómo se pasa y actualiza la información mediante nuevos atributos de grafo.

Muestreo de grafos y agrupación en GNN

Una práctica común para entrenar redes neuronales es actualizar los parámetros de la red con gradientes calculados en subconjuntos aleatorios de tamaño constante (tamaño de lote) de los datos de entrenamiento (mini lotes). Esta práctica presenta un desafío para los grafos debido a la variabilidad en el número de nodos y aristas adyacentes entre sí, lo que significa que no podemos tener un tamaño de lote constante. La idea principal para la agrupación con grafos es crear subgrafos que preserven las propiedades esenciales del grafo más grande.

Sesgos inductivos

Cuando construimos un modelo para resolver un problema en un tipo específico de datos, queremos especializar nuestros modelos para aprovechar las características de esos datos. Cuando esto se hace con éxito, a menudo vemos un mejor rendimiento predictivo, un menor tiempo de entrenamiento, menos parámetros y una mejor generalización.

Comparación de operaciones de agregación

Agrupar información de nodos y aristas vecinos es un paso crítico en cualquier arquitectura GNN razonablemente poderosa. Debido a que cada nodo tiene un número variable de vecinos, y debido a que queremos un método diferenciable para agregar esta información, queremos usar una operación de agregación suave que sea invariante al orden de los nodos y al número de nodos proporcionados.

Aristas y el dual del grafo

Una cosa a tener en cuenta es que las predicciones de aristas y las predicciones de nodos, aunque aparentemente diferentes, a menudo se reducen al mismo problema: una tarea de predicción de aristas en un grafo G se puede expresar como una predicción a nivel de nodo en el dual de G.

Convoluciones de grafos como multiplicaciones de matrices y multiplicaciones de matrices como recorridos en un grafo

Hemos hablado mucho sobre convoluciones de grafos y paso de mensajes, y por supuesto, esto plantea la pregunta de ¿cómo implementamos estas operaciones en la práctica? Para esta sección, exploramos algunas de las propiedades de la multiplicación de matrices, el paso de mensajes y su conexión con el recorrido de un grafo.

Redes de atención de grafos

Otra forma de comunicar información entre atributos de grafo es a través de la atención. Por ejemplo, cuando consideramos la suma de agregación de un nodo y sus nodos vecinos de 1 grado, también podríamos considerar el uso de una suma ponderada. El desafío entonces es asociar pesos de una manera invariante a la permutación. Un enfoque es considerar una función de puntuación escalar que asigne pesos basados en pares de nodos (f(nodo_i, nodo_j)). En este caso, la función de puntuación se puede interpretar como una función que mide qué tan relevante es un nodo vecino en relación con el nodo central.

Explicación y atribuciones de grafos

Cuando implementamos GNN en el mundo real, podemos preocuparnos por la interpretabilidad del modelo para generar credibilidad, depuración o descubrimiento científico. Los conceptos de grafo que nos interesa explicar varían de un contexto a otro. Por ejemplo, con las moléculas, podemos preocuparnos por la presencia o ausencia de subgrafos particulares, mientras que en una red de citas, podemos preocuparnos por el grado de conectividad de un artículo. Debido a la variedad de conceptos de grafo, hay muchas maneras de construir explicaciones.

Modelado generativo

Además de aprender modelos predictivos en grafos, también podemos preocuparnos por aprender un modelo generativo para grafos. Con un modelo generativo, podemos generar nuevos grafos muestreando de una distribución aprendida o completando un grafo dado un punto de partida. Una aplicación relevante está en el diseño de nuevos medicamentos, donde se desean nuevos grafos moleculares con propiedades específicas como candidatos para tratar una enfermedad.

Pensamientos finales

Los grafos son un tipo de datos estructurados poderosos y ricos que tienen fortalezas y desafíos muy diferentes a los de las imágenes y el texto. En este artículo, hemos descrito algunos de los hitos que los investigadores han ideado para construir modelos basados en redes neuronales que procesan grafos. Hemos recorrido algunas de las opciones de diseño importantes que deben tomarse al usar estas arquitecturas, y esperamos que el espacio de pruebas GNN pueda dar una intuición sobre cuáles son los resultados empíricos de estas opciones de diseño. El éxito de las GNN en los últimos años crea una gran oportunidad para una amplia gama de nuevos problemas, y estamos entusiasmados de ver lo que aportará el campo.

Fuente original: A Gentle Introduction to Graph Neural Networks