Redes Neuronales con Paso de Mensajes Retrasado y Reconfiguración Dinámica

Neural Networks with Delayed Message Passing and Dynamic Reconfiguration.

Mensaje de paso de mensajes retrasado

Las redes neuronales de grafos que utilizan el paso de mensajes (MPNN) tienden a sufrir del fenómeno de sobreaplastamiento, lo que ocasiona una disminución en el rendimiento para las tareas que dependen de interacciones a larga distancia. Esto se debe principalmente a que el paso de mensajes solo ocurre a nivel local, en los vecinos inmediatos de un nodo. Las técnicas de reconexión de grafos estáticos tradicionales intentan contrarrestar este efecto permitiendo que los nodos distantes se comuniquen instantáneamente (y, en el caso extremo de los transformadores, haciendo que todos los nodos sean accesibles en cada capa). Sin embargo, esto tiene un costo computacional y conlleva la ruptura del sesgo inductivo proporcionado por la estructura del grafo de entrada. En esta publicación, describimos dos mecanismos nuevos para superar el sobreaplastamiento mientras compensamos los efectos secundarios de los enfoques de reconexión estática: la reconexión dinámica y el mensaje de paso de mensajes retrasado. Estas técnicas se pueden incorporar en cualquier MPNN y dan como resultado un mejor rendimiento que los transformadores de grafos en tareas a larga distancia.

Esta publicación fue coescrita con Francesco Di Giovanni y Ben Gutteridge y se basa en el trabajo de B. Gutteridge et al., DRew: Dynamically rewired message passing with delay (2023), ICML.

Las redes neuronales de grafos de paso de mensajes clásicas (MPNN) operan mediante la agregación de información de los vecinos a 1 salto de cada nodo. En consecuencia, las tareas de aprendizaje que requieren interacciones a larga distancia (es decir, existe un nodo v cuya representación debe tener en cuenta la información contenida en algún nodo u a la distancia más corta (geodésica) d (u, v) = r > 1) requieren MPNN profundos con múltiples capas de paso de mensajes. Si la estructura del grafo es tal que el campo receptivo se expande exponencialmente rápido con la distancia de salto [1], puede que sea necesario “aplastar” demasiados mensajes en un vector de características de nodo fijo, un fenómeno conocido como sobreaplastamiento [2].

Sobreaplastamiento

En nuestros trabajos anteriores [3-4], formalizamos el sobreaplastamiento como la falta de sensibilidad de la salida de MPNN en un nodo u a la entrada en un nodo r-distante. Esto se puede cuantificar por un límite en la derivada parcial (Jacobian) de la forma

• Calcular la Eficiencia Computacional de los Modelos de Aprendizaje Profundo con FLOPs y MACs
• Revolucionando la eficiencia de la IA El SqueezeLLM de UC Berkeley presenta la cuantificación densa y dispersa, uniendo la calidad y la velocidad en la entrega de modelos de lenguaje grandes.
• Meta AI presenta I-JEPA revolucionario Un gran salto innovador en la visión por computadora que emula el aprendizaje y el razonamiento humano y animal.

|∂ x ᵤ ⁽ ʳ ⁾/∂ x ᵥ ⁽⁰⁾| < c (A ʳ) ᵤᵥ.

Aquí, c es una constante dependiente de la arquitectura MPNN (por ejemplo, regularidad de Lipschitz de la función de activación, profundidad, etc.) y A es la matriz de adyacencia normalizada del grafo. El sobreaplastamiento ocurre cuando las entradas de A ʳ decaen exponencialmente rápido con la distancia r. De hecho, ahora se sabe que el sobreaplastamiento es más generalmente un fenómeno que puede estar relacionado con la estructura local del grafo (como la curvatura negativa [3]), o su estructura global más allá de la distancia de la ruta más corta (por ejemplo, tiempo de conmutación o resistencia efectiva [4, 5]).

