Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers

Thank you for the detailed comments and valuable questions. We provide details to clarify your major concerns.

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.

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.

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

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

Finally, 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. Based on the existing results, we can observe that GCFormer outperforms GraphGPS in node classification tasks. We will add the above discussions and results to the revised version. Thank you.

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

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:

We can observe that GCFormer outperforms all implementations of GPS on the largest dataset, demonstrating the effectiveness of GCFormer in node classification. We will add the above results and discussions to the revised version.

Q3. Questions about $V_{i}^{a,p}$ and $N^{a,p}_{i}$.

A3. Thank you for pointing out this. They are the same. We will fix these typos in the revised version.

[1] Yujie Xing, et al. Less is More: on the Over-Globalizing Problem in Graph Transformers. ICML 2024.

[2] Deyu Bo, et al. Beyond Low-Frequency Information in Graph Convolutional Networks. AAAI 2021.

[3] Luis Müller, et al. Attending to Graph Transformers. TMLR, 2024.

Many thanks for the positive evaluation and insightful questions that help us improve this work. We provide the following detailed responses to your questions.

Q1. I suggest authors add recent representative graph Transformers, such as VCR-Graphormer [1], as baselines to make the experimental results more convicing.

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:

We can observe that GCFormer consistently surpasses VCR-Graphormer on all datasets, which demonstrates the superiority of GCFormer compared to recent tokenized graph Transformers. We will add the above results and discussions to the revised version.

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)?

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. We will reorganize the related sentences for a clear description in the revised version.

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.

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. We will update the description of the construction of positive and negative token sequences in the revised version.

[1] Dongqi Fu, et al. VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections. ICLR 2024.

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

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.

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.

Inspired 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. We will add the above discussions to the revised version to highlight the novelty and motivation of the proposed GCFormer.

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

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. The experimental results indicate the superiority of GCFormer for node classification, compared to representative graph contrastive learning-based methods.

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

We will add the above results and discussions to the revised version to strengthen the experiment section.

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?

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.

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

We 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. We will add the above results and discussions to the revised version. Thank you.

[1] Deyu Bo, et al. Beyond Low-Frequency Information in Graph Convolutional Networks. AAAI 2021.

[2] Yanling Wang, et al. ClusterSCL: Cluster-aware Supervised Contrastive Learning on Graphs. The Web Conference 2022.

[3] Siyue Xie, et al. CoCoS: Enhancing Semi-Supervised Learning on Graphs with Unlabeled Data via Contrastive Context Sharing. AAAI 2022.

[4] Xiao Shen, et al. Neighbor Contrastive Learning on Learnable Graph Augmentation. AAAI 2023.