Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new graph Transformer architecture that contains a sequence of tokens obtained by aggregating neighbors' features. It shows improved expressive power with information from multi-hop neighborhoods. So, the model treats a node as a sequence of tokens. The authors claim that the model has better scalability due to its mini-bash training. The authors theoretically analyze that the proposed method has more expressive power compared to decoupled GCN.
strength_and_weaknesses: Strengths:

* The proposed method shows competitive performance on many benchmark datasets.
* The multi-view/multi-scale representation of a node (a sequence of aggregated node features) is an interesting idea. The late fusion of the node features is new. However,  the attention-based readout can be viewed as deformable convolution with an adaptive receptive field since it varies neighborhood from 0-hop to K-hops. From this perspective, the authors may want to compare the proposed method with similar approaches in the literature. 

Weaknesses:

* Unlike the authors' presentation, the model does not utilize order information at all. Indeed, the model can be viewed as an ensemble model with features from different layers of a GNN while sharing the transformer's parameters. 
* One of the main contributions is "a sequence of tokens" for a node. But no ablation study is provided. For instance, simple feature concatenation is one naïve approach. Compared to straightforward construction, the authors should show the performance gain of the sequence of token node representation.
* Mini-batch training for large-scale graphs has already been studied in the literature. Unless the authors present a new technique, which significantly improves scalability, It is hard to consider the improved scalability as the contribution of this paper.
clarity,_quality,_novelty_and_reproducibility: * Overall, the paper reads well, and the architecture is clearly presented with figures.
* Since the method is simple, it doesn't seem to have a problem with reproducibility.
* Novelty is somewhat limited. But processing the multiple tokens for a node separately and merging them in the attention-based readout layer is interesting. To prove the value of this architecture, the authors need to provide ablation studies or additional analyses.
* The authors claim that the proposed method is theoretically superior to Decoupled GCN. But decoupled GCN is not clearly introduced. 
Although the proposed method exhibits empirically strong performance, technical contributions and novelty are limited.
summary_of_the_review: The proposed method shows a significant performance gain. Also, the multi-hop representations for each node and merging transformed node features in the attention-based readout layer are interesting ideas. However, the authors did not provide experimental results to justify their architecture. Lastly, scalability is improved by well-known mini-batch training. Overall, this paper has limited novelty and a few missing analyses.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a Graph Transformer architecture. It aggregates the neighborhood features from different hops and treat them as a sequence of token vectors for Transformer.
strength_and_weaknesses: Strengths:

- Different from existing graph transformer methods, this work treats different hops of neighborhood representations as tokens. This can make the proposed method scale to large graphs.

- The paper is written and organized well, and it is easy to follow.

- The provided source code facilitates good reproducibility of this work.

- The proposed method seems to have a promising performance in experiments.

Weaknesses:

- The authors argue that existing message passing-based GNNs have limitations such as over-smoothing and over-squashing. However, recently, there emerges a number of works e.g. [1,2,3,4,5] that address these limitations.

- The experiments are not extensive. Specifically, the running time cost and the memory cost of all the methods should be compared to better show the efficiency of the proposed method, since the efficiency of this work is highlighted throughout the text.

- This paper repeats itself in some pieces of text.

Refs:

[1] Huang, W., Rong, Y., Xu, T., Sun, F., & Huang, J. (2020). Tackling over-smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.09864.

[2] Lu, W., Zhan, Y., Guan, Z., Liu, L., Yu, B., Zhao, W., ... & Tao, D. (2021). SkipNode: On alleviating over-smoothing for deep graph convolutional networks. arXiv preprint arXiv:2112.11628.

[3]	Yang, C., Wang, R., Yao, S., Liu, S., & Abdelzaher, T. (2020). Revisiting over-smoothing in deep GCNs. arXiv preprint arXiv:2003.13663.

[4] Huang, W., Rong, Y., Xu, T., Sun, F., & Huang, J. (2020). Tackling over-smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.09864.

[5] Sun, Q., Li, J., Yuan, H., Fu, X., Peng, H., Ji, C., ... & Yu, P. S. (2022). Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing. arXiv preprint arXiv:2208.08302.
clarity,_quality,_novelty_and_reproducibility: - Clarity: easy to follow

- Quality: seem to be sound

- Novelty: fair

- Reproducibility: provided source code facilitates good reproducibility 

