SEA-GWNN: Simple and Effective Adaptive Graph Wavelet Neural Network

Swakshar Deb, Sejuti Rahman, Shafin RahmanAAAI 2024 · DOI

Abstract

Graph Wavelet Neural Networks (GWNNs) offer a promising approach to handling diverse graph structures by decomposing signals into multi-frequency components. However, traditional adaptive wavelet transforms often require bipartite graph structures, leading to structural degradation during the "splitting" phase. We present SEA-GWNN, a novel framework that utilizes a tree-based lifting scheme. By constructing local computational trees for each node, SEA-GWNN preserves the original graph topology while enabling adaptive filter learning. Our approach achieves state-of-the-art performance across homophilic and heterophilic datasets while maintaining high computational efficiency.

Introduction: The Challenge of Graph Heterophily

Graph Neural Networks (GNNs) typically perform well on homophilic graphs where connected nodes share similar attributes. However, they often falter on heterophilic graphs, where neighbors are likely to belong to different classes. Wavelet-based GNNs address this by using low-pass and high-pass filters to capture both smooth features and sharp differences.

The primary bottleneck in existing adaptive wavelet methods is the lifting scheme, which requires the graph to be bipartite. To satisfy this, traditional methods "split" the graph, often destroying critical connectivity and structural information. SEA-GWNN overcomes this by recognizing that while a global graph may not be bipartite, its local neighborhood—represented as a computational tree—always is. This allows the model to apply powerful lifting schemes without the destructive "lazy wavelet transform" split used in previous works.

Comparison between Vanilla Lifting (a) and the proposed Tree Lifting Transform (b).

Methodology

The SEA-GWNN architecture consists of three primary components designed for flexibility and speed:

  1. Tree-based Lifting Transform: Instead of a global split, the model builds multi-hop computational trees for every node. This allows the application of Split, Predict, and Update steps locally, ensuring the original graph's topology remains intact.
  2. Fusion Module: Traditional lifting schemes often separate frequencies into disjoint subsets. SEA-GWNN introduces a fusion operation that integrates "smooth" approximation and "detail" coefficients, resulting in a richer, multi-scale node representation.
  3. Detachment Strategy: To ensure scalability, the authors decouple higher-order lifting operators. By inducing higher-order structures from lower-order ones through matrix multiplication, the model avoids the computational burden of inverse lifting transforms.
The overall architecture of SEA-GWNN, illustrating the local lifting scheme and the subsequent fusion module for node prediction.

Experimental Results

SEA-GWNN was evaluated against standard benchmarks (Cora, Citeseer, PubMed) and various heterophilic and large-scale datasets (e.g., Squirrel, Penn94, Genius).

  • Accuracy and Adaptability: SEA-GWNN consistently outperformed baselines like GCN, GAT, and MixHop. It showed significant improvements in heterophilic settings where traditional GNNs struggle.
  • Frequency Balancing: The model utilizes a balancing factor ($\alpha$) to tune the importance of high-frequency information. Heterophilic graphs generally benefited from higher $\alpha$ values, while homophilic graphs performed better with lower values.
  • Efficiency: By bypassing the inverse wavelet transform and utilizing the detachment strategy, SEA-GWNN achieves a lower runtime per epoch compared to competitors like UFGConv and the original GWNN, making it suitable for large-scale applications.

Conclusion

SEA-GWNN provides a simple yet effective solution to the structural degradation problem in adaptive graph wavelets. By shifting the lifting transform to a local tree-based level, it preserves graph topology and enhances performance across a wide spectrum of graph types. Future work may extend this adaptive approach to dynamic graphs, leveraging the model's ability to learn filters "in place" without extensive preprocessing.

Summary updated

BibTeX
@inproceedings{deb2024sea,
  author = {Swakshar Deb and Sejuti Rahman and Shafin Rahman},
  title = {{SEA-GWNN: Simple and Effective Adaptive Graph Wavelet Neural Network}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i10.29058},
}
Figure