Rethinking Tokenized Graph Transformers for Node Classification

We appreciate the reviewer for providing positive feedback and valuable comments on our paper. Following are our detailed responses to your questions.

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.

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.

We will add the above discussions in the revised version to highlight the motivation of the readout function in SwapGT.

Q2. Moreover, do authors try other readout functions, such as attention-based method in NAGphormer?

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:

We 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.

We will add the above results as well as the discussions in the revised version.  

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?

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.

We will update the discussions about the results of performance comparison based on the above content in the revised version.  

Q4. There is no introduction for baselines. Why do you choose these methods? Can you provide the corresponding reasons?

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.

We will add the above discussions about the baselines in the revised version.

Thank you for detailed comments. We provide the following responses:

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.

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.

Then, 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.

In 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.

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.

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.

We will add the above discussions in the revised version to highlight the significance of performance improvement.

Q3. Missing limitations. The limitations of the proposed method are not adequately discussed, potentially limiting readers’ understanding of its scope and applicability.

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.

Based on the above content and your comments, we will update the discussions about the limitations of SwapGT in the revised version.

We appreciate the reviewer for providing positive feedback and valuable comments on our paper. Following are our detailed responses to your questions.

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.

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:

We 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.

We will add the above results and discussions in the revised version. Thank you. 

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?

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:

We 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.

We will add the completed results and the corresponding discussions in the revised version.

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?

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.

Q5. What is the value of the swapping probability $p$ in practice?

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.

Thank you for detailed comments. We provide the following responses:  

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?

A1. Thank you for your insightful questions. First, 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:

From 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.

We will add the above experimental results as well as the corresponding discussions in the revised version. Thank you. 

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?

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. Then, 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:

We 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.

We will add the above results and discussions in the revised version. Thank you. 

[1] Zaixi Zhang, et al. Hierarchical graph transformer with adaptive node sampling. NeurIPS 2022.

Dear Reviewer,

The authors have submitted a rebuttal. Please take a moment to read it and engage in discussion with the authors if necessary.

Best regards, AC

We sincerely thank Reviewer yYpa for recognizing our work. As we are currently within the reviewer-author discussion period, if you have any further questions or concerns regarding our work, we warmly welcome your feedback. We will do our utmost to address and clarify them. Once again, we truly appreciate your valuable time in reviewing and engaging in the discussion.