Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.
main_review: 
* Figure 3 is not clear to observe useful information for illustrating the performance comparison for different approaches.
 
* How to efficiently compute the series in (11) and (12), which are used in calculating the GDN convolution in (13)? If there is a truncation, what is a suitable degree?
 
* OGB should be considered to test by the proposed GDN and compared with existing methods.

* In the experiment part, there are three different tasks: imputation and graph generation. The author evaluated the graph generation results with AUC score, AP score and the negative log-likelihood of the latent variable posterior distribution. There is no standard deviation of graph generation's performance like graph classification experiment. It is hard to reproduce the model if the standard deviation is too high.

* Would it be appropriate to put section 3.3 in the experiment part as an example of the model utilizing the high pass signal?

* line 48, typo for 'de-nosing'
 
* The notation for the graph is usually defined as the triplet of $V, E,w$, which represent vertex set, edge set and edge weights, respectively.

* line 73, 'We show' to 'we show'
limitations_and_societal_impact: It is unclear to me where the low-pass and high-pass information are used in the proposed GDN model. In fact, from (10)--(13), it is difficult to tell where the multiscale property of the transform $\Psi_s$ is employed.
 
It would be much more persuasive if the authors could provide a toy example that showcases the method's computational speed or test some real large datasets, such as open graph benchmarks (OGB).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 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.
main_review: The paper tackles a new, scarcely explored problem: the definition of an efficient and effective Deconvolutional Network for Graph data.

It seems to be not the first paper to propose a definition / implementation for a GDN (see [50] Zhang et al.). The de-noising strategy is also borrowed by one of the cited works.

However, they seem to combine the ideas to create more efficient and effective version of a GDN, moving forward the discussion on how to better face this problem.
They also:
- openly and clearly point out the differences between their work and the related ones
- provide an in-depth explanation of their design choices
- compare the performance of all the related methods on all the tasks

---

The submissions appears technically sound. All claims are supported by proofs provided in the Appendix or by experimental results.

However, I would have found the results to be more solid if they were averaged over multiple runs (especially for the first task)

---

The paper is clearly written, well organized, and provides clear and on-point explanations of the differences between the proposed method and the ones it is compared against.

Some typos / confusing parts:
- use of the word *arts* (e.g. line 24, 28) instead of *articles*
- caption of Figure 2: *s=1* $\rightarrow$ *s=3* (maybe)
- line 121, wrong figure  *Figure 2 (b)* $\rightarrow$ *Figure 3 (b)*
- line 287,291: citation *(Kipf & Welling, 2017)* should be formatted as number
- line 224: capitalize *The performance*
- Confusing use of the term *inverse operator*.
  -  at line 119 you title the paragraph "Inverse operator vs [50]", meaning that "inverse operator" is your proposed GDN (minus the de-noising part)
  - in Figure 3/Section 3.3, "inverse operator" refers to [50] instead (if I understand correctly)
  - but [50] is also called "GCN decoder" in Table 1

  Please use consistent naming, it is really difficult to follow.
 
---

The submission presents a well justified and well documented improvement on the GDN model, showing practical improvements over the current baselines on a selection of tasks and datasets. The paper and related additional materials can be of help to further the research on this topic.

---

**After Author Response**

The authors addressed all my concerns and I confirm my initial evaluation.
limitations_and_societal_impact: The authors have clearly addressed the limitations of their method and suggested directions for further research.

They have briefly introduced possible negative societal impacts, but it might be adequate given the generality of the method introduced.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.
main_review: Overall, this work is a clearly-structured paper. I think it is about average. For the following reasons:

1) Techniques:
Overall, techniques proposed in this paper seems reasonable. 
One problem is that there is analysis on white and Gaussian noise, analysis on other types of noise is expected to be given.

2) Experiments

2.1)	This paper lacks general tasks, such as node classification and link prediction tasks, when compared with GNNs, such as Graphsage and GAT. In highly related works, such as [1] also provides node classification results to show the effectiveness of proposed model.

2.2)	This paper claims that proposed model is applicable to continuous and discrete feature values. However, results in Table 5 and Table 3 are all datasets with discrete values. Results on continuous feature datasets seem lacked.

3) Writings:
The paper is clearly-structured and easy to follow, definitions of symbols are clear.

[1] Handling Missing Data with Graph Representation Learning. NeurIPS, 2020.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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).
main_review: **Originality**: the contributions of the paper are novel and clear, and related works are appropriately cited. 

**Quality**: the paper is theoretically sound, with proofs included in the supplementary material. The derivation of the proposed methodology is clear and the authors clearly explain every choice that they have made (for example, the step at which to truncate the Maclaurin series is found experimentally).
The authors openly discuss the limitations of the work in a dedicated section.

