GRAPH EXPANSION IN PRUNED RECURRENT NEURAL NETWORK LAYERS PRESERVES PERFORMANCE

Suryam Arnav Kalra, Pabitra Mitra, Arindam Biswas, Biswajit BasuICLR 2024 · OpenReview

TL;DR

This paper investigates the "lottery ticket hypothesis" in recurrent neural networks (RNNs and LSTMs). They demonstrate that by pruning these networks while preserving their "expander graph" properties, performance can be maintained even at high sparsity levels. This suggests that the underlying graph structure of a network is crucial for its robustness and ability to generalize.

What Problem Does This Paper Address?

The "lottery ticket hypothesis" posits that dense neural networks contain smaller subnetworks ("winning tickets") that, when trained in isolation, can achieve comparable accuracy to the original dense network. This implies that high-capacity networks might be over-parameterized and that sparsity can be achieved without sacrificing performance. While this has been explored for feed-forward networks, its application to recurrent neural networks (RNNs and LSTMs), which are fundamental to sequence modeling, has been less understood. The challenge is to understand how to prune these inherently cyclic structures effectively, ensuring that the pruned network retains its ability to process sequential information robustly, especially in the presence of noise.

Methods

The authors approach this by viewing the recurrent neural network layers as graphs. They "unfold" the recurrent structure over time to create bipartite graphs. The core of their method involves analyzing the "expander graph" properties of these bipartite graphs, specifically focusing on spectral expansion. They use spectral bounds, particularly the Ramanujan bounds, which relate the eigenvalues of a graph's adjacency matrix to its connectivity. Pruning is performed by removing weights with the smallest magnitudes. The key is to ensure that after pruning, the remaining weights still satisfy these expander graph properties, quantified by spectral gap metrics ($\Delta_R$ and $\Delta_S$). They analyze both unweighted and weighted graph representations.

Datasets

  • MNIST: A sequential dataset used for training and evaluating RNNs.
  • Speech Commands: A dataset for limited-vocabulary speech recognition, used for training and evaluating LSTMs.

The paper also introduces variations of the MNIST dataset by adding Gaussian noise with varying variances to study the effect of noise on performance and graph properties.

Key Insights and Ideas

  • Expander Graph Properties are Key: The paper strongly suggests that maintaining high "expander graph" properties (specifically, large spectral gaps) in pruned RNN and LSTM layers is crucial for preserving classification accuracy.
  • Spectral Bounds as a Pruning Guide: The Ramanujan graph bounds ($\Delta_R$ and $\Delta_S$) serve as effective indicators for pruning. When these bounds are satisfied, accuracy remains high.
  • Noise Robustness: The expander graph properties are particularly important for noise robustness. As noise levels increase, networks that lose these properties suffer a more significant performance degradation.
  • Layer-wise Importance: In RNNs, the $W_{xh}$ (input-to-hidden) layer appears to lose its expander graph property before the $W_{hh}$ (hidden-to-hidden) layer, suggesting that the former plays a more significant role in maintaining network performance.
  • Weak Connectivity Leads to Collapse: When the expansion falls below the Ramanujan bounds, accuracy is maintained for a short period before eventually collapsing, indicating a transition to a weakly connected state.

Key Results

  • The paper demonstrates that pruning RNNs and LSTMs while maintaining their expander graph properties leads to preserved classification accuracy.
  • For MNIST, the $W_{xh}$ layer of RNNs loses its Ramanujan property at approximately 50% network density, while the $W_{hh}$ layer retains it until around 12% density.
  • For the Speech Commands dataset, the $W_{xh}$ layer of LSTMs loses the Ramanujan property at 50% density, and the $W_{hh}$ layer at 35% density.
  • Experiments with noisy MNIST data show that networks with satisfied Ramanujan bounds are significantly more robust to noise.

Limitations and Future Work

  • Not discussed in the paper: The paper focuses on spectral and combinatorial expansion properties. Other aspects of network structure or pruning might also be relevant.
  • Future Work: The authors' findings suggest that further research into how to design or prune networks to explicitly maintain these graph properties could lead to more efficient and robust deep learning models. The observed layer-wise differences also open avenues for targeted pruning strategies.

Summary updated

Abstract

Expansion property of a graph refers to its strong connectivity as well as sparseness. It has been reported that deep neural networks can be pruned to a high degree of sparsity while maintaining their performance. We prune recurrent networks such as RNNs and LSTMs, maintaining a large spectral gap of the underlying graphs and ensuring their layer-wise expansion properties. We also study the time unfolded recurrent network graphs in terms of the properties of their bipartite layers. Experimental results for the benchmark sequence MNIST, and Google speech command data with noise show that expander graph properties are key to preserving classification accuracy of RNN and LSTM
BibTeX
@inproceedings{kalra2024graph,
  author = {Suryam Arnav Kalra and Pabitra Mitra and Arindam Biswas and BISWAJIT BASU},
  title = {{GRAPH EXPANSION IN PRUNED RECURRENT NEURAL NETWORK LAYERS PRESERVES PERFORMANCE}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=hG5eu7ikDy},
}
Figure