LEAP: Local ECT-Based Learnable Positional Encodings for Graphs

Este trabalho apresenta o LEAP, um novo método de codificação posicional aprendível e baseado em estrutura local para grafos, que combina a Transformada de Característica de Euler Diferenciável (DECT) e sua variante local ($\ell$-ECT) para superar as limitações dos modelos de redes neurais em grafos e melhorar a representação de características topológicas.

O essencial

Imagine que você está tentando ensinar um computador a entender a diferença entre um mapa de metrô, uma teia de aranha e uma rede social de amigos. O desafio é que, para o computador, todos esses são apenas "pontos conectados por linhas" (grafos).

O problema é que os computadores atuais, chamados de Redes Neurais de Grafos (GNNs), são como pessoas que só conseguem ver o vizinho imediato. Elas trocam mensagens com quem está ao lado, mas têm dificuldade em entender a "forma" geral da rede ou a distância entre pontos distantes. É como tentar entender a estrutura de uma cidade apenas conversando com quem mora na sua rua, sem nunca ver o mapa inteiro.

Aqui entra o LEAP, o novo método apresentado neste artigo. Vamos explicar como ele funciona usando analogias do dia a dia:

1. O Problema: O "Mapa Cego"

Os métodos antigos tentam dar ao computador uma "posição" para cada ponto (nó) no gráfico. Alguns usam coordenadas (como latitude e longitude), outros usam a distância até o centro. Mas isso é limitado. É como tentar descrever a forma de uma montanha apenas dizendo "ela é alta" ou "ela está longe". Falta a textura e a topologia (a forma como as coisas se conectam).

2. A Solução: O "Raio-X Topológico" (ECT)

Os autores criaram o LEAP baseando-se em algo chamado Transformada de Característica de Euler (ECT).

• A Analogia: Imagine que você tem uma estátua estranha. Para entendê-la, você não olha apenas de frente. Você coloca uma luz forte em várias direções diferentes e projeta a sombra dela em uma parede.
  • Se você olhar de um ângulo, a sombra pode parecer um círculo.
  • Se olhar de outro, parece um triângulo.
  • Se olhar de cima, parece um quadrado.
  • Somando todas essas "sombras" (ou curvas de Euler) de vários ângulos, você consegue reconstruir a forma exata e complexa da estátua, mesmo sem vê-la diretamente.

O LEAP faz exatamente isso com os grafos. Ele "ilumina" a vizinhança de cada ponto de vários ângulos matemáticos e cria uma "impressão digital" única baseada na forma como os vizinhos estão conectados.

3. O Grande Truque: "Aprendendo a Olhar" (Aprendizável)

Antes do LEAP, essa técnica de "iluminação" era estática. Era como ter uma lanterna fixa que você não podia mexer.

• O que o LEAP faz: Ele torna essa lanterna inteligente e treinável. Durante o aprendizado, o computador descobre sozinho quais ângulos de luz são mais importantes para resolver o problema.
• A Metáfora: Imagine um pintor que precisa copiar um quadro.
  • Método antigo: Ele usa uma régua fixa e uma régua de ângulo fixo. Se o quadro for difícil, ele não consegue capturar os detalhes.
  • Método LEAP: O pintor aprende a segurar a régua e o pincel de formas diferentes para cada parte do quadro. Ele ajusta sua "visão" para capturar a essência da estrutura.

4. Por que isso é incrível?

O artigo mostra dois resultados principais:

1. Entendendo o Invisível: Eles criaram um teste onde os pontos não tinham nenhuma informação (como nomes ou cores), apenas a estrutura de conexões. Os métodos antigos falharam miseravelmente (achavam que tudo era igual). O LEAP, porém, conseguiu distinguir as formas perfeitamente (100% de acerto). Foi como se ele conseguisse ler a "alma" da rede, ignorando o que estava escrito nela e focando apenas em como ela era desenhada.
2. Melhorando Tudo: Quando adicionado a redes neurais comuns, o LEAP funcionou como um "superpoder". Em vários testes reais (como prever propriedades de moléculas ou classificar redes sociais), ele fez os computadores ficarem mais inteligentes e precisos do que qualquer método anterior.

