Transformateur Léger et Interprétable via Déroulement d'Algorithme de Graphe Mixte pour la Prévision du Trafic

Informations Fondamentales

• ID de l'article: 2505.13102
• Titre: Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast
• Auteurs: Ji Qi, Mingxiao Liu, Tam Thuc Do, Yuzhe Li, Zhuoshi Pan, Gene Cheung, H. Vicky Zhao
• Classification: cs.LG cs.AI eess.SP
• Date de publication: 12 octobre 2025 (arXiv v2)
• Lien de l'article: https://arxiv.org/abs/2505.13102

Résumé

Cet article propose un modèle Transformateur léger et interprétable basé sur le déroulement d'algorithme de graphe mixte pour la prévision du trafic. Contrairement aux Transformateurs traditionnels de type « boîte noire », cette méthode construit un réseau de neurones de type Transformateur interprétable en déroulant un algorithme d'optimisation de graphe mixte. Le modèle construit deux graphes : un graphe non orienté $\mathcal{G}^u$ capturant les corrélations géospatiales et un graphe orienté $\mathcal{G}^d$ capturant les relations temporelles. En concevant de nouveaux termes de variation de normes $\ell_2$ et $\ell_1$ pour quantifier et promouvoir la régularité du signal sur le graphe orienté, et en basant un algorithme itératif sur la méthode des multiplicateurs de direction alternée (ADMM), le modèle est déroulé en réseau avant pour l'apprentissage des paramètres piloté par les données. Les expériences montrent que ce modèle maintient des performances compétitives en prévision du trafic tout en réduisant considérablement le nombre de paramètres.

Contexte de Recherche et Motivation

Définition du Problème

La prévision du trafic est un problème important de modélisation de données spatio-temporelles qui nécessite de capturer simultanément :

1. Corrélation spatiale : corrélation entre les stations de surveillance géographiquement proches
2. Dépendance temporelle : influence des observations historiques sur l'avenir

Limitations des Méthodes Existantes

1. Transformateurs traditionnels : nombre de paramètres énorme, manque d'interprétabilité, contraintes de calcul et de mémoire lors du déploiement pratique
2. Méthodes basées sur des modèles : traitent souvent indépendamment les dimensions spatiales et temporelles, n'exploitent pas pleinement les relations spatio-temporelles
3. Méthodes d'apprentissage profond existantes : bien que performantes, restent des modèles « boîte noire » avec un grand nombre de paramètres

Motivation de la Recherche

1. Besoin urgent de modèles légers pour les applications industrielles
2. Le déroulement d'algorithme (Algorithm Unrolling) offre un nouveau paradigme combinant approches pilotées par modèles et pilotées par données
3. Les travaux existants n'utilisent que des graphes non orientés symétriques, incapables de modéliser efficacement les relations spatio-temporelles complexes

Contributions Principales

1. Première proposition de déroulement d'algorithme de graphe mixte : combine graphe non orienté (spatial) et graphe orienté (temporel) pour modéliser les relations spatio-temporelles complexes
2. Termes de régularisation de graphe orienté innovants : conçoit le régulariseur de Laplacien de graphe orienté (DGLR) et la variation totale de graphe orienté (DGTV)
3. Transformateur léger et interprétable : réalise une réduction massive des paramètres (seulement 6,4% de PDFormer) via déroulement d'algorithme ADMM
4. Contribution théorique : prouve que la définition de fréquence de graphe orienté se réduit à la fréquence de Fourier classique dans le cas de graphes linéaires orientés non pondérés

Détails de la Méthode

Définition de la Tâche

Étant donné les observations de N stations de surveillance à T+1 instants passés, prédire l'état du trafic pour les S instants futurs. L'entrée est un signal spatio-temporel partiellement observé $y \in \mathbb{R}^M$, la sortie est un signal spatio-temporel complet $x \in \mathbb{R}^{N(T+S+1)}$.

Construction de Graphe Mixte

Graphe Non Orienté $\mathcal{G}^u$

• Connecte les nœuds géographiquement proches au même instant
• Capture la corrélation spatiale
• Utilise une matrice d'adjacence symétrique $W^u$

Graphe Orienté $\mathcal{G}^d$

• Connecte les nœuds de l'instant $\tau$ aux instants $\tau+1, ..., \tau+W$ du même nœud
• Capture les relations causales temporelles
• Utilise une matrice d'adjacence non symétrique $W^d$

Conception des Termes de Variation de Graphe Orienté

Terme de Norme $\ell_2$ : Régulariseur de Laplacien de Graphe Orienté (DGLR)

