CaliGCL: Calibrated Graph Contrastive Learning via Partitioned Similarity and Consistency Discrimination

W1: The normalized adjacency matrix $\tilde{**A**}$ is calculated as $\tilde{**A**} = \hat{**D**}^{-1/2} \hat{**A**} \hat{**D**}^{-1/2}$, and $\hat{**A**}=**A**+**I**_N$, $\hat{**D**}$ is a diagonal matrix, and its diagonal element is ${\hat{**D**}}\_{ii}={\sum\_j} {\hat{**A**}\_{ij}}$. This will be clarified in the refined version.

W2: “all scenarios” mean all the possible combinations of feature partitions, namely all positively-aligned partitions, all negatively-aligned partitions, and mix of both positively-aligned and negatively-aligned partitions. Lines 167-168 mean that under all possible combinations of feature partitions, exponential partitioned similarity yields similarity greater than or equal to global exponential inner product, where Lines 162-166 only give a simple example to clarify that the proposed exponential partitioned similarity has the ability to amplify the positively-aligned partitions while suppressing the negatively-aligned partitions in the mixed scenario, which cannot generalize to the scenarios where the representation vectors have only positively-aligned or negatively-aligned partitions. And we stress the “all scenarios” to illustrate that through Theorem 2, the proposed exponential partitioned similarity can not only amplify the positively-aligned partitions and suppress the negatively-aligned partitions in the mixed scenario, but can be generalized to common scenarios.

W3: Feature shuffling ensures interactions across dimensions and avoids amplifying or suppressing fixed partitions during the training process. To illustrate the function of “Shuffling”, we provide the results of the model with and without shuffling in Tables 1-2. From the results, we could find that the model without shuffling has inferior performance when compared with that with shuffling. It is because that without shuffling, only the fixed partitions are amplified or suppressed during the whole training process. In contrast, the shuffling operator benefits the interactions across feature dimensions and ensures the model performance.

Table 1. Model performance without “Shuffling” for node-level datasets.

Table 2. Model performance without “Shuffling” for graph-level datasets.

W4: To provide a comprehensive comparison among the graph models, we first define $N$ as the number of nodes, $d$ as the dimension of the representations, $D$ as the hidden layer dimension of the discriminator, $|\mathcal{E}|$ as the number of edges, as the number of sampling adjacent nodes, $C$ as the number of clusters, $V$ as the number of augmented views, $k$ as the number of sampling negatives, $K$ is the number of partitions, and $T$ as the iteration of K-means algorithm. Based on these symbols, we provide the complexity of the comparative models in Table 3. From the results, we find that our model has $\mathcal{O}{(N^2)}$ complexity and though it is more computationally intensive than the graph generative models, it is comparable with the graph contrastive model, which illustrates the practicability of the proposed model.

Table 3. Complexity comparison between graph models.

W5: It is inappropriate to adopt the loss functions as the legends to cause misunderstandings. In Figure 6, the legend for the blue histogram is the result of the inner product and the legend for the pink histogram is the result of the discriminator. In the refined version, we will replace “General Contrastive Loss” with “Inner Product” and replace “Partitioned Contrastive Loss” with “Discriminator” for clarity.

Q1: We have recorded the losses of alternate training strategies (including losses of both encoder and discriminator) during the fine-tuning process to clarify that the model training gradually converges. Besides, both the losses of the encoder and the discriminator become stable in the training process. Since we are unable to provide Figures in the rebuttal, the loss plots will be included in the refined version.

Q2: Though $K$ amplifies the magnitude of exponential partitioned similarity, it doesn’t cause index flow in practice. When calculating the contrastive loss with the representations, they are always normalized, which means the inner product of a sample pair is limited in $[-1,1]$. Therefore, the training process will cause index flow unless $K$ is very large. However, according to the experiments, we find $K$ is always smaller than five. Additionally, another hyperparameter, namely the temperature coefficient $\tau$, could also adjust $K$ to avoid the index flow problem.