Resumo Simples

O LEAP é como dar aos computadores um novo par de óculos.

• Os óculos antigos só viam quem estava ao lado.
• Os óculos LEAP permitem que o computador veja a forma geométrica e a estrutura de um pedaço da rede, como se ele pudesse "sentir" a topologia (buracos, laços, conexões) de uma maneira que antes era impossível para máquinas.

Além disso, como esses óculos são "aprendizáveis", eles melhoram com o tempo, ajustando-se para ver exatamente o que é importante para a tarefa que o computador está tentando resolver. É um passo gigante para fazer a Inteligência Artificial entender o mundo complexo das conexões.

Resumo técnico

Resumo Técnico: LEAP

1. Problema e Motivação

As Redes Neurais em Grafos (GNNs) baseadas no paradigma de passagem de mensagens (MPNNs) enfrentam limitações teóricas e práticas bem documentadas, como a perda de sinais em grafos de grande diâmetro (oversquashing), o alisamento excessivo (oversmoothing) e a incapacidade de capturar eficientemente informações de subestruturas ou topologia global.

Para contornar isso, a comunidade tem explorado Codificações Posicionais (PEs) e Estruturais (SEs) para injetar informações estruturais nos nós. No entanto, as PEs existentes geralmente se baseiam apenas em aspectos geométricos (coordenadas, distâncias) ou topológicos específicos (como autovalores de Laplacianos ou passeios aleatórios), o que pode limitar sua expressividade. Além disso, muitas abordagens são estáticas (não treináveis) ou não conseguem capturar diferenças estruturais puras quando as características dos nós (features) não são informativas.

O objetivo deste trabalho é desenvolver uma codificação posicional que seja:

• Local e Estrutural: Focada na vizinhança do nó.
• Treinável (End-to-End): Integrável diretamente em pipelines de aprendizado profundo.
• Híbrida: Capaz de capturar simultaneamente informações geométricas e topológicas.

2. Metodologia

O artigo propõe o LEAP (Local ECT-based Learnable Positional Encodings), uma nova abordagem que combina a Transformada de Característica de Euler (ECT) com uma aproximação diferenciável e uma estratégia de projeção aprendível.

Conceitos Fundamentais:

• ECT (Transformada de Característica de Euler): Um invariante geométrico-topológico que descreve formas e grafos. Para grafos, a ECT mapeia vetores de direção para curvas que rastreiam a característica de Euler (nós - arestas) ao longo de subgrafos crescentes definidos por projeções.
• $\ell$-ECT (ECT Local): Uma variante da ECT calculada apenas sobre a vizinhança de $m$-hops de um nó, permitindo uma perspectiva local.
• DECT (ECT Diferenciável): Uma aproximação da ECT usando funções sigmóide para substituir funções indicadoras, tornando o processo diferenciável e apto para backpropagation.

O Pipeline do LEAP:

1. Seleção da Vizinhança: Para cada nó $v$, extrai-se o subgrafo da vizinhança de $m$-hops ($N_m(v, G)$).
2. Normalização: As características dos nós na vizinhança são centralizadas e normalizadas para residir na esfera unitária, garantindo invariância a escalas.
3. Cálculo da Matriz ECT: Calcula-se a aproximação diferenciável (DECT) para um conjunto finito de direções ($\Theta$) e thresholds ($T$), gerando uma matriz $M \in \mathbb{R}^{|\Theta| \times |T|}$.
4. Projeção Aprendível: Uma camada treinável ($\phi$) projeta a matriz $M$ em um vetor de codificação posicional de dimensão $k$.

Estratégias de Projeção:
O artigo avalia cinco estratégias para projetar a matriz ECT em vetores, incluindo:

• Projeção Linear (flattening).
• Convoluções 1D.
• DeepSets (para invariância a permutações das direções).
• Atenção (Transformer) simples e com PE (incorporando a direção como entrada).

Diferenciais:

• Ao contrário de PEs estáticas (como LaPE ou RWPE), o LEAP permite que as direções de projeção ($\Theta$) sejam inicializadas aleatoriamente e otimizadas durante o treinamento (LEAP-L), adaptando-se aos dados.
• O método é aplicável tanto a grafos atribuídos quanto não atribuídos (usando features aprendidas).

