Hierarchical Graph Transformer with Adaptive Node Sampling
Authors: ZAIXI ZHANG
Qi Liu
Qingyong Hu
Chee-Kong Lee
Venue: NeurIPS 2022 Accept (2022)
Keywords: Scalable Graph Transformers

Abstract: The Transformer architecture has achieved remarkable success in a number of domains including natural language processing and computer vision. However, when it comes to graph-structured data, transformers have not achieved competitive performance, especially on large graphs. In this paper, we identify the main deficiencies of current graph transformers: (1) Existing node sampling strategies in Graph Transformers are agnostic to the graph characteristics and the training process. (2) Most sampling strategies only focus on local neighbors and neglect the long-range dependencies in the graph. We conduct experimental investigations on synthetic datasets to show that existing sampling strategies are sub-optimal. To tackle the aforementioned problems, we formulate the optimization strategies of node sampling in Graph Transformer as an adversary bandit problem, where the rewards are related to the attention weights and can vary in the training procedure. Meanwhile, we propose a hierarchical attention scheme with graph coarsening to capture the long-range interactions while reducing computational complexity. Finally, we conduct extensive experiments on real-world datasets to demonstrate the superiority of our method over existing graph transformers and popular GNNs.

Hierarchical Graph Transformer with Adaptive Node Sampling
Zaixi Zhang Qi Liu 12; Qingyong Hu Chee-Kong Lee*
I: Anhui Province Key Lab of Big Data Analysis and Application, School of Computer Science and Technology, University of Science and Technology of China 2:State Key Laboratory of Cognitive Intelligence, Hefei, Anhui, China 3:Hong Kong University of Science and Technology, 4: Tencent America zaixi @ mail.ustc..du.cn. qiliuqi Setiing@@uttceedu... @ustc.edu.cn ghuag @ esc.ust.hk. checkonglec@lencce @teeeetteeccccmmmmmmmm
Abstract
The Transformer architecture has achieved remarkable success in number of domains including natural language processing and computer vision. However, when it comes to graph-structured data, transformers have achieved competitive performance, especially on large graphs. In this paper, we identify the main deficiencies of current graph transformers: (1) Existing node sampling strategies in Graph Transformers are agnostic to the graph characteristics and the training process. (2) Most sampling strategies only focus on local neighbors and neglect the long-range dependencies in the graph. We conduct experimental investigations on synthetic datasets show that existing sampling strategies are sub-optimal. To tackle the aforementioned problems, we formulate the optimization strategies of node sampling in Graph Transformer as an adversary bandit problem, where the rewards are related to the attention weights and can vary in the training procedure. Meanwhile, we propose a hierarchical attention scheme with graph coarsening to capture the long-range interactions while reducing computational complexity. Finally, we conduct extensive experiments on real-world datasets to demonstrate the superiority of our method over existing graph transformers and popular GNNs.
Introduction
In recent years, the Transformer architecture 33 and its variants (e.g., Bert 7 and VIT [8) have achieved unprecedented successes natural language processing (NLP) and computer vision (CV). In light of the superior performance of Transformer, some recent works [21 38) attempt to generalize Transformer for graph data by treating each node as a token and designing dedicated positional encoding. However, most of these works only focus on small graphs such as molecular graphs with tens of atoms [38]. For instance, Graphormer (38) achieves state-of-the-as performance on molecular property prediction tasks. When it comes large graphs, the quadratic computational and storage complexity of the vanilla Transformer with the number of nodes inhibits the practical application. Although some Sparse Transformer methods 30 19] can improve the efficiency of the vanilla Transformer, they have not exploited the unique characteristics quadratic or at least sub- sub-quadratic space complexity, which is still unaffordable in most practical cases. Moreover, the full-attention mechanism potentially introduces noise from numerous irrelevant nodes in the full graph.
graph data and require
To generalize Transformer to large graphs, existing Transformer- based methods explicitly or implicitly restrict each node's receptive field to reduce the computational and storage
on graphs
Qi Liu is the corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