Las potencias A ʳ en la expresión anterior reflejan el hecho de que la comunicación entre los nodos u y v a una distancia r en un MPNN es una secuencia de interacciones entre nodos adyacentes que comprenden diferentes caminos que conectan u y v. Como resultado, los nodos u y v intercambian información solo a partir de la capa r, y con una latencia igual a su distancia r. La sobresaturación se debe a que esta información se “diluye” a través del paso de mensajes repetidos sobre nodos intermedios a lo largo de estos caminos.

Reconexión de grafos

El problema de la sobresaturación se puede abordar parcialmente mediante la desconexión de la estructura del grafo de entrada de aquella que se utiliza como soporte para el cálculo de los mensajes, un procedimiento conocido como reconexión de grafos [6]. Por lo general, la reconexión se realiza como paso de preprocesamiento en el que el grafo de entrada G se reemplaza por algún otro grafo G’ que sea “más amigable” para el paso de mensajes, de acuerdo con alguna medida de conectividad espacial o espectral.

La forma más sencilla de lograr esto consiste en conectar todos los nodos dentro de una cierta distancia, permitiéndoles intercambiar información directamente. Esta es la idea detrás del esquema de paso de mensajes multi-salto [7]. Los Transformadores de Grafos [8] llevan esto al extremo, conectando todos los pares de nodos a través de un borde ponderado por atención.

De esta manera, la información ya no se “mezcla” con la de otros nodos a lo largo del camino y se puede evitar la sobresaturación. Sin embargo, tal reconexión hace que el grafo sea mucho más denso desde la primera capa, aumentando la huella computacional y comprometiendo en parte el sesgo inductivo otorgado por el grafo de entrada, ya que tanto los nodos locales como los globales interactúan de manera idéntica e instantánea en cada capa.

Reconexión dinámica de grafos

Al observar nuestro ejemplo anterior de dos nodos u y v a una distancia r > 1, en un MPNN clásico, hay que esperar r capas antes de que u y v puedan interactuar, y esta interacción nunca es directa. En cambio, sostenemos que una vez que llegamos a la capa r, los dos nodos han esperado “suficiente tiempo” y, por lo tanto, se les puede permitir interactuar directamente (a través de un borde adicional insertado, sin pasar por vecinos intermedios).

En consecuencia, en la primera capa propagamos mensajes solo sobre los bordes del grafo de entrada (como en los MPNN clásicos), pero en cada capa subsiguiente, el campo receptivo del nodo u se expande un salto [9]. Esto permite a los nodos distantes intercambiar información sin pasos intermedios mientras se preserva el sesgo inductivo otorgado por la topología del grafo de entrada: el grafo se densifica gradualmente en capas profundas de acuerdo con la distancia.

Llamamos a este mecanismo reconexión dinámica de grafos, o DRew abreviado [10]. Los MPNN de DRew se pueden ver como el “término medio” entre los MPNN clásicos que actúan localmente en el grafo de entrada y los Transformadores de Grafos que consideran todas las interacciones por pares a la vez.

Paso de mensajes retrasado

En los MPNN clásicos, dos nodos u y v a una distancia r siempre interactúan con un retraso constante de r capas, el tiempo mínimo que se tarda en llegar información de un nodo al otro. Por lo tanto, el nodo v “ve” el estado del nodo u (mezclado con las características de otros nodos) desde hace r capas. En cambio, en los MPNN de DRew, cuando dos nodos interactúan, lo hacen de manera instantánea, a través de un borde adicional insertado, utilizando su estado actual.

El paso de mensajes retrasado es un compromiso entre estos dos casos extremos: agregamos un retraso global (un hiperparámetro 𝝼) para los mensajes enviados entre los nodos.

Para simplificar, consideramos aquí dos casos simples: o bien sin retraso (como en DRew), o el caso de retraso máximo, donde dos nodos u y v a distancia r interactúan directamente desde la capa r en adelante, pero con un retraso constante de r (como en los MPNN clásicos): en la capa r, el nodo u puede intercambiar información con el estado del nodo v como era hace r capas [11].

El retraso controla la velocidad con la que fluye la información sobre el grafo. Sin retraso significa que los mensajes viajan más rápido, con nodos distantes interactuando instantáneamente una vez que se agrega un borde; por el contrario, cuanto mayor es el retraso, más lento es el flujo de información, con nodos distantes accediendo a estados pasados cuando se agrega un borde.

