NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs
Authors: Jinsong Chen
Kaiyuan Gao
Gaichao Li
Kun He
Venue: ICLR 2023 poster (2023)
Keywords: Graph Transformer
node classification
neighborhood aggregation
multi-hop neighborhood

Abstract: The graph Transformer emerges as a new architecture and has shown superior performance on various graph mining tasks. In this work, we observe that existing graph Transformers treat nodes as independent tokens and construct a single long sequence composed of all node tokens so as to train the Transformer model, causing it hard to scale to large graphs due to the quadratic complexity on the number of nodes for the self-attention computation. To this end, we propose a Neighborhood Aggregation Graph Transformer (NAGphormer) that treats each node as a sequence containing a series of tokens constructed by our proposed Hop2Token module. For each node, Hop2Token aggregates the neighborhood features from different hops into different representations and thereby produces a sequence of token vectors as one input. In this way, NAGphormer could be trained in a mini-batch manner and thus could scale to large graphs. Moreover, we mathematically show that as compared to a category of advanced Graph Neural Networks (GNNs), the decoupled Graph Convolutional Network, NAGphormer could learn more informative node representations from the multi-hop neighborhoods. Extensive experiments on benchmark datasets from small to large are conducted to demonstrate that NAGphormer consistently outperforms existing graph Transformers and mainstream GNNs. Code is available at https://github.com/JHL-HUST/NAGphormer.

Published as a conference paper at ICLR 2023
NAGPHORMER: A TOKENIZED GRAPH TRANSFORMER FOR NODE CLASSIFICATION IN LARGE GRAPHS
Jinsong Chen 1,2,3,, Kaiyuan 2ao2.3., Gaichao Li Kun 2e
1 Institute of Artificial Intelligence, Huazhong University of Science and Technology
2 School of Computer Science and Technology. Huazhong University of Science and Technology 3 Hooprofft Center Computing Science, Huazhong University of Science and Technology chen jinsong, im im_kai, kai, gaichaolee, brooklet 60) @hust. edu. cn
ABSTRACT
The graph Transformer emerges as new architecture and has shown superior performance various graph mining tasks. In this work, we observe that existing graph Transformers treat nodes as independent tokens and construct a single long sequence composed of all node tokens so train the Transformer model, causing it hard to scale to large graphs due to the quadratic complexity on the number of nodes for the self-attention computation. To this end, we propose a Neighborhood Aggregation Graph Transformer (NAGphormer) that treats each node as sequence containing a series of tokens constructed by our proposed Hop2 module. For each node, Hop2Token aggregates the neighborhood features from different hops into different representations and thereby produces a sequence of token vectors one input. In this way, NAGphormer could be trained in mini-batch manner and thus could scale to large graphs. Moreover, we mathematically show that as compared to category of advanced Graph Neural Networks (GNNs), the decou- pled Graph Convolutional Network, NAGphormer could learn more informative node representations from the multi-hop neighborhoods. Extensive experiments benchmark datasets from small to large are conducted to demonstrate that NAG- phormer consistently outperforms existing graph Transformers and mainstream GNNs. Code is available at
INTRODUCTION
Graphs, as a powerful data structure, are widely used to represent entities and their relations in variety of domains, such as social networks in sociology and protein-protein interaction networks in biology. Their complex features (e.g., attribute features and topology features) make the graph mining tasks very challenging. Graph Neural Networks (GNNs) (Chen et al., 2020c; Kipf & Welling, 2017: Veličković al., 2018), owing to the message passing mechanism that aggregates neighborhood information for learning the node representations (Gilmer et al., 2017), have been recognized as type of powerful deep learning techniques for graph mining tasks (Xu et al., 2019; Fan et al., 2019; Ying et al., 2018; Zhang& & Chen, 2018; Jin et al., 2019) over the last decade. Though effective, message passing-based GNNs have a number of inherent limitations, including over-smoothing (Chen al., 2020a) and over-squashing (Alon & Yahav, 2021) with the increment of model depth, limiting their potential capability for graph representation learning. Though recent efforts (Yang et al., 2020; Lu et al., 2021; Huang al., 2020; Sun et al., 2022) have been devoted to alleviate the impact of over-smoothing and over-squashing problems, the negative influence of these inherent limitations cannot be eliminated completely.
Transformers (Vaswani et al., 2017), on the other hand recently, are well-known deep learning archi- tectures that have shown superior performance in a variety of data with an underlying Euclidean or grid-like structure, such as natural languages (Devlin et al., 2019; Liu et al., 2019) and images (Doso- vitskiy al., 2021: Liu et al., 2021). Due to their great modeling capability, there is growing interest in generalizing Transformers to non-Euclidean data like graphs (Dwivedi & Bresson, 2020;
'The first two authors contribute equally.
1 Corresponning author.

---

Published as a conference paper at ICLR 2023
Hop2Token
Transformer backbone
A Attention-base readout layer
2-hop
Prodiction labols
Oulput
1-hop
Feature vedtors
Multilayer perceptron
O-hop
Atlention-based readout laver
Attention layer
Transformer encoder
Tokm
2
Toleen 0 1
Attilbuted network
Sequence modee
Linear pro ection
Figure Model framework of NAGphormer. NAGphormer first uses a novel neighborhood aggregation module, Hop2Token, to construct sequence for each node based on the tokens of different hops of neighbors. Then, NAGphormer learns the node representations using a Transformer backbone, and an attention based readout function is developed to aggregate neighborhood informa- tion of different hops adaptively. An MLP-based module used in the end for label prediction.
Kreuzer et al., 2021; Ying et al., 2021; Jain et al., 2021). However, graph-structured data generally contain more complicated properties, including structural topology and attribute features, that cannot be directly encoded into Transformers the tokens.
Existing graph Transformers have developed three techniques to address this issue (Min et al., 2022): introducing structural encoding (Dwivedi & Bresson, 2020; Kreuzer al., 2021), using GNNs as auxiliary modules (Jain et al., 2021), and incorporating graph bias into the attention matrix (Ying et al., 2021). By integrating structural information into the model, graph Transformers exhibit competitive performance on various graph mining tasks, and outperform GNNs on node classification (Kreuzer al., 2021; Chen al., 2022) and graph classification (Ying et al., 2021; Jain et al., 2021) tasks on small to mediate scale graphs.
In this work, we observe that existing graph Transformers treat the nodes as independent tokens and construct single sequence composed of all the node tokens to train the Transformer model, causing quadratic complexity on the number of nodes for the self-attention calculation. Training such a model on large graphs will cost huge amount of GPU resources that are generally unaffordable since the mini-batch training unsuitable for graph Transformers using a single long sequence as the input. Meanwhile, effective strategies that make GNNs scalable to large-scale graphs, including node sampling (Chen et al., 2018; Zou et al., 2019) and approximation propagation (Chen et al., 2020b; Feng et al., 2022), are not applicable graph Transformers, they capture the global attention of all node pairs and are independent of the message passing mechanism. The current paradigm of graph Transformers makes intractable generalize to large graphs.
To address the above challenge, we propose a novel model dubbed Neighborhood Aggregation Graph Transformer (NAGphormer) for node classification in large graphs. Unlike existing graph Transformers that regard the nodes as independent tokens, NAGphormer treats each node as a sequence and constructs tokens for each node by novel neighborhood aggregation module called Hop2Token. The key idea behind Hop2Token is to aggregate neighborhood features from multiple hops and transform each hop into a representation, which could be regarded as a token. Hop2Token then constructs sequence for each node based on the tokens in different hops to preserve the neighborhood information. The sequences are then fed into a Transformer-baan the node representations. By treating each node trained a mini-batch manner and hence can handle large graphs even on limited GPU resources.
module for learning sequence of tokens, NAGphormer could be
Considering that the contributions of neighbors in different hops differ to the final node representation, NAGphormer further provides an attention- readout function to learn the importance of each hop adaptively. Moreover, provide theoretical analysis the relationship between NAGphormer and an advanced category of GNNs, the decoupled Graph Convolutional Network (GCN) (Dong al., 2021; Klicpera et al., 2019; Wu et al., 2019; Chien et al., 2021). The analysis is from the
2

