Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper points out an interesting and important issue of GNNs, i.e., local aggregation is harmful for some disassortative graphs. It further proposes non-local GNNs by first sorting the nodes followed by aggregation. The paper is well written and easy to follow.

+ Positives
1. The paper studies an important problem. The proposed Non-local GNNs by first sorting the nodes followed by aggregation is interesting and makes sense.
2. The paper is well written and easy to follow.
3. Experiments well support the claim of the paper. The results demonstrated the effectiveness of the proposed method for disassortative graphs for node classification. In addition, the authors show the running time to demonstrate its efficiency and analyze the sorted nodes to demonstrate that the proposed method can learn non-local graphs.

-Negative
1. It seems that for some disassortative graphs such as Actor, Cornell, Texas and Wisconsin, using the node attributes to build the non-local graph is much effective than using the attributed graph. The authors may also need to compare a baseline that simply use MLP to learn node embedding, then construct the graph by calculating pairwise node similarity, followed by GNN for node classification. This can be treated as a variants of the proposed NLMLP to show that sorting the nodes is more efficient and more effective.

review_title: interesting and novel idea of non-local GNN for disassortative graphs

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a way of speeding up non-local aggregation on graph convolutional neural networks based on sorting the nodes into an ordering, and performing a 1-D convolution on this resulting ordering. This algorithm has the advantage of being asymptotically faster than other non-local aggregation schemes, and the paper demonstrates that empirically it can do at least as well as some of the other methods.

Strengths:
+ the proposed approach is simple, quite general, and rather different from other tools for graph neural nets that I'm aware of.
+ the experimental evaluation methodology is sound, and comparisons with several previous works are made

Weaknesses:
- the approach is difficult to interpret: it's difficult to convince someone working on GCNs why it would work.
- on some of the data sets, the gains observed as inconclusive. The experiments also focused on small data sets: it's unclear how such gains extend to more general settings.

I work mostly on graph algorithms, and only know a little about neural networks. So I'm evaluating this paper mostly as a practical graph algorithms. The effectiveness of such global sorting schemes based on a single score is very surprising, almost too surprising. On the other hand, my general impression is that graph algorithms is full of such surprises: many by now classical algorithms are arrived at by analyzing strange phenomenon that happen to work well. So I'm quite willing to suspend disbelief about why something like this would work, as that's a much more detailed process.

From the discussions, it seems that there are quite a bit of concerns raised about the experimentation process. On the other hand, the responses, and presentations in the paper, are also quite convincing to me. So I believe this result is ready to appear in the conference, if anything for the further discussion/interest it will generate, and would still like to recommend acceptance of this paper.
review_title: Interesting Simple Idea, Clearly Experimental Gains

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
The goal of the paper is to perform node classification for graphs. The authors propose a strategy to augment message passing graph neural networks with information from non-local nodes in the graph - with a focus on dis-assortative graphs. Dis-assortative graphs are graph datasets - where nodes with identical node labels are distant from each other in terms of edge connectivity. 

With node representation learnt from standard graph neural networks, etc., the authors propose to use an attention guided sorting mechanism, to create a proxy graph, where nodes which may have identical node labels be connected to each other (analogous to creating a k-nearest neighbor graph). Message passing is then employed on the proxy graph to learn final representations for the nodes.  Since the authors employ a single vector, namely 'c' (which they call calibration vector), to capture the 'importance of information' shared across different nodes  - there is a speedup in comparison to strategies which employ a pairwise comparison between all nodes in the graph.

Pros:
1. The idea to create a proxy graph to capture non local information is interesting
2. The proposed technique can be augmented with almost any existing GNN

