🤖 machine learning

Understanding Truncated Positional Encodings for Graph Neural Networks

Este artigo investiga as implicações teóricas e empíricas do uso de codificações posicionais truncadas em redes neurais de grafos, revelando que tal truncamento altera fundamentalmente o poder expressivo de diferentes famílias de codificação — tornando variantes espectrais não mais fortes que o teste 1-WL — e demonstrando que a combinação de múltiplas codificações truncadas supera o uso de qualquer família individual em conjuntos de dados do mundo real.

Autores originais: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Publicado 2026-06-12

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

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 entender o layout de uma cidade. O robô é uma Rede Neural de Grafos (GNN) e a cidade é um grafo composto por interseções (nós) e ruas (arestas).

Para fazer um bom trabalho, o robô precisa de mais do que apenas uma lista de quais ruas se conectam a quais. Ele precisa de Codificações Posicionais (PEs). Pense nas PEs como um "mapa" ou uma "bússola" que diz ao robô onde cada interseção está em relação a todas as outras. Sem esse mapa, o robô é como uma pessoa andando por uma cidade de olhos fechados, sabendo apenas quem está parado bem ao seu lado, mas sem ter ideia se está perto do centro da cidade ou preso em um beco sem saída.

O Problema: O Mapa "Perfeito" é Pesado Demais

Existem duas formas principais de criar esse mapa perfeito:

O Mapa Espectral: Usa matemática complexa (autovalores e autovetores) para ver as "vibrações" ou a forma global da cidade.
O Mapa de Caminhada (Walk Map): Conta de quantas maneiras você pode caminhar de um ponto a outro em 1 passo, 2 passos, 3 passos e assim por diante.

Matematicamente, se você usar o mapa inteiro (todos os passos, todas as vibrações), esses dois métodos são igualmente poderosos. Eles conseguem distinguir quase quaisquer dois layouts de cidade diferentes.

No entanto, há um porém: Criar esse mapa "completo" para uma cidade grande exige um poder de processamento e memória computacional massivos (especificamente, torna-se exponencialmente mais difícil conforme a cidade cresce). É como tentar carregar uma biblioteca de todos os mapas possíveis do mundo em sua mochila. É pesado demais para ser usado na vida real.

Por isso, engenheiros usam Codificações Posicionais Truncadas. Em vez da biblioteca inteira, eles pegam apenas os primeiros capítulos.

Espectral Truncado: Apenas as primeiras "vibrações" (autovetores).
Caminhada Truncada: Apenas os primeiros passos de caminhada (potências da matriz de adjacência).

A grande questão que o artigo faz é: Se cortarmos o final desses mapas, eles ainda funcionam da mesma forma?

A Grande Descoberta: "Cortar" Muda Tudo

Os autores descobriram uma resposta surpreendente: Não, eles não funcionam da mesma forma mais.

Quando você tem o mapa completo, os métodos Espectral e de Caminhada são gêmeos. Mas quando você os trunca (corta), eles se tornam irmãos muito diferentes, com diferentes forças e fraquezas.

A Armadilha do "Espectral Truncado": Às vezes, usar apenas as primeiras vibrações na verdade torna o robô pior em entender a cidade do que se ele não tivesse mapa nenhum! Em alguns casos, um mapa espectral truncado é tão fraco que nem consegue distinguir dois layouts de cidade que um teste simples de "verificação de vizinhos" (chamado teste 1-WL) consegue identificar facilmente.
A Armadilha da "Caminhada Truncada": Por outro lado, existem layouts de cidade que um mapa de caminhada truncado (contando apenas alguns passos) ignora completamente, mas um mapa espectral truncado detecta imediatamente.

A Analogia: Imagine tentar identificar uma pessoa.

O Mapa Espectral Completo é como conhecer todo o DNA e a história de vida dela.
O Mapa Espectral Truncado é como conhecer apenas a altura dela.
O Mapa de Caminhada Truncado é como saber quantos passos ela dá da sua casa até a mercearia.

Se você souber apenas a altura (Espectral Truncado), pode confundir duas pessoas da mesma altura. Se você souber apenas a distância de caminhada (Caminhada Truncada), pode confundir duas pessoas que moram à mesma distância da mercearia. Mas se você usar ambos, terá uma imagem muito melhor.

O Novo Herói: "Distâncias Harmônicas"

O artigo introduz uma nova família de mapas chamados distâncias k-harmônicas.

Pense na Resistência Efetiva (um tipo de distância 1-harmônica) como medir o quão "conectados" dois pontos estão, como quanta eletricidade flui entre eles.
O artigo mostra que a distância Biharmônica (2-harmônica) mede algo diferente: o quão "central" ou importante uma rua é para toda a cidade.

