🤖 machine learning

A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs

Este artículo demuestra que una amplia clase de Modelos Fundacionales de Grafos con atención global para Programas Lineales de Enteros Mixtos está fundamentalmente limitada al poder expresivo de la prueba de Weisfeiler-Leman de 1 dimensión, lo que significa que no pueden distinguir entre instancias no isomórficas equivalentes a 1-WL independientemente de su complejidad arquitectónica o configuración de parámetros.

Autores originales: Md Abrar Jahin, Craig A. Knoblock, Jay Pujara

Publicado 2026-07-21

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Md Abrar Jahin, Craig A. Knoblock, Jay Pujara

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando enseñarle a un robot a resolver un rompecabezas gigante y complejo. Este no es un rompecabezas con imágenes; es un "Programa Lineal de Enteros Mixtos" (MILP, por sus siglas en inglés), un tipo de problema matemático utilizado para determinar la mejor manera de programar vuelos, cortar acero o gestionar redes eléctricas. Para ayudar al robot, convertimos este rompecabezas en un mapa de puntos y líneas llamado "grafo". Los puntos son las piezas del rompecabezas (como variables y reglas) y las líneas muestran cómo se conectan.

Durante mucho tiempo, los mejores robots para este trabajo fueron como grupos de vigilancia vecinal. Solo podían observar a sus vecinos inmediatos para entender el mundo. Si dos puntos tenían los mismos vecinos, el robot pensaba que eran gemelos idénticos, incluso si el resto del rompecabezas era totalmente diferente. Esta limitación se conoce como la "prueba 1-WL" (un nombre elegante para un juego de emparejamiento de colores). Recientemente, llegó una nueva generación de robots llamados "Transformers de Grafos". Estos son gigantes con supervisión que pueden ver cada uno de los puntos en todo el rompecabezas a la vez, no solo a los vecinos. Todos esperaban que esta "visión global" les permitiera detectar las diferencias que los viejos robots pasaban por alto, resolviendo problemas que antes eran imposibles. Pero, ¿el hecho de verlo todo realmente los hace más inteligentes, o solo están mirando los mismos patrones de siempre?

Este artículo pone a prueba a estos robots con supervisión. Los autores, Md Abrar Jahin, Craig A. Knoblock y Jay Pujara, querían saber si estos nuevos modelos de "Atención Global" realmente pueden distinguir entre dos rompecabezas que parecen idénticos para los viejos robots de vigilancia vecinal. Construyeron una prueba matemática y realizaron una serie de experimentos con diez tipos diferentes de estos potentes modelos.

Aquí está el sorprendente giro que encontraron: No, la supervisión no ayuda.

Aunque estos nuevos modelos pueden mirar todo el grafo a la vez, el artículo demuestra matemáticamente que siguen atrapados en la misma caja que los viejos robots de vigilancia vecinal. Si dos rompecabezas matemáticos son "equivalentes a 1-WL" (es decir, pasan la prueba de emparejamiento de colores y parecen iguales para los viejos robots), estos nuevos y elegantes modelos les darán la misma huella digital electrónica. No importa qué tan grande sea el modelo, cuántos datos haya sido entrenado o cuántos parámetros tenga. Si los rompecabezas son estructuralmente similares de una manera específica, el modelo los trata como gemelos idénticos.

Para demostrar esto, los investigadores no solo conjeturaron; construyeron pares específicos de rompecabezas que son matemáticamente diferentes pero que parecen iguales ante la prueba de emparejamiento de colores. Alimentaron estos pares en diez modelos diferentes, incluyendo diseños populares como Graphormer y GraphGPS. El resultado fue un empate perfecto: cada uno de los modelos produjo respuestas bit a bit idénticas para los diferentes rompecabezas. Es como tener dos casas que se ven exactamente iguales desde la calle; incluso si tienes un dron que puede ver todo el vecindario, si las casas están pintadas del mismo color y tienen el mismo número de ventanas, el informe del dron dirá que son la misma casa.

El artículo también descubrió por qué sucede esto. El mecanismo de "atención global" —la parte que le permite al robot verlo todo— es en realidad una forma elegante de contar y promediar. Es una "función de multiconjunto simétrico", que es una forma elegante de decir que solo le importa la colección de vecinos, no su orden específico o disposición única. Debido a esto, el robot pierde la capacidad de distinguir entre ciertas estructuras complejas, sin importar cuánto lo intente.

