Improving Graph Few-shot Learning with Hyperbolic Space and Denoising Diffusion

1. Declaração do Problema

O artigo aborda os desafios da Aprendizagem de Poucos Exemplos em Grafos (Graph Few-Shot Learning - FSL), especificamente a tarefa de classificação de nós não supervisionada com poucos exemplos. O objetivo é classificar nós em novas categorias utilizando apenas um pequeno número de nós de suporte rotulados ($M$-shot) e um grande número de nós de consulta não rotulados, sem depender de dados rotulados durante a fase de meta-treinamento.

Os autores identificam duas limitações críticas nos métodos existentes de Graph FSL:

1. Limitações do Espaço Euclidiano: A maioria dos modelos atuais aprende representações de nós no espaço euclidiano. No entanto, dados de grafos do mundo real (por exemplo, estruturas organizacionais, taxonomias acadêmicas) frequentemente possuem estruturas hierárquicas ou semelhantes a árvores inerentes. A geometria euclidiana sofre de distorção significativa ao incorporar tais estruturas, falhando em capturar as verdadeiras relações geométricas.
2. Viés Distribucional e Overfitting: Na fase de meta-teste, os modelos geralmente treinam classificadores em um conjunto de suporte muito pequeno. Isso leva a dois problemas:
   • A distribuição empírica do pequeno conjunto de suporte frequentemente desvia-se significativamente da verdadeira distribuição subjacente da classe (mudança distribucional).
   • O treinamento direto em dados esparsos causa overfitting severo, prejudicando a generalização para o conjunto de consulta.

2. Metodologia: Framework IMPRESS

O framework proposto, IMPRESS (IMproves Praph Representation with Enhanced Space and Sampling), opera em duas fases: Meta-Treinamento e Meta-Teste. Ele integra Geometria Hiperbólica e Modelos de Difusão com Remoção de Ruído.

A. Fase de Meta-Treinamento

1. Aprendizado de Representação de Nós Hiperbólica:

   • Em vez do espaço euclidiano, o modelo aprende embeddings de nós em uma bola de Poincaré (espaço hiperbólico), que acomoda naturalmente estruturas hierárquicas.
   • Arquitetura: Um Variational Graph Autoencoder (VGAE) é utilizado.
     • Codificador: As características dos nós são projetadas do espaço euclidiano para o espaço tangente da variedade hiperbólica usando o mapa logarítmico. A convolução em grafos (GCN) é realizada no espaço tangente. Os embeddings resultantes são mapeados de volta ao espaço hiperbólico via o mapa exponencial.
     • Decodificador: Reconstrói a matriz de adjacência do grafo usando o produto interno das variáveis latentes no espaço hiperbólico.
   • Objetivo: O modelo é treinado de forma não supervisionada (usando apenas estrutura e características do grafo) para minimizar a perda de reconstrução e a divergência KL, aprendendo distribuições latentes que preservam a geometria hierárquica.

2. Difusão com Remoção de Ruído Guiada por Protótipos:

   • Como os rótulos não estão disponíveis durante o meta-treinamento, o modelo utiliza agrupamento não supervisionado (DBSCAN) nos embeddings latentes aprendidos para atribuir pseudo-rótulos e calcular protótipos de classe.
   • Um Modelo Probabilístico de Difusão com Remoção de Ruído (DDPM) é treinado nesses embeddings latentes.
   • Condicionamento: O processo de difusão é condicionado aos protótipos de classe através de um mecanismo de atenção cruzada. Isso permite que o modelo aprenda a distribuição de dados de cada classe sem rótulos verdadeiros explícitos, preparando-o para gerar amostras para novas classes posteriormente.

B. Fase de Meta-Teste

1. Geração de Embeddings:
   • Para uma nova tarefa com um pequeno conjunto de suporte ($S_{tes}$) e conjunto de consulta ($Q_{tes}$), o VGAE pré-treinado codifica os nós no espaço latente hiperbólico.
   • Protótipos de classe são calculados a partir do conjunto de suporte rotulado.
