Resumen Técnico: Modelo Fundacional de Grafos Centrado en la Estructura mediante Bases Geométricas

1. Declaración del Problema

Los Modelos Fundacionales de Grafos (GFMs) buscan aprender representaciones transferibles a través de diversos dominios de grafos. Sin embargo, los enfoques existentes enfrentan dos limitaciones principales:

1. Heterogeneidad Estructural: Los grafos varían significativamente en topología, escala y métricas inducidas entre dominios. A diferencia del texto o las imágenes, los grafos son objetos relacionales definidos únicamente hasta isomorfismo, careciendo de una referencia geométrica compartida.
2. Incompatibilidad de Características: Los espacios de características de los nodos a menudo difieren en dimensionalidad y semántica entre conjuntos de datos. Los GFMs actuales suelen imponer dimensiones de características fijas mediante proyecciones específicas del conjunto de datos, relleno o adaptadores. Si bien esto alinea los espacios de características, falla en alinear las estructuras subyacentes del grafo, lo que conduce a representaciones que reflejan pobremente la similitud intrínseca del grafo y limita la transferencia entre dominios.

Las alternativas existentes, como la tokenización de grafos, imponen ordenamientos artificiales sobre estructuras inherentemente desordenadas, violando la invariancia a permutaciones y fallando en capturar la geometría intrínseca del grafo.

2. Metodología: SCGFM

Los autores proponen Modelos Fundacionales de Grafos Centrados en la Estructura (SCGFM), que tratan la topología del grafo como la fuente principal de conocimiento transferible. La idea central es modelar los grafos como espacios de medida métrica (mm-espacios) y aprender un sistema de coordenadas estructural compartido.

2.1. Perspectiva Geométrica

SCGFM asume que los grafos del mundo real se encuentran dentro de un subconjunto totalmente acotado del espacio de mm-espacios. Basándose en el teorema de compacidad de Gromov, cualquier grafo puede aproximarse mediante sus distancias a un conjunto finito de patrones geométricos canónicos (bases).

2.2. Componentes Principales

El marco consta de dos etapas: Pre-entrenamiento de Bases Geométricas y Proyección para Tareas Específicas.

A. Bases Geométricas Aprendizables

SCGFM aprende un conjunto finito de $K$ bases geométricas $\{B_k\}_{k=1}^K$. Cada base $B_k$ se define como un mm-espacio finito $( [M], d_k, \mu_k )$:

• Métrica ($d_k$): Representada por una matriz simétrica y hueca aprendible $B_k \in [0, 1]^{M \times M}$, que parametriza los pesos de las aristas de una estructura de grafo canónica con $M$ nodos.
• Medida ($\mu_k$): Fijada a una distribución uniforme para asegurar acoplamientos bien definidos.

Estas bases forman colectivamente un sistema de coordenadas estructural compartido.

B. Alineación Estructural mediante Gromov–Wasserstein (GW)

Los grafos de entrada $G$ se alinean con las bases utilizando distancias de Gromov–Wasserstein (GW). Para garantizar la escalabilidad, el método emplea Gromov–Wasserstein Sliced (SGW), que reduce la complejidad computacional de $O(N^3)$ a cuasi-lineal $O(N \log N)$ proyectando las estructuras métricas en rebanadas unidimensionales.

Para un grafo $G$, la discrepancia estructural con cada base $B_k$ se calcula como $\delta_k = d_{GW}(G, B_k)$. Estas distancias se convierten en un vector de coordenadas estructurales $w$ (pesos) mediante una función softmax:
$$w_k = \frac{\exp(-\delta_k / \tau)}{\sum_j \exp(-\delta_j / \tau)}$$
Este vector $w$ sirve como la representación del grafo en el espacio geométrico compartido.

C. Re-codificación de Características

Para abordar la incompatibilidad de características sin asumir dimensiones fijas, SCGFM emplea un mecanismo de re-codificación de características consciente de la estructura:

1. Plan de Transporte: El plan de transporte óptimo $T_{ik}$ obtenido durante el cálculo de GW mapea los nodos del grafo de entrada a la base geométrica.
2. Proyección: Las características de los nodos se agregan y proyectan sobre las bases utilizando $T_{ik}$, resultando en una matriz de características unificada $H(G)$.
3. Unificación: Este proceso unifica las representaciones de nodos ancladas a la estructura, permaneciendo agnóstico a la dimensionalidad original de las características.

D. Objetivos de Entrenamiento

El objetivo de pre-entrenamiento minimiza una suma ponderada de tres pérdidas:

1. Pérdida de Reconstrucción GW ($L_{gw}$): Minimiza la distancia entre el grafo de entrada y un sustituto lineal del baricentro de GW (una combinación ponderada de bases).
2. Pérdida de Reconstrucción Estadística ($L_{rec}$): Un decodificador $f(\cdot)$ reconstruye estadísticas a nivel de grafo (histograma de grados, agrupamiento, motivos) a partir de $w$ para asegurar la fidelidad estructural.
3. Regularización de Diversidad ($L_{div}$): Impone una separación pairwise entre las bases para evitar el colapso y asegurar que abarquen el espacio estructural.

