Resumen Técnico: Cuando los Modelos de Lenguaje de Grafos Van Más Allá de la Memorización

1. Declaración del Problema

La pregunta central abordada por este trabajo es si los Modelos de Lenguaje de Grafos (GLM), decodificadores autoregresivos entrenados sobre representaciones serializadas de grafos, aprenden fundamentalmente las regularidades estructurales de los grafos o simplemente memorizan los datos de entrenamiento para emitir grafos desde una distribución casi empírica.

Las métricas actuales de fidelidad agregada (por ejemplo, Discrepancia Media Máxima de grado/clustering/orbita, MMD/FID basados en GIN) son insuficientes para resolver esta ambigüedad. Como se formaliza en el Corolario 3, el acuerdo en cualquier estadística de subgrafo acotada es matemáticamente consistente con ambos regímenes: un modelo que aprende patrones estructurales y un modelo que simplemente reproduce los grafos de entrenamiento de manera literal. Sin una referencia calibrada, puntuaciones altas de fidelidad no pueden distinguir entre "aprendizaje estructural" y "recuerdo literal".

2. Metodología

Los autores proponen un protocolo de diagnóstico calibrado diseñado para desentrañar la memorización del alineamiento estructural. Este marco opera sobre dos ejes: un eje de memorización (recuerdo literal vs. generación novel) y un eje de alineamiento (fidelidad distribucional a las estadísticas de subgrafos de entrenamiento).

Componentes Principales

1. Línea Base de Bootstrap a Nivel de Grafo:
   El protocolo introduce una distribución de referencia no aprendida, $\hat{P}^{boot}_G$, construida mediante remuestreo directo del corpus de entrenamiento. Esta línea base representa el alineamiento distribucional alcanzable únicamente mediante memorización. Un modelo se considera que va más allá de la memorización solo si sus estadísticas de subgrafos se desvían significativamente de esta distribución de bootstrap.

2. Minería de Subgrafos Frecuentes (gSpan):
   En lugar de depender de estadísticas agregadas de grafos, la evaluación se centra en patrones de subgrafos. Utilizando el algoritmo gSpan con un umbral de soporte mínimo ($\sigma = 0.1$), los autores enumeran los subgrafos conectados frecuentes tanto en las bases de datos de entrenamiento ($D_{tr}$) como en las generadas ($D_{gen}$).

3. Análisis Estratificado por Frecuencia:
   Para exponer dónde el alineamiento tiene éxito o falla, la distribución de soporte de los patrones de subgrafos se divide en tres estratos:

   • Cabeza: Top 10% (motivos de alta frecuencia).
   • Torso: Medio 80% (patrones moderadamente frecuentes).
   • Cola: Bottom 10% (patrones raros cerca del umbral de soporte).
     Las métricas (correlación de rango de Spearman, divergencia Jensen–Shannon, Masa Faltante) se calculan independientemente para cada estrato.

4. Robustez de la Serialización:
   El análisis se realiza a través de dos métodos de serialización distintos para asegurar que los hallazgos no sean artefactos de una tokenización específica:

   • Código DFS Canónico: Una representación única para grafos isomorfos.
   • Secuencias de Acciones DGMG: Una codificación de proceso de decisión secuencial (ADD_NODE, ADD_EDGE, etc.).

Configuración Experimental

• Modelos: Modelos de lenguaje causal estilo LLaMA (solo decodificador) entrenados desde cero sobre grafos serializados.
• Conjuntos de Datos: Cinco benchmarks de TU (MUTAG, PTC_MR, ENZYMES, PROTEINS, NCI1) y el corpus molecular a gran escala PCQM4Mv2 (~3.75M grafos).
• Líneas Base: Comparación contra líneas base estructurales que incluyen DiGress (difusión), GraphRNN y DGMG-official.

3. Resultados Clave

A. Régimen a Pequeña Escala (Benchmarks TU)

En conjuntos de datos pequeños, los GLM operan en un régimen dominado por la memorización.

• Alta Fidelidad mediante Recuerdo: Los modelos alcanzan altas correlaciones de Spearman ($\rho \approx 0.95\text{--}0.99$) y baja divergencia Jensen–Shannon. Sin embargo, la Calibración de Bootstrap revela que estas métricas caen dentro o por debajo del rango esperado por un simple remuestreo del conjunto de entrenamiento.
• Recuerdo Literal: Las tasas de coincidencia exacta de grafos completos (precisión) son extremadamente altas (por ejemplo, 82.8% en MUTAG, 100% en NCI1).
• Conclusión: En este régimen, la fidelidad agregada es una consecuencia estadística de la memorización, no una evidencia de aprendizaje estructural.