complexity. For example, Graph- 41 restricts the receptive field of each node to the nodes with top-k intimacy scores such as Personalized PageRank (PPR). GT-Sparse [9] only considers 1-hop neighboring nodes. We argue that existing Graph Transformers have the following deficiencies: (1) The fixed node sampling strategies in existing Graph Transformers are ignorant of the graph properties, which may sample uninformative nodes for attention. Therefore, an adaptive node sampling strategy aware of the graph properties is needed. We conduct case studies in Section to support our arguments. (2) Though the sampling method enables scalability, most node sampling strategies focus on local neighbors and neglect the long-range dependencies and global contexts of graphs. Hence, incorporating complementary global information is necessary for Graph Transformer.
To solve the challenge (I), we propose Adaptive Node Sampling for Graph Transformer (ANS-GT) and formulate the optimization strategy of node sampling in Graph Transformer as an adversary bandit problem. Specifically ANS-GT, we modify Exp4.P method K to adaptively assign weights to several chosen sampling heuristics (e.g.. 1-hop neighbors, 2-hop neighbors, PPR) and combine these sampling strategies to sample informative nodes. The reward is proportional to the attention weights and the sampling probabilities of nodes, i.c. the reward to certain sampling heuristic is higher if the sampling probability distribution and the node attention weights distribution are more similar. Then in the training process of Graph Transformer, the node sampling strategy is updated simultaneously to sample more informative nodes. With more informative nodes input into the self- attentien module, ANS-GT LT can achieve better performance.
To tackle the challenge (2). we propose a hierarchical attention scheme for Graph Transformer to encode both local and global information for each node. The hierarchical attention scheme consists of fine-grained local attention and coarse-grained global attention. In the local attention, we use the aforementioned adaptive node sampling strategy to select informative local nodes for attention. As for global attention, we first use graph coarsening algorithms [26] to pre-process the input graph and generate coarse graph. Such algorithms mimic down-sampling of the original graph via grouping the nodes into super-nodes while preserving global graph information as much as possible. The center nodes then interact with the sampled super-nodes. Such coarse-grained global attention helps each node capture disttneee dependencies while reducing the computational complexity of the vanilla Graph Transformers.
We conduct extensive experiments on real-world datasets show the effectiveness of ANS-GT. Our method outperforms all the existing Graph Transformer architectures and obtains srate-of-the-an results on benchmark datasets. Detailed analysis and ablation studies further show the superiority of the adaptive node sampling module and the hierarchical attention scheme.
In summary, we make the following contributions:
We propose Adaptive Node Sampling for Graph Transformer (ANS-GT), which modifies multi-armed bandit algorithm to adaptively sample nodes for attention.
In the hierarchical attention scheme, we introduce coarse-graine caase--rained global attention with graph coarsening, which helps graph transformer capture long-range dependencies while increasing efficiency.
We empirically evaluate our method on six benchmark datasets to show the advantage over existing Graph Transformers and popular GNNs.
2 Related Work
2.1 Transformers for Graph
Recently, Transformer (33) has shown its superiority in an increasing number of domains 7 8, 40), e.g. Bert 77 in NLP and ViT g in CV. Existing works attempting to generalize Transformer to graph data mainly focus on two problems: (1) How to design dedicated positional encoding for the nodes; (2) How to alleviate the quadratic computational complexity of the vanilla Transformer and scale the Graph Transformer to large graphs. As for the positional encoding. GT [9] firstly uses Laplacian eigenvectors to enhance node features. Graph-Bert [41] studies employing Weisfeiler-Lehman code to encode structural information. Graphormer (38) utilizes centrality encoding to enhance node features while incorporating edge information with spatial (SPD-indexed attention bias) and edge encoding.
SAN 21 further replaces the static Laplacian eigenvectors with learnable positional encodings and

---

