Search papers, labs, and topics across Lattice.
This paper introduces the Efficient Multi-Attention Graph Network (EMAGN), which addresses the scalability issues of self-attention mechanisms in traffic forecasting by linearizing the spatial attention process through learned clustering. By employing adaptive grouping of key and value vectors into super-clusters, EMAGN reduces computational complexity significantly while maintaining high accuracy. Experimental results on benchmark datasets indicate that EMAGN achieves comparable accuracy to full-attention models while drastically improving training and inference times and reducing memory usage, thus enabling larger model configurations on standard hardware.
EMAGN reduces the complexity of traffic forecasting models from quadratic to linear, enabling larger configurations without sacrificing performance.
Traffic forecasting is highly challenging due to complex and nonlinear spatial and temporal dependencies. Self-attention mechanisms have been widely adopted to model dynamic and long-range dependencies, achieving state-of-the-art performance, but suffer from limited scalability due to quadratic computational and memory complexity. To address this, we propose an Efficient Multi-Attention Graph Network (EMAGN) that linearises the spatial attention mechanism itself, inspired by the theory of fast high-dimensional Gaussian filtering. Two learned clustering matrices C_k and C_v adaptively group key and value vectors into M super-clusters, reducing complexity from O(N^2 d) to O(NMd) without sacrificing the flexibility of attention for dynamic dependency modelling. Experimental results on PEMS-BAY and METR-LA show that EMAGN achieves accuracy within 2.7-3.2% MAE of full-attention GMAN while reducing training time by 32%, inference time by 38%, and GPU memory by 58%. Critically, at K=16 attention heads, full-attention GMAN runs out of memory on a standard 11 GB GPU entirely while EMAGN continues to operate, demonstrating a categorical expansion of feasible model configurations. EMAGN also surpasses Linformer and Performer in both accuracy and efficiency within the same backbone, owing to its traffic-network-aware adaptive clustering.
CMU ML