Affinity Uncertainty-based Hard Negative Mining in Graph Contrastive Learning

Recently, contrastive learning [30, 31, 29, 32] has become a prominent technique in self-supervised learning. It has been successfully adapted into diverse domains, including the graph domain. A number of GCL methods [9, 10, 11, 33, 12, 34, 13, 14, 15, 35, 36] have been proposed. DGI [9] is an early attempt that obtained node representations by maximizing the mutual information between node embeddings and high-level graph information. MVGRL [10] improved DGI by introducing different structural views to learn node and graph-level representations. InfoGraph [11] performed contrastive learning by directly maximizing the consistency between sampled subgraphs and pooled graph representations. DiGCL [33] performed direct graph contrastive learning based on laplacian perturbation. Additionally, GraphCL [12] systematically explored the influence of different augmentations on graph-level contrastive learning. GRACE [34] designed a node-level contrastive framework by maximizing the agreement of node embeddings between two corrupted graph views. GCA [13] conducted node-level contrastive learning with adaptive augmentation on the topology and node attribute level. G-Zoom [19] learned node representation by establishing contrastiveness on different scales progressively. PA-GCL [37] explored channel-level contrastive learning among three generated proximity graphs and updated the generated graphs during the training process to improve their contrast effect. Besides, some studies have been put forward to enhance the GCL by automating data augmentations [14] or discarding explicit data augmentations [15] [36]. InfoGCL [35] further built principles to build the optimal GCL model based on Information Bottleneck [38]. The main differences among these methods lie in the way they obtain positive pairs. By contrast, our approach AUGCL focuses on hard negative mining, which is orthogonal to these GCL methods and can be plugged into their loss function to improve their performance on graph/node-level tasks.

Hard negative mining refers to generating or mining the negatives that are difficult to discriminate from the positive. Various methods have been proposed to perform hard negative mining to facilitate contrastive learning, including employing mixup strategy [39] to mix the anchor instance and negative instance to synthesize hard negatives [20, 40, 25, 41], and developing unsupervised sampling methods for selecting hard negative samples [22, 21]. Specifically, DCL [22] adopted positive-unlabeled learning [42] to avoid sampling false negatives. HCL [21] improved DCL [22] by further up-weighting the negatives close to the anchor. These methods are mainly focused on image data and they often treat negative instances that are most similar to the anchor instance as the hard negatives. However, for graph data, the similar negatives could be false negatives relative to the anchor, and the GCL performance would be degraded by employing these hard negative mining methods [23, 26]. To address this issue, ProGCL [23] exploited a two-component beta mixture model on the similarity distribution of negatives to estimate the probability of negative instances being true for an anchor and then measured the hardness of negative instances by integrating the estimated posterior probability and the similarity between the negative and the anchor. AdaS [27] devised an adaptive sampling strategy to emphasize the negatives that are neither too hard nor too easy to discriminate from the anchor, and employed a polarization regularizer to enhance the influence of them. HSAN [28] explored hard positives and negatives by introducing a weight-modulating function. Specifically, this function adjusts the weights of sample pairs in contrastive learning by calculating the disparity between high-confidence pseudo labels and the similarity obtained from both attribute and structure information. Instead of measuring the hardness of negatives, HCHSM [43] selected hard samples based on a mutual information agreement gap between positive and negative pairs and performed hierarchically contrastive learning for hard samples to exploit multilevel intrinsic graph features. Similar to ProGCL, our method also measures the hardness of negatives for each anchor instance. However, we employ the uncertainty estimation model to directly learn the negative instance hardness. The learned hardness is then incorporated into the contrastive loss via a weighting term, resulting in an anchor-instance-adaptive contrastive learning framework with good theoretical support.

Numerous methods and theories have been introduced to measure the prediction uncertainty, e.g., by using the maximum of predicted probabilities [44, 45, 46], the prediction entropy/energy [45, 47, 48, 49], or an extra (void/background) class [50, 51, 49]. These methods focus on calibrating prediction confidence in supervised learning, whereas we utilize uncertainty estimation under the self-supervised setting to empower contrastive learning. Our work is motivated by the observation that hard samples are typically the instances at the decision boundary between the positive and negative instances, which are also the samples that learning models are uncertain about. Thus, uncertainty estimation offers an effective way to measure the hardness of negative instances. To be applicable in graph contrastive learning, AUGCL is designed in a novel way by using an anchor-instance-dependent uncertainty learning approach.

