PaperlayerView exact revision on arXiv

Source-linked AI summary

FC-GAGA: Fully Connected Gated Graph Architecture for Spatio-Temporal Traffic Forecasting

Boris N. Oreshkin, Arezou Amini, Lucy Coyle, Mark J. Coates

arXiv:2007.15531v2cs.LGstat.ML

TL;DR

Multivariate forecasting can benefit from modeling interactions among related series, but existing graph-based approaches may be costly or require expert-defined relationships. FC-GAGA combines a fully connected time-series model with learned temporal and hard graph gates, and reports competitive forecasting with reduced training time.

  • Problem

    Graph-based time-series forecasting can model relationships among series, but existing approaches may be computationally costly, require expert-defined graphs, or rely on Markovian assumptions.

    Source: §1 · p. 1

  • Method

    FC-GAGA combines a fully connected time-series model with learnable temporal and hard graph gates to learn cross-node relationships from data.

    Source: §1 · p. 1, §1.2 · p. 2

  • Results

    FC-GAGA compares favorably with graph-based models on both traffic datasets and reduces training time by at least a factor of three relative to models with similar accuracy.

    Source: §1.2 · p. 2, Quantitative results · p. 4

  • Takeaways & Limitations

    The model can learn non-Markovian relations across variables over layers while maintaining computational efficiency.

    Source: §5 · p. 7

    The empirical evaluation covers two real-life traffic datasets and does not include additional application domains.

    Source: Broader Impact · p. 8

Abstract

from arXiv · show

Forecasting of multivariate time-series is an important problem that has applications in traffic management, cellular network configuration, and quantitative finance. A special case of the problem arises when there is a graph available that captures the relationships between the time-series. In this paper we propose a novel learning architecture that achieves performance competitive with or better than the best existing algorithms, without requiring knowledge of the graph. The key element of our proposed architecture is the learnable fully connected hard graph gating mechanism that enables the use of the state-of-the-art and highly computationally efficient fully connected time-series forecasting architecture in traffic forecasting applications. Experimental results for two public traffic network datasets illustrate the value of our approach, and ablation studies confirm the importance of each element of the architecture. The code is available here: https://github.com/boreshkinai/fc-gaga.

1 Introduction

Graph-aware forecasting can model interactions among related series, while FC-GAGA learns those relationships without requiring a predefined graph. The paper formulates forecasting over graph-linked time series and combines a fully connected forecasting model with learnable temporal and hard graph gates.

1 Introduction

  • Graphical modeling can represent cross-series causal interactions that would otherwise be difficult for a forecasting model to explain and predict.Without graphical modeling, the paper says these interactions become confounding factors.Source: §1 · p. 1
  • Existing graph-based models can be more complex and slower, require expert-defined relationships, or rely on Markovian assumptions.Source: §1 · p. 1

1.2 Summary of Contributions

  • FC-GAGA combines N-BEATS with learnable temporal and hard graph gates to learn relationships without requiring knowledge of the underlying graph.The architecture uses learnable graph weights to gate other nodes’ historical observations before processing them with fully connected residual blocks.Source: §1 · p. 1, §1.2 · p. 2

1.1 Problem Statement

  • The task is to predict each graph node’s H-step future from observations across all nodes through time T.The input at a node is its length-w history ending at time T.Source: §1.1 · pp. 1–2

2 FC-GAGA

FC-GAGA combines graph and time gates with a fully connected time-series model. Its layers learn node-specific graph gates, gate histories using time features, and iteratively refine forecasts.

Time gate block

  • The time gate models time covariates through multiplicative effects derived by a fully connected network and conditioned on node embeddings.Input and output time effects use separate projections because their time features can differ.Source: §2 · p. 2

Graph gate block

  • The hard graph gate weights other nodes’ histories for each target, then uses ReLU to shut off irrelevant node pairs and produce gated histories.The authors report that hard gating encourages sparse inputs; soft gating can overwhelm the fully connected network with many low-magnitude inputs.Source: §2 · pp. 2–3