B. Régimen a Gran Escala (PCQM4Mv2)

A escala (3.75M grafos), ocurre una transición de fase.

• Desacoplamiento: La memorización de grafos completos cae drásticamente (Precisión $\approx 31.7\%$), sin embargo, la correlación de Spearman a nivel de subgrafo permanece cerca del techo ($\rho \approx 0.976$).
• Alineamiento Solo-Novel: Cuando se restringe a un subconjunto "solo-novel" (excluyendo grafos memorizados), la correlación de Spearman rastrea la correlación de generación completa dentro de 0.026. Esto confirma que el modelo preserva las regularidades estructurales incluso para grafos no memorizados.
• Conclusión: Los GLM a gran escala internalizan con éxito las regularidades estructurales, actuando como mineros de grafos neuronales implícitos.

C. El Déficit Persistente de Patrones Raros

A través de todas las escalas y serializaciones, se observa una limitación fundamental:

• Éxito en Cabeza/Torso: Los patrones frecuentes y moderadamente frecuentes se reproducen con alta fidelidad ($\rho \ge 0.91$).
• Fallo en Cola: Los patrones raros (estrato Cola) están consistentemente mal cubiertos. La masa faltante para la Cola es un orden de magnitud mayor que para la Cabeza/Torso (por ejemplo, 13.5%–22.0% en conjuntos de datos TU vs. <1% para la Cabeza). La correlación de rango en la Cola es significativamente menor ($\rho \in [0.26, 0.56]$ en TU; $\approx 0.41$ en PCQM4Mv2).
• Robustez: Este déficit persiste independientemente de la capacidad del modelo (escalando de 10.5M a 451M parámetros) y del formato de serialización, lo que indica una brecha estructural en la generación autoregresiva actual para subestructuras raras.

D. Comparaciones con Líneas Base

• DiGress (Difusión): Logra una memorización cercana a cero pero falla en recuperar las distribuciones de subgrafos frecuentes ($\rho \approx 0.25$ en PCQM4Mv2), ocupando un régimen de baja memorización/bajo alineamiento.
• GraphRNN/DGMG-official: Las líneas base ciegas a las etiquetas fallan en recuperar completamente el soporte de subgrafos etiquetados, haciendo que las estadísticas de subgrafos estén indefinidas en la mayoría de los conjuntos de datos.

4. Contribuciones

1. Protocolo de Diagnóstico Calibrado: La introducción de un marco que combina la minería de subgrafos frecuentes con una línea base de bootstrap a nivel de grafo. Esto supera las limitaciones de las métricas agregadas al probar explícitamente si el alineamiento excede lo alcanzable mediante memorización.
2. Evidencia de Aprendizaje Estructural Dependiente de la Escala: La demostración de que los GLM transitan de un régimen dominado por la memorización en conjuntos de datos pequeños a un régimen desacoplado a escala, donde preservan las estadísticas de subgrafos para grafos novedosos.
3. Identificación del Déficit de Patrones Raros: La exposición de un fallo sistemático en aprender la distribución de patrones raros (Cola), que permanece como un cuello de botella incluso a medida que aumenta la capacidad del modelo.

5. Significado y Afirmaciones

El artículo afirma una respuesta condicional a si los GLM van más allá de la memorización: Sí, pero solo a escala suficiente y principalmente para subestructuras frecuentes.

• Cambio Metodológico: El trabajo argumenta que las métricas de fidelidad agregada son poco informativas sin una referencia de memorización. La calibración de bootstrap propuesta es necesaria para interpretar correctamente las puntuaciones altas de correlación.
• Minería Implícita: Los resultados sugieren que el modelado autoregresivo de serializaciones de grafos permite a los LLM internalizar implícitamente las regularidades estructurales (actuando como "mineros de grafos neuronales") sin enumeración explícita de patrones, siempre que el corpus de entrenamiento sea lo suficientemente grande como para evitar un colapso total sobre la distribución empírica.
• Limitaciones: Los autores notan modestamente que, si bien la "Cabeza" de la distribución se recupera bien, la "Cola" permanece como una brecha crítica. El modelo se comporta como un minero parcial, capturando estructuras de soporte dominantes pero fallando en generalizar a subestructuras raras.

El artículo concluye que el alto alineamiento observado en configuraciones a gran escala no es un artefacto de una serialización específica (confirmado mediante DFS y DGMG), sino una propiedad robusta de los modelos de lenguaje de grafos a gran escala, distinta tanto de la memorización pura como de las líneas base generativas no basadas en LLM.