Resumo Técnico: Contrastive FUSE

Declaração do Problema

O artigo aborda o desafio de aprender representações significativas de nós em grafos onde as características explícitas dos nós estão indisponíveis, são pouco confiáveis ou não transferíveis (grafos sem características ou esparsos em características). Diferentemente dos métodos padrão de incorporação de grafos não supervisionados que dependem exclusivamente da estrutura do grafo, ou dos métodos de aprendizado contrastivo auto-supervisionado que dependem de aumentações de dados, este trabalho foca em um cenário onde a supervisão está disponível apenas na forma de restrições parciais entre pares. Essas restrições indicam se dois nós devem ser similares (ligação obrigatória) ou dissimilares (ligação proibida), um cenário comum em domínios como biologia computacional (por exemplo, previsão de letalidade sintética), sistemas de recomendação (feedback implícito) e redes sensíveis à privacidade onde os atributos dos nós são inacessíveis.

O objetivo é desenvolver um framework rápido e escalável que aprenda incorporações discriminativas de nós otimizando conjuntamente para:

1. Coerência Estrutural: Preservar a estrutura global de comunidades do grafo.
2. Consistência entre Pares: Adherir às restrições sinalizadas entre pares fornecidas (atraindo pares similares, repelindo pares dissimilares).

Metodologia: Contrastive FUSE

Os autores propõem o Contrastive FUSE, um framework unificado que integra aprendizado estrutural baseado em modularidade com supervisão contrastiva através de uma formulação espectral.

1. Função Objetivo

O objetivo central $J(S)$ combina um termo estrutural e um termo contrastivo:
$$J(S) = \text{Tr}(S^\top \tilde{B}S) - \lambda \text{Tr}(S^\top L_c S)$$

• Termo Estrutural (Modularidade): O primeiro termo maximiza a modularidade, incentivando nós dentro da mesma comunidade a terem incorporações similares. Os autores utilizam uma matriz de modularidade modificada $\tilde{B} = A - \frac{d\mathbf{1}^\top}{2m}$, onde $A$ é a matriz de adjacência, $d$ é o vetor de graus e $m$ é o número total de arestas.
• Termo Contrastivo: O segundo termo utiliza um Laplaciano contrastivo sinalizado e normalizado ($L_c$) construído a partir da matriz de supervisão entre pares $Y$ (onde $Y_{ij} \in \{+1, -1, 0\}$). Este termo atua como um regularizador que aproxima pares positivos e afasta pares negativos no espaço de incorporação, normalizado pelo grau contrastivo de cada nó para evitar a dominância de nós altamente restritos.

2. Otimização Eficiente via Aproximação de Gradiente

Uma inovação chave é o tratamento do gradiente de modularidade. O gradiente exato do objetivo de modularidade envolve um termo de correção grau-grau ($d(d^\top S)$), que é computacionalmente caro e numericamente instável para grafos grandes e densos.

• Aproximação: Os autores propõem uma aproximação leve substituindo a agregação de graus ponderados $d^\top S$ pela soma global não ponderada $\mathbf{1}^\top S$.
• Justificativa Teórica: O artigo prova (Teorema 2) que, sob suposições moderadas sobre a distribuição da incorporação e a estrutura de graus do grafo, a direção de subida do gradiente aproximado proposto permanece estreitamente alinhada com o gradiente exato (similaridade de cosseno limitada). Isso permite economias computacionais significativas enquanto preserva o comportamento de busca de estrutura da modularidade.

3. Algoritmo de Otimização

O framework emprega ascensão de gradiente projetada:

1. Calcular o gradiente estrutural ($G_{mod} = \tilde{B}S$) e o gradiente contrastivo ($G_{con} = -L_c S$).
2. Combinar gradientes: $G = G_{mod} + \lambda G_{con}$.
3. Atualizar incorporações: $\tilde{S} = S + \eta G$.
4. Projeção: Impor restrições de norma unitária via normalização linha a linha ($S_i \leftarrow \tilde{S}_i / \|\tilde{S}_i\|_2$) para evitar soluções de escala triviais.
5. Classificação a Montante: As incorporações aprendidas são usadas como características de entrada para um classificador baseado em GNN (GCN, GAT ou GraphSAGE) seguido por um MLP para prever relações entre pares.

Contribuições Principais

1. Formulação Contrastiva Novel: Introduz um método para aprendizado de representação de nós sob supervisão entre pares que integra diretamente restrições de pares de nós rotulados ao objetivo de incorporação sem exigir características de nós.
2. Laplaciano Contrastivo Sinalizado e Normalizado: Propõe um operador Laplaciano específico que amplia o aprendizado baseado em modularidade ao atrair simultaneamente pares similares e repelir pares dissimilares de forma normalizada.
3. Esquema de Otimização Escalável: Desenvolve uma aproximação computacionalmente eficiente do gradiente de modularidade que reduz significativamente a sobrecarga enquanto mantém o alinhamento teórico com o objetivo exato, permitindo treinamento em grafos com milhões de arestas.

Resultados Experimentais

O método foi avaliado em um conjunto diversificado de benchmarks, incluindo redes de citação (Cora, CiteSeer, PubMed), grafos de compra conjunta (Amazon Photo, WikiCS) e conjuntos de dados OGB em grande escala (ArXiv, Products).

• Desempenho: O Contrastive FUSE alcançou desempenho de classificação de nós a montante competitivo ou superior (Acurácia e Macro-F1) em comparação com baselines de última geração, incluindo métodos não supervisionados (DeepWalk, Node2Vec), métodos contrastivos auto-supervisionados (DGI, GRACE, SGCL) e métodos espectrais (COLES).
• Escalabilidade e Eficiência: O framework demonstrou ganhos substanciais de tempo de execução. Em conjuntos de dados de escala média, foi significativamente mais rápido que baselines contrastivas como GRACE e SGCL. No conjunto de dados OGBN-ArXiv em grande escala, foi aproximadamente 13–14 vezes mais rápido que métodos baseados em passe aleatório (DeepWalk, Node2Vec) enquanto mantinha desempenho competitivo. Várias outras baselines falharam em executar no ArXiv devido a restrições de memória.
• Ablação: Remover o termo contrastivo (definindo $\lambda=0$) resultou em desempenho consistentemente inferior, confirmando a necessidade de supervisão entre pares para aprender representações discriminativas em cenários sem características.

Significado e Alegações

O artigo alega que o Contrastive FUSE efetivamente preenche a lacuna entre detecção de comunidades estruturais e aprendizado supervisionado entre pares. Seu significado principal reside em oferecer uma alternativa rápida e escalável aos métodos existentes de aprendizado contrastivo que tipicamente dependem de codificadores profundos caros, extensas aumentações de dados ou arquiteturas de passagem de mensagens.

Ao acoplar aprendizado estrutural inspirado em modularidade com supervisão contrastiva, o framework permite aprendizado eficiente de incorporações de nós em cenários onde as características dos nós estão ausentes, mas as relações entre pares são conhecidas. Os autores enfatizam que essa abordagem é particularmente valiosa para grafos em evolução ou específicos de contexto onde as incorporações devem ser recomputadas eficientemente, e para domínios como bioinformática e redes sensíveis à privacidade onde o aprendizado baseado apenas em estrutura é uma necessidade. O método alcança um compromisso favorável entre precisão preditiva e eficiência computacional, tornando-o adequado para aplicações reais em grande escala.