Deconvolutional Networks on Graph Data

Abstract:
In this paper, we consider an inverse problem in graph learning domain – “given the graph representations smoothed by Graph Convolutional Network (GCN), how can we reconstruct the input graph signal?" We propose Graph Deconvolutional Network (GDN) and motivate the design of GDN via a combination of inverse filters in spectral domain and de-noising layers in wavelet domain, as the inverse operation results in a high frequency amplifier and may amplify the noise. We demonstrate the effectiveness of the proposed method on several tasks including graph feature imputation and graph structure generation.

heading: 1 Introduction
text: Graph Convolutional Networks (GCNs) [6, 20] have been widely used to transform an input graph structure A and feature matrix X into graph representations H , which can be taken as a mapping function f : (A,X) → H . In this paper, we consider its inverse problem g : (A,H) → X , i.e., given the graph representations smoothed by GCNs, how can we reconstruct the input graph signal? More specifically, we initiate a systematic study of Graph Deconvolutional Networks (GDNs), to reconstruct the signals smoothed by GCNs. A good GDN component could benefit many applications such as reconstruction [44] and generation [19]. For examples in computer vision, several studies [45, 29] have demonstrated that the performance of autoencoders on reconstruction and generation can be further improved by encoding with Convolutional Networks and decoding with Deconvolutional Networks [46]. However, extending this symmetric autoencoder framework to graph-structured data requires graph deconvolutional operations, which remains open-ended and hasn’t been well studied as opposed to the large body of solutions that have already been proposed for GCNs.
Most GCNs proposed by prior works, e.g., Cheby-GCN [6] and GCN [20], exploit spectral graph convolutions [33] and Chebyshev polynomials [15] to retain coarse-grained information and avoid explicit eigen-decomposition of the graph Laplacian. Until recently, [39] and [8] have noticed that GCN [20] acts as a low pass filter in spectral domain and retains smoothed representations. Inspired by prior works in the domain of signal deconvolution [22, 9, 13], we are motivated to design a GDN by an inverse operation of the low pass filters embodied in GCNs. Furthermore, we observe directly reversing a low pass filter results in a high frequency amplifier in spectral domain and may amplify the noise. In this regard, we introduce a spectral-wavelet GDN to decode the smoothed representations into the input graph signals. The proposed spectral-wavelet GDN employs spectral graph convolutions with an inverse filter to obtain inversed signals and then de-noises the inversed signals in wavelet domain. In addition, we apply Maclaurin series as a fast approximation technique to compute both inverse filters and wavelet kernels [8].
We evaluate the effectiveness of the proposed GDN with two tasks: graph feature imputation [35, 44] and graph structure generation [19, 14]. For the former task, we further propose a graph autoencoder (GAE) framework that resembles the symmetric fashion of architectures [29]. The proposed GAE outperforms the state-of-the-arts on six benchmarks. For the latter task, our proposed GDN can
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
enhance the generation performance of popular variational autoencoder frameworks including VGAE [19] and Graphite [14].
The contributions of this work are summarized as follows:
• We propose Graph Deconvolutional Network (GDN), the opposite operation of Graph Convolutional Network (GCN) that reconstructs graph signals from smoothed node representations.
• We study GDN from the perspective of inverse operations in spectral domain and identity the inverse operation results in a high frequency amplifier and may amplify the noise. To solve the noise issue, a de-noising process based on graph wavelet is further proposed.

heading: 2 Preliminaries
text: In this work, we are given an undirected, unweighted graph G = (V,A,X). V is the node set and N = |V | denotes the number of nodes. The adjacency matrix A ∈ RN×N represents the graph structure. The feature matrix X ∈ RN×d represents the node attributes.

