PaperlayerView exact revision on arXiv

Source-linked AI summary

FourierGNN: Rethinking Multivariate Time Series Forecasting from a Pure Graph Perspective

Kun Yi, Qi Zhang, Wei Fan, Hui He, Liang Hu, Pengyang Wang, Ning An, Longbing Cao, Zhendong Niu

arXiv:2311.06190v1cs.LGcs.AI

TL;DR

MTS forecasters commonly separate spatial graph modeling from temporal modeling, creating compatibility and unified-dependency challenges. FourierGNN represents each window value as a node in a fully connected hypervariate graph and applies Fourier-space graph operators. Across seven benchmarks, it reports state-of-the-art accuracy with lower training cost and fewer parameters.

  • Problem

    Existing GNN-based MTS methods commonly separate graph networks for spatial dynamics from temporal networks for temporal dependencies.

  • Method

    FourierGNN reformulates each MTS window as a fully connected hypervariate graph whose nodes are individual series values, then stacks Fourier Graph Operators.

  • Results

    More than 10% average accuracy improvement, 14.6% lower training-time cost, and 20% fewer parameters were reported on seven real-world benchmarks.

  • Takeaways & Limitations

    The results support pure graph modeling as an accurate and efficient approach to unified spatiotemporal MTS forecasting.

  • Takeaways & Limitations

    The hypervariate graph assumes all nodes are fully connected because prior graph structure is usually unknown and values may be correlated through time-lag effects.

Abstract

from arXiv · show

Multivariate time series (MTS) forecasting has shown great importance in numerous industries. Current state-of-the-art graph neural network (GNN)-based forecasting methods usually require both graph networks (e.g., GCN) and temporal networks (e.g., LSTM) to capture inter-series (spatial) dynamics and intra-series (temporal) dependencies, respectively. However, the uncertain compatibility of the two networks puts an extra burden on handcrafted model designs. Moreover, the separate spatial and temporal modeling naturally violates the unified spatiotemporal inter-dependencies in real world, which largely hinders the forecasting performance. To overcome these problems, we explore an interesting direction of directly applying graph networks and rethink MTS forecasting from a pure graph perspective. We first define a novel data structure, hypervariate graph, which regards each series value (regardless of variates or timestamps) as a graph node, and represents sliding windows as space-time fully-connected graphs. This perspective considers spatiotemporal dynamics unitedly and reformulates classic MTS forecasting into the predictions on hypervariate graphs. Then, we propose a novel architecture Fourier Graph Neural Network (FourierGNN) by stacking our proposed Fourier Graph Operator (FGO) to perform matrix multiplications in Fourier space. FourierGNN accommodates adequate expressiveness and achieves much lower complexity, which can effectively and efficiently accomplish the forecasting. Besides, our theoretical analysis reveals FGO's equivalence to graph convolutions in the time domain, which further verifies the validity of FourierGNN. Extensive experiments on seven datasets have demonstrated our superior performance with higher efficiency and fewer parameters compared with state-of-the-art methods.

1 Introduction

MTS forecasting must capture temporal dependencies within series and spatial correlations across series. FourierGNN replaces separate spatial and temporal modeling with a unified hypervariate-graph formulation and reports strong accuracy and efficiency.

  • Motivation: Existing GNN forecasters often combine graph networks for spatial dynamics with temporal networks for temporal dependencies.This combination creates uncertain compatibility and increases handcrafted design burden.
  • Hypervariate Graph: A hypervariate graph treats each value in an input window as a node in a space-time fully-connected graph.This represents inter-series and intra-series correlations as unified node-node dependencies.
  • Hypervariate Graph: The formulation abandons separate spatial and temporal modeling in favor of adaptive, higher-resolution spatiotemporal dependencies.It fuses multiple variates and timestamps within one graph representation.
  • FourierGNN: FourierGNN addresses the large hypervariate graphs by using Fourier Graph Operators for efficient graph computation.The architecture is proposed because classic graph networks can be computationally expensive on graphs whose size grows with series count and window length.
  • Results: More than 10% average accuracy improvement, 14.6% lower training-time cost, and 20% fewer parameters were reported against state-of-the-art methods.These results were obtained on seven real-world benchmarks.

2 Related Work

