2025-11-20T09:28:14.240195

Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast

Qi, Do, Liu et al.

Unlike conventional "black-box" transformers with classical self-attention mechanism, we build a lightweight and interpretable transformer-like neural net by unrolling a mixed-graph-based optimization algorithm to forecast traffic with spatial and temporal dimensions. We construct two graphs: an undirected graph $\mathcal{G}^u$ capturing spatial correlations across geography, and a directed graph $\mathcal{G}^d$ capturing sequential relationships over time. We predict future samples of signal $\mathbf{x}$, assuming it is "smooth" with respect to both $\mathcal{G}^u$ and $\mathcal{G}^d$, where we design new $\ell_2$ and $\ell_1$-norm variational terms to quantify and promote signal smoothness (low-frequency reconstruction) on a directed graph. We design an iterative algorithm based on alternating direction method of multipliers (ADMM), and unroll it into a feed-forward network for data-driven parameter learning. We insert graph learning modules for $\mathcal{G}^u$ and $\mathcal{G}^d$ that play the role of self-attention. Experiments show that our unrolled networks achieve competitive traffic forecast performance as state-of-the-art prediction schemes, while reducing parameter counts drastically. Our code is available in https://github.com/SingularityUndefined/Unrolling-GSP-STForecast .

academic

混合グラフアルゴリズムアンローリングによる軽量で解釈可能なTransformerを用いた交通予測

基本情報

論文ID: 2505.13102
タイトル: Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast
著者: Ji Qi, Mingxiao Liu, Tam Thuc Do, Yuzhe Li, Zhuoshi Pan, Gene Cheung, H. Vicky Zhao
分類: cs.LG cs.AI eess.SP
発表日: 2025年10月12日 (arXiv v2)
論文リンク: https://arxiv.org/abs/2505.13102

要旨

本論文は、混合グラフアルゴリズムアンローリングに基づく軽量で解釈可能なTransformerモデルを交通予測に提案している。従来の「ブラックボックス」Transformerとは異なり、本手法は混合グラフ最適化アルゴリズムをアンローリングすることで、解釈可能なTransformer型ニューラルネットワークを構築している。モデルは2つのグラフを構築する：無向グラフ $\mathcal{G}^u$ は地理的空間相関性を捉え、有向グラフ $\mathcal{G}^d$ は時間的関係を捉える。有向グラフ上の信号平滑性を定量化・促進するための新しい $\ell_2$ および $\ell_1$ ノルム変分項を設計し、交互方向乗数法(ADMM)に基づいて反復アルゴリズムを設計し、これをフィードフォワードネットワークにアンローリングしてデータ駆動型のパラメータ学習を行う。実験により、本モデルは競争力のある交通予測性能を維持しながら、パラメータ数を大幅に削減することが示された。

研究背景と動機

問題定義

交通予測は重要な時空間データモデリング問題であり、以下を同時に捉える必要がある：

空間相関性：地理的に近い監視地点間の相関性
時間依存性：過去の観測が将来に与える影響関係

既存手法の限界

従来のTransformer：パラメータ数が膨大で解釈性に欠け、実際の展開時に計算とメモリの制約に直面する
モデルベースの手法：空間と時間の次元を独立に処理することが多く、時空間関係を十分に活用できない
既存の深層学習手法：性能は優れているがなお「ブラックボックス」モデルであり、パラメータ数が多い

研究動機

産業応用における軽量モデルの緊急の需要
アルゴリズムアンローリング(Algorithm Unrolling)がモデル駆動とデータ駆動を組み合わせた新しいパラダイムを提供
既存の研究は正の無向グラフのみを使用しており、複雑な時空間関係を効果的にモデル化できない

核心的貢献

混合グラフアルゴリズムアンローリングの初提案：無向グラフ(空間)と有向グラフ(時間)を組み合わせて複雑な時空間関係をモデル化
革新的な有向グラフ正則化項：有向グラフラプラシアン正則化器(DGLR)と有向グラフ全変動(DGTV)を設計
軽量で解釈可能なTransformer：ADMMアルゴリズムアンローリングにより、パラメータを大幅削減(PDFormerのわずか6.4%)
理論的貢献：有向グラフ周波数定義が無重み有向線グラフの場合に古典的フーリエ周波数に退化することを証明

方法の詳細

タスク定義