heading: 2.1 Convolution on graphs
text: The convolutional layers are used to derive smoothed node representations, such that nodes that are similar in topological space should be close enough in Euclidean space. Formally, the spectral graph convolution on a signal x ∈ RN is defined as:
h = gc ∗ x = Udiag(gc(λ1), . . . , gc(λN ))U>x, (1)
where {λi}Ni=1 are the eigenvalues of the normalized Laplacian matrix Lsym = D− 1 2LD− 1 2 , L and D are the Laplacian and degree matrices of the input graph A respectively, and U is the eigenvector matrix of Lsym = UΛU>. In this work, we focus on GCN [20], one of the popular convolution operations on graphs:
H = GCN(A,X), (2)
where H ∈ RN×v denotes smoothed node representations. Specifically, [39] show that GCN is a low pass filter in spectral domain with gc(λi) = 1− λi, i.e.,
hc = σ(Udiag(gc(λ))U>x), (3)
where σ(·) is the activation function.

heading: 2.2 Deconvolution on graphs
text: The deconvolutional layers are used to recover the original graph features given smoothed node representations. Formally, the spectral graph deconvolution on the smoothed representation h ∈ RN is defined as: x′ = gd ∗ h = Udiag(gd(λ1), . . . , gd(λN ))U>h, (4) With this deconvolution operation, we can use GDNs to produce fine-grained graph signals from the encoded H .
X ′ = GDN(A,H), (5)
where X ′ ∈ RN×d denotes the recovered graph features. We shall further discuss our design of GDN in Section 3.
From the perspective of encoder-decoder, the convolution operation could be used as an encoder and the deconvolution operation as a decoder. We show a schematic diagram of this encoder-decoder perspective in Figure 1.

heading: 3 Graph Deconvolutional Network
text: In this section, we present our design of GDN. Motivated by prior works in signal deconvolution [16], a naive deconvolutional net can be obtained using the inverse filter g−1c (λi) = 1 1−λi in spectral domain. Unfortunately, the naive deconvolutional net results in a high frequency amplifier and may amplify the noise [9, 13]. This point is obvious for g−1c (λi) as the signal fluctuates near λi = 1 if noise exists.

heading: 3.1 Noise analysis
text: Our target is to recover the original graph features given smoothed node representations hc encoded by GCN [20]. Without the noise, it is naive to obtain the closed-form recovery relationship by the inverse operation g−1c (λ) = 1 1−λ directly, i.e.,
x = Udiag(g−1c (λ))U >σ−1(hc), (6)
Here, we assume the activation function σ(·) is an inverse operator, e.g., Leaky ReLU, sigmoid, tanh. Actually, it is quite reasonable to consider such a prototypical model of invertible networks in the theoretical analysis. Otherwise, we need to address an ill-posed inverse problem instead as we automatically lose some information (e.g., null space). Hence, it is impossible to recover the ground-truth even under the noiseless model, see [1] for details.
Graph noise is ubiquitous in real-world applications. Following the convention in signal deconvolution [9] and image restoration [13], let’s consider the white noise model, i.e., ĥ is the smoothed node representations mixed with graph convolution and white noise,
ĥ = σ(Udiag(gc(λ))U>x) + , (7)
where is the white Gaussian noise (i.e., ∼ N (0, σ2IN )). Next, we show that it will amplify the noise if we apply the inverse operation to the white noise model directly. That is,
x′ = Udiag(g−1c (λ))U >σ−1(ĥ), (8)
Proposition 1. Considering the independent white noise model (7) and (8), if the inversed activation function is deferentiable which satisfies ∂σ−1(0) ≥ 1, the variance of x′ is larger than the white noised added on the generative model.
It was worthwhile mentioning that the condition regarding the inverse operator ∂σ−1(0) ≥ 1 is quite reasonable. Actually, it holds for many representative activation functions, including sigmoid, tanh and Leaky ReLU. Please refer to Appendix A for details. Proposition 1 shows the proposed inverse operation may introduce undesirable noise into the output graph. Thus, a de-noising process is necessary thereafter.

heading: 3.2 The proposed GDN
text: To ameliorate the noise issue, we propose an efficient, hybrid spectral-wavelet deconvolutional network that performs inverse signal recovery in spectral domain first, and then conducts a de-noising step in wavelet domain to remove the amplified noise [28].

heading: 3.2.1 Inverse operator
text: Regarding the inverse operation in (6), the core is to explicitly compute eigen-decomposition. We propose to apply Maclaurin series approximation on g−1c (Λ) = ∑∞ n=0 Λ
n and get a fast algorithm as below:
Udiag(g−1c (λ))U = ∑∞ n=0 L n sym. (9)
A detailed derivative of (9) can be found in Appendix E. When truncated low order approximation is used in practice with n ≤ 3 [6], we derive a spectral filter with g−1c (λi) = 1 + λi + λ2i + λ3i . Following [29], we can use another activation function and trainable parameter matrix to estimate σ−1, to avoid the potential non-invertible problem. Thus, the inverse operator becomes:
M = σ((IN + 3∑ n=1 Lnsym)HW3), (10)
where W3 is the parameter set to be learned.
We contrast the difference between inverse operator in this work and other reconstruction methods including [47] and GALA [30].
Inverse operator vs. GCN decoder [47] Compared with GCN decoder [47] which directly uses GCN for signal reconstruction, the proposed inverse operator demonstrates its efficacy in recovering the high frequency signals of the graph, as shown in Figure 3 (b). We shall further discuss this point in Section 3.3.
Inverse operator vs. GALA GALA [30] can be viewed as the first-order approximation towards inverse operator in this work, with a spectral kernel of 1 + λi. The difference is that our inverse operator can well approximate the inverse filter g−1c (λi) = 1 1−λi with third-order polynomials.

heading: 3.2.2 Wavelet de-noising
text: Wavelet-based methods have a strong impact on the field of de-noising, especially in image restoration when noise is amplified by inverse filters [28]. In the literature, many wavelet de-noising methods have been proposed, e.g., SureShrink [9], BayesShrink [5], and they differ in how they estimate the separating threshold. Our method generalizes these threshold ideas and automatically separates the noise from the useful information with a learning-based approach. Consider the input signal of wavelet system is mixed with Gaussian noise, the reasons why wavelet denoising works are: (1) a graph wavelet basis holds the majority of signal energy into a small number of large coefficients,
and (2) Gaussian noise in the original graph domain is again a Gaussian noise in wavelet domain (with the same amplitude), see [16] for details. The core thus becomes how we can separate a small number of large coefficients and the noise in wavelet domain. Given the latter is unknown, we adopt a trainable parameter matrix to linearly transform the noise under zero and useful coefficients bigger than zero, where ReLU is used to eliminate the noise.
Consider a set of wavelet bases Ψs = (Ψs1, . . . ,ΨsN ), where each one Ψsi denotes a signal on graph diffused away from node i and s is a scaling parameter [40], the wavelet bases can be written as Ψs = Ugs(Λ)U> and gs(·) is a filter kernel. Following previous works GWNN [40] and GRAPHWAVE [8], we use the heat kernel gs(λi) = e−sλi , as heat kernel admits easy calculation of inverse wavelet transform with g−1s (λi) = e
sλi . In addition, we can apply Maclaurin series approximation on heat kernel and neglect explicit eigen-decomposition by:
Ψs = ∑∞ n=0 (−1)n n! s nLnsym, (11)
Ψ−1s = ∑∞ n=0 sn n!L n sym, (12)
To cope with the noise threshold estimation problem, we introduce a parameterized matrix in wavelet domain and eliminate these noise coefficients via a ReLU function, in the hope of learning a separating threshold from the data itself. Together with the representation M raised in Section 3.2.1, we derive the reconstructed signal as: X ′ = ΨsReLU(Ψ−1s MW4)W5, (13) where W4 and W5 are trainable parameters.
We then contrast the difference between Wavelet Neural Network (WNN) in this work and other related WNNs including GWNN [40] and GRAPHWAVE [8].
Scalability An important issue in WNN is that one needs to avoid explicit eigen-decomposition to compute wavelet bases for large graphs. Both GRAPHWAVE and GWNN, though trying to avoid eigen-decomposition by exploiting Chebyshev polynomials, still rely integral operations (see Appendix D in [40]) and there is no clear way to scale up. Differently, we use Maclaurin series to approximate wavelet bases, which has explicit polynomial coefficients and can resemble the heat kernel well when n = 3. Please refer to Figure 2 for more details.
De-noising The purpose of both GWNN and GRAPHWAVE is to derive node presentations with localized graph convolution and flexible neighborhood, such that downstream tasks like classification can be simplified. On the contrary, our work implements wavelet neural network in the purpose of detaching the useful information and the noise amplified by inverse operator. Due to the different purpose, our work applies the activation function in wavelet domain while GWNN in the original vertex domain.

