Improving Spatio-Temporal Residual Error Propagation by Mitigating Over-Squashing

Technische Samenvatting: Teger – Verbetering van Spatio-Temporale Residuele Foutpropagatie door Over-Squashing te Mitigeren

Probleemstelling
Recurrente modellen voor multivariate tijdreeksvoorspelling, met name in Intelligent Transportation Systems (ITS), lijden onder residuele foutpropagatie. Kleine voorspellingonnauwkeurigheden versterken elkaar in de loop van de tijd, wat de prestaties op lange termijn verslechtert. Hoewel recente deep learning-modellen effectief tijdsvariërende contemporane correlaties parametriseren, gaan ze vaak uit van tijdelijke onafhankelijkheid van fouten en verwaarlozen ze ruimtelijke correlaties over het waargenomen netwerk. Bestaande methoden, zoals TCVAR, modelleren tijdelijke covariantie maar slagen er niet in ruimtelijke interacties vast te leggen. Bovendien worstelen deze modellen om volatiliteit expliciet vast te leggen, wat leidt tot verkeerd gekalibreerde onzekerheidsschattingen.

Een fundamentele theoretische beperking die is geïdentificeerd, is het fenomeen van over-squashing (OQ) in Graph Neural Networks (GNN's). OQ treedt op wanneer lange-afstandsafhankelijkheden excessief worden samengeperst in gebonden representaties, waardoor informatieverplaatsing wordt vervormd. In de context van verkeersvoorspelling manifesteert dit zich als knelpunt-edges (geïdentificeerd door negatieve discrete kromming) die de informatiestroom tussen verre knopen ernstig afzwakken. Bijgevolg onderschatten bestaande modellen cross-regionale correlaties en concentreren ze afhankelijkheid langs dunne ketens, waardoor ze de ware spatio-temporale covariantiestructuur van voorspellingresiduen niet modelleren.

Methodologie: Teger
De auteurs stellen Teger voor, een backbone-agnostisch probabilistisch raamwerk dat is ontworpen om spatio-temporale residuen op dynamische grafen te modelleren. Teger integreert een krommingsbewuste ruimtelijke covariantiemechanisme in een low-rank-plus-diagonaal (LRD) ruishead, waarbij bruikbare inferentie behouden blijft via de Woodbury-identiteit.

1. Probabilistische Formulering:
   Het model decomposeert de tijdreeksvariabele $x_t$ in een voorspellend gemiddelde $\mu_t$ en een stochastisch foutcomponent $\eta_t \sim \mathcal{N}(0, \Sigma_t)$. Om te handelen met grote $N$ (aantal knopen), wordt de covariantiematrix $\Sigma_t$ geparametriseerd als een low-rank-plus-diagonaal vorm: $\Sigma_t = L_t L_t^\top + \text{diag}(d_t)$.

2. Tijdelijke Correlatie:
   Tijdelijke afhankelijkheden over een eindige horizon $D$ worden vastgelegd door residuen te stapelen in een batch-vector $\eta^{bat}_t$. De tijdelijke correlatiematrix $C_t$ wordt gemodelleerd als een dynamische kernelmix (vergelijkbaar met TCVAR), waarbij gewichten worden geleerd via een softmax-netwerk.

3. Ruimtelijke Correlatie en Krommingsbewuste Herbedrading:
   De kerninnovatie is een krommingsbewust mechanisme voor herbedrading van ruimtelijke precisiematrices.

   • Identificatie van Knelpunten: De methode maakt gebruik van Balanced Forman-kromming om edges te identificeren die fungeren als informatieknelpunten (edges met kromming $\kappa(i, j) \leq -2 + \delta$).
   • Herverdelingstrategie: In tegenstelling tot structurele herbedradingmethoden (zoals LASER) die edges toevoegen of verwijderen om nieuwe paden te creëren, houdt Teger de invoertopologie vast. Het herbekijkt bestaande edges op basis van hun kromming. Edges die als knelpunten worden geïdentificeerd, worden versterkt met een leerbare functie: $W'_{ij,t} = W_{ij,t}(1 + \lambda b_{ij,t})$, waarbij $b_{ij,t}$ een knelpuntscore is afgeleid van de kromming.
   • Constructie van Covariantie: De herbekijkte graf-Laplaciaan $L'_t$ wordt geprojecteerd op een laag-dimensionale factorruimte ($R \ll N$) om een ruimtelijke precisiematrix te construeren $Q_t = \alpha I_R + \beta L^{(R)}_t + \sigma_{min} I_R$. De ruimtelijke factorcovariantie is dan $G_t = Q_t^{-1}$. Deze benadering staat een gesloten-vorm low-rank projectie toe, die naadloos integreert in de Woodbury-stijl covariantie-update.

4. Verfijning tijdens Inferentie:
   Om de onderschatting van volatiliteit en de propagatie van fouten in vroege stappen aan te pakken, hanteert Teger een verfijningstap. Het trekt steekproeven van de volgende-stap-residuen uit een Gaussische conditie die wordt geïnduceerd door de modelcovariantie. Cruciaal introduceert het knooppunt-gewijze volatiliteitsschaling, waarbij de conditionele covariantie wordt gescheiden in een dimensieloze correlatiematrix en een empirische knooppunt-gewijze volatiliteitsschatting (via exponentieel bewegend gemiddelde van gekwadrateerde residuen). Dit voorkomt dubbel tellen van marginale variantie terwijl het zich aanpast aan lokale volatiliteit.

Belangrijkste Bijdragen

1. Dynamisch LRD Covariantiemodel: Een probabilistisch raamwerk voor spatio-temporale residuen dat ruimtelijke afhankelijkheid vastlegt via graf-bewuste latente factoren en tijdelijke afhankelijkheid via een autoregressieve structuur.
2. Krommingsgebaseerd Ruimtelijk Mechanisme: Een nieuwe aanpak voor het modelleren van foutdiffusie op dynamische grafen met behulp van toestandsbewuste dynamica en volatiliteitsadaptatie, specifiek gericht op het mitigeren van over-squashing.
3. Efficiënt Herbekijkingsalgoritme: Een edge-herbekijkingsstap ingebed in de covariantiehead die de herbekijkte Laplaciaan afbeeldt op een $R$-dimensionale factorruimte met $O(R^3)$ complexiteit (tegenover $O(N^3)$), wat de eerste integratie vertegenwoordigt van krommingsgebaseerde herbedrading in een probabilistische spatio-temporale voorspeller.
4. Gefuseerd Raamwerk: Integratie van deze componenten in een unified autoregressief raamwerk dat computationele bruikbaarheid behoudt terwijl het de expressiviteit van onzekerheidsmodelleren uitbreidt.

Experimentele Resultaten
De auteurs hebben Teger geëvalueerd op vier real-world spatio-temporale datasets (PeMS03, PeMS04, PeMS07 en Brussel) met behulp van vier verschillende backbones: LSTM, Transformer, xLSTM en MTGNN.

• Prestaties: Teger presteerde consequent beter dan baselines, inclusief naïeve benaderingen, TCVAR (alleen tijdelijke correlatie) en LASER (structurele herbedrading), over de meeste voorspellinghorizons. De primaire gebruikte metriek was de Continuous Ranked Probability Score (CRPS).
• Kwantitatieve Winsten: Op de Brusselse dataset verbeterde Teger de CRPS met 25,3% ten opzichte van LASER. Over het algemeen verminderde het modelleren van ruimtelijke foutpropagatie de MAE-foutgrootte met bijna 30% ten opzichte van TCVAR.
• Theoretische Validatie: Het artikel rapporteert verbeteringen in spectrale connectiviteit (spectrale gap), verminderde effectieve weerstand (Kirchhoff-index) en verminderde lokale knelpunten (cut conductance) na het herbedradingproces.
• Interpreteerbaarheid: Kwalitatieve analyse op de Brusselse dataset toonde aan dat Teger's herbekijking de correspondentie tussen graf-topologie en fysieke wegstructuur behoudt, terwijl LASER's toegevoegde edges soms fysiek onrealistische paden introduceerden.

Betekenis en Claims
Het artikel claimt dat Teger een kritieke kloof in probabilistische voorspelling aanpakt: het onvermogen om spatio-temporale covariantiepatronen in residuen vast te leggen, die intrinsiek verbonden zijn met het over-squashing-fenomeen.

• Reikwijdte van de Claim: De auteurs zijn expliciet dat edge-herbekijking een "strikt zwakker hulpmiddel" is dan structurele herbedrading (zoals LASER of SDRF) omdat het geen nieuwe lange-afstandspaden kan creëren waar geen enkele bestaat. Ze betogen echter dat dit goed aansluit bij verkeersnetwerkvoorspelling waar de fysieke graf vaststaat, maar edge-belangrijkheden in de loop van de tijd variëren.
• Theoretisch Verband: Het werk biedt theoretisch bewijs dat krommingsbewuste herbedrading verbindt met (i) verlichting van over-squashing, (ii) verbeterde spectrale connectiviteit, (iii) verminderde effectieve weerstand en (iv) verbeterde covariantie-kalibratiegrenzen.
• Backbone-Agnosticisme: Teger vereist alleen de latente toestand geproduceerd door een willekeurige autoregressieve encoder, waardoor het toepasbaar is op een breed scala aan bestaande modellen (LSTM, Transformer, xLSTM).

De auteurs concluderen dat Teger door residuele foutpropagatie te mitigeren via krommingsbewuste ruimtelijke modellering, betrouwbaardere onzekerheidskwantificatie en verbeterde prestaties bij voorspelling op lange termijn bereikt in complexe spatio-temporale systemen.