Resumo Técnico: Weisfeiler–Leman é Incompleto em Grafos de Espectro Simples, portanto Canonicalize-os

Declaração do Problema

Redes Neurais em Grafos (GNNs) são amplamente utilizadas para aprendizado em dados estruturados em grafos, contudo, seu poder expressivo é frequentemente limitado pela hierarquia de Weisfeiler–Leman (WL). É um resultado conhecido que o teste WL de dimensão $k$ ($k$-WL) não consegue distinguir todos os grafos não isomórficos. No entanto, uma classe específica de grafos — aqueles com um espectro simples (onde a matriz de adjacência possui autovalores distintos) — admite teste de isomorfismo em tempo cúbico. Apesar dessa tratabilidade teórica, permanecia uma questão em aberto se a hierarquia WL, que limita superiormente a expressividade de muitas GNNs, poderia distinguir todos os grafos de espectro simples.

Além disso, embora codificações posicionais espectrais (por exemplo, autovetores do Laplaciano) sejam comumente integradas a GNNs para aprimorar a expressividade, elas sofrem de ambiguidades inerentes: ambiguidade de sinal para espectros simples e ambiguidade de base para autovalores repetidos. Métodos existentes para resolver essas ambiguidades (como SignNet, MAP e OAP) são comprovadamente incompletos em grafos de espectro simples, falhando em distinguir certos pares não isomórficos. Essa incompletude limita a capacidade de GNNs espectrais de alcançar aproximação universal nesta classe de grafos.

Metodologia

1. Prova da Incompletude do WL em Espectros Simples

Os autores estabelecem primeiro que toda a hierarquia WL é incompleta em grafos de espectro simples.

• Construção: Eles utilizam a construção de Cai–Fürer–Immerman (CFI), que gera pares de grafos não isomórficos indistinguíveis pelo $k$-WL.
• Codificação: Como os grafos CFI padrão não possuem um espectro simples, os autores introduzem um novo mecanismo de codificação integral. Eles mapeiam os padrões de adjacência CFI em uma matriz ortogonal $\tilde{X}$ composta por entradas inteiras.
• Formação de Multigrafos: Usando essa matriz ortogonal e uma matriz diagonal de autovalores inteiros distintos, eles constroem um par de multigrafos simétricos ($A_{G,0}$ e $A_{G,1}$) com espectros simples.
• Resultado: Eles provam que esses multigrafos de espectro simples construídos permanecem indistinguíveis pelo teste $k$-WL, demonstrando que nenhum nível da hierarquia WL pode resolver o problema de isomorfismo para esta classe, apesar do problema ser solúvel em tempo cúbico.

2. PRiSM: Uma Canonicalização Completa

Para abordar as limitações dos métodos espectrais existentes, os autores propõem o PRiSM (Partition, Refine, Solve, Match — Particionar, Refinar, Resolver, Correspondência), um procedimento de canonicalização comprovadamente completo para decomposições espectrais de grafos de espectro simples.

• Entrada: Uma matriz ortonormal por colunas $U$ de autovetores.
• Grupo de Ambiguidade: O procedimento lida com o grupo de ambiguidade $S_n \times \{-1, 1\}^k$ (permutações e inversões de sinal).
• Quatro Estágios:
  1. Particionar: Os vértices são agrupados com base em suas assinaturas invariantes de sinal (valores absolutos das entradas dos autovetores).
  2. Refinar: Uma variante espectral do procedimento de refinamento de cores WL é aplicada à partição. Isso refina iterativamente as classes de vértices usando o multiconjunto de características de arestas definidas por produtos elemento a elemento das entradas dos autovetores ($U_v \odot U_u$) até que a partição se estabilize.
  3. Resolver: A partição estável define um sistema de equações lineares sobre o corpo $\mathbb{Z}_2$. O sistema impõe que cada classe de partição contenha pelo menos uma linha com entradas não negativas. Resolver esse sistema determina os sinais canônicos únicos para os autovetores (até automorfismos do grafo).
  4. Correspondência: Uma vez fixados os sinais, as linhas são ordenadas lexicograficamente para resolver a ambiguidade de permutação, produzindo uma matriz canônica única.
