A Deep Graph Wavelet Convolutional Neural Network for Semi-supervised Node Classification

CNN achieves great performance on computer vision[1], natural language processing[16], and other fields[17][18][19][20]. Its success motivates researchers to define convolution operators on graphs. In this way, CNN can be generalized to graphs like social networks and citation networks. Related methods are classified into spatial methods and spectral ones.

Spatial methods perform extraction of spatial features for topological graphs based on similar ideas as weighted summation in CNN. Using different sampling methods for neighborhood nodes, such methods calculate the weighted sum of features of sampled nodes and then update node features. For example, MoNet[21] computes weighted neighborhood node features instead of using average values. GraphSAGE[22] presents an inductive framework that leverages node feature information to efficiently give rise to node embeddings for previously unseen data. GraphsGAN[23] generates fake samples to improve performance on graph-based semi-supervised learning.

Spectral methods carry out the convolution on graphs with the help of spectral theory. They perform convolution operations on topological graphs in accordance with the theory of spectral graph. In fact, the concept of graph Fourier transform is derived from graph signal processing. According to graph Fourier transform, graph convolution is defined. With the rapid development of deep learning methods, GCN in spectral methods also appear. Spectral CNN[24] first implements CNN on graphs using graph Fourier transform. GCN[25] motivates the choice of convolutional architecture via a localized first-order approximation of spectral graph convolutions.

Wavelet transform develops the idea of localization of short-time Fourier transform (STFT) and overcomes the weakness that the window size does not change with frequency at the same time. The wavelet transform is a signal encoding algorithm that is sparser than Fourier transform and has a very strong capability of information expression.

D.K. Hammond proposes a method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph[26]. GraphWave[27] learns a multidimensional structural embedding for each node based on the diffusion of a spectral graph wavelet centered at the node. It provides mathematical guarantees on the optimality of learned structural embeddings. Furthermore, GWNN[12] addresses the shortcomings of previous spectral graph CNN methods with graph Fourier transform. It takes graph wavelets as a set of bases instead of eigenvectors of graph Laplacian. GWNN redefines graph convolution based on graph wavelets, achieving high efficiency and high sparsity. Besides, GWNN also detaches the feature transformation from graph convolution and thus yields better results.

It has been proved that features of nodes in a graph would converge to the same values when repeatedly applying graph convolution operations on graphs[7]. In order to relieve such an over-smoothing problem and further enhance the feature extraction capability, several modified models for citation networks have been proposed. For example, JKNet[28] makes use of the jump connection and the adaptive aggregation mechanism to adapt to local neighborhood properties and tasks. IncepGCN takes advantage of the inception network and could be optimized by Dropedge[29]. In particular, GCNII[15] is viewed as an effective deep graph convolutional network, which is analyzed that a $K$-layer GCNII model can express a polynomial spectral filtering of order $K$ with arbitrary coefficients. Though various efforts have been made to improve the performance of deep graph convolution models, it is still shallow models that usually obtain the best result.

Let $G=(V,E)$ be a simple and connected undirected graph, where $V$ represents the set of nodes with $|V|=n$ and $E$ denotes the set of edges among nodes in $V$ with $|E|=m$. Assume A to express the adjacency matrix of $G$. D indicates the diagonal degree matrix with $\textbf{D}_{i,i}=\sum_{j}{\textbf{A}_{i,j}}$. Let $\textbf{L}=\textbf{I}_{n}-\textbf{D}^{-\frac{1}{2}}\textbf{A}\textbf{D}^{-\frac{1}{2}}$ stand for the normalized Laplacian matrix, where $\textbf{I}_{n}$ is the identity matrix with dimensions $n\times n$. Obviously, L is a symmetric positive semidefinite matrix with eigendecomposition $\textbf{L}=\textbf{U}\Lambda\textbf{U}^{T}$, where $\textbf{U}\in\mathbb{R}^{n\times n}$ denotes the complete set of orthonormal eigenvectors and $\Lambda$ is a diagonal matrix of real, non-negative eigenvalues.

