Abstract
Graph neural networks (GNNs) have become pivotal tools for processing graph-structured data, leveraging the message passing scheme as their core mechanism. However, traditional GNNs often grapple with issues such as instability, over-smoothing, and over-squashing, which can degrade performance and create a trade-off dilemma. In this paper, we introduce a discriminatively trained, multi-layer Deep Scattering Message Passing (DSMP) neural network designed to overcome these challenges. By harnessing spectral transformation, the DSMP model aggregates neighboring nodes with global information, thereby enhancing the precision and accuracy of graph signal processing. We provide theoretical proofs demonstrating the DSMP's effectiveness in mitigating these issues under specific conditions. Additionally, we support our claims with empirical evidence and thorough frequency analysis, showcasing the DSMP's superior ability to address instability, over-smoothing, and over-squashing.
Introduction
Traditional Graph Neural Networks (GNNs) are powerful but face a "triple threat" of pathologies as they scale in depth or complexity: over-smoothing, over-squashing, and instability. Over-smoothing occurs when node features converge to identical values in deep layers, effectively blurring the signal. Over-squashing refers to information bottlenecks where long-range dependencies are lost when forced through fixed-size vectors across limited edges. Finally, instability makes models sensitive to minor perturbations in graph structure.
To address these, we present Deep Scattering Message Passing (DSMP). DSMP utilizes graph wavelets to operate in the spectral domain, preserving signal energy and allowing for deeper, more stable models that capture both local details and global structure simultaneously.
Methods: Deep Scattering Message Passing
The DSMP architecture integrates Graph Scattering Transforms into the message-passing paradigm. Unlike standard spatial GNNs that focus on immediate neighbors, DSMP decomposes graph signals into multiple frequency bands using graph framelets.
Spectral Transformation and Framelets
DSMP employs low-pass filters to capture global trends and high-pass filters for local details. To maintain computational efficiency, the model uses Chebyshev polynomial approximations, avoiding the costly eigendecomposition of the graph Laplacian.
Learnable Scattering and Implicit Rewiring
While traditional scattering transforms use fixed filters, DSMP introduces learnable weighting parameters ($\theta$). This allows the model to adaptively weight different frequency bands. Mathematically, the use of multi-scale framelets is equivalent to "rewiring" the graph. By creating shortcuts between multi-hop neighbors, DSMP effectively bypasses the bottlenecks that cause over-squashing.
Theoretical Foundations
- Energy Conservation: The authors provide a theoretical proof for "Energy Conservation." By showing that the Dirichlet energy of the features is preserved, they demonstrate why DSMP doesn't suffer from over-smoothing.
- Stability: DSMP is proven to be Lipschitz continuous, ensuring that small input noise results in bounded output changes.
- Graph Density: The framelet approach creates a rewired graph that is strictly denser than the original, providing a wider channel for information flow.
Experimental Results
DSMP was evaluated across diverse benchmarks, including node classification (Cora, Citeseer, OGB-arxiv) and graph classification (PROTEINS, QM7, OGBG-MOLHIV).
Depth and Stability
In experiments on the PROTEINS dataset, DSMP maintained high accuracy and stable Dirichlet energy at depths of up to 50 layers. In contrast, standard GCN and GAT models saw performance collapse after just 10 layers.
Performance Benchmarks
DSMP consistently outperformed state-of-the-art baselines. On the PROTEINS dataset, DSMP achieved 79.6% accuracy, surpassing GCN (70.6%) and GIN (69.7%). It also excelled on bottleneck-heavy datasets like ENZYMES and IMDB, outperforming specialized rewiring methods like SDRF and FoSR.
Discussion and Conclusion
DSMP offers a unified framework to mitigate over-smoothing, over-squashing, and instability. While it introduces higher memory costs ($6E + 2R + O(Nd)$) due to storing multiple filtered versions of the graph, the trade-off is justified by its robustness and depth scalability. Future work will focus on applying DSMP to larger-scale datasets and investigating the interpretability of learned spectral weights to understand domain-specific feature prioritization.
Summary updated