2.3. Representación para Tareas Específicas

La incrustación final del grafo $z(G)$ es una concatenación de:

1. Coordenadas estructurales $w$.
2. Estadísticas reconstruidas $f(w)$.
3. Características proyectadas $vec(H(G))$.

Esta incrustación unificada se utiliza para tareas posteriores (clasificación de nodos o grafos) mediante un codificador congelado y un clasificador ligero (por ejemplo, Red Prototípica).

3. Contribuciones Clave

1. GFM Centrado en la Estructura: Un marco novedoso que habilita la transferencia entre conjuntos de datos de grafos heterogéneos sin arquitecturas específicas del conjunto de datos ni preprocesamiento de características, confiando en su lugar en un sistema de coordenadas geométrico compartido.
2. Bases Geométricas y Espacio Latente: La introducción de bases geométricas aprendibles que inducen un espacio latente alineado geométricamente. Los autores demuestran que las distancias en este espacio se correlacionan fuertemente con la geometría intrínseca de grafos GW.
3. Flexibilidad de Características: Un mecanismo para unificar características de nodos heterogéneas mediante alineación estructural, eliminando la necesidad de dimensiones de características fijas o preprocesamiento específico del dominio.
4. Garantías Teóricas: Demostración de que las coordenadas estructurales aprendidas y las estadísticas reconstruidas son continuas de Lipschitz con respecto a la distancia GW, asegurando estabilidad.

4. Resultados Experimentales

Los autores evaluaron SCGFM en 12 conjuntos de datos a través de 5 dominios (Moléculas, Redes Sociales, Académico, E-commerce, Sintético) para clasificación a nivel de grafo y a nivel de nodo bajo un protocolo de aprendizaje con pocos ejemplos (5-shot).

• Rendimiento: SCGFM superó consistentemente a líneas base sólidas, incluyendo GNNs vanillas (GCN, GIN, GAT), métodos auto-supervisados (GraphCL, GraphMAE) y GFMs existentes (GCOPE, RiemannGFM, GIT).
  • Clasificación de Grafos: Logró una precisión superior tanto dentro del dominio como entre dominios, particularmente en el conjunto de datos COLORS-3, donde las líneas base se degradaron a niveles cercanos al azar debido a grandes cambios estructurales.
  • Clasificación de Nodos: Demostró un comportamiento casi independiente del origen. Por ejemplo, en el conjunto de datos Reddit, el rendimiento se mantuvo alto (~84%) independientemente del dominio de pre-entrenamiento, atribuido a la capacidad del modelo para proyectar características semánticas de alta dimensión en un espacio donde la separabilidad lineal está garantizada (Teorema de Cover).
• Escalabilidad: SCGFM escaló suavemente a grafos con 5 millones de nodos, manteniendo el consumo máximo de memoria más bajo (~12 GB) entre todos los métodos. Los métodos competidores (GAT, GIT) encontraron errores de falta de memoria a escalas inferiores.
• Estudios de Ablación:
  • En conjuntos de datos dominados por características (por ejemplo, Cora), las características proyectadas $vec(H)$ fueron críticas; eliminarlas causó una caída catastrófica en el rendimiento.
  • En conjuntos de datos dominados por estructura (por ejemplo, PROTEINS, MUTAG), las coordenadas geométricas $w$ fueron los impulsores principales del rendimiento.
  • Tanto las pérdidas de reconstrucción como de diversidad fueron esenciales para un entrenamiento estable en todas las modalidades.
• Interpretabilidad: Las visualizaciones mostraron que las bases aprendidas se especializaron en motivos geométricos distintos (por ejemplo, clusters densos, patrones de anillo y cola) y evolucionaron desde patrones no estructurados hasta primitivos topológicos definidos durante el entrenamiento.
• Isometría: Las distancias euclidianas latentes mostraron una fuerte correlación lineal ($\rho \approx 0.70$) con las distancias GW reales, confirmando que la incrustación preserva la geometría intrínseca del grafo.

5. Significado y Afirmaciones

El artículo afirma que SCGFM ofrece una alternativa fundamentada a la tokenización de grafos y a los GFMs dependientes del dominio. Al modelar los grafos como espacios de medida métrica y utilizar distancias GW, SCGFM desacopla exitosamente la topología de la semántica.

Los autores enfatizan que su enfoque:

• Generaliza robustamente a través de dominios dispares sin modificaciones arquitectónicas.
• Proporciona estabilidad teórica mediante garantías de continuidad de Lipschitz.
• Escala eficientemente a grafos masivos, superando los cuellos de botella computacionales del cálculo exacto de GW mediante la aproximación SGW.
• Se adapta a la modalidad de datos, aprovechando eficazmente señales estructurales o semánticas según las características del conjunto de datos.

El trabajo se posiciona como un paso hacia un paradigma unificado y centrado en la estructura para modelos fundacionales de grafos que supera las limitaciones de los enfoques centrados en características y basados en tokens.