PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Wavelet Neural Network

Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, Xueqi Cheng

arXiv:1904.07785v1cs.LGstat.ML

TL;DR

Graph CNNs need convolution operators suited to non-Euclidean graphs, while Fourier-based spectral methods face computational and localization limitations. GWNN uses fast, sparse, localized graph wavelets and separates feature transformation from convolution, consistently outperforming previous spectral CNNs on semi-supervised classification across Cora, Citeseer, and Pubmed.

  • Problem

    Graph convolution must handle non-Euclidean neighborhoods, while graph Fourier-based methods require costly eigendecomposition, dense transforms, and produce non-local convolution.

  • Method

    GWNN replaces graph Fourier bases with graph wavelets and detaches feature transformation from graph convolution to improve efficiency and reduce parameter complexity.

  • Results

    GWNN consistently outperforms previous spectral CNNs on semi-supervised classification across Cora, Citeseer, and Pubmed, with 10% improvement on Cora and Citeseer and 5% improvement on Pubmed over Spectral CNN.

  • Takeaways & Limitations

    Sparse, localized, computationally efficient graph wavelets make GWNN's learning process efficient and interpretable, while detaching feature transformation makes it applicable to large graphs.

Abstract

from arXiv · show

We present graph wavelet neural network (GWNN), a novel graph convolutional neural network (CNN), leveraging graph wavelet transform to address the shortcomings of previous spectral graph CNN methods that depend on graph Fourier transform. Different from graph Fourier transform, graph wavelet transform can be obtained via a fast algorithm without requiring matrix eigendecomposition with high computational cost. Moreover, graph wavelets are sparse and localized in vertex domain, offering high efficiency and good interpretability for graph convolution. The proposed GWNN significantly outperforms previous spectral graph CNNs in the task of graph-based semi-supervised classification on three benchmark datasets: Cora, Citeseer and Pubmed.

1 INTRODUCTION

Graph CNNs must adapt convolution to non-Euclidean graph structure, where neighborhoods vary and conventional convolution is not directly defined. GWNN uses graph wavelets to provide efficient, sparse, localized graph convolution and outperforms prior spectral CNNs on three benchmark datasets.

  • Graph structure is non-Euclidean, making conventional convolution difficult because node neighborhoods can vary dramatically in size.
  • Existing graph CNN approaches define convolution through either spatial methods or spectral methods.
  • Spatial methods average neighboring vertex features with learned weighting, but selecting appropriate neighborhoods while preserving weight sharing remains challenging.
  • GWNN replaces Laplacian eigenvectors with graph wavelets and defines convolution through wavelet transform and the convolution theorem.
  • Graph wavelets avoid costly Laplacian eigendecomposition, are sparse and localized, and make graph convolution more efficient and interpretable.
  • GWNN consistently outperforms previous spectral CNNs on graph-based semi-supervised classification across Cora, Citeseer, and Pubmed.

2 OUR METHOD

The method replaces graph Fourier bases with graph wavelets to make graph convolution more efficient, sparse, localized, and flexible. GWNN further reduces parameters by separating feature transformation from convolution.

  • Graph Fourier limitations: Fourier-based graph convolution requires Laplacian eigendecomposition with O(n3) cost, dense matrix multiplication, and lacks vertex-domain localization.
  • Graph wavelet transform: Each graph wavelet represents a signal diffused from a centered node, making the resulting graph convolution localized in the vertex domain.
  • Graph wavelet transform: Graph wavelets replace Laplacian eigenvectors as convolution bases and can be computed with Chebyshev-polynomial approximations in O(m × |E|).
  • Graph wavelet transform: In Cora, more than 97% of elements in ψ−1_s are zero, whereas fewer than 1% of elements in U⊤ are zero.
  • Graph wavelet transform: The continuous scaling parameter s adjusts neighborhood range, with smaller s generally corresponding to smaller neighborhoods.
  • Graph wavelet neural network: GWNN layers transform n × p inputs into n × q outputs using wavelet-domain filters, and the two-layer model is trained for semi-supervised node classification.
  • Reducing parameter complexity: Detaching feature transformation from graph convolution reduces layer parameter complexity from O(n × p × q) to O(n + p × q).This reduction is particularly valuable when graph-based semi-supervised learning has limited labels.

3 RELATED WORKS

Prior graph CNN research divides into spectral and spatial approaches according to how convolution is defined. Related work includes Fourier- and polynomial-based spectral filters, neighborhood aggregation, attention, and graph wavelet constructions.

  • Graph CNN methods are classified as spectral or spatial according to whether convolution is defined through graph transforms or vertex neighborhoods.
  • Spectral methods: Spectral methods include graph Fourier convolution, windowed Fourier approaches, and Chebyshev polynomial parametrization for fast localized filtering.
  • Spatial methods: Spatial methods aggregate neighborhood information using one-hop aggregators, self-attention, or weighted combinations of multiple neighborhood features.
  • Graph wavelets: Graph wavelet research developed graph-adapted constructions, Chebyshev approximations that bypass Laplacian eigendecomposition, and multi-scale community mining.

4 EXPERIMENTS