heading: 3.3 Visualization
text: In Figure 3, we illustrate the difference between GDN and each component inside by visualizing the reconstructed road occupancy rates in a traffic network. The traffic network targets District 7 of California collected from Caltrans Performance Measurement System (PeMS)1. We select 4438 sensor stations as the node set V and collect their road average occupancy rates at 5pm on June 24, 2020. Following [23], we construct an adjacency matrix A by denoting Aij = 1 if sensor station vj and vi are adjacent on a freeway along the same direction. We reconstruct road occupancy rate of each sensor station with three decoder variants: (b) inverse operator, (c) our proposed GDN, (d) GCN decoder [47]. Here the three variants share the same encoders.
As can be seen, while both GDN and GCN decoders can resemble the input signal in low frequency, GDN decoder retains more high frequency information. For inverse operator decoder, although keeping much high frequency information (mixed with noise), it drops lots of low frequencies, making the decoded signals less similar to the input in Euclidean space.

heading: 4 Experiments
text: We validate the proposed GDN on graph feature imputation [35, 44] and graph generation [19, 14]. The former task reconstructs graph features and the latter generates graph structures.

heading: 4.1 Graph feature imputation
text: In our model, we consider feature imputation as feature recovery on graphs. The model is trained on an incomplete version of feature matrix (training data) and further used to infer the potential missing features (test data).
Datasets We use six benchmark datasets including several domains: citation networks (Cora, Citeseer) [32], product co-purchase networks (Amaphoto, Amacomp ) [26], social rating networks (Douban, Ciao2). For citation networks and product co-purchase networks, we use the preprocessed versions provided by [35] with uniform randomly missing rate of 10%. For Douban, we use the preprocessed dataset provided by [27]. For Ciao, we use a sub-matrix of 7,317 users and 1,000 items. Dataset statistics are summarized in Table 3 in the Appendix.
1http://pems.dot.ca.gov/ 2https://www.ciao.co.uk/
Setup Our graph autoencoder framework consists of an encoder and a decoder. Our encoder consists of two layers of Graph Convolutional Networks (GCN) [20]. Our decoder consists of one layer of proposed GDN, to produce fine-grained graphs. We use the Mean Squared Error (MSE) loss to reconstruct the features. We run 5 trials with different seeds and report the mean of the results. For detailed architecture, please refer to Appendix C. For detailed hyper-parameter settings, please refer to Appendix D. We report Root Mean Squared Error (RMSE).
Baselines We compare with three commonly used imputation methods and three deep learning based imputation models:
• MEAN, which replaces the missing feature entries with the mean values of all observed feature entries.
• KNN, which first identifies the k-nearest neighbor samples and imputes the missing feature entries with the mean entries of these k samples. We set k = 5 in this work.
• SVD [37], which replaces the missing feature entries based on matrix completion with iterative low-rank SVD decomposition.
• MICE [4], which is a multiple regression method that infers missing entries by Markov chain Monte Carlo (MCMC) techniques.
• GAIN [43], which is a deep learning imputation model with generative adversarial training.
• GRAPE [44], which is the state-of-the-art deep learning imputation model based on deep graph representations.
For ablation studies of the graph autoencoder framework specified in Appendix C, we also include the results of decoders using GCN decoder [47], GALA [30], and inverse decoder in Section 3.2.1, to be compared with our proposed GDN. Besides, we compare with popular matrix completion methods in Appendix B for discrete feature recovery.
Results The test RMSE on the six benchmarks are shown in Table 1. Our method performs the best on all datasets, e.g., it beats the second best model GRAPE by 0.02 on Citeseer and 0.031 on Ciao, which shows the superiority of our methods on feature imputation. The feature imputation RMSE with respect to different missing rate is shown in Figure 4. As can be seen, our method performs the best with respect to different missing rate, e.g., it achieves 0.016 improvement over the second best model GRAPE on Citeseer when the missing rate is 70%, and 0.007 improvement over the second best model GRAPE on Amacomp when the missing rate is 30%.
Ablation study We investigate the role of wavelet de-noising in our GDN. We let the four decoder variants share the same depth of layers and parameter size. As observed in Table 1, when decoding by inverse operator, the performance is on a par with that of GCN decoders [47] and outperformed by our GDN decoders on all six datasets, indicating the effectiveness of this hybrid design. The performance of inverse decoder specified in Section 3.2.1 is always better than that of GALA [30], which shows the superiority of our third-order approximation.