Complexity analysis

  • The graph gate has O(N^2) complexity, which the authors describe as N times smaller than graph-diffusion approaches with O(N^3) complexity.In practical configurations, total model complexity is dominated by O(N^2Rwd_h).Source: §2 · p. 3

Fully connected time-series block

  • The fully connected residual time-series block conditions its input on node embeddings, each node’s history, and graph-gated information.Residual-block forecasts are summed to form the model forecast.Source: §2 · p. 3

FC-GAGA layer stacking

  • Each layer has its own node embeddings and graph gate, accepts the sum of previous layers’ forecasts, and contributes to the final average forecast.This allows graph structure to change across layers as node representations are updated.Source: §2 · p. 3

3 Empirical Results

On METR-LA and PEMS-BAY, FC-GAGA compares favorably with graph-based and univariate forecasting baselines. Ablations and qualitative analyses examine its gates, layer stacking, and layer-specific forecasts.

Experimental setup

  • The evaluation uses METR-LA and PEMS-BAY traffic-speed readings collected at five-minute intervals, with 70/10/20 train, validation, and test splits.The datasets contain 207 sensors over four months and 325 sensors over six months, respectively.Source: §3 · p. 3

Quantitative results

  • FC-GAGA compares favorably with graph-based models on both datasets, most often outperforming adaptive-graph-only Graph WaveNet and significantly outperforming univariate baselines.The reported comparisons use DCRNN, STGCN, Graph WaveNet, and GMAN among the graph-based baselines; Table 1 reports the error metrics.Source: Quantitative results · p. 4, Table 1 · p. 4

Qualitative results

  • Layer 1 mainly supplies a baseline, layer 2 captures daily seasonality, and layer 3 provides intermittent corrections when recent signals change sharply.Figure 2 shows partial forecasts for a 15-minute-ahead prediction at one METR-LA node.Source: Quantitative results · p. 4, Figure 2 · p. 5
  • Different layers learn different spatial relationships: layer 1 gates less strictly and aggregates more broadly, while later layers concentrate on nodes nearer the forecast target.The authors interpret later layers as refining the baseline using more relevant nearby nodes.Source: Quantitative results · pp. 4–5, Figure 3 · p. 5, Figure 4 · p. 6

Ablation studies

  • More layers substantially improve METR-LA results but have little effect on PEMS-BAY; adding an identity-weight fourth layer noticeably improves performance.The authors suggest more layers for harder problems and fewer for easier ones when computational efficiency is prioritized.Source: Quantitative results · p. 5, Table 2 · p. 6
  • Each graph gate and the time gate improves on multivariate N-BEATS, while their combination improves further; hard-gated sparsification is essential in the tested graph-gate variants.Graph attention is outperformed by the univariate FC-GAGA identity variant.Source: Quantitative results · p. 5

Profiling results

  • About 2× less memory and compute time than Graph WaveNet, and about 10× faster than DCRNN, in the reported profiling experiment.FC-GAGA also used about 5–10× less memory than DCRNN and scaled between datasets with 207 and 325 nodes.Source: Quantitative results · p. 6

4 Related Work

Related work spans multivariate forecasting models, graph-based spatio-temporal architectures, and methods that learn graph structure from data. The supplied passages contrast these approaches with FC-GAGA’s sparse gating and fully connected forecasting design.

Multivariate time-series prediction

  • Neural forecasting models trained across many series can predict a single variable from its history and covariates, whereas FC-GAGA uses past information across series to forecast them jointly.Related approaches also use multiple input series to predict one target, including attention mechanisms for selecting variables and time lags.Source: §4 · p. 6

Graph-based models

  • Graph-based spatio-temporal models combine graph convolutions with recurrent or temporal networks, while other approaches operate directly on spatio-temporal graphs or add attention.Examples include GCNs combined with GRUs, LSTMs, TCNs, or RNNs, as well as graph learning on spatio-temporal graphs.Source: §4 · p. 6
  • Graph structures may be learned before prediction or jointly through adaptive adjacency matrices, but graph attention is unsuitable with a fully connected forecasting module in the reported comparison.The authors attribute an important sparsification effect that prevents overfitting to their graph gate.Source: §4 · p. 7

