When Should Graph Attention Be Sparse? Learning a Per-Edge Tsallis Index

Problema

As Redes de Atenção em Grafos (GAT) normalizam os escores de relevância de vizinhança usando softmax, o que corresponde à solução de máxima entropia sob a estatística de Shannon. Esse design assume implicitamente que os pesos de atenção devem ser distribuídos de acordo com estatísticas extensivas (Boltzmann–Gibbs). No entanto, grafos do mundo real frequentemente violam essas suposições:

• Grafos homofílicos (ex: redes de citações) frequentemente se beneficiam ao focar em alguns poucos vizinhos altamente relevantes, ignorando a cauda longa de outros fracamente relacionados.
• Grafos heterofílicos (ex: grafos da web) frequentemente se beneficiam ao agregar pequenas quantidades de evidência de muitos vizinhos dissimilarmente relacionados.

A softmax padrão é subótima para ambos os regimes porque não consegue representar zeros exatos (forçando uma atenção densa) e impõe um comportamento de cauda fixo. Embora existam alternativas esparsas como Sparsemax e $\alpha$-entmax, elas tipicamente dependem de hiperparâmetros fixos ou são restritas a regimes específicos (ex: $\alpha$-entmax é definida apenas para $\alpha \ge 1$, perdendo o regime de cauda pesada). Além disso, métodos existentes frequentemente tratam o índice de esparsidade como um hiperparâmetro congelado que requer busca em grade (grid search) por tarefa.

Metodologia: LTGA

Os autores propõem a LTGA (Learnable Tsallis Graph Attention), uma camada de atenção em grafos que substitui a normalização softmax padrão por uma $q$-softmax baseada na estatística de Tsallis. O índice entrópico $q$ é aprendido de ponta a ponta (end-to-end), permitindo que o modelo interpole continuamente entre três regimes:

1. Cauda pesada ($q < 1$): Suporte ilimitado, mantendo peso em vizinhos de baixo escore.
2. Shannon/Softmax ($q = 1$): A linha de base padrão do GAT.
3. Suporte compacto ($q > 1$): Produz zeros exatos para escores abaixo de um limiar, realizando efetivamente a poda de vizinhos não informativos.

Componentes Técnicos Principais:

• Reparametrização: Para garantir estabilidade numérica e evitar que o índice derive para regimes degenerados, $q$ é parametrizado como $q(\alpha) = 1 + \delta \tanh(\alpha)$, onde $\alpha$ é um escalar sem restrições. Isso fixa a inicialização na linha de base de Shannon ($q=1$) quando $\alpha=0$.
• Granularidades: O índice $q$ pode ser vinculado em quatro níveis de granularidade, trocando expressividade por contagem de parâmetros:
  • Global-q: Um único escalar compartilhado entre todas as camadas e cabeças (heads).
  • Layer-q: Um escalar por camada.
  • Head-q: Um escalar por cabeça de atenção.
  • Edge-q (LTGA-Edge): Um índice por aresta gerado por um pequeno MLP que mapeia os embeddings dos pontos finais para um portão (gate) escalar. Isso permite que diferentes arestas dentro da mesma vizinhança adotem diferentes regimes de atenção.
• Estabilidade Numérica: Uma ramificação de expansão de Taylor é usada próximo a $q=1$ para lidar com a singularidade removível na função $q$-exponencial, garantindo valores e gradientes contínuos.
• Estabilizadores de Treinamento:
  • Otimizador Desacoplado: Um otimizador Adam separado para os parâmetros $\alpha$ com um cronograma de warm-up (congelando $\alpha=0$ para os primeiros $T_w$ épocas) permite que os pesos das características converjam antes que a geometria da atenção mude.
  • Regularizador de Prior de Shannon: Uma penalidade quadrática em $(q-1)^2$ atua como a navalha de Occam, penalizando desvios da linha de base softmax, a menos que melhorem a perda da tarefa.

Principais Contribuições

