Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: I liked this paper quite a lot. Although this paper does not belong to my area of expertise, I was able to understand the paper clearly because of its lucid exposition. Experimentally, the authors show a novel GNN design with an attention module that has comparable performance to the MLP and outperforms other GNN designs. I believe that this will be a valuable contribution to many practical problems.

Unfortunately, this work does not have any theoretical results, and evaluating the experimental results is outside my range of expertise. Therefore I would like to defer this paper to my fellow reviewers.
review_title: This paper proposes a novel method for Graph Neural Networks with adaptive spectral filters that experimentally outeprform other GNN designs and has comparable performance with MLP in graphs having small local homophily.

final_score: rating: 7: Good paper, accept
review_content: Main Idea

In this paper, the authors study the problem of GCN for disassortative graphs. The authors proposed the GNAN method to allow attention on distant nodes indeed of limiting to local neighbors. The authors generalized the idea of graph wavelet with MLP to generate the attention score and utilized it to generate multiple attention heads. The authors carried out experiments on several real-world networks (4 assortative and 3 disassortative) with comparison to several state-of-art GCN methods.

Strength:
The authors study a very interesting problem of GCN/graph embedding or disassortative graphs.
The proposed method is well motivated with solid theoretical motivation from graph wavelets. The proposed model is very intuitive generalization of graph wavelet methods.
The empirical evaluation is very thorough on seven networks with comparison to about 10 baselines of different kinds.

Weakness:
Though the authors mentioned the use of sparsification of attention for speed-up, however, it mentioned that t is set to zero. It is interesting to see how scalable the proposed method is as it needs to have global attention to possibly all nodes. An empirical comparison of running time would be very helpful.
 The authors only carry out experiments on three disassortative which are all very small. It would be interesting to see more experiments on disassortative graphs. Alternatively, it would be interesting to have an experiment on synthetic graphs where the \beta can be controlled and varied smoothly to see how it affects the performance of different algorithms.
The authors picked only node classification of evaluation tasks. It is interesting to see how the disassortative could impact other tasks like graph reconstruction and link prediction. 

review_title: Official Blind Review #2

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work propose a new GNN architecture to help GNN break its limitation on only working over homophilic networks. The technical is to use introduce graph global attention. 

I think the paper is written okay. The motivation is clear. The solution is reasonable. However, I have following criticisms:
1. This work has limited novelty. Observing that GCN cannot work well over heterophilic networks is not a new idea and observation. Using attention to capture the features from far-away nodes is natural but not novel. I do not think that it is reasonable to argue against other works, e.g. [1] that adopts the above idea by saying they are not expressive enough. Expressiveness sometimes may lead to model overfitting. Actually, ChevNet [2] can also capture far-aways nodes and be expressive enough. Why does it not work well? I guess that it is due to some overfitting issue. Moreover, if I understand it correctly, the limited difference between this work and [3] is most likely the global attention, which has very limited contribution. 

2. Although the work claims everywhere to tend to decrease the complexity, when computing the global attention, one still needs to do computation for every pair of nodes, which is of course not scalable for even medium-sized graphs. 

3. The heterophilic networks used for evaluation are very small with only several hundred nodes. Why not try larger ones, say actor, Cham. in [4]? I guess the computational issue comes from the global attention. 

[1] Non-Local Graph Neural Networks.
[2] Convolutional neural networks on graphs with fast localized spectral filtering.
[3] Graph wavelet neural network
[4] Geom-gcn: Geometric graph convolutional networks.


---post-discussion update----
I would like to thank the authors for preparing the rebuttal and attending our discussion. However, I still think the complexity is a concern of this work. I do not think that Eq. (3) can be implemented within the complexity that the authors claimed. Moreover, if the authors use another way to compute the attention scores, that way should be very clearly stated instead of written in a different form. Given the high complexity, I cannot clearly see the advantage of this work in comparison to [1], as the non-local attention has been proposed in [1] already.

[1] Non-Local Graph Neural Networks.
review_title: High complexity and weak experiments 

Meta-review: This paper proposes a GNN that uses global attention based on graph wavelet transform for more flexible and data-dependent GNN feature aggregation without the assumption of local homophily.

Three reviewers gave conflicting opinions on this paper. The reviewer claiming rejection questioned the novelty of the paper and the complexity of the global attention mentioned in the paper. Even through the authors' responses and subsequent private discussions, concerns about complexity and novelty were not completely resolved.


Considering the authors' claim that the core contribution of this paper is to design fully learnable spectral filters without compromising computational efficiency, it is necessary to consider why it is meaningful to perform global attention based on graph wavelet transform in the first place. In terms of complexity, although the wavelet coefficient can be efficiently calculated using the Chebyshev polynomials mentioned by the authors, in the attention sparsification part, n log n is required **for each node** in sorting, resulting in complexity of n^2 or more. There may still be an advantage of complexity over using global attention in a message-passing architecture, but it will be necessary to clarify and verify that, given that the proposed method uses an approximation that limits global attention within K hops.

Also, this paper modifies the graph wavelet transform in graph theory, which requires a deeper discussion. For example, as the authors mentioned, the original wavelet coefficient psi_uv can be interpreted as the amount of energy that node v has received from node u in its local neighborhood. The psi_uv defined by the learnable filter as shown in Equation 3 has a different meaning from the original wavelet coefficient. There is insufficient insight as to whether it is justifiable to use this value as an attention coefficient.

Overall, the paper proposes potentially interesting ideas, but it seems to require further development for publication.
Decision: Reject