We use $\tilde{G}=(V,\tilde{E})$ to indicate the cyclic graph of $G$, i.e., the graph with a cycle attached to each node in $G$. Correspondingly, the adjacency matrix of $\tilde{G}$ is $\tilde{\textbf{A}}=\textbf{A}+\textbf{I}_{n}$ and the diagonal degree matrix is $\tilde{\textbf{D}}=\textbf{D}+\textbf{I}_{n}$. Let $\tilde{\textbf{L}}=\textbf{I}_{n}-\tilde{\textbf{D}}^{-\frac{1}{2}}\tilde{\textbf{A}}\tilde{\textbf{D}}^{-\frac{1}{2}}$ expresses the normalized Laplacian matrix of the cyclic graph $\tilde{G}$.

In this paper, we build a deep graph wavelet convolutional network (DeepGWC). On the basis of the above-mentioned, we define the $l$-th layer of DeepGWC as

where $\sigma$ is the activation function, $\textbf{H}^{l^{\prime}}$ is the results of graph convolution on H, and $\textbf{W}^{l^{\prime}}$ is the optimized feature transformation matrix. $\textbf{H}^{l^{\prime}}$ and $\textbf{W}^{l^{\prime}}$ in Eq. (7) are described as follows:

where $\alpha$ represents the ratio of the initial residual term $\textbf{H}^{0}$, $\beta_{l}$ is the ratio of the original feature transformation matrix $\textbf{W}^{l}$ of the $l$-th layer, and $0\leq\alpha,\beta\leq 1$. $\tilde{\textbf{P}}^{\prime}$ in Eq. (8) is given by

where $\gamma$ stands for the ratio of the graph wavelet term and $0\leq\gamma\leq 1$. As described in subsection III-C2, F is optimized with static elements, i.e., the modified F is the product of a static constant $f$ and the identity matrix. In fact, $\gamma$ and $f$ could be combined and the first item of Eq. (10) could be written as

However, to emphasize that we combine the Fourier bases and the wavelet bases, we still treat $\gamma$ and $f$ as two separate parameters later, i.e., we perform experiments according to Eq. (10). In this way, we could keep consistency with the form of vanilla wavelet bases in Eq. (6) to emphasize our modification about the filtering matrix F.

There are the three key hyperparameters, i.e., $\alpha$, $\beta$, and $\gamma$ in our DeepGWC model. Through adjusting such three parameters, the DeepGWC could be reduced to the following basic models like:

• •

  With $\alpha=0$, $\beta=1$ and $\gamma=0$, Eq. (7) can be simplified to Eq. (4) and our DeepGWC model is equivalent to the vanilla GCN model[25].

• •

  With $\alpha=0$, $\beta=1$ and $\gamma=1$, Eq. (7) can be simplified to Eq. (6) and our DeepGWC model is then reduced to the GWNN model[12].

• •

  With $\alpha\neq 0$, $\beta=0$ and $\gamma=0$, the weight matrix $\textbf{W}^{l}$ is ignored and our DeepGWC model then functions like the APPNP model[13].

• •

  With $\alpha\neq 0$, $\beta\neq 0$ and $\gamma=0$, the weight matrix $\textbf{W}^{l}$ is ignored and our DeepGWC model then resembles the GCNII model[15].

There are two hyperparameters in the calculation of graph wavelets in general. $s$ denotes the scaling parameter and $t$ stands for the threshold of $\psi_{s}$ and $\psi_{s}^{-1}$. Elements that are less than $t$ are ignored and reset to zero in $\psi_{s}$ and $\psi_{s}^{-1}$. Following the parameter settings of [12], we select the values of $s$ and $t$. For Cora, we set $s=1.0$, $t=1e-4$, and the calculated density of wavelet bases is 2.81%. For Citeseer, we set $s=0.7$, $t=1e-5$, and the density value is 1.52%. For Pubmed, we set $s=0.5$, $t=1e-7$, and the density value is 5.03%. We also provide the density values of wavelet bases. The wavelet bases with low density would not give rise to the calculation burden too much.

