Transformer Leggero e Interpretabile tramite Algoritmo di Grafo Misto Srotolato per la Previsione del Traffico

Informazioni Fondamentali

• ID Articolo: 2505.13102
• Titolo: Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast
• Autori: Ji Qi, Mingxiao Liu, Tam Thuc Do, Yuzhe Li, Zhuoshi Pan, Gene Cheung, H. Vicky Zhao
• Classificazione: cs.LG cs.AI eess.SP
• Data di Pubblicazione: 12 ottobre 2025 (arXiv v2)
• Link dell'Articolo: https://arxiv.org/abs/2505.13102

Riassunto

Questo articolo propone un modello Transformer leggero e interpretabile basato sullo srotolamento di algoritmi di grafo misto per la previsione del traffico. A differenza dei Transformer tradizionali "scatola nera", questo metodo costruisce una rete neurale di tipo Transformer interpretabile srotolando algoritmi di ottimizzazione di grafo misto. Il modello costruisce due grafi: un grafo non orientato $\mathcal{G}^u$ che cattura le correlazioni geospaziali e un grafo orientato $\mathcal{G}^d$ che cattura le relazioni temporali. Progettando nuovi termini variazionali con norma $\ell_2$ e $\ell_1$ per quantificare e promuovere la levigatezza del segnale sul grafo orientato, e basandosi sul metodo dei moltiplicatori di direzione alternata (ADMM), l'articolo progetta un algoritmo iterativo che viene srotolato come rete feedforward per l'apprendimento dei parametri guidato dai dati. Gli esperimenti dimostrano che il modello mantiene prestazioni competitive nella previsione del traffico riducendo significativamente il numero di parametri.

Contesto di Ricerca e Motivazione

Definizione del Problema

La previsione del traffico è un importante problema di modellazione di dati spazio-temporali che richiede di catturare simultaneamente:

1. Correlazione Spaziale: la correlazione tra stazioni di monitoraggio in prossimità geografica
2. Dipendenza Temporale: la relazione di influenza delle osservazioni storiche sul futuro

Limitazioni dei Metodi Esistenti

1. Transformer Tradizionali: numero enorme di parametri, mancanza di interpretabilità, vincoli computazionali e di memoria nella distribuzione pratica
2. Metodi Basati su Modelli: tendono a elaborare indipendentemente le dimensioni spaziali e temporali, non sfruttando pienamente le relazioni spazio-temporali
3. Metodi di Deep Learning Esistenti: sebbene con prestazioni eccellenti, rimangono modelli "scatola nera" con un gran numero di parametri

Motivazione della Ricerca

1. Necessità urgente di modelli leggeri per applicazioni industriali
2. Lo srotolamento di algoritmi (Algorithm Unrolling) fornisce un nuovo paradigma che combina approcci guidati dal modello e guidati dai dati
3. I lavori esistenti utilizzano solo grafi non orientati simmetrici, incapaci di modellare efficacemente relazioni spazio-temporali complesse

Contributi Principali

1. Prima proposta di srotolamento di algoritmi di grafo misto: combina grafi non orientati (spaziali) e grafi orientati (temporali) per modellare relazioni spazio-temporali complesse
2. Termini di regolarizzazione innovativi per grafi orientati: progetta il regolarizzatore di Laplaciano di grafo orientato (DGLR) e la variazione totale di grafo orientato (DGTV)
3. Transformer leggero e interpretabile: realizza una riduzione significativa dei parametri (solo il 6,4% di PDFormer) tramite srotolamento dell'algoritmo ADMM
4. Contributo Teorico: dimostra che la definizione di frequenza di grafo orientato si riduce a frequenze di Fourier classiche nel caso di grafi lineari orientati non ponderati

Dettagli del Metodo

Definizione del Compito

Dato N stazioni di monitoraggio con osservazioni in T+1 istanti di tempo precedenti, prevedere lo stato del traffico nei successivi S istanti di tempo. L'input è un segnale spazio-temporale parzialmente osservato $y \in \mathbb{R}^M$, l'output è un segnale spazio-temporale completo $x \in \mathbb{R}^{N(T+S+1)}$.

Costruzione di Grafo Misto

Grafo Non Orientato $\mathcal{G}^u$

• Connette nodi in posizioni geograficamente vicine nello stesso istante di tempo
• Cattura la correlazione spaziale
• Utilizza matrice di adiacenza simmetrica $W^u$

Grafo Orientato $\mathcal{G}^d$

