Resumo Técnico: Modelo Fundamental de Grafos Centrados na Estrutura via Bases Geométricas

1. Declaração do Problema

Modelos Fundamentais de Grafos (GFMs) visam aprender representações transferíveis entre diversos domínios de grafos. No entanto, as abordagens existentes enfrentam duas limitações primárias:

1. Heterogeneidade Estrutural: Grafos variam significativamente em topologia, escala e métricas induzidas entre domínios. Diferentemente de texto ou imagens, grafos são objetos relacionais definidos apenas até isomorfismo, carecendo de uma referência geométrica compartilhada.
2. Incompatibilidade de Características: Os espaços de características dos nós frequentemente diferem em dimensionalidade e semântica entre conjuntos de dados. Os GFMs atuais tipicamente impõem dimensões fixas de características por meio de projeções específicas de conjunto de dados, preenchimento (padding) ou adaptadores. Embora isso alinhe os espaços de características, falha em alinhar as estruturas subjacentes dos grafos, levando a representações que refletem pobremente a similaridade intrínseca do grafo e limitando a transferência entre domínios.

Alternativas existentes, como a tokenização de grafos, impõem ordenações artificiais em estruturas inerentemente desordenadas, violando a invariância à permutação e falhando em capturar a geometria intrínseca do grafo.

2. Metodologia: SCGFM

Os autores propõem Modelos Fundamentais de Grafos Centrados na Estrutura (SCGFM), que tratam a topologia do grafo como a principal fonte de conhecimento transferível. A ideia central é modelar grafos como espaços de medida métrica (mm-espaços) e aprender um sistema de coordenadas estrutural compartilhado.

2.1. Perspectiva Geométrica

O SCGFM assume que grafos do mundo real residem dentro de um subconjunto totalmente limitado do espaço de mm-espaços. Com base no teorema de compacidade de Gromov, qualquer grafo pode ser aproximado por suas distâncias a um conjunto finito de padrões geométricos canônicos (bases).

2.2. Componentes Principais

O framework consiste em duas etapas: Pré-treinamento de Bases Geométricas e Projeção Downstream.

A. Bases Geométricas Aprendíveis

O SCGFM aprende um conjunto finito de $K$ bases geométricas $\{B_k\}_{k=1}^K$. Cada base $B_k$ é definida como um mm-espaço finito $( [M], d_k, \mu_k )$:

• Métrica ($d_k$): Representada por uma matriz simétrica e oca aprendível $B_k \in [0, 1]^{M \times M}$, parametrizando os pesos das arestas de uma estrutura de grafo canônica com $M$ nós.
• Medida ($\mu_k$): Fixada em uma distribuição uniforme para garantir acoplamentos bem definidos.

Essas bases coletivamente formam um sistema de coordenadas estrutural compartilhado.

B. Alinhamento Estrutural via Gromov–Wasserstein (GW)

Grafos de entrada $G$ são alinhados às bases utilizando distâncias de Gromov–Wasserstein (GW). Para garantir escalabilidade, o método emprega Gromov–Wasserstein Fatiado (SGW), que reduz a complexidade computacional de $O(N^3)$ para quase linear $O(N \log N)$ projetando estruturas métricas em fatias unidimensionais.

Para um grafo $G$, a discrepância estrutural para cada base $B_k$ é calculada como $\delta_k = d_{GW}(G, B_k)$. Essas distâncias são convertidas em um vetor de coordenadas estruturais $w$ (pesos) via uma função softmax:
$$w_k = \frac{\exp(-\delta_k / \tau)}{\sum_j \exp(-\delta_j / \tau)}$$
Este vetor $w$ serve como a representação do grafo no espaço geométrico compartilhado.

C. Re-codificação de Características

Para abordar a incompatibilidade de características sem assumir dimensões fixas, o SCGFM emprega um mecanismo de re-codificação de características consciente da estrutura:

1. Plano de Transporte: O plano de transporte ótimo $T_{ik}$ obtido durante o cálculo de GW mapeia nós do grafo de entrada para a base geométrica.
2. Projeção: As características dos nós são agregadas e projetadas sobre as bases usando $T_{ik}$, resultando em uma matriz de características unificada $H(G)$.
3. Unificação: Este processo unifica representações de nós ancoradas à estrutura, permanecendo agnóstico à dimensionalidade original das características.

D. Objetivos de Treinamento

O objetivo de pré-treinamento minimiza uma soma ponderada de três perdas:

1. Perda de Reconstrução GW ($L_{gw}$): Minimiza a distância entre o grafo de entrada e um substituto linear do baricentro de GW (uma combinação ponderada de bases).
2. Perda de Reconstrução Estatística ($L_{rec}$): Um decodificador $f(\cdot)$ reconstrói estatísticas de nível de grafo (histograma de grau, agrupamento, motivos) a partir de $w$ para garantir fidelidade estrutural.
3. Regularização de Diversidade ($L_{div}$): Impõe separação par a par entre as bases para prevenir colapso e garantir que elas abranjam o espaço estrutural.

