Graph Hierarchical Recurrence for Long-Range Generalization

Technische Samenvatting: Grafische Hiërarchische Recurrentie voor Generalisatie op Lange Afstand

Probleemstelling
Grafische Neuronale Netwerken (GNN's) en Grafische Transformers (GT's) hebben zich gevestigd als de standaard voor grafenleren, maar ze staan voor fundamentele beperkingen in taken die het vastleggen van correlaties tussen verre grafische gebieden vereisen. Bestaande modellen lijden aan drie primaire pathologieën:

1. Over-squashing: De compressie van een exponentieel groeiend receptivveld naar vaste grootte knooprepresentaties.
2. Over-smoothing: De convergentie van knoopkenmerken naar homogene, niet-onderscheidbare embeddings.
3. Verdwijnende Gradiënten: Moeilijkheden bij het trainen van diepe Message-Passing Neural Networks (MPNN's), wat de informatiestroom over grote afstanden belemmert.

Hoewel oplossingen zoals grafische herschakeling (het introduceren van kunstmatige randen) en Grafische Transformers (het gebruik van globale aandacht) bestaan, brengen ze nieuwe problemen met zich mee: herschakeling vervormt topologische inductieve bias, en aandachtmechanismen leiden tot kwadratische computationele complexiteit, wat schaalbaarheid beperkt. Bovendien maakt het artikel onderscheid tussen generalisatie binnen het bereik (het doorgeven van informatie over afstanden die tijdens het trainen zijn gezien) en generalisatie buiten het bereik (extrapoleren naar afstanden die langer zijn dan die welke zijn waargenomen). Huidige modellen falen vaak bij generalisatie buiten het bereik en verslechteren snel wanneer testinstanties interactie-afstanden bevatten die de trainingshorizon overschrijden.

Methodologie: Grafische Hiërarchische Recurrentie (GHR)
De auteurs stellen Grafische Hiërarchische Recurrentie (GHR) voor, een raamwerk dat recurrente berekening combineert met multi-schaal grafische representaties om generalisatie op lange afstand en buiten het bereik aan te pakken zonder de topologie te vervormen of kwadratische complexiteit te veroorzaken.

• Twee-Niveau Hiërarchie: GHR werkt op twee niveaus: een laag-niveau graf ($G_L$) die de originele input vertegenwoordigt, en een hoog-niveau graf ($G_H$) verkregen via een pooling-map (bijvoorbeeld Graclus of geometrische blokpartitionering). De pooling-map is 1-Lipschitz, waardoor de diameter van $G_H$ kleiner is dan of gelijk is aan die van $G_L$, wat het aantal stappen vereist om de graf te overbruggen, vermindert.
• Geneste Recurrente Schemata: De kern van GHR is een globale recurrente stap ($R_W$) die hidden states voor beide niveaus iteratief bijwerkt. Deze stap maakt gebruik van een recurrente schemata met twee tijdschalen:
  • Hoog-Niveau Stroom: Geeft informatie door op de grovere, gepoolde graf $G_H$ ($T_H$ stappen). Deze stroom fungeert als een "shortcut" voor communicatie op lange afstand.
  • Laag-Niveau Stroom: Geeft informatie door op de originele graf $G_L$ ($T_L$ stappen).
  • Koppeling: De stromen zijn nauw gekoppeld. De hoog-niveau stroom leidt de laag-niveau stroom via unpooling (het uitzenden van hoog-niveau kenmerken terug naar laag-niveau knopen), terwijl de laag-niveau stroom de hoog-niveau stroom informeert via pooling.
• Architectuur-Agnosticisme: Het raamwerk is agnostisch ten opzichte van de specifieke message-passing-functie die wordt gebruikt (bijvoorbeeld GINE, GCN, GAT, GatedGCN). Het maakt gebruik van leerbare lineaire kaarten voor input-codering en RMSNorm om de grootte van kenmerken te stabiliseren.
• Trainingsstrategie: Het model wordt getraind met Backpropagation Through Time (BPTT) met een temporair afgepaste loss. Deze benadering past de loss toe bij elke recurrente stap, waarbij latere stappen zwaarder wegen om verdwijnende gradiënten te voorkomen, terwijl progressieve verfijning wordt toegestaan.

Belangrijkste Bijdragen

1. Nieuw Raamwerk: Introductie van GHR, een tweeniveau recurrente architectuur die grafische pooling gebruikt om een hiërarchie te creëren met twee message-passing-stromen, waardoor efficiënte propagatie op lange afstand mogelijk wordt terwijl de inductieve bias van de onderliggende topologie behouden blijft.
2. Generalisatie Buiten het Bereik: Aantonen dat GHR kan extrapoleren naar interactie-afstanden die aanzienlijk langer zijn dan die welke tijdens het trainen zijn waargenomen, een capaciteit waar bestaande feedforward- en op aandacht gebaseerde modellen in falen.
3. Parameter-efficiëntie: Validatie dat GHR state-of-the-art of concurrerende prestaties bereikt met 1% tot 10% van de trainbare parameters van huidige state-of-the-art modellen.
4. Ablatie-analyse: Bewijs dat zowel de hiërarchische structuur als het recurrente mechanisme noodzakelijk zijn voor generalisatie buiten het bereik; vlakke recurrente modellen falen in nauwkeurigheid binnen het bereik, terwijl diepe feedforward-modellen falen buiten het bereik.

Experimentele Resultaten
De auteurs evalueerden GHR op diverse benchmarks:

• ECHO Benchmark: GHR behaalde state-of-the-art resultaten op algoritmische taken (SSSP, Eccentricity, Diameter) en concurrerende resultaten op chemische taken (DFT-gebaseerde ladingen, moleculaire energieën), met gebruik van orde-grootte minder parameters dan baselines zoals GPS, GRIT en SWAN.
• LRIM Benchmark: Op het Long-Range Ising Model kwam GHR overeen met de prestaties van de baseline op taken binnen de verdeling en behaalde het superieure zero-shot extrapolatie naar grotere roostergroottes (bijvoorbeeld trainen op 16x16 en testen op 256x256), terwijl op aandacht gebaseerde modellen last hadden van out-of-memory-fouten of prestatiedegradatie.
• Random Geometrische Grafen (RGG): In gecontroleerde experimenten buiten het bereik behield GHR een bijna nul Mean Absolute Error (MAE) op kortste-padsafstanden tot 40 hops wanneer getraind was op afstanden tot 20 hops. Daarentegen degradeerden diepe GIN- en GPS-baselines lineair buiten hun trainingsdiepte.

Betekenis en Claims
Het artikel beweert dat GHR een complementaire richting biedt ten opzichte van de huidige trend om architecturen te schalen om grafische foundation-modellen te creëren. De resultaten suggereren dat verhoogde modelcapaciteit alleen niet voldoende is voor generalisatie, met name voor taken buiten het bereik. In plaats daarvan zijn architecturale mechanismen die hiërarchisch redeneren en recurrentie ondersteunen, cruciaal.

De auteurs positioneren GHR als een principiële methode om recurrente diepte te schalen zonder de modelgrootte te vergroten, wat effectief over-squashing en over-smoothing mitigeert terwijl de topologische integriteit behouden blijft. Zij concluderen dat het combineren van recurrentie met hiërarchische representaties een veelbelovende weg is naar schaalbare en generaliseerbare grafenleersystemen, hoewel zij opmerken dat het uitbreiden van de hiërarchie naar meer dan twee niveaus en het karakteriseren van de expressieve kracht van dergelijke modellen open richtingen blijven voor toekomstig werk.