Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 
# Summary

This paper proposed a simple graph neural network architecture that is easy to scale up and perform stochastic training. Instead of performing message passing as commonly used GNN, this paper first performs weighted combinations of node features per each hop of the neighbors of a center node, and then performs either CNN or attention mechanism to aggregate the features and obtain center node embedding. Since the feature aggregation can be performed offline, and the computation can easily be decomposed and stochastic training is straightforward, the method can easily scale up to graphs with 10M nodes. Experiments on median size or large size graphs show the comparable or better performance than alternatives. 

# Pros

- The idea is simple and easy to implement, while being effective at the same time. 
- The new design of the architecture 
- Experiments on large scale graphs are convincing.

# Cons

- some comparisons are incomplete
- Not sure how general this approach would be
- time/memory cost can be reported and compared


# Details

Overall I lean towards accepting the paper. 

This paper provides a simple yet efficient and effective approach for graph node embedding calculation. It enjoys similar computation efficiency as the SGC, but is a bit more expressive in the design, where the CNN or attention is introduced on top of the per-hop embeddings. I like such a simple design that adds the expressiveness without too much additional cost. 

It is also good to see the large scale experiments on OGB graphs. 

There are several aspects that can potentially be improved:

1. The SGC results are not presented in Table 4 or Table 5. It is necessary to include, as this might be the most relevant/comparable baseline.

2.  Would this approach be useful for graph classification? I understand that the main purpose of this approach is scalability, but it would also be good to know the potential limitation on its parameterization. Also it would be more comprehensive to see the results on small benchmarks like Cora, Pubmed, etc,. This is mainly to polish the paper and get a better understanding for users. It would be fine if the results are worse on these small graphs. 

3. The runtime (during preprocessing, stochastic training, etc) and memory cost can be reported.

# Questions

I’d like to see the replies to my questions above. 

# Improvement

It would be good to include additional experiments as mentioned above, to make the paper more comprehensive. 

review_title: review for "Neighbor2Seq"

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors proposed a neighborhood to sequence construction & pre-training approach to handling graph representation learning on large graphs.

The merits of this work include:

1. provide a decent attempt toward solving the computation bottleneck for representation learning on large graphs;
2. discusses and shows the benefits of the pre-training based on (unsupervised) sequence learning.

The limitations, on the other hand, is obvious:

1. Pre-training is a relatively standard technique for representation learning on large graphs, and the schema proposed in this paper has very limited novelty;
2. The application of attention mechanism for sequence learning is also a standard practice that has been widely adopted in this domain;
3. The only part where this paper may distinguish itself from the previous work is how the sequence is constructed from the neighborhood. However, minimal theoretical discussion and empirical ablation study are provided to reveal the guarantees & benefits of the proposed method.

Therefore, the limited novelty and contribution of this paper clearly outweigh its merits.

=======================================

After reviewing the response from the authors, I decide to change my evaluation score and confidence score.
review_title: Limited novelty and contribution

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes a method called neighbor2seq that converts the hierarchical structure of the center node to a sequence during message passing in graph neural networks. The proposed method aims to mitigate the issue of excessive computation and memory requirement of training graph neural networks. The proposed models Neighbor2Seq+Conv and Neighbor2Seq+Attn are tested on several datasets including a large scale benchmark dataset (ogbn-papers100M). The result shows some improvement especially on ogbn-papers100M while the improvement is not very obvious on other datasets.

Strength:
1. The idea of converting the graph topology to a sequence that could be tackled with methods designed for grid-like data is good. 
2. The proposed method shows improvement on a large scale dataset. There are also ablation studies that are useful to understand different components in the method, for example, removing the sequence information (position encoding here) clearly hurts the model performance. But it's surprising to see that Neighbor2Seq+Conv is better than Neighbor2Seq+Attn. I think there could be more information/experiment/insights added to explain why this is the case.

