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

Résumé Technique : Teger – Amélioration de la Propagation des Erreurs Résiduelles Spatio-Temporelles par Atténuation du Sur-Écrasement

Énoncé du Problème
Les modèles récurrents pour la prévision de séries temporelles multivariées, en particulier dans les Systèmes de Transport Intelligents (STI), souffrent de la propagation des erreurs résiduelles. De petites imprécisions de prédiction s'accumulent au fil du temps, dégradant les performances sur les horizons longs. Bien que les modèles récents d'apprentissage profond paramètrent efficacement les corrélations contemporaines variant dans le temps, ils supposent souvent l'indépendance temporelle des erreurs et négligent les corrélations spatiales à travers le réseau observé. Les méthodes existantes, telles que TCVAR, modélisent la covariance temporelle mais échouent à capturer les interactions spatiales. De plus, ces modèles peinent à capturer explicitement la volatilité, conduisant à des estimations d'incertitude mal calibrées.

Une limitation théorique fondamentale identifiée est le phénomène de sur-écrasement (OQ) dans les Réseaux de Neurones à Graphes (GNN). L'OQ se produit lorsque les dépendances à longue portée sont excessivement compressées dans des représentations bornées, déformant la propagation de l'information. Dans le contexte de la prévision du trafic, cela se manifeste par des arêtes goulots d'étranglement (identifiées par une courbure discrète négative) qui atténuent sévèrement le flux d'information entre les nœuds distants. Par conséquent, les modèles existants sous-estiment les corrélations inter-régionales et concentrent la dépendance le long de chaînes minces, échouant à modéliser la véritable structure de covariance spatio-temporelle des résidus de prévision.

Méthodologie : Teger
Les auteurs proposent Teger, un cadre probabiliste agnostique du backbone conçu pour modéliser les résidus spatio-temporels sur des graphes dynamiques. Teger intègre un mécanisme de covariance spatiale conscient de la courbure dans une tête de bruit de type plus-diagonale à rang faible (LRD), préservant une inférence traitable via l'identité de Woodbury.

1. Formulation Probabiliste :
   Le modèle décompose la variable de série temporelle $x_t$ en une moyenne prédictive $\mu_t$ et un composant d'erreur stochastique $\eta_t \sim \mathcal{N}(0, \Sigma_t)$. Pour gérer un grand $N$ (nombre de nœuds), la matrice de covariance $\Sigma_t$ est paramétrée sous une forme plus-diagonale à rang faible : $\Sigma_t = L_t L_t^\top + \text{diag}(d_t)$.

2. Corrélation Temporelle :
   Les dépendances temporelles sur un horizon fini $D$ sont capturées en empilant les résidus dans un vecteur de lot $\eta^{bat}_t$. La matrice de corrélation temporelle $C_t$ est modélisée comme un mélange de noyaux dynamiques (similaire à TCVAR), où les poids sont appris via un réseau softmax.

3. Corrélation Spatiale et Recâblage Conscient de la Courbure :
   L'innovation centrale est un mécanisme de recâblage de la matrice de précision spatiale conscient de la courbure.

   • Identification des Goulots d'Étranglement : La méthode utilise la courbure de Forman équilibrée pour identifier les arêtes agissant comme des goulots d'étranglement d'information (arêtes avec une courbure $\kappa(i, j) \leq -2 + \delta$).
   • Stratégie de Recalibrage : Contrairement aux méthodes de recâblage structurel (par exemple LASER) qui ajoutent ou suppriment des arêtes pour créer de nouveaux chemins, Teger maintient la topologie d'entrée fixe. Il recalibre les arêtes existantes en fonction de leur courbure. Les arêtes identifiées comme des goulots d'étranglement sont renforcées à l'aide d'une fonction apprenable : $W'_{ij,t} = W_{ij,t}(1 + \lambda b_{ij,t})$, où $b_{ij,t}$ est un score de goulot d'étranglement dérivé de la courbure.
   • Construction de la Covariance : Le Laplacien de graphe recalibré $L'_t$ est projeté dans un espace factoriel de basse dimension ($R \ll N$) pour construire une matrice de précision spatiale $Q_t = \alpha I_R + \beta L^{(R)}_t + \sigma_{min} I_R$. La covariance factorielle spatiale est alors $G_t = Q_t^{-1}$. Cette approche admet une projection à rang faible sous forme close, s'intégrant proprement dans la mise à jour de covariance de style Woodbury.