N個の監視地点における過去T+1時刻の観測値が与えられたとき、将来S時刻の交通状態を予測する。入力は部分的に観測された時空間信号 $y \in \mathbb{R}^M$ であり、出力は完全な時空間信号 $x \in \mathbb{R}^{N(T+S+1)}$ である。

混合グラフの構築

無向グラフ $\mathcal{G}^u$

同一時刻の地理的に近いノード同士を接続
空間相関性を捉える
対称隣接行列 $W^u$ を使用

有向グラフ $\mathcal{G}^d$

時刻 $\tau$ のノードから $\tau+1, ..., \tau+W$ 時刻の同じノードへ接続
時間的因果関係を捉える
非対称隣接行列 $W^d$ を使用

有向グラフ変分項の設計

$\ell_2$ ノルム項：有向グラフラプラシアン正則化器(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$

ここで $L_r^d = I - W_r^d$ は確率的ウォークラプラシアン行列、 $W_r^d = (D^d)^{-1}W^d$ は行確率的隣接行列である。

$\ell_1$ ノルム項：有向グラフ全変動(DGTV)

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

最適化目的関数

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

ここで $H$ はサンプリング行列、 $\mu_u, \mu_{d,2}, \mu_{d,1}$ は重み付けパラメータである。

ADMMアルゴリズム設計

補助変数 $\phi$ を導入することで、最適化問題を以下に変換する： $\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$

部分問題の求解

$x$ 部分問題：共役勾配法により線形システムを求解
$\phi$ 部分問題：ソフト閾値処理 $\phi_i^{\tau+1} = \text{sign}(\delta) \cdot \max(|\delta| - \rho^{-1}\mu_{d,1}, 0)$ ここで $\delta = (L_r^d)_i x^{\tau+1} - \rho^{-1}\gamma_i^\tau$

グラフ学習モジュール

無向グラフ学習(UGL)

マハラノビス距離を用いてノード相似性を計算： $d^u(i,j) = (f_i^u - f_j^u)^T M (f_i^u - f_j^u)$

辺の重みは正規化指数関数により計算： $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))}}$

有向グラフ学習(DGL)

同様に計量行列 $P$ を用いて有向辺の重みを計算。

ネットワークアーキテクチャ

ADMMの各反復をニューラル層として実装：

5つのADMMブロック、各ブロック25層
各ブロック前にグラフ学習モジュールを挿入
マルチヘッドアテンション機構を使用(4つの並列グラフ学習モジュール)

実験設定

データセット

METR-LA：ロサンゼルス交通速度データ、207ノード、1315辺
PEMS03：交通流量データ、358ノード、547辺
サンプリング間隔：5分
データ分割：6:2:2(訓練:検証:テスト)

評価指標

RMSE：二乗平均平方根誤差
MAE：平均絶対誤差
MAPE：平均絶対パーセント誤差

比較手法

6つのカテゴリーの基線手法を含む：

モデルベース：VAR
GNN手法：STGCN, STSGCN
GAT手法：GMAN, ST-Wave
Transformer手法：PDFormer, STAEformer
適応グラフ手法：Graph WaveNet, AGCRN
シンプルな線形モデル：STID, SimpleTM

実装詳細

予測期間：30/60/120分(6/12/24ステップ)
履歴ウィンドウ：60分(12ステップ)
オプティマイザー：Adam、学習率5×10⁻⁴
損失関数：Huber損失(δ=1)
ハードウェア：NVIDIA GeForce RTX 3090

実験結果

主要結果

データセット	期間	本手法	最良基線	パラメータ数比較
PEMS03	30分	26.10/17.03/18.85	23.71/15.05/18.16	34K vs 531K
PEMS03	60分	27.67/17.46/17.72	25.56/15.97/15.49	(6.4%パラメータ)
METR-LA	60分	12.34/5.18/11.80	11.96/5.49/9.65

主要な発見

パラメータ効率：PDFormerのわずか6.4%のパラメータ数で競争力のある性能を達成
長期予測の優位性：予測期間が長いほど、最良手法との性能差が小さくなる
データ効率：データが不足している場合、より安定した性能を示す

アブレーション実験

変種	PEMS03 (RMSE/MAE/MAPE)	METR-LA (RMSE/MAE/MAPE)
完全モデル	27.67/17.46/17.72	12.34/5.18/11.80
DGTVなし	27.78/17.85/17.90	12.36/5.40/12.31
DGLRなし	30.89/20.02/21.10	12.41/5.35/12.20
無向時間グラフ	27.52/17.87/18.82	12.51/5.42/12.11