heading: 4.2 Graph structure generation
text: Data and baselines We use three molecular graphs: MUTAG [21] containing mutagenic compounds, PTC-MR [21] containing compounds tested for carcinogenicity and ZINC [17] containing druglike organic molecules, to evaluate the performance of GDN on graph generation. Dataset statistics are summarized in Table 4 in the Appendix. We test GDN on two popular variational autoencoder framework including VGAE [19] and Graphite [14]. Our purpose is to validate if GDN helps with the generation performance.
Setup For VGAE and Graphite, we reconstruct the graph structures using their default methods and the features using GDN. The two reconstructions share the same encoders and sample from the same latent distributions. For detailed architecture, please refer to Appendix D. We train for 200 iterations with a learning rate of 0.01. For MUTAG and PTC-MR, we use 50% samples as train set and the remaining 50% as test set. For ZINC, we use the default train-test split.
Results Evaluating the sample quality of generative models is challenging [36]. In this work, we validate the generative performance with the log-likelihood (log p(A|Z)), area under the receiver operating characteristics curve (AUC) and average precision (AP). As shown in Table 2, GDN can improve the generative performance of both VGAE and Graphite in general, e.g., it improve the AP score of Graphite by 16.1% on MUTAG , the AUC score of Graphite by 20.9% on PTC-MR and log p(A|Z) of VGAE by 0.029 on ZINC, which shows the superiority of GDN.

heading: 5 Related work
text: Deconvolutional networks The area of signal deconvolution [22] has a long history in the signal processing community and is about the process of estimating the true signals given the degraded or smoothed signal characteristics [2]. Later deep learning studies [46, 29] consider deconvolutional
networks as the opposite operation for Convolutional Neural Networks (CNNs) and have mainly focused on Euclidean structures, e.g., image. For deconvolutional networks on non-Euclidean structures like graphs, the study is still sparse. [12] proposes the network deconvolution as inferring the true network given partially observed structure. [42] formulates the deconvolution as a preprocessing step on the observed signals, in order to improve classification accuracy. [47] considers recovering graph signals from the latent representation. However, it just adopts the filter design used in GCN and sheds little insight into the internal operation of GDN.
Graph autoencoders Since the introduction of Graph Neural Networks (GNNs) [20, 6] and autoencoders (AEs), many studies [19, 14] have used GNNs and AEs to encode to and decode from latent representations. Although some encouraging progress has been achieved, there is still no work about graph deconvolution that can up-sample latent feature maps to restore their original resolutions. In this regard, current graph autoencoders bypass the difficulty via (1) non-parameterized decoders [19, 7, 24], (2) GCN decoders [14], (3) multi-layer perceptron (MLP) decoders [34], and (4) Laplacian sharpening [30].
Graph feature imputation Feature imputation techniques can be generally classified into two groups: statistical approaches and deep learning models. The former group includes KNN, SVD [37], MICE [4], in which they makes assumptions about the data distribution through a parametric density function. The latter group includes GAIN [43], GRAPE [44]. Recently GRAPE [44] proposes graph feature imputation that assumes a network among items and the network is helpful in boosting the feature imputation performance. A related topic is matrix completion [27, 3, 11] in which it usually makes the assumption of finite and discrete feature values. Differently, both GRAPE and our method can recover both continuous and discrete feature values.
Graph structure generation Graph structure generation techniques can be classified into three groups: one-shot [19, 14, 34], substructure [18] and node-by-node [25]. As this work is more related to the group of one-shot, we refer the readers to [10] for the details of other groups. The group of one-shot generates the entire graph all at once. Representative works include VGAE [19], Graphite [14] and GraphVAE [34]. Both VGAE and Graphite reconstruct graphs based on the similarities of graph structures. Differently, GraphVAE considers both the similarities of structures and node features and reconstructs node features using MLP. In this work, we show that the performance of one-shot graph generators can be improved by reconstructing node features using GDN.