• Connette nodi dall'istante di tempo $\tau$ agli istanti $\tau+1, ..., \tau+W$ dello stesso nodo
• Cattura le relazioni causali temporali
• Utilizza matrice di adiacenza non simmetrica $W^d$

Progettazione di Termini Variazionali per Grafo Orientato

Termine con Norma $\ell_2$: Regolarizzatore di Laplaciano di Grafo Orientato (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$

dove $L_r^d = I - W_r^d$ è la matrice di Laplaciano di passeggiata casuale e $W_r^d = (D^d)^{-1}W^d$ è la matrice di adiacenza normalizzata per riga.

Termine con Norma $\ell_1$: Variazione Totale di Grafo Orientato (DGTV)

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

Funzione Obiettivo di Ottimizzazione

$\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$

dove $H$ è la matrice di campionamento e $\mu_u, \mu_{d,2}, \mu_{d,1}$ sono parametri di peso.

Progettazione dell'Algoritmo ADMM

Introducendo variabili ausiliarie $\phi$, il problema di ottimizzazione viene trasformato in: $\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.t. } \phi = L_r^d x$

Risoluzione dei Sottoproblemi

1. Sottoproblema $x$: risolto tramite metodo del gradiente coniugato per sistemi lineari
2. Sottoproblema $\phi$: operazione di soglia morbida $\phi_i^{\tau+1} = \text{sign}(\delta) \cdot \max(|\delta| - \rho^{-1}\mu_{d,1}, 0)$ dove $\delta = (L_r^d)_i x^{\tau+1} - \rho^{-1}\gamma_i^\tau$

Modulo di Apprendimento del Grafo

Apprendimento di Grafo Non Orientato (UGL)

Calcola la similarità tra nodi utilizzando la distanza di Mahalanobis: $d^u(i,j) = (f_i^u - f_j^u)^T M (f_i^u - f_j^u)$

I pesi degli archi vengono calcolati tramite funzione esponenziale normalizzata: $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))}}$

Apprendimento di Grafo Orientato (DGL)

Calcola similmente i pesi degli archi orientati utilizzando la matrice di metrica $P$.

Architettura della Rete

Implementa ogni iterazione ADMM come strato neurale:

• 5 blocchi ADMM, ogni blocco con 25 strati
• Modulo di apprendimento del grafo inserito prima di ogni blocco
• Utilizza meccanismo di attenzione multi-testa (4 moduli di apprendimento del grafo paralleli)

Configurazione Sperimentale

Dataset

• METR-LA: dati di velocità del traffico di Los Angeles, 207 nodi, 1315 archi
• PEMS03: dati di flusso del traffico, 358 nodi, 547 archi
• Intervallo di campionamento: 5 minuti
• Divisione dei dati: 6:2:2 (addestramento:validazione:test)

Metriche di Valutazione

• RMSE: radice dell'errore quadratico medio
• MAE: errore assoluto medio
• MAPE: errore percentuale assoluto medio

Metodi di Confronto

Include 6 categorie di metodi di base:

• Basati su modelli: VAR
• Metodi GNN: STGCN, STSGCN
• Metodi GAT: GMAN, ST-Wave
• Metodi Transformer: PDFormer, STAEformer
• Metodi di grafo adattivo: Graph WaveNet, AGCRN
• Modelli lineari semplici: STID, SimpleTM

Dettagli di Implementazione

• Lunghezza di previsione: 30/60/120 minuti (6/12/24 passi)
• Finestra storica: 60 minuti (12 passi)
• Ottimizzatore: Adam, tasso di apprendimento 5×10⁻⁴
• Funzione di perdita: perdita di Huber (δ=1)
• Hardware: NVIDIA GeForce RTX 3090

Risultati Sperimentali

Risultati Principali

Scoperte Chiave

1. Efficienza dei Parametri: utilizza solo il 6,4% dei parametri di PDFormer raggiungendo prestazioni competitive
2. Vantaggi nella Previsione a Lungo Termine: il divario di prestazioni dal miglior metodo diminuisce all'aumentare della lunghezza di previsione
3. Efficienza dei Dati: prestazioni più stabili in condizioni di scarsità di dati

Esperimenti di Ablazione

I risultati dimostrano:

• Il termine DGLR è il più critico per il miglioramento delle prestazioni
• Il termine DGTV fornisce anche un contributo evidente
• La modellazione con grafo orientato è superiore a quella con grafo non orientato

Verifica Teorica

