Rethinking Tokenized Graph Transformers  for Node Classification
Authors: Jinsong Chen
Chenyang Li
Gaichao Li
John E. Hopcroft
Kun He
Venue: NeurIPS 2025 poster ()
Keywords: graph Transformer
token swapping
token sequence
node classification
Primary area: deep_learning
TL;DR: We propose a new graph transformer that introduces a novel token swapping operation to generate diverse token sequences to further enhance model performance.

Abstract: Node tokenized graph Transformers (GTs) have shown promising performance in node classification. The generation of token sequences is the key module in existing tokenized GTs which transforms the input graph into token sequences, facilitating the node representation learning via Transformer. In this paper, we observe that the generations of token sequences in existing GTs only focus on the first-order neighbors on the constructed similarity graphs, which leads to the limited usage of nodes to generate diverse token sequences, further restricting the potential of tokenized GTs for node classification. To this end, we propose a new method termed SwapGT. SwapGT first introduces a novel token swapping operation based on the characteristics of token sequences that fully leverages the semantic relevance of nodes to generate more informative token sequences. Then, SwapGT leverages a Transformer-based backbone to learn node representations from the generated token sequences. Moreover, SwapGT develops a center alignment loss to constrain the representation learning from multiple token sequences, further enhancing the model performance. Extensive empirical results on various datasets showcase the superiority of SwapGT for node classification.
Code is available at https://github.com/JHL-HUST/SwapGT.

