Efficient and Stable Graph Scattering Transforms via Pruning.

Area of Science:

• Graph Machine Learning
• Deep Learning Architectures
• Signal Processing on Graphs

Background:

• Graph Convolutional Networks (GCNs) excel in graph learning but lack comprehensive analysis.
• Graph Scattering Transforms (GSTs) provide training-free GCNs with analytical benefits but suffer from exponential complexity.
• Deep GCN architectures requiring many layers are hindered by GSTs' computational cost.

Purpose of the Study:

• To develop an efficient Graph Scattering Transform (GST) approach to address the computational complexity limitations of deep GCNs.
• To introduce a novel pruned (p)GST method that retains informative features while bypassing exponential complexity.
• To analyze the stability and sensitivity of the proposed pGST method.

Main Methods:

• Introduced a pruned (p)GST approach guided by a graph-spectrum-inspired criterion.
• Developed an on-the-fly feature retention algorithm to bypass exponential complexity.
• Established theoretical stability guarantees for pGSTs under perturbations.
• Conducted analytical and experimental investigations into pGST sensitivity.

Main Results:

• The pGST approach significantly reduces computational complexity compared to standard GSTs.
• pGSTs demonstrate comparable performance to baseline GSTs and state-of-the-art GCNs in classification tasks.
• Stability of pGSTs was analytically established under graph and network perturbations.
• Numerical tests confirmed comparable performance and substantial computational savings.

Conclusions:

• The pruned Graph Scattering Transform (pGST) offers an efficient and stable alternative for deep graph learning.
• pGSTs achieve competitive performance in graph and 3D point cloud classification tasks.
• The pruning patterns offer insights into domain-specific GCN architecture design.