Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers
Authors: Jinsong Chen
Hanpeng Liu
John E. Hopcroft
Kun He
Venue: NeurIPS 2024 poster (2024)
Keywords: Node classification
Graph Transformer
Positive Token Sequence
Negative Token Sequence
Contrastive Learning
Primary area: graph_neural_networks
TL;DR: This paper enhances node classification in graph Transformers by leveraging contrastive learning and a hybrid token generator to capture diverse graph information.

Abstract: While tokenized graph Transformers have demonstrated strong performance in node classification tasks, their reliance on a limited subset of nodes with high similarity scores for constructing token sequences overlooks valuable information from other nodes, hindering their ability to fully harness graph information for learning optimal node representations. To address this limitation, we propose a novel graph Transformer called GCFormer. Unlike previous approaches, GCFormer develops a hybrid token generator to create two types of token sequences, positive and negative, to capture diverse graph information. And a tailored Transformer-based backbone is adopted to learn meaningful node representations from these generated token sequences. Additionally, GCFormer introduces contrastive learning to extract valuable information from both positive and negative token sequences, enhancing the quality of learned node representations. Extensive experimental results across various datasets, including homophily and heterophily graphs, demonstrate the superiority of GCFormer in node classification, when compared to representative graph neural networks (GNNs) and graph Transformers.

Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers
Jinsong Chen 1.233 Hanpeng Liu 1.3, John E. Hopcroft Kun Hel.3+
School of Computer Science and Technology, Huazhong University of Science and Technology
2 Institute of Artificial Intelligence, Huazhong University of Science and Technology
3 Hoperoft Center on Computing Science, Huazhong University of Science and Technology *Department of Computer Science, Cornell University {chenjinsone hanpengliu edu. en, jehêcs cornell. edu, brooklet60@hust. edu.
Abstract
While tokenized graph Transformers have demonstrated strong performance in node classification tasks, their reliance on a limited subset of nodes with high similarity scores for constructing token sequences overlooks valuable information from other nodes, hindering their ability to fully harness graph information for learning optimal node representations. To address this limitation, we propose novel graph Transformer called GCFormer. Unlike previous approaches, GCFormer develops hybrid token generator create two types of token sequences, positive and negative, to capture diverse graph information. And a tailored Transformer-based backbone is adopted learn meaningful node representations from these generated token sequences. Additionally, GCFormer introduces contrastive learning to extract valuable information from both positive and negative token sequences, enhancing the quality of learned node representations. Extensive experimental results across various datasets, including homophily and heterophily graphs, demonstrate the superiority of GCFormer in node classification, when compared to representative graph neural networks (GNNs) and graph Transformers.
1 Introduction
Node classification, a crucial machine learning task in graph data mining, has garnered significant attention recently due to its wide applicability in diverse areas such social network analysis [24, 35]. Among numerous techniques developed for this task, graph neural networks (GNNs) stand out as the leading architecture due their exceptional ability to model graph structural data.
Built on the pesssag--passing mechanism [14], GNNs [19, 8, 9. 33. 34] efficiently integrate node and graph topology features to learn informative node representations, effectively preserving both attribute and structural information. However, as research on GNNs progresses, inherent limitations of the bassage-passing framework, such as over-smoothing [5] and over-squashing [1], have emerged. These limitations hinder GNNs' ability to capture long-range dependencics in graphs, ultimately constraining their potential for node classification.
Recently, the emerging graph Transformer has attracted great attention in the field of graph represen- tation learning. The crux of this approach is to leverage the Transformer architecture to learn node representations from the input graph. Benefiting from the self-attention mechanism in Transformer, graph Transformers [45, 17, 6, 7, 50] can effectively capture the long-range dependencies in graphs. Serving as a new deep learning- based technique for graphs, graph Transformers have showeased
"Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Previous methods
Abendoned tokens
Token sompling
Model
input
Measure similarity
Imput
Trockformer-bockkbee
Ronk
Negative 1öken sompling
Positive taken sompling
Model input
Our methad
Input graph
Node tokenized graph Transformers
Figure 1: A toy example to illustrate the difference of the token generator between the token generator in our method and that used in the previous node tokenized graph Transformers. Previous methods only sample nodes with high similarity to construct token sequences. In contrast, our method introduces both positive and negative token sampling to preserve information carried by diverse nodes in the graph.
remarkable performance in the node classification task. In this study, We roughly divide the existing graph Transformers designed for node classification into two categories according to the model architecture: GNN-based graph Transformers and tokenized graph Transformers.
GNN-based graph Transformers [30, 42, 41, 23, 27] utilize a hybrid framework that merges Trans- former layers with GNN-style modules learn node representations. However, this approach may constrain the modeling capacity of the Transformer architecture due to the deeply coupled design of the Transformer and GNN layers. A recent study [44] also theoretically proves that directly applying Transformer to calculate the attention scores all node pairs could cause the over-globalizing prob- lem, which causes the model to overly rely on global information, negatively affecting the model's performance.
In contrast, tokenized graph Transformers [52, 50, 7, 13] initially generate token sequences for each node and only calculate attention scores between tokens within the token sequence, naturally avoiding the over-globalizing issue. These token sequences backbone to learn node representations. This mechanism allows the Transformer to flexibly extract informative node representations based the input token sequences, demonstrating impressive performance node classification. Note that, tokenized graph Transformers focus on building token sequences for each target node as model inputs, which different from TokenGT [18] that transforms all elements in graphs as tokens.
then processed by Transformer-bass based
Token generation is crucial step in tokenized graph Transformers, where node [50] and neigh- borhood [7] elements form the core of the token sequences. While neighborhood tokens primarily preserve local topology features [13], node tokens capture broader range of graph information, including long-range dependencies and intrinsic graph properties (e.g., homophily and heterophily). These advantages allow graph Transformers built node-oriented token sequences [52, 50, 13] to learn more informative node representations, compared to those based on neighborhood-oriente token sequences.
In this study, we observe that the techniques employed by existing tokenized graph Transformers for generating node-orient token sequences could be summarized two-step method. First, they estimate the node similarity matrix according to node information across various feature spaces, such as topology features [52] and attribute features [50, 13]. They then sample a fixed number of nodes with high similarity scores from the generated similarity matrix to construct the input token sequence for target node. As depicted in Figure only a small subset of nodes is considered, while other nodes are excluded during the training stage.
Compared to sampled nodes which capture the commonality with the target node, these abandoned nodes preserve the disparity, which is also valuable for learning distinguishable node representations. A previous study [3] has proved that leveraging the information from dissimilar nodes aids the

---

learning of node representations. Nevertheless, existing tokenized graph Transformers can not comprehensively utilize both similar and dissimilar nodes learn the representation of the target node, inevitably limiting the model performance for node classification. Hence, a natural question arises: How should we design a new graph Transformer to comprehensively and effectively leverage diverse nodes in graphs to learn distinguishable node representations?
To answer this question, we propose a new method called Graph Contrastive Transformer (GCFormer). Unlike previous graph Transformers, GCFormer first introduces a novel token sequence generator that produces both positive and negative token sequences for each node different feature spaces. In this way, various graph information carried by node tokens can be carefully preserved in different types of token sequences. Then, GCFormer develops a new Transformer- -based backbone tailored for effectively learning node representations from the generated positive and negative token sequences. Finally, GCFormer leverages the contrastive learning to comprehensively utilize the tokens both positive and negative sequences to further enhance the quality of learned node representations.
The main contributions of this paper are summarized follows:
We develop new token sequence generator that can generate different types of token sequences terms of positive and negative node tokens for each target node to preserve various graph information.
We propose new graph Transformer GCFormer that formulates Transformer-based back- bone and leverages the contrastive learning to comprehensively learn node representations from positive and negative token sequences.
We conduct extensive experiments on both homophily and heterophily graphs to validate the effectiveness of the proposed method. Experimental results demonstrate the superiority of GCFormer in node classification compared to representative GNNs and graph Transformers.
2
Related Work
In this section, we first introduce recent studies graph Transformers for node classification. We then briefly review studies about contrastive learning on graphs.
2.1 Graph Transformer
We categorize existing graph Transformers for node classification into GNN-based methods and tokenized methods. The former [30, 41, 42, 23, 27] combines the Transformer layers with GNN-style modules to learn node representations. GraphGPS [41], one of the representative approaches, incorpo- rates various linear Transformers, such as Reformer [20] and Big [47], and GNN layers [19] into a unified framework for graph representation learning. However, these approaches require performing the attention calculation on all node pairs, which can lead to what is known as the over-globalizing problem. A recent study [44] provides both empirical evidence and theoretical analysis to show that calculating attention scores for all nodes can cause the model to overly rely on global information, which can negatively affect the model's performance in node classification tasks.
In contrast, tokenized methods purely depend on the Transformer architecture. The key idea is to gen- erate token sequences for each node from the input graph, which are then fed to Transformer to learn node representations. Node-based [52, 50, 13] and neighborhood-basse have been developed to generate various token sequences for nodes. Node-based token generators first calculate the similarity of nodes according to node features such as attribute features [50], then sample nodes with high similarity scores as tokens of the input sequence. While neighborhood- based token generators [7] aggregate the features of multi-hop neighborhoods and further transform them into tokens to construct the token sequence. Compared to neighborhood tokens can express more complex graph information, such as long-range dependencies, which are more suitable for learning informative node representations.
[7, 11, 13] token generators
tokens, node-based based
Different from previous node token-based graph Transformers that only consider nodes with high similarity, our proposed GCFormer generates both positive and negative token sequences from all nodes in the graph. Various graph information carried by diverse nodes in two types of token sequences enables GCFormer to learn more distinguishable node representations, leading to superior performance.
3

---

2.2 Contrastive Learning on Graphs
Graph contrastive learning (GCL) [36, 54, 46, 31, 49] aims introduce the contrastive learning mechanism into GNNs to learn informative representations of graphs. Most of GCL approaches share similar framework that first performs graph augmentation techniques generate various features of different graph views and then applies the contrastive loss these generated views to learn graph representations [31]. Recent studies [32. 53, 48, 51J attempt to introduce contrastive learning into graph Transformers. However, these methods require the entire graph as the model input [51, 48] or need to combine GNN-based modules with tailored graph augmentation strategies [32, 53], which are hard to directly apply on tokenized graph Transformers in the node classification task.
Our proposed GCFormer develops new token generator generate both positive and negative token sequences for each node without any data augmentations. With the dedicated Transformer based backbone, GCFormer can effectively leverage the contrastive learning to comprehensively learn informative node representations from two types of token sequences.
Preliminaries
3.1 Node Classification
Consider an attributed graph 9 = (V, E), where and are the node and edge sets, respectively. We have the corresponding adjacency matrix A In where is the number of nodes. For arbitrary two nodes U; and U/ A.j = only if e;j E. The diagonal degree matrix D E Ra*= is represented D -Ø Aij. The normalized version of the adjaceney matrix with self-loops is represented as Å = (D++I 102 +A++I)(D) +D((+D))-H)
where I denotes the identity matrix. Nodes in are associated with attribute feature vectors, assembled into an attribute feature matrix denoted as X E Roxd where d is the dimension of the feature vector. The node label matrix Y E R where is the label count, consists of rows that are one-hot vectors encoding the label of each node. Each row in Y is a one-hot vector representing the label information of the corresponding node. Given subset nodes with known labels Vi, the objective node classification is to infer the labels for the remaining nodes in the set V Vi.
3.2 Transformer
Transformer stands notable model in deep learning, built upon the Encoder-Decode architecture. This brief overview focuses on the Transformer layer, a pivotal component of the model. Each Transformer layer is composed of two essential parts: Multi-Head Self-Attention (MSA) and Feed- Forward Networks (FFN).
MSA harnesses multiple attention heads, employing the self-attention mechanism to refine the representations of input entities. Given the input feature matrix H [g=x,, the calculation of the i-th attention head is follows:
QKT V
head, Softmax
(1)
ddz
where Q = HWQ. K HWk K and V = HWv. Wo E Rdoxds WK E Rdixxda and Wv E Rd xd. are learnable parameter matrices. The output of MSA with m attention heads is calculated as:
H' = (head, [heady/]- -..
[head, Wo.
where || denotes the vector concatenation operation and Wo is the learnable matrix.
FFN, comprised of two linear layers enveloping nonlinear activation function, is defined as:
= Lincar(((Linear(]]
(3)
where Linear(-) indicates linear layer, and ((-) symbolizes the nonlinear activation function.
4 Method
In this section, we detail our proposed GCFormer. First, we introduce the hybrid token generator, which produces both positive and negative token sequences for each node. Then, introduce the

---

tailored Transformer-basee backbone for extracting node representations from the generated token sequences. Finally, we introduce how integrate contrastive learning into GCFormer to enhanced node representations.
4.1 Hybrid Token Generator
The proposed hybrid token generator contains two steps: similarity estimating and node sampling. The critical operation of similarity estimating is to calculate the similarity score matrix S E "R"x" of all node pairs. Obviously, different node features lead to different score matrices, describing node pairs' relations in different feature spaces. To preserve the complex relations of nodes in the graph, besides the attribute-awae aware feature matrix X", we construct the topology-awe -aware feature matrix X":
A'=
where l is the propagation step. X preserves the local topology feature within the hohop neigh- borhood for each node, which the essential information to characterize the node property on the graph [7, 16].
Then, we utilize the cosine similarity to calculate the similarity score S E R and S E R based on the node feature matrices X and X', respectively. Given a node pair (vy, v2), the similarity scores in the attribute feature space Sūj and topology feature space Si are calculated as follows:
X
X X
X
S
S
After estimating the similarity scores of all node pairs, GCFormer then conducts two-stage sampling process involving positive token sampling and negative node sampling to generate the token sequences. Here, we introduce the sampling process based on the attribute similarity matrix S for a simplified description. For a given target node 24 in the positive token sampling stage, we adopt the top-k strategy to select nodes to construct the positive token sequence:
Vi {oyloy E Top(S;))
where Top(-) denotes the top-k sampling function and Vi denotes the positive token sequence with length Pa- As for the negative token sampling stage, we have the set of rest nodes for i after positive token sampling V.a." = V - V. P. In this paper, we regard all nodes in V.a. as the negative samples since their similarity scores are below the threshold of top-k selection. Then, we apply the sampling function to sample nodes from V.a." to construct the negative token sequence for iy:
V v..n {1yloy Sample(V,""))
(7)
where Sample(-) denotes an arbitrary sampling function. Here, we use uniform sampling for computing efficiency. Via0 denotes the negative token sequence with length nig
Following the same sampling process, we can obtain positive and negative token sequences V and 1/ based on the topology similarity matrix S'. The constructed positive and negative token sequences not only capture node relations in different feature spaces but also comprehensively extract valuable information from all nodes on the graph.
4.2 Transformer-based Backbone
GCFormer formulates a Transformer-based backbone to effectively learn node representations from positive and negative token sequences. For a node ii, first combine itself with generated positive and negative token sequences to construct the model input, H E (1+ xxd) (X,, Xp: Xn V.S.P, Un. V.a.") and H E [BI++pttm))xdd (X X X V, Un
V. Note that we utilize the generated X construct the model input of topology-aware token sequences. In this way, the topology features can be carefully preserved in the model input H*. exhibiting significant differences with previous methods [52, 50, 13] that utilize the attribute features to construct topology-ave -ware token sequences. Following previous studies [8, 7, 13), we leverage projection layers to obtain the initial input:
H
H Wa H H wt.
(8)
5

---

where Wa R and W E Rdddo denote the parameter matrices of the projection layers.
Given the model input Has of the node v4, GCFormer first separates the negative tokens from H resulting in two parts: pa,; E ((++))) and Na. E R Next, GCFormer adds virtual token with learnable features into Na, as the first token to facilitate extracting valuable information from negative tokens. Then, GCFormer adopts standard Transformers layers learn node representations from Pa, and Na,
paai0 MSA(P
pa (PN(PP..O)))
+ +pp.,
(9)
No MSA(N
(N No No. = FFN 10y
+ No,
(10)
where MSA(-) and FFN(.) denote the multi-head self-attention and feed-forward networks.
Through several Transformer layers, the corresponding pa, E (I(+)))) and N E (ad))ax contains information extracted from positive and negative token sequences, respec- tively. To effectively fuse information from different types of token sequences, inspired by signed attention mechanism in previous approaches [3, 10], we develop the following readout function:
H $ = po No.
(11)
where H E TR. xxout denote the node representation of v extracted from the attribute-aware token sequence.
The rationale of Equation 11 is that the representations Po (the target node) and N (the virtual node) contain the learned information from positive and negative token sequences, respectively. The desired representation of e; should be far away from the representations of negative tokens in the hidden feature space since there is high probability that they belong to different labels. While the signed aggregation operation can enforce H to be dissimilar with the representations of negative tokens according to the previous study [3, 10].
We can also obtain the representation H E RIixdaut extracting from the topology-awas token sequence H via the same operation. Considering the contributions attribute information and topology information vary on different graphs, develop a weighted fusion strategy to obtain the final representation Z:
Z a + - a) .
(12)
where a [0, 1] is a hyper-panee parameter to determine the contributions of attribute information and topology information to the final representation.
4.3 Integrating Contrastive Learning
Though Equation 11 leverages information of negative tokens to learn node representation, it fails to directly model relations between the target node and its negative tokens. To this end, introduce the contrastive learning loss [15] to fully utilize negative tokens for enhanced node representations. For node U; the contrastive learning loss is calculated as follows:
(a((s)) - log exp(Po pa."" /T)
exp(P') Pr."" /T)
log
(13)
En exp pa. No. /T) En exp N N /7)
where pa.1 = Eイ= P and p pa tion 13 enforces the representation of the target node to be close to the central representation of all positive tokens and away from all negative samples, which promotes learning distinguishable node representations, beneficial for downstream classification tasks. We further adopt the Cross-entropy loss for node classification:
PL P/. is temperature ppramm-rrameter. Equa-
PL
Les
Σ Y.n Y, MLP(Z'),
(14)
IEVI
where M-P(-) denotes the Multilayer Perceptron- classifier. Hence, the overall loss function of GCFormer is as follows:
C Lee + 3 Let:
(15)
where 8 is the coefficient for the contrastive learning term.

---

Table Comparison of all models in terms of mean accuracy stdev (%). The best results appear in
bold. The second results appear in underline.
Dataset
Photo
ACM
Comuter
Corafull
BlogCatalog
UA12010
Flickr
Romanempire
(())
0.83
0.82
0.78
0.57
0,40
0.36
0.24
0.05
APPNP
93.00gess
93.00
20.37 =1
94.77
76.41
84.661831
$2.96
SGC
9307
93.24
88, 90
22.77
=2m61=0m
69.87.am7
47.48
34.42
GPRGNN
94.57
93.42=030
90. 15034
69.08
94,36=029
76.94
85,91
67,06s622
FAGCN
94.06 =4.06
-3.37=024
83, 13.17
56.61=294
79,92-4.9
72. 12.
82.03=0aa
48.21
ACM-GCN
94,56=u2
93.04=129
85, 35.19-2.26
11
94,53-0.8
76.87+1422
83.85
63.35+130
SGFormer
=2.
93.79-104
81,86-3.1
64.62+1.0
94,33
+7.98+195
61,05+oar
41,31
ANS-GT
94.88euzi
93.92-12
89.58
91,93 =0.3
74.16
85.94
73,95
Specforner
g5.22
93.63
85.47
69.18 g855
94.21 goas
73.06
86.55 2ovu
63.69
VCR- CCR-Grrphormer
95.131uxx
93.24
90.14 _w
68.96 18.96
93.92..em
75.78
86,23 1ooe
74,76.0ax
GraphGPS
93.791mm
93.31
89.21 Lnzs
12.
94.35 Lo97
75.44
83.61
68.29 Love
NAGphormer
95.47.07
93.32gmm
90.79_n.ms
69.34 gm
94,42
76.36g11
26.85
74.94
GCFormer
95.65
94.32-uur
92.09-6.2
69.53
96.03-e.44
77.57+
87,90=e48
75.38
5 Experiments
5.1 Experimental Setup
We briefly introduce the experimental setup including datasets, baselines and parameter settings. Detailed information is provided Appendix A due to the space limitation.
Datasets, We adopt eight widely used datasets, including four homophily and four heterophily graphs:
Photo [7], ACM [37]. Computer [7]. Corafull [4]. BlogCatalog [28]. UA12010 [38], Flickr [28] and Romanempire [29]. The edge homophily ratio [22] (G) E [0, 1] is adopted to evaluate the graph's 's homophily level. H()) + means strong homophily, while H()) - 0 means strong heterophily. Statistics of datasets are summarized in Appendix A. Following the settings of previous
studies [41, 42], we randomly choose 50% of each label as the training set, 25% as the validation set, and the rest as the test set.
Baselines. We adopt eleven powerful approaches on node classification baselines, including GNNs and graph Transformers: APPNP [21], SGC [40]. GPRGNN [12], FAGCN [3], ACM-GCN [26], SGFormer [42]. ANS-GT [50]. Specformer [2]. WCR-Graphormer [13], GraphGPS [30] and NAGphormer [7]. The first five are representative GNNs and others are recent graph Transformers.
Parameter settings. For baselines, referring to recommended settings in their official implemen- tations, we perform hyper-parameter tuning for all models. For GCFormer, we try the dimen- sion of hidden representations in {128, 256, 512), number of layers in (1, 2,3, learning rate in {0.01, 0.005, 0.001}, dropout rate in {0.1, 0.3, 0.5). The training process is early stopped within 50 epochs and parameters are optimized using AdamW [25).
5.2 Performance Comparison
To evaluate the model performance in node classification, we run each model with different random seeds on datasets and report the average value of accuracy and the corresponding standard deviation.
Table reports the results. We can observe that GCFormer achieves the best performance all datasets, indicating the superiority of GCFormer on the node classification task. Specifically, all datasets, especially ANS-GT which
GCFormer beats recent tokenized graph Transformers is the representative method of node token sequence-base -based graph Transformers. This is because that GCFormer generates both positive and negative token sequences for each node, which preserve both commonality and disparity between node features. In addition, the tailored Transformer based backbone and contrastive learning enable GCFormer to comprehensively learn distinguishable node representations from different types of token sequences, further enhancing the performance in the node classification task. Moreover, we also find graph Transformer-based baselines achieve higher accuracy values than GNN-based basclines on over half of datasets. This is because graph Transformers can
Due to the various implementations of GraphGPS, here we only report the best combination. Detailed results of all combinations can refer to Appendix C.
7

---

1530
$2.00
65.9
12
2000
Px
Px
Pr
(a) Photo
(b) ACM
(c) Computer
(d) Corafull
TEK
B500
755
90.0
4000
X00
2.3.
3
5:30
Px
Px
Px
(c) BlogCatalog
(f) UA12010
(g) Flickr
(h) Romanempire
Figure 2: Performance of GCFormer with different sampling sizes all datasets.
effectively preserve various graph information, such as local topology features [7] and long-range dependencies [50], revealing the potential graph Transformers in graph mining tasks.
5.3 Parameter Sensitivity Analysis
The token sampling size and the aggregation weight in Equation 12 are key parameters in GCFormer. The former determines the model input and the latter controls the learning of final node representations from different feature spaces. Here, we conduct experiments to analyze the influence of these parameters on model performance.
Analysis token sampling sizes. To analyze the influence of different sampling sizes on model performance, vary Pk and n4 in 3 (2.3..... 10} where py and ny the lengths of positive token sequences and negative token sequences. Figure shows the changes in model performance across all datasets. Generally speaking, a large sampling size of negative tokens can lead to competitive model performance. For instance, fg over six can enable GCFormer to achieve high accuracy on almost all datasets except ACM. This is because large value of ny more conducive to preserving the disparity between target nodes and negative node tokens, leading to more distinguishable node representations. This phenomenon also indicates that introducing negative tokens can effectively enhance the performance of tokenized graph Transformers in node classification. In addition, GCFormer is relatively sensitive to ny. Half of the datasets, such as Photo and BlogCatalog, require small value of np to achieve competitive performance. While other datasets prefer large np- This because different graphs can exhibit diverse features, including node attribute features and graph topology features, which affect the sampling of positive tokens. And a large np could introduce irrelevant nodes into positive token sequences when the features of graphs are too complex to sample relevant nodes, further hurting the performance of GCFormer.
Analysis of a. To explore the influence of on model performance, we vary a in {0, O... 1} and observe the changes of model performance. = 0 or a = 1 mean that we abandon the information from attribute-aware token sequences or topology-aware token sequences when generating the final node representations. Results across all datasets are shown in Figure 3. We can find that the optimal falls (0. 1) for all datasets. This observation indicates that comprehensively considering the features of attribute and topology information is essential to learn distinguishable node representations. Another observation that the model performances on graphs extracted from the same domain exhibit similar changing trends. For instance, GCFormer achieves the best performance when BlogCotalog and Flickr, which are extracted from the social platforms. This may because graphs extracted from the same domains exhibit similar graph topology features and node attribute features.
0.5 on

---

Computer
100000
100.00
95.10
50.00
Accuracy (%)
13.00
11
X1.00
9100
50.00
Cloglatalog
UA12010
Flickr
Romanempire
Accuracy
90.00
70000
80.00
$5.00
12:00
75.00
50.00
0.0
0.4
0.1
Figure 3: Performance GCFormer with different a on all datasets.
GCFormer-N
GCFormer-C
GCForee-NE
GCFomer-NN
GCFomer
96.00
92.50
70.00
Accuracy (%)
92.00
91.50
95.00
93.50
91.00
94.50
93.00
90.50
68.50
Photo
ACM
Computer
Corafull
96.50
78.00
90.00
75,50
88.00
Accuracy
96.00
76.00
75.00
$4.00
72.00
82.00
74,00
BlogCatalog
UA12010
Flickr
Romanempire
Figure 4: Performances of GCFormer and its variants.
5.4 Ablation Study
Generating negative token sequences and integrating contrastive learning loss are two key designs of GCFormer. To comprehensively validate the effectiveness these designs, we propose four variants of GCFormer termed GCForme-NN, GCFormer-C C, GCFormer-Ne and GCFormer-NN GCFormer-N removes the negative token sequences and the contrastive learning loss. GCFormer-C only removes the contrastive learning loss. GCFormer-ND retains the use of Transformer layers for learning negative token representations but only employs these representations in the contrastive learning loss (ignoring them in Equation 11). GCFormer-NN, conversely, directly uses the representations of negative tokens for contrastive learning without passing them through Transformer layers. We then run four variants on all datasets and the results are shown in Figure We can observe that GCFormer beats four variants on all datasets, indicating the effectiveness of our key designs in enhancing the model performance. addition, can also find that GCFormer-C beats GCFormer-N on over half' datasets. This phenomenon demonstrates that introducing negative token sequences can effectively improve the model performance. Nevertheless, the performances of GCFormer- C behind GCFormer- N on three citation networks. This situation reveals that different types of graphs can affect the gains of introducing negative tokens. In addition, The results demonstrate that GCFormer-NE outperforms GCFormer-NN on all datasets, indicating that leveraging the Transformer to learn representations of negative tokens can effectively enhance the benefits of introducing contrastive learning. Furthermore, GCFormer surpasses GCFormer-NE, suggesting that comprchensively utilizing the representations

---

of negative tokens through the signed aggregation operation and contrastive learning can further augment the model's ability to learn more discriminative node representations.
Conclusion
In this paper, we propose GCFormer, novel graph Transformer for node classification. GCFormer establishes new framework of tokenized graph Transformers to effectively learn node representations. Specifically, GCFormer develops new hybrid token generator that generates both positive and negative token sequences. Compared to previous methods that only sample nodes with high similarity as tokens, GCFormer considers diverse nodes with high and low similarity. This merit enables GCFormer to preserve both commonality and disparity between node representations. By formulating baseed a Transformer- based backbone and integrating contrastive learning. GCFormer can comprehensively learn distinguishable node representations from different types of token sequences. Extensive experimental results on diverse graphs extracted from different domains showcase the superiority of GCFormer in node classification compared to representative GNNs and graph Transformers.
The main limitation of GCFormer is the unified sampling strategy for different types of graphs Experimental results show that the performance of GCFormer is sensitive to the sampling size on different graphs. The phenomenon implies that an adaptive sampling strategy is required to improve the performance and stability of GCFormer on diverse graphs.
Acknowledgments
This work is supported by National Natural Science Foundation (62076105,U2222017),
References
[1] Uri Alon and Eran Yahav. 2021, On the Bottleneck of Graph Neural Networks and its Practical Implications. In Proceedings of the International Conference Learning Representations.
[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 Artificial Intelligence. 3950-3957.
[4] Aleksandar Bojchevski and Stephan Günnemann. 2018 Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. In Proceedings of the International Conference on Learning Representations.
[5] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. 2020. Measuring and Relieving the Swor-Smoo Problem for Graph Neural Networks from the Topological View. In Proceedings of the AAAI Conference on Artificial Intelligence. 3438-3445.
[6] Dexiong Chen, Leslic O' O'Bray, and Karsten Borgwardt. 2022. Structure-awarr Transformer for Graph Representation Learning. In Proceedings of the International Conference Machine Learning, Vol. 162. 3469-3489.
[7] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. 2023. NAGphormer: A Tokenized Graph Transformer for Node Classification Large Graphs. Proceedings of the International Conference on Learning Representations.
[8] Jinsong Chen, Boyu Li, and Kun He. 2024. Neighhorhood Convolutional Graph Neural Network. Knowledge- 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] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In Proceedings of the International Conference on Learning Representations.
[13] Dongqi Fu, Zhigang Hua, Yan Xie, Jin Fang. Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. 2024. -CR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections. CoRR abs/2403. 16030 (2024).
[14] Justin Gilmer. Samuel S Schoenholz. Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural Message Passing for Quantum Chemistry. In Proceedings of the International Conference on Machine Learning. 1263-1272.
[15] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. 2020. Momentum Con- trast for Unsupervised Visual Representation Learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 9726-9735.
[16] 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. 181-190.
[17] Paras Jain, Zhanghao Wu, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. 2021. Representing Long-Rang Context for Graph Neural Networks with Global Attention. In Proceedings of the Annual Conference Neural Information Processing Systems. 19266-13279.
[18] Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. 2022. Pure Transformers are Powerful Graph Learners. In Proceedings of the Annual Conference on Neural Information Processing Systems.
[19] Thomas N Kipf' and Max Welling. 2017. Semi-supervised Classification with Graph Convolu- tional Networks, In Proceedings of the International Conference on Learning Representations.
[20] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. 2020. Reformer: The Efficient Transformer. In Proceedings of the International Conference on Learning Representations.
[21] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2019. Predict then Propa- gate: Graph Neural Networks Meet Personalized PageRank, Proceedings of the International Conference Learning Representations.
[22] 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, Vol. 162. 12242-13255
[23] Chuang Liu, Yibing Zhan, Xueqi Ma, Liang Ding, Dapeng Tao, Jia Wu, and Wenbin Hu. 2023. Gapformer: Graph transformer with graph pooling for node classification. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence. 21 2196-2205.
[24] Zewen Liu, Guancheng Wan, B Aditya Prakash, Max SY Lau, and Wei Jin. 2024. A review of graph neural networks in epidemic modeling. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 6577-6587.
[25] Ilya Loshchilov and Frank Hutter. 2019. Decoupled Weight Decay Regularization. In Proceed- ings of the International Conference on Learning Representations.
[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] 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. 533-544,
[28] 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. 393-401.
[29] 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.
[30] 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 Annual Conference on Neural Information Processing Systems.
[31] Xiao Shen, Dewang Sun, Shirui Pan, Xi Zhou, and Laurence T. Yang. 2023. Neighbor Con- trastive Learning on Learnable Graph Augmentation. In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence. 9782-9791.
[32] Yundong Sun, Dongjie Zhu, Yansong Wang, and Zhaoshuo Tian. 2024. GTC: GNN-Transformn Co-contrastive Learning for Self-supervised Heterogeneous Graph Representation. CoRR Abs/2403.15520 (2024).
[33] Zihan Tan, Guancheng Wan, Wenke Huang, and Mang Ye. 2024. FedSSP: Federated Graph Learning with Spectral Knowledge and Personalized Preference. In Thirty-eighth Annual Conference on Neural Information Processing Systems.
[34] Guancheng Wan, Wenke Huang, and Mang Ye. 2024. Federated Graph Learning under Domain Shift with Generalizable Prototypes. In Proceedings of the AAAI Conference Artificial Intelligence, Vol. 38. 15429-15437.
[35] Guancheng Wan, Zewen Liu, Max S.Y. Lau, B. Aditya Prakash, and Wei Jin. 2024. Epidemiology-Aware Neural ODE with Continuous Disease Transmission Graph. arXiv preprint arXiv:2410.00049 (2024).
[36] Guancheng Wan, Yijun Tian, Wenke Huang, Nitesh V Chawla, and Mang Ye. 2024. S3GCL: Spectral, Swift, Spatial Graph Contrastive Learning. In Forty-first International Conference on Machine Learning.
[37] 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. 2022-2032.
[38] 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. 1243-1253.
[39] Yanling Wang, Jing Zhang, Haoyang Li, Yuxiao Dong, Hongzhi Yin, Cuiping Li, and Hong Chen. 2022. ClusterSCL: Cluster-Aware Supervised Contrastive Learning on Graphs. In Proceedings of the ACM Web Conference 2022. 1611-162)
[40] 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. 6861-6877
[41] 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 Annual Conference on Neural Information Processing Systems, Vol. 35. 27387-27401.
[42] Qitian WU, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. 2023. Simplifying and empowering transformers for large-grape graph representations. In Proceedings of the Annual Conference on Neural Information Processing Systems.
12

---

[43] Siyue Xie, Da Sun Handason Tam, and Wing Cheong Lau. 2022. CoCoS: Enhancing Semi- supervised Learning on Graphs with Unlabeled Data via Contrastive Context Sharing. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence. 4272-4280.
[44] 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.
[45] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Liu. 2021. Do Transformers Really Perform Badly for Graph Representation. In Proceedings of the Annual Conference on Neural Information Processing Systems, Vol. 34. 28877-28888.
[46] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. 2020. Graph Contrastive Learning with Augmentations. In Proceedings of the Annual Conference on Neural Information Processing Systems.
[47] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. 2020. Big Bird: Transformers for Longer Sequences. In Proceedings of the Annual Conference Neural Information Processing Systems.
[48] Chun-Yo Chun-Yang Zhang, Wu-Peng Fang, Hai-Chun Cai, C. L. Philip Chen, and Yue-Na Lin. 2024. Sparse Graph Transformer With Contrastive Learning. IEEE Trans. Comput. Soc. Syst. 11, 1 (2024), 892-904.
[49] Yifci Zhang, Hao Zhu, Zixing Song. Piotr Koniusz, and Irwin King. 2022. COSTA: Covariance- Preserving Feature Augmentation for Graph Contrastive Learning. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2524 2534.
[50] 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, Vol. 35. 21171-21183.
[51] Han Zhao, Xu Yang, Kun Wei, Cheng Deng, and Dacheng Tao. 2024. Unsupervised Graph Transformer With Augmentation-Fret Contrastive Learning. IEEE Transactions on Knowledge and Data Engineering (2024).
[52] 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 1:Xiv:2110.1. 3099 (2021).
[53] Yangfu Zhu, Linmei Hu, Xinkai Ge, Wanrong Peng, and Bin Wu. 2022. Contrastive Graph Transformer Network for Personality Detection. In Proceedings of the Thirly-Fine International Joint Conference on Artificial Intelligence. 4559-4565
[54] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2020. Deep Graph Contrastive Representation Learning. CoRR abs/2006.041 04131 (2020).
13

---

A Detailed Experimental Settings
Here, we introduce the detailed information about experimental settings.
A.1 Datasets
In this paper, adopt cight datasets from diverse domains, including homophily and heterophily graphs. The statistics of datasets are summarized Table
Citation networks. ACM, Corafull and UA12010 are constructed from citation networks where nodes represent research papers and edges represent the relations between papers (e.g., having common authors citation relation).
Co-purchase networks. Photo and Computer extracted from the Amazon purchase network where nodes represent goods and edges represent that two goods appear in a same shopping list.
Social networks. BlogCatalog and Flickr are generated from social platforms BlogCatalog and Flickr, respectively. Nodes represent users and edges represent social relationships between users.
Wikipedia. Romanempire is extracted from English Wikipedia where nodes represent words in the text and edges represent that two words connected the dependency tree of the sentence.
ACM, UA12010, BlogCatalog and Flickr can downloaded from Corafull, Photo and Computer be downloaded from 2. Romanempire the principal components analysis (PCA) to reduce the raw features into 256-dimension vectors on Corafull, BlogCatalog, UA12010 and Flickr since the features of these datasets sparse which waste computing resources.
be downloaded from 3. In practice, first apply
Table 2: Statisties on datasets, ranked by the homophily level from high to low.
Dataset
# nodes
# edges
# features
labels
H +
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
Corafull
19,793
126,842
8,710
70
0.57
BlogCatalog
5,196
171,743
8,189
0.40
UA12010
3,067
28,311
4,973
19
0.36
Flickr
7,575
239,738
12,047
0.24
Romanempire
22,662
32,927
300
18
0.05
A.2 Parameter Configuration
Referring to the official implementations, we perform hyper-paramen tuning of baselines on each dataset. We adopt the grid search strategy to determine the optimal parameters. Specifically, We try learning rate {0.001, 0.005, 0.01), dropout {0.3, 0.5, 0.7). dimension of hidden represen- tations in {128, 512}. For GCFormer, we try and пı in (3.5, 7). a in (0.1..... 0.9). B in (0.05, O, 0.5, 1}. We implement all codes based on Python 3.8, Pytorch 1.11, and CUDA 11.0. All experiments are conducted on a Linux server with one Intel Xeon(R) Sliver 4210, 256G RAM and one RTX TITAN.
14

---

Table 3: Comparison of all models in terms of mean accuracy
stdev (%).
Dataser
Photo
ACM
Comuter
Corafull
BlogCatalog
UA12010
Flickr
Romanempine
(())
0.83
0.82
0.78
0.57
0.40
0.36
0.24
0.05
ClusterSCL
93.98
93.27
88. uss7
62.32
84.62
74.37
83.84=04
67.37
CoCoS
g3.73
93.24
89.66
64. 64.25 39.66:um
87.56gua
75.89
83.43
66,28
NCLA
94.21 jnzs
93.46 1024
89. jus
62. 12379
86.69 jus
76.28 Lus
84.06
71.89
GCFormer
95.65
94.32=m4
92.09
69. 69.53
96.03=044
77.57 =0.5
87,90=04s
75.38
Table 4: Performance of different GraphGPS's implementations." "T" and "P" indicate the original Transformer and Performer. "L", "R" and "D" indicate the Laplacian positional encoding, RWSE structural encoding and degree-based encoding. "OOM" indicates the out-of-memory issue.
Dataset
Photo
ACM
Comuter
Corafull
BlogCatalog
UA12010
Flickr
Romanempire
(g)
0.83
0.82
0.78
0.57
0.40
0.36
0.24
0.05
GCN+T+L
93.79
93.12
OOM
OOM
84.62
74.37
83.84
OOM
GCN+T+R
93.81
93.26
OOM
OOM
84.62
74.37
83.84
OOM
GCN+T+D
92.95
92.84
OOM
OOM
84.62
74.37
83.84
0OM
GCN+P+L
93.74
93.23
89.21
61.27
94.21
75.44
83.54
68.29
GCN+P+R
93.62
93.31
89.18
62.08
94.35
75.14
82.72
67.52
GCN+P+D
92.38
92.43
88.06
59.86
92.75
70.16
64.56
GCFomeer
95.65
94.32
92.09
69.53
96.03
77.57
87.90
75,38
B Performance Comparison with GSL-based Approaches
Here, conduct additional experiments validate the effectiveness of GCFormer on node classi- fication, compared with representative graph contrastive learning based methods. Specifically, we select three approaches, CluterSCL [39]. CoCoS [43] and NCLA [31] for performance comparison. We adopt their official implementations and turn hyper- hyper-parameten parameters accordingly on each dataset. The results shown Table We can obscrve that GCFormer outperforms representative GCL-based approaches on all datasets, demonstrating its superiority in node classification.
C Detailed results of GraphGPS
Here, we provide the detailed results of different implementations of GraphGPS. We adopt this resource code for experiments. The results are shown in Table 4. The results demonstrate that GCFormer outperforms GraphGPS on all datasets, highlighting the effectiveness of GCFormer in comparison representative graph Transformers in the task of node classification.
http:///gtthib.coo//uuimmmllllle graphoonnnnnnonnnnooooeo transformers transfrssee
15

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have claimed that this paper focuses on developing a new graph Trans- former for the node classification task in the abstract and introduction.
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.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed in the conclusion that the limitation of the proposed method is the unified sampling strategy for diverse graphs, making the performance sensitive to the sampling size of node tokens.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "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 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 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-text 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 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, 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 Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer:
[NA]
Justification:
There are no theoretical results in this paper.
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 in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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 be properly referenced.
4. Experimental Result Reproducibility
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)?
Question:
Answer: [Yes]
Justification: In the experiment section and appendix, we have provided the detailed experi- mental settings for results reproducing.
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 are provided or not.
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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require 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 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 dataset or 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 possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
17

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided open access to the datasets and detailed experimental settings for reproducing results in the appendix. The code will be released after the paper has been accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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 to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //wips.c... wwt.cc/cccpppcpuiiaeeeee gwwd//////////gg /Coaaae//odSSSbbaaaaa
onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
proposed method and baselines. If only subset of experiments 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 in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: 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 to understand the results?
Answer: [Yes]
Justification: We have provided the detailed experimental settings in the experiment section and appendix.
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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or 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; Following previous studies, we use the average accuracy and standard deviation to evaluate the model performance in the node classification task.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are 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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one 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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In the appendix, we have provided detailed information on hardware and software environments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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.
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 NeurIPS Code of Ethics https: /tturr////e/.../eeeeee cc cctppblcc//eeeeeeccceecceeceeeee cttpci//ehhhccheeeeeeenleemee
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: Our paper is conducted with the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in 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: This paper focuses on foundational research of graph representation learning, which does not involve societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
19

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment 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 tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional 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 to 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 describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
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 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 encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or 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?
Answer: [Yes]
Justification: We the public datasets for experiments in this paper and have cited the original paper that produced the dataset.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a 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.
20

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are 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 encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This 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 was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper focuses graph representation learning, which 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.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS 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 to 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:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending 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.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
22


Reviews:
[{"review_id": "rzzbbeqgtU", "reviewer": "Reviewer_rUu7", "summary": "This paper proposes a token sequence-based graph transformer method named Graph Contrastive Transformer (GCFormer). They first sample top-$k$ similarity nodes as positive token sequence and regard the rest as negative token sequence. Then, they use transformer to obtain the positive and negative representations and subtract negative representation from positive representation to get the node representation. Finally, the combination of contrastive loss and cross entropy loss is taken to optimize the model.", "questions": "- In the ablation study shown in Figure 4, GCNFormer-N scenario can achieve better performance than GCNFormer-C in some cases, which shows the proposed negative token sequence might harm the model performance. But introducing contrastive loss can remedy this problem. Could the authors provide some explanation? Have the authors tried using CE loss without negative samples version + CL loss?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The overall paper is clear and easy to understand. The introduction of proposed method and discussion on experiment is detailed.\n- The idea of introducing negative samples to graph transformer seems promising.", "weaknesses": "- The method is not new to the community and the intuition behind getting node representation by subtracting negative embedding from positive embedding is not clear.\n- Experimental result is not solid enough. Graph contrastive learning methods should be included as baselines. Figure 2 does not provide insightful information regarding the choose of $p_k$ and $n_k$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for providing valuable feedback and comments on our paper. Following are our detailed responses to your questions.\n>**Q1.** The method is not new to the community and the intuition behind getting node representation by subtracting negative embedding from positive embedding is not clear.\n\n**A1.** Previous research has focused on integrating contrastive learning into GNNs to improve performance in supervised node classification tasks. However, GNNs and graph Transformers represent distinct methodologies. As discussed in Section 2.2, strategies effective in GNNs may not directly apply to graph Transformers. This paper addresses the gap in leveraging contrastive learning for graph Transformers by proposing GCFormer, which introduces a novel hybrid token generator to produce both positive and negative tokens for each target node. Building on this capability, we formulate a contrastive learning-based loss function that fully exploits the information learned from both positive and negative tokens, thereby enhancing the overall model performance.\n\nInspired by the recent study FAGCN [1], which leverages positive and negative weights to aggregate low-frequency and high-frequency information, respectively, GCFormer employs a subtraction operation to mimic the signed aggregation operation. This enables the comprehensive learning of node representations from different types of tokens as discussed in Line 208-213.\nWe will add the above discussions to the revised version to highlight the novelty and motivation of the proposed GCFormer.\n\n>**Q2.** Experimental result is not solid enough. Graph contrastive learning methods should be included as baselines. Figure 2 does not provide insightful information regarding the choice of $p_k$ and $n_k$.\n\n**A2.** Thank you for your helpful suggestions. To address your concerns, we select three recent graph contrastive learning-based approaches for supervised node classification as baselines, CluterSCL[2], CoCoS[3], and NCLA[4]. The results are reported in the **common response** due to the space limitation.\nThe experimental results indicate the superiority of GCFormer for node classification, compared to representative graph contrastive learning-based methods. \n\nFigure 2 illustrates the impact of the sampling sizes $n_k$​ and $p_k$​ on the model's accuracy across various datasets. High accuracy is denoted by blue regions, while low accuracy is indicated by red regions. For $n_k$​, we observe that for most datasets (except ACM), the blue regions typically appear in the upper half of the grid along the y-axis, suggesting that a larger value of $n_k$ tends to lead to higher accuracy. For $p_k$​, though the distribution of the blue areas is less consistent, over half of datasets require a small value of $p_k$ to achieve the satisfied performance. These observations suggest that the combination of a large value of $n_k$​ and a small value of $p_k$ could be effective for achieving competitive performance.\n\nWe will add the above results and discussions to the revised version to strengthen the experiment section.\n\n\n>**Q3.** In the ablation study shown in Figure 4, GCNFormer-N scenario can achieve better performance than GCNFormer-C in some cases, which shows the proposed negative token sequence might harm the model performance. But introducing contrastive loss can remedy this problem. Could the authors provide some explanation? Have the authors tried using CE loss without negative samples version + CL loss?\n\n**A3.** Thank you for your insightful comments. GCFormer-C only encourages the target node's representation to be distinct from the virtual node's representation extracted from negative tokens, with no strong constraints imposed on the relationships among the representations of the target node, positive tokens, and negative tokens. In contrast, the contrastive loss function, as described in Equation (13), explicitly narrows the distance between the target node's representation and the central representation of positive tokens while simultaneously enlarging the distance between the target node's representation and the representations of negative tokens. This loss function enhances the model's ability to learn more distinguished representations of the target node, positive tokens, and negative tokens, which in turn further improves the overall model performance.\n\nTo address the concerns raised and provide a more comprehensive evaluation, we introduce two additional variants of GCFormer: GCFormer-NN and GCFormer-NL. GCFormer-NN retains the use of Transformer layers for learning negative token representations but only employs these representations in the contrastive learning loss (ignoring them in Equation 11). GCFormer-NL, conversely, directly uses the representations of negative tokens for contrastive learning without passing them through Transformer layers. The results of these variants are also summarized in the common response.\n\nWe can observe that utilizing the representations of negative tokens learned by Tranformer for contrastive learning can consistently improve the model performance. Moreover, GCFormer beats GCFormer-NE, indicating that combining Eq. (11) with the contrastive learning loss can fully extract the information of negative tokens to learn distinguished node representations.\nWe will add the above results and discussions to the revised version. Thank you.\n\n\n[1] Deyu Bo, et al. Beyond Low-Frequency Information in Graph Convolutional Networks. AAAI 2021.\n\n[2] Yanling Wang, et al. ClusterSCL: Cluster-aware Supervised Contrastive Learning on Graphs. The Web Conference 2022.\n\n[3] Siyue Xie, et al. CoCoS: Enhancing Semi-Supervised Learning on Graphs with Unlabeled Data via Contrastive Context Sharing. AAAI 2022.\n\n[4] Xiao Shen, et al. Neighbor Contrastive Learning on Learnable Graph Augmentation. AAAI 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l0LDsqvMF5", "reviewer": "Reviewer_9KjY", "summary": "This paper proposes a new graph Transformers for node classification. Different from previous graph Transformers that only select nodes with high-similarity to construct the token sequences, this paper proposes GCFormer, that considers both high-similairity and low-similarity nodes as tokens. Moreover, GCFormer introduces the contrastive learning to further enhance the quality of learned node representations. \nOverall, the idea that introduces negative token sequences and leverages contrastive learning to enhance the performance of tokenized graph Transformers is interesting.", "questions": "1. I suggest authors add recent representative graph Transformers, such as VCR-Graphormer [1], as baselines to make the experimental results more convicing.\n2. How do you utilize the virtual nodes to learn representations of negative token sequences? Do you assign learnable features to each virtual nodes, (like CLS tokens)?\n3. Moreover, how do you construct the token sequences (both positive and negative)? It seems that you set the target node and the virtual node as the first items of the positive token sequences and negative token sequences, respectively.   I suggest the authors provide more detailed information about the construction of token sequences.\n\n[1] Fu D, Hua Z, Xie Y, et al. VCR-graphormer: A mini-batch graph transformer via virtual connections. ICLR 2024.", "limitations": "The authors have discussed the limitations of the proposed method.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is written and easy to follow.\n2. This paper proposes a new architecture of graph Transformer.\n3. The empirical performance of GCFormer is outstanding.", "weaknesses": "1. Some representative baselines are missing.\n2. More details of GCFormer are required.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the positive evaluation and insightful questions that help us improve this work. We provide the following detailed responses to your questions.\n\n> **Q1.** I suggest authors add recent representative graph Transformers, such as VCR-Graphormer [1], as baselines to make the experimental results more convicing.\n\n**A1.** Per your suggestion, we conduct additional experiments to evaluate the performance of VCR-Graphormer [1] via the official implementation on GitHub. The results are as follows:\n|                | Pho.  | ACM   | Com.  | Cor.  | Blo.  | UAI.  | Fli.  | Rom.  |\n|----------------|-------|-------|-------|-------|-------|-------|-------|-------|\n| VCR-Graphormer | 95.13 | 93.24 | 90.14 | 68.96 | 93.92 | 75.78 | 86.23 | 74.76 |\n| GCFormer       | 95.65 | 94.32 | 92.09 | 69.53 | 96.03 | 77.57 | 87.90 | 75.38 |\n\nWe can observe that GCFormer consistently surpasses VCR-Graphormer on all datasets, which demonstrates the superiority of GCFormer compared to recent tokenized graph Transformers. \nWe will add the above results and discussions to the revised version.\n\n> **Q2.** How do you utilize the virtual nodes to learn representations of negative token sequences? Do you assign learnable features to each virtual nodes, (like CLS tokens)?\n\n**A2.** Thank you for your attention on this point. Each virtual node is associated with a learnable feature vector. Through the Transformer layer, these virtual nodes can preserve the information of tokens in negative token sequences via the self-attention mechanism. This usage of virtual nodes is analogous to the use of CLS tokens in natural language processing, where the CLS token aggregates information from the entire sequence to perform tasks such as text classification. In the context of GCFormer, the virtual nodes serve a similar purpose, aggregating and preserving the information from the negative tokens, which is then used to enhance the contrastive learning process.\nWe will reorganize the related sentences for a clear description in the revised version. \n\n> **Q3.** Moreover, how do you construct the token sequences (both positive and negative)? It seems that you set the target node and the virtual node as the first items of the positive token sequences and negative token sequences, respectively. I suggest the authors provide more detailed information about the construction of token sequences.\n\n**A3.** Thank you for your helpful suggestion. In practice, we utilize the target node and it's positive sampling nodes to construct the positive token sequence where the target node is the first item in the sequence. Similarly, we use the virtual node and the target node's negative sampling nodes to construct the negative token sequence where the virtual node is the first item. By placing the target node at the beginning of the positive sequence and the virtual node at the beginning of the negative sequence, we ensure that the first item in each sequence captures the learned information from the corresponding input sequence. This allows us to leverage the first item of each sequence effectively for downstream tasks.\nWe will update the description of the construction of positive and negative token sequences in the revised version.\n\n[1] Dongqi Fu, et al. VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections. ICLR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J94sN2Z6Cs", "reviewer": "Reviewer_pga6", "summary": "In this work, the authors present GCFormer, a new graph transformer (GT) architecture for improved node classification on homophilic and heterophilic graphs. To this end, the authors propose to sample a fixed number of both positive and negative tokens for each node $v$ in the graph and then restrict the attention computation for $v$ to only the positive and negative tokens. The sampling procedure is based on similarity scores that are computed both based on node attributes as well as topological information based on powers of the normalized adjacency matrix. The authors further introduce a contrastive loss, added to the supervised cross-entropy loss, with the goal of promoting  the representation of a given node to be close to the representation of the positive samples and to be far from the representation of the negative samples. GCFormer is evaluated on a range of node classification tasks, with varying levels of homophily.", "questions": "- Is the empirical setting on Roman-Empire derived from Platanov et al. (https://arxiv.org/abs/2302.11640) and if not, what changes to the empirical setting did the authors make? Are the results of GCFormer comparable to the results in Müller et al. (https://arxiv.org/abs/2302.04181)?\n- Are the $V^{a,p}_i$ in L180 and $N^{a,p}_i$ in L188 the same? I suspect this to be a typo but I wanted to make sure I did not misunderstand how the authors construct the positive and negative token sequences from the sampled positive and negative similarity scores.", "limitations": "The limitations of the work were adequately addressed.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The strengths of this work lie in the depth of the experimental study:\n\n- The authors select eight datasets with a wide range of homophily levels.\n- The authors tune all baselines with the same hyper-parameter ranges, enabling a fair comparison to prior works.\n- The authors present an ablation study, indicating the effectiveness of their proposed approach. Specifically, it becomes apparent that the idea of learning representations close to positive tokens and far away from negative tokens is effective (which, to me, is the central innovation in this work).", "weaknesses": "The main weakness of this paper is its poor disambiguation from prior work and the resulting weakened motivation of the proposed model. Concretely, it becomes evident in L51-57, as well as the related work, that the authors base their work mainly on GTs that, for each node $v$, perform attention over a reduced set of nodes similar to $v$ (based on node attributes and topological information) — I will refer to this class of models as *positive-sampling GTs*. The authors cite the following works:\n\n- ANS-GT (https://arxiv.org/abs/2210.03930)\n- Gophormer (https://arxiv.org/abs/2110.13094)\n- VCR-Graphormer (https://arxiv.org/abs/2403.16030)\n- NAGphormer (https://arxiv.org/abs/2305.12677)\n\nFirst I want to note that out of these, the authors *only compare to ANS-GT and NAGphormer*. The other transformer baselines in the experimental section are\n\n- SGFormer (https://arxiv.org/abs/2306.10759)\n- Specformer (https://arxiv.org/abs/2303.01028)\n\nnone of which fall into the category of positive-sampling GTs and instead perform attention between all node pairs. In addition, other GTs that perform attention between all node pairs are missing in the experimental study, most notably GraphGPS with linear attention (https://arxiv.org/abs/2205.12454). Specifically, the authors claim that GraphGPS has limited modeling capacity, yet the authors do not compare their approach to GraphGPS, neither do they present any other evidence supporting this claim. Instead, the authors argue that the design of GraphGPS \"could restrict the modeling capacity of Transformer and further limit the model performance” (L93-94). Indeed, GraphGPS with Performer attention appears to show much better performance on Roman-Empire than GCFormer and any of the baselines in this work; see Müller et al. (https://arxiv.org/abs/2302.04181) for GraphGPS+Performer on Roman-Empire, and see my question below on whether these results are directly comparable.\n\n*This is what I mean with poor disambiguation from prior work*. It is evident that the authors want to improve the state-of-the-art of positive-sampling GTs but the authors make claims throughout the paper that are referring to graph transformers in general. For example, in L61-63: “[…] existing graph Transformers can not comprehensively utilize both similar and dissimilar nodes to learn the representation of the target node, inevitably limiting the model performance for node classification”. Without additional evidence, this statement only holds for positive-sampling GTs. It is not obvious that the same holds for GTs performing attention between all node pairs, such as SGFormer, Specformer or GraphGPS with linear attention.\n\nAs a result, the work is not well motivated. While the motivation of GCFormer with respect to positive-sampling GTs is given, it is not demonstrated or argued sufficiently what the short-comings of models such as SGFormer, Specformer or GraphGPS with linear attention are in the first place and why GCFormer (or any of the positive-sampling GTs that GCFormer improves over) offers a conceptual improvement.\n\nThe only remedy to this are the empirical results, where GCFormer comes out on top compared to the positive-sampling GTs, SGFormer and Specformer. However, on five out of eight datasets, the second best performance is *within standard deviation* of GCFormer, indicating small but not convincing improvements over existing methods. Most notably, at the cost of less generality, since GCFormer does not compute attention between all node pairs.\n\nI expect the authors to clearly motivate their approach and demonstrate the benefits GCFormer offers. In addition, I hope that the authors can provide supporting evidence to the claims made about GraphGPS, for example by including GraphGPS with linear attention as a baseline in the experimental section or by arguing more specifically about its shortcomings in the context of node classification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments and valuable questions. We provide details to clarify your major concerns.\n\n>**Q1.** I expect the authors to clearly motivate their approach and demonstrate the benefits GCFormer offers. In addition, I hope that the authors can provide supporting evidence to the claims made about GraphGPS, for example by including GraphGPS with linear attention as a baseline in the experimental section or by arguing more specifically about its shortcomings in the context of node classification.\n\n**A1.** Thank you for your detailed and insightful comments. Firstly, we discuss the potential limitations of linear attention-based graph Transformers in the context of node classification tasks. These approaches require performing the attention calculation on all node pairs, which can lead to what is known as the \"over-globalizing\" problem. A recent study [1] (not included in the original version as it was released in May) provides both empirical evidence and theoretical analysis to show that calculating attention scores for all nodes can cause the model to overly rely on global information, which can negatively affect the model's performance in node classification tasks. In contrast, tokenized graph Transformers, such as GCFormer, only calculate attention scores between tokens within the token sequence, naturally avoiding the over-globalizing issue.\n\nSecondly, the claim that \"existing graph Transformers cannot comprehensively utilize both similar and dissimilar nodes to learn the representation of the target node\" is supported by the following observations. Existing tokenized graph Transformers typically ignore dissimilar nodes when learning node representations. For linear attention-based approaches, such as GraphGPS and SGFormer, the calculation of the self-attention mechanism can be seen as conducting a single aggregation operation on a fully connected graph. Each node receives information from all other nodes, including both similar and dissimilar ones. However, the aggregation weights produced by the self-attention mechanism are always positive. Utilizing positive weights to aggregate information from dissimilar nodes can be viewed as a smoothing operation [2]. This situation suggests that linear attention-based approaches are inefficient in utilizing both similar and dissimilar nodes to learn the representation of the target node, potentially leading to suboptimal performance.\n\nThirdly, to further enhance the performance of graph Transformers for node classification, we propose GCFormer, which is built upon the tokenized graph Transformer architecture. The main contribution of GCFormer lies in developing a new architecture for graph Transformers that enables the model to comprehensively leverage various tokens containing both similar and dissimilar nodes to learn node representations. By introducing negative tokens, GCFormer is the first attempt to explicitly incorporate dissimilar nodes into the learning process, thereby enriching the representations learned by graph Transformers. This innovation allows GCFormer to effectively distinguish between similar and dissimilar nodes, leading to improved performance in node classification tasks. \n\nFinally, we evaluate the performance of GraphGPS on our datasets. We utilize the implementation of GraphGPS provided by [3]. Note that the authors do not provide a ready-to-use script to reproduce the results on five new datasets, including Roman-empire. Therefore, we use the scripts for node classification on small graphs provided by [3] to search for the optimal combination of parameters. The results are summarized in the **common response** due to the space limitation.\nBased on the existing results, we can observe that GCFormer outperforms GraphGPS in node classification tasks. \nWe will add the above discussions and results to the revised version. Thank you.\n\n>**Q2.** Is the empirical setting on Roman-Empire derived from Platanov et al. and if not, what changes to the empirical setting did the authors make? Are the results of GCFormer comparable to the results in Müller et al.?\n\n**A2.** No, we resplit all datasets via the same random seed in our experimental environment to enable a fair comparison. And we cannot reproduce the results of GraphGPS reported in Table 4 [3] since the authors do not make the code of this part available in their official repertory. To address your concerns, we evaluate the performance of GCFormer on Question, which is the largest one of five new datasets. The results are reported in the following table:\n|                          | Questions |\n|--------------------------|-----------|\n| GCN+T+LPE | 77.85     |\n| GCN+T+RWSE  | 76.45     |\n| GCN+T+DEG  | 74.24     |\n| GCN+P+LPE | 76.71     |\n| GCN+P+RWSE  | 77.14     |\n| GCN+P+DEG   | 76.51     |\n| GCFormer                 | 80.87     |\n\nWe can observe that GCFormer outperforms all implementations of GPS on the largest dataset, demonstrating the effectiveness of GCFormer in node classification.\nWe will add the above results and discussions to the revised version.\n\n>**Q3.** Questions about $V_{i}^{a,p}$ and $N^{a,p}_{i}$.\n\n**A3.** Thank you for pointing out this. They are the same. We will fix these typos in the revised version. \n\n[1] Yujie Xing, et al. Less is More: on the Over-Globalizing Problem in Graph Transformers. ICML 2024.\n\n[2] Deyu Bo, et al. Beyond Low-Frequency Information in Graph Convolutional Networks. AAAI 2021.\n\n[3] Luis Müller, et al. Attending to Graph Transformers. TMLR, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Here, we present the experimental results to address the concerns of **Reviewer rUu7** and **Reviewer pga6**.

### **Reviewer rUu7** 
we first report the performance of GCFormer and three representative GCL-based methods for supervised node classification. The results are as follows:
|            | Pho.  | ACM   | Com.  | Cor.  | Blo.  | UAI.  | Fli.  | Rom.  |
|------------|-------|-------|-------|-------|-------|-------|-------|-------|
| ClusterSCL | 93.98 | 93.27 | 88.74 | 62.32 | 84.62 | 74.37 | 83.84 | 67.37 |
| CoCoS      | 93.73 | 93.24 | 89.66 | 64.25 | 87.56 | 75.89 | 83.43 | 66.28 |
| NCLA       | 94.21 | 93.46 | 89.52 | 62.79 | 86.69 | 76.28 | 84.06 | 71.89 |
| GCFormer   | 95.65 | 94.32 | 92.09 | 69.53 | 96.03 | 77.57 | 87.90 | 75.38 |

We can observe that GCFormer outperforms representative GCL-based approaches on all datasets, demonstrating its superiority in node classification.



Then, the results of GCFormer  and its four variants are as follows:
|             | Pho.  | ACM   | Com.  | Cor.  | Blo.  | UAI.  | Fli.  | Rom.  |
|-------------|-------|-------|-------|-------|-------|-------|-------|-------|
| GCFormer-N  | 95.26 | 93.79 | 91.21 | 69.26 | 95.27 | 76.93 | 84.21 | 74.86 |
| GCFormer-C  | 95.31 | 93.42 | 91.44 | 69.17 | 95.62 | 75.13 | 87.14 | 75.12 |
| GCFormer-NE | 95.42 | 93.82 | 91.64 | 69.44 | 95.82 | 77.14 | 87.37 | 75.13 |
| GCFormer-NN | 95.23 | 93.21 | 91.30 | 69.32 | 95.66 | 76.22 | 87.23 | 74.96 |
| GCFormer    | 95.65 | 94.32 | 92.09 | 69.53 | 96.03 | 77.57 | 87.90 | 75.38 |

The results demonstrate that GCFormer-NE outperforms GCFormer-NN on all datasets, indicating that leveraging the Transformer to learn representations of negative tokens can effectively enhance the benefits of introducing contrastive learning. Furthermore, GCFormer surpasses GCFormer-NE, suggesting that comprehensively utilizing the representations of negative tokens through the signed aggregation operation and contrastive learning can further augment the model's ability to learn more discriminative node representations.



### **Reviewer pga6** 
We report the performance of GraphGPS implemented by different model combinations. The results are as follows:
|            | Pho.  | ACM   | Com.  | Cor.  | Blo.  | UAI.  | Fli.  | Rom.  |
|------------|-------|-------|-------|-------|-------|-------|-------|-------|
| GCN+Transformer+LPE  | 93.79 | 93.12 | OOM   | OOM   | 94.14 | 74.06 | 83.61 | OOM   |
| GCN+Transformer+RWSE | 93.81 | 93.26 | OOM   | OOM   | 94.25 | 75.39 | 82.38 | OOM   |
| GCN+Transformer+DEG  | 92.95 | 92.84 | OOM   | OOM   | 92.51 | 69.81 | 81.54 | OOM   |
| GCN+Performer+LPE  | 93.74 | 93.23 | 89.21 | 61.27 | 94.21 | 75.44 | 83.54 | 68.29 |
| GCN+Performer+RWSE | 93.62 | 93.31 | 89.18 | 62.08 | 94.35 | 75.14 | 82.72 | 67.52 |
| GCN+Performer+DEG  | 92.38 | 92.43 | 88.06 | 59.86 | 92.75 | 70.16 | 80.88 | 64.56 |
| GCFormer   | 95.65 | 94.32 | 92.09 | 69.53 | 96.03 | 77.57 | 87.90  | 75.38 |

The results demonstrate that GCFormer outperforms GraphGPS on all datasets, highlighting the effectiveness of GCFormer in comparison to representative graph Transformers in the task of node classification.


**We will incorporate all the above results and discussions in the revised version, and we appreciate the reviewers' valuable suggestions.**

Meta-review: This paper proposes a new graph Transformers for node classification, named Graph Contrastive Transformer (GCFormer). Different from previous graph Transformers that only select nodes with high-similarity to construct the token sequences, GCFormer considers both high-similairity and low-similarity nodes as tokens, and introduces contrastive learning to enhance the quality of learned node representations. The work provides deep empirical studies, showing strong results on eight datasets with a wide range of homophily levels and rich ablation studies. It’d be beneficial to include more comparison with representative baselines, such as VCR-Graphormers and other Graph contrastive learning methods.
Decision: Accept (poster)