Venue: NeurIPS 2022 Conference

Reviews:

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: Most existing node sampling strategies in Graph Transformers are agnostic to the graph properties and do not consider long-range relationships between nodes. To address this issue, the authors of the paper propose  Adaptive Node Sampling for Graph Transformer (ANS-GT), which includes an adaptive node sampling strategy to account for graph properties to improve the efficiency of the Graph Transformer. ANS-GT also incorporates complementary global information through graph coarsening and hierarchical attention schemes. State-of-the-art results are shown on 6 benchmark datasets for the semi-supervised node classification task.
strengths_and_weaknesses: Strengths: 
1. The authors provide sound statistics showing that no sampling strategy performs consistently for graphs with different homophily ratios, thus requiring an adaptive node sampling strategy.
2. They formulate the problem as a multi-armed bandit problem and use the attention score as a reward.

Weakness: 
1. On line 133, bold uppercase H is used to denote the hidden state of the self-attention module, and bold lowercase h is used to denote the hidden state at position i. On line 137, an uppercase H is used to indicate the total number of heads, and a lowercase h is used to indicate heads. Also, on line 136, a bold uppercase W is used to denote the weight matrix in the self-attention module. On line 150, a capital W is used for edge weights. These letters are a bit overused and cause confusion. Sometimes bold uppercase letters are used for matrices, and sometimes lowercase letters are used for matrices. Sticking to one style would be great.
2. In Table 2 where different coarsening rates are compared, it'd be great to add c = 0 as a baseline and more possible rates.
questions: 1. What is the difference between ANS-GT and models that learn linear layers to predict adjacent nodes to attend?  
limitations: 1. Mathematical formulas are confusing and a bit difficult to read.
2. The performance relies on the external graph coarsening method which is not updated during ANS-GT training.
3. It would be nice to see evaluations on graph tasks other than node classification.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes a Transformer architecture for graph-structured data, especially on large graphs. Most existing graph Transformers focus on small-scale graphs and have difficulty learning node representations on large-scale graphs due to a scalability issue. To generalize a Transformer to large graphs, most works use fixed node sampling strategies. This paper addresses these challenges by proposing Adaptive Node Sampling for Graph Transformer (ANS-GT), which is based on an adversary bandit problem. Also, to capture long-distance dependencies, the authors present a hierarchical attention scheme for Graph Transformer with graph coarsening algorithms.
strengths_and_weaknesses: **Strengths**

1. The paper is clearly written and easy to follow.
2. The paper addresses the challenges of graph Transformers on large-scale graphs, which is an important problem.
3. The application of a multi-armed bandit mechanism to sampling informative nodes is interesting and seems clever.
4. Motivation is well articulated with experiments.

**Weakness**

1. The proposed methods consider heterophilic graphs. So, it would be better if graph neural networks for heterophilic graphs are included in related works. (Zhu, Jiong, et al., Chien, Eli, et al.)
2. There are many graph neural networks for heterophilic graph datasets such as H2GCN and GPRGNN (Zhu, Jiong, et al., Chien, Eli, et al.). It would be better if more baselines are included in Table1.
3. The paper proposes ANS-GT for generalizing graph Transformers to large-scale graphs. But, the largest dataset used in this paper is Pubmed, which consists of 19,717 nodes. At least I’d love to see the performance on OGB datasets such as ogbn-arxiv.
4. The contribution of each component of ANS-GT such as super nodes and global nodes is unclear. Even though the supplement includes ablation studies on the number of super nodes and global nodes, the experiments are limited to Cora dataset.
5. I think that the number of augmentation $\mathcal{S}$ needs to be considered when calculating the computational complexity of ANS-GT.

___
Zhu, Jiong, et al. "Beyond homophily in graph neural networks: Current limitations and effective designs.", NeurIPS 2020.

