Technische Samenvatting: Wanneer Graf-Taalmodellen Voorbij Memoriseren Gaan

1. Probleemstelling

De centrale vraag die dit werk adresseert, is of Graf-Taalmodellen (GLM's) – autoregressieve decoders getraind op geserialiseerde grafrepresentaties – fundamenteel de structurele regulariteiten van grafen leren of simpelweg trainingsdata memoriseren om grafen te genereren vanuit een bijna-empirische verdeling.

Huidige geaggregeerde fideliteitsmetrieken (bijv. graad/clustering/orbit Maximum Mean Discrepancy, GIN-gebaseerde MMD/FID) zijn ontoereikend om deze ambiguïteit op te lossen. Zoals geformaliseerd in Corollarium 3, is overeenstemming op elke enkele begrenste subgraafstatistiek wiskundig consistent met beide regimes: een model dat structurele patronen leert en een model dat trainingsgrafiek letterlijk reproduceert. Zonder een gekalibreerde referentie kunnen hoge fideliteitsscores niet onderscheid maken tussen "structureel leren" en "letterlijke recall".

2. Methodologie

De auteurs stellen een gekalibreerd diagnostisch protocol voor dat is ontworpen om memoriseren te ontwarren van structurele uitlijning. Dit kader werkt op twee assen: een memoriseringsas (letterlijke recall versus nieuwe generatie) en een uitlijningsas (distributie-fideliteit ten opzichte van trainings-subgraafstatistieken).

Kerncomponenten

1. Graf-niveau Bootstrap-baseline:
   Het protocol introduceert een niet-leerende referentieverdeling, $\hat{P}^{boot}_G$, die wordt geconstrueerd door direct te resamplen uit het trainingscorpus. Deze baseline vertegenwoordigt de distributie-uitlijning die uitsluitend door memoriseren haalbaar is. Een model wordt pas geacht voorbij memoriseren te gaan als zijn subgraafstatistieken significant afwijken van deze bootstrap-verdeling.

2. Frequent Subgraaf-mining (gSpan):
   In plaats van te vertrouwen op geaggregeerde grafstatistieken, richt de evaluatie zich op subgraafpatronen. Met behulp van het gSpan-algoritme met een minimum-ondersteuningsdrempel ($\sigma = 0.1$) enumereren de auteurs frequente verbonden subgrafen in zowel trainings- ($D_{tr}$) als gegenereerde ($D_{gen}$) databases.

3. Frequentie-gestratificeerde Analyse:
   Om te onthullen waar uitlijning slaagt of faalt, wordt de ondersteuningsverdeling van subgraafpatronen opgesplitst in drie strata:

   • Hoofd: Top 10% (hoge-frequentie motieven).
   • Torso: Midden 80% (matig frequente patronen).
   • Staart: Bodem 10% (zeldzame patronen nabij de ondersteuningsdrempel).
     Metrieken (Spearman rangcorrelatie, Jensen–Shannon-divergentie, Missing Mass) worden onafhankelijk voor elk stratum berekend.

4. Serialisatie-robustheid:
   De analyse wordt uitgevoerd over twee distincte serialisatiemethoden om ervoor te zorgen dat bevindingen geen artefacten zijn van een specifieke tokenisatie:

   • Canonieke DFS-code: Een unieke representatie voor isomorfische grafen.
   • DGMG-actiesequentie: Een sequentieel beslissingsproces-encoding (ADD_NODE, ADD_EDGE, enz.).

Experimentele Opstelling

• Modellen: LLaMA-stijl causale taalmodellen (decoder-only) vanaf nul getraind op geserialiseerde grafen.
• Datasets: Vijf TU-benchmarks (MUTAG, PTC_MR, ENZYMES, PROTEINS, NCI1) en het grootschalige PCQM4Mv2-moleculaire corpus (~3,75M grafen).
• Baselines: Vergelijking tegen structurele baselines, waaronder DiGress (diffusie), GraphRNN en DGMG-official.

3. Belangrijkste Resultaten

A. Klein-schaal Regime (TU-benchmarks)

Op kleine datasets opereren GLM's in een memoriserings-gedomineerd regime.

• Hoge Fideliteit door Recall: Modellen bereiken hoge Spearman-correlaties ($\rho \approx 0,95\text{--}0,99$) en lage Jensen–Shannon-divergentie. Echter, onthult de Bootstrap-kalibratie dat deze metrieken binnen of onder het bereik vallen dat verwacht wordt van eenvoudige resampling van de trainingsset.
• Letterlijke Recall: Exacte-match-rates voor hele grafen (precisie) zijn extreem hoog (bijv. 82,8% op MUTAG, 100% op NCI1).
• Conclusie: In dit regime is geaggregeerde fideliteit een statistisch gevolg van memoriseren, geen bewijs van structureel leren.

B. Groot-schaal Regime (PCQM4Mv2)

Op schaal (3,75M grafen) treedt een fasenovergang op.

• Koppeling: Memoriseren van hele grafen daalt scherp (Precisie $\approx 31,7\%$), maar de Spearman-correlatie op subgraafniveau blijft dicht bij het plafond ($\rho \approx 0,976$).
• Uitlijning Alleen voor Nieuwheid: Wanneer beperkt tot een "alleen-nieuw"-subset (exclusief gememoriseerde grafen), volgt de Spearman-correlatie de correlatie van volledige generatie binnen 0,026. Dit bevestigt dat het model structurele regulariteiten behoudt, zelfs voor niet-gememoriseerde grafen.
• Conclusie: Groot-schaal GLM's internaliseren succesvol structurele regulariteiten en fungeren als impliciete neurale graf-miners.

C. De Persistente Tekortkoming bij Zeldzame Patronen

Over alle schalen en serialisaties heen wordt een fundamentele beperking waargenomen:

• Hoofd/Torso Succes: Frequente en matig frequente patronen worden met hoge fideliteit gereproduceerd ($\rho \ge 0,91$).
• Staart Falen: Zeldzame patronen (Staart-stratum) worden consequent slecht gedekt. De Missing mass voor de Staart is een orde van grootte hoger dan voor Hoofd/Torso (bijv. 13,5%–22,0% op TU-datasets versus <1% voor Hoofd). De rangcorrelatie op de Staart is significant lager ($\rho \in [0,26, 0,56]$ op TU; $\approx 0,41$ op PCQM4Mv2).
• Robustheid: Dit tekort blijft bestaan ongeacht modelcapaciteit (schaling van 10,5M tot 451M parameters) en serialisatieformaat, wat wijst op een structurele kloof in huidige autoregressieve generatie voor zeldzame substructuren.

D. Vergelijkingen met Baselines

• DiGress (Diffusie): Bereikt bijna nul memoriseren maar faalt in het herstellen van frequente subgraafverdelingen ($\rho \approx 0,25$ op PCQM4Mv2), en bezet een regime van laag-memoriseren/laag-uitlijning.
• GraphRNN/DGMG-official: Label-onbewuste baselines falen volledig in het herstellen van gelabelde subgraaf-ondersteuning, waardoor subgraafstatistieken op de meeste datasets ongedefinieerd zijn.

4. Bijdragen

1. Gekalibreerd Diagnostisch Protocol: De introductie van een kader dat frequent subgraaf-mining combineert met een graf-niveau bootstrap-baseline. Dit overwint de beperkingen van geaggregeerde metrieken door expliciet te testen of uitlijning de haalbaarheid door memoriseren overstijgt.
2. Bewijs van Schaal-afhankelijk Structureel Leren: De demonstratie dat GLM's overgaan van een memoriserings-gedomineerd regime op kleine datasets naar een ontkoppeld regime op schaal, waarbij ze subgraafstatistieken behouden voor nieuwe grafen.
3. Identificatie van de Tekortkoming bij Zeldzame Patronen: De blootlegging van een systematisch falen om de verdeling van zeldzame (Staart) patronen te leren, wat een bottleneck blijft zelfs naarmate de modelcapaciteit toeneemt.

5. Betekenis en Claims

Het artikel claimt een voorwaardelijk antwoord op de vraag of GLM's voorbij memoriseren gaan: Ja, maar alleen bij voldoende schaal en voornamelijk voor frequente substructuren.

• Methodologische Verschuiving: Het werk betoogt dat geaggregeerde fideliteitsmetrieken oninformatief zijn zonder een memoriseringsreferentie. De voorgestelde bootstrap-kalibratie is noodzakelijk om hoge correlatiescores correct te interpreteren.
• Impliciete Mining: De resultaten suggereren dat autoregressieve modellering van grafserialisaties het LLM's mogelijk maakt om structurele regulariteiten impliciet te internaliseren (als "neurale graf-miners" fungerend) zonder expliciete patronenumeratie, mits het trainingscorpus groot genoeg is om een totale instorting op de empirische verdeling te voorkomen.
• Beperkingen: De auteurs merken bescheiden op dat terwijl het "Hoofd" van de verdeling goed wordt hersteld, de "Staart" een kritieke kloof blijft. Het model gedraagt zich als een partiële miner, die dominante ondersteuningsstructuren vastlegt maar faalt in het generaliseren naar zeldzame substructuren.

Het artikel concludeert dat de waargenomen hoge uitlijning in groot-schaal settings geen artefact is van een specifieke serialisatie (bevestigd via DFS en DGMG), maar een robuuste eigenschap van groot-schaal graf-taalmodellen, die verschilt van zowel puur memoriseren als generatieve baselines zonder LLM.