5 Conclusions

The conclusion presents FC-GAGA as a spatio-temporal forecasting architecture combining fully connected time-series modeling with temporal and graph gates. It reports efficient learning of non-Markovian relationships and favorable accuracy, runtime, and resource use.

Conclusions

  • FC-GAGA combines a fully connected time-series model with temporal and graph gating mechanisms for spatio-temporal forecasting.The conclusion describes both gating mechanisms as generally applicable and computationally efficient.Source: §5 · p. 7
  • The model learns non-Markovian relationships across variables over layers and is reported to achieve excellent generalization performance.Source: §5 · p. 7
  • For comparable accuracy, FC-GAGA is reported to use GPU memory and compute several times more efficiently than existing models.The conclusion says the paper profiles both training and inference runtime.Source: §5 · p. 7

Broader Impact

The broader-impact discussion connects computational efficiency to wider access to advanced AI and identifies traffic, weather, and grid-load forecasting as possible applications. It also notes that empirical evaluation is limited to two datasets and traffic forecasting.

Broader Impact

  • More computationally efficient AI could help small businesses, startups, and regions with limited computing resources use advanced algorithms.The discussion frames efficiency alongside maintaining accuracy.Source: Broader Impact · p. 8
  • The forecasting formulation may apply to traffic management, weather forecasting, and electrical-grid load forecasting, but only traffic has been empirically studied here.The paper reports evaluations on two real-life datasets and identifies both limited dataset coverage and absent studies in other domains as limitations.Source: Broader Impact · p. 8
  • Distribution shift and structural breaks can make training history invalid, so the discussion says measures to recognize and rectify these effects are important.Structural breaks are described as abrupt events that affect the data distribution for an arbitrary duration.Source: Broader Impact · p. 8

A Dataset Details

The evaluation uses METR-LA and PEMS-BAY traffic-speed data, aggregated into five-minute windows and split into training, validation, and test sets.

Dataset details

  • METR-LA has 207 sensors and 34,272 time steps; PEMS-BAY has 325 sensors and 52,116 time steps.METR-LA covers four months in Los Angeles County; PEMS-BAY covers six months in the Bay Area.Source: A Dataset Details · p. 10
  • Both datasets aggregate traffic-speed readings into five-minute windows and use 70%/10%/20% training, validation, and test splits.The split follows the original definition in Li et al. (2018).Source: A Dataset Details · p. 10

B Complexity Analysis Details

The complexity analysis accounts for the graph gate, time gate, and fully connected time-series model when producing forecasts for all nodes.

Complexity analysis

  • The graph gate scales as O(N^2(w+d)), combining the node-interaction matrix with gating N^2w input values.Here N is the number of nodes, w the input-history length, and d the node-embedding width.Source: B Complexity Analysis Details · p. 10
  • The time gate scales as O(N(d+w)d_h + NHd_h), producing a seasonality factor for each node from its time feature.The analysis notes that in most practical situations d+w>H.Source: B Complexity Analysis Details · p. 10
  • The fully connected model scales as O(R(2N^2wd_h + (L−2)Nd_h^2)) for L FC layers and R residual blocks.The first and last residual-block layers scale as O(N^2wd_h), while hidden layers scale as O(Nd_h^2).Source: B Complexity Analysis Details · p. 10
  • In most practical configurations, total model complexity is dominated by O(N^2Rwd_h).Source: B Complexity Analysis Details · p. 10

C Empirical Results Details

The appendix illustrates how FC-GAGA stacks contribute to forecasts and how their learned weights vary across nodes in PEMS-BAY.

Stack contributions

Spatial distribution of weights

Weights for each stack

  • In PEMS-BAY, average weights decrease from stack 1 to stack 2 to stack 3, while average distance grows with weight rank, especially for stacks 1 and 3.Stack 2's distance grows less rapidly, suggesting it often uses nodes farther away.Source: C Empirical Results Details · p. 10, Figure 16 · p. 19

Related papers

Loading 2007.15531v2…