Introducción al Aprendizaje de Máquina en Grafos

'Aprendizaje de Máquina en Grafos' Introduction

En esta publicación de blog, cubrimos los conceptos básicos del aprendizaje automático en grafos.

Primero estudiamos qué son los grafos, por qué se utilizan y cómo representarlos de la mejor manera. Luego, brevemente, analizamos cómo las personas aprenden en grafos, desde métodos preneuronales (explorando características del grafo al mismo tiempo) hasta lo que comúnmente se llaman Redes Neuronales en Grafos. Por último, echamos un vistazo al mundo de los Transformadores para grafos.

Grafos

¿Qué es un grafo?

En esencia, un grafo es una descripción de elementos conectados por relaciones.

Ejemplos de grafos incluyen redes sociales (Twitter, Mastodon, cualquier red de citas que vincula documentos y autores), moléculas, grafos de conocimiento (como diagramas UML, enciclopedias y cualquier sitio web con hipervínculos entre sus páginas), oraciones expresadas como árboles sintácticos, cualquier malla 3D, ¡y más! Por lo tanto, no es exagerado decir que los grafos están en todas partes.

• ¿Qué hace útil a un agente de diálogo?
• Optimum+ONNX Runtime Entrenamiento más fácil y rápido para tus modelos de Hugging Face
• El estado de la Visión por Computadora en Hugging Face 🤗

Los elementos de un grafo (o red) se llaman nodos (o vértices), y sus conexiones se llaman aristas (o enlaces). Por ejemplo, en una red social, los nodos son usuarios y las aristas son sus conexiones; en una molécula, los nodos son átomos y las aristas son sus enlaces moleculares.

• Un grafo con nodos o aristas tipificadas se llama heterogéneo (por ejemplo, redes de citas con elementos que pueden ser tanto documentos como autores tienen nodos tipificados, y diagramas XML donde las relaciones están tipificadas tienen aristas tipificadas). No se puede representar únicamente a través de su topología, se necesita información adicional. Esta publicación se centra en los grafos homogéneos.
• Un grafo también puede ser dirigido (como una red de seguidores, donde A sigue a B no implica que B siga a A) o no dirigido (como una molécula, donde la relación entre átomos va en ambas direcciones). Las aristas pueden conectar diferentes nodos o un nodo consigo mismo (autoloops), pero no todos los nodos necesitan estar conectados.

Si deseas utilizar tus datos, primero debes considerar su mejor caracterización (homogéneo/heterogéneo, dirigido/no dirigido, y así sucesivamente).

¿Para qué se utilizan los grafos?

Veamos una variedad de tareas posibles que podemos realizar en grafos.

A nivel de grafo, las principales tareas son:

• generación de grafos, utilizada en el descubrimiento de medicamentos para generar nuevas moléculas plausibles,
• evolución de grafos (dado un grafo, predecir cómo evolucionará a lo largo del tiempo), utilizado en física para predecir la evolución de sistemas,
• predicción a nivel de grafo (tareas de categorización o regresión a partir de grafos), como predecir la toxicidad de las moléculas.

A nivel de nodo, generalmente se trata de la predicción de propiedades de los nodos. Por ejemplo, Alphafold utiliza la predicción de propiedades de los nodos para predecir las coordenadas 3D de los átomos dados el grafo general de la molécula y, por lo tanto, predecir cómo se pliegan las moléculas en el espacio 3D, un problema difícil de bioquímica.

A nivel de arista, se trata de la predicción de propiedades de las aristas o de la predicción de aristas faltantes. La predicción de propiedades de las aristas ayuda a la predicción de efectos secundarios de medicamentos a predecir efectos secundarios adversos dados un par de medicamentos. La predicción de aristas faltantes se utiliza en sistemas de recomendación para predecir si dos nodos en un grafo están relacionados.

También es posible trabajar a nivel de subgrafo en la detección de comunidades o la predicción de propiedades de subgrafos. Las redes sociales utilizan la detección de comunidades para determinar cómo están conectadas las personas. La predicción de propiedades de subgrafos se puede encontrar en sistemas de itinerarios (como Google Maps) para predecir los tiempos estimados de llegada.

