Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: In this paper, the authors propose a spectral-based analysis method to analyze the modeling abilities of major GNNs. Specifically, the first use the concept of convolution support to unite the ideas of spatial-based methods and spectral-based methods. By further identifying the frequency profile of different models, the authors obtain an overview of which spectrum range different models may cover. The evaluation on regular and in-regular graph datasets validate their arguments. In general, the paper brings an interesting perspective in addition to the WL-test to reveal the expressive power of GNNs, and both the theory and evaluation sound solid. It would be better if the authors can further address a few issues.

First, the authors summarize that in certain cases (e.g., sum pooling), the spatial based methods can be considered in the form of Eqn. 3 shows. Though the authors describe that advanced methods like GAT can also be described in this way, it would be great if the authors can make an explicit argument in the beginning of Sec. 3 to describe whether general spatial based methods (e.g., using max pooling, or other $upd(x, y)$ functions) can also be described in this way. 

I also suggest the authors to revise Definition 2 to further explain why each convolution support has the same frequency response over different graphs in a spectral designed case, as there might be some training parameters that can be affected by different graph structures. In addition, in Corollary 1.1, the authors indicate the frequency profile of any given graph convolution support can be defined as Eqn. 7, it is unclear if this also includes spatial-designed graph convolution.

The analysis in Sec. 5 is interesting, but it would be better if the authors can expand the discussion on how we can further utilize the obtained frequency profile to analyze the expressive power of different GNNs. Dividing different filters into low-pass, high-pass, and mid-band categories seem to be in a very coarse granularity and it would be better if the authors can discuss some potential directions for more detailed analysis. I’m also interested in if the number of kernels of the same category (e.g., low-pass filters) may affect model performance. It would be interesting to see if any experimental results are provided to analyze the impact of the number of kernels, the distribution of types rather than their categories only. 

In summary, this work provides a new perspective in analyzing the expressive power of GNNs and I suggest the authors to further address the above issues.
review_title: R3

final_score: rating: 6: Marginally above acceptance threshold
review_content: 1. Summary: 

The authors study the expressive power of GNNs from the spectral view and bridge the gap between spectral and spatial designs of graph convolutions by casting several popular GNN models into a common framework. The authors also shows the necessity of non-low-pass filters on some datasets.

2. Strong points of the paper:

a) The writing is quite clear to understand.

b) The experiments indicate the need to go beyond low-pass filtering.

3. Clearly state your recommendation (accept or reject) with one or two key reasons for this choice:

I am slightly leaning towards recommending a rejection to this paper, with the main reason being that I am not sure if the contributions are sufficiently significant, as I will elaborate below.

4. Provide supporting arguments for your recommendation:

a) Regarding the results on the frequency responses obtained for the different models, those on ChebNet and CayleyNet seem not surprising since the spectrum is their starting point. The filtering properties of GCN have also been relatively well-studied, such as in [1, 2, 3, 4, 5], plus equation (10) only holds when the graph is roughly regular. 

b) In section 5, some of the claims ask for more justifications, such as “GCNs need a high number of convolutional kernels if the input-output pairs can be figured out certain simple filters”, and “since GIN is not spectral-designed, there is no guaranty that it works the same for different graph datasets”. They could be correct in the end, but it will be better to support them with either theoretical arguments or experimental evidence. For example, could you come up with specific examples that show the limits of GCNs and GINs mentioned here? 

c) For GAT, it is not clear whether using randomly sampled attention weights is representative of its normal filtering behavior.

5. Ask questions you would like answered by the authors to help you clarify your understanding of the paper and provide the additional evidence you need to be confident in your assessment:

a) In what way is the theoretical analysis here helpful for our understanding of the different kinds of GNNs beyond existing work on the filtering properties of GNNs? 

b) As I mentioned above, it would be nice if some of the claims can be further supported.  

c) On Page 3, the second line, what exactly does “$\lambda_i$” mean? Does “i” refer to the i-th feature dimension or the i-th eigenvector?  

6. Additional feedbacks:

Possible typo: On Page 6, the third line from the bottom, should it be Figure 2a and Figure 2b instead of Figure 1a and Figure 1b?

References:

[1] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks.

[2] Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters.

[3] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification.

[4] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper insights into graph convolutional networks for semi-supervised learning.

[5] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, Jie Tang. Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: ## Summary

This paper shows an equivalence framework between Graph Neural Networks (GNNs) defined in the spatial domain (based on local node neighbourhoods updates) and spectral domain (based on filters defined on eigenvalues of the graph Laplacian). Using this framework,  the paper derives the spectral equivalent of common spatial GNNs hence showing these act  low-pass filters in the spectral domain. The paper shows experimentally that on MNIST superpixel dataset, spatial GNNs show poor results compared to spectral GNNs. 
 