$x^T\mathcal{L}_r^d x = x^T(L_r^d)^T L_r^d x = \|x - W_r^d x\|_2^2$

où $L_r^d = I - W_r^d$ est la matrice de Laplacien de marche aléatoire et $W_r^d = (D^d)^{-1}W^d$ est la matrice d'adjacence normalisée par ligne.

Terme de Norme $\ell_1$ : Variation Totale de Graphe Orienté (DGTV)

$\|L_r^d x\|_1 = \sum_{j \in \bar{S}} |x_j - \sum_i w_{j,i} x_i|$

Fonction Objectif d'Optimisation

$\min_x \|y - Hx\|_2^2 + \mu_u x^T L^u x + \mu_{d,2} x^T \mathcal{L}_r^d x + \mu_{d,1} \|L_r^d x\|_1$

où $H$ est la matrice d'échantillonnage et $\mu_u, \mu_{d,2}, \mu_{d,1}$ sont les paramètres de poids.

Conception de l'Algorithme ADMM

En introduisant une variable auxiliaire $\phi$, le problème d'optimisation est transformé en : $\min_{x,\phi} \|y - Hx\|_2^2 + \mu_u x^T L^u x + \mu_{d,2} x^T \mathcal{L}_r^d x + \mu_{d,1} \|\phi\|_1$$\text{s.c. } \phi = L_r^d x$

Résolution des Sous-problèmes

1. Sous-problème $x$ : résolu via méthode du gradient conjugué
2. Sous-problème $\phi$ : opération de seuillage doux $\phi_i^{\tau+1} = \text{sign}(\delta) \cdot \max(|\delta| - \rho^{-1}\mu_{d,1}, 0)$ où $\delta = (L_r^d)_i x^{\tau+1} - \rho^{-1}\gamma_i^\tau$

Module d'Apprentissage de Graphe

Apprentissage de Graphe Non Orienté (UGL)

Calcule la similarité des nœuds via distance de Mahalanobis : $d^u(i,j) = (f_i^u - f_j^u)^T M (f_i^u - f_j^u)$

Les poids des arêtes sont calculés via fonction exponentielle normalisée : $w_{i,j}^u = \frac{\exp(-d^u(i,j))}{\sqrt{\sum_{l \in \mathcal{N}_i} \exp(-d^u(i,l))} \sqrt{\sum_{k \in \mathcal{N}_j} \exp(-d^u(k,j))}}$

Apprentissage de Graphe Orienté (DGL)

Calcule de manière similaire les poids des arêtes orientées via matrice de métrique $P$.

Architecture du Réseau

Implémente chaque itération ADMM comme couche de neurone :

• 5 blocs ADMM, chaque bloc contenant 25 couches
• Insertion d'un module d'apprentissage de graphe avant chaque bloc
• Utilisation de mécanisme d'attention multi-têtes (4 modules d'apprentissage de graphe parallèles)

Configuration Expérimentale

Ensembles de Données

• METR-LA : données de vitesse du trafic de Los Angeles, 207 nœuds, 1315 arêtes
• PEMS03 : données de flux de trafic, 358 nœuds, 547 arêtes
• Intervalle d'échantillonnage : 5 minutes
• Division des données : 6:2:2 (entraînement:validation:test)

Métriques d'Évaluation

• RMSE : erreur quadratique moyenne
• MAE : erreur absolue moyenne
• MAPE : erreur absolue moyenne en pourcentage

Méthodes de Comparaison

Incluent 6 catégories de méthodes de base :

• Basées sur modèles : VAR
• Méthodes GNN : STGCN, STSGCN
• Méthodes GAT : GMAN, ST-Wave
• Méthodes Transformer : PDFormer, STAEformer
• Méthodes de graphe adaptatif : Graph WaveNet, AGCRN
• Modèles linéaires simples : STID, SimpleTM

Détails d'Implémentation

• Durée de prévision : 30/60/120 minutes (6/12/24 pas)
• Fenêtre historique : 60 minutes (12 pas)
• Optimiseur : Adam, taux d'apprentissage 5×10⁻⁴
• Fonction de perte : perte de Huber (δ=1)
• Matériel : NVIDIA GeForce RTX 3090

Résultats Expérimentaux

Résultats Principaux

Découvertes Clés

1. Efficacité des paramètres : utilise seulement 6,4% des paramètres de PDFormer pour atteindre des performances compétitives
2. Avantage en prévision à long terme : l'écart avec la meilleure méthode diminue à mesure que la durée de prévision augmente
3. Efficacité des données : performance plus stable en cas de données rares