Note that we employ a linear connection layer before the graph convolution layers of DeepGWC that projects the original feature dimension on the hidden embedding dimension $\textbf{H}^{0}$. Similarly, there is also a linear connection layer after the graph convolution layers that maps the hidden embedding dimension to the output layer Y, which has the same number of neurons as classes delivered in the dataset. Then we perform the logarithm-softmax operation below:

where Z denotes the actual output of the whole DeepGWC model. In the experiments, the negative log likelihood (NLL) loss function is exploited. Moreover, the proportion of nodes classified correctly is used as the metric to evaluate the accuracy of models. We adopt the Adam optimizer to train our DeepGWC. Following [15], we set $\beta_{l}=\log(1+\eta/l)\approx\eta/l$ where $\eta$ is a hyperparameter and $l$ means the $l$-th layer of DeepGWC. Dropout is adopted to avoid the overfitting issue.

On Cora, Citeseer, and Pubmed, we follow the parameter settings of the vanilla GCN[25] to ensure impartial performance comparison. For every dataset, 20 labeled nodes per class are adopted for training. In order to optimize the parameters of the DeepGWC model, 500 samples are used for validation and 1,000 ones for testing so as to get final results.

We report the experimental results of the proposed model yielded on three datasets including Cora, CiteSeer, and Pubmed as shown in Table II. We quote the experimental results of Spectral CNN[24], ChebyNet[30], GCN[25], and GWNN[12] that are already reported in [12]. The results of GAT[32], APPNP[13], JKNet[28], and IncepGCN[29] are provided according to [15]. For Cora, CiteSeer, and Pubmed, the depths of JKNet[28] are 4, 16, and 32, respectively, while the depths of IncepGCN[29] are 64, 4, and 4, respectively. By contrast, our DeepGWC model has depths of 64, 64, and 32, respectively. The others are all shallow models.

For the DeepGWC, we utilize the Adam Optimizer with a learning rate of 0.001. The detailed hyperparameters of DeepGWC of Table II are given as follows. Let $f$ stand for the element of the filtering matrix F, which is searched over (0.4, 0.8, 1.2, 1.6). Suppose that $L$ represents the number of graph wavelet convolution layers in DeepGWC, $d$ represents the dimension of hidden layers. We get the results of Table II with the parameters of:

• •

  For Cora, we set $L=64$, $d=64$, $\alpha=0.3$, $\eta=0.8$, $\gamma=0.4$, $f=0.4$.

• •

  For Citeseer, we set $L=64$, $d=256$, $\alpha=0.1$, $\eta=0.8$, $\gamma=0.4$, $f=0.4$.

• •

  For Pubmed, we set $L=32$, $d=512$, $\alpha=0.1$, $\eta=0.4$, $\gamma=0.4$, $f=0.6$.

As for the parameters above, larger datasets require higher hidden feature dimension $d$ to express information as completely as possible. We follow the setting of $\alpha$ and $\eta$ of GCNII[15] basically for the three datasets. The proportion of wavelet bases in the combined bases is reflected in the value of $\gamma\cdot f$, which is 0.16 for Cora and Citeseer, and 0.24 for Pubmed. The proportion of wavelet bases for Pubmed is higher than that for Cora and Citeseer because there are more nodes in Pubmed than Cora and Citeseer obviously. The locality of wavelet bases is important in the case of a large number of nodes.

Analyzing Table II, the DeepGWC improves GCNII[15] and achieves the best results among all the shallow and deep graph models on the three benchmark datasets. The average accuracies on the three datasets of DeepGWC is higher than that of the other models by at least 1.3%. We believe that the adaptability of our DeepGWC plays an important role in obtaining the best results for semi-supervised node classification problems. DeepGWC outperforms GCNII on every dataset, which indicates the excellence of wavelet bases. In addition, for DeepGWC with 8 graph wavelet convolution layers, we utilize the t-SNE algorithm[35] to visualize the learned embeddings during training on the Cora dataset. As shown in Fig.1, different colors represent different classes of articles. The difference between features of different classes become more obvious as the training proceeds.