summary_of_the_review: The idea is good. Although some necessary experiments are missing, I encourage the authors to supplement these experiments during the discussion phase, to well support their arguments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes Hop2Token to scale a graph transformer to larger graphs by using multi-hop aggregated features of each node as the input tokens to graph transformer, instead of using all nodes as the tokens. The overall transformer using Hop2Token is called NAGphormer, which also uses structural encoding and attention-based readout function. The method is tested on both small and large node classification datasets and demonstrates empirical gains.
strength_and_weaknesses: Strength
- The proposed Hop2Token method is novel, simple, and can be efficiently implemented.
- NAGphormer demonstrates empirical gains over thorough experiments and ablations.
- The paper is clearly written and easy to follow.

Weaknesses
- Several important previous works are not mentioned and compared against, most notably "Recipe for a General, Powerful, Scalable Graph Transformer", which proposes reducing computation costs using a linear transformer. Other recent graph transformers like K-Subgraph SAT and EGT should also be compared if the authors wish to support the claim "consistently outperforms existing graph Transformers and mainstream GNNs".
- The expressivity result against decoupled GCN does not seem very strong, since decoupled GCN is very simple and limited itself (probably by WL1 test, also https://arxiv.org/pdf/2010.12408.pdf shows that it can be seen as two times label propagations.)
- Hop2Token fundamentally tries to compress an exponentially more amount of nodes information to a single token as the hop k increases. This is known to suffer from over-squashing issue. Although this may not be shown in the experimented datasets (maybe due to high homophily), this is a concern conceptually. 

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. To the best of my knowledge, Hop2Token is novel, although heavily related to the decoupled GCN and APPNP lines of work. The NAGphormer is less novel beyond Hop2Token and seems mainly serves as a way to adapt a standard transformer to Hop2Token (e.g. structural encoding has already been studied in previous works). 
summary_of_the_review: Overall, the proposed Hop2Token seems a conceptually interesting and promising way to enable mini-batch training over larger graphs. However, several important baselines are missing and the method in its current form could suffer from severe over-squashing problems.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new neighborhood aggregation method based on the number of hops. With this method, a graph transformer is developed with node-wise input sequences. Moreover, a self-attention readout function is applied to integrate the representations learned from the transformer module.
strength_and_weaknesses: Strengths:

1. With node-wise sequences as inputs, mini-batch can be used, and training becomes more scalable.
2. Extensive experiments are conducted to compare NAGphormer with many baseline models in small to large-scale tasks. Additionally, an ablation study on the effect of different readout functions and propagation steps is performed.
3. The empirical performance of NAGphormer is outstanding.


Weaknesses:

1. The authors propose that with Hop2Token, NAGphormer is more expressive than decoupled GCN family. However, in the experimental section, no decoupled GCN models are compared. Therefore, it will be more persuasive if the authors can add some of the decoupled GCN as baselines.
2. Given the good performance of NAGphormer, from the ablation study over the depth of the model, it seems that NAGphormer also suffers from oversmoothing or oversquashing problems since as the depth increases, the performance deteriorates. 

clarity,_quality,_novelty_and_reproducibility: 1. The paper is written clearly.
2. The code of the experiments is submitted.

summary_of_the_review: The idea of node-wise sequence input is novel, and the proposed model is competitive compared with current SOTAs.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a graph transformer architecture that aggregates the neighborhood features from different hops and treats them as a sequence of token vectors for the transformer. It shows improved expressive power with information from multi-hop neighborhoods. The authors theoretically analyze that the proposed method has more expressive power than decoupled GCN. 

**Strengths:**
* The proposed method shows competitive performance on many benchmark datasets. The empirical performance of NAGphormer is outstanding.
* The multi-view/multi-scale representation of a node (a sequence of aggregated node features) is an interesting idea. The late fusion of the node features is new. 

**Weaknesses:**
* One of the main contributions is "a sequence of tokens" for a node. Authors could provide additional ablation analyses. For instance, simple feature concatenation is one naïve approach. Compared to straightforward construction, the authors should show the performance gain of the sequence of token node representation.
* The authors argue that existing MPNNs have limitations such as over-smoothing and over-squashing. However, recent studies address those limitations, and it is unclear what the implications are for the NAGphormer. From the ablation study over the depth of the model, it seems that NAGphormer also suffers from over-smoothing or over-squashing problems since, as the depth increases, the performance deteriorates.
justification_for_why_not_higher_score: See the above-mentioned weaknesses. 
justification_for_why_not_lower_score: See the above-mentioned strengths.
Decision: Accept: poster