🤖 machine learning

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

Este artigo demonstra que uma ampla classe de Modelos de Fundação de Grafos de atenção global para Programas Lineares de Inteiros Mistos é fundamentalmente limitada ao poder expressivo do teste de Weisfeiler-Leman 1-dimensional, o que significa que eles não podem distinguir entre instâncias não isomórficas 1-WL-equivalentes, independentemente de sua complexidade arquitetônica ou configurações de parâmetros.

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

Publicado 2026-07-21

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

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

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando ensinar um robô a resolver um quebra-cabeça gigante e complexo. Este não é um quebra-cabeça de imagens; é um "Programa Linear de Variáveis Inteiras Mistas" (MILP, na sigla em inglês), um tipo de problema matemático usado para determinar a melhor maneira de agendar voos, cortar aço ou gerenciar redes elétricas. Para ajudar o robô, transformamos o quebra-cabeça em um mapa de pontos e linhas chamado "grafo". Os pontos são as peças do quebra-cabeça (como variáveis e regras) e as linhas mostem como elas se conectam.

Por muito tempo, os melhores robôs para este trabalho foram como grupos de vigilância de bairro. Eles podiam apenas olhar para seus vizinhos imediatos para entender o mundo. Se dois pontos tivessem os mesmos vizinhos, o robô pensava que eles eram gêmeos idênticos, mesmo que o resto do quebra-cabeça fosse totalmente diferente. Essa limitação é conhecida como o "teste 1-WL" (um nome chique para um jogo de combinar cores). Recentemente, uma nova geração de robôs chamados "Transformers de Grafos" chegou. Estes são gigantes de visão superaguçada que podem ver cada ponto em todo o quebra-culo de uma só vez, não apenas os vizinhos. Todos esperavam que essa "visão global" permitisse que eles percebessem as diferenças que os antigos robôs perderam, resolvendo problemas que antes eram impossíveis. Mas será que ver tudo realmente os torna mais espertos, ou eles estão apenas olhando para os mesmos padrões de sempre?

Este artigo coloca esses robôs de visão superaguçada à prova. Os autores, Md Abrar Jahin, Craig A. Knoblock e Jay Pujara, queriam saber se esses novos modelos de "Atenção Global" conseguem realmente distinguir dois quebra-cabeças que parecem idênticos para os antigos robôs de vigilância de bairro. Eles construíram uma prova matemática e realizaram uma série de experimentos com dez tipos diferentes desses modelos poderosos.

Aqui está a reviravolta surpreendente que encontraram: Não, a supervisão não ajuda.

Embora esses novos modelos possam olhar para o grafo inteiro de uma só vez, o artigo prova matematicamente que eles ainda estão presos na mesma caixa que os antigos robôs de vigilância de bairro. Se dois quebra-cabeças matemáticos são "equivalentes a 1-WL" (o que significa que passam no teste de combinação de cores e parecem iguais para os antigos robôs), esses novos e sofisticados modelos darão a eles a mesma impressão digital digital. Não importa o quão grande seja o modelo, quanto dado ele tenha sido treinado ou quantos parâmetros ele possua. Se os quebra-cabeças forem estruturalmente semelhantes de uma forma específica, o modelo os tratará como gêmeos idênticos.

Para provar isso, os pesquisadores não apenas adivinharam; eles construíram pares específicos de quebra-cabeças que são matematicamente diferentes, mas que parecem iguais ao teste de combinação de cores. Eles alimentaram esses pares em dez modelos diferentes, incluindo designs populares como Graphormer e GraphGPS. O resultado foi um empate perfeito: todos os modelos produziram respostas bit a bit idênticas para os diferentes quebra-cabeças. É como ter duas casas que parecem exatamente iguais pela rua; mesmo que você tenha um drone que possa ver todo o bairro, se as casas forem pintadas da mesma cor e tiverem o mesmo número de janelas, o relatório do drone dirá que são a mesma casa.

O artigo também descobriu por que isso acontece. O mecanismo de "atenção global" — a parte que permite ao robô ver tudo — é, na verdade, uma forma chique de contar e tirar a média. É uma "função de multiconjunto simétrica", que é uma maneira sofisticada de dizer que ela só se importa com a coleção de vizinhos, não com sua ordem específica ou arranjo único. Por causa disso, o robô perde a capacidade de distinguir certas estruturas complexas, não importa o quanto tente.