**Clarity**: the paper is very well written and organized, guiding the reader through the math. Some prior knowledge of graph convolution is required to follow the paper, but this can be expected for this kind of work. 
I am confident that I could reproduce the results of the paper given the description of the methodology. 

**Significance**: the significance of the paper is limited. 

- The main issue that I see is that there is no clear reason why a graph representation composed of only low and high frequencies should be more desirable than a graph representation of only low frequencies, especially for the tasks considered here. 
The experiments mildly validate the authors' assumption but the performance improvements are not always significant w.r.t. prior art. The results can be just as well ascribed to the bigger number of parameters that the GNN has when using the GDN decoder, and it is not clear that the spectral analysis conducted to derive GDN is at all related to the performance improvements. 
    - Related to the comment above, why do the GCN decoder and inverse decoder have the same performance in the first experiment, given that they have opposite behaviors? This likely indicates that the experiment is not strongly related to the analysis conducted in the paper.

- A second problem is that this method simply changes GCN from a low-pass to a band-stop filter, but there are classes of GCNs that can already implement such filtering operations, e.g., GCNs based on rational filters. 

Overall, while the paper and the design of GDN are interesting, I don't think that they represent a major contribution to the field of GNNs. 

**Comments**:

- The claim that the proposed method has a complexity of O(|E|) can be misleading because the method does not use the recursive implementation of the Chebynet paper, but rather pre-computes the powers of the Laplacian. This means that the cost of GDN will quickly converge to O(N^2) and will be O(N^2) by the time that n (index of the Maclaurin series) is as big as the graph diameter. In real-world networks and small graphs (like the ones tested in the paper), this number is likely to be small and therefore the cost of computing GDN is non-negligible.

- GDN is supposed to be an approximation of the exact inverse operator. However, from Fig. 3 we see that the two have qualitatively different behaviors in the low frequencies. 
Why does GDN retrieve the low-frequency components whereas the exact inverse operator does not? Can the authors elaborate more on this aspect?

I am more than happy to revise my score if the authors address my concerns.
limitations_and_societal_impact: The limitations are adequately addressed in a dedicated section and the paper is unlikely to have a negative societal impact.
review_title: null

Meta-review: The paper proposes a (niche) topic that is still not well explored, i.e. the definition of an efficient and effective deconvolutional network for graph data. This is done by mainly exploiting already existing results, however introducing a significant level of novelty. During the discussion period the authors were able to clarify all the main issues raised by the reviewers.  An additional contribution to the evaluation of the merits of the paper was coming from another AC, that although recognising the technical correctness of the approach, pointed out some issues that can be summarised as follows: i) motivation of the work is weak since a clear need for GDN and a target application is not clearly identified; ii) proposed experiments do not go to the core point, both in  terms of used datasets (in Cora and Citeseer lowpass information is generally sufficient for the classification task), and more importantly - in terms of the methods GDN is compared to; in short, the experimental assessment has been adapted to search for a justification of the definition of "the opposite of GCN"; iii) since at the end of the day the main component in the proposed method is the combination of lowpass and highpass filters, essentially to formulate bandpass filters that capture sufficient information for imputation and graph generation, it would be appropriate to compare the method to other graph filter constructions: in addition to the architectures based on Chebyshev polynomials (e.g., Chebynet) mentioned by the authors, numerous highly-related works have studied the use of various filter constructions to retain and recover highpass and bandpass information, including CayleyNets (Levie et al. 2017), MixHop (Abu-El-Haija et al., 2019), interferometric graph transforms (Oyallon, 2020), GNNs with ARMA filters (Bianchi, 2021), and some extensive body of work on a variety of graph scattering architectures (for example, Gama et al. 2018; Gao et al. 2019; Zou & Lerman 2020; Ioannidis et al. 2020); these works all aim to leverage high pass, bandpass, or wavelet filters to extract information beyond the low frequencies retained by the Kipf & Welling GCN, with numerous applications considered, which would provide a more established benchmark for the proposed method; in particular, for graph generation, [Zou & Lerman (2019)](https://doi.org/10.1109/IJCNN.2019.8851705) and [Castro et al. (2020)](https://ieeexplore.ieee.org/document/9378305) both showed the efficacy of scattering networks in such tasks.
In summary, the contribution seems to be technical correct, however it is not striking due to the direct exploitation of already published results, it needs a better motivation, consequent evaluation, and presentation. Notwithstanding these issues, that should be addressed by the authors, the proposed approach could eventually be used for works in explainability, which is a very important direction of research to aim for.
Decision: Accept (Poster)