4.8 Article

Efficient and Stable Graph Scattering Transforms via Pruning

Journal

Publisher

IEEE COMPUTER SOC
DOI: 10.1109/TPAMI.2020.3025258

Keywords

Three-dimensional displays; Scattering; Transforms; Feature extraction; Stability analysis; Perturbation methods; Convolution

Funding

  1. Mitsubishi Electric Research Laboratories
  2. Doctoral Dissertation Fellowship of the University of Minnesota
  3. NSF [171141, 1500713]

Ask authors/readers for more resources

This study introduces an efficient pruned GST approach to address the complexity limitation of traditional GSTs. The pruned GSTs retain informative scattering features while bypassing exponential complexity, and achieve comparable performance to state-of-the-art GCNs.
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 that extract features from graph data, and are amenable to generalization and stability analyses. The price paid by GSTs is exponential complexity in space and time 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 also 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, it is shown that graph data in different domains call for different network architectures, and that the pruning algorithm may be employed to guide the design choices for contemporary GCNs.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.8
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available