No entanto, há um lado positivo. Os autores descobriram que o problema não são os olhos do robô; é o mapa que eles estão olhando. Se você der ao robô um "codificação posicional" especial — um tipo de sistema de coordenadas GPS que diz a cada ponto onde ele está em uma caminhada aleatória pelo quebra-cabeça — os modelos subitamente tornam-se capazes de distinguir a diferença. Sem essas pistas extras, os modelos são cegos a certas diferenças estruturais. Mas com elas, os modelos finalmente conseguem ver as características únicas do quebra-cabeça.

Em resumo, o artigo mostra que simplesmente tornar os modelos de grafos maiores e dar-lhes "atenção global" não os torna automaticamente mais espertos. Eles ainda estão limitados pelas regras básicas de como contam e agrupam informações. Para resolver os quebra-cabeças matemáticos mais difíceis, não precisamos apenas de olhos maiores; precisamos dar aos modelos mapas melhores para olharem em primeiro lugar.

Resumo Técnico: Uma Caracterização de Weisfeiler–Leman para Transformers de Grafos com Atenção Global para Programas Lineares de Inteiros Mistos

Enunciado do Problema
Modelos de fundação de grafos (GFMs) equipados com mecanismos de atenção global são cada vez mais empregados para aprender representações de Programas Lineares de Inteiros Mistos (MILPs). Esses modelos visam capturar informações estruturais que vão além das restrições de localidade das Redes Neurais de Grafos (GNNs) padrão de passagem de mensagens. No entanto, o poder expressivo teórico dessas arquiteturas hierárquicas — especificamente se a atenção global permite que elas distingam estruturas de grafos que as GNNs padrão não conseguem — permanece não resolvido. Este artigo aborda se os transformers de grafos com atenção global para grafos bipartidos de MILP excedem o poder de distinção do teste de refinamento de cores Weisfeiler–Leman unidimensional (1-WL).

Metodologia
Os autores empregam uma análise teórica composicional combinada com uma extensa validação empírica.

Estrutura Teórica: O estudo formaliza uma ampla classe de codificadores de grafos hierárquicos usados em modelos de fundação de MILP. Esses codificadores consistem em seis estágios: (i) projeções de entrada por tipo, (ii) autoatenção linear normalizada estilo SGFormer, (iii) atenção cruzada ponderada por arestas entre tipos de nós, (iv) um ramo paralelo de passagem de mensagem bipartida (estilo Gasse), (v) fusão convexa por nó e (vi) pooling invariante à permutação. Os autores definem um operador como "limitado por 1-WL" se ele preserva a equivalência 1-WL: se dois conjuntos de nós de entrada concordam como multiconjuntos de cores, os conjuntos de saída também devem concordar como multiconjuntos sob a mesma bijeção. Eles provam que cada componente arquitetônico (autoatenção, atenção cruzada, passagem de mensagem, fusão e pooling) funciona como uma função de multiconjunto simétrica, preservando assim a equivalência 1-WL.
Construção Empírica: Para testar essa teoria, os autores constroem uma família parametrizada de grafos de MILP 1-WL-equivalentes, mas não isomorfos. Esses pares incluem:
- Família de Ciclos: Um único grafo circulante bipartido $d$ -regular ( $G_A$ ) versus $k$ cópias disjuntas de um grafo bipartido completo ( $G_B$ ).
- Família Cúbica: Variantes com diferentes regularidades e girth para controlar artefatos específicos de ciclos.
- Validação: A não-isomorfia é verificada via verificações exatas de isomorfismo de subgrafos e contagem de componentes conectados (uma propriedade invisível ao 1-WL). A viabilidade é confirmada usando solvers exatos.
Configuração Experimental: Dez codificadores arquiteturalmente diversos foram avaliados, incluindo variantes SGFormer+GCN pré-treinadas e inicializadas aleatoriamente, estilos Graphormer, GraphGPS, Set-Transformer e GCNs bipartidas estilo Gasse. Os experimentos variaram a capacidade do modelo (parâmetros de $10^3$ a $2,5 \times 10^6$ ), escala do grafo (até 800 nós), operadores de pooling e precisão numérica.