Rethinking Tokenized Graph Transformers for Node Classification
Jinsong Chen 12; Chenyang 3 Gaichao Li John E. Hopcroft Kun He Hel.3t 1,3 School of Computer Science and Technology. Huazhong University of Science and Technology Faculty Artificial Intelligence in Education, Central China Normal University Hooproff Center on Computing Science, Huazhong University of Science and Technology 'Department of Computer Science, Coreell University guangmianchenaiicee Cccuu edu. cn, {chenyangli waapengggi.aiccchhoooo gaichaolee earooleeee@@uuutee sehhst.eduu cn, jehêcs. cornell edu, brookl et00hust edu,
Abstract
Node tokenized graph Transformers (GTs) have shown promising performance node classification. The generation of token sequences is the key module in existing tokenized GTss which transforms the input graph into token sequences, facilitating the node representation learning via Transformer. In this paper, we observe that the generations of token sequences in existing GTss only focus on the first-order neighbors on the constructed similarity graphs, which leads to the limited usage of nodes to generate diverse token sequences, further restricting the potential of tokenized GT's for node classification. To this end, we propose a new method termed SwapGT. SwapGT first introduces novel token swapping operation based on the characteristics of token sequences that fully leverages the semantic relevance of nodes to generate more informative token sequences. Then, SwapGT leverages a Transformer-bant generated token sequences. Moreover, SwapGT develops center alignment loss to constrain the representation learning from multiple token sequences, further enhancing the model performance. Extensive empirical results various datasets showcase the superiority of SwapGT for node classification. Code is available at http:///ittbb.com///HHHHHS//////
backbone to learn node representations from the
Introduction
Node classification [22], the task of predicting node labels in graph, is fundamental problem in graph data mining with numerous real-world applications. Graph Neural Networks (GNNs) [42, 23] have traditionally been the dominant approaches. However, the message passing mechanism inherent to GNNs suffers from some limitations, such as over-smoothing [5], which prevents them from effectively capturing deep graph structural information and hinders their performance in downstream tasks. In contrast, Graph Transformers (GTs), which adapt the Transformer framework for graph- based learning, have emerged as a promising alternative, demonstrating impressive performance in node classification. Existing GTs can be broadly classified into two categories based on their model architecture: hybrid GT's and tokenized GTs.
Hybrid GTs combine the strengths GNN and Transformer, using GNNs to capture local graph topology and Transformers model global semantic relationships. However, recent studies have highlighted a key issue with this approach: directly modeling semantic correlations among all node pairs using Transformers can lead to the over-globalization problem [39], which compromises model
"Equal contribution.
i Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Sempling space
Target rade
Sumpled rode
Abandoned node
OO00 Seq.
0 Seq. 2
O
Single seq.
Previous methods
method
Figure 1: The toy example of token generation on the constructed k--N graph. Previous methods only focus on 1-hop neighborhood to construct single token sequence. While our method can flexibly select tokens from multi-hop neighborhoods to generate diverse token sequences.
performance. Tokenized GTs, the other hand, generate independent token sequences for each node, which encapsulate both local topological and global semantic information. Transformer models are then utilized learn node representations from these token sequences. The advantage of tokenized GT's is that they limit the token sequences to a small, manageable number of tokens, naturally avoiding the over-globall see--llbbalization issue. In tokenized GT's, the token sequences typically include two types tokens: neighborhood tokens and node tokens. Neighborhood tokens aggregate multi-hop neighborhood information of a target node, while node tokens sampled based the similarity between nodes.
However, recent studies [17] have shown that neighborhood tokens often fail to preserve complex graph properties such as long-range dependencics and heterophily, limiting the richness of node representations. On the other hand, node tokens, generated through various sampling strategies, can better capture correlations between nodes both feature and topological spaces [44, 7J, making them more effective in preserving complex graph information. As result, this paper focuses node token- GT'..
A recent study [7] formalized the node token generation process as two key steps: similarity evaluation and top-k sampling. In first step, similarity scores between node pairs are calculated based on different similarity measures preserve the relations of nodes in different feature spaces. While the second step, the top & nodes with the highest similarity scores are selected as node tokens to construct the token sequence. In this paper, provide existing tokenized GTs. We identify that the token generation process can be viewed as neighbor selection operation the k-nearest neighbor (k-NN) graph. Specifically, k-NN graph is constructed based on node pair similarities, and the neighbor nodes within the first-order neighborhood of each node selected to form the token sequence.
perspective
token generation in
Figure illustrates this idea with a toy example. We can observe that only a small subset of nodes is selected via existing token generation strategies, which indicates that existing methods have limited exploitation
the k-NN graph and are unable to comprehensively utilize the correlations between node pairs to explore more informative nodes with potential association to construct token sequences. This situation inevitably restricts the ability of tokenized GTs to capture informative node representations. Furthermore, in scenarios with sparse training data, relying token sequences generated from limited set of nodes may lead to over-fitting, as Transformers, being complex models, may struggle to generalize effectively.
This leads to the following research question: How can we more comprehensively and effectively exploit node pair correlations to generate diverse token sequences, thus improving the performance of tokenized GT's for node classificution? To address this, we introduce a novel method called SwapGT. Specifically, SwapGT introduces new operation, token swapping, which leverages the semantic correlations of nodes the k-NN to swap tokens in different token sequences, generating more diverse token sequences. By incorporating multiple token sequences, SwapGT enables the model to

---

learn more comprehensive node representations. Additionally, SwapGT employs a Transformer-bast backbone and introduces tailored readout function learn node representations from the generated token sequences. To handle the case where node is assigned multiple token sequences, we propose a center alignment loss to guide the training process. The main contributions of this paper are summarized as follows:
We propose a novel token swapping operation that fully exploits semantic correlations of nodes generate diverse token sequences.
We develop Transformer- backbone with a center alignment loss to learn node representations from the generated diverse token sequences.
Extensive experiments on various datasets with different training data ratios showcase the effectiveness of SwapGT in node classification.
2 Relation Work
2.1 Graph Neural Networks
GNNs [41, 43, 19, 9, 8, 21] have shown remarkable performance in this task. Previous studies [33, 40, 36, 24] have primarily concentrated on the incorporation of diverse graph structural information into framework. Classic deep learning techniques, such as the attention mechanism [33, 4] and residual connections [40, 14], have been exploited to enhance the information aggregation on graphs. Moreover, aggregating information from high-order neighbors [24, 1, 46, 47] nodes with high similarity across different feature spaces [30] has been demonstrated to be efficacious in improving model performance. Follow-up up GNNs have focused on the utilization of complex graph features to extract distinctive node representations. A prevalent strategy entails the utilization of signed aggregation weights [3, 15, 25, 20, 13] to optimize the aggregation operation. In addition. Zhang el al. [42] have excellently integrated L.MSs with GNNs, employing causal inference to mitigate biases introduced by the L.MSs. Nevertheless, restricted by the inherent limitations of peessag--passing mechanism, the potential of GNNs for graph data mining has been inevitably weakened. Developing a new graph deep learning paradigm has attracted great attention in graph representation learning.
the message-passia
2.2 Graph Transformers
GTs [16, 28, 39, 48] have emerged as a novel architecture for graph representation learning and have exhibited substantial potential in node classification. A commonly adopted design paradigm for GTs is the combination Transformer modules with GNN-style modules to construct hybrid neural network layers, called hybrid GTs [37, 38. 2]. In this design, Transformer is employed to capture global information, while GNNs are utilized for local information extraction [32, 16, 10]. Despite effectiveness, directly utilizing Transformer model the interactions of all node pairs could occur the over-globalization issue [39], inevitably weakening the potential for graph representation learning.
An alternative yet effective design of GT's involves transforming the input graph into independent token sequences termed tokenized GTs [44, 17, 27, 7, 12], which are then fed into the Transformer layer for node representation learning. Neighborhood tokens [6. 11, 27, 17, 7] and node tokens [44, 7, 17] are two typical elements in existing tokenized GT'. The former, generally constructed by propagation approaches, such random walk [6. 11] and personalized PageRank [17]. The latter is generated by diverse sampling methods based different similarity mcasurements, such as PageRank score [17] and attribute similarity [44]. Since tokenized GTs only focus on the generated tokens, they naturally avoiding the over-g wver-globalization issue
As pointed out in previous study [17], node token oriented GT's are more efficient in capturing various graph information, such as long-range dependencies and heterophily, compared to neighborhood token oriented GTs. However, we identify that previous methods only leverage a small subset of nodes as tokens for node representation learning, which could limit the model ability of deeply exploring graph information. In this paper, we develop a new method SwapGT that introduces novel token swapping operation to produce more informative token sequences, further enhancing the model performance.
3

---

Attribute view
A A
A 000
Token swopping
Readout
Transformen
Topology view
Torget talke SoQATIE
layer
Aue
AOOO
secipping
The overall framework of SwapGT. First, generate the initial token sequences from both the attribute view and topology view. Then, we utilize the proposed token swapping operation to generate token sequences for each target node. These generated token sequences are then fed into a Transformer-basee backbone to learn node representations and generate predicted labels. Additionally, center alignment loss is adopted further constrain the representations extracted from different token sequences.
Figure 2:
Preliminaries
Suppose attributed graph is denoted = (V, EV, where V and E the of nodes and edges in the graph. X 1a is the attribute feature matrix, where n and d are the number of nodes and the dimension the attribute feature vector, respectively. We also have the adjacency matrix A = {0, 1 R If there is an edge between nodes v and Uy. Aij 1; otherwise, Ai 0.
Á denotes the normalized version calculated as Å ID/2)) + I) + 1)- where D and I are the diagonal degree matrix and the identity matrix, respectively. In the scenario of node classification, each node associated with one-hot vector to identify the unique label information, resulting in label matrix Y Raxe where e is the number of labels. Given a set of labeled nodes Vt, the goal of the task is to predict the labels the rest nodes V - VL.
Methodology
In this section, we detail our proposed SwapGT, involving two main stages: token sequences generation via token swapping and token representation learning with Transformer-basee backbone. The overall framework of SwapGT' is shown in Figure
4.1 Token Sampling
Token sampling, which aims to select relevant nodes from input graph to construct token sequence for each target node, is crucial operation in recent GTs [44, 17]. Generally speaking, the token sampling operation for the target node v; can be summarized as follows:
N = {wylu Ju E Top(SS,
(1)
where N₂ denotes the token set of node us. Top(-) denotes the top-k sampling operation and k is the number of sampled tokens. S, E 1 denotes the vector of similarity scores between & and other nodes. Obviously, different strategies for measuring node similarity will result in different sets of sampled tokens. According to empirical results in previous studies [44, 17], measuring the node similarity from different feature spaces sample different types of tokens effectively enhance the model performance. Hence, in this paper, we sample the tokens from both the attribute feature space and the topology feature space, resulting in two token sets N,A and NT. respectively.
Specifically, for N₁A, we utilize the raw attribute features to calculate the cosine similarity of each node pair to obtain the similarity scores. For NT, we adopt the neighborhood features to represent the topology features of nodes. The neighborhood feature matrix is calculated as X' = o( A, X. K) where K denotes the number of propagation steps and Φ(-) denotes personalized PageRank propagation [24]. The influence of K on the model performance is discussed in Appendix A. Then we leverage the neighborhood features to measure the similarity of nodes the topology feature space via the cosine similarity.

---

Algorithm The Token Swapping Algorithm
Input: Sampled token set of all nodes E R=**; Target node v; Probability p. Swapping times
Output: The new token set N2 E IR of U/ 1: Initialize No = N;;
2: for to to do
3: Initialize Nnew = 0:
4: for Vy N do
5: if Tradooo (0, 1) > then Nnew Nuew U {uz};
6:
7:
else
8:
nnw ((N,); Nnew Nuie U {y"em);
9:
end if
11: end for
N = Nnnww
13:
end for
14:
return N
4.2
Token Swapping
As discussed in Figure 1, existing node token generators [45, 44, 17] could be regarded as selecting the 1-hop neighborhood nodes in the constructed k--N graph, which is inefficient in fully leveraging the semantic relevance between nodes and restricts the diversity of the token sequences, further limiting the model performance. To effectively obtain diverse token sequences, SwapGT introduces novel operation based on the unique characteristic of token sequences, called token swapping. The key idea is to swap tokens in different sequences to construct new token sequences. Specifically, for each node token , in the token set of node ut, we generate new node token vhe = =(N,) based on the token set N2 of vy. where ((-) denotes the random sampling operation. Then, the new token set N/ of v is generated as follows:
N (C(N))),, e N.).
Equation 2 indicates that for each node token U/ we swap it with random node y nnew in its node token set N2 to construct the new token N2 for the target node u4 Appendix B provides toy example to illustrate the token swapping operation.
Here, provide deep insights for the token swapping operation. According to Figure nodes in the token set are the 1 1-hop neighbors of the target node in the k-NN graph. Therefore, the selected node nee is within the 2-hop neighborhoods of e;. Therefore, performing the swapping operation t times is equal to enlarge the sampling space from 1-hop neighborhood to (t + 1 neighborhood. Hence, the swapping operation effectively utilizes the semantic relevance between nodes generate diverse token sequences. The overall algorithm of token swapping is summarized in Algorithm 1. Moreover, we theoretically analyze the probability of sampling neighbors from different k-NN hops on the constructed k-NN graph:
Fact 1. If we guarantee that (t - 1)p 1, in the generated token sequences, the probability of sampling lower-order neighbors is greater than sampling higher-order neighbors on the constructed I--N graph, where t denotes the maximum swapping times, and p denotes the probability of swapping tokens per time in Algorithm
The detailed proof of Fact 1 is provided in Appendix C. Fact 1 indicates that SwapGT prefers to sample low-order neighbors on the constructed k-NN graph which are more likely to be relevant, reducing the potential noise and effectively generating relevant token sequences for each node.
After generating various token sets, we utilize them to construct the input token sequence for representation learning. Given a token set N₁, the input token sequence Z of node is as:
Z X; X N........
XN.
(3)
By performing Algorithm s times, we can finally obtain + s token sets for the target node v, combine all token sequences generated by Equation 3 based on different token sets to obtain the final
5

---

input token sequences Z, E ((++))(+++)xd Following the same process, the input token sequences generated by N/ and N? are denoted as Z and z respectively.
4.3
Transformer-based Backhone
The proposed Transformer-basee backbone aims to learn node representations and predict the node labels according to the imput token sequences. Take the input sequence Z for example, we first utilize the projection layer to obtain the model input:
z A.) = -(Z
where p(-) denotes the projection layer and Z A.(0) ((++s)x(b-)))) d) denotes the model input of node V/. Then, a Transformer layer-based encoder is applied to learn node representations from the model input:
z,4.00 = MSA (LN
( (2) + 2, 2,,0111)
(5)
2,1000 = FFN (LN
(z (2,. + Z (,1111)
(6)
where 1 1, L indicates the /-th Transformer layer. MSA,FFN and (.) denote the multi-head self-attention mechanism, feed-forward networks and the LayerNorm operation the standard Transformer layer.
Through the encoder, we obtain the representations of input token sequences Z A.(L)
g(L+s)x(L+))xdd Then, we take the representation of the first item each token sequence as the final representation of the input sequence. This is because the first item in each token sequence the target node itself, and the output representation has learned necessary information from other sampling tokens in the input sequence via the Transformer encoder.
Hence, the final output of the Transformer encoder is denoted as Z (l++s)xdz Then, we utilize the following readout function to obtain the node representation learned from multi token sequences:
z Zo
Z A.i
where || denotes the concatenation operation, ZAA."" E gixde denotes the representation of o; learned from token sequences generated from the attribute feature space. Similarly, we can obtain Z from the topology feature space. effectively utilize information of different feature spaces, we leverage the following strategy to fuse the learned representations:
z = = z. + +1 (1--a) a) Z
where a E [0, 1] is hyper-parameter to balance the contribution from attribute features and topology features on the final node representation. At the end, we adopt Multi-Layer Perception- predictor for label prediction and the cross-entropy loss for model training:
Lee
Σ Iy MLP((Z) NEV2 1=
Σ
(9)
4.4 Center Alignment Loss
To further enhance the model's generalization, we develop a center alignment loss to constrain the representations learned from different token sequences for each node. Specifically, given the representations of multi-token sequences Z' E <1++s)ddz, we first calculate the center representation Z: (1+s) Ez=oZ Then, the center alignment loss is calculated as follows:
CAL(Z' z3) = -
Cosine(Z),,2
(10)

---

Table 1: Comparison of all models in terms of mean accuracy + stdev (%) under dense splitting, The best results appear in bold. The second results appear underline.
Dataset
Photo 0.83
ACM
Computer 0.78
Citeseer 0.74
WikiCS
BlogCatalog 0.40
UA12010
Flickr
H
0.82
0,66
0.36
01.24
93.74gmm
V3.24
58 18.90
76.81 asot
76.672
22.61
69.87211
47.45 47.488214)
APPNP
94,98
93.00
21.31
77.52
81.962t
94.77
77.41
84. 14.666:2 21
GPRONN
94.57
93.42.1m
90.15.a3
82.43
94.36.
76
85.91
FAGCN
94.06gmm
93.37
83,17
76. 19
79,89
79.92_
72.17
g2.03
BM-GCN
95.10
93.68
a7.91
83,90
83.97
ACM-GCN
94.56ea21
93.04
85.19
77.62
83 43.95-c44
94.53=
76.87
83.83
ANS-GT
94188
89.58
82.53
91.93
74.16
85.54
NAGphoemer
95.47
93.32
90.79
77.68
83.61=:2s
94.42-ea3
76.36s:12
86.85-2.5
SGFormer
92.93em
93.79
81.66
77.86axm
39.65
94.33
57.98
61.08
Spacformer
95.22
93.63
85.47=14
77.96
83,74-ca2
94,21=021
73.06
86.55-243
VCR VCR-Graphommer
95.38
Lauos
90.47
77.21
80.82:2tm
94, 94.19
76.08
25.96
CorFerrer
95.29
93.82ams
90.21
77.
74
g3.28
93.98
76.85
86.84 g4
PolyFormer
95.45
94.27
90.87
48.03
83,79
95.08-603
77.92
87.01
Swaptl
95.92gas
94,98
91.73ga
28,49
84.52.4m
95.931ge4
79.06.44
87.56
where Cosine(-) denotes the cosine similarity function.
The rationale of Equation 10 is that the representations learned from different token sequences can be regarded as different views of the target node. Therefore, these representations should naturally be close to each other in the latent space. In practice, separately calculate the center alignment loss of token sequences from different feature spaces:
L = CAL(ZA A. z + "
(11)
The overall loss of SwapGT as follows:
Loe + x feeer
(12)
where À is coefficient controlling the balance between the two loss functions.
5 Experiments
5.1 Dataset
We adopt eight widely used datasets, involving homophily and heterophily graphs: Photo [6]. ACM [34], Computer [6), BlogCatalog [29], UA12010 [35], Flickr [29] and Wiki-CS [31]. The edge homophily ratio [25] H()) [o, 1] is adopted to evaluate the graph's homophily level. H(G)
1 means strong homophily, while (g) + 0 means strong heterophily. Statistics of datasets summarized in Appendix D.I. To comprehensively evaluate the model performance in node classification, we provide two strategies to split datasets, called dense splitting and sparse splitting. In randomly choose 50% of each label as the training set, 25% as the validation set, and the rest as the test set, which is a common setting is previous studies [37, 38]. While in sparse splitting [15], we adopt 995% splitting for training set, validation and test set.
dense splitting,
5.2 Baseline
We adopt 13 representative approaches as the baselines: SGC [36], APPNP [24], GPRGNN [15],
FAGCN [3], BM-GCN [18], ACM-GCN [26], ANS-GT [44], NAGphormer [6], SGFormer [38], Specformer [2], VCR-Graphormer [17], CoBFormer [39] and PolyFormer [27]. The first six are
mainstream GNNs and others are representative GTs. Implementation details are summarized in Appendix D.2.
5.3 Performance Comparison
To evaluate the model performance in node classification, each model ten times with random initializations. The results in terms mean accuracy and standard deviation are reported in Table and Table 2.
First, we can observe that SwapGT achieves the best performance on all datasets with different data splitting strategies, demonstrating the effectiveness of SwapGT in node classification. Then,
7

---

Table 2: Comparison of all models in terms of mean accuracy - stdev (%) under sparse splitting. The best results appear in bold. The second results appear in underline.
Dataset
Photo 0.83
ACM 0.82
Compater 0.78
Citeseer 0.74
WikiCS
BlogCatalog
UA12010 0.36
Flickr
M
0.66
0.40
0.24
SGC
91. 91.90
89.57
06.41
24.99
71.23
21.61
39.43
APPNP
92.24
87.64
76.10
77.42
81. 81.76
71.39 61.65
GPRONN
92.13
86.38
66.50,am
77.59.54
a4.57
58.75
71.89 cm.
FAGUN
92.02
88.47
23
64 24
25.2
76.38
54.67
63.68
BM-GCN
90.11 91.19.am
16.14
77.39
84.05
m7:51
60.82
ACM-GCN
91.71
89 12.6
86.64-025
64.85
77.68-237
77.17-134
56.05=2:1
64.58
ANS-GT
90.42.474
88.
84.95
62.94
75.72a54
78.26.45:
55.85
64.42
NAGphoemer
91.65
89.73-
85.31
63.66
76.93
79.19
58.36
67.48
SGFormer
90.13
88.05
80.07
62.4
74.69
78.15
50.19
51.0
Specformer
90.57
88, 10
85. sos5
62.64
75.24-23:
79.75=12>
57.42-123
56.94
VCR CCR-Graphormer
86.81 91.39
85. 06
57.6 sir
72.81
24.90=1
56.43=119
50.93
Cormer
91.21 aaoe
89. g8
85. 85.06
63.82g1 x
76
79.44
58.23
66 16.94g118
PolyFormer
91.522.04
89.8
g5775
64.77
75.12
81.02
58.89.437
67.85&1.0
Swaptl
92.9.3g
90.92..44
88. 4ag
69.9
88.11 g8.
63.96:2..
72. 22.16gi
SwapOT-0
SwapOT
Photo
ACM
BlogCatalog
UA12010
06.00
100 00
100.00
80:00
(%)
95.00
75.00
94.00
92.00
90,00
70:00
42.00
15.00-
65
M0,00
00000
00000
Donse
Sparse
Dlasse
Sparse
Desse
Sparse
Desse
Sparse
Figure 3: Performances of SwapGT with or without the center alignment loss.
can find that advanced GTs obtain more competitive performance than GNNs on over half datasets under dense splitting, But under sparse splitting, the situation reversed. An intuitive explanation is that Transformer has more learnable parameters than GNNs, which bring more powerful modeling capacity. However, it also requires more training data than GNNs in the training stage to ensure the performance. Therefore, when the training data is sufficient. GTs can achieve promising performance. And when the training data is sparse, GT's usually leg behind GNNs. Our proposed SwapGT addresses this issue by introducing the token swapping operation to generate diverse token sequences. This operation effectively augments the training data, ensuring the model training even in the sparse data scenario. In addition, the tailored center alignment loss also constrains the model parameter learning, further enhancing the model performance.
Moreover, the performance gain of SwapGT in the sparse setting is larger than in the dense setting. Specifically, SwapGT can achieve around 3.5% and 3.2% performance improvement on BlogCatalog and Citeseer, respectively. This is because the token swapping operation in SwapGT can leverage the semantic relevance of node tokens to generate more informative token sequences, which could be regarded as a data augmentation strategy. These augmented token sequences can improve the data utilization efficiency and significantly enhance the quality of node representation learning, especially in the data sparse splitting. Hence, SwapGT can bring more significant improvement in the sparse splitting.
5.4 Study on the center alignment loss
The center alignment loss, proposed constrain the representation learning from multiple token sequences, is a key design of SwapGT. Here, we validate the effectiveness of the center alignment loss in node classification. Specifically, we develop variant of SwapGT by removing the center alignment loss, called SwapGT-O, Then, we evaluate the performance of SwapGT-O on all datasets under dense splitting and sparse splitting. Due to the space limitation, we only report the results on four datasets in Figure 3, other results are reported in Appendix A.2. Based on the experimental results, we can have the following observations: 1) SwapGT beats SwapGT-O on all datasets, indicating that the developed center alignment loss can effectively enhance the performance of SwapGT. 2) Adopting the center alignment loss can bring more significant improvements sparse setting than those in dense setting. This situation implies that introducing the reasonable constraint loss function based on the property of node token sequences can effectively improve the model training when the training data is sparse.
8

---

Swapti-4
SwapGT-R
SwayKTT
Photo
ACM
BlogCatalog
UA120100
09.00
100
100100
40.00
96.00
96
15.00-
Accuras
94.00
02.00
10 (00
100001
65.00
90.00
Donse
Sparse
Detse
Sparse
Dense
Sparse
Donc
Sparse
Figure 4: Performances of SwapGT with different token sequence generation strategies.
Sparse
Dense
Photo
ACM
BlogCatalog
L'120100
96.00
96.00
100000
94.00
55.00
10100-
60.00
90.00
50.00
70
88.00
40.00
50.00
Figure 5: Analysis on the swapping times t.
5.5
Study on the token sequence generation
The generation of token sequences another key module of SwapGTT, which develops a novel token swapping operation can fully leverage the semantic relevance of nodes to generate informative token sequences. In this section, we evaluate the effectiveness of the proposed strategy by comparing it with two naive strategies. One is to enlarge the sampling size k. We propose variant called SwapGT-L by sampling 2k tokens to construct token sequences. The other to randomly sample tokens from the enlarged 2 token set to construct multiple token sequences, called SwapGT-R. Performance of these variants are shown in Figure 4 and results on other datasets are reported in Appendix A.3.
We can observe that SwapGT-R outperforms SwapGT-L on most cases, indicating that constructing multiple token sequences better for node representation learning of tokenized GTss than generating single long token sequence. Moreover, SwapGTT surpasses SwapGiT-R on all cases, showcasing the superiority of the proposed token swapping operation in generation of multiple token sequences. This observation also implies that constructing informative token sequences can effectively improve the performance of tokenized GTs.
5.6 Analysis on the swapping times t
As discussed in Section 4.2, t determines the range of candidate tokens from the constructed k-NN graph, further affecting the model performance. To validate the influence of f on model performance. we vary in {1, 2, 3, 4] and observe the changes of model performance. Results are shown in Figure and Appendix A.5. We can clearly observe that SwapGT can achieve satisfidd performance on all datasets when é is no less than 2. This situation indicates that learning from tokens with semantic associations beyond the immediate neighbors can effectively enhancing the model performance. This phenomenon also reveals that reasonably enlarging the sampling space seek more informative tokens promising way to improve the effect of node tokenized GTs.
5.7 Analysis on the augmentation times s
The augmentation times determines how many token sequences are adopted for node representation learning. Similar to we vary in {1, (1,2,.... 2..... 8} and report the performance of SwapGT. Results are shown in Figure 6 and Appendix A.6. Generally speaking, sparse splitting requires larger to achieve the best performance, compared to dense splitting. This is because SwapGT needs more token sequences for model training in the sparse data scenario. This situation indicates that a tailored data augmentation strategy can effectively improve the performance of tokenized GTs when training data is sparse. Moreover, the optimal varies on different graphs. This is because different graphs exhibit different topology features and attribute features, which affects the generation of token sequences, further influencing the model performance.

---

Sparse
Pboto
ACM
BlogCatalog
UA12010
98.00
100.00
100100
90.00
Accuncy (%g)
$4.00
50.00
50.00
70.00
92.00
50.00
Figure 6: Analysis on the augmentation times
Conclusion
In this paper, we introduced novel tokenized Graph Transformer SwapGT for node classification. In SwapGT, we developed novel token swapping operation that flexibly swaps tokens in different token sequences, thereby generating diverse token sequences. This enhances the model's I's ability to capture rich node representations. Furthermore, SwapGTT employs tailored Transformer- based backbone with center alignment loss to learn node representations from the generated multiple token sequences. The center alignment loss helps guide the learning process when nodes are associated with multiple token sequences, ensuring that the learned representations are consistent and informative. Experimental results demonstrate that SwapGT significantly improves node classification performance, outperforming several representative GT and GNN models.
Acknowledgments
This work is supported by National Natural Science Foundation (U22B2017).
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor. Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019. MixHop: Higher-Orde Graph Convolutional Architectures via Sparsified Neighborhood Mixing. In Proceedings of the International Conference on Machine Learning.
[2] Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. 2023. Specformer: Spectral Graph Neural Networks Meet Transformers. In Proceedings of the International Conference on Learning Representations.
[3] Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. 2021. Beyond Low-frequency Informa- tion in Graph Convolutional Networks. In Proceedings of the AAAI Conference on Artificial Intelligence.
[4] Shaked Brody, Uri Alon, and Eran Yahav. 2022. How Attentive are Graph Attention Networks?. In Proceedings of the International Conference Learning Representations.
[5] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. 2020. Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View. In Proceedings of the AAAI Conference on Artificial Intelligence.
[6] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. 2023. NAGphormer: Tokenized Graph Transformer for Node Classification in Large Graphs. In Proceedings of the International Conference on Learning Representations.
[7] Jinsong Chen, Siyu Jiang, and Kun He. 2024. NTFormer: Composite Node Tokenized Graph Transformer for Node Classification. IEEE Transactions on Big Data (2024).
[8] Jinsong Chen, Boyu Li, and Kun He. 2024. Neighborhood Convolutional Graph Neural Network. Knowledge-Based Systems (2024), 111861.
[9] Jinsong Chen, Boyu Li, Qiuting He, and Kun He. 2024. PAMT: A Novel Propagation-Based Approach via Adaptive Similarity Mask for Node Classification. IEEE Transactions on Compu- tational Social Systems (2024).
10

---

[10] Jinsong Chen, Gaichao Li, John E. Hopcroft, and Kun He. 2023. SignGT: Signed Attention- based Graph Transformer for Graph Representation Learning. CoRR abs/2310.11022 (2023).
[11]
Jinsong Chen, Chang Liu, Kaiyuan Gao, Gaichao Li, and Kun He. 2024. NAGphormer+: A Tokenized Graph Transformer With Neighborhood Augmentation for Node Classification in Large Graphs. IEEE Transactions on Big Data (2024).
[12] Jinsong Chen, Hanpeng Liu, John E. Hopcroft, and Kun He. 2024. Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers. In Proceedings of the 38th Annual Conference on Neural Information Processing Systems.
[13] Jinsong Chen, Meng Wang, and Kun He. 2025. Hybrid Long-Range Dependency-Awan Graph Convolutional Network for Node Classification. Knowledge and Information Systems (2025).
[14] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and Deep Graph Convolutional Networks. In Proceedings of the International Conference on Machine Learning.
[15] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In Proceedings of the International Conference Learning Representations.
[16] Chenhui Deng, Zichao Yue, and Zhiru Zhang. 2024. Polynormer: Polynomial-Expressin Graph Transformer in Linear Time, In Proceedings of the International Conference on Learning Representations.
[17] Dongqi Fu, Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. 2024. VCR- CCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections. In Proceedings of the International Conference Learning Representations.
[18] Dongxiao He, Chundong Liang, Huixin Liu, Mingxiang Wen, Pengfei Jiao, and Zhiyong Feng. 2022. Block Modeling-Guide Graph Convolutional Neural Networks. In Proceedings of the Sixtt AAAI Conference on Artificial Intelligence.
[19] Qiuting He, Jinsong Chen, Hao Xu, and Kun He. 2022. Structural Robust Label Propagation on Homogeneous Graphs, In Proceedings of the IEEE International Conference on Data Mining.
[20] Jincheng Huang, Lun Du Xu Chen, Qiang Fu, Shi Han, and Dongmei Zhang. 2023. Robust mid-pass filtering graph convolutional networks. In Proceedings of the ACM Web Conference 2023. 328-338.
[21] Jincheng Huang, Yujie Mo, Xiaoshuang Shi, Lei Feng, and Xiaofeng Zhu. 2025. Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks. In Forty-second International Conference on Machine Learning.
[22] Jincheng Huang, Jialie Shen, Xiaoshuang Shi, and Xiaofeng Zhu. 2024. On Which Nodes Does GCN Fail? Enhancing GCN From the Node Perspective. In Forty-first International Conference on Machine Learning.
[23] Thomas N Kipf and Max Welling. 2017. Semi-supervised Classification with Graph Convolu- tional Networks. In Proceedings of the International Conference Learning Representations.
[24] Johannes Klicpera, Aleksandar Bojchevski. and Stephan Günnemann. 2019. Predict then Propa- gate: Graph Neural Networks Meet Personalized PageRank. In Proceedings of the International Conference on Learning Representations.
[25] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. 2022. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. In Proceedings of the International Conference on Machine Learning.
[26] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. 2022. Revisiting Heterophily For Graph Neural Networks. In Proceedings of the Annual Conference on Neural Information Processing Systems.
11

---

[27] Jiahong Ma, Mingguo He, and Zhewei Wei. 2024. PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer. Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining.
[28] Xiaojun Ma, Qin Chen, Yi Wu, Guojie Song. Liang Wang, and Bo Zheng. 2023. Rethinking Structural Encodings: Adaptive Graph Transformer for Node Classification Task. In Proceedings of the ACM Web Conference.
[29] Zaiqiao Meng. Shangsong Liang, Hongyan Bao, and Xiangliang Zhang. 2019. Co-Embedding Attributed Networks. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining.
[30] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-GCN: Geometric Graph Convolutional Networks. In Proceedings of the International Conference on Learning Representations.
[31] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. 2023. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. In Proceedings of the Eleventh International Conference on Learning Representations.
[32] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. 2022. Recipe for General, Powerful, Scalable Graph Transformer. In Proceedings of the Anmual Conference on Neural Information Processing Systems.
[33] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. Graph Attention Networks. Proceedings of the International Conference on Learning Representations.
[34] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S. Yu. 2019. Heterogeneous Graph Attention Network. In Proceedings of the World Wide Web Conference.
[35] Xiao Wang. Meiqi Zhu, Deyu Bo, Peng Cui, Chuan Shi, and Jian Pei. 2020. AM-GCN: Adaptive Multi-channel Graph Convolutional Networks. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining.
[36] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying Graph Convolutional Networks. In Proceedings of the International Conference on Machine Learning.
[37] Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. 2022. NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification. In Proceedings of the Anmual Conference on Neural Information Processing Systems.
[38] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nic, Haitian Jiang, Yatao Bian, and Junehi Yan. 2023. Simplifying and empowering transformers for large- gaggegrrah representations. In Proceedings of the Annual Conference on Neural Information Processing Systems.
[39] Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. 2024. Less is More: the Over- Globalizing Problem in Graph Transformers. In Proceedings of the International Conference on Machine Learning.
[40] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Jegelka. 2018. Representation Learning on Graphs with Jumping Knowledge Networks. In Proceedings of the International conference on machine learning.
[41] Guixian Zhang, Guan Yuan, Debo Cheng, Lin Liu, Jiuyong Li, and Shichao Zhang. 2025. Disentangled contrastive learning for fair graph representations. Neural Networks 181 (2025), 106781.
[42] Guixian Zhang, Guan Yuan, Debo Cheng, Lin Liu, Jiuyong Li, and Shichao Zhang. 2025. Mitigating Propensity Bias of Large Language Models for Recommender Systems. ACM Transactions on Information Systems 43, (2025), 1-26.
12

---

[43] Guixian Zhang, Shichao Zhang. and Guan Yuan. 2024. Bayesian graph local extrema convo- lution with long-tail strategy for misinformation detection, ACM Transactions on Knowledge Discovery from Data 18, 4 (2024), 1-21.
[44] Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. 2022. Hierarchical Graph Transformer with Adaptive Node Sampling. Proceedings of the Annual Conference on Neural Information Processing Systems.
[45] Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. 2021. Gophormer: Ego-Graph Transformer for Node Classification. arXiv preprint arXiv:2110. 13094 (2021).
[46] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. In Proceedings of the Annual Conference on Neural Information Processing Systems.
[47] Jiaming Zhuo, Can Cui, Kun Fu, Bingxin Niu, Dongxiao He, Yuanfang Guo, Zhen Wang, Chuan Wang, Xiaochun Cao, and Liang Yang. 2023. Propagation is All You Need: A New Framework for Representation Learning and Classifier Training on Graphs. Proceedings of the ACM International Conference Multimedia. 481-489.
[48] Jiaming Zhuo, Yuwei Liu, Yintong Lu, Ziyi Ma, Kun Fu, Chuan Wang, Yuanfang Guo, Zhen Wang, Xiaochun Cao, and Liang Yang. 2025. DUALFormer: Dual Graph Transformer. In Proceedings of the International Conference on Learning Representations.
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] " "provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction accurately reflect that this paper focuses on the tokenized graph Transformer. This paper develops a novel token swapping operation to construct informative token sequences, enhancing the generalization of tokenized graph Transformers.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
We provide deep discussion about the limitation of SwapGT in Appendix E. Guidelines:
Justification:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
14

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex: system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof'
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Appendix C, we theoretically analyze the elements token sequences generated by the token swapping operation.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer:[Yes
Justification: We provide detailed information about the experimental setup in the main text and Appendix D. including datasets and implementation details.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
15

---

If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Please refer to http://ghhhbbcom//HHHHUUUS///
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.o cc/
cablic/guidens htt////dd///ooeeubbeeee
(oodeSumiissiononi onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https: // /nipp..cc wwwpcc/ppppc///eec..cc.ee......t httpllicgggieeeeeeeeeeeee http://ooeemissiioooiiio
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
16

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We provide detailed information about the experimental setup in the main text and Appendix D, including datasets and implementation details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: We report the average accuracy results as well as the corresponding standard deviation values following the previous studies.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the detailed information of compute resources in Appendix D.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
17

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttpp:::///uuuss..... httpppie/ttiisttuiiiieeeeeeepeee
Answer: [Yes]
Justification: This paper follows the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper focuses on enhancing the performance tokenized graph Trans- formers in node classification, which is foundational research and has societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
18

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We use the public datasets in experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method developed in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the core method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : //tperipss...//eee Cwtrrrissscc///oooooe for what should or should be described.
/LLM)
20

---

A Additional Experimental Results
In this section, provide the additional experimental results of ablation studies and parameter
studies.
A.1 Study of the propagation step
SwapGT leverages the graph diffusion strategy to calculate the topological features of nodes, which are further utilized to generate token sequences the topology feature space. Here, we investigate the influence of the propagation step K the model performance. Specifically, vary K in {1, 2, 3, 4} and observe the performance of SwapGT. The results under dense splitting and sparse splitting are shown in Figure 7 and Figure 8.
Photo
ACM
Computer
Citeseer
98.00
96.00
94.00
30,00
92.00
79.00
90.00
78,00
94.00
94.00
88,00
77,00
92.00
93.00
86,00
76,00
WikiCS
BlogCatalog
UA12010
Flickr
86.00
98.00
50,00
90.00
Acquncy (%)
96.00
78.00
$8.00
84.00
94.00
76.00
$6.00
82.00
92.00
74.00
$4.00
Figure 7:
Performances of SwapGT with different propagation steps under dense splitting.
Photo
ACM
Computer
Citesoer
04.00
94.00
90.00
72,00
(96)
92.00
88.00
92.00
70,00
90.00
36.00
90.00
$8.00
$1.00
88.00
96.00
82.00
66.00
WikiCS
Batalog
UA12010
Flickr
80.00
90.00
66.00
74,00
64.00
72.00
78.00
62.00
70,00
76.00
84.00
82.00
60,00
68.00
74.00
80.00
58.00
66,00
Figure Performances SwapGT with different propagation steps under sparse splitting.
Generally speaking, the influence of propagation steps is greater the sparse splitting due to the heightened sensitivity of sparse splitting input data during model training. Moreover, observe that the optimal propagation steps consistently fall within the range datasets under different splitting strategies. This is because that excessively large K values risk over-smoothing while insufficient values fail to capture meaningful structural patterns. practice, utilize the grid search determine the optimal K within constrained parameter space (K <=))).
on almost all
A.2 Study of the center alignment loss
The experimental results of SwapGT and SwapGT-O on the rest datasets are shown Figure We can observe that SwapGT outperforms SwapGT-O on most datasets. Moreover, the effect of applying the center alignment loss on SwapGT in sparse splitting is more significant than that in dense splitting. The above observations are in line with those reported in the main text. Therefore.
21

---

we can conclude that the center alignment loss can effectively enhance the performance of SwapGT node classification.
A.3
Study of the token sequence generation
The experimental results of SwapGT with different token sequence generation strategies the rest datasets are shown Figure 10. We can find that the additional experimental results exhibit similar observations shown in the main text. This situation demonstrates the effectiveness of the token sequence generation with the proposed token swapping operation in enhancing the performance of tokenized GTss Moreover, operation vary on different graphs based on the results shown in Figure 4 and Figure 10. This phenomenon may attribute that different graphs possess unique topology and attribute information, which further impact the selection of node tokens. While SwapGT applies the uniform strategy for selecting node tokens, which could lead to varying gains of token swapping. This situation also motivates us to consider different strategies of token selection on different graphs as the future work.
also observe that the gains of introducing the token swapping
SwupGT--O
SwapGT
Computer
Citeseer
WikiCS
Flickr
100.00
Accuaryy (%)
Accoarcy (%)
75.00
68.00
75.00
$4.00
65.00
Donse
Sparse
Dense
Sparse
Dense
Sparse
Dense
Sparse
Figure Performances of SwapGT with or without the center alignment loss.
SwapGT-L
SaapGT-R
SwapGT
Computer
Citeseer
WikiCS
Flickr
80,00
85.00
90.00
Accumey (3g)
Accumcy (%)
Accumcy (%g
Accuracy (%6)
90.00
75.00
80.00
80.00-
85,00
70.00
75.00
70.00
80.00
65.00
70.00
60.00
Dense
Sparse
Dense
Sparse
Dense
Sparse
Dense
Sparso
Figure 10: Performances of SwapGT with different token sequence generation strategies.
Photo
ACM
Computer
Citeseer
Accuracy (16)
95.00
96.00
92.00
94.00
91.00
92.00
92.00
76.00
10
30
30
10
15
70
10
31
30
10
20
30
WikiCS
BlogCatalog
UA12010
Flickr
$6.00
97.00
82.00
90.00
Arcuracy (%6
85.00
96.00
80.00
$4.00
8%. 88.00
95.00
78.00
83.00
86.00
94.00
76.00
Figure 11: Performances of SwapGT with different sampling sizes under dense splitting.
22

---

Pholo
ACM
Computer
Citeseer
94,00
92,00
90.00
76.00
Acenicy (%)
92.00
90.00
88.00
72,00
90,00
86.00
68.00
86.00 10
30
70
10
70
70
WikiCS
BlogCatalog
UA12010
Flickr
80,00
89.00
65.00
74.00
Aveurcy (56
78.00
88.00
64.00
72.00
65.00
76.00
87.00-
70.00
74,00
86.0 00
61.00
68.00
72,00
85.00
60.00
66.00
Figure 12:
Performances of SwapGT with different sampling sizes under sparse splitting.
A.4
Study of the token sampling size
To investigate the influence of token sampling size on model performance, we vary the sampling size (4, 6, 8, 10, 15, 20, 30) and report the corresponding results of SwapGTT on all datasets under different splitting strategies. Figure 11 and Figure 12 show the results. We can observe that the best choice of the sampling size falls within 10 on almost all datasets, which implies that enlarging the length of token sequences cannot enhance the model performance splitting or sparse splitting. This may because that a large sampling size is more easily to introduce irrelevant nodes as tokens, which further hurt the model performance.
most cases whether in dense
A.5 Analysis of the swapping times é
Here we report the rest results of SwapGT with varying t, which are shown in Figure 13. Similar to the phenomenons shown in Figure 5, SwapGT can achieve the best performance all datasets when > 2. Based on the results shown in Figure 13 and Figure 5, we can conclude that introducing tokens beyond first-order neighbors via the proposed token swapping operation effective improve the performance of SwapGT in node classification.
Sparse
Dense
Computer
Citeseer
WikiCS
Flickr
100.00
80.00
90,00
90.00
Accuracy(55)
Accuracy (%)
Accuncy (%))
95.00
Acouray
75.00
85.00
80.00
00.00
70.00
60.00
70.00
85.00
65.00
75.00
60.00
Figure 13: Performances of SwapGT with varying t.
A.6 Analysis of the augmentation times s
Similar to analysis of I, the rest results of SwapGT with varying are shown in Figure 14. We can also observe the similar situations shown in Figure 6 that SwapGTT requires a larger value of under sparse splitting compared to dense splitting. The situation demonstrates that introducing augmented token sequences can bring more significant performance gain in sparse splitting than that in dense splitting.
A.7 Analysis of readout functions
The readout function also an important module in SwapGT, According to Equation 7, we regard the combination of the raw token sequence and the augmented token sequences as the final node
23

---

Spanse
Dense
Computer
Citeseer
WIkiCS
04.00
80.00
90.00
100.00
Accurayy (%6
Accuracy (%)
90000
70.00
80,00
80.00
88.00
65.00
75.00
70.00
60.00
Figure 14: Performances of SwapGT with varying s.
Table 3: Comparison of SwapGT and its variant under dense splitting.
Dataset
Photo
ACM
Computer
Citeseer
WikiCS
BlogCatalog
UAT2010
Flickr
SwapGT-AT
95.58
94.61
91.35
77.92
83.95
95,47
78.32
87.11
SwapGT 95.92
94.98
91.73
78.49
84.52
95.93
79.06
87.56
representation. This strategy can ensure the independence of the information from the original token sequence and generated token sequences. Moreover, we utilize the mean function to obtain the information of generated token sequences, which is simple but efficient strategy and has been widely adopted in GNNs.
Here, we conduct experiments to validate the effectiveness of the proposed readout function, Specifi- cally, we develop a variant named SwapGT-AN which leverages the attention- based readout function from NAGphormer[6] for node representation learning. The results are reported in Table 3 and Table
We can observe that SwapGT beats this variant on all datasets. The reason may he that the neighbor- hood tokens in NAGiphormer have varying importance. In this situation, the attention-basee readout function can enhance the model performance. However, the augmented token sequences generated by the token swapping operation do not have this characteristic. Hence, the simple readout function may be more suitable for SwapGT.
B Illustration of Token Swapping
Here, we provide a toy example to understand the operation of token swapping. As shown in Figure 15, node is the target node. We first select node 3 and consider the tokens in its token sequences as candidates. Then we select node 6 from the candidates to swap node 3, and construct the new token sequence.
Token swapping
!
3
A
Select
Replace
!
Sample
Init. seq.
Swapping
Output
Figure 15: Illustration of the token swapping.
C
Proof of Fact
Here provide the detailed proof for Fact 1.
Fact 1. If we guarantee that (1. + 1)p 1, the generated token sequences, the probability of sampling lower-order neighbors is greater than sampling higher-order neighbors the constructed
24

---

Table 4: Comparison of SwapGT and its variant under sparse splitting.
Dataset
Photo
ACM
Computer
Citeseer
WikiCS
BlogCatalog
UAT2010
Flickr
SwapGT-AT
92.32
89.65
87,30
68.13
77.86 78.11
87.25
63.18
71.21
SwapGT
92.93
90.92
88.14
69.91
88.11
63,96
72.16
k-NN graph, where I. denotes the maximum swapping times, and denotes the probability of swapping tokens per time in Algorithm
First, as discussed in Section 4.2, performing the swapping operation t times enlarges the ((+1)-hop neighborhood on the constructed k-NN graph. Then, for an arbitrary node i, the probability of sampling its m-hop neighbors on the constructed k-NN graph (i.e., swapping for (m 1) times and maintaining for (t + 1) times) is described as follows:
Proof.
sampling space from l-hop neighborhood
P.T C(t, 1p" (1 m
(13)
Here, is the symbol of the combination number. In the augmented token sequences, neighbors of node from different k-NN hops all may be sampled. To reduce the noise caused by sampling too many high-hop neighbors on the constructed k-NN graph, the probability of sampling lower-order neighbors is expected to be greater, i.e,, p. p.
According to Equation 13,
P. pmm
C (t, m 1) 1) pmppp_1__-00 (1 (1-p) p)) C mt) -1- p)--m
1!
(m - 1)! m + 1)! -p-- - p) m-
>
'p" (1 - -m--m
ml (t m)!
1 1-p > P
( m +1 m
m > (t 1)p
where 1 S m, m + 1 1 1, i.e. 1 1 m S t. If we guarantee that (t + 1)p < 1, it obvious that (t + 1)p < 1 S m. Finally, we can obtain Fact 1.
Fact suggests that with suitable maximum swapping times t and probability of swapping tokens per time p. SwapGT is capable of well handling the potential noise and effectively enlarging the sampling space.
D Experimental Settings
D.I Dataset
Here we introduce datasets adopted for experiments. The detailed statistics of all datasets are reported in Table 5.
Academic graphs: This type of graph is formed by academic papers or authors and the citation relationships among them. Nodes in the graph represent academic papers authors, and edges represent the citation relationships between papers or co-author relationships between two authors. The features of nodes are composed of bag-of-words vectors, which are extracted and generated from the abstracts and introductions of the academic papers. The labels of nodes correspond to the research fields of the academic papers or authors. ACM, Citeseer, WikiCS and UA12010 belong to this type.
Co-purchase graphs: This type of graph is constructed based on users' shopping behaviors. Nodes in the graph represent products. The edges between nodes indicate that two products are often purchased together. The features of nodes are composed of log--ff-ordde vectors extracted from product reviews. The category of a node corresponds to the type of goods the product belongs to. Computer and Photo belong to this type.
25

---

Social graphs: This type of graph is formed by the activity records of users on social platforms. Nodes in the graph represent users on the social platform. The edges between nodes indicate the social relations between two users. Node features represent the text information extracted from the authors' homepage. The label of node refers the interest groups of users. BlogCata and Flickr belong to this type.
Table 5: Statistics of datasets, ranked by the homophily level.
Dataset
# nodes
# edges
# features labels
H. 1
Photo
7,650
238,163
745
0.83
ACM
3,025
1,3128
1,870
3
0.82
Computer
13,752
491,722
767
10
0.78
Citeseer
3,327
4,552
3,703
6
0.74
WikiCS
11,701
216,123
300
10
0.66
BlogCatalog
5,196
171,743
8,189
6
0.40
UA12010
3,067
28,311
4,973
19
0.36
Flickr
7,575
239,738
12,047
0.24
D.2 Implementation Details
For baselines, we refer their official implementations and conduct systematic tuning process each dataset. For SwapGT, we employ grid search strategy to identify the optimal parameter settings. Specifically, We try the learning rate in {0.001, 0. 0.005, 0.01]. dropout {0.3, 0.5, 0.7). dimension of hidden representations in {256. 512]. & in {4, 6, 8), in {O.l.... 0.9}. All experiments are implemented using Python 3.8, PyTorch 1.11, and CUDA 11.0 and executed on a Linux server with an Intel Xeon Silver 4210 processor, 256 GB of RAM, and 2080TI GPU.
D.3 Baselines
In this paper, we select mainstream GNNs and GT's as baselines. For GNNs, there categories of them, coupled GNNs and decoupled GNNs. FAGCN [3], BM-GCN [18], ACM-GCN [26] are recent coupled GNNs for node classification. SGC [36]. APPNP [24], GPRGNN [15] are representative decoupled GNNs, For GTs, we select methods from tokenized GTs and hybrid GTs. ANS-GT [44], NAGphormer [6], VCR-Graphen CCR-Graphormer [17] and PolyFormer [27] are powerful tokenized GTs. While SGFormer [38], Specformer [2] and CoBFormer [39] are representative hybrid GTs.
E
Limitation of SwapGT
potential limitation SwapGT could be that SwapGT applies uniform swapping probability p to all tokens in the sequence. A hierarchical probability swapping framework may be a better solution, where nodes within the top-k most relevant subset (e.g., the top k/3 nodes) are assigned higher swapping probabilities, while others receive lower probabilities. This refinement could mitigate noise interference.
26


Reviews:
[{"review_id": "TJmGK9wKX0", "reviewer": "Reviewer_yYpa", "summary": "This paper identifies a key limitation in existing tokenized Graph Transformers (GTs), where the token sequences for a target node are generated only from its immediate (1-hop) neighbors on a pre-constructed similarity graph. The authors argue this restricts the diversity of information available to the Transformer, limiting its performance, especially in sparse data settings. To address this, they propose SwapGT, a novel tokenized GT framework.\n\nThe core contribution is a token swapping operation, a data augmentation technique that creates multiple, diverse token sequences for each node by iteratively swapping tokens with those from their neighbors' token sets, effectively sampling from multi-hop neighborhoods on the similarity graph. Extensive experiments show that SwapGT consistently outperforms a wide range of GNN and GT baselines, particularly in sparse training scenarios.", "questions": "- The entire method depends on the initial k-NN graph. How sensitive is the model's performance to the choice of k in this initial step? Does a poor choice of k disproportionately harm SwapGT compared to a standard 1-hop GT?\n\n- The token swapping operation is presented as the best way to leverage multi-hop information. How does this strategy compare, both conceptually and empirically, to other established multi-hop sampling techniques?", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n-  The paper does an excellent job of identifying a concrete and sensible limitation in the current design of tokenized GTs—the restricted sampling space for token generation. The framing of this process as a 1-hop neighborhood selection on a k-NN graph is insightful and provides a strong, clear motivation for the proposed solution.\n\n- The proposed token swapping operation is an original and well-designed solution to the identified problem. It serves as an elegant, graph-specific data augmentation technique that expands the model's view to multi-hop semantic neighbors in a controlled fashion.\n\n- The quality of the proposed method is demonstrated through rigorous experiments on eight benchmark datasets, including both homophilous and heterophilous graphs. The inclusion of standard deviation in the result tables further strengthens the reliability of these claims.\n\n- The paper is well-written, clearly structured, and easy to follow. The overall framework is well-illustrated in Figure 2, and the token swapping algorithm is precisely detailed in Algorithm 1. The authors provide thorough ablation studies for each component of their method and include detailed experimental settings in the appendix, which aids in understanding and reproducibility\n\nWeaknesses\n- The method introduces several new hyperparameters, including the swapping times t, swapping probability p, number of augmented sequences s, and the fusion coefficient α. The parameter analysis in Figures 5 and 6 shows that model performance is sensitive to \nt and s, and their optimal values vary across datasets. This reliance on careful tuning might limit the method's practical, out-of-the-box applicability.\n\n- The paper includes a probabilistic analysis in Fact 1, showing that the swapping mechanism preferentially samples lower-hop neighbors on the k-NN graph. While this is a nice sanity check to show the process isn't completely random, it is a very light theoretical contribution. It does not provide any formal guarantees on the quality of the learned representations or why this specific sampling strategy leads to better generalization compared to others.\n\n- The study on token generation strategies in Section 5.5 compares SwapGT against two \"naive\" variants: using a single, longer sequence (SwapGT-L) and randomly sampling from a larger pool (SwapGT-R). While SwapGT outperforms them, these baselines were designed by the authors for the ablation. The study would be more compelling if it compared the token swapping strategy against other established multi-hop or graph augmentation techniques from the literature, adapted to the tokenized GT context.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for detailed comments. We provide the following responses:\n \n\n**Q1**. The entire method depends on the initial $k$-NN graph. How sensitive is the model's performance to the choice of $k$ in this initial step? Does a poor choice of $k$ disproportionately harm SwapGT compared to a standard 1-hop GT?\n\n**A1**. Thank you for your insightful questions. \nFirst, regarding the choice of $k$ in the $k$-NN graph: as noted in Lines 149–151, $k$ is indeed set equal to the sampling size of token sequences. In our original submission, we conducted extensive experiments to investigate how varying this token sampling size impacts model performance across datasets. Our findings consistently show that the optimal sampling size falls within the range of $k$=10 for nearly all datasets tested. This suggests that simply enlarging the length of token sequences, whether through dense or sparse splitting strategies, does not lead to performance improvements in most cases. We hypothesize this is because a larger sampling size increases the probability of introducing irrelevant or noisy nodes as tokens, ultimately degrading model performance. To compare the performance of SwapGT with the worst $k$ and the standard 1-hop GT, we evaluate the performance of standard 1-hop GT on the same sampling size of token sequences. The results are as follows:\n\n| Dense | Photo |  ACM  | Computer | Citeseer | Blogcatalog |  UAI  | Flickr | wikics |\n|:-----:|:-----:|:-----:|:--------:|:--------:|:-----------:|:-----:|:------:|:------:|\n| 1-hop | 94.59 | 93.08 |   90.63  |   75.56  |    93.87    | 75.31 |  85.27 |  82.09 |\n| Worst | 94.71 | 93.26 |   91.06  |   76.20  |    94.16    | 75.65 |  85.34 |  82.30 |\n\n| Sparse | Photo |  ACM  | Computer | Citeseer | Blogcatalog |  UAI  | Flickr | wikics |\n|:------:|:-----:|:-----:|:--------:|:--------:|:-----------:|:-----:|:------:|:------:|\n|  1-hop | 90.80 | 86.76 |   85.55  |   62.89  |    86.13    | 60.56 |  67.61 |  75.46 |\n|  Worst | 91.38 | 87.43 |   86.93  |   63.07  |    86.45    | 61.54 |  68.02 |  75.72 |\n\nFrom these results, we can clearly observe that SwapGT maintains superior performance over the standard 1-hop GT even in worst-case k scenarios. This is because that the token swapping operation can introduce more informative node tokens for node representation learning. \n\nWe will add the above experimental results as well as the corresponding discussions in the revised version. Thank you. \n\n**Q2**. The token swapping operation is presented as the best way to leverage multi-hop information. How does this strategy compare, both conceptually and empirically, to other established multi-hop sampling techniques?\n\n**A2**. Thank you for your insightful questions. First, existing multi-hop node sampling-based strategy depend on the calculation of similarity scores between nodes. They only select the nodes with top-$k$ similarity as node tokens, which naturally ignores the semantic relevance between nodes. In contrast, our proposed token swapping operation can fully utilize the nodes’ semantic relevance to generate various token sequences, resulting in more informative token sequence and further leading to the performance improvement.\nThen, we compare the proposed method with a representative multi-hop node sampling-based tokenized graph Transformer called ANS-GT [1] which leverages random walk-based strategies to sample nodes from multi-hop neighborhoods. The results are as follows:\n\n\n|  Dense | Photo |  ACM  | Computer | Citeseer | Blogcatalog |  UAI  | Flickr | wikics |\n|:------:|:-----:|:-----:|:--------:|:--------:|:-----------:|:-----:|:------:|:------:|\n| ANS-GT | 94.88 | 93.92 |   89.58  |   77.54  |    91.93    | 74.16 |  85.94 |  82.53 |\n| SwapGT | 95.92 | 94.98 |   91.73  |   78.49  |    95.93    | 79.06 |  87.56 |  84.52 |\n\n| Sparse | Photo |  ACM  | Computer | Citeseer | Blogcatalog |  UAI  | Flickr | wikics |\n|:------:|:-----:|:-----:|:--------:|:--------:|:-----------:|:-----:|:------:|:------:|\n| ANS-GT | 90.42 | 88.58 |   84.95  |   62.94  |    78.26    | 55.85 |  64.42 |  75.72 |\n| SwapGT | 92.93 | 90.92 |   88.14  |   69.91  |    88.11    | 63.96 |  72.16 |  78.11 |\n\nWe can observe that SwapGT consistently beats ANS-GT on all datasets under different splitting strategies, which indicates the effectiveness of token swapping operation in SwapGT for node classification, compared to representative sampling-based tokenized GT.\n\nWe will add the above results and discussions in the revised version. Thank you. \n\n[1] Zaixi Zhang, et al. Hierarchical graph transformer with adaptive node sampling. NeurIPS 2022."}, {"review_id": "r7wXtrb85l", "reviewer": "Reviewer_n87V", "summary": "This paper proposes a novel tokenized graph Transformer named SwapGT for the node classification task. Specifically, the authors firstly analyze the drawbacks of token generation in existing tokenized graph Transformers. Then, they design a new token generator called token swapping. By swapping tokens between different token sequences, the proposed token generator can generate diverse token sequences which carry rich graph information. In addition, the authors also develop a center-alignment loss to help the model learn node representations from multi-token sequences. Extensive results indicate that SwapGT outperforms other mainstream methods in the node classification task, such as GNNs and GTs.", "questions": "The questions are summarized as follows:\n\n1. According to Fig. 2, the proposed SwapGT can be regarded as a generalized framework where the Transformer layer is just utilized to learn node representations from input token sequences. In this way, the learning module is optional. I am curious about the performance of SwapGT when integrated with other Transformer variants, such as linear Transformer and PolyFormer.  \n2. Based on Q1, I suggest authors conduct additional ablation studies to validate the influence of learning module on model performance, just like the ablation studies in GraphGPS.\n3. I have noticed that $\\alpha$ in Eq. (8) is an important hyper-parameter. So, can you provide the necessary experiments to explore the influence of $\\alpha$ on model performance? \n4. In A.4, the authors provide the results of SwapGT with different token sampling size. I have found that sparse splitting prefers larger sampling size. Can you provide some insightful discussions for this phenomenon? \n5. What is the value of the swapping probability $p$ in practice?", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The strengths and weaknesses are summarized as follows:\n\nStrengths:  \n1. The motivation of SwapGT is clear.\n2. The idea of swapping token between different token sequences is new and interesting.\n3. The paper is well written.\n4. The experiments of performance comparison are extensive.\n\nWeaknesses:  \n1. The authors only consider standard Transformer.\n2. The experimental section lacks additional ablation studies.  \n3. The analysis of the key hyper-parameter is also required.", "was_revised": true, "final_justification": "The authors provide the additional empirical results of ablation study and parameter analysis which address my concerns raised in the rebuttal. And I also review the comments of other reviewers. Finally, I decide to keep my score.", "rebuttal": "We appreciate the reviewer for providing positive feedback and valuable comments on our paper. Following are our detailed responses to your questions.\n\n**Q1&Q2**. According to Fig. 2, the proposed SwapGT can be regarded as a generalized framework where the Transformer layer is just utilized to learn node representations from input token sequences. In this way, the learning module is optional. I am curious about the performance of SwapGT when integrated with other Transformer variants, such as linear Transformer and PolyFormer? Based on Q1, I suggest authors conduct additional ablation studies to validate the influence of learning module on model performance, just like the ablation studies in GraphGPS.\n\n**A1&A2**. Thank you for your insightful questions. Per your suggestions, we develop two variants of SwapGT, named SwapGT-LT and SwapGT-PF. The former replace the standard Transformer module with the linear attention-based version. The latter introduce the signed attention-based learning module introduced by PolyFormer for representation learning. The results are as follows:\n\n|   Sparse  | Photo |  ACM  | Computer | Citeseer | Blogcatalog |  UAI  | Flickr | wikics |\n|:---------:|:-----:|:-----:|:--------:|:--------:|:-----------:|:-----:|:------:|:------:|\n| SwapGT-LT | 91.35 | 89.06 |   85.69  |   67.21  |    83.73    | 58.22 |  65.13 |  75.13 |\n| SwapGT-PF | 92.08 | 90.15 |   87.03  |   68.74  |    86.97    | 62.92 |  71.44 |  77.32 |\n|   SwapGT  | 92.93 | 90.92 |   88.14  |   69.91  |    88.11    | 63.96 |  72.16 |  78.11 |\n\n|   Dense   | Photo |  ACM  | Computer | Citeseer | Blogcatalog |  UAI  | Flickr | wikics |\n|:---------:|:-----:|:-----:|:--------:|:--------:|:-----------:|:-----:|:------:|:------:|\n| SwapGT-LT | 94.16 | 94.07 |   86.26  |   77.98  |    94.41    | 74.03 |  82.44 |  81.23 |\n| SwapGT-PF | 95.65 | 94.42 |   91.09  |   78.17  |    95.37    | 78.25 |  87.24 |  84.08 |\n|   SwapGT  | 95.92 | 94.98 |   91.73  |   78.49  |    95.93    | 79.06 |  87.56 |  84.52 |\n\nWe can observe that SwapGT beats these two variants on all datasets. This situation indicates that the standard Transformer module is capable of learning informative node representations in the tokenized graph Transformer architecture.\n\nWe will add the above results and discussions in the revised version. Thank you. \n\n**Q3**. I have noticed that $\\alpha$ in Eq. (8) is an important hyper-parameter. So, can you provide the necessary experiments to explore the influence of $\\alpha$ on model performance?\n\n**A3**. Thank you for your insightful questions. Following your suggestions, we vary $\\alpha$ in {0, 0.1, …, 1} and observe the performance of SwapGT. The results are as follows:\n\n| sparse | Photo  | ACM    | Computer | Citeseer | WikiCS | Blogcatalog | UAI2010 | Flickr |\n|--------|--------|--------|----------|----------|--------|-------------|---------|--------|\n| 0      | 92.87  | 88.72  | 87.75    | 68.56    | 76.71  | 86.25       | 59.63   | 71.98  |\n| 0.1    | 92.93  | 90.92  | 88.14    | 68.74    | 76.39  | 88.11       | 60.45   | 72.12  |\n| 0.2    | 92.55  | 89.18  | 87.68    | 69.59    | 78.11  | 84.97       | 61.31   | 72.13  |\n| 0.3    | 92.03  | 88.86  | 86.83    | 69.78    | 76.75  | 86.15       | 61.45   | 72.16  |\n| 0.4    | 91.32  | 87.64  | 85.62    | 69.78    | 76.26  | 85.76       | 63.82   | 72.13  |\n| 0.5    | 89.95  | 86.88  | 85.20    | 68.86    | 75.61  | 85.16       | 63.96   | 72.05  |\n| 0.6    | 86.93  | 86.91  | 82.94    | 69.62    | 73.96  | 85.76       | 63.68   | 71.98  |\n| 0.7    | 86.86  | 85.17  | 82.17    | 69.46    | 73.97  | 85.34       | 57.88   | 71.92  |\n| 0.8    | 83.75  | 83.26  | 80.11    | 69.75    | 72.38  | 84.59       | 56.68   | 71.86  |\n| 0.9    | 81.59  | 81.73  | 77.47    | 69.91    | 70.43  | 83.84       | 54.61   | 70.66  |\n| 1      | 78.92  | 78.42  | 74.05    | 69.81    | 70.07  | 82.77       | 54.37   | 71.62  |\n\n| dense | Photo  | ACM    | Computer | Citeseer | WikiCS | Blogcatalog | UAI2010 | Flickr |\n|-------|--------|--------|----------|----------|--------|-------------|---------|--------|\n| 0     | 94.98  | 93.66  | 91.44    | 78.37    | 84.49  | 94.77       | 77.36   | 86.03  |\n| 0.1   | 95.92  | 93.79  | 91.73    | 78.49    | 84.52  | 94.16       | 77.62   | 86.61  |\n| 0.2   | 94.56  | 94.59  | 91.15    | 78.37    | 84.04  | 94.08       | 79.06   | 86.77  |\n| 0.3   | 95.19  | 94.85  | 91.06    | 78.37    | 83.98  | 94.39       | 78.14   | 86.66  |\n| 0.4   | 94.98  | 94.85  | 90.48    | 78.37    | 83.87  | 95.93       | 77.36   | 87.40  |\n| 0.5   | 94.51  | 94.85  | 89.66    | 78.13    | 84.21  | 94.85       | 78.40   | 87.56  |\n| 0.6   | 94.51  | 94.98  | 89.20    | 78.37    | 83.33  | 95.16       | 78.27   | 86.98  |\n| 0.7   | 93.98  | 94.98  | 88.61    | 78.01    | 82.75  | 95.31       | 76.44   | 86.45  |\n| 0.8   | 93.62  | 93.66  | 87.74    | 78.37    | 82.98  | 95.31       | 76.96   | 87.40  |\n| 0.9   | 93.20  | 92.34  | 86.72    | 78.01    | 83.26  | 94.77       | 76.18   | 87.19  |\n| 1     | 92.78  | 90.76  | 85.73    | 78.37    | 82.10  | 94.62       | 76.57   | 85.92  |\n\nWe can observe that the optimal $\\alpha$ resides within the (0, 1) which indicates that learning node representations from different feature spaces can effectively enhance the model performance. Notably, peak model accuracy occurs when $\\alpha$ falls in (0,0.5], which may reveal that the topology information is more important than the attribute information in the node classification task.\n\nWe will add the completed results and the corresponding discussions in the revised version.\n\n**Q4**. In A.4, the authors provide the results of SwapGT with different token sampling size. I have found that sparse splitting prefers larger sampling size. Can you provide some insightful discussions for this phenomenon?\n\n**A4**. Thank you for your helpful suggestions. The reason could be that the model faces more serious data sparsity issue under the sparse splitting. In this situation, a larger sampling size can bring more node tokens, which can alleviate the impact of data sparsity on the model performance. We will add the above discussions in the revised version.\n \n**Q5**. What is the value of the swapping probability $p$ in practice?\n\n**A5**. Thank you for your questions. In practice, we set $p$ as 0.5 in all experiments. We will clarify the setting of $p$ in the revised version."}, {"review_id": "zfBImpRgmy", "reviewer": "Reviewer_ZA1z", "summary": "This paper proposes a novel tokenized Graph Transformer for node classification by developing a novel token swapping operation that flexibly swaps tokens in different token sequences,called SwapGT,significantly outperforming several GTs and GNNs on extensive experiments.", "questions": "See the weakness part.", "limitations": "No. The authors do not adequately address the limitations of their study and its potential future optimization directions of their work.\n\n- Cons of the novel token swapping operation proposed by SwapGT?\n\n- Any other more efficient method to enhances the model’s ability to capture rich node representations?", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- S1. The method proposed in this paper enhances the model’s ability to capture rich node representations.\n- S2. Experiments on real-world datasets demonstrate that SwapGT achieves better performance on node classification, compared with several representative GNNs and GTs.\n\nWeaknesses:\n- W1. Limited Novelty. The novelty is not clearly articulated, and the distinction from prior tokenized GTs needs further clarification. This paper also lacks a discussion between the proposed method and GTs with global attention.\n- W2. Performance Improvement. Although the proposed SwapGT addresses the performance degradation in sparse splitting, it seems that GNNs do not suffer from sparse splitting, which weakens the significance of performance improvement.\n- W3. Missing limitations. The limitations of the proposed method are not adequately discussed, potentially limiting readers’ understanding of its scope and applicability.", "was_revised": true, "final_justification": "The authors' response has addressed my concerns on novelty and experiments. Therefore, I decide to raise my score.", "rebuttal": "Thank you for detailed comments. We provide the following responses:\n\n**Q1**. Limited Novelty. The novelty is not clearly articulated, and the distinction from prior tokenized GTs needs further clarification. This paper also lacks a discussion between the proposed method and GTs with global attention.\n\n**A1**. Thank you for your comments. First, regarding the differences between SwapGT and prior node-tokenized GTs: as outlined in Lines 45–61 and 109–115, existing node tokenized GTs typically construct token sequences by statically selecting 1-hop neighbors of target nodes from the k-NN graph. In contrast, SwapGT introduces a critical innovation through its token swapping operation, which dynamically expands token sequences beyond the fixed 1-hop neighborhood. By incorporating nodes from broader regions of the k-NN graph (i.e., beyond direct 1-hop connections) into token sequences, SwapGT generates more diverse and contextually rich token sets. This flexibility allows the model to capture more informative structural patterns, which we demonstrate empirically enhances performance in node classification. Besides, the novelty of the proposed SwapGT has also been recognized by all other reviewers.\n\nThen, as discussed in Line 27-35 and Line 94-108, GTs with global attention usually adopts the design of combining Transformer modules with GNN-style modules to construct hybrid neural network layers, which requires the entire graph as the model input and calculating the attention scores between all nodes, leading to the over-globalization issue. While SwapGT adopts the tokenized design, which transforms the input graph into independent token sequences for node representation learning. Since tokenized GTs only focus on the generated tokens, they naturally avoiding the over-globalization issue.\n\nIn the revised version, we will update the discussions of SwapGT and prior GTs, including tokenized GTs and GTs with global attention to highlight the novelty of SwapGT.\n\n**Q2**. Performance Improvement. Although the proposed SwapGT addresses the performance degradation in sparse splitting, it seems that GNNs do not suffer from sparse splitting, which weakens the significance of performance improvement.\n\n**A2**. Thank you for your comments. According to the results shown in Table 2, SwapGT gains 0.5% performance improvement over the runner-up baseline on most datasets. Specifically, SwapGT can achieve around 3.5% and 3.2% performance improvement on BlogCatalog and Citeseer, respectively. These results showcase that the designs of SwapGT can bring significant performance improvement for the node classification task.\n\nWe will add the above discussions in the revised version to highlight the significance of performance improvement.\n\n**Q3**. Missing limitations. The limitations of the proposed method are not adequately discussed, potentially limiting readers’ understanding of its scope and applicability.\n\n**A3**. Thank you for your comments. In the submitted version, we have discussed the limitation of SwapGT in the Appendix E. The potential limitation in SwapGT could be that SwapGT applies a uniform swapping probability $p$ to all tokens in the sequence which ignores the importance of different node tokens. A hierarchical probability swapping framework may be a better solution, where nodes within the top-k most relevant subset are assigned higher swapping probabilities, while others receive lower probabilities. This refinement could mitigate noise interference. In addition, your two suggestions are also valuable for discussing the limitation of SwapGT.\n\nBased on the above content and your comments, we will update the discussions about the limitations of SwapGT in the revised version."}, {"review_id": "MBWfIal21G", "reviewer": "Reviewer_chKg", "summary": "The tokenized graph Transformer has been a popular architecture of graph Transformers for node classification in recent years. While this paper reveals a common limitation of existing tokenized graph Transformer that these methods only leverage limited graph information to construct the token sequences, resulting in unsatisfied performance in several situations (e.g., sparse training data). To address this issue, the authors propose a new method called SwapGT which introduces a novel operation, token swapping. This proposed operation can generate diverse token sequences based on the initial token sequence, like a data augmentation strategy. In the end, the generated token sequences enhance the performance of graph Transformers for node classification, especially in the data sparsity situation.", "questions": "1.\tBased on the previous tokenized graph Transformers (e.g., NAGphormer), the readout function is also an important module. However, the proposed readout function in Eq. (7) lacks necessary motivations. Please provide the insights for the proposed strategy.\n2.\tMoreover, do authors try other readout functions, such as attention-based method in NAGphormer?\n3.\tAlthough the experimental results in both dense splitting and sparse splitting show the promising results, these results lack deeper discussion. For instance, I notice that SwapGT show more significant improvement in the sparse splitting. Can you explain? \n4.\tThere is no introduction for baselines. Why do you choose these methods? Can you provide the corresponding reasons?", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper is well organized and easy to follow.\n2.\tThe proposed token swapping operation is novel.\n3.\tThe authors provide the corresponding theoretical analysis of the generated token sequences.\n4.\tThe empirical results show promising performance.\n\nWeaknesses:\n\n1.\tSome modules lack motivation.\n2.\tExperimental results need deeper and more insightful discussions.\n3.\tThe baselines need necessary introductions, and the reason of selecting baselines is also required.", "was_revised": true, "final_justification": "In the rebuttal, the authors address my main concern about the motivation of the key modules in their proposed method. I'd like to maintain the score as 5.", "rebuttal": "We appreciate the reviewer for providing positive feedback and valuable comments on our paper. Following are our detailed responses to your questions.\n\n**Q1**. Based on the previous tokenized graph Transformers (e.g., NAGphormer), the readout function is also an important module. However, the proposed readout function in Eq. (7) lacks necessary motivations. Please provide the insights for the proposed strategy.\n\n**A1**. Thank you for your insightful suggestions. According to Eq. (7), we regard the combination of the raw token sequence and the augmented token sequences as the final node representation. This strategy can ensure the independence of the information from the original token sequence and generated token sequences. Moreover, we utilize the mean function to obtain the information of generated token sequences, which is a simple but efficient strategy and has been widely adopted in GNNs, such as GraphSAGE.\n\nWe will add the above discussions in the revised version to highlight the motivation of the readout function in SwapGT.\n\n**Q2**. Moreover, do authors try other readout functions, such as attention-based method in NAGphormer?\n\n**A2**. Thank you for your helpful questions. Per your suggestion, we develop a variant named SwapGT-AT which leverages the attention-based readout function for node representation learning. The results are as follows:\n\n| Sparse    | Photo | ACM   | Computer | Citeseer | Blogcatalog | UAI   | Flickr | wikics |\n|-----------|-------|-------|----------|----------|-------------|-------|--------|--------|\n| SwapGT-AT | 92.32 | 89.65 | 87.30    | 68.13    | 87.25       | 63.18 | 71.21  | 77.86  |\n| SwapGT    | 92.93 | 90.92 | 88.14    | 69.91    | 88.11       | 63.96 | 72.16  | 78.11  |\n\n| Dense     | Photo | ACM   | Computer | Citeseer | Blogcatalog | UAI   | Flickr | wikics |\n|-----------|-------|-------|----------|----------|-------------|-------|--------|--------|\n| SwapGT-AT | 95.58 | 94.61 | 91.35    | 77.92    | 95.47       | 78.32 | 87.11  | 83.95  |\n| SwapGT    | 95.92 | 94.98 | 91.73    | 78.49    | 95.93       | 79.06 | 87.56  | 84.52  |\n\nWe can observe that SwapGT beats this variant on all datasets. The reason may be that the neighborhood tokens in NAGphormer have varying importance. In this situation, the attention-based readout function can enhance the model performance. However, the augmented token sequences generated by the token swapping operation do not have this characteristic. Hence, the simple readout function may be more suitable for SwapGT.\n\nWe will add the above results as well as the discussions in the revised version.\n \n\n**Q3**. Although the experimental results in both dense splitting and sparse splitting show the promising results, these results lack deeper discussion. For instance, I notice that SwapGT show more significant improvement in the sparse splitting. Can you explain?\n\n**A3**. Thank you for your insightful questions. As discussed in Line 241-249, the token swapping operation in SwapGT can leverage the semantic relevance of node tokens to generate more informative token sequences, which could be regarded as a data augmentation strategy. These augmented token sequences can improve the data utilization efficiency and significantly enhance the quality of node representation learning, especially in the data sparse splitting. Hence, SwapGT can bring more significant improvement in the sparse splitting.\n\nWe will update the discussions about the results of performance comparison based on the above content in the revised version.\n \n\n**Q4**. There is no introduction for baselines. Why do you choose these methods? Can you provide the corresponding reasons?\n\n\n**A4**. Thank you for your helpful questions. In this paper, we select mainstream GNNs and GTs as baselines. For GNNs, there are two categories of them, coupled GNNs and decoupled GNNs. FAGCN, BM-GCN, ACM-GCN are recent coupled GNNs for node classification. SGC, APPNP, GPRGNN are representative decoupled GNNs. For GTs, we select methods from tokenized GTs and hybrid GTs. NAGphormer, VCR-Graphormer and PolyFormer are powerful tokenized GTs. While SGFormer, Specformer and CoBFormer are representative hybrid GTs.\n\nWe will add the above discussions about the baselines in the revised version."}]

Author rebuttal:

Meta-review: In this paper, the authors study node tokenized graph Transformers (GTs) for node classification. The authors argue that existing GTs only consider first-order neighbors on the similarity graphs, and propose SwapGT, adopting swapping operations to generate more informative token sequences. It also adopts a center alignment loss to constrain the representation learning. Experiments show the effectiveness of SwapGT for node classification.

The paper received mixed comments. The reviewers agree that the paper is clearly written, well-structured, and motivated by a concrete limitation in existing tokenized GTs. Initially, several concerns regarding technical novelty and insufficient experiments have been raised. During rebuttal, the authors have provided more results and explanations, which successfully address the concerns of three reviewers. The only remaining negative reviewer did not engage in discussions all along. I have briefly checked the paper and review comments. Despite some potential weaknesses, such as the technical analyses not being very deep, its core idea is novel and the empirical validation is extensive, so the paper makes a meaningful contribution to advancing tokenized GTs. I therefore recommend acceptance.
Decision: Accept (poster)