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

• URL: http://arxiv.org/abs/2505.13102v2
• Date: Sun, 12 Oct 2025 04:45:53 GMT
• Title: Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast
• Abstract summary: We build a lightweight and interpretable transformer-like neural net by unrolling a mixed-graph-based optimization algorithm.<n>We insert graph learning modules for $mathcalGu$ and $mathcalGd$ that play the role of self-attention.<n> Experiments show that our unrolled networks achieve competitive traffic forecast performance as state-of-the-art prediction schemes.
• Score: 28.36772736512295
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 .

Related papers

• Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation [36.25340747048208]
  A crucial assumption in graph signal processing (GSP) is the existence of an underlying graph that captures the pairwise similarities between nodes.<n>For spatial-temporal data in which node-to-node similarities evolve over time, a static spatial graph is insufficient.<n>We model the graph changes in two consecutive adjacency matrices $P = W(2) - W(1)$ across time as a low-rank matrix.
  arXiv  Detail & Related papers  (2026-06-22T23:33:33Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• Sparse Probabilistic Graph Circuits [0.0]
  We introduce Sparse PGCs, a new class of tractable generative models that operate directly on sparse graph representation.<n>In the context of de novo drug design, we empirically demonstrate that SPGCs retain exact inference capabilities, improve memory efficiency and inference speed, and match the performance of intractable DGMs in key metrics.
  arXiv  Detail & Related papers  (2025-08-11T08:47:27Z)
• Graph Spring Neural ODEs for Link Sign Prediction [49.71046810937725]
  We propose a novel message-passing layer architecture called Graph Spring Network (GSN) modeled after spring forces.<n>We show that our method achieves accuracy close to the state-of-the-art methods with node generation time speedup factors of up to 28,000 on large graphs.
  arXiv  Detail & Related papers  (2024-12-17T13:50:20Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Transfer Learning for Latent Variable Network Models [18.31057192626801]
  We study transfer learning for estimation in latent variable network models. We show that if the latent variables are shared, then vanishing error is possible. Our algorithm achieves $o(1)$ error and does not assume a parametric form on the source or target networks.
  arXiv  Detail & Related papers  (2024-06-05T16:33:30Z)
• GraphGPT: Generative Pre-trained Graph Eulerian Transformer [8.675197550607358]
  We introduce a novel generative pre-trained model for graph learning based on the Graph Eulerian Transformer (GET)<n>GraphGPT achieves performance comparable to or surpassing state-of-the-art methods on multiple large-scale Open Graph Benchmark (OGB) datasets.<n> Notably, generative pre-training enables scaling GraphGPT to 2 billion parameters while maintaining performance gains.
  arXiv  Detail & Related papers  (2023-12-31T16:19:30Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
  arXiv  Detail & Related papers  (2022-08-18T09:19:01Z)
• DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
  DADAO is the first decentralized, accelerated, asynchronous, primal, first-order algorithm to minimize a sum of $L$-smooth and $mu$-strongly convex functions distributed over a given network of size $n$. We show that our algorithm requires $mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ local and only $mathcalO(nsqrtchisqrtfracLmulog(
  arXiv  Detail & Related papers  (2022-07-26T08:47:54Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  We prove that the practical single loop accelerated gradient tracking needs $O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$.<n>Our convergence rates improve significantly over the ones of $O(frac1epsilon5/7)$ and $O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
  arXiv  Detail & Related papers  (2021-04-06T15:34:14Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  We consider a structural assumption on the graph Laplacian matrix $L$. The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria. We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
  arXiv  Detail & Related papers  (2020-10-25T18:12:50Z)
• Training (Overparametrized) Neural Networks in Near-Linear Time [21.616949485102342]
  We show how to speed up the algorithm of [CGH+1] for training (mildly overetrized) ReparamLU networks. The centerpiece of our algorithm is to reformulate the Gauss-Newton as an $ell$-recondition.
  arXiv  Detail & Related papers  (2020-06-20T20:26:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.