Trabajar en estas tareas se puede hacer de dos formas.

Cuando deseas predecir la evolución de un grafo específico, trabajas en un entorno transductivo, donde todo (entrenamiento, validación y prueba) se realiza en el mismo grafo único. Si esta es tu configuración, ¡ten cuidado! Crear conjuntos de datos de entrenamiento/evaluación/prueba a partir de un solo grafo no es trivial. Sin embargo, gran parte del trabajo se realiza utilizando grafos diferentes (divisiones de entrenamiento/evaluación/prueba separadas), lo que se llama una configuración inductiva.

¿Cómo representamos los grafos?

Las formas comunes de representar un grafo para procesarlo y operarlo son:

• como el conjunto de todas sus aristas (posiblemente complementado con el conjunto de todos sus nodos)
• o como la matriz de adyacencia entre todos sus nodos. Una matriz de adyacencia es una matriz cuadrada (de tamaño de nodos * tamaño de nodos) que indica qué nodos están conectados directamente entre sí (donde (A_{ij} = 1) si (n_i) y (n_j) están conectados, de lo contrario 0). Nota: la mayoría de los grafos no están densamente conectados y, por lo tanto, tienen matrices de adyacencia dispersas, lo que puede dificultar los cálculos.

Sin embargo, aunque estas representaciones parezcan familiares, ¡no te dejes engañar!

Los grafos son muy diferentes de los objetos típicos utilizados en el aprendizaje automático porque su topología es más compleja que simplemente “una secuencia” (como texto y audio) o “una cuadrícula ordenada” (imágenes y videos, por ejemplo): aunque puedan representarse como listas o matrices, ¡su representación no debe considerarse un objeto ordenado!

Pero, ¿qué significa esto? Si tienes una frase y mezclas sus palabras, creas una nueva frase. Si tienes una imagen y reorganizas sus columnas, creas una nueva imagen.

Esto no ocurre con un grafo: si mezclas su lista de aristas o las columnas de su matriz de adyacencia, sigue siendo el mismo grafo. (Explicamos esto de manera más formal un poco más abajo, busca invarianza de permutación).

Representaciones de grafos a través del aprendizaje automático

El proceso habitual para trabajar con grafos mediante aprendizaje automático es, primero, generar una representación significativa para tus elementos de interés (nodos, aristas o grafos completos según tu tarea), y luego utilizarlos para entrenar un predictor para tu tarea objetivo. Queremos (como en otras modalidades) restringir las representaciones matemáticas de tus objetos para que los objetos similares sean matemáticamente cercanos. Sin embargo, esta similitud es difícil de definir estrictamente en el aprendizaje automático de grafos: por ejemplo, ¿son dos nodos más similares cuando tienen las mismas etiquetas o los mismos vecinos?

Nota: En las secciones siguientes, nos centraremos en generar representaciones de nodos. Una vez que tengas representaciones a nivel de nodo, es posible obtener información a nivel de arista o de grafo. Para la información a nivel de arista, puedes concatenar las representaciones de pares de nodos o realizar un producto escalar. Para la información a nivel de grafo, es posible realizar un agrupamiento global (promedio, suma, etc.) en el tensor concatenado de todas las representaciones a nivel de nodo. Sin embargo, esto suavizará y perderá información sobre el grafo; un agrupamiento jerárquico recursivo puede tener más sentido, o agregar un nodo virtual conectado a todos los demás nodos en el grafo y utilizar su representación como la representación general del grafo.

Enfoques previos a los modelos neuronales

Uso simple de características diseñadas

Antes de las redes neuronales, los grafos y sus elementos de interés se podían representar como combinaciones de características, de manera específica para cada tarea. Ahora, estas características todavía se utilizan para la ampliación de datos y el aprendizaje semisupervisado, aunque existen métodos más complejos de generación de características; puede ser esencial encontrar la mejor manera de proporcionarlas a tu red según tu tarea.

Las características a nivel de nodo pueden proporcionar información sobre la importancia (¿cuán importante es este nodo para el grafo?) y/o la estructura (¿cuál es la forma del grafo alrededor del nodo?), y se pueden combinar.