Self-supervised graph representation learning has demonstrated promising performance in empowering diverse graph learning tasks. This work focuses on node-level and graph-level tasks. Particularly, let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ denote a graph where $\mathcal{V}$ and $\mathcal{E}$ denote the set of nodes and edges respectively, then for a node-level task, the goal of self-supervised graph representation learning is to leverage a single graph $\mathcal{G}$ to learn an encoder $\psi(\mathcal{V},\mathcal{E})$ without using the labels of nodes so that $\psi(\mathcal{V},\mathcal{E})$ can yield an expressive low-dimensional embedding $z_{i}$ for each node in $\mathcal{V}$. The resulting node embeddings $\mathcal{Z}=\{z_{i}\}_{i=1}^{|\mathcal{V}|}$ can then be used in various downstream node-level tasks, such as node classification. For a graph-level task, the goal instead is to learn a graph encoder $\psi(\mathcal{V}_{i},\mathcal{E}_{i})$ given a set of $N$ graphs $\{\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{E}_{i})\}_{i=1}^{N}$, where the encoder $\psi(\mathcal{V}_{i},\mathcal{E}_{i})$ outputs a low-dimensional embedding $z_{i}$ for each graph $\mathcal{G}_{i}$, and the graph embeddings $\mathcal{Z}=\{z_{i}\}_{i=1}^{N}$ can then be used in various downstream graph-level tasks, e.g., graph classification. Our approach can be used to improve the self-supervised learning of graph representations and node representations, as shown in Sec. IV. Without loss of generality, we use the graph-level tasks to introduce our approach below.

Graph contrastive learning is one of the most popular approaches for self-supervised graph representation learning. As an instance-wise discriminative approach, it aims to pull two different augmentations of the same graph closer and push augmentations of different graphs apart [12, 10]. InfoNCE [29] is among the most popular contrastive learning loss functions to achieve this goal. Specifically, given a minibatch of randomly sampled graphs $\{\mathcal{G}_{i}\}_{i=1}^{N}$, two augmentation functions $t_{1}$ and $t_{2}$ are first sampled from the augmentation pool $\mathcal{T}$ which consists of all possible augmentations. Then, two graph views $\{\widetilde{\mathcal{G}}_{i}\}_{i=1}^{N}$ and $\{\widehat{\mathcal{G}}_{i}\}_{i=1}^{N}$ are generated by applying $t_{1},t_{2}$ to each graph. The embeddings $\{\widetilde{z}_{i}\}_{i=1}^{N}$ and $\{\widehat{z}_{i}\}_{i=1}^{N}$ of the augmented graphs are obtained by feeding the augmented graphs into a shared GNN encoder $\psi(\cdot)$, followed by a projection head (2-layer perceptron) [31]. For an anchor instance $\widetilde{\mathcal{G}}_{i}$ – a graph augmented from $\mathcal{G}_{i}$ using $t_{1}$, the positive is $\widehat{\mathcal{G}}_{i}$ – a graph augmented from the same graph $\mathcal{G}_{i}$ but using a different augmentation $t_{2}$, while the source of the negative instances is $\{\widehat{\mathcal{G}}_{j}\}_{j=1}^{N}$, from which negative instances are sampled. To enforce the maximization of the consistency between positive embeddings, the pairwise objective for a positive pair $(\widetilde{z}_{i},\widehat{z}_{i})$ is formulated as:

where $\tau$ denotes the temperature parameter and $h(\widetilde{z}_{i},\widehat{z}_{j})$ is the cosine similarity function measuring similarity between $\widetilde{z}_{i}$ and $\widehat{z}_{j}$.

Although these graph contrastive learning methods have achieved great success in graph representation learning, they often fail to consider the semantics of negatives in $\{\widehat{\mathcal{G}}_{j}\}_{j=1}^{N}$. Consequently, instances that share the same semantics with the positive can be sampled and treated as negatives in (1). This false negative sampling issue, also known as sampling bias in [22], would hinder the learning of contrastive representations between positive instances and negative instances. More importantly, the contrastive learning cannot exploit hard negatives, i.e., instances that are similar to but semantically different from the anchor, which are driving force for contrastive learning to learn substantially enhanced discriminative representations, as shown in the literature empirically and theoretically [21, 20, 23].

To address the negative sampling weaknesses discussed in Sec. III-B, we present a novel framework for learning an affinity uncertainty-based hardness measure for enhancing current state-of-the-art graph contrastive learning methods. The key idea is to first learn the hardness of a negative instance relative to each anchor instance by comparing the affinity between them to the affinities of the anchor instance to the other instances. The hardness results can then be plugged into a contrastive loss, e.g., InfoNCE, to improve the effectiveness of current GCL methods in utilizing the hard negatives.