Related work applies GNNs to structural dependencies in MTS, but commonly separates graph-based spatial modeling from temporal modeling. FourierGNN instead motivates a unified spatiotemporal formulation while building on broader Fourier-based forecasting research.

  • GNNs for MTS Forecasting: GNN-based MTS models are used because they can model structural dependencies between variates.Some methods require predefined graphs, while others learn graphs from inter-series correlations or self-attention.
  • GNNs for MTS Forecasting: Most prior approaches use a graph network for spatial correlations and a temporal network for temporal dependencies separately.Examples include AGCRN with GCN and GRU, and GraphWaveNet with GCN and TCN.
  • Fourier Transform: Fourier-based forecasting research includes DFT-based frequency decomposition, wavelet decomposition, and Fourier blocks for complex periodic patterns.These methods generally integrate Fourier theory into neural forecasting architectures.

3 Problem Definition

The problem definition represents a historical multivariate window as input and asks the forecasting function to predict the next τ timestamps. Existing formulations expose separate graph and temporal-network parameters.

  • Task Definition: The input window Xt contains N series observed across T historical timestamps.Each timestamp vector xt contains the multivariate values of all N series.
  • Task Definition: The forecasting task predicts Yt, the next τ timestamps, from the historical window Xt.The predictions are denoted ˆYt and are produced by a parameterized forecasting function Fθ.
  • Existing Formulation: Many existing models rewrite the forecasting function using separate graph-network parameters θg and temporal-network parameters θt.These parameters represent learned spatial-temporal dependencies used for prediction.

4 Methodology

FourierGNN reformulates MTS forecasting on fully connected hypervariate graphs and performs recursive graph operations in Fourier space. Its operators retain graph-convolution expressiveness while reducing complexity for large graphs.

  • 4.1 The Pure Graph Formulation: A hypervariate graph contains NT nodes, with each element of the N×T input window represented as one node.The graph is initialized as fully connected because spatial and temporal correlations are not generally known in advance.
  • 4.1 The Pure Graph Formulation: The hypervariate formulation represents spatial and temporal dependencies jointly as node-node dependencies.It is intended to capture time-lag relationships across variates and timestamps at higher resolution.
  • 4.2 FourierGNN: FourierGNN uses Fourier Graph Operators, which apply learnable transformations to graph features in Fourier space.The design targets the computational cost and optimization difficulty of classic graph networks on large hypervariate graphs.
  • 4.2 FourierGNN: Multiplication by an FGO in Fourier space corresponds to graph shifting or convolution in the time domain.The convolution theorem provides the connection between Fourier-space multiplication and time-domain graph operations.
  • 4.2 FourierGNN: Stacked FGOs recursively combine multi-order graph operations with nonlinear activations and residual output.The recursive products correspond to multi-order convolutions, while σ models nonlinear information diffusion.
  • Theoretical Analysis: Theoretical analysis establishes equivalence between recursive Fourier-space FGO multiplication and multi-order time-domain graph convolutions.Different weights across diffusion orders allow extensive dependencies among graph nodes to be modeled.
  • Complexity Analysis: FourierGNN has O(nd log n + Knd^2) time complexity, compared with O(n^2d + nd^2) for equivalent time-domain operations.The log-linear dependence on node count motivates its efficiency advantage.
  • MTS Forecasting Architecture: For MTS forecasting, the model embeds hypervariate-graph nodes, applies FourierGNN, transforms outputs back with IDFT, and maps them through fully connected layers.The architecture begins from the input MTS and operates on embedded graph representations.

5 Experiments