La centralidad del nodo mide la importancia del nodo en el grafo. Se puede calcular de forma recursiva sumando la centralidad de los vecinos de cada nodo hasta la convergencia, o a través de medidas de distancia más corta entre nodos, por ejemplo. El grado del nodo es la cantidad de vecinos directos que tiene. El coeficiente de agrupamiento mide cuán conectados están los vecinos del nodo. Los vectores de grado de gráficos cuentan cuántos grafos diferentes están enraizados en un nodo dado, donde los grafos son todos los mini grafos que se pueden crear con un número dado de nodos conectados (con tres nodos conectados, puedes tener una línea con dos aristas o un triángulo con tres aristas).

Las características a nivel de arista complementan la representación con información más detallada sobre la conectividad de los nodos, e incluyen la distancia más corta entre dos nodos, sus vecinos comunes y su índice Katz (que es la cantidad de caminos posibles de hasta una cierta longitud entre dos nodos; se puede calcular directamente a partir de la matriz de adyacencia).

Las características a nivel de grafo contienen información de alto nivel sobre la similitud y las especificidades del grafo. El recuento total de grafos pequeños, aunque computacionalmente costoso, proporciona información sobre la forma de los subgrafos. Los métodos de kernel miden la similitud entre grafos a través de diferentes métodos de “conjunto de nodos” (similar a un conjunto de palabras).

Enfoques basados en caminatas

Los enfoques basados en caminatas utilizan la probabilidad de visitar un nodo j desde un nodo i en una caminata aleatoria para definir métricas de similitud. Estos enfoques combinan información local y global. Por ejemplo, Node2Vec simula caminatas aleatorias entre nodos de un grafo, luego procesa estas caminatas con un skip-gram, de manera similar a como lo haríamos con palabras en oraciones, para calcular incrustaciones. Estos enfoques también se pueden utilizar para acelerar los cálculos del método Page Rank, que asigna una puntuación de importancia a cada nodo (basada en su conectividad con otros nodos, evaluada como su frecuencia de visita en una caminata aleatoria, por ejemplo).

Sin embargo, estos métodos tienen límites: no pueden obtener embeddings para nodos nuevos, no capturan la similitud estructural entre nodos de manera fina y no pueden utilizar características adicionales.

Redes Neuronales en Grafos

Las redes neuronales pueden generalizar a datos no vistos. Dadas las limitaciones de representación que mencionamos anteriormente, ¿qué características debería tener una buena red neuronal para trabajar en grafos?

Debería:

• ser invariante a la permutación:
  • Ecuación: f ( P ( G ) ) = f ( G ) f(P(G))=f(G) f ( P ( G ) ) = f ( G ) siendo f la red, P la función de permutación, G el grafo
  • Explicación: la representación de un grafo y sus permutaciones deberían ser iguales después de pasar por la red
• ser equivariante a la permutación
  • Ecuación: P ( f ( G ) ) = f ( P ( G ) ) P(f(G))=f(P(G)) P ( f ( G ) ) = f ( P ( G ) ) siendo f la red, P la función de permutación, G el grafo
  • Explicación: permutar los nodos antes de pasarlos a la red debería ser equivalente a permutar sus representaciones

Las redes neuronales típicas, como las RNN o las CNN, no son invariantes a la permutación. Por lo tanto, se introdujo una nueva arquitectura, la Red Neuronal en Grafos (GNN por sus siglas en inglés), inicialmente como una máquina basada en estados.

Un GNN está compuesto por capas sucesivas. Cada capa de un GNN representa un nodo como la combinación ( agregación ) de las representaciones de sus vecinos y de sí mismo de la capa anterior ( paso de mensajes ), además generalmente se aplica una función de activación para agregar no linealidad.

Comparación con otros modelos: Una CNN puede verse como un GNN con tamaños de vecindario fijos (a través de la ventana deslizante) y un orden específico (no es equivariante a la permutación). Un Transformer sin embeddings posicionales puede verse como un GNN en un grafo de entrada completamente conectado.

Agregación y paso de mensajes

Existen muchas formas de agregar mensajes de los nodos vecinos, como sumar o promediar, por ejemplo. Algunos trabajos destacados que siguen esta idea incluyen:

• Las Redes Convolucionales en Grafos promedian la representación normalizada de los vecinos de un nodo (la mayoría de los GNNs son en realidad GCNs);
• Las Redes de Atención en Grafos aprenden a ponderar los diferentes vecinos en función de su importancia (como los transformers);
• GraphSAGE muestrea vecinos a diferentes distancias antes de agregar su información en varios pasos con max pooling.
• Las Redes de Isomorfismo en Grafos agregan representaciones aplicando una MLP a la suma de las representaciones de los nodos vecinos.

Elegir una agregación: Algunas técnicas de agregación (especialmente el promedio/la máxima agrupación) pueden fallar al crear representaciones que diferencien finamente nodos con vecindarios diferentes de nodos similares (por ejemplo, a través del promedio, un vecindario con 4 nodos, representados como 1,1,-1,-1, promediado como 0, no será diferente a otro con solo 3 nodos representados como -1, 0, 1).

Forma de los GNN y el problema de sobre-alisado

En cada nueva capa, la representación del nodo incluye cada vez más nodos.

Un nodo, a través de la primera capa, es la agregación de sus vecinos directos. A través de la segunda capa, sigue siendo la agregación de sus vecinos directos, pero esta vez, sus representaciones incluyen a sus propios vecinos (de la primera capa). Después de n capas, la representación de todos los nodos se convierte en una agregación de todos sus vecinos a una distancia n, ¡por lo tanto, de todo el grafo si su diámetro es menor que n!

Si tu red tiene demasiadas capas, existe el riesgo de que cada nodo se convierta en una agregación de todo el grafo (y que las representaciones de los nodos converjan a la misma para todos los nodos). Esto se llama el problema de sobre-alisado

Esto se puede resolver:

• ajustando el GNN para tener un número de capas lo suficientemente pequeño como para no aproximar cada nodo como toda la red (analizando primero el diámetro y la forma del grafo)
• aumentando la complejidad de las capas
• agregando capas no relacionadas con el paso de mensajes para procesar los mensajes (como MLP simples)
• agregando conexiones de salto.

El problema de sobre-alisado es un área importante de estudio en el aprendizaje automático en grafos, ya que impide que los GNNs se escalen, como se ha demostrado en otras modalidades con los Transformers.

Transformadores de Grafos

Un Transformer sin su capa de codificación posicional es invariante a la permutación, y se sabe que los Transformers escalan bien, por lo que recientemente las personas han comenzado a adaptar los Transformers a grafos (Encuesta). La mayoría de los métodos se centran en las mejores formas de representar los grafos buscando las mejores características y las mejores formas de representar la información posicional y ajustando la atención para adaptarse a estos nuevos datos.

A continuación se presentan algunos métodos interesantes que obtuvieron resultados de vanguardia o cercanos en uno de los conjuntos de referencia más difíciles disponibles hasta la fecha de escritura, el Stanford’s Open Graph Benchmark:

• Transformador de Grafos para Aprendizaje de Grafos a Secuencia (Cai y Lam, 2020) introdujo un Codificador de Grafos, que representa los nodos como una concatenación de sus incrustaciones y codificaciones posicionales, las relaciones de nodos como los caminos más cortos entre ellos, y combina ambos en una atención de auto-relación mejorada.
• Reconsiderando los Transformadores de Grafos con Atención Espectral (Kreuzer et al, 2021) introdujo las Redes de Atención Espectral (SANs). Estas combinan características de nodos con codificación posicional aprendida (calculada a partir de los vectores/valores propios del Laplaciano), para usar como claves y consultas en la atención, siendo los valores de atención las características de las aristas.
• GRPE: Codificación Posicional Relativa para Transformador de Grafos (Park et al, 2021) introdujo el Transformador de Codificación Posicional Relativa de Grafos. Representa un grafo combinando una codificación posicional a nivel de grafo con información de nodos, una codificación posicional a nivel de arista con información de nodos, y combina ambos en la atención.
• Autoatención Global como Reemplazo para la Convolución de Grafos (Hussain et al, 2021) introdujo el Transformador con Autoatención Mejorada. Esta arquitectura incrusta nodos y aristas por separado, y los agrega en una atención modificada.
• ¿Los Transformadores Realmente Funcionan Mal para la Representación de Grafos? (Ying et al, 2021) presenta Graphormer de Microsoft, que ganó el primer lugar en el OGB cuando salió. Esta arquitectura utiliza características de nodos como consultas/claves/valores en la atención, y suma su representación con una combinación de codificaciones de centralidad, espaciales y de aristas en el mecanismo de atención.

