Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes that adding transformers on top of Graph Neural Networks layers aids performance, and furthermore that adding a readout position is a better way to get a final output vs. simple aggregation strategies.  Other papers have in various forms attempted to add transformers to neural networks, but this paper uses a position-encoding free, approach that performs better while being simpler.  This also demonstrates the importance of long range information propagation in solving GNN problems.  They demonstrate the superior performance of their method empirically in a variety of interesting benchmarks.

main_review: Originality: Other papers have applied Transformers on top of GNNs but this paper demonstrates that a simpler approach which completely ignores position encoding for transformer part actually results in better performance in the tested applications.  It also introduces using the <CLS> readout position, as done in sequence applications, helps performance in the graph neural network application, which is apparently novel in this context as well.

Impact: The authors empirically demonstrate performance improvements on a variety of datasets.  Furthermore, this paper can also lead that to many other potential network architectures that can further improve performance, such as alternating between transformer and GNN layers.  It also shows the importance of long distance information propagation in solving real graph problems.

Clarity:  The paper is well written and easy to follow.  Diagrams are of a good quality and results and their exposition are easy to follow.

Quality:  Submission appears technically sound and is supported by empirical , if not theoretical, evidence.  Ablation studies were performed to narrow down the contributions by the various contributions suggested by the paper, showing the importance of each stage.  

As a comment however, the paper doesn't demonstrate that actual position encoding isn't helpful - instead it shows that the currently tested schemes are not helpful.  There might be other encodings that perform even better than the suggested approach.     

limitations_and_societal_impact: They have address limitations and potential negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes to use a transformer that attends over all nodes in the graph, given an intermediate representation obtained using a standard GNN module. Contributions 1) usage of a self-attention mechanism that takes into account all nodes in the graph, as opposed to previous methods discussed in the related work. 2) the removal of the positioning encoding to allow permutation invariance. 3) Quantitative results on several datasets, overcoming the baselines and supporting the method with empirical evidence. 

main_review: The paper is well written and clear. The work is well positioned with respect to existing work, to the best of my knowledge, clearly stating what are the benefits and contributions of the proposed method. 

The usage of a transformer to learn long-range dependencies is well motivated, drawing evidence from the NLP and vision communities. The method is simple and flexible to the GNN backbone used, as shown in the experimental section. 

The technical novelty is moderate, but the method has been tested on several datasets, showing good results and overcoming a basic Transformer and other GNNs. 


Additional questions/comments: 
- In equation 3, it seems it should be $ \alpha^l_{v,w} = softmax(\alpha^l_{v,u}) $
- What happens if a positional encoding is used? I would expect the quantitative results to degrade, but it might be a relevant study to show that the choice of no positional encoding is beneficial for the model. 
- What is the computational cost overhead of adding GraphTrans to a specific backbone? And how many more parameters does it introduce?

Overall, it is a relevant contribution to the field that comes from a sound motivation and is sufficiently benchmarked in the experimental section. 

limitations_and_societal_impact: The limitations are not discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes to combine GNN with a permutation-invariant transformer called GraphTrans for the graph classification tasks. The GNN module is used to learn representations from graph structure,  while the transformer module without a positional encoding is to learn long-range pairwise relationships, with "CLS"-like readout to obtain a global graph embedding. Experimental results show that the proposed simple architecture leads to state-of-the-art results on several graph classification tasks, better than other GNN models. These results also suggest that modeling all pairwise node-node interactions in the graph is
particularly important for large graph classification tasks.
main_review: Pros:
1. GraphTrans proposes to use transformer layers (without position embeddings) to learn the pairwise node interactions and summarize the graph representation after a normal GNN model. 
2. Adding this kind of transformer to the GNN improves the performance of various graph classification tasks.