Chien, Eli, et al. "Adaptive universal generalized pagerank graph neural network.", ICLR 2021.
questions: 
1. It would be better if the comparison with heterophilic graph neural networks is included. Is there any comparisons with heterophilic graph neural networks such as H2GCN and GPRGNN?
2. The contribution of each component of ANS-GT is unclear. Is there any ablation study on the graph coarsening and the global nodes?
3. ANS-GT is the graph Transformer for large-scale graphs. But the experiments has been conducted on relatively small datasets compared to OGB. If it is applicable, please include the experimental results on OGB datasets such as ogbn-arxiv.
4.  I think that the baselines except for Gophormer are trained without augmentation. So, I wonder the performance of ANS-GT when the number of input sequences $\mathcal{S}$ is 1.
limitations: The authors have adequately addressed the limitations.
review_title: null

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: This paper proposes a new transformer-based architecture for graph-structured data with adaptive node sampling and hierarchical attention. To learn effective sparse token/node sampling, the authors cast the learning as a multi-arm bandit problem to capture long-range dependency as well as messages from close neighbors. Unlike previous sampling strategies that do not take into account the characteristics of graphs, the proposed method learns the effective sampling by adjusting the weights of a set of sampling schemes. Optimizing these weights is formulated as a bandit problem.
strengths_and_weaknesses: * This paper pinpoints the limitations of transformers for graph-structured data. Especially for large-scale graphs, transformers suffer from quadratic scalability. Although hierarchical transformers with windows like SWIN transformer have been studied, due to the irregularity of graphs, they could not be directly extended to the graph domain. So, combining with previous efforts to design efficient node sampling schemes in the graph domain, the authors proposed a strategy to learn to combine multiple node sampling schemes. It is an interesting direction.
* The paper is well-written. Even though this paper requires knowledge of multiple previous works, this paper concisely introduced related methods with equations. 
* The proposed method achieved significant improvement on top of a Graph Transformer. 
questions: * Transformer with multi-arm bandit formulation is studied in the context of memory replay. Transformer with Memory Replay [AAAI2022]: Transformer with Token Replay. It is not directly related to graph neural networks, but more transformer+multi-arm bandit frameworks could be discussed in the related work section. 
* Heterophily graph data have been recently studied by multiple seminal works. Geom-GCN, H_2GCN, and more recent works. The previous works compared their performance with more datasets: Texas, Wisconsin, and Cornell. Also, H2GCN achieved competitive performance. Those methods must be included as baselines. Another problem is that the dataset split is different from the graph neural networks which studied heterophilic graphs. Because of that, the performance provided in this paper is not compatible with GNNs, which are specifically designed for heterophilic graphs. 
* If the attention is used to define the reward, then why are the pre-defined node sampling methods needed? Is there a way to directly predict the nodes that will get the high attention scores and use those as a distribution for sampling?
* Do the node sampling methods need to provide relative importance of nodes given a centner node? How can you update the relative importance of other nodes given a center node? In addition, if the attention was computed for each center node, then why does attention needs to be computed for all tokens as in Figure 2? Figure 2 was a bit busy and confusing.
limitations: * Overall, the paper is well-written. The proposed method has many interesting components, and it is a novel construction. However, the experiments of this paper failed to include strong and recent graph neural networks, which have shown their effectiveness on both homophilic and heterophilic graphs. Also, more heterophilic graphs could be considered as previous works in the literature.
* Node sampling is the main contribution, but the discussion about supernodes and hierarchical attention was relatively less clear due to a short introduction.
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 paper tries to scale up graph transformers to larger graphs with two novel methods. They first identify that the challenge of large graphs for graph transformers are agnostic about the graph structure during training, which motivates them to use bandit learning to utilize multiple node sampling strategies simultaneously. Another challenge is that the graph transformers are unable to capture distant information, which was tackled by introducing a hierarchical attention mechanism that allows the nodes to attend to a coarsened graph sparsely. While keeping the computational complexity linear to the number of nodes, the proposed method achieves state-of-the-art results on multiple datasets.
strengths_and_weaknesses: The paper is well-motivated, with an investigation of current node sampling strategies to show that the effective sampling strategies may depend on the actual dataset. The proposed solution, i.e. adaptive sampling with bandit learning, well fits the needings and is empirically supported by the evidence shown in fig 3. The other improvement -- the hierarchical attention -- is both novel and effective for distant information capturing.

The paper is well written, with a clear structure and simple notations to follow. Together with the diagrams shown in fig 2, the presentation of this work is neat and illustrative.

The experiment results are strong, with consistent improvement over the baselines. The ablation study shows that both tricks are working and effective, especially compared to other graph transformers.

The paper is great overall, and I trust the paper would have a positive impact on the field of GNNs. However, I also observe a few drawbacks that might hurt the influence of the paper:

1. Using bandit learning to tune the weights of sample strategies enables the model to automatically adjust the weights, and fig 3 shows that the weights would quickly converge. However, it is not convincing to show the necessity of bandit learning. I wonder if a baseline that simply takes the average of 4 distributions (i.e. fixing the weights to be 0.25) can achieve similar performance.

2. While the coarsened graph is a good choice to capture distant information, it introduces extra algorithmic computational overhead. It would be good if the authors can provide an estimate of the running time of the coarsening algorithm compared to the training/inference of the graph models.

3. A minor suggestion: It is a bit confusing to boldface "Reward Scheme" in L226 because you just said you would use 4 sampling approaches and have exactly 4 boldfaced items.

4. It would be good to provide more details about the employment of the coarsening algorithm. A succinct description of the algorithm will make the paper more self-contained.

questions: 1. Although the hierarchical graph attention is a novel method proposed in this paper and the other 4 strategies (1-/2- hops, KNN, and PPR) are existing ones, all of them can be treated as a distribution over all nodes. In this sense, I wonder why don't you incorporate hierarchical attention as part of the bandit learning?

2. For the attention over the coarsened graph, how do you represent the supernodes? Do you aggregate the node features within each cluster, or do you pick a representative? Or do they have their own features that are not shared with their member nodes (if so, how are they related to their members?)?
limitations: I don't think this paper will have potential societal impacts.
review_title: null

Meta-review: metareview: The paper proposes to account for the graph properties when performing node sampling. The proposed method learns the effective sampling by adjusting the weights of a set of sampling schemes, based on an adversary bandit formulation. Besides, a hierarchical attention scheme for Graph Transformer is presented with graph coarsening algorithms. Overall the algorithm is sound and effective, as shown empirically on a range of benchmarks. The paper is well-written. The reviewers asked for comparison with other methods on more datasets, which the authors have partially resolved in their responses. 
confidence: Less certain
Decision: Accept