Experiments on real-world benchmarks evaluate FourierGNN against diverse forecasting and GNN baselines, measuring accuracy, efficiency, component contributions, and learned spatiotemporal representations. FourierGNN reports strong average accuracy improvements alongside lower training costs and parameter volumes.

  • Experimental Setup: Experiments use seven real-world benchmarks spanning traffic, energy, web traffic, electrocardiogram, and COVID-19 applications, with chronological dataset splits.Datasets are min-max normalized; most use a 7:2:1 training-validation-test split, while COVID-19 uses 6:2:2.
  • Experimental Setup: FourierGNN is compared with classical, deep learning, Transformer, frequency-enhanced Transformer, and graph-based forecasting models, including methods with pre-defined graph structures.Evaluation uses MAE, RMSE, and MAPE, with comparative-model parameters tuned on validation data.
  • Main Results: 9.4% lower MAE and 10.9% lower RMSE on average than the best-performing baselines across datasets establish FourierGNN as a new state-of-the-art in Table 1.The evaluation uses input and prediction lengths of 12, and the paper attributes the advantage to simultaneously learning comprehensive spatiotemporal and time-varying dependencies.
  • Main Results: 30.1% and 30.2% average improvements on MAE and RMSE, respectively, over the best baseline are reported for COVID-19 multi-step forecasting.The comparison covers different prediction lengths and includes GNN-based models plus CoST.
  • Model Analysis: 32.2% and 9.5% fewer parameters than GraphWaveNet on Traffic and Wiki, with 5.8% and 23.3% faster training, respectively, demonstrate efficiency gains.FourierGNN has the lowest parameter volume among the compared models; the paper links parameter reduction to shared scale-free parameters for each node.
  • Model Analysis: Ablations support node embedding, dynamic FGOs, residual connections, and multi-order diffusion, while visualizations show distinct temporal patterns and adaptive filtering of correlations and noise.The ablation studies are conducted on METR-LA and COVID-19, and visualization experiments use METR-LA and COVID-19 representations.

6 Conclusion Remarks

FourierGNN reframes multivariate time-series forecasting as pure graph learning through hypervariate graphs and Fourier-domain graph operators. Experiments report strong forecasting performance, efficiency, and parameter savings.

  • 6 Conclusion Remarks: FourierGNN represents each series value as a graph node, uniting spatiotemporal dynamics in a hypervariate graph.The model reformulates forecasting as prediction on this graph and applies Fourier Graph Operators in Fourier space.
  • 6 Conclusion Remarks: FourierGNN achieves state-of-the-art performance with higher efficiency and fewer parameters than existing methods.The conclusion attributes these properties to Fourier-domain matrix multiplication with adequate expressiveness and lower complexity.
  • 6 Conclusion Remarks: The hypervariate graph effectively encodes spatiotemporal inter-dependencies for multivariate forecasting.

B Convolution Theorem

The paper motivates unified graph modeling by emphasizing time-lagged cross-variable dependencies and develops Fourier-domain operators for large fully connected hypervariate graphs. The n-invariant operator reduces costs while retaining forecasting effectiveness.

  • Motivation: Time-lagged dependencies between variables are common in real-world multivariate time series and challenging to model across timestamps.The paper gives financial relationships such as dollar and gold as an example.
  • Hypervariate Graph: Hypervariate graphs connect variables across timestamps to encode temporal, spatial, and time-varying spatiotemporal dependencies together.
  • Fourier Graph Operator: Fourier-domain parameterization uses a complex-valued matrix for translation-invariant kernels and a d×d matrix for the n-invariant fully connected case.The n-invariant formulation uses a shared operator independent of the graph size n.
  • Fourier Graph Operator: The n-invariant FGO resembles a shared-weight convolution filter, reducing parameter volume and computation while operating over embedded MTS features.
  • Effectiveness of n-invariant FGO: The n-invariant FGO achieves slightly better performance on ECG and COVID-19 while avoiding the larger parameters and training costs of the n-variant alternative.The paper describes it as n-agnostic and lightweight, with empirical support from the ablation study.

C.3 Proof of Proposition 1 and Interpretation of FourierGNN

The paper proves that recursive Fourier Graph Operator multiplication corresponds to multi-order graph convolutions in the time domain. It contrasts FourierGNN with GCNs and GATs and describes the benchmark setting used for evaluation.

  • Proof of Proposition 1: Fourier-space recursion with FGOs is equivalent to multi-order graph convolutions in the time domain.The proposition defines graph features, adjacency structure, diffusion matrices, weight matrices, and Fourier transforms for this equivalence.
  • Interpretation of FourierGNN: FourierGNN assigns different weights to neighbors at each diffusion order, enabling it to model complex spatiotemporal dependencies.
  • Compared with Other Graph Neural Networks: Unlike GCNs, FourierGNN uses discrete rather than graph Fourier transforms and avoids eigendecompositions or similarly costly matrix operations.
  • Compared with Other Graph Neural Networks: For complete graphs, K-layer attention costs are proportional to Kn^2, whereas K-layer FourierGNN inference costs are proportional to n log n.
  • Experiments: The evaluation uses seven public multivariate benchmarks spanning solar power, Wikipedia views, traffic, ECG, electricity, COVID-19, and Los Angeles traffic sensors.The experiments compare FourierGNN with representative and state-of-the-art forecasting models.