Principais Contribuições

Caracterização Teórica: O artigo estabelece que uma ampla classe de transformers de grafos com atenção global hierárquica para MILPs é estritamente limitada pelo teste 1-WL. Independentemente das configurações de parâmetros, essas arquiteturas atribuem embeddings idênticos a qualquer par de grafos de MILP que sejam 1-WL equivalentes. Este resultado decorre do fato de que todas as operações constituintes (incluindo atenção linear global e atenção cruzada) são agregações de multiconjuntos simétricos.
Validação Empírica: Através de dez codificadores diversos e variando capacidades, os autores demonstram que pares de grafos não isomorfos, porém 1-WL-equivalentes, mapeiam para embeddings numericamente idênticos (bit-idênticos dentro da precisão de ponto flutuante). A taxa de correspondência exata é de 1,00 em todas as configurações testadas.
Consequências Downstream: O estudo mostra que invariantes de grafos que variam dentro de uma classe de equivalência 1-WL (por exemplo, o número de componentes conectados, contagens de ciclos, gaps espectrais) não são recuperáveis das representações de base. Experimentos de sondagem (probing) revelam que o desempenho de predição para esses alvos cai para níveis próximos ao acaso em populações 1-WL-equivalentes, enquanto o desempenho se recupera quando codificações posicionais estruturais são introduzidas.
Localização da Expressividade: Os autores identificam que a fonte de expressividade além do 1-WL reside na codificação de entrada, e não no mecanismo de atenção. Enquanto os codificadores de base falham em distinguir os pares construídos, aumentar as entradas com Codificações Posicionais de Caminhada Aleatória (RWPE) ou Codificações Posicionais de Laplaciano (LapPE) separa com sucesso as representações. No entanto, o artigo também observa que a RWPE de comprimento finito tem limites, pois certos pares 1-WL-equivalentes permanecem indistinguíveis mesmo com essas codificações.
Ferramenta de Diagnóstico: Um diagnóstico agnóstico ao codificador é introduzido para detectar a equivalência de representação induzida por 1-WL em embeddings de grafos.

Resultos

Equivalência de Representação: Todos os codificadores testados produziram embeddings para pares 1-WL-equivalentes com uma similaridade de cosseno média de 1,000000 e uma diferença máxima de coordenadas inferior a $6,0 \times 10^{-8}$ (float32).
Invariância de Escala: Aumentar o tamanho do modelo de $\approx 10^4$ para $2,5 \times 10^6$ parâmetros e escalar o tamanho do grafo para 800 nós não alterou a equivalência.
Falha de Sondagem: Sondas lineares e MLP treinadas em embeddings de base falharam em prever o número de componentes conectados ( $R^2 \approx -0,01$ ) para instâncias 1-WL-equivalentes, apesar da alta variância no alvo.
Sucesso da Codificação Posicional: A introdução de RWPE permitiu que as sondagens recuperassem esses invariantes ( $R^2 \approx 0,51$ ) e permitiu que classificadores downstream distinguissem os pares com precisão quase perfeita (0,97–1,00), exceto para ablações apenas de GCN que tiveram dificuldade em propagar sinais posicionais.

Significância
O artigo afirma que o poder expressivo dos atuais modelos de fundação de grafos com atenção global para MILPs é fundamentalmente limitado pelo teste 1-WL quando dependem apenas da representação de grafo bipartido padrão. A incapacidade de distinguir instâncias 1-WL-equivalentes implica que tarefas downstream que dependem de propriedades estruturais invisíveis ao 1-WL (como diferenças de viabilidade ou conectividade) não podem ser resolvidas corretamente por esses modelos sozinhos, independentemente de dados de treinamento ou capacidade do modelo. Os autores concluem que as melhorias de desempenho atribuídas a transformers de grafos devem ser entendidas no contexto da representação de entrada; especificamente, a inclusão de codificações posicionais estruturais é o principal motor de expressividade além do 1-WL nesses sistemas, e não o mecanismo de atenção em si. Isso fornece uma base teórica e empírica para diagnosticar o colapso de representação em modelos de otimização baseados em grafos.

Mais como este