Experiments evaluate GWNN on semi-supervised node classification across Cora, Citeseer, and Pubmed, while analyzing parameter reduction, performance, sparsity, and interpretability. GWNN improves accuracy over spectral and spatial baselines, and its wavelet representations are sparse and linked to localized document-level patterns.

  • Datasets and setup: GWNN is evaluated on Cora, Citeseer, and Pubmed citation networks using 20 labeled nodes per class for training.Nodes represent documents and edges represent citation links.
  • Detaching feature transformation: Detaching feature transformation reduces parameter complexity from O(n × p × q) to O(K + p × q) in ChebyNet.The detached formulation separates feature transformation from graph convolution.
  • Detaching feature transformation: Fewer parameters substantially improve Pubmed accuracy, while Citeseer shows a small accuracy drop that may reflect reduced modeling capacity.The Pubmed label rate is only 0.003, making overfitting particularly relevant in the reported explanation.
  • Performance of GWNN: GWNN improves classification accuracy on all three datasets, with 10% improvement over Spectral CNN on Cora and Citeseer and 5% on Pubmed.The paper attributes the advantage to localized, flexible diffusion and greater freedom to learn convolution kernels than ChebyNet.
  • Sparsity: Wavelet transform matrices and projected signals are much sparser than their Fourier counterparts on Cora.Sparse wavelets accelerate computation and capture neighboring topology, while projected wavelet signals contain fewer non-zero elements.
  • Interpretability: Wavelet bases provide interpretable feature-document relations: Word984 activates Case-Based documents, whereas Word1177 activates documents across different classes.The top-10 active bases follow the class distributions of the two words in Cora.

5 CONCLUSION

The conclusion presents GWNN as a graph convolutional network that replaces graph Fourier transform with graph wavelet transform. Its local, sparse, and efficient representations, combined with detached feature transformation, support interpretable learning and improved semi-supervised performance on large graphs.

  • Conclusion: GWNN replaces graph Fourier transform with graph wavelet transform to obtain local, sparse, and computationally efficient graph convolution.These properties make the learning process interpretable and efficient.
  • Conclusion: Detaching feature transformation reduces parameter count and dependence on extensive training data, improving GWNN’s applicability to large graphs.The conclusion links this design choice to remarkable performance improvement in graph-based semi-supervised learning.

APPENDIX A LOCALIZED GRAPH CONVOLUTION VIA WAVELET TRANSFORM

The wavelet-based convolution is localized in the vertex domain because graph wavelets and their associated operators preserve local graph structure. Increasing the scaling parameter s expands feature diffusion beyond smaller neighborhoods.

  • Graph wavelets describe the neighboring topology of a target node, supporting localized convolution in the vertex domain.
  • The resulting matrix operator is local because nonzero entries indicate correlations between vertices connected through a wavelet center.
  • As scaling parameter s increases, the range of feature diffusion becomes larger.
  • Figure 4 measures convolutional correlation between the first node and other nodes at different scaling ranges.

APPENDIX B INFLUENCE OF HYPER-PARAMETERS

The scaling parameter s controls the neighborhood range in GWNN, while t primarily affects computational efficiency. Moderate increases in s improve Cora accuracy, but excessive values include irrelevant nodes and reduce accuracy.

  • The scaling parameter s modulates the range of neighboring nodes used by graph convolution.
  • Increasing s from zero enlarges the neighborhood and initially increases accuracy on Cora.
  • When s becomes too large, including irrelevant nodes decreases accuracy on Cora.
  • The hyper-parameter t is used for computational efficiency and has only slight influence on performance.
  • For specific datasets, s and t are selected by validation grid search; an appropriate s is generally [0.5, 1].

APPENDIX C PARAMETER COMPLEXITY OF NODE CLASSIFICATION

GWNN separates feature transformation from graph convolution to reduce parameter complexity. It performs better than ChebyNet on Cora and Citeseer with lower complexity, but remains more complex than ChebyNet on Pubmed.

  • Spectral CNN has parameter complexity O(n ∗p ∗q), whereas ChebyNet reduces it to O(K ∗p ∗q) and GCN uses K=1.
  • GWNN detaches feature transformation from graph convolution to reduce the number of learned parameters.
  • GWNN achieves better performance than ChebyNet on Cora and Citeseer while using smaller parameter complexity.
  • On Pubmed, GWNN has larger parameter complexity than ChebyNet because Pubmed contains a large number of nodes.
  • Selecting wavelets associated with a subset of nodes is proposed as future work to further reduce parameter complexity, potentially with performance loss.

APPENDIX D FAST GRAPH WAVELETS WITH CHEBYSHEV POLYNOMIAL APPROXIMATION

GWNN obtains graph wavelets through Chebyshev polynomial approximation rather than explicit eigendecomposition. The approximation uses a truncated polynomial expansion and recurrence relations for efficient computation.

  • Chebyshev polynomials approximate the graph wavelets ψs and ψ−1_s with computational complexity O(m × |E|).
  • The recurrence Tk(y) = 2yTk−1(y) − Tk−2(y) generates the Chebyshev polynomials efficiently.
  • For y in [-1, 1], Tk(y) = cos(k arccos(y)) and Tk(y) remains within [-1, 1].
  • The spectral domain [0, λmax] is shifted through x = a(y + 1) before applying the polynomial approximation.
  • Truncating the Chebyshev expansion to m terms yields the polynomial approximation used for fast wavelet computation.

APPENDIX E ANALYSIS ON SPASITY OF SPECTRAL TRANSFORM AND LAPLACIAN MATRIX

Graph-wavelet sparsity depends on Laplacian sparsity and the hyper-parameter s. The comparison with GCN identifies wavelet sparsity as a limitation affecting time complexity.

  • Graph-wavelet sparsity depends on the sparsity of the Laplacian matrix and the hyper-parameter s.
  • Table 6 reports sparsity statistics for the spectral transform matrix and Laplacian matrix on Cora.
  • The Laplacian matrix is sparser than graph wavelets, limiting GWNN through higher time complexity than methods using the Laplacian and identity matrices, such as GCN.
  • GWNN localizes spectral graph convolution by replacing graph Fourier transform with graph wavelet transform, unlike ChebyNet and GCN's vertex-domain formulation.
Loading 1904.07785v1…