We further investigate the influence of network depths on model performance. Table III shows the classification accuracy vs. the network depth. For every dataset, the best accuracy with a fixed number of layers is marked in bold. For specific datasets and methods, the cell with a grey background in each row gives the best result in that row, i.e., the best number of layers. We report the classification results of GCN[25], JKNet[28], IncepGCN[29], GWNN[12], GCNII[15], and our DeepGWC model with 2, 4, 8, 16, 32, and 64 layers, where Dropedge[29] is further equipped with GCN[25], JKNet[28], and IncepGCN[29], respectively.

It is easy to see from Table III that our DeepGWC model improves GCNII[15] and yields the best results with all numbers of layers. The accuracy of the DeepGWC model becomes better roughly as the number of layers increases. GCN[25] and dropped GCN[29] do have good results with 2 layers, but their performance gets worse rapidly when stacking much more layers. Meanwhile, JKNet[28] and IncepGCN[29] reach their best results with higher layers, but the accuracy is still not guaranteed when the number of layers exceeds 32 layers. GWNN[12] suffers more from the over-smoothing problem than the vanilla GCN[25]. Besides, there exists a serious memory issue on Pubmed when using GWNN[12] with more than 4 layers. Among the baselines, the performance of GCNII[15] is exceptionally good because of its success in reliving the over-smoothing problem. The proposed DeepGWC improves GCNII with wavelet bases further.

We accomplish the comparison of DeepGWC with all the converted models GCN[25], GWNN[12], and GCNII[15] models as described in Subsection III-E and accordingly complete the ablation study. Fig.2 shows the classification accuracy vs. the number of layers of our DeepGWC model and the three relevant baselines which motivate our study. It is readily observed from Fig. 2 that the performance of both GCN[25] and GWNN[12] draws rapidly with the increase of the number of layers, while both GCNII[15] and DeepGWC steadily get better performance when stacking more layers. As a result of the addition of graph wavelet bases, our DeepGWC model achieves better performance than GCNII[15] in the semi-supervised node classification task.

We complete experiments on training with less labeled nodes. MultiStage[33] and M3S[33] are two training methods that enable GCNs to learn graph embeddings with few supervised signals. Following the experiments of M3S[33], we use Label Propagation (LP)[34] and GCN[25] as baselines. For GCN[25], we adopt four training strategies, i.e., Co-training, Self-training, Union, and Intersection additionally[7]. For Cora and Citeseer, we train our DeepGWC model and the baselines with the label rates of 0.5%, 1%, 2%, 3%, and 4%. For Pubmed, we train the models with the label rates of 0.03%, 0.05%, and 0.1% because Pubmed has more nodes. 500 samples are employed for validation and 1,000 ones for testing so as to get final results. We exploit the same number of layers and hyperparameters as that in Table II for GWNN[12], GCNII[15], and DeepGWC. We only adjust the label rates.

Table IV, Table V, and Table VI list the classification results with fewer training samples. Our DeepGWC model obtains the best performance on most of the experiments with lower label rates. The accuracy of DeepGWC is 5.88% higher than that of M3S[33] on average, which focuses on improving the generalization capability of GCNs on graphs with few labeled nodes.

We compare DeepGWC with GCN[25], GWNN[12], and GCNII[15] in the case of less training data more carefully. The comparison results are shown in Fig. 3. It should be noted that DeepGWC performs better when there is less training data. In other words, the gap between DeepGWC and GCNII[15] is more obvious in the case of lower label rates. In experiments on Cora and Citeseer with the label rates of 0.5% and 1%, DeepGWC exceeds GCNII[15] by 4.1% on average while the gap is 0.73% for the label rates of 2%, 3%, and 4%. Besides, comparing GCN[25] and GWNN[12] that are both shallow models, we find that it is also in the case of lower label rates that GWNN[12] yields better results than that with normal label rates. The comparison between DeepGWC and GCNII[15] and the comparison between GWNN[12] and GCN[25] with fewer training nodes further prove the excellent capability of feature extraction of graph wavelets. It suggests that graph wavelets succeed in extracting useful information even with less labeled nodes.