designs an attention mechanism that distinguishes local connectivity. For the scalability issue, one immediate idea is to restrict the number of attending nodes. For example, GAT [4 and GT-Sparse [ only consider the 1-hop neighboring nodes; Gophormer [46] uses GraphSAGE
sampling to uniformly sample ego-graphs with pre-defined maximum depth; Graph-Bert 41 restricts the receptive field of each node to the nodes with top-k intimacy scores (e.g., Katz and PPR). However, these fixed node sampling strategies sacrifice the advantage of the Transformer architecture. SAC [22] tries to use LSTM edge predictor to predict edges for self-attention operations. However, the fact that LSTM can hardly be parallelized reduces the computational efficiency of the Transformer.
2.2 Sparse Transformers
In parallel, many efforts have been devoted reducing the computational complexity of the Trans- former in the field of NLP 23 and CV 32
In the domain of NLP, Longformer 2 applies block-wise or strode patterns while only fixing on fixed neighbors. Reformer [9 replaces dot-product attention by using upproximate attention computation based on locality-sensitiie hashing. Routing Trans- former [30] employs online k-means clustering on the tokens. Linformer (35] demonstrates that the self-attention mechanism can be approximated by low-rank matrix and reduces the complexity from (n²) to (nn). As for vision transformers, Swin Transformer [24] proposes the shifted windowing scheme which brings greater efficiency by limiting self-attention computation to non-overlapping local windows while also allowing for cross-window connection. Focal Transformer [37] presents a new mechanism incorporating both fine-grainee local and coarse-grained global attention to capture short- and long-range visual dependencies efficiently. However, these sparse transformers do not take the unique graph properties into consideration.
2.3 Graph Neural Networks and Node Sampling
follow a message- meessage-psssing passing schema that iteratively updates the representation of node by aggregating representations from neighboring nodes. When generalizing to large graphs, Graph Neural Networks face a similar scalability issue. This is mainly due to the uncontrollable neighborhood expansion in the aggregation stage of GNN. Several node sampling algorithms have been proposed to limit the neighborhood expansion, which mainly falls into node-wise sampling methods and layer-wis, wise sampling methods. node-wise sampling, each node samples k neighbors from its sampling distribution, then the total number of nodes in the (-th layer becomes (kk). GraphSage [ is one of the most well-known node-wise sampling methods with the uniform sampling distribution. GCN-BS (25) introduces variance reduced sampler based on multi-armed bandits. To alleviate the exponential neighbor expansion O(k') of the node-wise samplers, layer- layer-wise samplers define the sampling distribution probability of sampling nodes given a set of nodes in the upper layer [4] [6] 49). From another perspective, these
Graph neural networks (GNNs) 18
sampling methods also be categorized into fixed sampling strategies [II] 4 49] and adaptive
strategies (25 39). However, none of the above sampling methods in GNNs can be directly applied
in Graph Transformer Graph Transformer does not follow the message passing schema.
Preliminaries
3.1 Problem Definition
Let G = (A,X) denote the unweighted graph where A E R represents the symmetric adjacency matrix with n nodes, and X E RR is the attribute matrix p attributes per node. The element Aij in the adjacency matrix equals to 1 if there exists an edge between node and node Uj. otherwise A, = O. The label of node v, is yi- In the node classification problem, the classifier has the knowledge of the labels of subset of nodes Vr. The goal of semi-supervised node classification is to infer the labels of nodes in VVVV by learning a classification function.
3.2 Transformer Architecture
The Transformer architecture consists of series of Transformer layers 33 Each Transformer layer has two parts: a multi-head self-attention (MHA) module and a position-wise feed-forward network (FFN). Let H [h kmm] mx denote the input to the self-attention module where d is
3

---

the hidden dimension, h E Rdx1 is the hidden representation at position i, and m is the number of positions. The MHA module firstly projects the input H query-, key., value-spaces, denoted as Q K, V. using three matrices Wq E Rdddxx WK E Rdxdk and Wy E Rdxdy;
Q = HWQ, H V-HWy
(I)
Then, in each head i E {1. 21. B) (B the total number of heads), the scaled dot-product attention mechanism is applied to the corresponding (Qi, K, Vi}:
Q
head, Softmax
V
vdk
Finally, the outputs from different heads are further concatenated and transformed to obtain the final output of MHA:
(H) Concat
Wo,
where W o E Rdxd In this work, we employ dx dy d/ B.
3.3
Graph Coarsening
The goal of Graph Coarsening 29 26
is to reduce the number of nodes graph by clustering them into super-nodes while preserving the global information of the graph as much as possible. Given a graph G = (V, E) (V is the node set and
the edge set), the coarse graph a smaller weighted graph G" = (V', E"). G' is obtained from the original graph by first computing a partition {C1, C2,, ,Cirr of V. i.c., the clusters C₁ ... Civ'' are disjoint and cover all the nodes in V. Each cluster C, corresponds to a super-node in G' The partition can also be characterized by a matrix P {0, 1J1V with Poj = 1 and only if node v; G belongs to cluster Cj. Its normalized version can be defined by P a PD- 1, where D is a [V] |V' diagonal matrix with |C&l as its i-th diagonal entry. The feature matrix and weighted adjacency matrix of G' are defined by X' & pr and A' & pd AP. After Graph Coarsening, the number of nodes/edges in G' is significantly smaller than that of G. The coarsening rate can be defined as V'
[
4 Motivating Observations
To generalize Transformer to large graphs, existing Graph Transformer models typically choose to sample a batch of nodes attention. However, real-world graph datasets exhibit different properties, which makes a fixed node sampling strategy unsuitable for all kinds of graphs. Here, we present simple yet intuitive case study to illustrate how the performance of Graph Transformer changes with different node sampling strategies. The main idea is to four popular node sampling strategies for node classification: I-hop neighbors, 2-hop neighbors, PPR, and KNN. Then, we will check the performance of Graph Transformer graphs with different properties. If the performance drops sharply when the property varies, it will indicate that graphs with different properties may require different node sampling strategies.
We conduct experiments on the Newman artificial net- works [00 since it enable us to obtain networks with different properties easily. More detailed settings can be found in Appendix A Here, we consider the prop- erty of homophily/heteroplin lowing previous works [47), the degree of homophily can be defined as the fraction edges in net- work connecting nodes with the same class label, i.e. Graphs with a closer to 1 tend to have more edges connecting nodes within the same class, i.e. strong homophily; whereas networks with a closer to have more edges connecting nodes in different classes, i.e. strong heterophily.
0.9
0.8
as one example. Fol-
Accuracy
0.7
0.5
1hhp
A ((
0.4
E
KNN
0.3
1.0
a
Figure 1: Performance of Graph Trans- former using different node sampling mech- anisms: --hop. 2-hop, PPR and kNN re- spectively on Newman networks.
As shown in Figure there no sampling strategy that dominates other strategies across the spectrum of

---

a, which supports our claim that an adaptive sampling method needed for graphs with different properties. For graphs with strong homophily (e.g.. = 1.0), it is easy to obtain high accuracy by sampling 1-hop neighbors or nodes with top PPR scores. On the other hand, for graphs with strong heterophily (e-g. = 0.05), the accuracy of using 2-hop neighbors as neighborhoods (i.e., 73.1 73.1%) ()) is much higher than that of using 1 1-hop neighbors and PPR. The probable reason is that the homophily ratio of 2-hop neighbors may rise with the increase of inter-class edges. Finally, Graph Transformer with KNN node sampling can get the most consistent results since KNN only calculates the similarity of attributes. Thus, KNN achieves the best performance (i.e., 77.2% accuracy) when all the nodes connected randomly, i.e. 0.25 for the Newman network.
Hence, considering different graph properties (c.g., homoohiiy-hhcceophily).. Graph Transformer should adaptively sample the most informative nodes for attention. These observations motivate us to design the proposed hierarchical Graph Transformer with adaptive node sampling in Section 5
5 The Proposed Method
In light of the limitations of existing Graph Transformers for large graphs and the motivating observation in the previous section, we propose two effective methods for Graph Transformer to adaptively sample informative nodes and capture the long-range coarse-grained dependencies in this section. We also show that our method has a computational complexity of (n). The overview of the model framework is shown in Figure 2
5.1 Adaptive Node Sampling
Our Adaptive Node Sampling module aims adaptively choose the batch of most informative nodes by multi-armed bandit mechanism. In our setting, it is intuitive that the contributions of nodes to the learning performance can be sensitivsiie Meanwhile, the rewards which are associated with the model training process are not independent random variables across the iterations. The above situation can satisfy the adversarial setting in the multi-armed bandit problem [. To adaptively choose the most informative nodes with the designed sampling strategies, we adjust the method ALBL proposed in [14, which modifies the EXP4.P method 3 EXP4.P possesses a strong theoretical guarantee for the adversarial setting.
Formally, let w' (wi, ... ,wk) be the adaptive weight vector in iteration 4, where the k-th non- negative element w is the weight corresponding to the k-th node sampling strategy. The weight vector w then scaled Pmin > 0. Our ANS-GT adaptively sample nodes based on the probability vector and then obtains the reward of the action.
probability vector = (pi.... pxx) where pt [Pmin- 1] with
For each center node, we consider the sampling probability matrix Q' E K where K is the number of sampling heuristics and is the number of nodes in the graph. Specifically, O%, denotes the k-th sampling strategy's preference on selecting node j iteration and Q' is normalized to satisfy プØ Qf.; = 1. Note that our ANS-GT is general framework and is not restricted to certain set of sampling heuristics. In our work, we adopt four representative sampling heuristics:
1-/2-hop neighbors: We adopt the normalized adjacency matrix = カ- 1011A0 Á for 1-hop neigh- bors and 2 for h-hop neighbors, where À = A + I is the adjacency matrix of the graph G with self connections added and Î is diagonal matrix with D;: Σ, A.j-
We adopts the cosine similarity of node attributes to measure the similarities of nodes. Mathematically, the similarity score S.j between node and j is calculated as Sty = x2-4; ( (x))) where H; is the feature vector of node V;.
KNN:
PPR: The Personalized PageRank (27) matrix S is calculated as: = cll - (1 c) where factor E [0, 1] (set to 0.15 in experiments). A denotes the column-normallied adjacency matrix.
5

---

Input Graph
Proximity Encoding
(c)
Lx
Malmul
the other
Sodtmax
1
(d)
Graph Coarsening
1-0pp neighters
PPH
(g
Schmmsi 1/v2
(e)
Input Sequence
hop zeighöons
KNN
Soore esch node A IM
wf (wip w(ke
(0l
.pk
Update
of DK M.0
Calculate
A daptive Node Sampling Module
2
Sampling Strategies
Figure Model framework our proposed method: (a) An example input graph. The center node for sampling is colored red. (b) We consider four sampling strategies in this work, i.e. 1-hop neighbors, 2-hop neighbors, PPR, and KNN. (c) The proximity encoding module. (d) Graph coarsening to cluster nodes into super-nodes. (e) The adaptive node sampling module. (f) The self-attention module in Graph Transformer. The output node embeddings are used for node classification.
(g) In the sampled input node sequences, the gray nodes are the fine-grained nodes; the white nodes are the coarse- coarse-grained grained nodes from graph coarsening: the green nodes denote the global nodes. (h) We use the first row of the attention matrix, i.e., A1,; multiplying the magnitude of the corresponding value V; to represent the significance of each node. Then we calculate the reward for each sampling strategy and update the weights.
Finally, given the probability vector p¹ and the node sampling matrices Q' the final node sampling probability is:
of
Qh.
(4)
k=1
We introduce novel reward scheme based the attention weights which is intrinsic in Transformer. Formally, given an attention matrix A = (estmaax(K?")ai matrix, i.e., AI,; multiplying the magnitude of corresponding value VÚ to represent the significance of each node the center node: 8; AI.i || In the situation of multiple heads and layers in the Transformer, we average the significance scores in multiple attention matrices. The reward
we use the first row of the attention
to the k-th sampling strategy is: т Σ +,Qi. where N the number of sampled nodes for w! each center node. can be interpreted as the dot product between the significance score vector and the normalized sampling probability vector. The intuition behind the reward design is that the reward to a certain sampling heuristic is higher if the sampling probability distribution and the node significance score distribution are closer. Thus, exploiting such sampling heuristic can help graph transformer sample more informative nodes. Finally, we update w with the reward. In experiments, for the efficiency and stability of training, we update the sampling weights and resample nodes every T epochs. The pseudo-code of ANS-GT is listed in Algorithm
5.2 Hierarchical Graph Attention
We argue that most node sampling strategies (e.g., 1-hop neighbors) focus on local information and neglect long-range dependencies or global contexts. Therefore, to efficiently capture both the local and global information in the graph, we propose novel hierarchical graph attention scheme including ane-ggrineed attention and coarse-grained attention. Specifically, we use the proposed adaptive node sampling for local fined- fined-grained attention. On the other hand, we adopt the graph

---

Algorithm ANS-GT
Input: Total training epochs E; Pmini update period T'; the number of sampled nodes N. Output: Trained Graph Transformer model, optimized w².
1: Set w/ = 1 for k = 1.... K.
2: Calculate the sampling probability matrix Q"
3: for t = 1, ...
do
4: Train Graph Transformer with the sampled node sequences.
5: if 1%T = then
6: Obtains the attention matrices and calculate the significance scores: &; = A1, x || wi W + Pmin for l: = 1, 1,. K.
7: Set W = Ek=ı wt. and set p/. (1 K Pmmin) Ej=1
8:
Calculate // in Equ. 4 and sample N nodes.
9: Set ii=1
s.Qis and update the weight vector wxt1 using Vi
(oman (r 11
.++ w
Wi
10: end if
11: end for
coarsening algorithm 26 to generate the coarsened graph G". The sampled n, super-nodes from G' are used to capture long-range dependencies. Similar to [46]. we also use ng global nodes with learnable features to store global context information. Finally, the hierarchical nodes are concatenated with the center nodes as the input sequences.
For the positional encoding, we use the proximity encoding in [6] (m; 1)) = [i, m {0.-... .V- 1), where Á denotes the normalized adjacency matrices with self-loop. Note that our framework is agnostic to the positional encoding scheme and we left other positional encoding methods such as Laplacian eigenvectors [9] for future exploration. We follow the Graphormer
framework obtain the output of the I-th transformer layer, (1);
( 1) MHA(LN((H ((-))) ((-1)
(EN(LN(H(-))) (
(6)
We apply the layer normalization (LN) before the multi-head self-attention (MHA) and the feed- forward network (FFN).
5.3 Optimization and Inference
In the training and inference, sample S input sequences for each center node and use the center node representation from the final Transformer layer 2(() for prediction. Note that computational complexity is controllable by choosing suitable number of sampled nodes. A MLP (Multi-Layer
Perceptron) is used to predict the node class:
y -MIP SMEP 2((0) )
where Te E cx11 stands for the classification result, C stands for the number of classes. In the training process, we optimize the average cross entropy loss of labeled training nodes Vz:
L f=
Σ
Σ
v log 7
(8)
1VEV ==1
where y; Cx is the ground truth label of center node e. In the inference stage, take bagging aggregation to improve accuracy and reduce variance:
0
S
(9)
1=1

---

Table 1: Node classification performance (meantstd% % the best results are bolded).
Model
Cora
Citesser
Pubmed
Chameleon
Actor
Squirrel
Texas
Cornell
Wisconsin
GCN
87.33+11.38
79.43+11.26
84,86+0.19
60 75
31.39H0
43. 43.1550.18
75. 16
66.74+1.39
64.31+2.16
GAT
86. 26.2294.55
80.1 1306.2
84.40+0.05
63.90+0.66
36.05.0
42.72+0.39
78.76+0.87
76.04+1.35
66.01+1.48
GrapSSGGE
86 06.90
79. 79.23.0.55
86. 19
05.1540
38.5550.46
41 41.26,0026
79.03:144
72.54.1.50
79.41:3.60
APPNP
87.1540.43
79.33+0.35
17.07
519140.56
38.80
37.7620.45
18..85
91.7540.72
82.5613.57
JKN
78.43+0.31 87.70+0065
87 66
62.92240.49
23.4220.28
42.60aa150
77.51=1.72
64.26e1.16
81.20+1 96
Hg
87.92-0.82
77.60 77.60+0.76
89.55+0.14
61.20+0,05
36.22+0.3
38.51-0.30
36.17-2.67
84 84.93+1.89
87.73+1.57
GPRGNN
88.27#0.40
78.46+0..88
89.38
64 64.56611.59
39.27s0:21
46.3440777
91.84a1.25
90.25a1.95
86,58
7184410.62
67.3810.76
82.11
17.8611.20
37.94g0:26
25, 25.68.022
66.70.1.13
60.39.1.66
65.08
SAN
74.02+1.01
70.64
86.22ss).5
55.62a11.43
38.2440.53
25. 25.5653123
10.10:1.82
61.20&1.17
65. 80
Graphormer
72.8510.76
66.2110.83
82.7610.24
36.811199
37,8550.29
25.45.0.12
18.5611.74
59 39.41a1.21
67.53
Gophormer
87.6540.20
76.43+0.78
88.3320.44
57.4060014
37.50s0042
37,8550026
88.251195
89.4641.51
85.0922.00
ANS-GT
88.6010.45
80.25.0.39
89. 59.5620.55
65.42a0.71
40.10:1.12
45.88.034
93.24:1.85
92.10s1.78
88.62s2.24
5.4
Computational Complexity
Compared with existing Graph Transformers, ANS-GT requires extra computational costs on graph coarsening and sampling weights update. Here we want to show that the overall computational complexity of ANS-GT is linear with the number of nodes n. Hence, ANS-GT is scalable to large graphs. First, the computational complexity of graph coarsening is linear with (26) and we only need do it once before training. Second, the computational cost of self-attention calculation in one epoch is (nnS(N + n, + n²y²) where the number of sampled nodes N, the number of sampled super-nodes nz the number of global nodes ng, and the number of augmentations S are specified constants. Finally, the cost of updating sampling weights is linear to which is mainly attributed to the computation of rewards. Empirical efficiency analyses of ANS-GT are shown in the Appendix C
Experiments
6.1 Experimental Setup
Datasets. To comprehensively evaluate the effectiveness of ANS-GT, we conduct experiments on the six benchmark datasets including citation graphs Cora, CiteSeer, and PubMed [18]; Wikipedia
graphs Chameleon, Squirrel; the Actor co-occurrence graph [5]; and WebKB datasets (28 including
Cornell, Texas, and Wisconsin. We set the train-validation-test split 60%/20%/2004 The statistics
of datasets are shown in the Appendix C
Baselines. To evaluate the effectiveness of ANS-GT graph representation learning, com- pare it with 12 baseline methods, including 8 popular GNN methods, i.e. GCN [18] GAT
[34]
GraphSAGE (II), JKNet (36), APPNP (0), Geom-GCN 28 H₂GCN 48), and GPRGNN 6
along with four of Graph Transformers, i.e. GT 9. SAN (11. Graphormer 38 and Gophormer (46). We use node classification accuracy the evaluation metric.
Implementation Details. We adopt AdamW as the optimizer and set the hyper-parameter e to 1e-8 and (31, (22 to (0.99.0.999). The peak learning rate is set to 2e-4 with 100 epochs warm-up stage followed by a linear decay learning rate scheduler. We adopt the Variational Neighborhoods [26] with a coarsening rate of 0.01 as the default coarsening method. All models were trained on one NVIDIA Tesla V100 GPU.
Parameter Settings. In the default setting, the dropout rate is set to 0.5, the end learning rate is set to 1e-9, the hidden dimension d is set to 128, the number of training epochs is set to 1,000, update period T is set to 100, N is set to 20, M is set to 10, and the number of attention head H is set as We tune other hyper-parameters on each dataset based on by grid search. The searching space of batch size, number of data augmentation S, the number of layers L,, number of sampled nodes, number of sampled super-nodes, number global nodes are (8, 16, 32), (4, 8, 16, 32), 4,5, 6). {10, 15, 20, 25), {0, 3, 6, 9}. 2,,2,3) respectively.
8

---

WHagh
Suretin WHGH
200
180
Spock
100
Spea
(a) Cora
(b) Citeseer
(c) Actor
(d) Squirrel
Figure 3: The normalized sampling weights as a function training epochs on four datasets.
6.2 Effectiveness of ANS-GT
Node Classification Performance. The node classification results are shown in Table We apply independent runs random data splitting and report the means and standard deviations. We have the following obervations: (1) Generally, we observe that ANS-GT overperforms all Graph Transformer baselines and achieves state-of-the-art results on nearly all datasets, which demonstrates the effectiveness of our proposed model. (2) We note that some Graph Transformer baselines achieve poor performance rel) compared with graph neural network models. This is probably due to the full graph atten- tion mechanisms the fixed node sampling schemes of existing Graph Transformers. For in- stance, ANS-GT achieves an accuracy of 45.88% on Squirrel while the best baseline has 43.15%.
node classification (e.g.. GT only obtains 25. 65. Squir-
Effectiveness of Adaptive Node Sampling. Our pro- posed adaptive node sampling module can adjust the weights for sampling based on the rewards as the train- ing progresses. To evaluate its effectiveness and give more insights into the ANS module, we show the nor- malized sampling weights as function of training epochs on four datasets in Figure 3 Generally, we observe that the sampling weights of different pling strategies are time-sensitive and gradually stabi- lize with the increase of the number of epochs. Inter- estingly, we find PPR and 1-hop neighbors achieves high weights Cora while 2-hop neighbors dominate other sampling strategies on Squirrel. This may be ex- plained by the fact that Cora and Squirrel are strong dataset respectively. For Cite- seer and Actor, the weights of KNN firstly goes up and gradually decreases. This is probably due to the reason that nodes with similar attributes are most useful for the training at the beginning stage; local neighbors such as nodes with high PPR scores are more useful the munituning stage. Furthermore, Figure 4 shows the ablation studies of the adaptive node sampling module. We can observe that ANS-GT has large advantage compared to its variant without the adaptive sampling module denoted as HGT (e.g., On Chameleon, ANS-GT achieves 65.42% while HGT only has 57.20%).
80
ANS-GT
70
Accuracy
60
40
30
Citeseer
Chameleun
Actor
Squirel
Figure 4: Ablation studies to show the ef- fectiveness of the adaptive node sampling module. HGT refers to the Hierarchical Graph Transformer without adaptive node sampling.
homoopilyyhheerophhin
Graph Coarsening Methods. In ANS-GT, we apply hierarchical attention mechanism where the interactions between the center node and super- nodes generated by graph coarsening are consid- ered. Here, evaluate ANS-GT with different coarsening algorithms and different coarsening rates. Specifically, the considered coarsening al- gorithms include Variation Neighborhoods (VN) 26)]. Variation Edges (VE) 26), and Algebraic (JC) [29. We vary the coarsening rate from 0.01 to 0.50. In Table [ we can observe that there is
Table 2: Sensitivity analysis coarsening algo- rithms and coarsening rate.
Datasel Method
c=0.01
=00.55
c=0.10
c=0.50
==1.00
VN
88.60
88.55
88.1
87.85
87.26
87.95
88.30
87.32
87.22
JC
88.49
88.20
87.46
87.36
87.28
VN
39.72
39.45
40.10
38.83
39.08
Actor
VE
39.20
39.66
39.51
38.94
39.06
39.92
39.09
no significant difference between different coars-

---

ening algorithms, indicating the robustness of ANS-GT w.r.t them. As for the coarsening rate, the results indicate that the coarsening rate of 0.01 0.10 has the best performance.
Conclusion
Motivated by the obstacles to generalize Transformer to large graphs, we propose Adaptive Node Sampling for Graph Transformer (ANS-GT), which modifies a multi-armed bandit algorithm to adaptively sample nodes for attention in this paper. To incorporate long-range dependencies and global contexts, we further design a hierarchical graph attention scheme in which coarse-grainet attention is achieved with graph coarsening. We empirically evaluate our method on six benchmark datasets to show the advantage over existing Graph Transformers and popular GNNs. The detailed analysis demonstrates that the adaptive node sampling module could effectively adjust the sampling strategies according to graph properties. Finally, We hope our work can help Transformer generalize to the graph domain and encourage the unified modeling of multi-modaa data.
8 Acknowledgments
This research was partially supported by grants from the National Natural Science Foundation of China (Grant No.s 61922073 and U20A20229).
References
[1] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-777 77, 2002.
[2] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint 25X5v:2004.05110, 2020.
[3] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourleenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[4] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. ICLR, 2018.
[5] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. ICLR, 2020.
[6] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
[7] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 10XKv:8810.0444 2018.
[8] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint P:Xiv:2010.11922 2020.
[9] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:20/2.0996 2020.
[10] Michelle Girvan and Mark Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821-7826 2002.
[11] William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, pages 1025-1035, 2017.
10

---

[12] Xueting Han, Zhenhuan Huang. Bang An, and Jing Bai. Adaptive transfer learning graph neural networks. In SIGKDD, pages 565-574, 2021.
[13] Dongxiao He, Zhiyong Feng. Di Jin, Xiaobao Wang. and Weixiong Zhang. Joint identification of network communities and semanties via integrative modeling of network topologies and node contents. In AAAI, 2017.
[14] Wei-Ning Hsu and Hsuan-Tien Lin. Active learning by learning, In AAAI, 2015.
[15] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00663 2020.
[16] Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. NeurlPS, 2018.
[17] Zengfeng Huang. Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. SIGKDD, 2021.
[18] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
[19] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. ICLR, 2020.
[20] Johannes Kliepera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. ICLR, 2018
[21] Devin Kreuzer, Dominique Beaini, William L Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2106.03892 2021.
[22] Xiaoya Li, Yuxian Meng, Mingxin Zhou, Qinghong Han, Fei Wu, and Jiwei Li. Sac: Accelerat- ing and structuring self-attention via sparse adaptive connection. NeurlPS, 2020.
[23] Rui Liu and Barzan Mozafari. Transformer with memory replay. AAAI, 2022.
[24] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hicrarchical vision transformer using shifted windows. ICCV, 2021.
[25] Ziqi Liu, Zhengwei Wu, Zhiqiang Zhang, Jun Zhou, Shuang Yang, Le Song, and Yuan Qi. Bandit samplers for training graph neural networks. NeurlPS, 2020.
[26] Andreas Loukas. Graph reduction with spectral and guarantees. J. Mach. Learn Res., 20(11)) 2019.
[27] Lawrence Page, Sergey Brin, Rajeev Motwani, and Temy Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[28) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In /CLR, 2020.
[29] Dorit Ron, Ilya Safro, and Achi Brandt. Relaxation- coarsening and multiscale graph organization. Multiscale Modeling & Simulation, 91) 423, 2011.
[30] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68, 68, 2021.
[31] Zixing Song, Yifei Zhang, and Irwin King. Towards an optimal asymmetric graph structure for robust semi-supervised node classification. In KDD,, pages 1656-1665, 2022.
[32] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. arXiv preprint arXiv:2009.06732, 2020.

---

[33] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 9998-6088, 2017.
[34] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
[35] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv:2006.0440 0000006888 2020.
[36] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, pages 5453-5462, 2018.
[37] Jianwei Yang. Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao. Focal self-attention for local-global interactions in vision transformers. NewrIPS, 2021.
[38] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tin-Yan Liu. Do transformers really perform bad for graph representation? NewrIPS, 2021.
[39] Minji Yoon, Théophile Gervet, Baoxu Shi, Sufeng Niu, Qi He, and Jaewon Yang. Performance- adaptive sampling strategy towards fast and accurate graph neural networks. In SIGKDD, 2021.
[40] George Zerveas, Srideepika Jayaraman, Dhaval Patel, Anuradha Bhamidipaty, and Carsten Eickhoff. A transformer- based framework for multivariate time series representation learning. In SIGKDD, pages 21 2124, 2021.
[41] Jiawei Zhang, Haopeng Zhang, Congying Xia, and Sun. Graph-bert: Only attention needed for learning graph representations. arXiv preprint arXiv:2001.051444 2020.
[42] Zaix Zhang, Qi Liu, Zhenya Huang, Hao Wang. Chee-Kong Lee, and Enhong Chen. Model inversion attacks against graph neural networks. TKDE, 2022.
[43] Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee. Motif-based graph self-supervised learning for molecular property prediction. NeurlPS, 1587 2021.
[44] Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Checkong Lee. Protgnn: Towards self-explaining graph neural networks. AAAI, pages 9127-91 2022.
[45] Zaixi Zhang, Qi Liu, Shengyu Zhang, Chang-Yo Yu Hsieh, Liang Shi, and Chee-Kong Lee. Graph supervide learning for optoelectronic properties of organic semiconductors. ICMI. Al4Science Workshop, 2021.
[46] Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification. arXiv preprint 1rXi:22100.33044 2021.
[47] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS. 2020.
[48] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In NeurIPS, 2020.
[49] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. NeurlPS, 2019.
12

---

Checklist
1. Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
2. Did you describe the limitations your work? [Yes] Please see Appendix.
3. Did you discuss any potential negative social impacts of your work? [Yes] Please see Appendix.
4. Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
1. Did you state the full set of assumptions of all theoretical results? [N/A]
2. Did you include complete proofs of all theoretical results? [N/A]
1. Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [No] The code will be released once the paper is accepted.
2. Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
3. Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
4. Did you include the total amount of computing and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
1. If your work uses existing assets, did you cite the creators? [Yes]
2. Did you mention the license the assets? [N/A]
3. Did you include any new assets either in the supplemental material or as URL? [N/A]
4. Did you discuss whether and how consent obtained from people whose data you'i 're using/curating? [N/A]
5. Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
1. Did you include the full text of instructions given to participants and screenshots, if applica- ble? [N/A]
2. Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
3. Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "hA89PVYiNi", "reviewer": "Reviewer_vEEU", "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.", "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.\n2. The performance relies on the external graph coarsening method which is not updated during ANS-GT training.\n3. It would be nice to see evaluations on graph tasks other than node classification.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. 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.\n2. They formulate the problem as a multi-armed bandit problem and use the attention score as a reward.\n\nWeakness: \n1. 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.\n2. In Table 2 where different coarsening rates are compared, it'd be great to add c = 0 as a baseline and more possible rates.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NaTrOWLTYLf", "reviewer": "Reviewer_cmdK", "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.", "questions": "\n1. 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?\n2. The contribution of each component of ANS-GT is unclear. Is there any ablation study on the graph coarsening and the global nodes?\n3. 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.\n4.  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.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper is clearly written and easy to follow.\n2. The paper addresses the challenges of graph Transformers on large-scale graphs, which is an important problem.\n3. The application of a multi-armed bandit mechanism to sampling informative nodes is interesting and seems clever.\n4. Motivation is well articulated with experiments.\n\n**Weakness**\n\n1. 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.)\n2. 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.\n3. 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.\n4. 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.\n5. I think that the number of augmentation $\\mathcal{S}$ needs to be considered when calculating the computational complexity of ANS-GT.\n\n___\nZhu, Jiong, et al. \"Beyond homophily in graph neural networks: Current limitations and effective designs.\", NeurIPS 2020.\n\nChien, Eli, et al. \"Adaptive universal generalized pagerank graph neural network.\", ICLR 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JMxUFYRsYl9", "reviewer": "Reviewer_BtvG", "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.", "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. \n* 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. \n* 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?\n* 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.\n* Node sampling is the main contribution, but the discussion about supernodes and hierarchical attention was relatively less clear due to a short introduction. ", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n* The paper is well-written. Even though this paper requires knowledge of multiple previous works, this paper concisely introduced related methods with equations. \n* The proposed method achieved significant improvement on top of a Graph Transformer. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "64PVFIp90h", "reviewer": "Reviewer_6Yic", "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.", "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?\n\n2. 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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.\n\nThe 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.\n\nThe 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:\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept