Riepilogo Tecnico: Quando i Modelli Linguistici su Grafi Vanno Oltre la Memorizzazione

1. Enunciato del Problema

La domanda centrale affrontata da questo lavoro è se i Modelli Linguistici su Grafi (GLM)—decodificatori autoregressivi addestrati su rappresentazioni serializzate di grafi—imparino fondamentalmente le regolarità strutturali dei grafi o semplicemente memorizzino i dati di addestramento per emettere grafi da una distribuzione quasi empirica.

Le attuali metriche aggregate di fedeltà (ad es. discrepanza media massima per grado/clustering/orbita, MMD/FID basati su GIN) sono insufficienti per risolvere questa ambiguità. Come formalizzato nel Corollario 3, l'accordo su qualsiasi singola statistica di sottografo limitata è matematicamente coerente con entrambi i regimi: un modello che apprende pattern strutturali e un modello che semplicemente riproduce i grafi di addestramento alla lettera. Senza un riferimento calibrato, punteggi di alta fedeltà non possono distinguere tra "apprendimento strutturale" e "richiamo alla lettera".

2. Metodologia

Gli autori propongono un protocollo diagnostico calibrato progettato per disgiungere la memorizzazione dall'allineamento strutturale. Questo framework opera su due assi: un asse della memorizzazione (richiamo alla lettera vs. generazione nuova) e un asse dell'allineamento (fedeltà distribuzionale alle statistiche dei sottografi di addestramento).

Componenti Principali

1. Baseline di Bootstrap a Livello di Grafo:
   Il protocollo introduce una distribuzione di riferimento non apprendente, $\hat{P}^{boot}_G$, costruita campionando direttamente dal corpus di addestramento. Questa baseline rappresenta l'allineamento distribuzionale ottenibile esclusivamente attraverso la memorizzazione. Un modello è considerato andare oltre la memorizzazione solo se le sue statistiche di sottografo si discostano significativamente da questa distribuzione di bootstrap.

2. Estrazione di Sottografi Frequenti (gSpan):
   Invece di affidarsi a statistiche aggregate del grafo, la valutazione si concentra sui pattern di sottografi. Utilizzando l'algoritmo gSpan con una soglia di supporto minimo ($\sigma = 0.1$), gli autori enumerano i sottografi connessi frequenti sia nel database di addestramento ($D_{tr}$) che in quello generato ($D_{gen}$).

3. Analisi Stratificata per Frequenza:
   Per esporre dove l'allineamento ha successo o fallisce, la distribuzione del supporto dei pattern di sottografi è suddivisa in tre strati:

   • Testa: Top 10% (motivi ad alta frequenza).
   • Torace: 80% centrale (pattern moderatamente frequenti).
   • Coda: Bottom 10% (pattern rari vicini alla soglia di supporto).
     Le metriche (correlazione di rango di Spearman, divergenza di Jensen–Shannon, Massa Mancante) sono calcolate indipendentemente per ciascuno strato.

4. Robustezza alla Serializzazione:
   L'analisi è condotta su due metodi di serializzazione distinti per garantire che i risultati non siano artefatti di una specifica tokenizzazione:

   • Codice DFS Canonico: Una rappresentazione unica per grafi isomorfi.
   • Sequenze di Azioni DGMG: Una codifica di processo decisionale sequenziale (ADD_NODE, ADD_EDGE, ecc.).

Configurazione Sperimentale

• Modelli: Modelli linguistici causali in stile LLaMA (solo decodificatore) addestrati da zero su grafi serializzati.
• Dataset: Cinque benchmark TU (MUTAG, PTC_MR, ENZYMES, PROTEINS, NCI1) e il corpus molecolare su larga scala PCQM4Mv2 (~3,75M grafi).
• Baseline: Confronto con baseline strutturali tra cui DiGress (diffusione), GraphRNN e DGMG-official.

3. Risultati Chiave

A. Regime su Piccola Scala (Benchmark TU)

Su dataset piccoli, i GLM operano in un regime dominato dalla memorizzazione.

• Alta Fedeltà tramite Richiamo: I modelli raggiungono alte correlazioni di Spearman ($\rho \approx 0,95\text{--}0,99$) e bassa divergenza di Jensen–Shannon. Tuttavia, la Calibrazione Bootstrap rivela che queste metriche rientrano o sono inferiori all'intervallo atteso dal semplice ricampionamento del set di addestramento.
• Richiamo alla Lettera: I tassi di corrispondenza esatta di grafo intero (precisione) sono estremamente elevati (ad es. 82,8% su MUTAG, 100% su NCI1).
• Conclusione: In questo regime, l'alta fedeltà aggregata è una conseguenza statistica della memorizzazione, non una prova di apprendimento strutturale.

B. Regime su Grande Scala (PCQM4Mv2)

Su larga scala (3,75M grafi), si verifica una transizione di fase.

• Disaccoppiamento: La memorizzazione di grafi interi crolla bruscamente (Precisione $\approx 31,7\%$), eppure la correlazione di Spearman a livello di sottografo rimane vicina al limite superiore ($\rho \approx 0,976$).
• Allineamento Solo su Novità: Quando limitato a un sottoinsieme "solo-novità" (escludendo i grafi memorizzati), la correlazione di Spearman traccia la correlazione di generazione completa entro 0,026. Ciò conferma che il modello preserva le regolarità strutturali anche per grafi non memorizzati.
• Conclusione: I GLM su larga scala internalizzano con successo le regolarità strutturali, agendo come estrattori di grafi neurali impliciti.

C. Il Deficit Persistente dei Pattern Rari

Attraverso tutte le scale e serializzazioni, si osserva una limitazione fondamentale:

• Successo Testa/Torace: I pattern frequenti e moderatamente frequenti sono riprodotti con alta fedeltà ($\rho \ge 0,91$).
• Fallimento Coda: I pattern rari (strato Coda) sono sistematicamente poco coperti. La massa mancante per la Coda è di un ordine di grandezza superiore rispetto a Testa/Torace (ad es. 13,5%–22,0% sui dataset TU vs <1% per la Testa). La correlazione di rango sulla Coda è significativamente inferiore ($\rho \in [0,26, 0,56]$ su TU; $\approx 0,41$ su PCQM4Mv2).
• Robustezza: Questo deficit persiste indipendentemente dalla capacità del modello (scalando da 10,5M a 451M parametri) e dal formato di serializzazione, indicando un divario strutturale nella generazione autoregressiva attuale per le sottostrutture rare.

D. Confronti con le Baseline

• DiGress (Diffusione): Raggiunge una memorizzazione quasi nulla ma fallisce nel recuperare le distribuzioni di sottografi frequenti ($\rho \approx 0,25$ su PCQM4Mv2), occupando un regime a bassa memorizzazione/basso allineamento.
• GraphRNN/DGMG-official: Le baseline ignare delle etichette falliscono nel recuperare completamente il supporto dei sottografi etichettati, rendendo le statistiche dei sottografi non definite sulla maggior parte dei dataset.

4. Contributi

1. Protocollo Diagnostico Calibrato: L'introduzione di un framework che combina l'estrazione di sottografi frequenti con una baseline di bootstrap a livello di grafo. Questo supera i limiti delle metriche aggregate testando esplicitamente se l'allineamento supera quanto ottenibile tramite memorizzazione.
2. Prova di Apprendimento Strutturale Dipendente dalla Scala: La dimostrazione che i GLM transitano da un regime dominato dalla memorizzazione su dataset piccoli a un regime disaccoppiato su larga scala, dove preservano le statistiche dei sottografi per grafi nuovi.
3. Identificazione del Deficit dei Pattern Rari: L'esposizione di un fallimento sistematico nell'apprendere la distribuzione dei pattern rari (Coda), che rimane un collo di bottiglia anche all'aumentare della capacità del modello.

5. Significato e Affermazioni

Il documento afferma una risposta condizionale alla questione se i GLM vadano oltre la memorizzazione: Sì, ma solo a scala sufficiente e principalmente per le sottostrutture frequenti.

• Cambiamento Metodologico: Il lavoro sostiene che le metriche di fedeltà aggregate sono non informative senza un riferimento di memorizzazione. La calibrazione bootstrap proposta è necessaria per interpretare correttamente i punteggi di alta correlazione.
• Estrazione Implicita: I risultati suggeriscono che la modellazione autoregressiva delle serializzazioni di grafi permette agli LLM di internalizzare implicitamente le regolarità strutturali (agendo come "estrattori di grafi neurali") senza enumerazione esplicita dei pattern, a condizione che il corpus di addestramento sia abbastanza grande da prevenire il collasso totale sulla distribuzione empirica.
• Limitazioni: Gli autori notano con modestia che mentre la "Testa" della distribuzione è ben recuperata, la "Coda" rimane un divario critico. Il modello si comporta come un estrattore parziale, catturando le strutture di supporto dominanti ma fallendo nel generalizzare alle sottostrutture rare.

Il documento conclude che l'alto allineamento osservato in contesti su larga scala non è un artefatto di una specifica serializzazione (confermato tramite DFS e DGMG) ma una proprietà robusta dei modelli linguistici su grafi su larga scala, distinta sia dalla pura memorizzazione che dalle baseline generative non basate su LLM.