TecNoticias, tu portal de información

Paso de mensajes de todos los pares con O(N)

Imagen: Unsplash. Recientemente, la creación de modelos de Transformer para manejar datos estructurados en gráficos ha despertado un gran interés en la comunidad de investigación de aprendizaje automático. Un desafío crítico surge de la complejidad cuadrática de la atención global que dificulta el escalado de Transformers a gráficos grandes. Este blog presentará brevemente un trabajo reciente sobre NeurIPS22:

NodeFormer: un transformador de aprendizaje de estructura gráfica escalable para la clasificación de nodos con su implementación pública disponible.

Este trabajo propone un transformador de gráficos escalable para gráficos de clasificación de nodos grandes donde los números de nodos pueden variar de miles a millones (o incluso más). El módulo clave es un paso de mensajes kernelizado basado en Gumbel-Softmax que logra propagación de características de todos los pares dentro de la complejidad O (N) (N para #nodos). El siguiente contenido resumirá la idea principal y los resultados de este trabajo. A diferencia de las redes neuronales gráficas (GNN) que recurren al paso de mensajes sobre una topología gráfica de entrada fija, los transformadores gráficos pueden agregar de manera más flexible información global de todos los nodos mediante topología adaptativa en cada capa de propagación. Específicamente, los Transformadores gráficos tienen varias ventajas:Manejo de estructuras imperfectas. Para datos de gráficos con heterofilia, dependencia de largo alcance y bordes espurios, los GNN a menudo muestran una potencia insuficiente debido a sus diseños de agregación de características locales. Sin embargo, los transformadores adoptan una atención global que agrega información de todos los nodos en una capa, lo que puede superar las limitaciones de las estructuras de entrada.Evitar el aplastamiento excesivo. Los GNN pueden perder la información de manera exponencial al agregar información en un vector de longitud fija, mientras que los transformadores de gráficos aprovechan la agregación atenta global que puede atender de forma adaptativa a los nodos dominantes que son informativos para las tareas predictivas del nodo de destino.Flexibilidad para tareas sin gráficos. Más allá de los problemas de gráficos, también existe una amplia variedad de tareas en las que no existe una estructura gráfica. Por ejemplo, clasificación de imágenes y texto (cada imagen puede verse como un nodo pero no hay un gráfico que las conecte) y simulación física (cada partícula es un nodo pero no un gráfico observado explícitamente). Si bien una práctica común es usar k-NN sobre características de entrada para construir un gráfico de similitud para el paso de mensajes, dicho gráfico creado artificialmente a menudo es independiente de las tareas predictivas posteriores y conduciría a un rendimiento subóptimo. Los transformadores resuelven este problema al permitir el aprendizaje automático de estructuras gráficas adaptables para el paso de mensajes.Para la clasificación de nodos, Transformers puede agregar información de todos los demás nodos en una capa. La regla de actualización por capas proporcionada por Transformers se puede ver como una composición de actualización de incrustación de nodo de un paso y estimación de estructura de gráfico (podemos tratar la matriz de atención como una matriz de adyacencia de gráfico) Varios desafíos hacen que sea un problema no trivial para construir Transformadores en gráficos grandes, en particular los que tienen más de miles de nodos.Complejidad cuadrática para la atención global: El cálculo de atención para la agregación de características de todos los pares requiere una complejidad O(N²) que es prohibitiva para gráficos grandes donde N puede ser arbitrariamente grande, por ejemplo, de miles a millones. Hablando concretamente, una GPU común con 16 GB de memoria no podría ejecutar tal atención global en todos los nodos si N es más de 10K.Recomendación de Graph Sparsity: Los gráficos del mundo real a menudo son escasos en comparación con el gráfico atento (podemos tratar la matriz de atención como una matriz de adyacencia de gráfico ponderado) que conecta densamente todos los pares de nodos. El problema es que cuando N aumenta, la propagación de características en un gráfico tan denso puede causar lo que llamamos un problema de sobrenormalización, lo que significa que la información de diferentes nodos se diluye en otros. Un remedio plausible para dispersar las estructuras aprendibles antes de la propagación. Nuestro trabajo NodeFormer combina un mapa de características aleatorias y Gumbel-Softmax como un modelo unificado para abordar los problemas mencionados anteriormente. Específicamente, Gumbel-Softmax se usa por primera vez para reemplazar la agregación de características atenta original basada en Softmax:La actualización para la representación de nodos de la siguiente capa usando todas las representaciones de nodos en la capa actual. El Gumbel-Sofmtax puede verse como la relajación continua de muestrear un nodo vecino de todos los nodos para el nodo de destino u. En la práctica, se pueden muestrear K veces, lo que da lugar a un conjunto de nodos vecinos muestreados. q, k, v son características transformadas a partir de representaciones de nodos. La ecuación anterior define el cálculo para el nodo u que requiere O(N), y para calcular las representaciones para N nodos se requiere una complejidad O(N²) ya que uno tiene que calcular de forma independiente todos los pares de puntajes de atención. Para resolver esta dificultad, recurrimos a la idea principal en Performer y adoptamos el mapa de características aleatorias (RFM) para aproximar el Gumbel-Softmax (la adopción original de RFM en Performer tiene como objetivo aproximar la atención determinista de Softmax y aquí extendemos dicha técnica a Gumbel-Softmax con ruido estocástico).La nueva regla de actualización que utiliza el Gumbel-Softmax kernelizado propuesto. La derivación de LHS a RHS está de acuerdo con la regla de asociación básica del producto matricial Críticamente, en el nuevo cálculo, es decir, el RHS de la ecuación anterior, los dos términos de suma (sobre N nodos) son compartidos por todos los nodos y pueden calcularse una sola vez en una capa. Por lo tanto, esto da lugar a una complejidad O(N) para actualizar N nodos en una capa. Otra cuestión importante es cómo hacer uso de las estructuras de entrada (si están disponibles) ya que el mensaje anterior de todos los pares ignora el gráfico de entrada. Además proponemos dos estrategias simples:Adición de sesgo relacional: además, asumimos un término escalar aprendible que se agrega a la puntuación de atención entre los nodos u y v si hay un borde entre ellos en el gráfico de entrada.Pérdida de regularización de borde: use la puntuación de atención para el borde (u, v) como una probabilidad estimada y defina una pérdida de estimación de máxima verosimilitud (MLE) para todos los bordes observados. Intuitivamente, este diseño maximiza el peso de la atención para los bordes observados. Pero la importancia (o, digamos, la información) del gráfico de entrada varía entre diferentes conjuntos de datos. Entonces, en la práctica, uno necesita ajustar el peso (como un hiperparámetro) que determina cuánto énfasis en los gráficos de entrada. La siguiente figura muestra el flujo de datos general de NodeFormer.Flujo de datos de NodeFormer cuyas entradas contienen características de nodo y adyacencia de gráficos similares a los GNN comunes. La parte roja es el mensaje de todos los pares que pasa por Gumbel-Softmax kernelizado, la parte verde es el sesgo relacional y la parte azul es para la pérdida de regularización de borde. Los últimos dos componentes se pueden omitir si el gráfico de entrada no es importante o no está disponible. Aplicamos NodeFormer a las tareas de clasificación de nodos y logramos resultados muy competitivos en ocho conjuntos de datos en comparación con los GNN comunes y los modelos de aprendizaje de estructura gráfica de última generación LDS e IDGL .Resultados de experimentos comparativos para NodeFormer y modelos GNN comunes Más allá de la clasificación de nodos, también consideramos tareas de clasificación de imágenes y texto donde faltan gráficos de entrada. Usamos k-NN con diferentes k (5, 10, 15, 20) para construir un gráfico y también consideramos no usar el gráfico de entrada para NodeFormer. Curiosamente, el último caso no conduce a una caída obvia del rendimiento y, en ocasiones, puede generar un mejor rendimiento.Visualización de incrustaciones de nodos y puntajes de atención estimados (filtre los que tienen pesos bajos). Marcamos los nodos de la misma clase de etiqueta con un color. La atención global tiende a conectar nodos dentro de la misma clase y también aumenta la conectividad global del grafo. Aquí destacamos algunas ventajas de NodeFormer:Capacidad: NodeFormer aprende de forma adaptativa la estructura del gráfico a través de escasas atenciones en cada capa y potencialmente agrega información de todos los nodos.Escalabilidad: NodeFormer permite la complejidad O(N) y el entrenamiento de particiones en minilotes. En la práctica, se escala con éxito a gráficos grandes con millones de nodos utilizando solo 4 GB de memoria.Eficiencia: El entrenamiento de NodeFormer se puede realizar de manera eficiente de principio a fin con la optimización basada en gradientes. Por ejemplo, el entrenamiento y la evaluación de Cora en 1000 épocas solo toma de 1 a 2 minutos.Flexibilidad: NodeFormer es flexible para el aprendizaje inductivo y el manejo de casos sin gráficos. Este blog presenta un nuevo Transformador de gráficos que escala con éxito a gráficos grandes y muestra un rendimiento prometedor sobre los GNN comunes. Los modelos de estilo transformador poseen algunas ventajas inherentes que pueden superar las limitaciones de las GNN con respecto al manejo de la dependencia de largo alcance, la heterofilia, el aplastamiento excesivo, el ruido de gráficos y la ausencia total de gráficos. A pesar de esto, la construcción de potentes transformadores de gráficos que puedan servir como modelo de representación de gráficos de próxima generación sigue siendo un problema abierto y poco explorado, y esperamos que este trabajo pueda arrojar algunas ideas en esta dirección. Si está interesado en este trabajo, puede leer el papel para más detalles.

artículo: https://openreview.net/pdf?id=sMezXGG5Socode: https://github.com/qitianwu/NodeFormer

Todas las imágenes, a menos que se indique lo contrario, son del autor.