Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this work, the authors mainly combine the GNN and Transformer to learn both local and global information in large-scale graph.
main_review: strengths

1. The paper is easy to follow, the ideas combine the GNNs and Transformer is interesting, take benefits of the GNN, local aggregation and Transformer, global aggregation.

2. The coarsening part is good, to reduce the complexity of the self-attention in the Transformer.

3. A sampling techniques are also adopted for mini-batch training.


Weakness:
1. The novelty of this work is not very high, it combines a lot of existing of techniques, for example GNN, Transformer, Graph Coarsening, Sampling, PPR etc. These methods are widely explored[1, 2].  The overall design is very straightforward. Somehow I feel the model is a little heavy with more model parameters.

[1] https://openreview.net/forum?id=uxpzitPEooJ
[2] https://arxiv.org/pdf/2106.05150.pdf

2. The idea of the global and long range dependecies is also widely expolited, For example 
[1] Geom-GCN: Geometric Graph Convolutional Networks
[2] Improving Breadth-Wise Backpropagation in Graph Neural Networks Helps Learning Long-Range Dependencies

summary_of_the_review: In summary, I think the idea of combine GNN and Transformer is very interesting. However, the novelty of this work is very straightforward, a mixture of many existing work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to use the transformer architecture on the coarse graph obtained from the graph coarsening algorithm.

To be more specific,
* Since directly using the transformer architecture to the large-scale graph is computationally prohibitive, the authors use the existing graph coarsening algorithms to the large graphs, and then use the transformer on the coarse graphs, which can capture the global information of the given graph in contrast to the GNNs capturing local information.
* To simultaneously use both local and global structures of the graph, the authors first separately capture the local and global information of the given graph with GNNs on the original graph and transformers on the coarse graph, respectively, and then propagate information of local and global to each other with the cross-view propagation scheme.
* The authors show that the proposed Coarformer outperforms baselines on node classification tasks, and also show that the proposed model is highly efficient against the global transformer models for graphs.
main_review: ### Strengths
* Application of transformer on large-graphs with graph coarsening is a relatively undiscovered problem (though not entirely novel, see below weaknesses).
* Information propagation across GNNs and transformer to capture both local and global information on graphs is novel and valuable.
* The paper is well-written and easy to understand.

### Weaknesses
* Using transformer on the compressed graph is already discovered idea [1]. Specifically, [1] captures the local information on the original graph with GNNs, and then further captures the global information on the compressed graph with transformer. Also, the idea of alleviating computational complexities, both memory and time, in the paper is similar to the mentioned previous work [1].
* In Table 2, it seems the authors do not incorporate the time for graph coarsening. If the authors compress the large graph, then the resulting computational cost for coarsening is likely to be large. What relative cost does the proposed method needs for graph coarsening?
* In Figure 2, the authors only display the GPU memory usage of small size graphs, namely Cora and Chameleon. I think the extra memory usage required for the proposed method is relatively increasing, when we use the large-size graphs that authors tackle. Thus, since the authors target the large graphs, I recommend the authors to change the datasets in Figure 2 to larger ones, such as OGB or PubMed.
* In Table 4, I think the experimental comparisons against baselines are not enough or entirely fair. The authors exclude the powerful transformer-based baseline, namely Graphormer, but also it seems the authors use a small number of batches for baselines (Correct me if I misunderstand).

### Typos
* In Section 3.3, I think the $\beta$ in the sentence "we adopt $\beta=1$ in our experiment" should be changed to the $\gamma$. The $\beta$ is already defined as the learnable parameter for the PPR matrix in Section 3.1.
* In the caption of Table 1, "." is missing at the end.

---
[1] Baek et al., Accurate Learning of Graph Representations with Graph Multiset Pooling, ICLR 2021.

---
**-------------------- After rebuttal --------------------**

Summing up all my reviews and follow-up comments, I think this paper is above the borderline, and I lean towards an acceptance of this work.
summary_of_the_review: I think this is a borderline paper, as graph coarsening to use the transformer on large graphs is not entirely novel, however, it also has clear merits: a novel scheme of information propagation across original and coarse graphs; an almost complete piece of work except for some minor issues in the weaknesses above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes Coarformer, a two-view architecture that consists of a standard GNN learning pipeline, and a Transformer over a coarsened graph.