Q3: Though with learnable augmentations, the graph models [1-2] generally optimize the strength of graph augmentations (e.g., the ratio of edge removal), or the combination of adopted augmentation strategies. However, the input data is still modified randomly but with a more appropriate ratio or augmentation combination. Without explicit constraints, they may still destroy meaningful structures or features. In contrast, CaliGCL uses a discriminator to explicitly check semantic consistency between sample pairs and attempts to calibrate the semantics-biased sample pairs to correct the contrastive learning process directly, which further reduces the possibility of semantic shift caused by the random augmentations.

[1]Graph contrastive learning with personalized augmentation, in TKDE 2024.

[2] Adversarial Graph Augmentation to Improve Graph Contrastive Learning, in NeurIPS 2021.

W1: Eq. (6) corresponds to an example where a pair of positive samples $(h_v, h_v')$ has both negatively-aligned and positively-aligned partitions, and the inner product of the sample pair is the sum of the inner products of the partitions, namely

$h_{v_i}^T h_{v_j} = [ h_{v_i}^{(1)}]^T [ h_{v_j}^{(1)}]+[h_{v_i}^{(2)}]^T [h_{v_j}^{(2)}].$

Assume that $h_{v_i}^T h_{v_j} > 0$ and the first partition is negatively-aligned, namely $[h_{v_i}^{(1)}]^T [h_{v_j}^{(1)}] < 0$, it is easy to find that the inner product of the second partition has

$[h_{v_i}^{(2)}]^T [h_{v_j}^{(2)}] > h_{v_i}^T h_{v_j}.$

Therefore, as your comment, without doubling the inner product of partitions, it also holds the following conclusion

$\exp\left( \frac{[ h_{v_i}^{(1)}]^T [h_{v_j}^{(1)}]}{\tau} \right) \to 0, \quad \text{and} \quad \exp\left( \frac{[h_{v_i}^{(2)}]^T [h_{v_j}^{(2)} ]}{\tau} \right) \geq \exp\left( \frac{h_{v_i}^T h_{v_j}}{\tau} \right).$

However, this may not hold for the situation where the sample pairs have only positively-aligned or negatively-aligned partitions. For example, when the sample pair is divided into two positively-aligned partitions, we have

$\exp\left( \frac{[h_{v_i}^{(1)}]^T [h_{v_j}^{(1)}]}{\tau} \right) \leq \exp\left( \frac{h_{v_i}^T h_{v_j}}{\tau} \right), \quad \text{and} \quad \exp\left( \frac{[h_{v_i}^{(2)}]^T[h_{v_j}^{(2)}]}{\tau} \right) \leq \exp\left( \frac{h_{v_i}^T h_{v_j}}{\tau} \right).$

It is difficult to compare the values of the original exponential inner product and the sum of the exponential partitioned similarity for judging which is larger. To amplify the sum of the exponential partitioned similarity and make it larger, we follow Jensen’s inequality to leave the original exponential inner product less than or equal to the sum of the exponential partitioned similarity by multiplying the inner product with the number of blocks, and it corresponds to doubling the inner product in Eq. (6). This operator is necessary to generalize the conclusion to more common situations where the partitions are all positively-aligned or negatively-aligned, and we provide the corresponding proof in Theorem 2. Additionally, for Eq. (6), the double inner product has another merit to further facilitate the negatively-aligned partitions to approach zero more quickly while further amplifying the positively-aligned partitions.

W2: We provide the classification results on IMDB-BINARY (IMDB-B) and REDDIT-BINARY (RDT-B) datasets with the means and standard deviations in Tables 1-2. In the refined version, we will include the shaded regions around the broken line in Figure 3 to indicate standard deviations.

Table 1. Hyperparameter analysis for the temperature coefficient.

Table 2. Hyperparameter analysis for the partition size.

W3: We provide a t-SNE visualization comparing CaliGCL and other baselines to demonstrate the quality of learned representations. From the visualization results, we find the samples of different classes in PiGCL and iGCL are mixed; the boundaries of different classes in GREET, S2GAE, Bandana, and SGRL are ambiguous without margins. In contrast, the boundaries of different classes in CaliGCL are separated with larger margins. Since we are unable to provide the Figures in the rebuttal, the visualization and the analysis will be included in the refined version.

Q1: "Connected positives" refer to nodes that are connected with the anchor node in the topology, and they are the adjacent nodes. Based on the homogeneity principle, these nodes are always considered as positives. The encoder corresponds to the arrows between the input graphs and the feature information, such as feature information $**H**_U$, $**H**_V$, and $**H**\_\mathcal{G}$ in Figure 2. We will supplement the missing details in the refined version.

Q2: We use the Hadamard product to preserve fine-grained dimension-wise interactions between node representations. Though both the concatenation and the Hadamard product can preserve the dimension-wise information, the Hadamard product with dimension-wise multiplication emphasizes that the feature elements of a sample pair are closely correlated in corresponding dimensions, which is suited for relationship (similar or dissimilar) prediction. Besides, the Hadamard product doesn’t extend the feature dimensions when compared with the concatenation operator, which will save half the computation cost on calculating the consistency scores than the concatenation operator.

Q3: The ability of the discriminator to realize the calibrated sample assignments during training mainly contributes to its identification for semantic consistency of sample pairs. To illustrate the identification ability of the discriminator, we have provided some experiment results to show that the discriminator has superior ability to predict semantic consistency of sample pairs, and the results are shown in Figure 6, where the blue histogram corresponds to the inner product and the pink histogram corresponds to the discriminator.

In the experiments, we use the inner product and the discriminator to judge the semantic consistency of sample pairs. Specifically, we assume the sample pairs with positive inner products are positive in the former method, otherwise negative, while the output of the discriminator can naturally give a judgement of semantic consistency of the sample pairs in the latter method. We compare the predictions with the true labels of the sample pairs to obtain the prediction accuracy, and the results are shown in Figure 6, where the ‘w/o aug’ and ‘aug’ represent the results of the prediction accuracy on the original data and the augmented data, respectively. Figure 6 illustrates that the discriminator has superior performance than the inner product on discriminating the semantic consistency of sample pairs under both the ‘w/o aug’ and ‘aug’ conditions, which demonstrates that the discriminator could further help the model to calibrate the contrastive learning process.

Q4: The training for an ideal discriminator always needs numerous positive and negative sample pairs. Since we have no true labels to train the discriminator in an unsupervised setting, we attempt to find the reliable positives and negatives for training the discriminator. In our method, we only pick out the positives from the overlapped samples that are both adjacent and selected with the K-NN algorithm. Based on this strict condition, the positives are more reliable but always very scarce. However, the negative samples are easy to sample, so we can collect much more negative samples than positive samples, which leads to the imbalance problem between the positive and negative sample pairs. This means that though balanced sampling for positives and negatives is more efficient, it is difficult to conduct. To address the inevitable imbalance problem and prevent the encoder from giving consistent predictions as negative pairs, we adopt the balanced softmax loss function instead adjusts the sampling ratio between positives and negatives, offering a more reliable solution to the imbalance problem.

---

We have carefully read your comments and made extensive efforts to understand your concerns, particularly the core issue regarding the definitions of “entropy” and “hardness”.

At the beginning, we think that the concepts of entropy and hardness you mentioned might not be directly applicable to our model, since our motivation is to calibrate biased similarity estimation caused by conflicting feature elements and address semantic inconsistency arising from data augmentations but doesn’t explicitly incorporate entropy-based reweighting or hardness-aware mining in the traditional sense.

However, we also reconsider what deeper concern or theoretical ambiguity might have motivated your comment and why these concepts are brought up. Considering this, we attempt to infer your original intent and the underlying motivation behind your question, and suppose that “entropy” denotes the softmax-like contrastive loss, and “hardness” is the trade-off between a learning signal from hard negatives and the harm due to the correction of false negatives. Guided by this understanding, we provide the following response in hopes that it can address your concerns.

If we misunderstand your question or don't resolve the issues you intend to highlight, we would greatly appreciate any clarification in the discussion phase and try our best to provide a more targeted and clear response.

---

W1 & Q2: We would like to clarify that Eq. 4 does not involve this issue, and we assume that the equation you referred to might be Eq. 5, and our responses are based on Eq. 5.

“Entropy” denotes the softmax-like contrastive loss, such as cross-entropy [1-2]. Given the fact that the contrastive loss is regarded as the cross-entropy, the definition of entropy is obtained by substituting Eq. 5 into Eq. 10 as

$\text{Entropy} = - \log \left( \frac{\sum_k \exp \left( K[h_u^{(k)}]^T h_v^{(k)} \right) / \tau}{\sum_j \sum_k \exp \left( K[h_u^{(k)}]^T h_{v_j}^{(k)} \right) / \tau + \sum_{j \neq i} \sum_k \exp \left( K[h_u^{(k)}]^T h_{u_j}^{(k)} \right) / \tau} \right)$

where $K$ is the number of partitions, $\tau$ is the temperature, $u_i$ and $v_i$ are the $i$-th samples in the augmented views $U$ and $V$, respectively. Here, $(u_i, v_i)$ is a positive pair, $(u_i, v_j)$ and $(u_i, u_j), j \neq i$ are negative pairs.

“Hardness” reflects the trade-off between learning from difficult negatives and avoiding false negatives [3-4]. In our unsupervised setting without labels, this difficulty arises from distinguishing positive and negative pairs. To address this, we introduce a learnable semantics-consistency discriminator that predicts whether a pair is positive or negative based on a threshold $\eta$. We then define hardness as the absolute difference between the predicted consistency score and the threshold, rather than using an entropy-based formulation as

$\text{hardness} = 1 - |p_{v_i, v_j} - \eta|$

where $p_{v_i, v_j}$ is the predicted consistency score of pair $(v_i, v_j)$, and $\eta$ is the threshold for judging whether the sample pairs are positive or negative.

In the theoretical section, Eq. (5) defines an enhanced contrastive similarity designed to reduce the influence of conflicting features within representation vectors. Traditional inner product similarity may suppress positively-synergistic signals due to cancellation from negatively-synergistic ones, even within positive pairs. To address this, Theorems 2 and 3 illustrate the behavioral benefits:

1. Theorem 2 shows that the exponential partitioned similarity in Eq. (5) upper-bounds the standard exponential inner product. This allows positive pairs with aligned partitions to receive higher similarity scores, even when negatively-aligned partitions would otherwise suppress them, thereby enhancing contrastive discriminability.

2. Theorem 3 shows that using partitioned similarity leads to a contrastive loss that provides a tighter lower bound on mutual information. This implies that our method better preserves semantic consistency and promotes the learning of more informative representations.

These theorems provide both mathematical support and behavioral interpretation for our model.

[1] Representation Learning with Contrastive Predictive Coding, in Arxiv 2018.

[2] A Simple Framework for Contrastive Learning of Visual Representations, in ICML 2020.

[3] Understanding the Behaviour of Contrastive Loss, in CVPR 2021.

[4] Debiased Contrastive Learning, in NeurIPS 2020.

W2 & Q1: We conduct experiments to show the contributions of the anchor hardness or the positive similarity in the calibration strategy. To evaluate the anchor hardness, we remove hard negatives of anchors (hardness $\ge$ 0.9 and consistency score < $\eta$) from the loss. Similarly, to evaluate the positive similarity, we remove all the positive pairs (consistency score $\ge \eta$) but preserve the corresponding samples of anchors in the augmented views in the loss. The results are listed in Table 1. Additionally, we provide the performance gaps between CaliGCL and the models without either anchor hardness or positive similarity. Generally, larger gaps correspond to greater contributions of the components. From the results, we find that both the anchor hardness and positive similarity contribute to the performance gains, which validates the effectiveness of the discriminator to calibrate the false-negatives and false-positives. Besides, we observe that positive similarity contributes more in small datasets (Citeseer, Photo, and Computers) while the anchor hardness contributes more in relatively large datasets (Pubmed and DBLP).

Table 1. Comparison of performance gains concerning anchor hardness and positive similarity.

W3 & Q3: We provide the comparative results on model performance, training time, and GPU memory across two large-scale graph datasets, namely Arxiv and Mag in Table 2. The results demonstrate that CaliGCL can be applied to the large-scale datasets. For the model performance, we could observe that CaliGCL has the best performance when compared with other graph models across the two large-scale datasets, which illustrates that the calibration strategy aids in refining the contrastive process and enhances the model performance. However, the training time and GPU memory are heavier than other models due to the discrimination process. Even so, the time and space overheads of the model are within several times that of other models, and overall, they are at the same level.

Table 2. Performance and complexity comparison among the graph models across large-scale datasets.

W4 & Q4: We clarify that CaliGCL differs from existing adaptive weighting methods [1-3] in terms of motivation, methodology, and experiment results. Specifically, we highlight the following key contributions or innovations from theoretical and algorithmic perspectives:

Algorithmic Innovations:

1. Broader bias correction: While most existing GCL methods focus on false negatives [1–2], they often overlook false positive cases where augmentations disrupt true positive pairs. CaliGCL’s discriminator addresses both, enabling more comprehensive correction of contrastive supervision.

2. Comprehensive calibration perspective: Previous adaptive methods typically rely on feature similarity [1] or homophily principle [2] for reweighting. Except for them, CaliGCL introduces a finer-grained partition-level view, allowing calibration at a more detailed level beyond feature similarity or local adjacency.

3. Learnable semantics-consistency: Unlike prior methods that rely on fixed or heuristic similarity measures [1–3], CaliGCL uses a learnable discriminator to adaptively assess whether augmented pairs remain semantically consistent. This leads to more accurate supervision, especially in complex scenarios.

4. Empirical superiority: Beyond theoretical contributions, CaliGCL consistently outperforms existing adaptive weighting methods across various datasets, demonstrating its effectiveness in addressing semantic shifts and feature conflicts for better representation learning.

Theoretical Innovations:

The theoretical section provides a solid foundation for why our method generates more expressive representations than existing methods.

1. Theorem 1 reveals the existence and effect of negatively-aligned partitions in positive pairs, supporting our motivation to suppress their influence.

2. Theorem 2 proves that the proposed exponential partitioned similarity yields a more ideal similarity than the inner product, thereby improving feature discrimination.

3. Theorem 3 further shows that the partition contrastive loss serves as a tighter upper bound on the mutual information lower bound, meaning that it preserves or improves representation quality than the standard contrastive loss.

[1] HomoGCL: Rethinking Homophily in Graph Contrastive Learning, in KDD 2023.

[2] Enhancing Contrastive Learning on Graphs with Node Similarity, in KDD 2024.

[3] Debiased Contrastive Learning, in NeurIPS 2020.

Dear Reviewer,

We sincerely appreciate your time and insightful comments on our paper. As the author-reviewer discussion phase is nearing its deadline, we’d like to kindly confirm if you’ve had a chance to review our responses or if you require any additional clarifications from our side.

Your feedback is crucial to our work, and we’d be grateful for any final thoughts you may have before the discussion period closes.

Thank you again for your efforts!

Best regards,

Authors.

W1: Semantic shift bias corresponds to the semantic relationships between sample pairs which are altered due to augmentations, such as the positive pairs becoming negative pairs. The contrastive supervision is the pre-defined supervision about how to realize the positive or negative assignments. In graph contrastive learning, the contrastive supervision is to assign corresponding nodes across views as positives while others as negatives.

W2: Figure 1 shows that with augmentations, the ratio of positively-aligned partitions decreases, indicating that some positive pairs are no longer aligned and supporting the existence of semantic shifts. However, Figure 1 focuses on the condition that a part of positive pairs become negative pairs. To illustrate the condition that the negative pairs may become positive pairs, we count the negative pairs whose inner product similarities become positive after augmentation, and find that 99,742 negative pairs show semantic shifts. This illustrates the possibility that negative pairs turn into latent positive pairs. The relevant statistics will be added in Figure 1 in the refined version.

For Figure 2, we will supplement these semantics-bias pairs after the augmentation process in detail in the refined manuscript.

W3: Since the augmentations may change the semantic consistency between sample pairs, we propose the discriminator designed for finding the semantic-consistent pairs for calibrating the contrastive process and preventing semantic shift bias. And it is designed as a four-layer MLP with activation functions. We provide the specific configurations across different datasets in Tables 1-2, where Dis_dim is the hidden dimension of the discriminator and Act is the activation function applied in the hidden layer. The last layer will add a Sigmoid function to output the consistency scores.

Table 1. Design of the discriminator for node-level datasets.

Table 2. Design of the discriminator for graph-level datasets.

Q1: The sample pairs used for pre-training have not undergone random augmentations, since the random augmentations may change the semantic consistency of sample pairs. When using the biased samples to train the discriminator, it must restrict its reliability and effectiveness. In order to pick out reasonable positive and negative pairs, we only select the positive and negative pairs in the original graph based on the K-NN algorithm and the homogeneity principle.

Q2: The same in your comment, both the partition contrastive objective and the original contrastive objective follow the InfoNCE objective form that is the lower bound of the mutual information. Theorem 3 is proposed for proving that the proposed partition contrastive objective provides a tighter upper bound than the contrastive objective, not an upper bound of mutual information. We provide discussions on this issue in the following: Formally, the InfoNCE objective for a positive pair $(h, h_+)$ over a batch of size $N$ is

$\mathcal{J}\_{\text{Info}} = \log \left( \frac{\exp(S(h, h_+)/\tau)}{\sum_h \exp(S(h, h)/\tau)} \right)$

It corresponds to

$I(h; h_+) \geq \log N + \mathcal{J}_{\text{Info}}.$

Therefore, the InfoNCE objective is the lower bound of the mutual information. In the paper, the partitioned exponential similarity is defined as:

$S_{\text{part}}(h, h_+) = \frac{1}{K} \sum_k \exp \left( \frac{K \cdot \left[ h^{(k)} \right]^T \left[ h_+^{(k)} \right]}{\tau} \right),$

where $h^{(k)}$ and $h_+^{(k)}$ are the $k$-th partitions of representations $h$ and $h_+$, respectively. The partitioned exponential similarity results in the partitioned contrastive objective as

$\mathcal{J}\_{\text{part}} = \log \left( \frac{S_{\text{part}}(h, h_+)}{\sum_h S_{\text{part}}(h, h_+)} \right).$

Since the objective obeys the InfoNCE formation, we also have

$I(h; h_+) \geq \log N + \mathcal{J}_{\text{part}}.$

Hence, both the contrastive objective and the proposed objective are the lower bounds of the mutual information. However, Theorem 3 proves $\mathcal{J}_{\text{part}}$ is the upper bound of $\mathcal{J}\_{\text{Info}}$, which leads to the following conclusion:

$I(h; h_+) \geq \log N + \mathcal{J}\_{\text{part}} \geq \log N + \mathcal{J}\_{\text{Info}}.$

It means $\mathcal{J}\_{\text{part}}$ is a more ideal objective than $\mathcal{J}\_{\text{Info}}$, which induces a tighter lower bound on mutual information. Theorem 3 provides the inappropriate wording for misunderstandings. We will revise the wording of Theorem 3 as “The partition contrastive objective serves as a tighter lower bound on mutual information, and thus yields an upper-bounded estimate compared to the contrastive objective” in the refined version.