Mini-Batch Class Composition Bias in Link Prediction

1. Declaração do Problema

O artigo aborda uma desconexão crítica entre as tarefas de Predição de Links e Classificação de Nós em Redes Neurais de Grafos (GNNs).

• A Intuição: Geralmente, hipotetiza-se que GNNs treinadas para predição de links devem aprender representações de grafos consistentes com aquelas aprendidas para classificação de nós. Isso baseia-se na premissa de que, em grafos homofílicos (onde nós da mesma classe se conectam), os padrões estruturais usados para prever links devem inerentemente codificar informações de classe dos nós.
• A Realidade: Os autores demonstram que essa intuição frequentemente falha na prática. Modelos populares de predição de links frequentemente falham em aprender características significativas de classe de nós. Em vez disso, eles aprendem um heurístico trivial dependente de mini-lotes, habilitado por camadas de Normalização em Lote (BN).
• O Mecanismo de Falha: O treinamento padrão de predição de links constrói mini-lotes com uma razão fixa de arestas positivas (existentes) e negativas (não existentes) (tipicamente 50/50). A camada de Normalização em Lote calcula estatísticas (média e variância) sobre o lote. Como a distribuição de classes é fixa, a camada de BN permite que o modelo "trapaceie" aprendendo um mapeamento simples baseado na composição do lote, em vez da topologia real do grafo ou nas características dos nós. Isso leva a métricas de desempenho infladas (por exemplo, Hits@K) que não refletem uma verdadeira compreensão das propriedades subjacentes do grafo.

2. Metodologia

A. Análise Teórica do Viés

Os autores derivam matematicamente como a Normalização em Lote facilita esse viés:

1. Em um mini-lote padrão com $K_+$ arestas positivas e $K_-$ arestas negativas (onde $K_+ \approx K_-$), a camada de BN normaliza as ativações com base na média do lote $\mu = K_+/K$ e variância $\sigma^2 = K_+K_-/K^2$.
2. Essa normalização colapsa todas as arestas positivas para um único valor constante e todas as arestas negativas para outro valor constante dentro do lote.
3. Uma transformação afim subsequente ($\gamma \hat{a} + \beta$) pode separar facilmente essas duas constantes, permitindo que o modelo preveja a existência de arestas com base exclusivamente na composição do lote, e não em características aprendidas.

B. Solução Proposta: Mini-Lotagem Corrigida de Viés

Para forçar o modelo a aprender características robustas (ou seja, características relevantes para a classe do nó) em vez de heurísticas de lote, os autores propõem um novo regime de treinamento:

• Composição de Classes Randomizada: Em vez de fixar a razão de arestas positivas para negativas, a fração de arestas positivas ($p$) em cada mini-lote é amostrada aleatoriamente de uma distribuição uniforme: $p \sim U\{1, \dots, K-1\}$.
• Efeito: Essa randomização garante que as estatísticas do lote (média e variância) calculadas pela camada de BN variem de forma imprevisível entre os lotes. Consequentemente, uma regra de decisão baseada apenas na composição do lote torna-se instável e ineficaz, forçando a rede a depender das características reais das arestas e dos embeddings dos nós para minimizar a perda.

C. Métricas de Avaliação

Para verificar se os modelos estão aprendendo características de classe de nós, os autores introduzem métodos de avaliação específicos:

1. Razão de Traço (TR): Usada para medir a separabilidade dos embeddings de arestas com base no rótulo de classe do nó de origem. Um TR mais alto indica um melhor alinhamento entre as representações de arestas e as classes dos nós.
2. Agregação de Embeddings de Nós: Como os preditores de links geram embeddings de arestas ($Z_2$), os autores agregam esses embeddings de volta aos nós, calculando a média dos embeddings de todas as arestas incidentes para um determinado nó ($x'_v$).
3. Agrupamento e NMI: Eles realizam agrupamento $k$-means nesses embeddings de nós agregados e medem a Informação Mútua Normalizada (NMI) contra os rótulos reais dos nós. Um NMI alto indica que o preditor de links aprendeu representações úteis para a classificação de nós.

3. Contribuições Principais

1. Identificação de um Viés Oculto: O artigo revela que modelos padrão de predição de links frequentemente exploram a razão fixa de positivos/negativos em mini-lotes via Normalização em Lote, levando a um aprendizado de "atalho" que contorna a extração complexa de características.
2. Prova Teórica: Fornece uma derivação matemática mostrando como as camadas de BN colapsam as ativações em constantes dependentes de classe quando a composição do lote é fixa.
3. Esquema de Treinamento Corrigido de Viés: Introduz uma modificação simples e agnóstica à arquitetura (randomização da composição de classes do mini-lote) que elimina essa heurística.
4. Validação Empírica: Demonstra que, embora essa correção possa reduzir ligeiramente a precisão bruta de predição de links (Hits@K), ela melhora significativamente o alinhamento das representações aprendidas com características de classe de nós, provando que os modelos estavam anteriormente "trapaceando".

4. Resultados Experimentais

Os autores avaliaram seis modelos populares (BUDDY, ELPH, GCN, NCN, NEOGNN, GraphSAGE) em múltiplos conjuntos de dados (Cora, Citeseer, Pubmed, CS, Computers, Photo, ogbl-collab, ogbl-ppa).

• Desempenho de Predição de Links (Hits@100):

  • Como esperado, remover o viés geralmente causou uma diminuição nas pontuações Hits@100.
  • Exemplo: No conjunto de dados ogbl-collab, o GCN caiu de 42,0 para 16,3. Em Computers, o BUDDY caiu de 56,0 para 42,5.
  • Interpretação: A queda confirma que o alto desempenho original era parcialmente devido à heurística de lote explorável.

• Alinhamento de Representação (Razão de Traço):

  • Em quase todos os modelos e conjuntos de dados, a Razão de Traço aumentou significativamente sob o esquema corrigido de viés.
  • Exemplo: Em Cora, o TR do GCN aumentou de 0,039 para 0,165. Em CS, o TR do BUDDY saltou de 0,225 para 0,728.
  • Interpretação: Os modelos agora estão aprendendo representações de arestas que são altamente separáveis por classe de nó.

• Alinhamento de Classificação de Nós (NMI):

  • Quando os embeddings de arestas foram agregados aos nós, as pontuações de NMI melhoraram dramaticamente com a correção de viés.
  • Exemplo: Em CS, o NMI do BUDDY aumentou de 0,218 para 0,621. Em Cora, o NMI do ELPH subiu de 0,193 para 0,414.
  • Interpretação: Isso confirma que preditores de links, quando treinados corretamente, podem aprender características preditivas de classes de nós, validando a intuição inicial que estava anteriormente mascarada pelo viés.

• Estudo de Ablação:

  • Quando as camadas de Normalização em Lote foram removidas completamente, a lacuna de desempenho entre o treinamento "Original" e o "Corrigido de Viés" desapareceu (TR e Hits@K permaneceram semelhantes). Isso confirma que a Normalização em Lote é o habilitador do viés.

5. Significado e Implicações

• Reavaliação do SOTA: O artigo sugere que os benchmarks atuais de estado da arte em predição de links podem estar superestimando a capacidade das GNNs de aprender representações de grafos generalizadas. Muitos modelos podem estar alcançando altas pontuações explorando artefatos de treinamento em vez de aprender propriedades estruturais.
• Transferibilidade de Tarefas: As descobertas apoiam a hipótese de que predição de links e classificação de nós compartilham um espaço de representação subjacente comum, mas isso só é acessível se o regime de treinamento impedir o aprendizado de atalhos.
• Recomendação Prática: Os autores recomendam adotar a mini-lotagem corrigida de viés (randomização das razões positivos/negativos) como uma prática padrão. Isso garante que os modelos aprendam características que são robustas, transferíveis entre tarefas e verdadeiramente reflexivas das propriedades estruturais e semânticas do grafo, mesmo que isso venha a um custo ligeiro para as métricas brutas de predição de links.