Sin embargo, hay un rayo de esperanza. Los autores descubrieron que el problema no son los ojos del robot; es el mapa que está mirando. Si le das al robot un "codificación posicional" especial —una especie de sistema de coordenadas GPS que le dice a cada punto dónde está en un paseo aleatorio a través del rompecabezas—, los modelos de repente son capaces de distinguir la diferencia. Sin estas pistas adicionales, los modelos son ciegos a ciertas diferencias estructurales. Pero con ellas, los modelos finalmente pueden ver las características únicas del rompecabezas.

En resumen, el artículo muestra que simplemente hacer los modelos de grafos más grandes y darles "atención global" no los hace automáticamente más inteligentes. Siguen limitados por las reglas básicas de cómo cuentan y agrupan la información. Para resolver los rompecabezas matemáticos más difíciles, no solo necesitamos ojos más grandes; necesitamos darles a los modelos mejores mapas para mirar en primer lugar.

Resumen Técnico: Una caracterización mediante Weisfeiler–Leman de los Transformadores de Grafos con Atención Global para Programas Lineales Enteros Mixtos

Planteamiento del Problema
Los modelos fundacionales de grafos (GFM) equipados con mecanismos de atención global se emplean cada vez más para aprender representaciones de Programas Lineales Enteros Mixtos (MILP). Estos modelos pretenden capturar información estructural más allá de las restricciones de localidad de las Redes Neuronales de Grafos (GNN) estándar de paso de mensajes. Sin embargo, el poder expresivo teórico de estas arquitecturas jerárquicas —específicamente, si la atención global permite distinguir estructuras de grafos que las GNN estándar no pueden distinguir— sigue sin resolverse. Este artículo aborda si los transformadores de grafos de atención global para grafos de MILP bipartitos exceden el poder de distinción de la prueba de refinamiento de colores de unidimensional Weisfeiler–Leman (1-WL).

Metodología
Los autores emplean un análisis teórico composicional combinado con una extensa validación empírica.

Marco Teórico: El estudio formaliza una clase amplia de codificadores de grafos jerárquicos utilizados en los modelos fundacionales de MILP. Estos codificadores constan de seis etapas: (i) proyecciones de entrada por tipo, (ii) autoatención lineal normalizada estilo SGFormer, (iii) atención cruzada ponderada por aristas entre tipos de nodos, (iv) una rama paralela de paso de mensajes bipartito (estilo Gasse), (v) fusión convexa por nodo y (vi) agrupación (pooling) invariante a la permutación. Los autores definen un operador como "limitado por 1-WL" si preserva la equivalencia 1-WL: si dos conjuntos de nodos de entrada coinciden como multiconjuntos de colores, los conjuntos de salida también deben coincidir como multiconjuntos bajo la misma biyección. Demuestran que cada componente arquitectónico (autoatención, atención cruzada, paso de mensajes, fusión y agrupación) funciona como una función de multiconjunto simétrica, preservando así la equivalencia 1-WL.
Construcción Empírica: Para probar esta teoría, los autores construyen una familia parametrizada de grafos de MILP no isomorfos pero 1-WL-equivalentes. Estos pares incluyen:
- Familia de Ciclos: Un único grafo circulante bipartito $d$ -regular conectado ( $G_A$ ) frente a $k$ copias disjuntas de un grafo bipartito completo ( $G_B$ ).
- Familia Cúbica: Variantes con diferente regularidad y girth para controlar artefactos específicos de ciclos.
- Validación: La no isomorfía se verifica mediante comprobaciones exactas de isomorfismo de subgrafos y conteo de componentes conectados (una propiedad invisible para 1-WL). La factibilidad se confirma mediante solvers exactos.
Configuración Experimental: Se evaluaron diez codificadores arquitectónicamente diversos, incluyendo variantes de SGFormer+GCN, Graphormer-style, GraphGPS-style, Set-Transformer y GCNs bipartitos estilo Gasse, tanto pre-entrenados como con inicialización aleatoria. Los experimentos variaron la capacidad del modelo (parámetros de $10^3$ a $2.5 \times 10^6$ ), la escala del grafo (hasta 800 nodos), los operadores de agrupación y la precisión numérica.