---

Published as a conference paper at ICLR 2023
perspective of self-attention mechanism and Hop2Token, indicating that NAGphormer is capable of learning more informative node representations from the multi-hop neighborhoods. We conduct extensive experiments various popular benchmarks, including six small datasets and three large datasets, and the results demonstrate the superiority of the proposed method.
The main contributions of this work follows:
We propose Hop2Token, novel neighborhood aggregation method that aggregates the neighborhood features from each hop into a node representation, resulting in a sequence of token vectors that preserves neighborhood information for different hops. In this way, we can regard each node in the complex graph data as sequence of tokens, and treat them analogously as in natural language processing and computer vision fields.
We propose new graph Transformer model, NAGphormer, for the node classification task. NAGphormer can be trained in mini-batch manner depending on the output of Hop2Token, and therefore enables the model to handle large graphs. We also develop an attention- based readout function adaptively learn the importance of different-hop neighborhoods to further boost the model performance.
We prove that from the perspective of self-attention mechanism, the proposed NAGphormer can learn more expressive node representations from the multi-hop neighborhoods compared to an advanced category of GNNs, the decoupled GCN.
Extensive experiments benchmark datasets from small large demonstrate that NAG- phormer consistently outperforms existing graph Transformers and mainstream GNNs.
BACKGROUND
2.1 PROBLEM FORMULATION
Let G (V, E) be unweighted and undirected attributed graph, where V = {vi, U2, and n n= [V]. Each node E has a feature vector x, E X, where X E RRad is the feature matrix describing the attribute information of nodes and the dimension of feature vector. A Rax= represents the adjacency matrix and D the diagonal degrec matrix. The normalized adjacency matrix is defined Á = 1/2 AD 112 where A denotes the adjacency matrix with self-loops and D denotes the corresponding degree matrix. The node classification task provides a labeled node set Vi and an unlabeled node set V.. Let Y E Raxe denote the label matrix where is the number of classes. Given the labels Yv,, the goal is to predict the labels Yv, for unlabeled nodes.
2.2 GRAPH NEURAL NETWORK
Graph Neural Network (GNN) has become a powerful technique to model the graph-structured data. Graph Convolutional Network (GCN) (Kipf & Welling, 2017) typical model of GNN that applies the first-order approximation of spectral convolution (Defferrard et al., 2016) to aggregate information of immediate neighbors. A GCN layer can written as:
(1+1) ((AH")
where H E x and ( E t (41) denote the representation of nodes and the learnable parameter matrix in the /-th layer, respectively. af-) denotes the non-linear activation function.
Equation contains two operations, neighborhood aggregation and feature transformation, which are coupled in the GCN layer. Such coupled design would lead to the over-smoothing problem (Chen al., 2020a) when the number of layers increases, limiting the model to capture deep structural information. To address this issue, the decoupled GCN (Klicpera et al., 2019; Wu al., 2019) separates the feature transformation and neighborhood aggregation the GCN layer and treats them independent modules. A general form of decoupled GCN is described as (Chien et al., 2021):
K
H ÁH HO) = fx(X),
(2)
k=0
3

---

Published as a conference paper at ICLR 2023
where Z denotes the final representations of nodes, H denotes the hidden representations of nodes propagation step B& denotes the aggregation coefficient of propagation step k, A denotes the normalized adjacency matrix, fo denotes a neural network module and X denotes the raw attribute feature matrix. Such decoupled design exhibits high computational efficiency and enables the model capture deeper structural information. More related works on GNNs are provided in Appendix A.
2.3 TRANSFORMER
The Transformer encoder (Vaswani al., 2017) contains a sequence of Transformer layers, where each layer is comprised with multi-head self-attention (MSA) and position-wise feed-forward network (FFN). The MSA module the critical component that aims to capture the semantic correlation between the input tokens. For simplicity, use the single-head self-atte attentin module for description. Suppose we have an input H RR"d for the self self-attention module where n the number of tokens and d the hidden dimension. The self-attention module first projects H into three subspaces, namely Q K and V:
Q = HW? K = HW* V HW
where Wº RRdxx WK E Rgdxdx and W E Rdxdy are the projection matrices. The output matrix is calculated as:
QK
H' softmax
V.
vdx
The attention matrix, softmax sequence. Specifically, it calculates the dot product between each token pair after projection. The softmax is applied row-wise.
[KK"
captures the pair-wise similarity of input tokens in the
vdk
Graph Transformer. The Transformer architecture has attracted increasing attention in graph representation learning in recent years. The key idea graph Transformer is to integrate graph structural information to the Transformer architecture so learn the node representations. Existing graph Transformers could be divided into three categories: (I) Replace the positional encoding with Laplacian eigenvectors (Dwivedi & Bresson, 2020; Kreuzer et al., 2021) or degree-related feature vectors (Ying et al., 2021) to capture the structural features of nodes. (II) In addition to positional encoding, GNNs are used as auxiliary modules to enable the Transformer model to capture structural information (Jain et al., 2021; Rong et al., 2020). (III) Introduce graph information bias into the attention score of each node pair, e.g., the chortest-path distance (Ying et al., 2021). We provide detailed review of graph Transformer in Appendix A.
3 THE PROPOSED NAGPHORMER
In this section, we present the proposed NAGphormer in details. To handle graphs at scale, we first introduce a novel neighborhood aggregation module called Hop2Token, then we build NAGphormer together with structural encoding and attention-based readout function.
3.1 HOP2TOKEN
How to aggregate information from adjacent nodes into a node representation is crucial in reasonably powerful Graph Neural Network (GNN) architectures. To inherit the desirable properties, design Hop2Token considering the neighborhood information of different hops.
For node v. let (v) {u e Vid(u, u) < k} be its k-hop neighborhood, where d(v, u) represents the distance of shortest path between v and u. We define (u) = {u}, i.e., the 0-hop neighborhood the node itself. Hop2Token, we transform the k-hop neighborhood. AV*(w) (v) into a neighborhood embedding X with an aggregation operator é. In this way, the k-h representation of a node can be expressed as:
(5) By Equation 5, we calculate the neighborhood embeddings for variable hops of node and further construct a sequence to represent its neighborhood information, i.e., S,, = (x., x!. x ). where K is fixed as hyperparameter. Assume x is d-dimensional vector, the sequences of all nodes
x =<(*((v))
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 The Hop2Token Algorithm
Input: Normalized adjacency matrix A; Feature matrix X; Propagation step K Output: Sequences of all nodes X
1: for k = 0 K do
2: for : 0 n do
X X[i]:
4: end for
5: X Áx:
6:
end for
7: return Sequences of all nodes X
in graph G will construct a tensor X E [x*((++) To better illustrate the implementation of HopeToken, we decompose Xg to a sequence
(X,,X1. Xk), where X E IR" "xd can be seen as the k-hop neighborhood matrix. Here we define Xo as the original feature matrix X.
In practice, we apply propagation process similar the method in (Chien al., 2021; He et al., 2022) to obtain the sequence of K-hop neighborhood matrices. Given the normalized adjacency matrix Å (aka the transition matrix (Gasteiger et al., 2019)) and X, multiplying Á with X aggregates immediate neighborhood information. Applying this multiplication consecutively allows us to propa- gate information larger distances. For example, can access 2-hop neighborhood information by AAAX). Thereafter, the k-hop neighhorhood matrix be described as:
X A X
(6)
The detailed implementation is drawn in Algorithm The advantages of Hop2Token is two-fold. (I) Hop2TToken is parameerii method. It can be conducted offline before the model training, and the output of Hop2Tooken supports mini-batch training. In this way, the model can handle graphs of arbitrary sizes, thus allowing the generalization of graph Transformer to large-scale graphs. (II) Encoding k-hop neighborhood a node into one representation is helpful for capturing the hop-wise semantic correlation, which is ignored in typical GNNs (Kipf & Welling, 2017; Klicpera et al., 2019; Chien et al., 2021).
3.2
NAGPHORMER FOR NODE CLASSIFICATION
Figure depicts the architecture of NAGphormer. Given an attributed graph, first concatenate matrix constructed by eigendecomposition to the attribute matrix, and gain structure-aware feature matrix. Accordingly, the effective feature vector for node v is extended as Rdd,, The detailed construction is described in Section 3.3.
Next, we assemble an aggregated neighborhood sequence as S, = (x x!, x by applying Hop2Token. Then we map S, the hidden dimension dm of the Transformer with learnable linear projection:
Z
[x] E; x E.
x
where E E Idd' and (0)
E R (K +1)xdm.
Then, we feed the projected sequence into the Transformer encoder. The building blocks of the Transformer contain multi-head self-attention (MSA) and position-wise feed-forward network (FFN).
We follow the implementation of the vanilla Transformer encoder described in (Vaswani et al., 2017). while LayerNorm (LN) is applied before each block (Xiong et al.. 2020). And the FFN consists of two linear layers with a GELU non-linearity:
z = MSA (LN
1
+ + (()))
(8)
Z FFN LN
Z (
(9)
where / L,..., implies the f-th layer of the Transformer.
In the end, novel readout function is applied to the output of the Transformer encoder. Through sev- eral Transformer layers, the corresponding output ( contains the embeddings for all neighborhoods
5

---

Published as a conference paper at ICLR 2023
of node It requires readout function to aggregate the information of different neighborhoods into one embedding. Common readout functions include summation and mean (Hamilton et al., 2017). However, these methods ignore the importance of different neighborhoods. Inspired by GAT (Veličković et al., 2018), we propose an attention-basee readout function to learn such impor- tance by computing the attention coefficients between O-hop neighhorhood (i.e., the node itself) and every other neighborhood. For detailed implementation, please refer to Section 3.3.
The time and space complexity of NAGphormer are O(n(K + 1) and O(b(K + +1) + 6(K 1)d + d' L). respectively (n: number of nodes, K: number of hops, d: dimension of feature vector, L: number of layers, b: batch size). The detailed complexity analysis is provided Appendix
3.3 IMPLEMENTATION DETAILS
Structural encoding. Besides the attribute information of nodes, the structural information of nodes is also a crucial feature for graph mining tasks. We adopt the eigenvectors of Laplacian matrix of the graph for capturing the structural information of nodes. Specifically, we select the eigenvectors corresponding to the s smallest non-trivial eigenvalues to construct the structure matrix U e _=xx (Dwivedi & Bresson, 2020; Kreuzer et al., 2021). Then combine the original feature matrix X with the structure matrix U to preserve both the attribute and structural information:
X' = X
(10)
Here || indicates the concatenation operator and X' E R=x(d++)) denotes the fused feature matrix, which then used as the input of Hop2Token for calculating the information of different-hog neighborhoods.
Attention-based readout function. For the output matrix Z E R (K++))xdm of node, Zo is the token representation of the node itself and Zu its k-hop representation. We calculate the normalized attention coefficients for its k-hop neighborhood:
exp (Zo IZ,) W
(11)
K E exp( |Z. (Z)
where W. E IR 1x2m denotes the learnable projection and i 1,..., K. Therefore, the readout function takes the correlation between each neighborhood and the node representation into account. The node representation is finally aggregated follows:
K
Zon = Zo
02 Z
(12)
3.4 THEORETICAL ANALYSIS NAGPHORMER
In this subsection, we discuss the relation of NAGphormer and decoupled GCN through the lens of the node representations of Hop2Token and the self-attention mechanism. We theoretically show that NAGphormer could learn more informative node representations from the multi-hop neighborhoods than decoupled GCN does.
Fact 1. From the perspective of the output node representations of Hop2Token, we can regard the decoupled GCN as applying a self-attention mechanism with a fixed attention matrix R ([K+1)x(K+I) where SKA = 3& (k E (O....K)) and other elements are all zeroes.
Here K denotes the total propagation step, represents the current propagation step. 3% represents the aggregation weight at propagation step l: in the decoupled GCN. The detailed proof of Fact is provided in Appendix C. Fact indicates that the decoupled GCN, an advanced category of GNN, only captures partial information of the multi-hop neighborhoods through the incomplete attention matrix. Moreover, the fixed attention coefficients of 3% (k E {0. .O., ...,,,K)) 3 for all nodes also limit the model learn the node representations adaptively from their individual neighborhood information.
In contrast, our proposed NAGphormer first utilizes the self-attention mechanism to learn the repre- sentations of different-hop neighborhoods based on their semantic correlation. Then NAGphormer develops an attention- based readout function to adaptively learn the node representations from their neighborhood information, which helps the model learn more informative node representations.

---

Published as a conference paper at ICLR 2023
Comparison of all models in terms of mean accuracy + stdev (%) on small-scale datasets. The best results appear in bold. OOM indicates the out-of-memory eιror.
Table 1:
Method
Puhmed
CoraFull
Compater
Photo
CS
Physics
GCN
86.54 0.12 61.76
+
89.65 = 0.52 92.70 = 0.20 92.92
= 0.12 96.1 0.07
GAT
86.32 = 0.16 64.47 + 0.18
90.78 + 0.13 93.87
+ 0.11 93.61
# 0.14
96.17 + 0.08
APPNP
88.43 0.15
65,16
0.28
90.18
1 0.17
94.32
1: 0.14 94.49
1 0.07
96.54 0.07
GPRGNN
89.34 = 0.25
67.12
4: 0.31
89.32
4 0.29
94.49
1 0.14
95.13
1: 0.09
96.85
1 0.08
GmphSAINT
88.96
0.16
67.85
+ 0.21
90.22
0.15
91.72
+ 0.13 94.41
+ 0.09
96.43 + 0.05
PPRGo
87,38
0.11
63.54 1. 0.25
88.69 1. 0.21
93.61
1. 0.12 92.52
1 0.15
95.51 0.08
GRAND+
88.64
0.09
71.37 +: 0.11
88.74
4: 0.11
94.75
+ 0.12
93.92
0.08
96.47
0.04
GT
88.79 00 0.12 61.05 + 0.38 91.18 + 0.17
94.74 + 0.13 94.64
+ 0.13 97.05 +: 0.05
Graphormer
00M
00M
OOM
92.74
1: 0.14
OOM
OOM
SAN
88.22 0.15 59.01 + 0.34
89.83 # 0.16
94.86 + 0.10
94,51
# 0.15
0OM
GraphGPS
88.94
0.16 55.76 + 0.23
OOM
95,06
0.13 93.93 + 0.12
0OM
NAGipormer
89.70 0.19 71.51 1 0.13 91.22 1 0.14 95.49
1: 0.11 95.75
0.09 97.34 0.03
4 EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Here we briefly introduce datasets and baselines in experiments. More details are in Appendix D.
Datasets. We conduct experiments on nine widely used datasets of various scales, including six small-scale datasets and three relatively large-scale datasets. For small-scale datasets, we adopt Pubmed, CoraFull, Computer, Photo, CS and Physics from the Deep Graph Library (DGL). We apply 60%/20%/20% train/val/test random splits for small-scale datasets. For large-scale datasets, we adopt AMiner-CS, CS, Reddit and Amazon2M from (Feng et al., 2022). The splits of large-scall scale datasets are followed the settings from (Feng al., 2022). Detailed information is provided in Appendix D.I.
Baselines. We compare NAGphormer with twelve advanced baselines, including: (I) four full- batch GNNs: GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), APPNP (Kliepera et al., 2019) and GPRGNN (Chien et al., 2021); (II) three scalable GNNs: GraphSAINT (Zeng al., 2020), PPRGo (Bojehevski et al., 2020) and GRAND+ (Feng et al., 2022); (III) five graph Transformers' GT (Dwivedi & Bresson, 2020), SAN (Kreuzer et al., 2021), Graphormer (Ying et al., 2021), GraphGPS (Rampásek et al., 2022) and Gophormer (Zhao al., 2021)?.
4.2 COMPARISON ON SMALL-SCALE DATASETS
We conduct 10 trials with random seeds for each model and take the mean accuracy and standard deviation for comparison on small-scale datasets, and the results are reported in Table 1. From the experimental results, can observe that NAGphormer outperforms the baselines consistently on all these datasets. For the superiority over GNN-based methods, it is because NAGphormer utilizes Hop2Token and the Transformer model to capture the semantic relevance of different hop neighbors overlooked in most GNNs, especially compared to APPNP and GPRGNN, which are two decoupled GCNs. Besides, the performance of NAGphormer also surpasses graph Transformer-basee methods, indicating that leveraging the local information is beneficial for node classification. In particular, NAGphormer outperforms GT and SAN, which also introduce the eigenvectors of Laplacian matrix as the structural encoding into Transformers for learning the node representations, demonstrating the superiority of our proposed NAGphormer. Moreover, We observe that Graphormer, SAN, and GraphGPS suffer from the oft-of-memory error even in some small graphs, further demonstrating the necessity of designing a scalable graph Transformer for large-scale graphs.
Another recent graph Transformer, SAT (Chen et al., 2022), is not considered as it reports OOM even in our small-scale graphs.
We compare the performance of our NAGphormer with Gophormer on the datasets reported in the original paper (Zhao et al., 2021) in Appendix E since the authors did not make their code available, and we implemented their algorithm but could not reproduce the same results as reported in their paper. Nevertheless, it still shows that results are very competitive with their reported results.
7

---

Published as a conference paper at ICLR 2023
Table 2: Comparison of all models in terms of mean accuracy + stdev (%) large-scale datasets. The best results appear in bold.
Method
AMiner-CS
Reddit
Amazon2M
PPRGo
49.07 0.19
90.38 + 0.11
66.12 +: 0.59
GraphSAINT
51.86 0.21
92.35
0.08
75.21 0.15
GRAND+
54.67 + 0.25
92.81 = 0.03
75.49
: 0.11
NAGphormer 56.21 + 0.42
93.58 + 0.05
77,43 +: 0.24
Table 3:
The accuracy (%) with or without structural encoding.
Pubmed CoraFull
Computer
Physics
Aminer-
Reddit Amazen2M
W/O-SE
89.06
70.42
95.52
90.44
95.02
97.10
55.64
93.47
76.98
71.51
95.75
95.49
77.43
Gain
+0.64
+1.09
+0.23
+0.78
+0.47
+0.24
0.57
+0.11
-0.45
4.3 COMPARISON ON LARGE-SCALE DATASETS
To verify the scalability of NAGphormer, we continue the comparison on three large-scale datasets. For the baselines, we only compare with three scalable GNNs, as existing graph Transformers not work on such large-scale datasets due to their high computational cost. The results are summarized in Table 2. NAGphormer consistently outperforms the scalable GNNs on all datasets, indicating that NAGphormer can better preserve the local information of nodes and is capable of handling the node classification task in large graphs. The cost of training the model is reported in Appendix G, which demonstrates the efficiency of NAGphormer for handling large graphs.
4.4 ABLATION STUDY
To analyze the effectiveness of structural encoding and attention based readout function, we perform series of ablation studies all datasets.
Structural encoding. We compare our proposed NAGphormer to its variant without the structural encoding module to measure the gain of structural encoding. The results are summarized in Table 3. We can observe that the gains of adding structural encoding vary in different datasets, since different graphs exhibit different topology structure. Therefore, the gain of structural encoding is sensitive to the structure of graphs. These results also indicate that introducing the structural encoding can improve the model performance for the node classification task.
Attentionbbasd readout function. We conduct a comparative experiment between the proposed attention-based readout function ATTT, (Equation 11) with previous readout functions, i.e., SIN. and SUM.. The function of SIN. utilizes the corresponding representation of the node itself learned by the Transformer layer as the final output to predict labels. And SUM. can be regarded as aggregating all information of different hops equally. From Figure 2, we observe that ATT. outperforms other readout functions on small-scale datasets, indicating that aggregating information from different neighborhoods adaptively is beneficial learn more expressive node representations, further im- proving the model performance on node classification. Due to the page limitation, the results on lcrge-scale datasets which exhibit similar observations are provided in Appendix F.
4.5 PARAMETER STUDY
To further evaluate the performance of NAGphormer, we study the influence of two key parameters: the number of propagation steps K and the number of Transformer layers T.. Specifically, we perform experiments AMiner-CSS CS, Reddit and Amazon2M by setting different values of K and L.
On parameter K. We fix = and vary the number of propagation steps K in {4, 6.. 20} Figure 3(a) reports the model performance. We can observe that the values of K are different for each dataset to achieve the best performance since different networks exhibit different neighborhood structures. Besides,
also observe that the model performance does not decline significantly even if is relatively large to 20. For instance, the performance on Reddit dataset changes slightly (< 0.1%) with the increment of K, which indicates that learning the node representations from the
8

---

Published as a conference paper at ICLR 2023
7016
05
00:00
94%
V014
$1.00
2014
SU.
Patral
Coohd
C5
Cuepuee
Pouto
Plysa
Figure 2: The performance of NAGphormer via different readout functions.
$2.59
00
12
16
(a) On the number propagation steps K
AmsasrCS
Anmeendh
(b) On the number of Transformer layers L
Figure 3: Performance of NAGphormer on different parameters.
information of multi-hop neighborhoods via the self-attention mechanism and attention- readout function can alleviate the impact of over-smoothing or over-squashing problems. addition, the model performance changes differently on three datasets with the increment of K. The reason may be that these datasets are different types networks and have diverse properties. This observation also indicates that neighborhood information on different types of networks has different effects on the model performance. In practice, we set K = for AMiner-CS, and set K = for others since the large propagation step will bring the high time cost of Hop2Token
Amanzon2M.
On parameter L. We fix the best value of K and vary L from to 5 on each dataset. The results are shown in Figure 3(b). Generally speaking, smaller L can achieve high accuracy while larger L degrades the performance of NAGphormer. Such result can attribute to the fact that a larger is more likely to cause over-fitting. set for AMiner-CS, and set for other datasets.
CONCLUSION
We propose NAGphormer, novel and powerful graph Transformer for the node classification task. By utilizing novel module Hop2Token extract the features of different-hop neighborhoods and transform them into tokens. NAGphormer treats each node as a sequence composed of the corresponding neighborhood tokens. In this way, graph structural information of each node could be carefully preserved. Meanwhile, such a tokenized design enables NAGphormer to be trained in mini-batch manner, enabling NAGphormer handle large-scale graphs. In addition, NAGphormer develops attention-based readout function for learning the node representation from multi-hop neighborhoods adaptively, further boosting the model performance. We also provide theoretical analysis indicating that NAGphormer can learn more expressive node representations than the decoupled GCN. Experiments on various datasets from small to large demonstrate the superiority of NAGphormer over representative graph Transformers and Graph Neural Networks. Our tokenized design makes graph Transformers possible to handle large graphs. We wish our work inspire more works in this direction, and in future work, will generalize NAGphormer other graph mining tasks, such as graph classification.
ACKNOWLEDGMENTS
This work is supported by National Natural Science Foundation (U22B2017,620766)

---

Published as a conference paper at ICLR 2023
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In Proceedings of the International Conference on Learning Representations, 2021.
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki. Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with up- proximate pagerank. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference Artificial Intelligence, 2020a.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pp. 3469-3489, 2022.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the International Conference on Learning Representations, 2018.
Ming Chen, Zhewei Wei, Bolin Ding. Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. In Proceedings of the Advances in Neural Information Processing Systems, 2020b.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the International Conference on Machine Learning, 2020c.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the ACM SIGKDD International Conference
Knowledge Discovery & Data Mining, 2019.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In Proceedings of the International Conference on Learning Representations, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the Advances in Neural Information Processing Systems, pp. 3837-3845, 2016.
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. NAACL-HLT, 2019.
Hande Dong, Jiawei Chen, Fuli Feng, Xiangnan He, Shuxian Bi, Zhaolin Ding, and Peng Cui. On the equivalence decoupled graph convolution network and label propagation. In Proceedings of the Web Conference, pp. 3651 3651-3662, 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In Proceedings of the International Conference on Learning Representations, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. CoRR, abs/2012.09699 2020.
Wenqi Fan, Yao Ma, Qing Li, Yuan Hc, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In Proceedings of the Web Conference, 2019.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han. Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. In Proceedings of the Advances in Neural Information Processing Systems, 2020.
10

---

Published as a conference paper at ICLR 2023
Wenzheng Feng. Yuxiao Dong, Tinglin Huang, Ziqi Yin, Xu Cheng, Evgeny Kharlamov, and Jie Tang. Grand+: Scalable graph random neural networks. arXiv preprint arXiv:2203.06388 2022.
Johannes Gasteiger, Stefan WeiB enberger, and Stephan Günnemann. Diffusion improves graph
learning. In Proceedings of the Advances in Neural Information Processing Systems, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the International Conference on Machine Learning, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the Advances in Neural Information Processing Systems, 2017.
Qiuting He, Jinsong Chen, Hao Xu, and Kun He. Structural robust label propagation homogeneous graphs. In IEEE International Conference on Data Mining, 2022.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over-smoothing for general graph convolutional networks, arXiv preprini ar arXiv:2008.0995 2020.
Md. Shamim Hussain, Mohammed J. Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
Paras Jain, Zhanghao Wu, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing rongeranee context for graph neural networks with global attention. In Proceedings of the Advances in Neural Information Processing Systems, 2021.
Di Jin, Ziyang Liu, Weihao Li, Dongxiao He, and Weixiong Zhang. Graph convolutional networks meet markov random fields: Semi-supervised community detection in attribute networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the ACM International Conference on Web Search and Data Mining, 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks In Proceedings of the International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks personalized pagerank. In Proceedings of the International Conference on Learning Representations, 2019.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Proceedings of the Advances Neural Information Processing Systems, 2021.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. 16692, 2019.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. CoRR, abs/2103. 14030, 2021.
llya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proceedings of the International Conference on Learning Representations, 2019.
Weigang Lu, Yibing Zhan, Ziyu Guan, Liu Liu, Baosheng Yu, Wei Zhao, Yaming Yang, and Dacheng Tao. Skipnode: On alleviating over- smoothnn for deep graph convolutional networks. arXiv preprint arXiv:2112. 2021.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang. Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.08455 2022.

---

Published as a conference paper at ICLR 2023
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven driven active surveying for collective classification. In Proceedings of the Interattonnal Workshop on Mining and Learning with Graphs, 2012.
Ladislav Rampásek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. In Proceedings of the Advances in Neural Information Processing Systems, 2022.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. In Proceedings of the Advances in Neural Information Processing Systems, 2020.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojehevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS, 2018.
Qingyun Sun, Jianxin Li, Haonan Yuan, Xingeheng Fu, Hao Peng, Cheng Ji, Qian Li, and Philip S Yu. Position-aware structure learning for graph topology-imbalance by relieving under-reaching and over-squashing. In Proceedings of the ACM International Conference Information & Knowledge Management, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the Advances in Neural Information Processing Systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the International Conference on Learning Representations, 2018
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In Proceedings of the International Conference on Machine Learning, 2019.
Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Proceedings of the Advances in Neural Information Processing Systems, 2022.
Ruibin Xiong, Yunchang Yang. Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In Proceedings of the International Conference on Machine Learning, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful graph neural networks. In Proceedings of the International Conference on Learning Representations, 2019.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over-smoothing in deep gens. arXiv preprint arXiv:2003. 13663 2020.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation. In Proceedings of the Advances in Neural Information Processing Systems, 2021.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovee. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna.
Graphsaint: Graph sampling based inductive learning method. In Proceedings of the International Conference on Learning Representations, 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Proceedings of the Advances in Neural Information Processing Systems, 2018.
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 21Xiv:2110.1394. 2021.
12

---

Published as a conference paper at ICLR 2023
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependen importance sampling for training deep and large graph convolutional networks. Proceedings of the Advances in Neural Information Processing Systems, 2019.
13

---

Published as a conference paper at ICLR 2023
A RELATED WORK
A.1 GRAPH NEURAL NETWORK
Graph Neural Network (GNN) has become a powerful technique for modeling the graph-structured data. Based on the message passing mechanism, GNN can learn the node representations from topology features and attribute features simultancously. Typical GNNs, such as GCN (Kipf & Welling, 2017) and GAT (Veličković et al., 2018). leverage the features of immediate neighbors via different aggregation strategies to learn the node representations, exhibiting competitive performance on various graph mining tasks. However, typical GNNs obey the coupled design that binds the aggregation module and the feature transformation module in each GNN layer, leading to the over- smoothing (Chen et al., 2020a) and over-squashing issues (Alon & Yahav, 2021) on high-layer GNNs. Such a problem limits the model's is ability to capture deep graph structural information. A reasonable solution to decouple the aggregation and feature transformation modules in GNN layer. treating them as independent modules (Klicpera et al.. 2019; Wu et al., 2019; Chien et al., 2021). termed decoupled Graph Convolutional Network (decoupled GCN) (Dong et al., 2021). Decoupled GCN utilizes various propagation methods, such as personalized PageRank Klicpera et al. (2019) and random walk Wu et al. (2019), to aggregate features of multi-hop neighborhoods and further generate the node representations. Since the nonlinear activation functions between GNN layers are removed, decoupled GCN exhibits high computational efficiency and has become an advanced type of GNN in recent years. Besides the decoupled strategy, recent works (Yang et al., 2020; Lu et al., 2021: Huang et al., 2020; Sun et al., 2022) make efforts to address the over-smoothing and over weer-squahhing issues by developing novel training tricks (Yang al., 2020; Huang al., 2020) or new graph neural network architectures (Lu et al., 2021; Sun et al., 2022). By introducing the carefully designed techniques, the impact of over-smoothing and over-squashing problems in GNNs could be well alleviated.
Scalable GNN. Most GNNs (Chen et al., 2020c; Jin et al., 2021; Kipf & Welling, 2017; Veličković al.. 2018) require the entire adjacency matrix as the input during training. In this way, when applying to large-scale graphs. the cost of training is too high to afford. There are two categories of strategies for generalizing GNN large-scale graphs:
(I) The node sampling strategy (Hamilton et al., 2017: Chiang et al., 2019; Zou et al., 2019; Zeng et al., 2020) that sample partial nodes from the whole graph via different methods, such as random sampling from neighbors (Hamilton et al., 2017) and sampling from GNN layers (Zou et al., 2019), to reduce the size of nodes for model training.
(II) The approximation propagation (Chen et al., 2020b; Feng et al., 2022: Bojchevski et al., 2020) that accelerates the propagation operation via several approximation methods, such as approximate PageRank (Bojchevski et al., 2020) and sub-matrix approximation (Feng et al., 2022).
However, by designing various compling-based or approximation- methods to reduce the training cost, these models will inevitably lead to information loss and somehow restrict their performance on large-scale networks.
A.2 GRAPH TRANSFORMER
In existing graph Transformers, there are mainly three strategies to incorporate graph structural information into the Transformer architecture so as to learn the node representations:
(I) Extracting the positional embedding from graph structure. Dwivedi et al. (Dwivedi & Bresson, 2020) utilize Laplacian eigenvectors to represent positional encodings of the original Transformer and fuse them with the raw attributes of nodes as the input. Derived from (Dwivedi & Bresson, 2020), Devin et al. (Kreuzer et al., 2021) leverage the full spectrum of Laplacian matrix to learn the positional encodings.
(II) Combining GNN and Transformer. In addition to representing structural information by the eigenvectors, Wu et al. (Jain et al., 2021) regard GNNs as an auxiliary module to extract fixed local structural information of nodes and further feed them into the Transformer to learn long-range pairwise relationships. Chen et al. (Chen et al., 2022) utilize GNN model the structure extractor to learn different types of structural information, such as subrree and i subbbgga,,, to capture the structure similarity of node pairs via the self-attention mechanism. Rampákek et al. (Rampásek et al.,
14

---

Published as a conference paper at ICLR 2023
2022) develop a hybrid layer that contains GNN layer and self-attention layer to capture both local and global information.
(III) Integrating the graph structural bias into the self-attention matrix. There are several efforts to transform various graph structure features into attention biases and integrate them into the self- attention matrix to enable the Transformer to capture graph structural information. Ying et al. (Ying et al., 2021) propose a spatial encoding method that models the structural similarity of node pairs based on the length of their shortest path. Zhao et al. (Zhao et al., 2021) propose proximity-enhanced attention matrix by considering the relationship of node pairs in different neighborhoods. Besides, by modeling edge features in chemical and molecular graphs, Dwivedi et al. (Dwivedi Bresson, 2020) extend graph Transformers to edge feature representation by injecting them into the self self-attention module of Transformers. Hussain et al. (Hussain et al., 2022) utilize the edge features to strengthen the expressiveness of the attention matrix. Wu et al. (Wu et al., 2022) introduce the topology structural information as the relational bias to strengthen the original attention matrix.
Nevertheless, except GraphGPS (Rampásek et al., 2022) and Nodeformer (Wu et al., 2022) whose complexities are linear to the number of nodes and edges, the aforementioned methods adopt the fully-connected attention mechanism upon all the node pairs, in which the spatial complexity is quadratic with the number of nodes. Such high complexity makes these methods hard to directly handle graph mining tasks large-scale networks with millions of nodes and edges. A recent work (Zhao et al., 2021) samples several ego-graphs of each node and then utilizes Transformer to learn the node representations on these ego-graphs model training. However, the sampling process is still time-consuming in large graphs. Moreover, the sampled ego-graphs only contain limited neighborhood information due the fixed and small sampled graph size for all nodes, which is insufficient to learn the informative node representations.
to reduce the computational cost of
B COMPLEXITY ANALYSIS OF NAGPHORMER
This section provides the complexity analysis of NAGphormer on time and space.
Time complexity. The time complexity of NAGphormer mainly depends on the self-attention module of the Transformer. So the computational complexity of NAGphormer is O(n K + 1)2d), where n denotes the number of nodes, K denotes the number of hops and the dimension of parameter matrix (i.e., feature vector).
Space complexity. The space complexity is based on the number of model parameters and the outputs of each layer. The first part is mainly on the Transformer layer Ld. where L is the number of Transformer layers. The second part is on the attention matrix and the hidden node representations, O(b(K + 1)² + b(K + 1)d), where denotes the batch size. Thus, the total space complexity is OO((K + 1)2 + b(K K + 1)d + d.).).
C PROOF OF FACT 1
Here we provide the detailed proof for Fact 1.
Fact 1. From the perspective of the output node representations of Hop2Token, we can regard the decoupled GCN as applying a self-attention mechanism with fixed attention matrix S e [[(+1)x((+)) where SK. Bx (k E (O..., K}) and other elements are all zeroes.
Proof. First, both Hop2Token and decouple GCN utilize the same propagation process to obtain the information of different-hop neighborhoods. So the neighborhood information of node i at propagation step l for brevity.
the same symbol H(()) (k) RR. lxd represent
For an arbitrary node each element Zi. {1, .... d} of the output representation Z; Bixd learned by the decoupled GCN according to Equation 2 is calculated as:
K Σ
Zi.
3 H
(13)
m
k=0
15

---

Published as a conference paper at ICLR 2023
Table 4: Statistics datasets.
Dataset
# Nodes
Edges
# Features
# Classes
Pubmed
19,717
44,324
500
CoraFull
19,793
126,842
8,710
70
Computer
13,752
491,722
767
10
Photo
7,650
238.163
745
8
CS
18,333
163,788
6,805
15
Physics
34,493
495,924
8,415
5
AMiner-CS
593,486
6,217,004
100
18
Reddit
232,965
11,606,919
602
41
Amazon2M
2,449,029
61,859,140
100
47
On the other hand, the output X; E ((++))dd of Hop2Token in the matrix form for node is described as:
(0)
1,0
(1)
X;
(14)
H
K
H (K)
Suppose we have the following attention matrix S e R (K+
0
0
0
0
S
(15)
Bo
B1
3K.
Following Equation 4, the output matrix T IR ())+1))x learned by the self-attention mechanism can be described as:
0
0
SX;
(16)
LYo
M
Ya
where Ym = =k H4
(2) i. (m E {l,...,d))
Further, obtain each clement Thfina (m {1, d)) of the final representation T final Rlxd of node by using summation readout function:
K
T
Final
Σ
TTm = (0 (0++0 +0++0 + + mm
8
Zi.m-
(17)
k=
km
Finally, we can obtain Fact 1.
D EXPERIMENTAL DETAILS
D.1 DATASET DESCRIPTION
Here we provide detailed descriptions for each dataset. Pubmed (Namata et al., 2012), Cora- Full (Shchur et al., 2018) and AMiner-CS (Feng et al., 2020) are citation networks in which nodes represent papers and edges represent citations. Computer (Shchur et al., 2018), Photo (Shchur et al., 2018), Amazon2M (Chiang et al., 2019) are co-purchase networks, where nodes indicate goods and edges indicate that the two connected goods are frequently bought together. CS (Shchur et al., 2018) and Physics (Shchur al., 2018) are co-authorship networks, where nodes denote authors and edges
16

---

Published as a conference paper at ICLR 2023
Table 5: Further comparison of NAGphormer and Gophormer. The best results appear in bold.
Cora
Citescer
Pumbed Blogcatalog
DBLP Flickr
Gophormer
87.85
80.23
89.40
96.03
85.20
91.51
NAGphormer 88.15
80.12
89.70
96.73
85,95
91.80
78.00
SIN
SUM
77.00
Accuscy
$4.00
76.00
93,00
$2,00
75.00
50.00
92.50
74.00
AMiner-CS CS
Reddk
Amuzun2M
Figure 4: The performance of different readout functions on large-scale datasets.
represent that authors have co-authored least one paper. Reddit (Hamilton al., 2017) is social network where nodes represent posts and edges denote that the same user has commented on the two connected posts. The statistics on datasets are reported in Table 4.
D.2 IMPLEMENTATION DETAILS
Referring to the recommended settings in the official implementations, we perform hyperparameter tuning for each baseline. For the model configuration of NAGphormer, we try the number of Transformer layers in {1, 2, .... 5). the hidden dimension in {128, 256, 512), and the propagation steps (2, ..., 20). Parameters are optimized with the AdamW (Loshchilov & Hutter, 2019) optimizer, using learning rate of in {le 3, 5e 3, Le - 4} and weight decay of {lc 4, 5e 4, 1e 5).
We also search the dropout rate in {0.1, 0.3, 0.5}. The batch size is set to 2000. The training process early stopped within 50 epochs. All experiments are conducted Linux server with 1 19-9900k CPU, RTX 2080TI GPU and 64G RAM.
E FURTHER COMPARISON WITH GOPHORMER
Gophormer (Zhao et al., 2021) is recent work on arXiv that generalizes the Transformer graphs for the node classification task. Since the code or model of Gophormer not available, for the comparison of NAGphormer and Gophormer, we run NAGphormer on the datasets used in the original paper (Zhao et al., 2021) with the same ratio of random splits. Our results in terms of accuracy (%) reported in Table 5. For Gophormer, observe that NAGphormer outperforms Gophormer on all datasets except Citeseer even on their data using their reported results, demonstrating that NAGphormer is more potent than Gophormer on the node classification task.
their reported results (Zhao et al., 2021). We can
F ABLATION STUDY OF READOUT FUNCTION ON LARGE-SCALE DATASETS
Figure 4 exhibits the performance of NAGphormer via different readout functions large-scale datasets. The results show that our proposed attention readout function consistently outper- forms others (SIN. and SUM.) on three large-scale datasets, demonstrating that learning the node representations from multi- hop neighborhoods adaptively can improve the model performance for the node classification task.
17

---

Published as a conference paper at ICLR 2023
Table 6: The training large-scale graphs in terms of GPU memory (MB) and running time (s).
Aminer-CS
Reddit
Amazon2M
Memory (MB)
Time (8)
Memory (MB)
Time (s)
Memory (MB)
Time (8)
GraphSAINT
1,641
23.67
2,565
43.15
5,317
334.08
PPRGo 1,075
14.21
1,093
35.73
1,097
152.62
GRAND+ 1,091
21.41
1,213
197.97
1.123
207.85
NAGphormer
1,827
19.87
1,925
20.72
2,035
58.66
G EFFICIENCY EXPERIMENTS ON LARGE-SCALE GRAPHS
In this section, we validate the efficiency of NAGphormer on large-scale graphs. Specifically, we compare the training cost terms of running time (s) and GPU memory (MB) of NAGphormer and three scalable GNNs, PPRGo, GraphSAINT and GRAND+. For scalable GNNs, We adopt the official implements on Github. However, all methods contain diverse pre-processing steps built on different programming language frameworks, such approximate matrix-caleulation based C++ framework in GRAND+. ensure the fair comparison, we report the running time cost including the training stage and inference stage since these stages of all models are based on Pytorch framework. The results are summarized in Table 6.
From the experimental results, with large graphs. For instance, on Amazon2M which contains two million nodes and 60 million edges, NAGphormer achieves almost 3x acceleration compared with the second fastest model PPRGo. The reason is that the time complexity of NAGphormer is mainly depended on the number of nodes and has nothing with the number of edges, while the time consumption of other methods is related to the number of edges and nodes since these methods involve the propagation operation during the training and inference stages. As for the GPU memory cost, since NAGphormer utilizes the mini-batch training, the GPU memory cost is determined by the batch size. Hence, the GPU memory cost of NAGphormer affordable by choosing proper batch size even on large-scale graphs.
observe that NAGphormer shows high efficiency when dealing
18


Reviews:
[{"review_id": "nCoKqFh0n71", "reviewer": "Reviewer_b2CU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a new neighborhood aggregation method based on the number of hops. With this method, a graph transformer is developed with node-wise input sequences. Moreover, a self-attention readout function is applied to integrate the representations learned from the transformer module.", "summary_of_the_review": "The idea of node-wise sequence input is novel, and the proposed model is competitive compared with current SOTAs.", "strength_and_weaknesses": "Strengths:\n\n1. With node-wise sequences as inputs, mini-batch can be used, and training becomes more scalable.\n2. Extensive experiments are conducted to compare NAGphormer with many baseline models in small to large-scale tasks. Additionally, an ablation study on the effect of different readout functions and propagation steps is performed.\n3. The empirical performance of NAGphormer is outstanding.\n\n\nWeaknesses:\n\n1. The authors propose that with Hop2Token, NAGphormer is more expressive than decoupled GCN family. However, in the experimental section, no decoupled GCN models are compared. Therefore, it will be more persuasive if the authors can add some of the decoupled GCN as baselines.\n2. Given the good performance of NAGphormer, from the ablation study over the depth of the model, it seems that NAGphormer also suffers from oversmoothing or oversquashing problems since as the depth increases, the performance deteriorates. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fd7TEqSBLX", "reviewer": "Reviewer_wvBc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a new graph Transformer architecture that contains a sequence of tokens obtained by aggregating neighbors' features. It shows improved expressive power with information from multi-hop neighborhoods. So, the model treats a node as a sequence of tokens. The authors claim that the model has better scalability due to its mini-bash training. The authors theoretically analyze that the proposed method has more expressive power compared to decoupled GCN.", "summary_of_the_review": "The proposed method shows a significant performance gain. Also, the multi-hop representations for each node and merging transformed node features in the attention-based readout layer are interesting ideas. However, the authors did not provide experimental results to justify their architecture. Lastly, scalability is improved by well-known mini-batch training. Overall, this paper has limited novelty and a few missing analyses.", "strength_and_weaknesses": "Strengths:\n\n* The proposed method shows competitive performance on many benchmark datasets.\n* The multi-view/multi-scale representation of a node (a sequence of aggregated node features) is an interesting idea. The late fusion of the node features is new. However,  the attention-based readout can be viewed as deformable convolution with an adaptive receptive field since it varies neighborhood from 0-hop to K-hops. From this perspective, the authors may want to compare the proposed method with similar approaches in the literature. \n\nWeaknesses:\n\n* Unlike the authors' presentation, the model does not utilize order information at all. Indeed, the model can be viewed as an ensemble model with features from different layers of a GNN while sharing the transformer's parameters. \n* One of the main contributions is \"a sequence of tokens\" for a node. But no ablation study is provided. For instance, simple feature concatenation is one naïve approach. Compared to straightforward construction, the authors should show the performance gain of the sequence of token node representation.\n* Mini-batch training for large-scale graphs has already been studied in the literature. Unless the authors present a new technique, which significantly improves scalability, It is hard to consider the improved scalability as the contribution of this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "a-76SZtI1c", "reviewer": "Reviewer_gZ4g", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a Graph Transformer architecture. It aggregates the neighborhood features from different hops and treat them as a sequence of token vectors for Transformer.", "summary_of_the_review": "The idea is good. Although some necessary experiments are missing, I encourage the authors to supplement these experiments during the discussion phase, to well support their arguments.\n", "strength_and_weaknesses": "Strengths:\n\n- Different from existing graph transformer methods, this work treats different hops of neighborhood representations as tokens. This can make the proposed method scale to large graphs.\n\n- The paper is written and organized well, and it is easy to follow.\n\n- The provided source code facilitates good reproducibility of this work.\n\n- The proposed method seems to have a promising performance in experiments.\n\nWeaknesses:\n\n- The authors argue that existing message passing-based GNNs have limitations such as over-smoothing and over-squashing. However, recently, there emerges a number of works e.g. [1,2,3,4,5] that address these limitations.\n\n- The experiments are not extensive. Specifically, the running time cost and the memory cost of all the methods should be compared to better show the efficiency of the proposed method, since the efficiency of this work is highlighted throughout the text.\n\n- This paper repeats itself in some pieces of text.\n\nRefs:\n\n[1] Huang, W., Rong, Y., Xu, T., Sun, F., & Huang, J. (2020). Tackling over-smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.09864.\n\n[2] Lu, W., Zhan, Y., Guan, Z., Liu, L., Yu, B., Zhao, W., ... & Tao, D. (2021). SkipNode: On alleviating over-smoothing for deep graph convolutional networks. arXiv preprint arXiv:2112.11628.\n\n[3]\tYang, C., Wang, R., Yao, S., Liu, S., & Abdelzaher, T. (2020). Revisiting over-smoothing in deep GCNs. arXiv preprint arXiv:2003.13663.\n\n[4] Huang, W., Rong, Y., Xu, T., Sun, F., & Huang, J. (2020). Tackling over-smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.09864.\n\n[5] Sun, Q., Li, J., Yuan, H., Fu, X., Peng, H., Ji, C., ... & Yu, P. S. (2022). Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing. arXiv preprint arXiv:2208.08302.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XICIbG86_p", "reviewer": "Reviewer_zQFG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes Hop2Token to scale a graph transformer to larger graphs by using multi-hop aggregated features of each node as the input tokens to graph transformer, instead of using all nodes as the tokens. The overall transformer using Hop2Token is called NAGphormer, which also uses structural encoding and attention-based readout function. The method is tested on both small and large node classification datasets and demonstrates empirical gains.", "summary_of_the_review": "Overall, the proposed Hop2Token seems a conceptually interesting and promising way to enable mini-batch training over larger graphs. However, several important baselines are missing and the method in its current form could suffer from severe over-squashing problems. ", "strength_and_weaknesses": "Strength\n- The proposed Hop2Token method is novel, simple, and can be efficiently implemented.\n- NAGphormer demonstrates empirical gains over thorough experiments and ablations.\n- The paper is clearly written and easy to follow.\n\nWeaknesses\n- Several important previous works are not mentioned and compared against, most notably \"Recipe for a General, Powerful, Scalable Graph Transformer\", which proposes reducing computation costs using a linear transformer. Other recent graph transformers like K-Subgraph SAT and EGT should also be compared if the authors wish to support the claim \"consistently outperforms existing graph Transformers and mainstream GNNs\".\n- The expressivity result against decoupled GCN does not seem very strong, since decoupled GCN is very simple and limited itself (probably by WL1 test, also https://arxiv.org/pdf/2010.12408.pdf shows that it can be seen as two times label propagations.)\n- Hop2Token fundamentally tries to compress an exponentially more amount of nodes information to a single token as the hop k increases. This is known to suffer from over-squashing issue. Although this may not be shown in the experimented datasets (maybe due to high homophily), this is a concern conceptually. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster