A Study on Graph-Structured Recurrent Neural Networks and Sparsification with Application to Epidemic Forecasting

Zhijian Li, Xiyang Luo, Bao Wang, Andrea L. Bertozzi, Jack Xin

TL;DR

This paper introduces a Graph-Structured Recurrent Neural Network (GSRNN) for epidemic forecasting that leverages geographical relationships to improve accuracy. They also demonstrate a method to sparsify the network using a transformed-l1 penalty, significantly reducing model complexity without sacrificing predictive power.

What Problem Does This Paper Address?

Epidemic forecasting, particularly for diseases like influenza, is a critical public health challenge. Traditional approaches often treat this as a purely time-series problem, ignoring the inherent spatial nature of disease spread. While some methods have incorporated external data like social media trends, they often lack a principled way to model regional interactions. This paper aims to bridge this gap by developing a model that explicitly incorporates geographical structure to improve forecasting accuracy and efficiency.

Methods

The core of the proposed solution is a Graph-Structured Recurrent Neural Network (GSRNN). This model builds upon standard Recurrent Neural Networks (RNNs), specifically using LSTMs to mitigate vanishing gradient issues. The key innovation is the integration of a graph structure representing spatial relationships between geographical regions (in this case, Health and Human Services regions in the US).

The GSRNN works by:

  • Partitioning Nodes: Regions are classified into two groups based on their historical activity levels: "relatively active" (H) and "relatively inactive" (L).
  • Edge RNNs: For each type of connection between regions (H-H, L-L, H-L), a dedicated edge RNN is trained to model the interaction. These edge RNNs take features from connected nodes and their historical data as input.
  • Node RNNs: After processing information through edge RNNs, the aggregated features are fed into node RNNs, one for each class (H and L), to capture region-specific dynamics.
  • Sparsification: To improve efficiency, the authors employ a transformed-l1 (Tl1) penalty during training. This non-convex penalty encourages sparsity in the network weights, effectively driving many weights to zero. They also explore the standard l1 penalty. Post-training, a hard thresholding is applied to further zero out small weights.

Datasets

The primary dataset used for training and evaluation is CDC influenza data collected from approximately 100 public and 300 private laboratories across the US. This data is organized by Health and Human Services (HHS) regions, providing the geographical structure for the graph. The data spans from 2013 to 2015.

Key Insights and Ideas

  • Spatial Structure Matters: The infectious nature of epidemics inherently involves spatial spread. Explicitly modeling these geographical relationships, as done with the graph structure, leads to improved forecasting accuracy compared to purely time-series models.
  • Hierarchical Modeling: The GSRNN's architecture, with edge RNNs capturing pairwise interactions and node RNNs summarizing regional dynamics, provides a hierarchical way to process spatio-temporal information.
  • Sparsity for Efficiency: Achieving state-of-the-art accuracy is important, but so is model efficiency. The Tl1 penalty offers a powerful way to induce sparsity, leading to smaller, faster models without compromising predictive performance. This is crucial for real-world deployment.
  • Class-based Interactions: Differentiating interactions based on activity levels (high vs. low) allows the model to capture nuanced regional dynamics.

Key Results

  • State-of-the-Art Accuracy: The GSRNN achieved state-of-the-art forecasting accuracy on the benchmark CDC dataset, outperforming models like AR(3), ARGO, and a standard LSTM.
  • Significant Sparsification: The Tl1 penalty, combined with post-training hard thresholding, achieved high sparsity, reducing the number of non-zero weights by up to 70% while maintaining prediction accuracy.
  • Reduced Inference Latency: The sparsification directly leads to reduced inference latency, making the model more practical for real-time applications.
  • Competitive Performance: While ARGO was competitive in some regions, GSRNN showed more consistent performance across all 10 HHS regions.

Limitations and Future Work

  • Graph Construction: The current graph construction relies on geographical adjacency. The authors acknowledge that other strategies, such as inferring connectivity from multivariate Hawkes processes (as used in prior crime forecasting work), could be explored for more powerful graph structures.
  • Sparsification Methods: While the Tl1 penalty is effective, the paper mentions that a relaxed splitting method could enforce sparsity more quickly, and leaves this as future work.
  • Laplacian Smoothing: The authors suggest exploring training RNNs with recently developed Laplacian smoothing gradient descent methods for potential further improvements.
  • Wider Neighborhoods: Future work could also involve exploring wider neighborhood interactions within the graph.

Summary updated

Abstract

We study epidemic forecasting on real-world health data by a graph-structured recurrent neural network (GSRNN). We achieve state-of-the-art forecasting accuracy on the benchmark CDC dataset. To improve model efficiency, we sparsify the network weights via a transformed-\(\ell _1\) penalty without losing prediction accuracy in numerical experiments.
BibTeX
@inproceedings{li2019study,
  author = {Zhijian Li and Xiyang Luo and Bao Wang and Andrea L. Bertozzi and Jack Xin},
  title = {{A Study on Graph-Structured Recurrent Neural Networks and Sparsification with Application to Epidemic Forecasting}},
  booktitle = {WCGO},
  year = {2019},
  url = {https://openreview.net/forum?id=lRTLjbNBDb},
}
Figure