El marco 𝝼DRew

Llamamos a una arquitectura que combina el cableado dinámico con el paso de mensajes retrasado 𝝼DRew (pronunciado “Andrew”).

Una forma de ver 𝝼DRew es como una arquitectura con conexiones de salto dispersas, lo que permite que los mensajes viajen no solo “horizontalmente” (entre nodos del grafo dentro de la misma capa, como en los MPNN clásicos), sino también “verticalmente” (a través de diferentes capas). La idea de depender de bordes verticales en GNNs no es nueva, y de hecho se puede pensar en las conexiones residuales como enlaces verticales que conectan cada nodo con el mismo nodo en la capa anterior.

El mecanismo de retraso extiende este enfoque creando bordes verticales que conectan un nodo u y un nodo v diferente en alguna capa anterior dependiendo de la distancia del grafo entre u y v. De esta manera, podemos aprovechar los beneficios intrínsecos de las conexiones de salto para las redes neuronales profundas mientras las condicionamos en la información geométrica adicional que tenemos a nuestra disposición en forma de distancia del grafo.

𝝼DRew alivia la sobrepresión ya que los nodos distantes ahora tienen acceso a múltiples vías (más cortas) para intercambiar información, evitando la “dilución de información” del paso de mensajes local repetido. A diferencia del cableado estático, 𝝼DRew logra este efecto ralentizando la densificación del grafo y haciéndolo dependiente de la capa, reduciendo así la huella de memoria.

𝝼DRew es adecuado para explorar el grafo a diferentes velocidades, manejar interacciones a larga distancia y mejorar en general el poder de las GNN muy profundas. Dado que 𝝼DRew determina dónde y cuándo se intercambian los mensajes, pero no cómo, se puede ver como una meta-arquitectura que puede mejorar los MPNN existentes.

Resultados experimentales

En nuestro artículo [10], proporcionamos una extensa comparación de 𝝼DRew con las líneas de base de MPNN clásicas, el cableado estático y las arquitecturas tipo Transformer, utilizando un presupuesto de parámetros fijo. En el reciente benchmark de largo alcance (LRGB) presentado por Vijay Dwivedi y coautores [11], 𝝼DRew supera en la mayoría de los casos a todos los anteriores.

Un estudio de ablación de 𝝼DRew en una de las tareas LRGB revela otra contribución crucial de nuestro marco de trabajo: la capacidad de ajustar 𝝼 para adaptarse a la tarea. Observamos que cuanto más se use el retraso (menor valor de 𝝼), mejor será el rendimiento para un gran número de capas L, mientras que el uso de menos retraso (alto 𝝼) garantiza un llenado más rápido del grafo computacional y una mayor densidad de conexiones después de menos capas. En consecuencia, en arquitecturas poco profundas (L pequeña), eliminar el retraso por completo (𝝼=∞) funciona mejor. Por el contrario, en arquitecturas profundas (L grande), más retraso (𝝼 pequeña) “ralentiza” la densificación del grafo de paso de mensajes, lo que conduce a un mejor rendimiento.

Las arquitecturas tipo MPNN tradicionales difieren en la forma en que se intercambian los mensajes [12]. Las técnicas de re-cableado de grafos agregan un nivel adicional de control sobre dónde se envían en el grafo. Nuestro nuevo enfoque de re-cableado de grafos dinámico con paso de mensajes retrasado permite controlar aún más cuándo se intercambian los mensajes.

Este enfoque parece ser muy poderoso, y nuestro trabajo es solo un primer intento de aprovechar la idea de acceder a estados pasados en una red neuronal de grafos según las “propiedades geométricas” de los datos subyacentes. Esperamos que este nuevo paradigma pueda llevar a marcos más teóricamente fundamentados y desafiar la idea de que los MPNN no pueden resolver tareas a largo plazo a menos que se les agreguen capas de atención cuadrática.

[1] Esto es típico, por ejemplo, en grafos de “pequeño mundo” como las redes sociales.

[2] U. Alon y E. Yahav, Sobre el cuello de botella de las redes neuronales de grafos y sus implicaciones prácticas (2021), ICLR .