Contribuciones Clave

Caracterización Teórica: El artículo establece que una clase amplia de transformadores de grafos de atención global jerárquicos para MILP está estrictamente limitada por la prueba 1-WL. Independientemente de la configuración de parámetros, estas arquitecturas asignan embeddings idénticos a cualquier par de grafos de MILP que sean 1-WL-equivalentes. Este resultado se deriva del hecho de que todas las operaciones constitutivas (incluyendo la atención lineal global y la atención cruzada) son agregaciones de multiconjuntos simétricos.
Validación Empírica: A través de diez codificadores diversos y diversas capacidades, los autores demuestran que los pares de grafos no isomorfos 1-WL-equivalentes mapean a embeddings numéricamente idénticos (idénticos en bits dentro de la precisión de punto flotante). La tasa de coincidencia exacta es de 1.00 en todas las configuraciones probadas.
Consecuencias Downstream: El estudio muestra que los invariantes de grafos que varían dentro de una clase de equivalencia 1-WL (por ejemplo, el número de componentes conectados, conteos de ciclos, brechas espectrales) no son recuperables de las representaciones base. Los experimentos de sondeo revelan que el rendimiento de la predicción para estos objetivos cae a niveles cercanos al azar en poblaciones 1-WL-equivalentes, mientras que el rendimiento se recupera cuando se introducen codificaciones posicionales estructurales.
Localización de la Expresividad: Los autores identifican que la fuente de la expresividad más allá de 1-WL reside en la codificación de entrada y no en el mecanismo de atención. Mientras que los codificadores base fallan en distinguir los pares construidos, el aumento de las entradas con Codificaciones Posicionales de Caminata Aleatoria (RWPE) o Codificaciones Posicionales de Laplaciano (LapPE) separa exitosamente las representaciones. Sin embargo, el artículo también señala que la longitud finita de RWPE tiene límites, ya que ciertos pares 1-WL-equivalentes siguen siendo indistinguibles incluso con estas codificaciones.
Herramienta de Diagnóstico: Se introduce un diagnóstico agnóstico al codificador para detectar la equivalencia de representación inducida por 1-WL en los embeddings de grafos.

Resultos

Equivalencia de Representación: Todos los codificadores probados produjeron embeddings para pares 1-WL-equivalentes con una similitud de coseno media de 1.000000 y una diferencia máxima de coordenadas de menos de $6.0 \times 10^{-8}$ (float32).
Invariancia a la Escala: El aumento del tamaño del modelo de $\approx 10^4$ a $2.5 \times 10^6$ parámetros y el escalado del tamaño del grafo a 800 nodos no alteró la equivalencia.
Fallo de Sondeo: Los sondos lineales y MLP entrenados en los embeddings base fallaron en predecir el número de componentes conectados ( $R^2 \approx -0.01$ ) para instancias 1-WL-equivalentes, a pesar de la alta varianza en el objetivo.
Éxito de la Codificación Posicional: La introducción de RWPE permitió que los sondos recuperaran estos invariantes ( $R^2 \approx 0.51$ ) y permitió a los clasificadores downstream distinguir los pares con una precisión casi perfecta (0.97–1.00), excepto en las ablaciones de solo GCN que tuvieron dificultades para propagar las señales posicionales.

Significancia
El artículo sostiene que el poder expresivo de los modelos fundacionales de grafos actuales con atención global para MILP está fundamentalmente limitado por la prueba 1-WL cuando dependen únicamente de la representación estándar de grafo bipartito. La incapacidad de distinguir instancias 1-WL-equivalentes implica que las tareas posteriores que dependen de propiedades estructurales invisibles para 1-WL (como diferencias de factibilidad o conectividad) no pueden ser resueltas correctamente por estos modelos por sí solos, independientemente de los datos de entrenamiento o la capacidad del modelo. Los autores concluyen que las mejoras en el rendimiento atribuidas a los transformadores de grafos deben entenderse en el contexto de la representación de entrada; específicamente, la inclusión de codificaciones posicionales estructurales es el principal motor de la expresividad más allá de 1-WL en estos sistemas, más que el mecanismo de atención en sí mismo. Esto proporciona una base teórica y empírica para diagnosticar el colapso de la representación en modelos de optimización basados en grafos.

Más como este