Wavelet-based Graph Neural Networks

Abstract

This thesis focuses on spectral-based graph neural networks (GNNs). In Chapter 2, we use multiresolution Haar-like wavelets to design a framework of GNNs which equips with graph convolution and pooling strategies. The resulting model is called MathNet whose wavelet transform matrix is constructed with a coarse-grained chain. So our proposed MathNet not only enjoys the multiresolution analysis from the Haar-like wavelets but also leverages the clustering information of the graph data. Furthermore, we develop a novel multiscale representation system for graph data, called decimated framelets, which form a localized tight frame on the graph in Chapter 3. Based on this, we establish decimated G-framelet transforms for the decomposition and reconstruction of the graph data at multi resolutions via a constructive data-driven filter bank. The graph framelets are built on a chain-based orthonormal basis that supports fast graph Fourier transforms. From this, we give a fast algorithm for the decimated G-framelet transforms, or FGT, that has linear computational complexity O (N) for a graph of size N. Finally, in Chapter 4, we present a new approach for assembling graph neural networks based on the undecimated framelet transforms which provide a multiscale representation for graph-structured data. With the framelet system, we can decompose the graph feature into low-pass and high-pass frequencies as extracted features for network training, which then defines an undecimated-framelet-based graph convolution UFGConv. The framelet decomposition naturally induces a graph pooling strategy UFGPool by aggregating the graph feature into low-pass and high-pass spectra, which considers both the feature values and geometry of the graph data and conserves the total information. Moreover, we propose shrinkage as a new activation for UFGConv, which thresholds the high-frequency information at different scales.