Efficient and Stable Graph Scattering Transforms via Pruning
- 18 September 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 44 (3) , 1232-1246
Abstract
Graph convolutional networks (GCNs) have well-documented performance in various graph learning tasks, but their analysis is still at its infancy. Graph scattering transforms (GSTs) offer training-free deep GCN models, and are amenable to generalization and stability analyses. The price paid by GSTs is exponential complexity that increases with the number of layers. This discourages deployment of GSTs when a deep architecture is needed. The present work addresses the complexity limitation of GSTs by introducing an efficient so-termed pruned (p)GST approach. The resultant pruning algorithm is guided by a graph-spectrum-inspired criterion, and retains informative scattering features on-the-fly while bypassing the exponential complexity associated with GSTs. Stability of the novel pGSTs is established when the input graph data or the network structure are perturbed. Furthermore, the sensitivity of pGST to random and localized signal perturbations is investigated analytically and experimentally. Numerical tests showcase that pGST performs comparably to the baseline GST at considerable computational savings. Furthermore, pGST achieves comparable performance to state-of-the-art GCNs in graph and 3D point cloud classification tasks. Upon analyzing the pGST pruning patterns, graph data in different domains call for different network architectures, and the pruning algorithm may guide the design choices for contemporary GCNs.Keywords
All Related Versions
Funding Information
- Mitsubishi Electric Research Laboratories
- University of Minnesota Foundation
- National Science Foundation (171141, 1500713)
This publication has 22 references indexed in Scilit:
- Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency FramesIEEE Transactions on Signal Processing, 2015
- Invariant Scattering Convolution NetworksIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- Group Invariant ScatteringCommunications on Pure and Applied Mathematics, 2012
- Deep Learning via Semi-supervised Embedding2012
- Wavelets on graphs via spectral graph theoryApplied and Computational Harmonic Analysis, 2011
- Shortest-Path Kernels on Graphs2005
- Space-frequency quantization for wavelet image codingIEEE Transactions on Image Processing, 1997
- Principal component filter banks for optimal multiresolution analysisIEEE Transactions on Signal Processing, 1995
- Best wavelet packet bases in a rate-distortion senseIEEE Transactions on Image Processing, 1993
- Pruning algorithms-a surveyIEEE Transactions on Neural Networks, 1993