4. Raffinement au Moment de l'Inférence :
   Pour répondre à la sous-estimation de la volatilité et à la propagation des erreurs des premières étapes, Teger emploie une étape de raffinement. Il génère des échantillons de résidus pour l'étape suivante à partir d'une conditionnelle gaussienne induite par la covariance du modèle. Crucialement, il introduit un calibrage de la volatilité au niveau des nœuds, séparant la covariance conditionnelle en une matrice de corrélation sans dimension et une estimation empirique de la volatilité au niveau des nœuds (via une moyenne mobile exponentielle des résidus au carré). Cela évite le double comptage de la variance marginale tout en s'adaptant à la volatilité locale.

Contributions Clés

1. Modèle de Covariance LRD Dynamique : Un cadre probabiliste pour les résidus spatio-temporels qui capture la dépendance spatiale via des facteurs latents conscients du graphe et la dépendance temporelle via une structure autorégressive.
2. Mécanisme Spatial Basé sur la Courbure : Une approche novatrice pour modéliser la diffusion des erreurs sur des graphes dynamiques en utilisant des dynamiques conscientes de l'état et une adaptation de la volatilité, ciblant spécifiquement l'atténuation du sur-écrasement.
3. Algorithme de Recalibrage Efficace : Une étape de recalibrage des arêtes intégrée dans la tête de covariance qui mappe le Laplacien recâblé dans un espace factoriel de dimension $R$ avec une complexité $O(R^3)$ (contre $O(N^3)$), représentant la première intégration d'un recâblage basé sur la courbure dans un prévisionneur spatio-temporel probabiliste.
4. Cadre Unifié : Intégration de ces composants dans un cadre autorégressif unifié qui maintient la faisabilité computationnelle tout en élargissant l'expressivité de la modélisation de l'incertitude.

Résultats Expérimentaux
Les auteurs ont évalué Teger sur quatre jeux de données spatio-temporels réels (PeMS03, PeMS04, PeMS07 et Bruxelles) en utilisant quatre backbones différents : LSTM, Transformer, xLSTM et MTGNN.

• Performance : Teger a systématiquement surpassé les références, y compris les approches naïves, TCVAR (corrélation temporelle uniquement) et LASER (recâblage structurel), sur la plupart des horizons de prévision. La métrique principale utilisée était le Score de Probabilité Classé Continu (CRPS).
• Gains Quantitatifs : Sur le jeu de données Bruxelles, Teger a amélioré le CRPS de 25,3 % par rapport à LASER. En général, la modélisation de la propagation spatiale des erreurs a réduit l'amplitude de l'erreur MAE de près de 30 % par rapport à TCVAR.
• Validation Théorique : L'article rapporte des améliorations de la connectivité spectrale (écart spectral), une résistance effective réduite (indice de Kirchhoff) et une atténuation des goulots d'étranglement locaux (conductance de coupe) suite au processus de recâblage.
• Interprétabilité : L'analyse qualitative sur le jeu de données Bruxelles a montré que le recalibrage de Teger préserve la correspondance entre la topologie du graphe et la structure physique du réseau routier, tandis que les arêtes ajoutées par LASER introduisaient parfois des chemins physiquement irréalistes.

Signification et Revendications
L'article revendique que Teger comble une lacune critique dans la prévision probabiliste : l'incapacité à capturer les motifs de covariance spatio-temporelle dans les résidus, intrinsèquement liés au phénomène de sur-écrasement.

• Portée de la Revendication : Les auteurs sont explicites sur le fait que le recalibrage des arêtes est un outil « strictement plus faible » que le recâblage structurel (comme LASER ou SDRF) car il ne peut pas créer de nouveaux chemins à longue portée là où il n'en existe pas. Cependant, ils soutiennent que cela correspond bien à la prévision de réseaux routiers où le graphe physique est fixe, mais où l'importance des arêtes varie dans le temps.
• Lien Théorique : Le travail fournit des preuves théoriques reliant le recâblage conscient de la courbure à (i) l'atténuation du sur-écrasement, (ii) une connectivité spectrale améliorée, (iii) une résistance effective réduite et (iv) des bornes de calibration de covariance améliorées.
• Agnosticisme du Backbone : Teger ne nécessite que l'état latent produit par n'importe quel encodeur autorégressif, le rendant applicable à une large gamme de modèles existants (LSTM, Transformer, xLSTM).

Les auteurs concluent qu'en atténuant la propagation des erreurs résiduelles grâce à une modélisation spatiale consciente de la courbure, Teger atteint une quantification de l'incertitude plus fiable et une amélioration des performances de prévision sur les horizons longs dans des systèmes spatio-temporels complexes.