Overview of AUGCL. Since the hardness of a negative instance varies largely w.r.t. different anchor instances, our approach AUGCL aims to learn a hardness measure based on the relative affinity between the negative instance and each anchor instance. That is, for an anchor instance $\widetilde{z}_{i}$ and its negative instance candidate set $\mathcal{\widehat{Z}}_{i}=\{\widehat{z}_{j}\}_{j=1}^{N}$, we learn a single hardness measure function $\phi(\widehat{z}_{j}|\widetilde{z}_{i};\Theta):\mathcal{\widehat{Z}}_{i}\rightarrow\mathbb{R}$ that yields a hardness value for each $\widehat{z}\in\mathcal{\widehat{Z}}_{i}$ relative to $\widetilde{z}_{i}$. Note that the function $\phi$ parameterized by $\Theta$ is trained across all anchor instances; yet the hardness it yields for the negative instance $\widehat{z}_{j}$ is dependent on the anchor $\widetilde{z}_{i}$. For brevity, $\phi(\widehat{z}_{j}|\widetilde{z}_{i};\Theta)$ is denoted as $\phi_{i}(\widehat{z}_{j};\Theta)$ hereafter.

Unlike current hardness measures that define the hardness of a negative instance based on its individual relation to the anchor instance (e.g., the similarity between them), one key novelty in AUGCL is that it defines the hardness based on two groups of pairwise affinities between the negative instances and the anchor instance. More specifically, we introduce the concept of affinity uncertainty below to achieve this goal:

The affinity uncertainty in (2) takes a holistic approach that considers diverse affinities of the negative instances within and across the two groups $\mathcal{C}_{1}^{i}$ and $\mathcal{C}_{2}^{i}$ to learn an accurate hardness for each negative instance $\widehat{z}$. As shown in the literature (e.g., [51]) and Fig. 1, instances that are ambiguous to distinguish are assigned to large uncertainty values. These instances typically have a poor affinity to both groups $\mathcal{C}_{1}^{i}$ and $\mathcal{C}_{2}^{i}$, such as those located on the boundary between the two groups. By contrast, if the instances are coherently aligned within $\mathcal{C}_{1}^{i}$ or $\mathcal{C}_{2}^{i}$, their uncertainty would be small. Thus, this type of uncertainty can be naturally used to define the hardness of the negative instances.

The obtained hardness can then be easily plugged into existing contrastive losses, such as the InfoNCE loss, via a weighting term for the negative instances. Particularly, the AUGCL-enhanced InfoNCE is given as follows:

where $w_{ij}=\alpha\phi_{i}(\widehat{z}_{j};\Theta)$ is the hardness-based weight added to $\widehat{z}_{j}$ relative to $\widetilde{z}_{i}$. $\phi_{i}(\widehat{z}_{j};\Theta)$ is the hardness learned by AUGCL for the negative instance $\widehat{z}_{j}$ w.r.t. the anchor instance $\widetilde{z}_{i}$ and $\alpha$ is a hyperparameter. This enables effective exploitation of the hard negatives, as large weights are expected for hard negatives while small weights are expected for the other instances, e.g., false negatives.

The overall procedure of AUGCL is illustrated in Fig. 2. It follows the standard graph contrastive learning in the graph augmentation and contrastive learning except that we incorporate the affinity uncertainty-based hardness through a weighting term into the contrastive loss as in (3). The right panel in Fig. 2 shows the steps of learning an anchor-dependent hardness measure $\phi$ for each anchor $\widetilde{z}_{i}$, consisting of instance partition and uncertainty estimation as indicated in Def. 1. Before introducing the details of these two components in Sec. III-D, below we demonstrate the theoretical motivation of the proposed method.

Theoretical Motivation. We show below that (3) is equivalent to a triplet loss with an adaptive margin exponentially proportional to the learned hardness-based weight $\phi_{i}(\widehat{z}_{j};\Theta)$. This provides a more straightforward explanation of the working mechanism of the proposed weighting method.

The proof for this theorem is detailed in the Appendix. From the theorem, we can see that the optimal embeddings to (4) should satisfy the following inequality:

where $m_{ij}=\frac{\tau}{2}\log(\alpha u_{ij})$ and $u_{ij}=\phi_{i}(\widehat{z}_{j};\Theta)$. Thus, $m_{ij}$ is equivalent to a transformed affinity uncertainty-based hardness of the negative instance $\widehat{z}_{j}$ relative to the anchor $\widetilde{z}_{i}$, satisfying:

If $\widehat{z}_{j}$ is a hard negative for $\widetilde{z}_{i}$, the large uncertainty $u_{ij}$ between $\widetilde{z}_{i}$ and $\widehat{z}_{j}$ makes the inequality (5) hard to satisfy through $m_{ij}>0$, enforcing better representation learning. On the contrary, if the uncertainty $u_{ij}$ is small, (5) can be easily satisfied with $m_{ij}\ll 0$, reducing the impact of the possible false negative instances.

We introduce an instantiation of our AUGCL framework in this subsection. As demonstrated in Def. 1, the affinity uncertainty-based hardness function $\phi$ parameterized with $\Theta$ can be decomposed into two modules, including a binary clustering function $f:\{\widehat{z}_{j}\}_{j=1}^{N}\rightarrow\{0,1\}$ parameterized by $\Theta_{f}$ and an uncertainty estimation function $g:\{\widehat{z}_{j}\}_{j=1}^{N}\times\{0,1\}\rightarrow\mathbb{R}$ parameterized by $\Theta_{g}$, i.e., $\Theta=\{\Theta_{f},\Theta_{g}\}$. AUGCL is a generic framework. Different clustering and uncertainty estimation methods can be adopted in AUGCL to implement a specific model, as shown by our empirical results in Sec. IV-D. Below we describe the two modules of the best instantiated AUGCL model based on our experiments.

We take $k$-means and Deep Gambler [51] as the partition and uncertainty estimation methods, respectively, to analyze the additional time complexity introduced by AUGCL. Specifically, let $L$ be the number of MLP layers in DG and $d$ be the number of hidden units for all layers. For the graph classification task, given a graph dataset with $N$ graphs and the batch size is set as $B$, the time complexities of partition and the uncertainty modeling are $\mathcal{O}(2(\frac{N}{B})B^{2}T)$ and $\mathcal{O}(KL(\frac{N}{B})B^{2}d^{2})$ respectively, where $T$ is the number of iterations for $k$-means and $K$ is the number of training epochs for the uncertainty estimation model. For the node classification task, given a graph with $N$ nodes, in order to reduce the computation cost, we only sample $M$ ($M\ll N$) negatives for an anchor when training AUGCL. The resulting time complexities of the partition and training uncertainty model are $\mathcal{O}(2NMT)$ and $\mathcal{O}(KLNMd^{2})$ respectively. In experiments, we use the well-established $k$-means clustering implementation from scikit-learn [59], as it runs very fast in practice. Besides, the values of $K$, $L$, $M$ and $d$ are relatively small and the uncertainty estimation model is only trained once. Therefore, the computational overhead over the base model is not significant.

Self-supervised learning has shown effective performance in defending against adversarial perturbations [72, 73]. This subsection investigates whether AUGCL can further improve over the GCL methods on this important property. In this experiment, following [74], three different types of graph adversarial attacks: RandSampling, GradArgmax and RL-S2V are used, where RandSampling randomly adds or deletes edges from graphs, GradArgmax performs edge modification based on gradient information, and RL-S2V is a reinforcement learning based attack method that learns a generalizable attack policy. We also use the widely-used evaluation protocol as in [74] where the graph task is to classify the component numbers in synthetic graphs and structure2vec [71] is adopted as the graph encoder, with different depths of structure2vec considered in the experiments. Both the original structure2vec trained from scratch (i.e., no pre-training) and the pre-trained structure2vec [71] using GraphCL [12] are used as baselines. The experimental results of our method are obtained by incorporating our affinity uncertainty-based hardness into GraphCL to pre-train the structure2vec. The best-competing method ProGCL is adopted in the same way. The results are reported in Table V.

From the table, we can observe that: i) all three GCL methods GraphCL, ProGCL, and AUGCL can largely improve the robustness against all three graph adversarial attacks, particularly the more advanced attacks GradArgmax and RL-S2V, on different network layers, compared with the original model, ii) the robustness can be further improved by exploiting hard negative mining techniques used in ProGCL and AUGCL, compared to GraphCL, and iii) compared with ProGCL, the better hard negative mining in our method AUGCL generally results in more remarkably and stably improved robustness over the GraphCL. Overall, the proposed method AUGCL increases the classification accuracy by up to 8% over GraphCL and up to 2.7% over ProGCL and performs very competitively to the two methods (i.e., around 0.2%-0.8% difference) in the limited cases where AUGCL is not the best performer.