• Extensão: Para grafos com autovalores repetidos (espectro não simples), o PRiSM é estendido heuristicamente. Ele aplica o procedimento base ao bloco de espectro simples ($m=1$) e utiliza decomposição QR e seleção de pivô para resolver espaços próprios de ordem superior ($m > 1$).

3. Garantias Teóricas

• Completude: O PRiSM é provado ser uma canonicalização válida, significando que produz a mesma saída para grafos isomórficos e saídas diferentes para grafos de espectro simples não isomórficos.
• Aproximação Universal: Ao compor o PRiSM com uma rede de conjuntos universal (por exemplo, DeepSets ou Transformers), o modelo resultante alcança aproximação universal para qualquer função invariante a isomorfismo em grafos de espectro simples. Isso resolve o problema em aberto de alcançar completude para GNNs espectrais nesta classe.

Resultados Chave

Achados Teóricos

• Teorema 1: Para todo número natural $k$, existem multigrafos de espectro simples não isomórficos com $\Theta(k)$ nós que não são distinguidos pelo algoritmo $k$-WL. Isso implica que todas as famílias de GNNs alinhadas ao $k$-WL (incluindo PPGN, $k$-GNNs e Transformers de Grafos) são incompletas em grafos de espectro simples.
• Teorema 2: O PRiSM fornece uma canonicalização válida para decomposições espectrais de espectro simples.
• Teorema 3: Modelos compostos por PRiSM e redes de conjuntos universais alcançam aproximação universal em grafos de espectro simples.

Desempenho Empírico

Os autores avaliaram o PRiSM em três benchmarks:

1. Benchmark de Expressividade BREC: O PRiSM superou canonicalizações concorrentes (MAP, OAP) na distinção de pares de grafos não isomórficos, particularmente nas categorias Regular e Extension. Ele distinguiu corretamente 212/360 pares, comparado a 199/360 para MAP/OAP.
2. Predição de Propriedades Moleculares (ZINC, OGB-Mol): O PRiSM alcançou desempenho state-of-the-art ou empatado com o melhor na regressão molecular (ZINC) e tarefas de classificação (MOLTOX21, MOLPCBA) usando tanto backbones GatedGCN quanto PNA.
3. Backbones de Transformer (OGB, Alchemy): Quando usado como codificação posicional para Transformers de Grafos, o PRiSM superou todas as linhas de base (LPE, MAP, OAP) em todos os quatro conjuntos de dados (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). Os autores atribuem isso ao PRiSM fornecer uma ordenação determinística de vértices além de autovetores com sinal corrigido, o que é crucial para mecanismos de atenção de Transformer.

Significado e Alegações

O artigo afirma resolver uma lacuna fundamental na compreensão teórica da expressividade de GNNs e métodos espectrais:

1. Incompletude do WL: Prova definitivamente que a hierarquia WL, apesar de seu poder crescente, não consegue distinguir todos os grafos de espectro simples, uma classe onde o isomorfismo é teoricamente fácil.
2. Primeira Canonicalização Completa: O PRiSM é apresentado como a primeira canonicalização de sinal comprovadamente completa para decomposições espectrais de espectro simples, superando as limitações de métodos anteriores como MAP e OAP, que são incompletos nesta classe.
3. Aproximação Universal: O trabalho estabelece que GNNs espectrais podem alcançar aproximação universal em grafos de espectro simples se emparelhadas com uma canonicalização completa como o PRiSM, justificando o uso de codificações posicionais Laplacianas canonicalizadas.
4. Utilidade Prática: Empiricamente, o método demonstra que resolver ambiguidades espectrais completamente leva a melhorias tangíveis em tarefas subsequentes, superando abordagens existentes invariantes a sinal e de canonicalização.

Os autores notam limitações, especificamente que a garantia de completude aplica-se estritamente a grafos de espectro simples (ou multigrafos construídos na prova) e que o procedimento de canonicalização é descontínuo, uma propriedade que eles argumentam ser matematicamente inevitável para canonicalizações de sinal completas. Eles também deixam a extensão da prova de incompletude para grafos combinatórios simples (sem arestas múltiplas) como trabalho futuro.