My Concerns:
1. (Dis-assortative or i.i.d.): - The authors in Figure 1 - show that homophily of the created proxy graph is a value larger than that of the original graph. However, from table A.2 in the appendix - it is clear to see that MLP's outperform GNN's with or without the attention sorting in the dis-assortative graphs - and the performance of the MLP's and proposed augmented NLMLP are well within one standard deviation from each other. This questions the need to employ a proxy graph construction on top of MLP's for these datasets as it appears like the data can be treated as i.i.d (and not relational). Moreover, these datasets (used from Pei et al. 2020) are extremely small to draw any significant conclusion. Also almost no gains are seen on the assortative datasets Citeseer, Cora, Pubmed (Please add datasets from OGB) - and their running times (when augmented with a proxy graph - are the gains worthy of increased run times?).
2. (Baselines): Since the authors propose a strategy to construct a proxy graph (and the number of neighbors of each node in the proxy graph is the same??) - baselines such as creating graphs where nodes with identical labels are connected are also connected to each other / GNN on simple k-Nearest neighbors created using initial features (While a simple k-NN might appear more expensive - but the computation here is a single time effort) appears crucial. Also add a baseline, where adjacency structure of the graphs are iteratively updated during training such as - Learning discrete structures for graph neural networks (Franceschi, et al. ICML 2019)
3. (Sufficiency, lack of details): The use of a single calibration vector may not be sufficient to sort the nodes - there are no guarantees in the paper to say when a single calibration vector would suffice. Also, the number of classes of nodes in each of the datasets used here are very small - and also does not trivially extend to multi-label classification of nodes. Also how do you also determine the number of neighbors in a proxy graph and do all nodes need to have the same number of neighbors in the proxy graph??? There are missing equations about how the calibration vector 'c' is learnt (what are the objective, etc) and the effect of running time when there are a large number of neighbors considered in the proxy graph -  without any equations its hard to argue against the case that the number of gradients to be computed would explode, when the number of neighbors are increased in the proxy graph (especially when jointly learning the GNN and the proposed augmentation).


Other minor concerns:
If possible, please include the difference between assortative and non-assortative graphs in the introduction - it makes it easier for a reader.

If details are added and the concerns are addressed, I will be happy to improve my score.
review_title: Review of Non-Local Graph Neural Networks

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper targets on addressing the node embedding problem in disassortative graphs. A non-local aggregation framework is proposed, since local aggregation may be harmful for some disassortative graphs. To address the high computational cost in the recent Geom-GCN model that has an attention-like step to compute the Euclidean distance between every pair of nodes, an idea of attention-guided sorting is introduced. It learns an ordering of nodes, such that distant but informative nodes are put near each other. The sorting order depends on the attention scores computed with the local embedding vector of a node. Then Covn(.) function is applied on the sorted sequence of local node embeddings to obtain the non-local embedding. The final node embedding is then the concatenation of the local and non-local embedding, which is used for node classification. 

The presented simple approach is an interesting idea to “push” the distant but informative nodes together. However, it is unclear how the “attention-guided sorting” is aware of the “distant” nodes. The local node embedding vectors z can be obtained either by the node content, or by GNN. If z is from the node content only, the attention score a is calculated without consideration how nodes are close or distant on the graph. The whole approach works purely for node content classification. If z is from GNN,  nodes close on the graph have similar z embedding vectors and thus will be sorted next to each other. Then, the sorting doesn’t take “distant” nodes close. 

Although the experimental results show the proposed approach performs better than several baselines, more and stronger GNN models are expected to be compared with, e.g., GINs. Especially on Chameleon and Squirrel datasets, theses two “disassortative” graphs can be handled by GNN kinds of models. The node classification in other four “disassortative” graphs in fact can be treated as a standard class classification task by ignoring the graph structures, as MLP on node features is already good. 

Thanks for the clarifications from the authors. The discussion was very helpful. 
review_title: the idea of “push” the distant but informative nodes together is not reflected

Meta-review: This paper is right at the borderline: the reviewers agree it is well written, proposing a simple but interesting idea. However, there was a feeling among the reviewers (especially reviewer 1) that the paper could be strengthened considerably with a better discussion/some theory on the sufficiency of the calibration vectors, as well as experiments on larger datasets. Doing one of these would have substantially strengthened the paper. Due to the remaining shortcomings, the recommendation is not to accept the paper in its present state.
Decision: Reject