Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary

Several theoretical analyses have been conducted on MPNN-type NNs. On the other hand, although many graph neural network models take the approach of graph filtering, there is little theoretical analysis on graph NNs that take the filtering approach. This paper analyzed the learnability of filtering type graph NNs.
First, the authors hypothesized that the data used practical tasks consisted of true low-frequency information and high-frequency noise (Assumption 2), and verified the correctness of the assumption.
Next, the authors quantitatively evaluated the difference between the case where we feed noisy data to a graph NN and the case where we feed noiseless data to an MLP. The authors showed that a two-layer GCN approximately behaves as a noise-filtering + a two-layered MLP (Theorem 8). Based on this observation, the authors proposed gfNN, which directly models the latter architecture. We can interpret gfNN as an SGC whose final linear transformation is replaced with an MLP.
Finally, the authors empirically showed that gfNN achieved the same level of accuracy as existing GNNs in the citation network tasks. Furthermore, the authors created a dataset that has meaningful information in the high-frequency area (BA-High). It was shown that the existing GNN, including gfNN, did not perform well, while a GNN designed to pass high frequency (gfNN-high) can predict accurately.


Decision

I judge that this paper contributes to deepning the understanding of graph NNs and is worth to be accepted based on the following three points.
First, it enabled us to understand what causes the oversmoothing phenomena. Several studies have shown that Laplacian-type graph convolution works as a low pass filter. However, most of them considered a linear setting and did not explain how the graph convolution behaves when a graph NN has non-linear activation functions. Compared to them, their result admits non-linearity.
Second, by showing that we can approximate a GCN by a noise filter followed by an MLP, this paper has made the relationship between a GCN and an SGC clearer.
Finally, the authors experimentally showed that existing graph NNs do not have predictive power when useful information is in high-frequency domains. It gives insights on what graph NNs can and cannot solve.
For these reasons, I think this paper has contributed to a deeper understanding of graph NNs and sufficiently significant.


Suggestions

- If I understand correctly, the title of Section 4 reflects the content of Lemma 5 in Section 5 rather than the content of Theorem 3 and (5). I recommend the authors to reconsider the titles of Sections 4 and 5.
- Could you add more explanations to the proof of Theorem 8 in Appendix A. Especially, I could not understand how the term $\tilde{O}(\epsilon^{1/4})$ is derived.


Questions

- I could not find implementations of graph NNs in the notebook to the code (I only found the ls result of dataset directories). Do you plan to release the experiment code?
- At the beginning of Section 6, the authors wrote that they set $k$ to $2$ (hence two-layered GNNs are in consideration). But Theorems 7 and 8 considered the optimal $k^\ast$ in Corollary 6. Which is correct?
- In Section 3, the authors claimed that the performance of MLPs is relatively more robust to the Gaussian noise in the low-frequency regime compared to the high-frequency regime. Certainly, the decrease in performance at $\sigma = 0.01$ is massive in the high-frequency setting for the CiteSeer dataset. However, it is hard to see this trend in Cora and Pubmed. Therefore, I think it is a little too aggressive to conclude that claim.
review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: The authors extend the existing work SGC [1] to a nonlinear version, which addresses the limitations of dealing with nonlinear feature. It further extends the theoretical finding in [1] about the low-pass filtering functionality of graph convolutional networks and shows its advantage in dealing with graph signal processing problem. Evaluation of the proposed method is performed on 7 datasets for node classification task.
Pros:
1. This work goes into detail of the theoretical finding of SGC.
2. Authors conduct extensive experiments on multiple datasets.
Cons:
1. The proposed graph neural network mode is an extension of the existing model SGC, which address the limitation of SGC to model the node feature nonlinearity. It is a good extension, but the novelty is limited.
2. Authors further extend the theoretical finding in [1] and verify the fact that low-pass filtering functionality of graph neural network provide better noise robustness than two layer MLP. It has some novelty, but the novelty is incremental.
3. In the experiment, the performance gap between SGC and gfNN is very small on noise robustness study and traditional node classification. The performance gap between GCN and gfNN is also small on noise robustness study is also small, which can not support the conclusion "GCN has a risk of overfitting to the noise"
4. The paper has the problem of notation missing, e.g on page 2, Fig1 is never mentioned; on page 7, the notation of "LG" is missed in Fig 5.
5. The code link is given but no code is missing.
[1]Wu, Tianyi Zhang, Amauri Holanda de Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q.Weinberger. Simplifying graph convolutional networks. ICML2019

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The paper shows the graph signal convolution in GCN-based models is typically a low-pass filter. Besides, the authors propose a simplified GCN-framework named gfNN, which is demonstrated on various benchmark datasets.  To be honest, the paper is well-motivated, well-written. And,  I enjoyed reading through the paper. 

However, I have some concerns regarding the technical contributions of this paper.
(1) "GNN is a low-pass filter" is not a new observation. Various works (SGC, [Shuman, et al., 2013]) have studied this observation before. 
(2) If the frequency of the label vector is higher than the threshold of the low-pass filter (e.g., gfNN), will the model be problematic? 
(3) It seems the only difference between SGC and gfNN is that gfNN is equipped with one more hidden layer. The authors claim that gfNN perform better than SGC is because "the true features are non-linearly separable". If it is the case, then the technical contribution of gfNN is trivial. 

Overall, I still like this paper due to its interesting point of the presentation. I vote for weak accept, but I am fine if it is rejected. 
review_title: Official Blind Review #2

Meta-review: This paper studies two-layer graph convolutional networks and two-layer multi-layer perceptions and develops quantitative results of their effect in signal processing settings. The paper received 3 reviews by experts working in this area. R1 recommends Weak Accept, indicating that the paper provides some useful insight (e.g. into when graph neural networks are or are not appropriate for particular problems) and poses some specific technical questions. In follow up discussions after the author response, R1 and authors agree that there are some over claims in the paper but that these could be addressed with some toning down of claims and additional discussion. R2 recommends Weak Accept but raises several concerns about the technical contribution of the paper, indicating that some of the conclusions were already known or are unsurprising. R2 concludes "I vote for weak accept, but I am fine if it is rejected." R3 recommends Reject, also questioning the significance of the technical contribution and whether some of the conclusions are well-supported by experiments, as well as some minor concerns about clarity of writing. In their thoughtful responses, authors acknowledge these concerns.  Given the split decision, the AC also read the paper. While it is clear it has significant merit, the concerns about significance of the contribution and support for conclusions (as acknowledged by authors) are important, and the AC feels a revision of the paper and another round of peer review is really needed to flesh these issues out. 
Decision: Reject