Source-linked AI summary
Structured Sequence Modeling with Graph Convolutional Recurrent Networks
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, Xavier Bresson
TL;DR
The paper addresses sequence prediction when observations have dependencies structured by arbitrary graphs rather than simple grids. It proposes GCRN, combining graph CNNs for spatial structure with RNNs for dynamics, and reports improved performance or learning speed across video prediction and language modeling tasks.
Problem
The central challenge is modeling time-varying sequences whose observation features are linked by graph relationships, including irregular spatial and non-spatial domains.
Method
GCRN combines graph CNNs with recurrent networks and evaluates two architectures: stacked CNN–RNN and convLSTM.
Results
Across moving-MNIST video prediction and Penn Treebank language modeling, the models showed improved performance or faster learning under supported experimental settings.
Takeaways & Limitations
Graph spatial information can complement recurrent dynamics for structured sequence prediction, with Model 2 performing well on video prediction and Model 1 showing promising language-modeling performance.
Takeaways & Limitations
The graph CNN filtering formulation has direct spectral-evaluation costs that can be prohibitively expensive for large graphs, motivating localized approximations.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Structured sequences can contain spatial and temporal dependencies on domains more complex than regular grids. GCRN combines graph CNNs with RNNs to model these structures simultaneously.
- Existing CNN–RNN approaches model spatial and temporal regularities effectively for visual sequences, but generally assume grid-like spatial structure.
- Graph-structured sequences include video frames, measurements on irregular station networks, social or biological networks, and vocabulary-graph random walks.
- The proposed architecture combines graph convolution with recurrent processing, while allowing the recurrent component to be replaced by LSTM or GRU networks.
- GCRN merges graph CNNs and RNNs to identify meaningful spatial structures and dynamic patterns in time-varying graph-based data.
2 PRELIMINARIES
Structured sequence modeling predicts future observations whose features are linked through graph relationships. Graph convolutions provide localized, computationally efficient filtering, complementing recurrent models for temporal dependencies.
- 2.1 STRUCTURED SEQUENCE MODELING: Sequence modeling predicts the most likely future length-K sequence from the previous J observations, including conditional word prediction in n-gram language models.
- 2.1 STRUCTURED SEQUENCE MODELING: Structured sequences represent observations as graph signals whose features are linked by pairwise relationships encoded in a weighted graph.
- 2.1 STRUCTURED SEQUENCE MODELING: Exploiting graph structure reduces the dimensionality of possible predictions, making structured sequence problems more tractable.
- 2.2 LONG SHORT-TERM MEMORY: LSTM uses input, forget, and output gates with recurrent states to model long-range dependencies while limiting rapid gradient vanishing.
- 2.3 CONVOLUTIONAL NEURAL NETWORKS ON GRAPHS: Graph CNNs generalize convolution to arbitrary graphs through spatial or spectral formulations, addressing domains without a natural vertex ordering.
- 2.3 CONVOLUTIONAL NEURAL NETWORKS ON GRAPHS: Spectral graph filtering uses the graph Laplacian and Fourier-domain multiplication, but direct evaluation can be expensive because it requires O(n^2) operations.
- 2.3 CONVOLUTIONAL NEURAL NETWORKS ON GRAPHS: A truncated Chebyshev-polynomial expansion makes graph filtering K-localized and computable in O(K|E|) operations.
3 RELATED WORKS
Prior work extends recurrent sequence models to regular grids, trees, graphs, and spatio-temporal graph mixtures. These approaches differ in how they encode spatial relationships and propagate information across structured data.
- Shi et al. extend LSTM to regular grid-structured sequences by replacing fully connected multiplications with two-dimensional convolutions.Their model maintains spatially distributed hidden and cell states, with parameter count independent of the grid dimensions.
- Tree-structured and graph-based recurrent models gather states from children or neighboring nodes through weighted aggregation.Tai et al. study tree topologies, while Liang et al. extend the approach to graphs.
- Jain et al. represent spatio-temporal graphs with a rich recurrent-network mixture assigning recurrent networks to nodes and edges.Communication remains limited to directly connected nodes and edges.
- Li et al. propagate node representations iteratively until convergence, whereas the present work uses graph CNNs to diffuse information across nodes.The two approaches are related through polynomial spectral filters.
4 PROPOSED GCRN MODELS
The proposed GCRN models combine graph convolutions with recurrent sequence learning in two architectures: a stacked graph CNN and LSTM, and a graph-convolutional convLSTM. The formulation supports graph-structured inputs and can extend beyond LSTMs to vanilla RNNs and GRUs.
- 4 PROPOSED GCRN MODELS: The paper proposes two GCRN architectures: a stacked graph CNN with an LSTM and a convLSTM using graph convolutions inside recurrent operations.The architectures are investigated in real-world applications.
- Model 1: Model 1 applies a graph CNN to each graph-structured observation before sequence learning with an LSTM.The graph CNN output xCNN_t feeds the recurrent component, while hidden and cell states remain distributed over graph nodes.
- Model 2: Model 2 generalizes convLSTM to arbitrary graphs by replacing Euclidean two-dimensional convolution with graph convolution.The input, hidden state, and recurrent gates use graph-convolution operations, with cell and hidden states updated through LSTM equations.
- Graph convolutions: Graph convolution kernels use Chebyshev coefficients whose support K determines parameterization independently of the number of nodes.The support K also controls the communication overhead in distributed computing.
- Extensions: The graph-convolutional recurrent blend applies beyond LSTMs to vanilla RNNs and gated recurrent units.The paper also notes that structure-aware LSTM cells can be stacked in encoder-decoder sequence-to-sequence models.
5 EXPERIMENTS
Experiments evaluate GCRN on moving-MNIST and Penn Treebank, showing graph convolutions can capture spatio-temporal structure and improve image performance or language-model learning under suitable conditions.
- 5.1 SPATIO-TEMPORAL SEQUENCE MODELING ON MOVING-MNIST: Moving-MNIST experiments use 20-frame sequences with 10 input and 10 prediction frames, including translating and rotating digits.The graph is a Euclidean-distance k-nearest-neighbor graph over pixel locations, and GCRN uses Model 2 for comparison with prior work.
- 5.1 SPATIO-TEMPORAL SEQUENCE MODELING ON MOVING-MNIST: Graph CNNs can outperform regular CNNs on image grids because isotropic spectral filters use fewer parameters while capturing comparable spatial support.A spectral filter with K = 3 corresponds to a 5×5 patch, but uses 3 rather than 25 parameters.
- 5.1 SPATIO-TEMPORAL SEQUENCE MODELING ON MOVING-MNIST: LSTM+CNN(5 × 5) rivals LSTM+GCNN with K = 3, while larger filters favor GCNNs and model complexity remains linear in filter size.The comparison is reported for K = 5 versus a 9 × 9 CNN filter, with Figure 3 examining filter support and graph construction.
- 5.2 NATURAL LANGUAGE MODELING ON PENN TREEBANK: Penn Treebank contains 1,036,580 words and uses a 10,000-word vocabulary whose word embeddings define a 4-nearest-neighbor graph.The corpus is split into 929k training, 73k validation, and 82k test words; Figure 6 visualizes the resulting adjacency structure.
- 5.2 NATURAL LANGUAGE MODELING ON PENN TREEBANK: Without dropout, standalone LSTM is more accurate than graph LSTM at 120.16 versus 177.14 perplexity, whereas dropout reverses the comparison at 98.67 versus 112.98.Graph structure speeds learning but overfits without dropout; Model 1 outperforms Model 2, whose larger state dimensionality may explain its weaker performance.
6 CONCLUSION AND FUTURE WORK
The paper concludes that GCRN combines graph CNNs and recurrent models for graph-structured temporal data, with promising results in video prediction and language modeling. It identifies broader dynamic-graph applications and stability analysis as future directions.
- 6 CONCLUSION AND FUTURE WORK: GCRN combines graph CNNs for spatial structures with RNNs for dynamic patterns in graph-structured, time-varying data.The study evaluates a stacked CNN-RNN architecture and a convLSTM architecture across video prediction and natural-language modeling.
- 6 CONCLUSION AND FUTURE WORK: Model 2 improves video-prediction results, while Model 1 provides promising language-modeling performance, particularly in learning speed.The conclusion also reports that isotropic filters can outperform classical 2D filters with fewer parameters.
- 6 CONCLUSION AND FUTURE WORK: Graph CNNs and RNNs provide a versatile way to introduce side information, such as word semantics, by structuring a data matrix.The conclusion frames graph structure as a mechanism for exploiting non-grid organization in structured sequences.
- 6 CONCLUSION AND FUTURE WORK: Future work targets naturally dynamic graph signals such as fMRI and sensor networks, alongside analyses of graph-induced stability in RNNs.The authors also plan to investigate whether graph structure prevents unstable dynamic behaviors and whether fast learning can accelerate language modeling.