Os autores provam que, embora esses novos mapas sejam poderosos, eles também têm limites. Se você usar apenas o mapa de "resistência", pode perder detalhes que o mapa "biharmônico" captura, e vice-versa. No entanto, se você usar suficientes desses mapas harmônicos, pode recriar o poder dos mapas completos e pesados.

O Conselho Prático: "Misturar e Combinar"

Como nenhum tipo de mapa truncado é perfeito sozinho, os autores sugerem uma regra de ouro para engenheiros: Não dependa de apenas um tipo de mapa truncado.

Em vez disso, misture-os.

Combine alguns passos do mapa de "Caminhada".
Combine algumas "vibrações" do mapa "Espectral".
Adicione uma ou duas distâncias "Harmônicas".

O Experimento:
Os autores testaram isso em conjuntos de dados do mundo real (como prever propriedades químicas de moléculas).

Usar apenas um tipo de mapa truncado era aceitável.
Usar uma mistura de diferentes mapas truncados foi significativamente melhor.

É como navegar em uma cidade: ter uma bússola (Espectral), um pedômetro (Caminhada) e uma medida de fluxo de tráfego (Harmônica) ao mesmo tempo é muito melhor do que depender de apenas um deles.

Resumo

Mapas completos são pesados demais para o uso no mundo real, por isso usamos versões "truncadas" (cortadas).
O corte quebra a igualdade: Mapas Espectrais Truncados e de Caminhada Truncada não são mais iguais; eles possuem diferentes pontos cegos.
Alguns cortes são piores do que não ter mapa nenhum: Em alguns casos, um mapa espectral truncado é mais fraco do que um teste muito básico.
A Solução: Não escolha apenas um. Misture diferentes tipos de mapas truncados para obter o melhor desempenho sem o alto custo computacional.

Resumo Técnico: Compreendendo Codificações Posicionais Truncadas para Redes Neurais de Grafos

Declaração do Problema

As Redes Neurais de Grafos (GNNs), particularmente as Redes Neurais de Passagem de Mensagens (MPNNs), são fundamentalmente limitadas em sua capacidade de capturar informações estruturais globais, uma restrição formalizada por sua equivalência ao teste 1-Weisfeiler-Lehman (1-WL). Para superar isso, os Transformers de Grafos (GTs) e as GNNs aprimoradas utilizam Codificações Posicionais (PEs) para injetar informações estruturais. Duas famílias dominantes de PEs são as codificações espectrais (derivadas dos autoespaços do Laplaciano) e as codificações baseadas em passeios (derivadas de potências da matriz de adjacência).

Teoricamente, versões completas dessas codificações (usando $\Omega(n)$ autovetores ou potências de matriz) são equivalentes em poder de expressão, situando-se entre os testes 1-WL e 3-WL. No entanto, computar essas codificações completas requer complexidade de tempo e espaço de $O(n^3)$ , o que é proibitivo para aplicações do mundo real. Consequentemente, os praticantes dependem de variantes truncadas (por exemplo, os primeiros $k$ autovetores ou as primeiras $k$ potências da matriz de adjacência). As propriedades teóricas, o poder de expressão e as forças comparativas dessas PEs truncadas permanecem amplamente inexploradas, criando um hiato entre as garantias teóricas e a implementação prática.

Metodologia

Os autores iniciam um estudo sistemático das PEs truncadas através de análise teórica e validação empírica.

Estrutura Teórica

O artigo utiliza a hierarquia WL e suas variantes para caracterizar o poder de expressão de diferentes PEs:

Teste $\psi$ -WL: Uma variante do teste WL onde as cores dos nós são atualizadas usando uma codificação posicional relativa (RPE) $\psi$ .
Teste Sparse- $\psi$ -WL: Uma extensão para MPNNs onde $\psi$ é usado como características de aresta.
Principais Famílias Analisadas:
1. Projeções de Autoespaço Truncadas ( $k$ -EP-WL): Usando as primeiras $k$ projeções do autoespaço do Laplaciano.
2. Codificações de Passeio Truncadas ( $k$ -Walk-WL): Usando as primeiras $k$ potências da matriz de adjacência.
3. Resistência Efetiva (Resistance-WL): Uma distância espectral específica (distância 1-harmônica).
4. Distâncias $k$ -harmônicas: Uma generalização da resistência efetiva definida como $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ .

Os autores constroem pares de grafos específicos (por exemplo, produtos de grafos de caminho e grafos completos, ou ciclos vs. uniões disjuntas de ciclos) para provar separabilidade ou indistinguibilidade sob diferentes PEs truncadas e testes WL.

Avaliação Empírica

Experimentos foram conduzidos em três benchmarks:

BREC: Um conjunto de dados projetado para medir a "expressividade realizada" de GNNs ao testar sua capacidade de distinguir grafos não isomorfos que variam de indistinguíveis por 1-WL a 4-WL.
ZINC-12k: Um benchmark de regressão de grafos para solubilidade molecular, usado para testar a hipótese de que a mistura de PEs truncadas melhora o desempenho.
ogbg-molhiv: Um benchmark de classificação binária para inibição de HIV.