El enfoque más reciente es Transformadores Puros como Aprendices Poderosos de Grafos (Kim et al, 2022), que introdujo TokenGT. Este método representa los grafos de entrada como una secuencia de incrustaciones de nodos y aristas (aumentadas con identificadores de nodos ortogonales y identificadores de tipo entrenables), sin codificación posicional, y proporciona esta secuencia a los Transformers como entrada. ¡Es extremadamente simple, pero inteligente!

Un poco diferente, Recipe for a General, Powerful, Scalable Graph Transformer (Rampášek et al, 2022) introduce, no un modelo, sino un marco de trabajo, llamado GraphGPS. Permite combinar redes de paso de mensajes con transformadores lineales (de largo alcance) para crear fácilmente redes híbridas. Este marco de trabajo también contiene varias herramientas para calcular codificaciones posicionales y estructurales (a nivel de nodos, grafos, aristas), aumento de características, caminatas aleatorias, etc.

El uso de transformadores para grafos aún es un campo muy incipiente, pero parece prometedor, ya que podría aliviar varias limitaciones de las GNN, como la capacidad de escalar a grafos más grandes/densos o aumentar el tamaño del modelo sin suavización excesiva.

Si desea profundizar, puede consultar algunos de estos cursos:

• Formato académico
  • Machine Learning with Graphs de Stanford
  • Graph Representation Learning de McGill
• Formato de video
  • Curso de Aprendizaje Profundo Geométrico
• Libros
  • Graph Representation Learning*, Hamilton
• Encuestas
  • Guía de Estudio de Redes Neuronales de Grafos
• Direcciones de investigación
  • GraphML in 2023 resume direcciones interesantes y plausibles para GraphML en 2023.

Algunas bibliotecas útiles para trabajar con grafos son PyGeometric o la Deep Graph Library (para ML de grafos) y NetworkX (para manipular grafos de manera más general).

Si necesita referencias de calidad, puede consultar:

• OGB, el Open Graph Benchmark: los conjuntos de datos de referencia para evaluaciones de grafos, para diferentes tareas y escalas de datos.
• Benchmarking de GNNs: biblioteca y conjuntos de datos para evaluar las redes de ML de grafos y su expresividad. El artículo asociado estudia notablemente qué conjuntos de datos son relevantes desde un punto de vista estadístico, qué propiedades de los grafos permiten evaluar y qué conjuntos de datos ya no deben utilizarse como referencia.
• Benchmark de Grafos de Largo Alcance: benchmark reciente (noviembre de 2022) que analiza la información de largo alcance en los grafos.
• Taxonomía de Benchmarks en Aprendizaje de Representación de Grafos: artículo publicado en la conferencia Learning on Graphs 2022, que analiza y clasifica los conjuntos de datos de referencia existentes.

Para obtener más conjuntos de datos, consulte:

• Paper with code Graph tasks Leaderboards : Tabla de clasificación para conjuntos de datos y pruebas públicas – tenga cuidado, no todos los puntos de referencia en esta tabla de clasificación siguen siendo relevantes
• TU datasets : Compilación de conjuntos de datos disponibles públicamente, ahora ordenados por categorías y características. La mayoría de estos conjuntos de datos también se pueden cargar con PyG, y algunos de ellos se han trasladado a Datasets
• SNAP datasets: Colección de conjuntos de datos de redes grandes de Stanford:
• Conjuntos de datos de MoleculeNet
• Repositorio de conjuntos de datos relacionales

Atribución de imágenes externas

Los emojis en la miniatura provienen de Openmoji (CC-BY-SA 4.0), la figura de Graphlets proviene de Biological network comparison using graphlet degree distribution (Pržulj, 2007).

We will continue to update Zepes; if you have any questions or suggestions, please contact us!