Cons:
1. The number of parameters in GraphTrans is much bigger (maybe doubled) than its GNN version without a transformer (I assume all experiments used 4 layers of transformers as stated on page 6). Thus the improvement presented in Table1-3 may not be fair comparisons.
2. Combining Transformer with GNN is very common for NLP tasks (pre-trained transformer LM as an encoder for input text sequence), followed by GNN on graphs such as knowledge graphs or dependency parsing trees. Thus the novelty of GraphTrans in this paper is rather limited. I do not agree with the statement that the transformer in GraphTrans is learning "long-range" relationships, because the module is computing any pair of feature interactions, with attention weights to control the contribution of each node to the final graph embedding. So it would make sense to try another set of experiments: to switch the order of transformer and GNN, i.e use transformer module first and then GNN, and see the results.
3. Since the transformer uses self-attention, it would make sense to compare to GAT-like GNN models (for example, the recent paper on direct multi-hop attention network, although this paper only showed results on node classification and knowledge graph embedding, not on graph classification.
4. The limitation of GraphTrans is that it is only for graph-level classification, and is not suited to node classification. 

Questions:
1. The last row of ablation results in Table 5 is explained in lines 290-292: not sure how the embeddings of input graph are concatenated with input embedding of the transformer, and where they are used.

Some typos on line 110, Figure 2 caption, line 286, line 292 need to be fixed.

***
After reading the authors' responses to my questions, I have adjusted my review score. I am not convinced on the novelty side of the method. However, if only considering the graph classification task, their experimental results have shown the effectiveness of the proposed method.
limitations_and_societal_impact: See above comments.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Current GNN methods fail at utilizing long-range dependencies in graphs due to over smoothing. However, in some cases, long-range information might be useful. Inspired by the success of transformers in computer vision tasks, this paper tackles the challenge of learning long-range dependencies in GNNs by simply augmenting a common GNN architecture with a transformer sub-network. They also borrow a “readout” token from NLP which improves the final learned representation of the graph.
main_review: 1. **Scalability - $O(n^2)$ memory complexity**

   My main concern regarding this paper - is its scalability which is very shortly discussed in the checklist. The transformer subnetwork has to compute and hold in memory attention maps of size, which for graphs already reaching ~100 nodes it could raise a memory issue. Unlike NLP tasks where a usual sentence would contain at most tens of words, graph learning tasks could reach graphs of thousands of nodes. 

2. **Originality**

   The authors fail to mention that global attention in graph networks has already been introduced in [1]. The difference between [1] and these works is that the global attention layers are augmented to each GNN layer in [1] and not just at the end. Also, [1] deals with the scalability issue by learning a low-rank representation of the attention matrix having a memory complexity of $O(kn)$ where $k$ is the rank and $k<<n$. 

   I therefore feel that the differences between the methods are quite minor unless we see empirical evidence or theoretical justification as to why this work is better and novel than [1]. 

3. **Experimental Evaluation**

   - The method is only tested on graph classification tasks. Is the transformer subnetwork also beneficial for node classification and link prediction? 
   - Significantly better performance has already been achieved on the NC1 and NC109 datasets in [2]. Is the setting different?


   

***Other comments***

- Typo in the title of section 3 

  > Motivation: Learning to model long-range pairwise interactions in gr

  What is gr?



---

[1] Puny, O., Ben-Hamu, H., & Lipman, Y. (2020). Global Attention Improves Graph Networks Generalization. *arXiv preprint arXiv:2006.07846*.

[2] Morris, Christopher et al. “Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings.” arXiv: Data Structures and Algorithms (2020): n. pag.


---
After reading the authors' responses and the other reviews I think the paper still lacks novelty, however it shows strong performance. I therefore update my score. 
limitations_and_societal_impact: The authors shortly discuss the limitations in the checklist section as mentioned above in the main review.
review_title: null

Meta-review: The majority of the reviewers recommend accepting this paper (3 of 4).
The only reviewer not recommending acceptance did not properly engage in discussion and the authors responded to their concerns.
The AC recommends acceptance.

Decision: Accept (Poster)