Os autores avaliaram arquiteturas Graphormer-GD e MPNNs (GINE) usando várias combinações de PEs truncadas, incluindo famílias únicas e misturas de codificações espectrais, de passeios e $k$ -harmônicas.

Contribuições Principais e Resultados

1. Divergência de Poder de Expressão em Formas Truncadas

O artigo prova que, embora as codificações espectrais e de passeio completas sejam equivalentes, suas formas truncadas são fundamentalmente diferentes:

Espectral Truncada vs. 1-WL: Os autores mostram que as projeções de autoespaço truncadas ( $k$ -EP-WL) podem ser mais fracas que o teste 1-WL. Especificamente, existem pares de grafos distinguíveis pelo 1-WL, mas indistinguíveis pelo $k$ -EP-WL para $k \in \Omega(n)$ (Teorema 4.1).
Passeio Truncado vs. Espectral: Inversamente, existem pares de grafos distinguíveis por uma única projeção de autoespaço (1-EP-WL), mas indistinguíveis por codificações de passeio de tamanho $\Omega(n)$ (Teorema 4.2).
Implicação: Nenhuma família de PE truncada é estritamente superior; elas capturam aspectos estruturais diferentes e podem ser incomparáveis à hierarquia WL padrão.

2. Limitações da Resistência Efetiva

O artigo analisa a Resistência Efetiva (distância 1-harmônica) e descobre que ela é uma PE mais fraca do que as projeções de autoespaço completas ou codificações de passeio em grafos ponderados.

Teorema 4.3: Existem grafos ponderados indistinguíveis pelo Resistance-WL, mas distinguíveis pelo Adjacency-WL (e, portanto, 1-WL em grafos não ponderados).
Corolário 4.1: O Resistance-WL não codifica todo o espectro do grafo, refutando uma conjectura anterior.

3. Distâncias $k$ -harmônicas como uma Ponte

Os autores introduzem as distâncias $k$ -harmônicas como uma ponte natural entre as codificações espectrais e polinomiais.

Completude: A concatenação de $\Theta(n)$ distâncias $k$ -harmônicas produz uma codificação equivalente em poder às codificações espectrais ou de passeio completas (Teorema 4.6).
Poder Diferencial: Mesmo dentro da família $k-harmônica$, codificações de tamanho fixo diferem. Por exemplo, a distância bi-harmônica (2-harmônica) pode distinguir certos pares de árvores em um número constante de iterações, enquanto a resistência efetiva (1-harmônica) requer $O(n)$ iterações (Teorema 4.7).
Robustez: No entanto, se uma distância $k$ -harmônica distingue um par de grafos, a maioria das outras distâncias $k$ -harmônicas também os distinguirá (Teorema 4.8).

4. Achados Empíricos: O Poder da Mistura

Resultados BREC: As distâncias $k$ -harmônicas alcançaram resultados competitivos com codificações de canal único e baixo custo, muitas vezes igualando o teto teórico para grafos entre 1-WL e 3-WL.
Resultados ZINC: O achado mais significativo é que misturar PEs de diferentes famílias (por exemplo, combinando passeios truncados e $k$ -harmônicos) supera qualquer família individual. Uma mistura de passeios truncados e $k$ -harmônicos alcançou o menor Erro Absoluto Médio (MAE) no ZINC-12k, superando as linhas de base de família única.
Eficiência: O artigo observa que as distâncias $k$ -harmônicas podem ser aproximadas em $O(mk \cdot \text{poly}(\log n))$ de tempo usando solucionadores de Laplaciano rápidos e projeções de Johnson-Lindenstrauss, evitando o custo de $O(n^3)$ da computação exata.

Significância e Alegações

O artigo afirma iniciar o estudo teórico das codificações posicionais truncadas, mudando a perspectiva de vê-las meramente como aproximações de codificações completas para vê-las como um espaço de design distinto com propriedades de expressão únicas.

Insight Teórico: O trabalho demonstra que a truncagem altera fundamentalmente a informação capturada pelas PEs, tornando-as incomparáveis à hierarquia WL padrão em casos específicos.
Orientação Prática: Os autores propõem uma regra prática: misture PEs de diferentes famílias ao usar codificações truncadas. Esta abordagem captura pistas estruturais complementares enquanto controla os custos computacionais.
Escopo Modesto: Os autores reconhecem que, embora o isomorfismo de grafos seja um proxy principiológico, tarefas do mundo real envolvem sinais de jusante (centralidade, motivos) que podem não se alinhar estritamente com o teste de isomorfismo. Assim, a principal contribuição é estabelecer uma base teórica e um ponto de partida para um estudo empírico sistemático, em vez de reivindicar uma solução universal para todas as tarefas de aprendizado de grafos.