Fractal Graph Contrastive Learning

Resumo Técnico: Aprendizado Contrastivo de Grafos Fractais (FractalGCL)

Enunciação do Problema
O Aprendizado Contrastivo de Grafos (GCL) depende da geração de ampliações de grafos semanticamente consistentes para criar pares positivos para aprendizado auto-supervisionado. No entanto, os métodos existentes utilizam predominantemente perturbações locais (por exemplo, exclusão aleatória de nós/arestas, mascaramento de atributos) ou restrições topológicas fixas. Os autores argumentam que essas abordagens oferecem controle limitado sobre a consistência estrutural global, frequentemente falhando em garantir que as visualizações ampliadas retenham as propriedades globais intrínsecas do grafo original. Essa falta de um mecanismo principiado para impor similaridade global cria um gargalo no aprendizado de representações de grafos de alta qualidade, particularmente para grafos que exibem estruturas complexas e multi-escala.

Metodologia
O artigo propõe o FractalGCL, um framework fundamentado na geometria fractal para abordar o desafio da consistência global. A metodologia consiste em três componentes principais:

1. Ampliação Baseada em Renormalização:
   Em vez de perturbações locais aleatórias, o FractalGCL gera visualizações positivas via renormalização de grafos. Este processo envolve particionar os vértices do grafo em "caixas" (supervértices) disjuntas e conectadas com base em uma restrição de raio. Cada caixa é colapsada em um único supervértice, e as arestas são formadas entre os supervértices se uma aresta existia entre seus vértices constituintes no grafo original.

   • Base Teórica: Os autores invocam o Teorema 3.2, afirmando que a renormalização limitada preserva a dimensão de contagem de caixas (dimensão fractal) no limite de diâmetro infinito. Isso garante que a visualização ampliada $R(G)$ mantenha similaridade estrutural com o grafo original $G$ em uma escala grosseira.
   • Construção de Entrada: A visualização ampliada alimentada ao codificador é a união disjunta $A(G) = G \sqcup R(G)$, permitindo que o modelo processe simultaneamente estruturas locais de alta granularidade e estruturas renormalizadas de baixa granularidade.

2. Função de Perda Contrastiva Consciente da Dimensão Fractal:
   O framework introduz uma função de perda novel que penaliza explicitamente discrepâncias na dimensão de contagem de caixas em escala finita entre o grafo âncora e sua visualização ampliada.

   • A perda modifica os logits contrastivos padrão adicionando um termo proporcional a $|\hat{d}_{B}(G_i) - \hat{d}_{B}(R(G_i))|$, onde $\hat{d}_{B}$ é a dimensão de caixa estimada.
   • Pares Positivos: A pontuação de similaridade é penalizada se a visualização renormalizada desviar significativamente em dimensão da âncora, desencorajando ampliações não confiáveis.
   • Pares Negativos: A força de repulsão entre pares negativos é reponderada com base na discrepância de contagem de caixas entre a âncora e a visualização renormalizada da amostra negativa. Grafos com geometrias em escala finita significativamente diferentes recebem repulsão mais forte.

3. Surrogado Gaussiano para Eficiência:
   Calcular a dimensão de contagem de caixas para cada grafo renormalizado é computacionalmente caro ($O(|V|^3)$ em cenários de pior caso). Para tornar o método prático, os autores derivam um surrogado Gaussiano controlado por diâmetro.

   • Eles provam (Proposição 3.5) que a discrepância de renormalização $\Delta(G) = \hat{d}_{B}(G) - \hat{d}_{B}(R(G))$ pode ser aproximada por uma distribuição Gaussiana $N(0, \sigma^2)$ controlada pelo diâmetro do grafo e pela incerteza de regressão.
   • Este surrogado evita regressões repetidas de contagem de caixas durante o treinamento, reduzindo o tempo de execução em aproximadamente 61%.
   • Fallback Seguro: Um mecanismo de gate desativa a correção fractal (definindo o peso $\alpha=0$) se o diâmetro do grafo for pequeno ($\le 9$) ou se o ajuste de contagem de caixas for fraco ($R^2 < 0.9$), garantindo que o modelo retorne ao comportamento padrão de GCL quando as suposições fractais não se sustentarem.

Principais Contribuições

• Geometria Fractal em GCL: O artigo está entre os primeiros a injetar uma visão fractal matematicamente rigorosa no aprendizado de representação de grafos, demonstrando que propriedades estruturais globais e livres de escala são um sinal potente para aprendizado contrastivo.
• Arquitetura Orientada por Teoria: A integração de ampliações baseadas em renormalização e uma função de perda consciente de dimensão fornece uma alternativa principial às perturbações locais heurísticas.
• Implementação Eficiente: A derivação do surrogado Gaussiano transforma um método teoricamente sólido, mas computacionalmente proibitivo, em uma ferramenta prática, alcançando uma aceleração significativa sem sacrificar o desempenho.
• Mecanismo de Robustez: O fallback ao nível do objetivo garante que o método não degrade o desempenho em grafos que carecem de escalamento fractal claro ou são muito pequenos para estimativa confiável de dimensão.

Resultados Experimentais
Os autores avaliam o FractalGCL em três configurações distintas:

1. Pré-treinamento Congelado (MalNet-Tiny): O FractalGCL serve como uma ferramenta eficaz de pré-treinamento congelado. Quando combinado com classificadores a jusante (por exemplo, SAGE, JK-SAGE), melhora a precisão em relação às linhas de base, com o maior ganho sendo 1,20 pontos percentuais no modelo SAGE-pequeno.
2. Benchmarks Padrão (TUDataset): Em cinco conjuntos de dados (NCI1, MUTAG, PROTEINS, D&D, REDDIT-M5K), o FractalGCL alcança a maior precisão média (76,93%), superando o próximo melhor método (GradGCL) por 1,29 pontos percentuais. Ele ocupa o primeiro lugar em todos os cinco conjuntos de dados individuais. A margem de desempenho é notavelmente maior no conjunto de dados D&D, que exibe fortes características fractais.
3. Aplicação do Mundo Real (Tráfego Urbano): Avaliado em tarefas de classificação de segurança no tráfego usando redes rodoviárias de Chicago, São Francisco e Nova York, o FractalGCL alcança uma precisão média de 61,76%, superando a próxima melhor linha de base por 4,51 pontos percentuais.

Significado e Alegações
O artigo alega que o FractalGCL demonstra que a consistência estrutural global, formalizada através da geometria fractal, é um fator crítico, mas frequentemente negligenciado, no aprendizado de representação de grafos. Ao ir além das perturbações locais para impor auto-similaridade multi-escala, o método melhora a qualidade dos embeddings aprendidos.

Os autores observam modestamente que a eficácia do método depende da presença de uma estrutura fractal significativa em escala finita. Eles reconhecem que, para grafos com escalamento fractal fraco ou diâmetros muito pequenos, a correção fractal pode ser menos informativa, razão pela qual o mecanismo de fallback proposto é essencial. O trabalho posiciona a geometria fractal não apenas como uma curiosidade teórica, mas como um prior prático e escalável para o design de objetivos robustos de aprendizado contrastivo de grafos.