Source-linked AI summary
ProGCL: Rethinking Hard Negative Mining in Graph Contrastive Learning
Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, Stan Z. Li
TL;DR
Existing hard-negative mining methods are limited in GCL because message passing makes many similarity-based hard negatives false negatives. ProGCL estimates the probability that a negative is true and combines it with similarity, using ProGCL-weight and ProGCL-mix to improve GCL. It reports consistent gains over base methods, multiple state-of-the-art unsupervised results, and performance exceeding supervised baselines on some benchmarks.
Problem
Existing hard-negative mining techniques provide limited benefits in GCL because similarity-selected hard negatives are often false negatives that push same-class samples apart.
Method
ProGCL fits a two-component beta mixture model to estimate each negative’s probability of being true, then combines that probability with similarity for hardness estimation.
Results
ProGCL brings notable and consistent improvements over base GCL methods, achieves multiple state-of-the-art unsupervised results, and exceeds supervised performance on some benchmarks.
Takeaways & Limitations
ProGCL provides two schemes, ProGCL-weight and ProGCL-mix, that can boost various negatives-based GCL methods.
Takeaways & Limitations
The theoretical analysis assumes that G is a non-bipartite and connected graph.
Abstract
from arXiv · showhide
Contrastive Learning (CL) has emerged as a dominant technique for unsupervised representation learning which embeds augmented versions of the anchor close to each other (positive samples) and pushes the embeddings of other samples (negatives) apart. As revealed in recent studies, CL can benefit from hard negatives (negatives that are most similar to the anchor). However, we observe limited benefits when we adopt existing hard negative mining techniques of other domains in Graph Contrastive Learning (GCL). We perform both experimental and theoretical analysis on this phenomenon and find it can be attributed to the message passing of Graph Neural Networks (GNNs). Unlike CL in other domains, most hard negatives are potentially false negatives (negatives that share the same class with the anchor) if they are selected merely according to the similarities between anchor and themselves, which will undesirably push away the samples of the same class. To remedy this deficiency, we propose an effective method, dubbed \textbf{ProGCL}, to estimate the probability of a negative being true one, which constitutes a more suitable measure for negatives' hardness together with similarity. Additionally, we devise two schemes (i.e., \textbf{ProGCL-weight} and \textbf{ProGCL-mix}) to boost the performance of GCL. Extensive experiments demonstrate that ProGCL brings notable and consistent improvements over base GCL methods and yields multiple state-of-the-art results on several unsupervised benchmarks or even exceeds the performance of supervised ones. Also, ProGCL is readily pluggable into various negatives-based GCL methods for performance improvement. We release the code at \textcolor{magenta}{\url{https://github.com/junxia97/ProGCL}}.
1. Introduction
Existing hard-negative mining methods provide limited or negative gains in GCL because similarity-based hard negatives are often false negatives. ProGCL addresses this by estimating whether negatives are true and using that probability with similarity to improve mining.
- Motivation: Existing hard-negative mining techniques yield minor improvements or performance drops when applied to Graph Contrastive Learning.The paper attributes this behavior to differences between contrastive learning and graph contrastive learning.
- Motivation: GCL negatives remain bimodally distributed during its first stage before progressively becoming unimodal during the second stage.This differs from the largely unimodal negative distributions observed during SimCLR training.
- Motivation: Similarity-based selection marks many false negatives as hard, undesirably pushing semantically similar samples away and degrading GCL performance.The paper links this sampling bias to message passing in graph neural networks.
- Approach: ProGCL estimates the probability that a negative is true and combines it with similarity to obtain a more suitable hardness measure.The method uses a two-component beta mixture model to distinguish true and false negatives.
- Approach: ProGCL-weight and ProGCL-mix are two schemes designed to improve hard-negative mining in GCL.They are intended as pluggable schemes for negatives-based GCL methods.
- Results: ProGCL delivers notable and consistent gains over base GCL methods, multiple state-of-the-art unsupervised results, and performance exceeding supervised baselines in some benchmarks.The method also boosts various negatives-based GCL methods.
2. Related Work
Related work spans unsupervised graph representation learning methods and hard-negative strategies from contrastive learning. The paper distinguishes ProGCL from these approaches by targeting node-level GCL and homogeneous graphs.
- Graph Contrastive Learning: Graph contrastive learning methods learn graph- or node-level representations without resource-intensive annotations.Prior methods include mutual-information objectives, diffusion, graph augmentations, and node-level contrastive learning.
- Hard-Negative Mining: HCL and MoCHi emphasize or synthesize hard negatives, while Ring samples negatives around each positive.These methods originate in broader contrastive learning rather than the paper’s proposed GCL-specific approach.
- Hard-Negative Mining: Hard-negative techniques that work in other contrastive-learning settings do not work well in GCL.This motivates a mining strategy tailored to GCL’s negative-sampling behavior.
- Hard-Negative Mining: A structure-enhanced scheme discovers hard negatives in metapath-induced views for heterogeneous graphs but is not suitable for homogeneous graphs without metapaths.Its applicability is therefore narrower than methods designed for homogeneous GCL.
3. Methodology
ProGCL analyzes how GNN message passing changes negative-sample similarities in node-level GCL and uses a beta mixture model to estimate whether negatives are true. It then incorporates this probability with similarity to weight negatives and synthesize hard negatives through ProGCL-weight and ProGCL-mix.
- GCL framework: Node-level GCL creates two augmented graph views and forms inter-view and intra-view negative pairs around node anchors.The framework encodes corresponding nodes in two views and uses cosine-similarity-based critics for contrastive learning.
- Message-passing analysis: Message passing makes neighbor similarities larger and produces a bimodal-to-unimodal negative distribution unlike GCL with an MLP encoder alone.The analysis attributes this difference to GNN message passing and describes later instance discrimination as pushing other samples away regardless of semantic class.
- Message-passing analysis: Theoretical analysis shows that repeated message passing decreases distances between node embeddings under the stated connected, non-bipartite graph assumptions.Theorem 3.1 analyzes embeddings after repeated message passing using the graph propagation operator and its spectral properties.
- True-negative estimation: ProGCL fits a two-component beta mixture model to similarity distributions and uses posterior probabilities to estimate whether each negative is true.BMM is chosen because beta distributions model skewed similarities on [0, 1] more flexibly than Gaussian distributions.
- ProGCL-weight: ProGCL-weight defines negative hardness by combining similarity with the posterior probability that a negative is true.The resulting measure can weight both inter-view and intra-view negative pairs.
- ProGCL-mix: ProGCL-mix synthesizes hard negatives by convexly combining selected existing negatives while emphasizing those more likely to be true negatives.It mixes pairs from the hardest negatives selected by the proposed measure and uses probability-based coefficients; synthesis is performed with inter-view hard negatives.
4. Experiments
Experiments evaluate ProGCL across transductive, inductive, large-scale, plug-in, and ablation settings. Results show consistent gains, while BMM-based probability estimation and mixing are generally strongest.
- Experimental setting: Experiments cover seven graph datasets, transductive and inductive node classification, and comparisons with unsupervised and supervised baselines.The datasets are Amazon-Photo, Amazon-Computers, Wiki-CS, Coauthor-CS, Reddit, Flickr, and ogbn-arXiv.
- State-of-the-art comparison: ProGCL consistently outperforms previous unsupervised baselines and sometimes supervised baselines on transductive classification.The evaluation reports accuracy on transductive tasks and uses GRACE or GCA as base models depending on the setting.
- State-of-the-art comparison: ProGCL achieves competitive inductive performance, and ProGCL-mix generally performs better than ProGCL-weight.The inductive evaluation reports micro-averaged F1-scores.
- Large-scale OGB dataset: On ogbn-arXiv, ProGCL outperforms other unsupervised baselines while providing a tradeoff between performance and complexity.Results are reported on both validation and test sets because the dataset uses a chronological split.
- Plug-in evaluation: ProGCL consistently improves MERIT and is readily pluggable into various negatives-based GCL methods.The MERIT evaluation supports transfer beyond the GCA and GRACE base models.
- Ablation study: BMM outperforms GMM in both weight and mix schemes because it fits the negatives distribution better.The paper also finds that BMM’s estimated posterior is better than random or tuned probability alternatives.
- Ablation study: Compared with GCA, existing hard-negative mining methods bring limited benefits, whereas ProGCL yields consistent and significant improvements.The comparison includes DCL, HCL, Ring, and MoCHi.
- Hyperparameter sensitivity analysis: More synthetic samples generally improve ProGCL-mix, but oversized N ′ provides no significant accuracy or efficiency advantage.The sensitivity analysis varies the number of hardest negatives and synthetic negatives on Amazon-Photo.
5. Conclusions
The paper explains the failure of existing hard-negative mining methods in GCL and introduces BMM-based probability estimation with two schemes to improve GCL. It identifies broader applications and theoretical explanations as future directions.
- Conclusions: The paper attributes weak hard-negative mining performance in GCL to graph-specific effects and introduces BMM to estimate whether negatives are true ones.It combines this estimate with similarity and develops ProGCL-weight and ProGCL-mix.
- Conclusions: Future work includes applying GCL to social analysis and drug discovery and developing theoretical explanations for contrastive learning’s success.
A. Datasets
The experiments use seven graph datasets spanning co-purchase, citation, academic collaboration, image, social, and large-scale scientific-paper networks. Their nodes, edges, features, and labels represent different graph-learning settings.
- Dataset descriptions: Wiki-CS is a Wikipedia reference network with article nodes, hyperlink edges, GloVe-based features, and ten computer-science classes.
- Dataset descriptions: Amazon-Photo and Amazon-Computers are co-purchase networks whose nodes are products with review-based features and category labels.
- Dataset descriptions: Coauthor-CS represents authors connected by co-authorship, with keyword features and labels based on their most active research field.
- Dataset descriptions: Flickr is an image graph connecting images that share properties, while Reddit connects posts commented on by the same user.
- Dataset descriptions: ogbn-arXiv is a symmetrized citation network of computer-science papers classified into 40 arXiv subject-area classes.Its node features are average word embeddings computed from the paper corpus.
B. More Similarity Histograms of Negativess in SimCLR (CL) and GCA (GCL).
Similarity distributions differ substantially between CL and GCL. In graph data, many negatives that appear hard by similarity are false negatives, explaining why similarity-only mining fails.
- Similarity distributions: Figure 9 compares negative-sample similarity histograms for SimCLR and GCA across graph contrastive learning settings.
- Similarity distributions: Unlike in CL, graph-structured data contains many false negatives among the samples most similar to an anchor.Selecting these samples as hard negatives can undesirably push away nodes from the same class.
C.1. Transductive learning
The transductive encoder uses a two-layer GCN, with normalized adjacency incorporating self-loops and learnable weight matrices separated by nonlinear activations.
- A two-layer GCN serves as the encoder for transductive learning.
- The adjacency matrix is augmented with self-loops before normalization.The augmented matrix is defined as ˆA = A + I.
- Each layer applies a nonlinear activation function and a learnable weight matrix.
- For large-scale graph datasets, the encoder extends to three-layer GraphSAGE-GCN with residual connections.
D. Hyper-parameters Analysis
The analysis specifies ProGCL’s hyperparameters and inductive procedure, including BMM fitting, minibatch probability estimation, and subsequent weight or mix optimization.
- Hyperparameter specifications: The starting epoch E determines when the beta mixture model is fitted, while winit initializes the false-negative mixture weight.
- Hyperparameter analysis: The transductive grid searches E over 50–800 and winit over 0.01–0.25.
- Hyperparameter analysis: Accuracy varies substantially with E on Amazon-Photo but only slightly on Coauthor-CS.
- Inductive procedure: In inductive learning, ProGCL samples GraphSAGE subgraphs and generates two augmented views before computing minibatch probabilities.
- Inductive procedure: After epoch E, ProGCL-weight updates with Jw, whereas ProGCL-mix updates with Jm using stored estimated probabilities.
- Inductive procedure: Before epoch E, the algorithm updates encoder parameters with the base contrastive objective J.