2. Aumento de Dados:
   • O modelo de difusão treinado gera $D$ novos embeddings de nós sintéticos para cada nova classe, condicionados aos protótipos do conjunto de suporte.
   • Essas amostras geradas são combinadas com o conjunto de suporte original para formar um conjunto de suporte aumentado ($\tilde{S}_{tes}$), efetivamente aumentando o tamanho da amostra de $M$ para $M+D$.
3. Classificação:
   • Um classificador linear é treinado no conjunto de suporte aumentado e avaliado no conjunto de consulta.

3. Principais Contribuições

1. Framework Inovador (IMPRESS): O primeiro framework a combinar Espaço Hiperbólico para representação estrutural e Difusão com Remoção de Ruído para enriquecimento distribucional no contexto de aprendizagem de poucos exemplos em grafos não supervisionada.
2. Avanço Teórico:
   • Provou que a codificação hiperbólica fornece um limite de generalização mais apertado ($O(e^{-\delta})$) em comparação com a codificação euclidiana para grafos $\delta$-hiperbólicos.
   • Derivou um limite de erro de classificação mostrando que o método proposto reduz o erro minimizando a variância intra-classe, maximizando a distância inter-classe e reduzindo a distância de Wasserstein entre as distribuições geradas e verdadeiras.
3. Difusão Guiada por Protótipos: Introduziu um mecanismo para guiar modelos de difusão usando protótipos de classe em um cenário não supervisionado, resolvendo o desafio de gerar amostras para novas classes sem informações prévias de rótulos.
4. Superioridade Empírica: Demonstrou desempenho consistente de ponta (state-of-the-art) em múltiplos benchmarks.

4. Resultados Experimentais

O modelo foi avaliado em seis conjuntos de dados de referência: CoraFull, Coauthor-CS, Cora, WikiCS, Cora-ML, CiteSeer, e o de grande escala ogbn-arxiv.

• Desempenho: O IMPRESS superou consistentemente uma ampla gama de baselines, incluindo:
  • Métodos de embedding de grafos (GCN, SGC).
  • Meta-aprendizagem tradicional (ProtoNet, MAML).
  • Meta-aprendizagem em grafos (Meta-GNN, GPN, TEG, COSMIC).
  • Meta-aprendizagem em grafos não supervisionada (VNT, NaQ).
  • Exemplo: No ogbn-arxiv (5-way 3-shot), o IMPRESS alcançou 61,11% de precisão, superando significativamente o segundo colocado (COSMIC com 52,98%). No CoraFull, atingiu 85,49% (vs. 75,18% para o próximo melhor).
• Estudos de Ablação:
  • A remoção do componente hiperbólico (w/o hyp) causou uma queda significativa no desempenho, confirmando a necessidade da geometria hiperbólica para dados hierárquicos.
  • A remoção do componente de difusão (w/o dif) também degradou o desempenho, validando que o aumento de dados via difusão mitiga efetivamente a escassez de rótulos e o viés distribucional.
• Sensibilidade a Hiperparâmetros:
  • A curvatura ótima ($c$) foi encontrada entre 0,5 e 2,0.
  • O número de amostras geradas ($D$) mostrou uma tendência em forma de U invertido, com desempenho ótimo em $D=50$.

5. Significado

Este trabalho preenche a lacuna entre aprendizado profundo geométrico e modelagem generativa para dados de grafos.

• Insight Geométrico: Valida que grafos do mundo real são melhor modelados no espaço hiperbólico, oferecendo uma solução teórica e prática para o problema de "distorção" dos embeddings euclidianos.
• Solução para Escassez de Dados: Ao alavancar modelos de difusão para sintetizar amostras de alta qualidade condicionadas à classe, oferece uma estratégia robusta para superar o gargalo de "poucos dados" na aprendizagem de poucos exemplos, reduzindo o overfitting e melhorando as fronteiras de decisão.
• Capacidade Não Supervisionada: A capacidade de treinar modelos de difusão usando pseudo-rótulos derivados de agrupamento não supervisionado torna o framework altamente aplicável a cenários do mundo real onde dados rotulados são caros ou inexistentes.