[3] J. Topping et al. , Comprender el exceso de compresión y los cuellos de botella en los grafos a través de la curvatura (2022), ICLR.

[4] El tiempo de desplazamiento es el tiempo esperado que tarda un paseo aleatorio en ir del nodo v al nodo u y regresar. Ver F. Di Giovanni et al. , Sobre el exceso de compresión en las redes neuronales de paso de mensajes: El impacto de la anchura, profundidad y topología (2023), ICML .

[5] Ver Teorema 4.3 en F. Di Giovanni et al. ¿Cómo afecta el exceso de compresión al poder de las GNN? (2023) arXiv :2306.03589.

[6] El re-cableado de grafos es una técnica algo controvertida en la comunidad de GNN, ya que algunos creen que el grafo de entrada es sagrado y no debe alterarse. De facto, la mayoría de las GNN modernas emplean alguna forma de re-cableado de grafos, ya sea explícitamente (como paso de preprocesamiento) o implícitamente (por ejemplo, mediante muestreo de vecinos o el uso de nodos virtuales).

[7] R. Abboud, R. Dimitrov e I. Ceylan, Redes de camino más corto para la predicción de propiedades de grafos (2022),

arXiv :2206.01003.

[8] Ver, por ejemplo, V. P. Dwivedi y X. Bresson, Una generalización de las redes Transformador a los grafos (2021), arXiv :2012.09699 y C. Ying et al., ¿Realmente los Transformadores tienen un mal rendimiento en la representación de grafos? (2021), NeurIPS.

[9] El re-cableado dinámico da como resultado la siguiente fórmula de paso de mensajes:

m ᵤ ⁽ ˡ ᵏ ⁾=AGG({ x ᵥ ⁽ ˡ ⁾ : v∈𝒩ₖ ( u )}) con 1 ≤ k ≤ l +1

x ᵤ ⁽ ˡ ⁺¹⁾=UP( x ᵤ ⁽ ˡ ⁾, m ᵤ ⁽ ˡ ¹⁾,…, m ᵤ ⁽ ˡ ˡ ⁺¹⁾)

donde AGG es un operador de agregación invariante a la permutación, 𝒩ₖ (u) es el vecindario de k saltos del nodo u y UP es una operación de actualización que recibe mensajes de cada k-salto por separado. Véase la ecuación 5 en [10].

[10] B. Gutteridge et al., DRew: Dynamically rewired message passing with delay (2023), ICML.

[11] El paso de mensaje con retraso toma la forma

m ᵤ ⁽ ˡ ᵏ ⁾=AGG({ x ᵥ ⁽ ˡ ᐨ ˢ ⁽ ᵏ ⁾ ⁾ : v∈𝒩ₖ (u)}) con 1 ≤ k ≤ l +1

x ᵤ ⁽ ˡ ⁺¹⁾=UP( x ᵤ ⁽ ˡ ⁾, m ᵤ ⁽ ˡ ¹⁾,…, m ᵤ ⁽ ˡ ˡ ⁺¹⁾)

donde s ( k )=max{0, k ﹣𝝼}, véase la ecuación 6 en [10]. La elección de 𝝼=∞ corresponde a ningún retraso (como en DRew) y 𝝼 = 1 corresponde a MPNN clásico (dos nodos u y v a distancia r interactúan directamente desde la capa r en adelante, pero con un retraso constante de r.

[11] V. P. Dwivedi et al., Long range graph benchmark (2022), arXiv:2206.08164.

[12] En nuestro proto-libro M. M. Bronstein et al., Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges (2021), distinguimos entre tres “sabores” de MPNN: convolucional, atencional y paso de mensajes genérico.

Agradecemos a Federico Barbero, Fabrizio Frasca y Emanuele Rossi por revisar esta publicación y ofrecer comentarios perspicaces. Para obtener artículos adicionales sobre aprendizaje profundo en grafos, consulte las otras publicaciones de Michael en Towards Data Science, suscríbase a sus publicaciones y canal de YouTube, obtenga la membresía de Zepes o sígalo en Twitter.

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