Towards Expressive Spectral-Temporal Graph Neural Networks for Time Series Forecasting

Area of Science:

• Graph Neural Networks
• Time Series Analysis
• Machine Learning Theory

Background:

• Spectral-temporal graph neural networks (GNNs) are crucial for time series forecasting in energy and transportation.
• Existing models lack a clear theoretical understanding of their expressive power.
• Further research is needed to elucidate the foundational principles of these GNNs.

Purpose of the Study:

• To establish a theoretical framework for understanding the expressive power of spectral-temporal GNNs.
• To analyze the limitations and capabilities of linear spectral-temporal GNNs.
• To provide a blueprint for designing effective spatial and temporal modules in spectral domains.

Main Methods:

• Developed a theoretical framework to analyze the expressive power of spectral-temporal GNNs.
• Utilized an extended first-order Weisfeiler-Leman algorithm on dynamic graphs to bound GNN expressiveness.
• Proposed a novel instantiation, Temporal Graph Gegenbauer Convolution (TGGC).

Main Results:

• Linear spectral-temporal GNNs demonstrate universal expressive power under mild assumptions.
• The expressive power is theoretically bounded by the proposed Weisfeiler-Leman variant.
• The proposed TGGC model significantly outperforms existing methods using only linear components, showcasing enhanced efficiency.

Conclusions:

• Spectral-temporal GNNs possess significant theoretical power for time series forecasting.
• The theoretical framework provides practical insights for designing more effective GNN architectures.
• The TGGC model represents a practical and efficient advancement in spectral-temporal GNNs for forecasting.