Expériences d'Ablation

Les résultats montrent :

• Le terme DGLR est le plus critique pour l'amélioration des performances
• Le terme DGTV contribue également de manière significative
• La modélisation de graphe orienté surpasse la modélisation de graphe non orienté

Vérification Théorique

Le Théorème 3.1 prouve que pour un graphe linéaire orienté non pondéré, le Laplacien de graphe orienté symétrisé $\mathcal{L}_r^d = (L_r^d)^T L_r^d$ est équivalent à la matrice de Laplacien du graphe linéaire non orienté, validant la rationalité de la définition de fréquence.

Travaux Connexes

Modèles Légers

• Grands modèles de langage : adaptation de rang faible LoRA, quantification des paramètres
• Amélioration vocale : auto-attention causale locale
• Traitement d'images : traitement séparé des canaux YUV

Méthodes de Prévision du Trafic

1. Méthodes GNN : STGCN, Graph WaveNet, etc., se concentrant sur la modélisation spatiale
2. Méthodes Transformer : double Transformer traitant séparément les dimensions spatio-temporelles
3. Modèles linéaires simples : remettent en question l'efficacité des modèles complexes

Déroulement d'Algorithme

• Déroule les itérations d'algorithmes d'optimisation en couches de neurones
• Combine interprétabilité mathématique et capacité pilotée par données
• Applications réussies en traitement d'images

Conclusion et Discussion

Conclusions Principales

1. Le déroulement d'algorithme de graphe mixte réalise avec succès un modèle de prévision du trafic léger et interprétable
2. Les termes de variation de graphe orienté capturent efficacement les relations causales temporelles
3. Maintient des performances compétitives tout en réduisant considérablement le nombre de paramètres

Limitations

1. Restriction de distance : la distance de Mahalanobis apprise est non négative, tandis que l'auto-attention traditionnelle peut être négative
2. Parcimonie du graphe : les connexions réelles des routes limitent la connectivité du graphe
3. Fenêtre temporelle fixe : la fenêtre temporelle prédéfinie peut manquer de flexibilité

Directions Futures

1. Extension à des distances signées et modélisations de graphe plus complexes
2. Apprentissage adaptatif de fenêtres temporelles
3. Application à d'autres tâches de prévision spatio-temporelle

Évaluation Approfondie

Points Forts

1. Innovation théorique : première définition de concept de fréquence pour graphe orienté avec conception de termes de régularisation correspondants
2. Méthode novatrice : le déroulement d'algorithme de graphe mixte offre une nouvelle perspective pour la conception de Transformateurs
3. Valeur pratique : la réduction significative des paramètres a une importance majeure pour le déploiement réel
4. Interprétabilité : chaque couche correspond à une itération d'algorithme d'optimisation avec signification mathématique claire

Insuffisances

1. Compromis de performance : surpasse toujours pas les meilleures méthodes de base sur certaines métriques
2. Portée d'application : validation principalement sur prévision du trafic, généralisation à d'autres tâches spatio-temporelles inconnue
3. Analyse théorique : manque d'analyse théorique de convergence et de complexité

Impact

1. Contribution académique : offre une nouvelle perspective pour le traitement de signal graphique et la conception de Transformateurs
2. Valeur pratique : la nature légère convient aux environnements d'informatique en bordure et aux ressources limitées
3. Reproductibilité : fournit code open source avec configuration expérimentale détaillée

Scénarios d'Application

1. Environnements aux ressources limitées : appareils mobiles, informatique en bordure
2. Systèmes de prévision en temps réel : systèmes de gestion du trafic nécessitant une réponse rapide
3. Applications d'IA explicable : systèmes critiques pour la sécurité nécessitant la transparence du modèle

Références

L'article cite plusieurs travaux importants, notamment :

• Article original Transformer (Vaswani et al., 2017)
• Synthèse du déroulement d'algorithme (Monga et al., 2021)
• Fondamentaux du traitement de signal graphique (Ortega et al., 2018)
• Travaux connexes en prévision du trafic (Li et al., 2017; Yu et al., 2018)

Évaluation Globale : Ceci est un travail innovant dans le domaine de la prévision du trafic qui étend avec succès l'idée de déroulement d'algorithme au cadre de graphe mixte, réduisant considérablement le nombre de paramètres tout en maintenant les performances. Bien qu'il y ait encore place à amélioration sur certaines métriques, ses caractéristiques légères et interprétables lui confèrent une valeur pratique et une signification académique importantes.