heading: 6 Conclusion
text: In this paper, we present Graph Deconvolutional Network (GDN), the opposite of GCN that recovers graph signals from smoothed representations. The introduced GDN uses spectral graph convolutions with an inverse filter to obtain inversed signals and then de-noises the inversed signals in wavelet domain. The effectiveness of the proposed method is validated on graph feature imputation and graph structure generation tasks.

heading: 7 Limitation
text: Broadly speaking, graph signal restoration is an ill-posed problem. In this regard, the prior knowledge is important for high-quality recovery. This paper only pays attention to vanilla GCN [20] (Kipf & Welling, 2017) and it is not clear whether the spectral-wavelet GDN ideas can be applied to other GNNs, e.g., GAT [38], GIN [41]. Another limitation of this work is that the heat kernel in wavelet parts is not a band-pass filter, as it should be.

heading: 8 Broader Impact
text: This work initiates the restoration of graph signals smoothed by vanilla GCN [20] (Kipf & Welling, 2017). As a sequence, researchers in drug design or molecule generation may benefit from this research, since the visualization and understanding of GCN based representations is worthwhile to be further explored.
Acknowledgments and Disclosure of Funding
The work was supported by NSFC Grant No. U1936205 and General Research Fund from the Research Grant Council of the Hong Kong Special Administrative Region, China [Project No.: CUHK 14205618].

Review summaries:
This paper derives an inverse operator, which is said to be better than other methods in ref [50] and GALA. The work also points out the inverse operation results in a high pass filter and may amplify the noise. Motivated by this observation, a de-noising layer is designed and introduced into the proposed network. The graph deconvolution uses the wavelet transforms on the graph, which is implemented based on heat kernel and the series in terms of symmetric graph Laplacian. Theoretical analysis was provided for the derivation of the deconvolutional layer.

In this paper the authors introduce a Graph Deconvolutional Network (GDN) as a combination of inverse GCN filters (spectral domain) and denoising layers (wavelet domain). They motivate the design of their GDN by observing that a simple inverse GCN filter likely results in noise amplification. The proposed architecture also has computational and scalability advantages over the previous ones in the literature.  The authors test the capabilities of the GDN on two tasks: 1. feature imputation (reconstructing graph *features*) 2. graph generation (reconstructing graph *structure*), where GDN is used to enhance the performance of two graph-generation techniques  They compare their proposed architecture with various baseline and state-of-the-art approaches and achieve the best performance in all of the tasks.

This paper presents Graph Deconvolutional Networks (GDN), a kind of graph neural network designed to invert the low-pass filtering operation implemented by Graph Convolutional Networks (GCN, Kipf & Welling, 2016).  GDN uses a high-pass filter to invert the effect of GCN and a learnable thresholding operation in the wavelet domain to remove any high-frequency noise. The method relies on the Maclaurin series to approximate the high-pass filter (which in principle should be the exact inversion of GCN, although this is expensive) and the wavelet basis (which relies on the eigendecomposition of the graph Laplacian).   The authors conclude the paper with two main kinds of experiments:   1. Graph feature imputation, in which only a fraction of the nodes in a graph is observed and the remaining must be reconstructed. 2. Graph generation using graph variational autoencoders (Kipf & Welling, 2017) and the Graphite technique (Grover et al., 2019).

This paper proposed GDN, the opposite of GCN that recovers graph signals from smoothed representations. The introduced GDN uses spectral graph convolutions with a high pass filter to obtain inversed signals and then de-noises the inversed signals in wavelet domain. Effectiveness of GDN is validated on graph feature imputation and graph structure generation tasks.