Resumo Técnico: HOPPER – Extração de Saltos Aprendível para Modelos de Sequência de Grafos Linearizados

1. Definição do Problema

As Redes Neurais de Grafos (GNNs), particularmente as Redes Neurais de Passagem de Mensagens (MPNNs), enfrentam desafios fundamentais na modelagem de dependências de longo alcance. Nas MPNNs padrão, a distância que a informação percorre (profundidade de informação) está estritamente acoplada ao número de transformações não lineares aplicadas (profundidade de processamento). Para capturar informações de nós a $r$ saltos de distância, um modelo requer pelo menos $r$ camadas. Esse acoplamento leva a dificuldades de otimização, suavização excessiva (over-smoothing, perda de identidade do nó) e esmagamento excessivo (over-squashing, compressão de vizinhanças extensas em vetores de dimensão fixa), o que limita severamente o desempenho em tarefas que exigem contexto global.

Modelos de Sequência de Grafos Linearizados (LGSMs) foram propostos para desacoplar essas dimensões. Os LGSMs tratam os estados de propagação sucessivos de cada nó como uma sequência sobre a profundidade de informação, permitindo que um modelo de sequência moderno (por exemplo, um Modelo de Espaço de Estados) processe esses estados independentemente da ordenação dos nós. No entanto, os LGSMs existentes dependem de operadores de grafos fixos (como potências de adjacência normalizadas ou recorrências de não-retrocesso/non-backtracking) para construir essas sequências. Essas regras fixas não conseguem se adaptar a estruturas de grafos específicas, características de nós ou à utilidade variável de diferentes intervalos de vizinhança através de diferentes tarefas e profundidades de informação. Consequentemente, o modelo de sequência a jusante pode ser forçado a compensar estratégias de propagação subótimas impostas pelo extrator fixo.

2. Metodologia: HOPPER

Os autores introduzem o HOPPER, uma extensão aprendível de ponta a ponta do LGSM que aprende como as sequências de saltos são extraídas antes de serem processadas por um modelo de espaço de estados. O HOPPER preserva a separação da profundidade de informação e da profundidade de processamento, introduzindo adaptabilidade através de quatro componentes principais:

2.1 Resumo de Grafo Invariante à Permutação

Para condicionar a propagação ao grafo de entrada sem violar a equivariância à permutação, o HOPPER primeiro constrói um resumo de grafo de dimensão fixa ($h_{graph}$).

• As características dos nós são aumentadas com informações de vizinhança de um salto ($H_{nbr} = A_{rw}H$).
• Um conjunto de consultas sementes (seed queries) aprendíveis ($Q_s$) realiza atenção cruzada (cross-attention) com essas representações de nós aumentadas.
• A representação latente resultante é vetorizada para formar $h_{graph}$. Este resumo é invariante à ordenação dos nós e independente do tamanho do grafo.

2.2 Geração de Coeficientes Condicionados ao Salto

Uma hiperrede gera coeficientes de propagação condicionados tanto ao resumo global do grafo ($h_{graph}$) quanto a um embedding de salto específico ($e_k$).

• A hiperrede produz escalares ($\alpha_A, \alpha_D, \alpha_I, \beta$) que determinam a combinação linear de operadores estruturais em cada salto.
• Isso permite que a regra de propagação varie entre diferentes grafos e se adapte dinamicamente conforme a profundidade de informação aumenta.

2.3 Recorrência Estrutural-Estado Linear

O núcleo do extrator é uma recorrência linear que acumula um estado estrutural $U^{(k)}$ sobre uma janela de memória finita de tamanho $M$:
$$U^{(k)} = \sum_{j=1}^{M} \left( \alpha_A^{(k)}[j]A + \alpha_D^{(k)}[j]D + \alpha_I^{(k)}[j]I \right) U^{(k-j)}$$

• $U^{(0)} = H$ (características iniciais).
• A recorrência utiliza matrizes de adjacência não normalizadas ($A$) e de grau ($D$) para manter a estrutura polinomial exata, embora variantes normalizadas sejam usadas para estabilidade numérica em sequências profundas.
• Crucialmente, a normalização e as não-linearidades são mantidas fora da recorrência para preservar as propriedades algébricas necessárias para recuperar os extratores LGSM fixos.

2.4 Correção por Atenção de Características

Para enriquecer a sequência extraída sem introduzir não-linearidades na recorrência estrutural, um termo de atenção de características é aplicado apenas ao estado de saída:
$$S^{(k)} = \text{LayerNorm}\left( U^{(k)} + \beta_k F_k U^{(k)} \right)$$
onde $F_k$ é uma matriz de atenção computada a partir das características originais dos nós. Isso permite que o modelo corrija ou pondere o estado estrutural com base no conteúdo das características.

