Resumo Técnico: Rede Neural de Grafos aproveitando a Conectividade de Rótulos de Classe de Ordem Superior para Grafos Heterófilos

Declaração do Problema

A classificação de nós em Redes Neurais de Grafos (GNNs) alcançou alta precisão em grafos homófilos, onde nós com rótulos de classe semelhantes tendem a se conectar. No entanto, o desempenho degrada-se significamente em grafos heterófilos, onde nós com diferentes rótulos de classe têm maior probabilidade de estarem conectados.

Os autores identificam uma limitação específica nas GNNs atuais (incluindo aquelas derivadas de Redes Neurais Convolucionais de Grafos como GCN, GAT e modelos avançados para heterofilia como H2GCN e LINKX): elas transformam o problema de classificação de nós em um mapeamento simples do espaço de incorporação (embedding) para o espaço de rótulo de classe. Consequentemente, esses modelos falham em capturar a conectividade de rótulos de classe de ordem superior — as relações estruturais entre rótulos de classe que abrangem múltiplos saltos (hops) via arestas direcionadas. Embora alguns métodos utilizem uma matriz de compatibilidade de classes para capturar a conectividade de 1ª ordem, eles não consideram interações complexas de rótulos de múltiplos saltos frequentemente observadas em grafos direcionados do mundo real (ex: o conjunto de dados Texas, onde nós "Estudante" conectam-se a nós "Departamento", que por sua vez conectam-se a nós "Funcionário").

Metodologia

A abordagem proposta introduz um classificador inovador, o Classificador de Contexto de Rótulo (LCC), e um framework para integrá-lo com GNNs existentes.

1. Classificador de Contexto de Rótulo (LCC)

O LCC é projetado para capturar a conectividade de rótulos de classe de ordem superior, tratando sequências de rótulos de classe ao longo de caminhadas (walks) no grafo como contexto, inspirado no modelo word2vec Skip-gram. O processo envolve três etapas principais:

• Extração de Caminhada de Rótulos (Label Walk Extraction): A partir de um nó alvo, quatro tipos distintos de caminhadas de rótulos são extraídos. Uma caminhada de rótulo é uma sequência de rótulos de classe onde os nós são substituídos por seus rótulos. Se um nó não estiver no conjunto de treinamento, um rótulo nulo é utilizado.
  • Caminhada Direta (Forward Walk): Uma busca em profundidade seguindo a direção das arestas (Alvo $\to$ Filho $\to$ Neto).
  • Caminhada Reversa (Backward Walk): Uma busca em profundidade seguindo a direção inversa das arestas (Alvo $\to$ Pai $\to$ Avô).
  • Caminhada de Irmãos (Sibling Walk): Atravessa para trás até um nó pai e depois para frente para seus outros filhos (Alvo $\to$ Pai $\to$ Irmão). Isso captura a conectividade entre nós que compartilham um pai comum.
  • Caminhada de Guardião (Guardian Walk): Atravessa para frente até um nó filho e depois para trás para seus outros pais (Alvo $\to$ Filho $\to$ Co-pai). Isso captura a conectividade entre nós que compartilham um filho comum.
• Geração de Incorporação de Contexto de Rótulo (Label Context Embedding Generation): Usando as caminhadas de rótulos extraídas, o modelo aprende incorporações que representam o "contexto do rótulo". Um MLP (Perceptron Multicamadas) simples de duas camadas é treinado para prever os rótulos de contexto (os rótulos subsequentes na caminhada) dado o rótulo do nó alvo como entrada. A camada oculta produz as incorporações de contexto de rótulo ($Z$).
• Treinamento do Classificador: O classificador LCC final é um MLP treinado na concatenação das características originais do nó e das incorporações de contexto de rótulo derivadas dos quatro tipos de caminhada.

2. Integração com GNNs

Para aproveitar os pontos fortes de ambas as GNNs tradicionais (que capturam informações de características e estrutura local) e o LCC (que captura conectividade de rótulo de ordem superior), os autores propõem um esquema de integração adaptativa:

• Treinamento Independente: Tanto a GNN quanto o LCC são treinados independentemente no conjunto de treinamento.
• Ponderação Adaptativa: A importância de cada modelo é determinada usando a perda de validação (validation loss). Os pesos ($w_{LCC}$ e $w_{GNN}$) são calculados como o recíproco da perda de validação, ajustados por um parâmetro de temperatura ($T$).
• Predição de Ensemble: A predição final é uma média ponderada das saídas da GNN e do LCC. Esta integração não requer treinamento de modelo adicional, apenas o cálculo de pesos com base no desempenho de validação.

Principais Contribuições

1. Proposta do LCC: Um classificador inovador que estima rótulos de nós capturando a conectividade de rótulos de classe de ordem superior através de quatro caminhadas de rótulo sensíveis à direção (Direta, Reversa, Irmãos, Guardião).
2. Framework de Integração Adaptativa: Um método para integrar o LCC com qualquer GNN existente, combinando adaptativamente pesos de importância baseados na perda de validação, sem exigir custos de treinamento adicionais.
3. Validação Empírica: Resultados experimentais demonstrando que a integração do LCC com GNNs supera os métodos de Estado da Arte (SOTA) em grafos direcionados heterófilos.

Resultados Experimentais

Os autores avaliaram seu método em sete conjuntos de dados de grafos direcionados heterófilos: Cornell, Texas, Wisconsin, Chameleon, Squirrel, Roman-Empire e Amazon-Ratings.

• Melhoria de Desempenho: Os modelos integrados (ex: H2GCN+LCC, LINKX+LCC, GloGNN+LCC) alcançaram a maior precisão de classificação de nós em todos os conjuntos de dados comparados com GNNs isoladas, MLPs e o LCC sozinho.
• Complementaridade: Os resultados indicam que o LCC e as GNNs capturam propriedades de grafos diferentes. Na maioria dos casos, a integração melhorou a precisão em relação aos componentes individuais.
• Eficácia das Caminhadas de Rótulos: O LCC superou significativamente um MLP vanilla (que usa apenas características do nó), confirmando que as incorporações de contexto de rótulo capturam efetivamente a conectividade de rótulo. Notavelmente, os ganhos de precisão excederam 10% em conjuntos de dados como Chameleon, Squirrel, Roman-Empire e Amazon-Ratings.
• Importância do Tipo de Caminhada: A importância de tipos específicos de caminhada variou conforme o conjunto de dados. Por exemplo, as caminhadas de Guardião foram mais críticas para Chameleon, Squirrel e Amazon-Ratings, enquanto as caminhadas de Irmãos foram mais eficazes para Roman-Empire.
• Comprimento da Caminhada: Aumentar o comprimento da caminhada (para as caminhadas direta/reversa) ou utilizar caminhadas de 2 saltos (irmãos/guardião) geralmente melhorou o desempenho, destacando a necessidade de capturar a conectividade de ordem superior.

Significância e Alegações

O artigo alega que a principal fraqueza das GNNs atuais em cenários heterófilos é sua incapacidade de modelar como os rótulos de classe se conectam através de múltiplos saltos em grafos direcionados. Ao modelar explicitamente essas relações de ordem superior via caminhadas de rótulos, o LCC fornece um sinal complementar às GNNs baseadas em características.

Os autores enfatizam que sua abordagem não requer mudanças arquitetônicas complexas nas GNNs existentes; em vez disso, oferece um classificador modular que pode ser adaptativamente combinado com qualquer GNN para aumentar o desempenho. Os resultados sugerem que aproveitar a informação estrutural entre rótulos de classe, em vez de apenas características de nós ou vizinhos imediatos, é crucial para a classificação precisa em grafos direcionados heterófilos. O trabalho é apoiado pelas concessões JSPS KAKENHI e JST ASPIRE.