E.5 Details for Visualization Experiments

The visualization experiments reconstruct learned hypervariate-graph relationships from FourierGNN node representations and inspect them across variables, timestamps, layers, and consecutive days. COVID-19 visualizations specifically expose time-varying county dependencies.

  • Visualization Method: FourierGNN outputs are converted with the inverse discrete Fourier transform into node representations used to calculate a normalized adjacency matrix.
  • Visualization Method: Because the full hypervariate adjacency matrix is too large to display, the study visualizes subgraphs from multiple perspectives.The visualizations cover different variables, timestamps, and model layers.
  • COVID-19 Visualization: Figure 10 displays four 10×10 county sub-adjacency matrices across four consecutive days to reveal time-varying dependencies.The visualization samples 10 of the 55 counties in the COVID-19 dataset.

F Additional Results

Additional experiments show that FourierGNN maintains strong accuracy across prediction lengths, datasets, and graph sizes while improving efficiency. Its advantages are especially evident in multi-step forecasting and large-scale settings.

  • Multi-step Forecasting: FourierGNN outperforms five compared models on Wiki across all prediction lengths, improving MAE, RMSE, and MAPE by 7.4%, 3.5%, and 22.3% on average.The compared models include StemGNN, AGCRN, GraphWaveNet, MTGNN, and Informer.
  • Evaluation Scope: The additional evaluations cover multi-step forecasting on Wiki, METR-LA, and ECG datasets.Figure 5 presents the ECG multi-step prediction comparison, while Tables 9 and 10 report Wiki and METR-LA results.
  • Multi-step Forecasting: FourierGNN improves average METR-LA MAE by 5.7% and RMSE by 1.5% across prediction lengths.The comparison includes seven MTS models and uses the dataset’s predefined graph topology.
  • Scalability: FourierGNN retains a leading edge as Wiki graph size increases, demonstrating scalability on large-scale datasets.The analysis evaluates MAE, RMSE, and MAPE under different numbers of nodes.

G.2 Parameter Analysis

Parameter and component analyses examine diffusion depth, input-window length, embedding size, and architectural variants. The results favor moderate diffusion and embedding choices while identifying embeddings and dynamic FGOs as especially influential.

  • Input Window: Longer input lookback windows improve FourierGNN’s RMSE and MAPE on ECG.The analysis attributes this pattern to learning a more comprehensive hypervariate graph from longer MTS inputs.
  • Embedding Size: Larger embedding sizes improve fitting ability but can cause overfitting when they become too large.Figure 8 analyzes the effect of embedding dimension.
  • Ablation Study: Ablation results show that embedding and dynamic FGO components contribute more to state-of-the-art performance than residual and summation designs.The study compares variants including w/o Embedding, w/o Dynamic FGO, w/o Residual, and w/o Summation.
  • Diffusion Visualization: Visualization of layer outputs examines how FourierGNN’s adjacency patterns evolve across diffusion layers and timestamps.The analysis selects 10 COVID-19 counties and compares the input spectrum with outputs from the first, second, and third layers.

H.2 Visualization of Time-Varying Dependencies Learned by FourierGNN

FourierGNN learns time-varying dependencies among variables through its hypervariate graph structure and Fourier Graph Operators. COVID-19 visualizations show spatial patterns evolving continuously over consecutive days.

  • Time-Varying Dependencies: Heatmaps of 10 randomly selected COVID-19 counties over four consecutive days reveal spatial patterns that continuously evolve over time.The visualization uses adjacency matrices to examine time-varying dependencies among variables.
  • Interpretation: The hypervariate graph and FGOs enable FourierGNN to attend to and exploit time-varying dependencies among variates.The paper links their combination to modeling intricate spatiotemporal relationships.
Loading 2311.06190v1…