A sequência resultante $S$ é processada por uma pilha de blocos de Modelo de Espaço de Estados (SSM) baseados em Mamba2, que operam independentemente na sequência de cada nó.

3. Contribuições Principais e Propriedades Teóricas

O artigo estabelece várias garantias teóricas em relação ao HOPPER:

• Equivariância à Permutação: Apesar de condicionar a propagação a um resumo de grafo aprendido, o HOPPER permanece permutação-equivariante. A reordenação do grafo de entrada resulta na mesma permutação aplicada às sequências de nós extraídas, garantindo que o modelo não dependa de ordenações arbitrárias de nós.
• Estrutura Polinomial Adaptável ao Grafo: Os estados estruturais correspondem a polinômios não comutativos de grau finito em $A$ e $D$. Condicionado aos coeficientes da hiperrede, o $k$-ésimo estado propaga informação por, no máximo, $k$ saltos. No entanto, os próprios coeficientes se adaptam ao grafo e às características, permitendo que a regra de propagação mude dinamicamente.
• Recuperação de Extratores Fixos: O HOPPER é uma generalização dos LGSMs existentes. Ao definir coeficientes específicos, ele pode recuperar exatamente:
  • Propagação de adjacência normalizada ($S = A_{sym}$).
  • Propagação de não-retrocesso (non-backtracking).
  • Propagação de Chebyshev estável (que é não-expansiva).
• Sensibilidade de Longo Alcance Ótima: Sob uma restrição de estabilidade espectral uniforme (onde a norma do propagador é $\le 1$), o artigo prova que a propagação de Chebyshev (realizável pelo HOP certo do HOPPER) atinge a sensibilidade de primeira chegada máxima possível ($2^{r-1}$ vezes maior que a propagação de potência padrão) para nós à distância $r$.
• Mitigação da Suavização Excessiva (Over-Smoothing): A análise teórica mostra que, enquanto a propagação de adjacência repetida faz com que a informação espectral não estacionária desapareça (suavização excessiva), a sequência de Chebyshev preserva uma fração não nula dessa informação através da profundidade da sequência.

4. Resultados Experimentais

O HOPPER foi avaliado em dois benchmarks:

1. ECHO-SYNTH (Propriedades de Grafos Sintéticos):

   • Tarefas: Diâmetro do grafo (DIAM), excentricidade do nó (ECC) e predição de caminho mínimo de origem única (SSSP).
   • Resultados: O HOPPER alcançou o estado da arte no ECC (MSE: 6.571 vs. LGSM: 13.549) e no SSSP (MSE: 0.021 vs. LGSM: 0.040). Permaneceu competitivo no DIAM, ficando ligeiramente atrás da melhor variante de LGSM, mas superando todas as outras linhas de base, incluindo Graph Transformers e métodos de reestruturação (rewiring).

2. LRIM-16 (Dependência de Longo Alcance Baseada em Física):

   • Tarefa: Regressão de energia ao nível do nó em grades periódicas de Ising 16x16 com interações de longo alcance.
   • Resultados: O desempenho variou com o tamanho da janela de memória estrutural $M$. Um tamanho de janela de $M=8$ produziu os melhores resultados (log10 MSE: -3.505), demonstrando que a quantidade de memória estrutural retida durante a extração impacta significativamente o desempenho em tarefas baseadas em física.

5. Significância e Alegações

O artigo afirma que o HOPPER fornece uma abordagem flexível e eficaz para o aprendizado de representações de grafos de longo alcance ao tornar o processo de extração de sequência aprendível.

• Desacoplamento: Ele consegue desacoplar a profundidade de informação da profundidade de processamento, permitindo propagação profunda sem as não-linearidades cumulativas que causam suavização excessiva e esmagamento excessivo em GNNs tradicionais.
• Adaptabilidade: Diferente dos LGSMs fixos, o HOPPER adapta sua estratégia de propagação à estrutura específica do grafo, às características dos nós e à profundidade de informação, evitando as sequências subótimas que operadores fixos poderiam produzir.
• Fundamentação Teórica: O framework não é apenas empiricamente eficaz, mas teoricamente fundamentado, mostrando que pode recuperar esquemas de propagação estabelecidos enquanto oferece uma classe mais rica de polinômios de grafos que otimizam a sensibilidade de longo alcance e preservam a informação espectral.
• Trabalhos Futuros: Os autores observam que estender o HOPPER para domínios moleculares do mundo real é uma direção natural para trabalhos futuros, mas não alegam sucesso atual nesse domínio específico.

Em resumo, o HOPPER demonstra que a extração de sequência aprendível, combinada com modelos de espaço de estados modernos, oferece uma alternativa superior às regras de propagação fixas para capturar dependências de longo alcance em grafos.