Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors propose a recipe on how to build a general, powerful, scalable  graph Transformer with linear complexity and state-of-the-art results on a diverse set of benchmarks.
strengths_and_weaknesses: Strengths:

1. The proposed model is scalable due to its linear comlexity.

2. The work considers lots of message:  positional and structural encodings with local message passing and global attention.

3. The code is available and the performance of this work is good. 

Weaknesses:
1. The overall algorithm can be well presented, like a presudo algorithm can be helpful to understand the implementation.

2.   Many recent studies show that the dense attention map is not necessary in the Transformer. In graph Transformer, Do we really need to allow nodes to attend to all other nodes in a graph (global attenion).

3. The universal function on graph is not clear. A more detailed analysis why the proposed framework can achieve universal funtion approximator is required.
questions: 
*  Many recent studies show that the dense attention map is not necessary in the Transformer. In graph Transformer, Do we really need to allow nodes to attend to all other nodes in a graph (global attenion).
* The universal function on graph is not clear. A more detailed analysis why the proposed framework can achieve universal funtion approximator is required.
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a way how to efficiently use transformers on graph data. They report modular architecture, containing of graph positional encodings, structural encodings, and graph features, that further passed to an ensemble of arbitrary transformer block and arbitrary message passing neural network.
strengths_and_weaknesses: The paper deals with an important and trending task. It's a nice and interesting read overall, the paper is technically sound, and well structured and describes the problem well. The authors provided performance testing on sufficient amount of datasets, and show the performance deviation with different random seeds. The authors provided a package built on top of graphGym which is a big plus.

On the other hand, the solid proof to use transformer block is missing. The authors claim that their solution has linear complexity, however from the table 2 is clear that linear attention block gives only marginal performance improvement, when for standard tasks (like LRA benchmark) linear transformers are on par, or even outperform vanilla transformer.
questions: How the model performs if we use another architecture instead of transformer block? Say simple MLP?
limitations: The authors addressed the potential societal impact and limitations in the collusion section.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper provides a general, powerful, scalable (GPS) graph Transformer with linear complexity. The authors redefine positional encodings (PEs) and structural encodings (SEs) with local, global, and relative categories and try to incorporate PEs and SEs with local and global attention in a graph Transformer. With the proposed GPS layers, the authors show the competitive result on several datasets. The proposed definition of PE and SE is general, and the paper has a good presentation of writing logic. However, I have several problems about the methods and experiments.
strengths_and_weaknesses: 1. The authors summarize the previous works about positional encodings and propose novel categories of structural encodings.
2. The authors explain the rationality of definition and categories by the 1-Weisfeiler-Leman test and Circular Skip Link (CSL) graph.
3. Based on PEs and SEs, the authors propose the GPS layer and present its characteristics with theoretical analysis. 
4. The paper has good writing and logical structure.
questions: refer to "limitations"
limitations: 1. The PE and SE categories of local, global and relative are confusing. The local and global are opposite, but relative is another dimension, and it should be more suitable compared with the absolute PE.
2. The description of relative SE is inconsistent with its example. The authors claimed that description allows two nodes to understand how much their structures differ, but examples are not enough to illustrate. Relative SE lacks support from related work, and this paper has no novelty on this point. Relative SE is more like a definition forcibly created to correspond to relative PE.
3. The contribution of this paper is unclear. The first point should be merged with the third point, and the fifth point should not be regarded as the contribution of this paper. 
4. All methods in the paper are summary and induction, which lack novelty. There is no key innovation part of the paper.   
5. The result of SAN on ogbg-molhiv dataset misses the decimal point and zero in Table 4.
review_title: null

Meta-review: metareview: This paper presents a powerful, general, scalable, and linearly complex graph Transformer. Positional encodings and structural encodings are redefined with local, global, and relative categories, and an attempt has been made to include  local and global focus attentions in a graph Transformer. All of the reviewers acknowledged the novelty of this work, particularly within the context of the domain, and therefore voted for its acceptance. Please take feedback from reviewers into account when preparing the camera-ready version.
confidence: Certain
Decision: Accept