This paper represents an interesting idea that scales Transformer to large graphs.
main_review: Overall, this paper tackles an important question on scaling Transformer to large graphs.
The proposed method is technically sound. 
The experimental results are not very strong (performance gain over baselines are marginal).

With that being said, I have the following concerns for the paper:

1 The proposed Coarformer is not well motivated and seems overly complicated. 
It seems that the main contribution is to operate the Transformer on a coarsened graph. 
The rest of the method is quite standard.
I think a simpler model to discuss is to use the GNN node embeddings as the input to the coarsened graph, or directly combine the predictions from both models.

2 Proposition 1 is not well explained. I'm not sure why it can lead to the claim that "Coarformer can cooperate with mini-batch training and thus is viable on large graphs".

3 How important is the graph coarsening algorithm? How scalable is the algorithm being used?


summary_of_the_review: Overall, I like the motivation of the paper. The proposed methodology should be improved though. And the experimental results are not very strong.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes hierarchical neural network model for processing graphs. The lower level can use any GNN model suitable for processing smaller subgaphs of the original graph while the higher level part realized by a transformer operates on an abstracted 'coarse' graph.
main_review: Strong points
* I find the empirical part of the paper solid. Training is performed over many splits. The model is tested on several datasets and many baselines and ablations are presented.
* The model is more memory efficient than other baselines which might be important in practical applications.

Weak points:
* Most of the results where Coarformer outperforms other baselines are not statistically significant (e.g. in Tab 1 and 3), there is usually some baseline that has mean value inside the confidence interval of Coarformer. However overall the model performs strongly and it is great that authors report the confidence intervals. 
* The idea of using hierarchical graph representations to bridge long range dependencies isn't new, however I feel that prior work isn't properly discussed, other hierarchical graph models are missing in the Related Work section. Papers like DiffPool https://arxiv.org/abs/1806.08804 are highly relevant in my opinion. Other relevant papers are e.g. https://aclanthology.org/2020.emnlp-main.710.pdf or https://arxiv.org/pdf/2105.03388.pdf 

Question:
* Sec 3.1 --- Is use of PPR as attention bias in graph transformers new? No citation is in that paragraph.
* Loss on coarse graph is just auxiliary, correct?
* How does the number of Coarformer's parameters compare to other compared models? Is lower memory consumption just a function of fewer parameters or is it solely due to the different structure of the computation graph?
* Why are you testing just transformer based architectures on the global scale? E.g. GraphSAGE can be used for both local and global level.


Presentation improvements:

* BERT (Kenton & Toutanova, 2019) is a strange citation for BERT, I was expecting Devlin et al.
* Cite PPR.
* Sec 3.1 says that \Beta is a learnable param, however Sec 3.3 says it is set to 1 for simplicity. I would omit \Beta completely since I don't see any value in it. In every formula one can add similar hparams that are set to 1 and they don't add any value to the model.
* Related Work (no S)
* Define HPO, I get that it is hyper param optimization but it isn't explicitly stated.
* Cite SPD.
* Add at least one sentence describing VN, VE and Alg JC and cite them.
* Instead of Tab 5 a graph with 'c' on the x axis would be more appropriate. It will be easier to interpret the data and see possible trends in it.
* Table 12, Cornell column: Coarformer is in bold even though GT has better result.
summary_of_the_review: I am slightly leaning towards acceptance. While I think that related work should be better discussed I think that many people can be interested in low memory overhead of the model and the whole community can benefit from that.

--------------- Post Rebuttal -------------------
After the latest round of improvements I believe the paper is above the acceptance bar.
review_title: null

Meta-review: The paper aims to scale transformers to large graphs. In this regard, authors propose to first obtain a "coarse" version of the large graph using existing algorithms. With reduced number of nodes in the coarse graph, we can employ the transformer efficiently to capture the global information. To capture the local information, GNNs are employed. Finally, authors carry out extensive experiments on a range of graph datasets. Also, reviewers do appreciate reporting the confidence intervals. We thank the reviewers and authors for engaging in an active discussion. Unfortunately, the reviewers are in a consensus that novelty of the proposed method is limited: it is combination of existing techniques and similar ideas have been widely used in the literature. Also, the empirical results are not very significant. Thus, unfortunately I cannot recommend an acceptance of the paper in its current form.
Decision: Reject