2.3. Representação Downstream

O embedding final do grafo $z(G)$ é uma concatenação de:

1. Coordenadas estruturais $w$.
2. Estatísticas reconstruídas $f(w)$.
3. Características projetadas $vec(H(G))$.

Este embedding unificado é usado para tarefas downstream (classificação de nós ou grafos) via um encoder congelado e um classificador leve (por exemplo, Rede Prototípica).

3. Contribuições Principais

1. GFM Centrada na Estrutura: Um framework inovador que permite transferência entre conjuntos de dados de grafos heterogêneos sem arquiteturas específicas de conjunto de dados ou pré-processamento de características, dependendo em vez disso de um sistema de coordenadas geométrico compartilhado.
2. Bases Geométricas e Espaço Latente: A introdução de bases geométricas aprendíveis que induzem um espaço latente alinhado geometricamente. Os autores demonstram que distâncias neste espaço correlacionam-se fortemente com a geometria intrínseca de grafos GW.
3. Flexibilidade de Características: Um mecanismo para unificar características de nós heterogêneas através de alinhamento estrutural, eliminando a necessidade de dimensões fixas de características ou pré-processamento específico de domínio.
4. Garantias Teóricas: Prova de que as coordenadas estruturais aprendidas e as estatísticas reconstruídas são Lipschitz contínuas em relação à distância GW, garantindo estabilidade.

4. Resultados Experimentais

Os autores avaliaram o SCGFM em 12 conjuntos de dados através de 5 domínios (Moléculas, Redes Sociais, Acadêmico, E-commerce, Sintético) para classificação de nível de grafo e de nó sob um protocolo de aprendizado com poucos exemplos (5-shot).

• Desempenho: O SCGFM superou consistentemente bases fortes, incluindo GNNs vanilla (GCN, GIN, GAT), métodos auto-supervisionados (GraphCL, GraphMAE) e GFMs existentes (GCOPE, RiemannGFM, GIT).
  • Classificação de Grafos: Alcançou precisão superior dentro do domínio e entre domínios, particularmente no conjunto de dados COLORS-3, onde as bases degradaram-se para níveis próximos ao acaso devido a grandes deslocamentos estruturais.
  • Classificação de Nós: Demonstrou comportamento quase independente da fonte. Por exemplo, no conjunto de dados Reddit, o desempenho permaneceu alto (~84%) independentemente do domínio de pré-treinamento, atribuído à capacidade do modelo de projetar características semânticas de alta dimensionalidade em um espaço onde a separabilidade linear é garantida (Teorema de Cover).
• Escalabilidade: O SCGFM escalou suavemente para grafos com 5 milhões de nós, mantendo o menor consumo de pico de memória (~12 GB) entre todos os métodos. Métodos concorrentes (GAT, GIT) encontraram erros de falta de memória em escalas menores.
• Estudos de Ablação:
  • Em conjuntos de dados dominados por características (por exemplo, Cora), as características projetadas $vec(H)$ foram críticas; removê-las causou uma queda catastrófica no desempenho.
  • Em conjuntos de dados dominados por estrutura (por exemplo, PROTEINS, MUTAG), as coordenadas geométricas $w$ foram os principais impulsionadores do desempenho.
  • Tanto as perdas de reconstrução quanto de diversidade foram essenciais para treinamento estável em todas as modalidades.
• Interpretabilidade: Visualizações mostraram que as bases aprendidas se especializaram em motivos geométricos distintos (por exemplo, clusters densos, padrões de anel e cauda) e evoluíram de padrões não estruturados para primitivos topológicos nítidos durante o treinamento.
• Isometria: As distâncias euclidianas latentes mostraram uma forte correlação linear ($\rho \approx 0,70$) com as verdadeiras distâncias GW, confirmando que o embedding preserva a geometria intrínseca do grafo.

5. Significado e Alegações

O artigo alega que o SCGFM oferece uma alternativa principiante à tokenização de grafos e GFMs dependentes de domínio. Ao modelar grafos como espaços de medida métrica e utilizar distâncias GW, o SCGFM desacopla com sucesso a topologia da semântica.

Os autores enfatizam que sua abordagem:

• Generaliza robustamente entre domínios dispares sem modificações arquiteturais.
• Fornece estabilidade teórica através de garantias de continuidade Lipschitz.
• Escala eficientemente para grafos massivos, superando os gargalos computacionais do cálculo exato de GW via aproximação SGW.
• Adapta-se à modalidade de dados, aproveitando efetivamente sinais estruturais ou semânticos dependendo das características do conjunto de dados.

O trabalho posiciona-se como um passo em direção a um paradigma unificado e centrado na estrutura para modelos fundamentais de grafos que supera as limitações das abordagens centradas em características e baseadas em tokens.