Pruned Graph Scattering Transforms

Vassilis N. Ioannidis, Siheng Chen, Georgios B. Giannakis

Graph Convolutional Networks (GCNs) have revolutionized machine learning on graphs, but they are often criticized as "black boxes" with controversial design rules. For instance, while some researchers find deep GCNs helpful, others argue they add little value and suffer from over-smoothing.

Graph Scattering Transforms (GSTs) were developed to provide a mathematically rigorous, theoretical foundation for GCNs. By using fixed filter banks and nonlinearities, GSTs create stable, non-trainable representations. However, GSTs have a major structural flaw: they are built as a tree where every node branches out into $J$ new nodes at every layer. For a network with $L$ layers, the number of features grows exponentially as $J^L$. This explosion makes deep GSTs computationally prohibitive.

To solve this, researchers have introduced Pruned Graph Scattering Transforms (pGST), a data-adaptive approach that prunes uninformative branches on-the-fly. The result is a stable, efficient architecture that matches state-of-the-art performance while revealing that different data domains inherently require different network depths.

The Pruning Mechanism

The core innovation of pGST is a pruning algorithm that decides whether to expand a branch of the scattering tree based on the input signal's properties, specifically using a "spectral alignment" criterion.

Illustration of the Graph Scattering Transform tree, showing how signals are filtered and branches are expanded or pruned.
  1. Spectral Alignment: If a specific graph filter's frequency response does not overlap with the energy of the signal at a given node, the output will be negligible. The pGST evaluates the ratio of the output energy to the input energy for each filter.
  2. On-the-fly Decision: If this energy ratio falls below a user-defined threshold ($\tau$), the branch is pruned during the forward pass. This bypasses the need to calculate deeper, uninformative features for that branch.
  3. Theoretical Stability: The authors provide mathematical proof that pGST is stable. If an input signal is perturbed by small noise, the pruning pattern remains consistent, and the resulting features do not change drastically.

Like the original GST, feature extraction remains unsupervised. The resulting pruned features are then fed into a simple classifier (such as an SVM or Gradient Boosting) for the final downstream task.

Domain-Adaptive Architectures

The paper evaluates pGST across diverse domains, including social networks, bioinformatics, scientific collaboration, and 3D computer vision. One of the most striking findings is that the "optimal" architecture emerges naturally from the data itself.

A 3D point cloud (Stanford bunny) and its corresponding deep pruned scattering tree.
  • Social Networks: These are typically "small-world" graphs where information is captured locally. pGST naturally prunes deep branches in these datasets, resulting in a shallow architecture.
  • 3D Point Clouds: Conversely, tasks like 3D point cloud classification (e.g., the ModelNet40 dataset) require capturing multi-scale geometric structures. Here, pGST retains deeper branches, mathematically justifying the use of deep networks in this specific domain.

This adaptive pruning proves that you don't need the whole tree to achieve high performance. In an authorship attribution task, pGST achieved comparable accuracy to the full GST while computing as little as 3.8% to 12.8% of the total possible features.

Performance and Limitations

Overall, pGST performs comparably to—and sometimes better than—the full baseline GST and state-of-the-art GCNs like DiffPool or GraphSage, particularly when training data is scarce.

Furthermore, the computational savings are massive. In a Facebook subnetwork source localization dataset, pGST was nearly two orders of magnitude faster than the full transform. Experiments also confirmed the theoretical stability results, showing that pGST maintains high classification accuracy even as the Signal-to-Noise Ratio (SNR) decreases.

Limitations and Future Work: * Threshold Sensitivity: The pruning is controlled by the hyperparameter $\tau$. While cross-validation helps, optimal pruning still relies somewhat on manual tuning. * Worst-Case Complexity: While pGST is highly efficient in practice, its theoretical worst-case complexity remains exponential if no branches are pruned (though this is exceedingly rare with real-world data). * Supervised Pruning: Currently, pruning is unsupervised and based solely on signal energy. Future iterations could involve "task-aware" pruning, where decisions are influenced directly by the specific labels of the classification task.

By proving stability for a pruned architecture, pGST successfully bridges the gap between rigid mathematical transforms and the flexible, adaptive nature of modern deep learning.

Summary updated

Abstract

Graph convolutional networks (GCNs) have achieved remarkable performance in a variety of network science learning tasks. However, theoretical analysis of such approaches is still at its infancy. Graph scattering transforms (GSTs) are non-trainable deep GCN models that are amenable to generalization and stability analyses. The present work addresses some limitations of GSTs by introducing a novel 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. It is further established that pGSTs are stable to perturbations of the input graph signals with bounded energy. Experiments showcase that i) pGST performs comparably to the baseline GST that uses all scattering features, while achieving significant computational savings; ii) pGST achieves comparable performance to state-of-the-art GCNs; and iii) Graph data from various domains lead to different scattering patterns, suggesting domain-adaptive pGST network architectures.
BibTeX
@inproceedings{ioannidis2020pruned,
  author = {Vassilis N. Ioannidis and Siheng Chen and Georgios B. Giannakis},
  title = {{Pruned Graph Scattering Transforms}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
}
Figure