Technical Summary: When Graph Language Models Go Beyond Memorization

1. Problem Statement

The central question addressed by this work is whether Graph Language Models (GLMs)—autoregressive decoders trained on serialized graph representations—fundamentally learn the structural regularities of graphs or merely memorize training data to emit graphs from a near-empirical distribution.

Current aggregate fidelity metrics (e.g., degree/clustering/orbit Maximum Mean Discrepancy, GIN-based MMD/FID) are insufficient to resolve this ambiguity. As formalized in Corollary 3, agreement on any single bounded subgraph statistic is mathematically consistent with both regimes: a model that learns structural patterns and a model that simply reproduces training graphs verbatim. Without a calibrated reference, high fidelity scores cannot distinguish between "structural learning" and "verbatim recall."

2. Methodology

The authors propose a calibrated diagnostic protocol designed to disentangle memorization from structural alignment. This framework operates on two axes: a memorization axis (verbatim recall vs. novel generation) and an alignment axis (distributional fidelity to training subgraph statistics).

Core Components

1. Graph-Level Bootstrap Baseline:
   The protocol introduces a non-learning reference distribution, $\hat{P}^{boot}_G$, constructed by resampling directly from the training corpus. This baseline represents the distributional alignment achievable solely through memorization. A model is considered to go beyond memorization only if its subgraph statistics significantly depart from this bootstrap distribution.

2. Frequent Subgraph Mining (gSpan):
   Instead of relying on aggregate graph statistics, the evaluation focuses on subgraph patterns. Using the gSpan algorithm with a minimum-support threshold ($\sigma = 0.1$), the authors enumerate frequent connected subgraphs in both training ($D_{tr}$) and generated ($D_{gen}$) databases.

3. Frequency-Stratified Analysis:
   To expose where alignment succeeds or fails, the support distribution of subgraph patterns is partitioned into three strata:

   • Head: Top 10% (high-frequency motifs).
   • Torso: Middle 80% (moderately frequent patterns).
   • Tail: Bottom 10% (rare patterns near the support threshold).
     Metrics (Spearman rank correlation, Jensen–Shannon divergence, Missing Mass) are computed independently for each stratum.

4. Serialization Robustness:
   The analysis is conducted across two distinct serialization methods to ensure findings are not artifacts of a specific tokenization:

   • Canonical DFS Code: A unique representation for isomorphic graphs.
   • DGMG Action Sequences: A sequential decision process encoding (ADD_NODE, ADD_EDGE, etc.).

Experimental Setup

• Models: LLaMA-style causal language models (decoder-only) trained from scratch on serialized graphs.
• Datasets: Five TU benchmarks (MUTAG, PTC_MR, ENZYMES, PROTEINS, NCI1) and the large-scale PCQM4Mv2 molecular corpus (~3.75M graphs).
• Baselines: Comparison against structural baselines including DiGress (diffusion), GraphRNN, and DGMG-official.

3. Key Results

A. Small-Scale Regime (TU Benchmarks)

On small datasets, GLMs operate in a memorization-dominated regime.

• High Fidelity via Recall: Models achieve high Spearman correlations ($\rho \approx 0.95\text{--}0.99$) and low Jensen–Shannon divergence. However, the Bootstrap Calibration reveals that these metrics fall within or below the range expected from simple resampling of the training set.
• Verbatim Recall: Whole-graph exact-match rates (precision) are extremely high (e.g., 82.8% on MUTAG, 100% on NCI1).
• Conclusion: In this regime, aggregate fidelity is a statistical consequence of memorization, not evidence of structural learning.

B. Large-Scale Regime (PCQM4Mv2)

At scale (3.75M graphs), a phase transition occurs.

• Decoupling: Whole-graph memorization drops sharply (Precision $\approx 31.7\%$), yet subgraph-level Spearman correlation remains near ceiling ($\rho \approx 0.976$).
• Novelty-Only Alignment: When restricted to a "novel-only" subset (excluding memorized graphs), the Spearman correlation tracks the full-generation correlation within 0.026. This confirms that the model preserves structural regularities even for unmemorized graphs.
• Conclusion: Large-scale GLMs successfully internalize structural regularities, acting as implicit neural graph miners.

C. The Persistent Rare-Pattern Deficit

Across all scales and serializations, a fundamental limitation is observed:

• Head/Torso Success: Frequent and moderately frequent patterns are reproduced with high fidelity ($\rho \ge 0.91$).
• Tail Failure: Rare patterns (Tail stratum) are consistently poorly covered. Missing mass for the Tail is an order of magnitude higher than for Head/Torso (e.g., 13.5%–22.0% on TU datasets vs. <1% for Head). Rank correlation on the Tail is significantly lower ($\rho \in [0.26, 0.56]$ on TU; $\approx 0.41$ on PCQM4Mv2).
• Robustness: This deficit persists regardless of model capacity (scaling from 10.5M to 451M parameters) and serialization format, indicating a structural gap in current autoregressive generation for rare substructures.

D. Baseline Comparisons

• DiGress (Diffusion): Achieves near-zero memorization but fails to recover frequent subgraph distributions ($\rho \approx 0.25$ on PCQM4Mv2), occupying a low-memorization/low-alignment regime.
• GraphRNN/DGMG-official: Label-unaware baselines fail to recover labeled subgraph support entirely, rendering subgraph statistics undefined on most datasets.

4. Contributions

1. Calibrated Diagnostic Protocol: The introduction of a framework combining frequent subgraph mining with a graph-level bootstrap baseline. This overcomes the limitations of aggregate metrics by explicitly testing whether alignment exceeds what is achievable via memorization.
2. Evidence of Scale-Dependent Structural Learning: The demonstration that GLMs transition from a memorization-dominated regime on small datasets to a decoupled regime at scale, where they preserve subgraph statistics for novel graphs.
3. Identification of the Rare-Pattern Deficit: The exposure of a systematic failure to learn the distribution of rare (Tail) patterns, which remains a bottleneck even as model capacity increases.

5. Significance and Claims

The paper claims a conditional answer to whether GLMs go beyond memorization: Yes, but only at sufficient scale and primarily for frequent substructures.

• Methodological Shift: The work argues that aggregate fidelity metrics are uninformative without a memorization reference. The proposed bootstrap calibration is necessary to interpret high correlation scores correctly.
• Implicit Mining: The results suggest that autoregressive modeling of graph serializations allows LLMs to implicitly internalize structural regularities (acting as "neural graph miners") without explicit pattern enumeration, provided the training corpus is large enough to prevent total collapse onto the empirical distribution.
• Limitations: The authors modestly note that while the "Head" of the distribution is well-recovered, the "Tail" remains a critical gap. The model behaves as a partial miner, capturing dominant support structures but failing to generalize to rare substructures.

The paper concludes that the observed high alignment in large-scale settings is not an artifact of a specific serialization (confirmed via DFS and DGMG) but a robust property of large-scale graph language models, distinct from both pure memorization and non-LLM generative baselines.