Il Teorema 3.1 dimostra che per grafi lineari orientati non ponderati, il Laplaciano di grafo orientato simmetrizzato $\mathcal{L}_r^d = (L_r^d)^T L_r^d$ è equivalente alla matrice di Laplaciano del grafo lineare non orientato, verificando la razionalità della definizione di frequenza.

Lavori Correlati

Modelli Leggeri

• Modelli di linguaggio di grandi dimensioni: adattamento a basso rango LoRA, quantizzazione dei parametri
• Miglioramento del parlato: attenzione causale locale
• Elaborazione di immagini: elaborazione separata di canali YUV

Metodi di Previsione del Traffico

1. Metodi GNN: STGCN, Graph WaveNet, ecc., focalizzati sulla modellazione spaziale
2. Metodi Transformer: doppi Transformer che elaborano separatamente le dimensioni spazio-temporali
3. Modelli Lineari Semplici: mettono in discussione l'efficacia dei modelli complessi

Srotolamento di Algoritmi

• Srotola le iterazioni dell'algoritmo di ottimizzazione come strati neurali
• Combina interpretabilità matematica e capacità guidate dai dati
• Ha avuto applicazioni di successo nell'elaborazione di immagini

Conclusioni e Discussione

Conclusioni Principali

1. Lo srotolamento di algoritmi di grafo misto realizza con successo un modello di previsione del traffico leggero e interpretabile
2. I termini variazionali di grafo orientato catturano efficacemente le relazioni causali temporali
3. Mantiene prestazioni competitive riducendo significativamente il numero di parametri

Limitazioni

1. Vincolo di Distanza: la distanza di Mahalanobis appresa è non negativa, mentre l'attenzione autonoma tradizionale può essere negativa
2. Sparsità del Grafo: i vincoli basati su connessioni stradali reali limitano la connettività del grafo
3. Finestra Temporale Fissa: la finestra temporale predefinita potrebbe non essere sufficientemente flessibile

Direzioni Future

1. Estensione a distanze con segno e modellazione di grafo più complessa
2. Apprendimento di finestre temporali adattive
3. Applicazione ad altri compiti di previsione spazio-temporale

Valutazione Approfondita

Vantaggi

1. Innovazione Teorica: prima definizione di concetto di frequenza per grafi orientati e progettazione di termini di regolarizzazione corrispondenti
2. Metodo Innovativo: lo srotolamento di algoritmi di grafo misto fornisce una nuova prospettiva per la progettazione di Transformer
3. Valore Pratico: la significativa riduzione dei parametri ha importanza rilevante per la distribuzione pratica
4. Interpretabilità: ogni strato corrisponde a un'iterazione dell'algoritmo di ottimizzazione con significato matematico esplicito

Insufficienze

1. Compromesso di Prestazioni: in alcuni indicatori rimane ancora inferiore ai migliori metodi di base
2. Ambito di Applicabilità: principalmente validato sulla previsione del traffico, la generalizzabilità ad altri compiti spazio-temporali rimane sconosciuta
3. Analisi Teorica: mancano analisi teoriche di convergenza e complessità

Impatto

1. Contributo Accademico: fornisce una nuova prospettiva per l'elaborazione di segnali di grafo e la progettazione di Transformer
2. Valore Pratico: le caratteristiche leggere sono adatte al calcolo edge e agli ambienti con risorse limitate
3. Riproducibilità: fornisce codice open source e impostazioni sperimentali dettagliate

Scenari Applicabili

1. Ambienti con Risorse Limitate: dispositivi mobili, calcolo edge
2. Sistemi di Previsione in Tempo Reale: sistemi di gestione del traffico che richiedono risposta rapida
3. Applicazioni di IA Interpretabile: sistemi critici per la sicurezza che richiedono trasparenza del modello

Riferimenti Bibliografici

L'articolo cita numerosi lavori importanti, inclusi:

• Articolo originale su Transformer (Vaswani et al., 2017)
• Rassegna su srotolamento di algoritmi (Monga et al., 2021)
• Fondamenti di elaborazione di segnali di grafo (Ortega et al., 2018)
• Lavori correlati sulla previsione del traffico (Li et al., 2017; Yu et al., 2018)

Valutazione Complessiva: Questo è un lavoro innovativo nel campo della previsione del traffico che estende con successo il concetto di srotolamento di algoritmi a impostazioni di grafo misto, riducendo significativamente il numero di parametri mantenendo le prestazioni. Sebbene vi sia ancora spazio per miglioramenti in alcuni indicatori, le caratteristiche di leggerezza e interpretabilità conferiscono a questo lavoro un importante valore pratico e significato accademico.