3. Contribuições Principais

1. Proposta do LEAP: Introdução da primeira codificação posicional local para grafos baseada em $\ell$-ECT que é totalmente treinável de ponta a ponta.
2. Captura de Topologia Pura: Demonstração experimental de que o LEAP consegue distinguir estruturas de grafos mesmo quando as características dos nós são não-informativas (ou seja, resolve tarefas puramente topológicas onde MPNNs falham).
3. Desempenho Superior: Evidência empírica de que o LEAP supera codificações posicionais estabelecidas (RWPE, LaPE) em múltiplos benchmarks e arquiteturas (GCN, GAT, GIN, e arquiteturas sem passagem de mensagens).
4. Análise de Robustez: Estudos de ablação que mostram a estabilidade do método em relação a hiperparâmetros (dimensão de embedding, número de hops) e a superioridade de direções aprendidas em relação a direções fixas.

4. Resultados Experimentais

Os autores avaliaram o LEAP em diversos conjuntos de dados sintéticos e reais (TU Benchmark, Alchemy, HIV):

• Dataset Sintético: Em um teste com 40.000 grafos onde a tarefa dependia apenas da contagem de arestas (topologia) e as features dos nós eram ruído, o LEAP alcançou 100% de precisão. Em contraste, GCN e GAT padrão tiveram precisão inferior a 72%, falhando em capturar a estrutura sem features informativas.
• Classificação em Benchmarks (TU): O LEAP (especialmente com direções aprendidas - LEAP-L) obteve consistentemente os melhores ou segundos melhores resultados em conjuntos de dados como LETTER-H, LETTER-M, LETTER-L e FINGERPRINT.
  • Em alguns casos (ex: LETTER-H), o uso de LEAP com uma arquitetura "NoMP" (sem passagem de mensagens) superou modelos GNN tradicionais, destacando a força da codificação estrutural.
• Dataset Alchemy (Regressão): O LEAP superou todas as baselines, demonstrando eficácia em tarefas de regressão com invariância rotacional.
• Dataset HIV (Classificação): O LEAP performou bem, superando o RWPE (sua contraparte local). Embora a codificação global (LaPE) tenha sido forte isoladamente, a combinação de LaPE + LEAP resultou no melhor desempenho global, sugerindo que as abordagens local e global são complementares.
• Ablação de Hiperparâmetros:
  • Vizinhança: Vizinhos de 1-hop foram suficientes; aumentar para 2-hops não melhorou significativamente o desempenho e, em alguns casos, piorou.
  • Direções: O aprendizado das direções (LEAP-L) geralmente superou o uso de direções fixas (LEAP-F).
  • Projeção: Nenhuma estratégia de projeção foi universalmente superior; a escolha depende da combinação dataset-arquitetura.

5. Significância e Conclusão

O LEAP representa um avanço significativo na aprendizagem de representações de grafos e na topologia profunda (topological deep learning).

• Ponte entre Topologia e Deep Learning: O trabalho demonstra como invariantes topológicos clássicos (ECT) podem ser adaptados para redes neurais modernas através de aproximações diferenciáveis e treinamento end-to-end.
• Superação de Limitações do MPNN: Ao fornecer informações estruturais ricas e locais, o LEAP mitiga a necessidade de arquiteturas complexas para capturar padrões topológicos simples.
• Versatilidade: O método é compatível com qualquer GNN e pode ser combinado com outras PEs (globais) para obter o melhor dos dois mundos.

Limitações e Futuro:
O método ainda depende de features de nós (embora possam ser aprendidas) e introduz hiperparâmetros adicionais (número de direções, suavização). Trabalhos futuros visam formalizar a expressividade teórica, tornar a etapa de ECT totalmente diferenciável (aprendendo os thresholds) e estender o método para complexos simpliciais e celulares de ordem superior.

Em suma, o LEAP estabelece um novo estado da arte para codificações posicionais locais, provando que a integração de topologia geométrica aprendível é uma ferramenta poderosa para a próxima geração de modelos de grafos.