Abstract This paper introduces Graph Convolutional Recurrent Network (GCRN), a deep learning model able to predict structured sequences of data. Precisely, GCRN is a generalization of classical recurrent neural networks (RNN) to data structured by an arbitrary graph. Such structured sequences can represent series of frames in videos, spatio-temporal measurements on a network of sensors, or random walks on a vocabulary graph for natural language modeling. The proposed model combines convolutional neural networks (CNN) on graphs to identify spatial structures and RNN to find dynamic patterns. We study two possible architectures of GCRN, and apply the models to two practical problems: predicting moving MNIST data, and modeling natural language with the Penn Treebank dataset. Experiments show that exploiting simultaneously graph spatial and dynamic information about data can improve both precision and learning speed.
Introduction
Standard Recurrent Neural Networks (RNNs) and Long Short-Term Memory (LSTM) networks are powerful tools for modeling sequential data. Extensions like ConvLSTM have successfully adapted these architectures for spatio-temporal data on regular 2D grids, such as video frames. However, many real-world datasets—ranging from meteorological sensor networks and brain fMRI scans to social networks and semantic word relationships—exist on irregular, non-Euclidean graphs. This paper addresses the challenge of modeling time-varying data on arbitrary graphs by introducing the Graph Convolutional Recurrent Network (GCRN).
Methodology
The GCRN framework bridges the gap between graph representation learning and sequence modeling. The core innovation lies in replacing standard matrix multiplications or Euclidean convolutions with spectral graph convolutions. These convolutions are approximated by Chebyshev polynomials, resulting in filters that are strictly localized to a $K$-hop neighborhood and computationally efficient, scaling linearly with the number of edges.
The authors propose two primary architectures:
- Model 1 (Stacked): A Graph CNN acts as a spatial feature extractor at each time step $t$. The resulting feature vectors are then passed into a standard fully-connected LSTM.
- Model 2 (Integrated): A direct generalization of the ConvLSTM. In this model, the internal gates of the LSTM (input, forget, output, and cell states) utilize graph convolutions instead of 2D Euclidean convolutions.
Experimental Setup
The models were evaluated on three distinct tasks:
- Moving MNIST: A synthetic dataset of handwritten digits moving within a 64x64 grid.
- Rotating & Moving MNIST: A variant designed to test rotation invariance, where digits rotate as they move.
- Penn Treebank (PTB): An NLP benchmark. To apply GCRN, the authors constructed a 4-nearest-neighbor graph of the vocabulary based on word2vec embedding distances.
Key Results and Insights
The experiments revealed several significant advantages of the GCRN approach:
- Parameter Efficiency in Video Prediction: On Moving MNIST, Model 2 (Integrated) achieved superior performance (cross-entropy of 3400) compared to a standard LSTM+CNN (3851), while using only 3.7 million parameters—nearly four times fewer than the baseline's 13.5 million.
- Rotation Invariance: Graph spectral filters are inherently isotropic, treating all edges equally. This property allows them to outperform standard CNNs on regular grids for tasks involving rotation, as they do not rely on fixed "up/down/left/right" orientations.
- Graph Regularization in NLP: For language modeling, Model 1 (Stacked) with dropout achieved a test perplexity of 98.67, significantly better than a standalone LSTM (112.98). The graph structure acts as a constraint that helps the model navigate semantic spaces more effectively.
Limitations and Conclusion
While GCRN shows great promise, Model 2 faced challenges in NLP tasks. Replacing dense layers with graph convolutions over a large vocabulary (10,000 nodes) led to a dimensionality explosion in the hidden states. Future work will focus on applying GCRNs to naturally occurring dynamic graphs, such as sensor networks, and exploring dimensionality reduction to make integrated architectures more viable for large-scale language modeling.
Summary updated