Weakness:
1. Since the proposed model is trying to mitigate the excessive computation and memory requirement issues, make it more efficient, and alleviate over-squashing, I'm expecting to see more in-depth analysis and empirical/theoretical justification with regard to those issues that the method is trying to solve. However, there's only some time complexity comparison and some argument about over-squashing. Can you provide the comparison of space complexity since memory requirement mitigation is one of your motivation? Also, Neighbor2Seq does not seem to improve upon the computation as compare with most of the methods listed in table 1? For the argument of alleviating over-squashing, can you provide more details? Why is converting to a sequence alleviating over-squashing? It seems that some sequence models also suffer from over-squashing, isn't it (trying to squash the whole sequence information into a single vector)? Please provide more explanation/analytical results, etc.
2. The experiment results do not seem to improve a lot compared with existing models for some datasets and tasks. It seems that Neighbor2Seq+Conv consistently performs better than Neighbor2Seq+Attn in all experiment. Can you provide analysis of the number of parameters of your proposed model (2 variants) compared with existing models? Since people usually see that attention based approach performs better, is it because conv based one has more parameters. Does the proposed method have more parameters than existing models in general? Can you also provide some empirical comparison on the training time of your model compared with baseline models?
review_title: need more clarification on the connection of the method and the issues it's trying to mitigate

final_score: rating: 5: Marginally below acceptance threshold
review_content: Overall, the paper propose an interesting approach for computing node embeddings in a scalable way.
However, the contribution is incremental as the idea of embedding nodes using sequences is not new; moreover, the discussion with prior works is very weak.

Concretely, important related works are missing. 
There is an ICML 2018 paper, "Anonymous Walk Embeddings" (https://arxiv.org/pdf/1805.11921.pdf). There are many following up papers as well. The idea of this line of works is to embedding node/graphs by random walk sequences. While the approaches are not exactly the same as  Neighbor2Seq, the idea of embedding nodes using sequences is not new. However, none of these works are mentioned in this paper. The authors should compare these papers in the experiments as the baselines. Without such comparison, it is hard to evaluate the performance gain of the proposed Neighbor2Seq.

Additionally, the discussion with prior works is very weak.
The paper misleads the readers by arguing "However, they have inherent difficulties when applied on large graphs due to their excessive computation and memory requirements" in Section 2.1. The paper refers 
However, existing approaches can scale to huge graphs. For example in the PinSage paper (https://arxiv.org/pdf/1806.01973.pdf), they can scale their GNN model to 3 billion nodes. Failing to mentioning this point is misleading for the readers, and is exaggerating the motivation of this paper.

More comments:
1 The exact configuration of the Neighbor2Seq model is not mentioned. Providing an algorithm will greatly help.

2 I can imagine multiple ways for sampling sequences from a node's neighborhood. However, they are not discussed in the paper.

3 How does the expressive power of Neighbor2Seq compares with WL test? I assume Neighbor2Seq is theoretically less expressive than WL test. 

4 I guess there will be failure cases of this kind of Neighbor2Seq, when the topology of node neighborhood structure matters for the final performance. For example, Neighbor2Seq probably won't perform well for graph isomorphism tests. I suggest mentioning potential limitations in the paper.
review_title: Lacks discussions with prior works

Meta-review: This paper presents a way to aggregate and precompute node features on a graph to enable fast parallel training of neural models on massive graphs for various node prediction tasks.  We have seen quite a few papers in this line of work (precompute node features without training, and then treat the nodes as independent during training) recently and this is a continuation in this trend.

Most reviewers lean toward rejection.  The main concern is the lack of novelty and the marginally better results reported in the experiments.  In some sense, the proposed method could be thought of as replacing the concatenation operation of node features across multiple hops used in the SIGN paper with a sequence model, either conv + pool, or attention.  Given this, the novelty of this paper is indeed a bit limited.  Additionally, it is unclear why this sequence model perspective is better than concatenation, which should be in principle more expressive and in practice faster and more efficient (as also reported in Table 6).

I recommend rejecting this paper, but do encourage the authors to position their work better with respect to prior work and really consider what’s the defining advantage of their approach compared to alternatives, like SIGN.
Decision: Reject