## Recommendation 
I recommend this paper be accepted (Accept/weak accept given reviewer confidence - 2/5)

## Strong and weak points 
+ The paper does not present a new method but makes clear the connection between spatial-designed and spectral-designed GNNs which has not been previously documented to my knowledge. The connection between spatial and spectral GNNs is remarked upon in Bruna's original 2013 paper and is discussed in later papers (e.g., Kipf&Welling GCN, Wu+2019a_ICML). However, this paper makes the connection explicit. 

- On the flip side, the technical novelty in the paper might not be sufficient but I would still argue that the paper merits publication.  

- One weak point of the paper is the lack of empirical evaluation on downstream tasks. I understand this is not the main focus of the paper  and these numbers are reported in the respective papers but I would like to see the numbers (even if directly taken from literature). The MNIST superpixel dataset gives a highly biased view for need of high-pass filter (which is provided by spectrally-designed GNNs). For example, see [Wu2019a, ICML'19] Tables or Table 2 in https://arxiv.org/pdf/2003.00982.pdf . 


## Questions to the authors 
- Since the theoretical frequency response of CayleyNet, ChebNet, GCN, GIN and GAT,  is one of the main contributions of this paper,  I think the paper would benefit from presenting this in a tabular form in the main text e.g.,  Method, Classification (design(spatial/spectral), support (fixed/trainable), frequency response dependent on graph structure, etc.) 

- The paper mentions the necessity of high-pass and band-pass filters. However, the paper does not show any toy example of a GNN which acts as a  band-pass filter.

- The paper mentions Weisfeiler-Lehman test in the introduction as a theoretical tool for expressive power of GNNs and its limitations in that for "as powerful as k-WL" GNNs, the test cannot distinguish between their discriminative power. However, k-WL for $k \ge 2$ implies non-local updates since multisets are considered. So is the above framework limited to 1-WL GNNs?  

review_title: + Paper makes explicit connection between spectral and spatial GNNs and shows frequency response of common GNNs.  - Technical novelty? = Can be improved: Strong conclusion from empirical evaluation, 

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ==== Summary ====

This work studies the performance of different Graph Neural Network (GNN) from a spectral perspective. In particular, it shows the kernel for all kinds of proposed GNN models can be expressed in a general form with a specific frequency response definition, which indicates the spectral property (spectrum) of the kernel. Based on this definition, this work empirically studies the band-pass property for kernels in different models and demonstrate the importance of such spectral perspective.

==== Pros ====

+ I like the spectral analysis, which is interesting, novel and appears to be important. 
+ The discussion on different GNN models is comprehensive and solid enough.
+ The experimental result shows that it is important to have different kinds of filters 

==== Cons ====

I do not have too much criticism about this work. I am interested to see if there could be some extra discussion/example about how should we choose the kernel for some specific problem, based on the spectral perspective. The experimental result in Sec 5.2 shows that for tasks on images using some kernel with spectrum cover the whole region has the best performance, then *how about other tasks such as semi-supervised learning?* It would be great if there is some guidance/analysis, otherwise we still need to determine the most suitable model based on empirical result. 

Another question is that, the expressive power analyzed by WL-test involves the depth of the network, while in this work it appears that only one layer is considered, so I am wondering *what is the relation between the depth and the expressive power, from a spectral perspective?* To me it seems to be difficult to analyze, but I believe it is worth to address, as we have seen the importance of depth in CNNs. 

==== Reason for score ====

This paper is clear-written, the spectral perspective looks very interesting to me, the theoretical analysis appears to be correct and solid, and the experimental result verifies that the analysis from such perspective is important indeed.  Therefore I tend to vote a clear accept. 

==== Minor comments ====

- Below Eq. (2), '$g_0, g_1$ ... trainable models', a typo?
review_title: An interesting perspective for analyzing Graph Neural Network

Meta-review: This paper gives a new theoretical tool to connect the gap between the spectral perspective and spatial perspective of graph neural networks. The frame-work is considerably broad and can deal with several existing methods. From this view point, the connection between the spatial and spectral perspectives are made explicit while they are noticed in an informal way by existing researches. The frequency response of several methods are analyzed through theories with support by some numerical experiments.

The idea of connecting spatial and spectral perspective would not be entirely new, but the main novelty of this paper is to make it explicit and analyzed the frequency response of well-known methods concretely. This is informative to the literature and extends some known results to more general settings. The numerical experiments well justify the plausibility of the theory. For reasons mentioned above, I think this paper is worth publishing in ICLR2021.
Decision: Accept (Poster)