1. Índice Entrópico Aprendível: A LTGA introduz um $q$ aprendível para a atenção em grafos, cobrindo toda a família Tsallis de dois lados ($q<1$ e $q>1$), ao contrário de trabalhos anteriores restritos a $\alpha \ge 1$.
2. Formulação Estável: O artigo fornece uma formulação $q$-softmax numericamente estável com uma ramificação de Taylor em torno do limite de Shannon, juntamente com estratégias de reparametrização e regularização para permitir um treinamento estável de ponta a end.
3. Avaliação Abrangente: O método é avaliado em oito benchmarks abrangendo um amplo espectro de homofilia ($h \in [0.05, 0.81]$), comparando contra softmax, grades de $q$ congelado, $\alpha$-entmax ajustado, sparsemax e arquiteturas específicas de heterofilia.
4. Análise de Interpretabilidade: Os autores analisam o comportamento do índice aprendido, vinculando $q>1$ à poda de vizinhança dependente de dados e verificando que as arestas podadas são, de fato, "ruído" (baixo acordo de rótulos e similaridade de características).

Resultados

• Desempenho: Em 10 sementes e 8 conjuntos de dados, a LTGA-Edge atinge o melhor ranking médio de Friedman (2.75), superando GAT (3.19) e GATv2 (4.06). No entanto, o teste omnibus não rejeita a hipótese nula ($p=0.199$), indicando que a diferença de desempenho agregada não é estatisticamente significativa entre todos os métodos.
• Ganhos Específicos: Os principais ganhos são observados em benchmarks heterofílicos:
  • Roman-Empire ($h=0.05$): LTGA-Edge melhora a acurácia em +16.3% sobre GAT e +1.4% sobre GATv2.
  • Amazon-Ratings ($h=0.38$): LTGA-Edge melhora a acurácia em +0.8% sobre GAT e +1.1% sobre GATv2.
  • Em grafos homofílicos (Cora, CiteSeer, PubMed), $q$ converge para 1, e a LTGA performa comparavelmente ao GATv2.
• Aprendizado vs. Ajuste: Aprender $q$ não supera estritamente a busca pelo $q$ congelado ideal. Uma grade congelada ajustada via validação alcançou 61.4%, o $\alpha$-entmax ajustado alcançou 62.2%, e um controle de capacidade equivalente alcançou 62.0%, comparado a 61.7% para LTGA-Edge. O artigo conclui que o valor de aprender $q$ é a conveniência (uma única execução em vez de uma busca em grade) e a adaptabilidade, em vez de um teto bruto de acurácia.
• Validação do Mecanismo:
  • Em Roman-Empire, o índice aprendido poda cerca de 42% dos coeficientes de atenção para exatamente zero.
  • Seletividade: As arestas podadas possuem significativamente menor acordo de rótulos (9.3% vs 43.5% para arestas mantidas) e similaridade de características.
  • Contrafatuais: Restaurar as arestas podadas na inferência reduz a acurácia em 7.1 pontos; podar aleatoriamente o mesmo número de arestas reduz a acurácia 13.0 pontos mais do que a poda aprendida, confirmando que a esparsidade é seletiva e benéfica.
• Granularidade: Embora a LTGA-Edge apresente o melhor ranking médio, as granularidades escalares (Global, Layer, Head) performam de forma semelhante em datasets onde $q$ se move, sugerindo que a capacidade por aresta é o principal motor de desempenho em grafos heterofílicos.

Significância e Alegações

O artigo alega modestamente que a LTGA fornece um framework unificado e aprendível para a normalização de atenção em grafos que se adapta às necessidades estatísticas específicas de um grafo sem ajuste manual de hiperparâmetros.

• Interpretabilidade: Onde $q$ se afasta da linha de base de Shannon, ele o faz de forma interpretável: $q>1$ corresponde à poda seletiva de vizinhos não informativos (suporte compacto), enquanto $q<1$ corresponde à difusão de cauda pesada.
• Limitações: Os autores declaram explicitamente que o regime de cauda pesada ($q<1$) não mostrou benefícios empíricos nos benchmarks testados. Eles também observam que, em datasets pequenos e de alta variância (WebKB), o método não oferece vantagem sobre o GATv2.
• Posicionamento: Não se alega que a LTGA seja complementar a arquiteturas específicas de heterofilia (como H2GCN ou GPR-GNN), pois esses modelos não normalizam a atenção da mesma forma. Em vez disso, a LTGA compete diretamente com modelos baseados em atenção e oferece um mecanismo para substituir a normalização softmax fixa por uma alternativa adaptativa e orientada a dados.

Em resumo, a LTGA demonstra que aprender o índice entrópico permite que uma rede de atenção em grafos descubra automaticamente se deve ser densa, esparsa ou de cauda pesada com base na homofilia do grafo, ofereando uma alternativa robusta e de execução única aos mecanismos de atenção esparsa buscados via grade.