This subsection evaluates the impact of using different clustering and uncertainty estimation methods in $f$ and $g$, respectively. The GraphCL${}_{\text{AUGCL}}$ method is used, with GraphCL as the baseline.

Partition Methods in $f$. An important module of our proposed method is the instance-wise partition function $f$. $k$-means is used by default to implement $f$. Here we also examine the use of spectral clustering [75] to perform the binary partition. The results are shown in Table VI. We can see that AUGCL using either spectral clustering or $k$-means achieves similar improvement over GraphCL, suggesting the stability of our method w.r.t. the generation of the partition labels. AUGCL with $k$-means clustering performs consistently better than spectral clustering. Hence, $k$-means clustering is used by default in our experiments and recommended in practice.

Uncertainty Estimation Methods in $g$. The uncertainty estimation method $g$ is another important module in AUGCL. In addition to the extra class-based method used by default in AUGCL, two alternative approaches are used, including the maximum prediction probability-based method Softmax-Response [44] and the entropy-based method Predictive Entropy [45]. We also include a distance-based method as another simplified variant of AUGCL. The detailed descriptions of these uncertainty estimation methods are presented in Appendix.

The results are reported in Table VI. It is clear that regardless of the specific uncertainty estimation method used, all variants of AUGCL can generally improve the baseline GraphCL on nearly all datasets. This provides further evidence for the effectiveness of our approach. Additionally, the uncertainty estimation method matters: the default method (a recently proposed extra class-based method [51, 49]), a more effective uncertainty estimation model than the other three methods, shows consistently better performance than the other three variants, implying that the hardness can be better captured by more advanced uncertainty estimation methods.

We examine the sensitivity of AUGCL w.r.t two key hyperparameters, i.e., the uncertainty parameter $\alpha$ in (3) and the reward parameter $o$ in $\phi$ (particularly in (7)). Without loss of generality, one graph dataset from biochemical molecules and social networks respectively, i.e., PROTEINS and IMDB-B, are used.

Uncertainty Parameter $\alpha$. $\alpha$ is adaptively set, depending on the uncertainty matrix $\mathbf{U}$, to enable stable performance of AUGCL. Particularly, given $\mathbf{U}$, we can calculate the mean $\mu$ and standard deviation $\delta$ of $\mathbf{U}$, based on which $\alpha$ is set to $\alpha=\frac{1}{\mu}$. We vary the parameter $\alpha$ in the range of $\{\frac{1}{\mu-\delta},\frac{1}{\mu-0.5\delta},\frac{1}{\mu},\frac{1}{\mu+0.5\delta},\frac{1}{\mu+\delta}\}$. The mean classification accuracy (%) under different $\alpha$ are shown in Fig. 3(a) where the labels in the x-axis denote the coefficient of $\delta$ when calculating $\alpha$. It is clear that the performance of our model is generally stable with varying $\alpha$, and $\alpha=\frac{1}{\mu}$ is a recommended setting.

Reward Parameter $o$. We further examine the reward parameter $o$ in the uncertainty estimation model [51]. With $o$ varying in $\{1.5,1.6,1.7,1.8,1.9\}$, we report the mean classification accuracy (%) in Fig. 3(b). The results also show that AUGCL can achieve reasonably stable performance for a wide range of the $o$ settings.

This subsection demonstrates the computation time of the proposed method. Following the experimental setting in the hyperparameter analysis section, we compare the training time on PROTEINS and IMDB-B datasets in a single run with the same setting. The comparison results of our method AUGCL to the baseline GraphCL [12] and all the hardness-aware methods are reported in Table VII.

From the table, we can see that the utilization of hardness-aware methods leads to some increases in computation time. Although AUGCL has the highest computation time, the overall computational overhead compared to the baseline is very minor.

This subsection demonstrates the convergence of the proposed method. We illustrate the loss curves on PROTEINS and IMDB-B datasets in Fig 4(b).

From the figure, we can see that the proposed method achieves fast convergence. Note that there are abrupt drops for both datasets at epoch 10 instead of gradual decreases of loss values. This is attributed to the affinity uncertainty learning performed at epoch 10, in which the learned hardness-based weights effectively capture the hardness of the negatives, i.e., large weights for hard negatives while small weights for the other instances (false and easy negatives). By incorporating the learned weights, the loss from false and easy negatives is significantly reduced, resulting in the learning focusing on the hard negatives and facilitating the convergence of graph contrastive learning.