Research map / Graph learning / Graph self-supervised learning
Does GCL Need a Large Number of Negative Samples? Enhancing Graph Contrastive Learning with Effective and Efficient Negative Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Challenges the consensus that graph contrastive learning needs many negatives and proposes E2Neg, which trains a GCN with InfoNCE on a small set of spectrally clustered, topologically decoupled center subgraphs as negatives, cutting memory and time by large factors.
Problem
Graph contrastive learning typically uses as many negative node pairs as possible, incurring high computational cost, while nodes in a graph are topologically coupled and violate the independence assumption behind InfoNCE negatives.
Approach
Theoretical analysis suggests that many negatives hinder distinguishing semantics; E2Neg spectrally clusters the graph, picks one centrality-based center per cluster, rebuilds directed k-hop subgraphs around centers so each neighbor attaches to at most one center, augments by swapping centers, and computes InfoNCE only over the few center embeddings.
Key results
- E2Neg achieves the best node classification accuracy on most datasets, e.g., 93.48% on CS and 93.36% on Photo, outperforming GRACE, GCA and ProGCL.
- E2Neg reduces memory usage by roughly 56-98% and trains 4.6-229x faster per epoch than compared GCL baselines.
- Using only fewer than 50 negative nodes (typically), E2Neg maintains or improves accuracy versus full negative sampling, which runs out of memory on Physics for GRACE/GCA/ProGCL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use E2Neg instead of the strongest listed baseline | E2Neg · PubMed node classification | accuracy: 86.46 ± 0.54 -> 86.72 ± 1.09 | Helped |
| use E2Neg instead of the strongest listed baseline | E2Neg · CS node classification | accuracy: 93.18 ± 0.50 -> 93.48 ± 0.59 | Helped |
| use E2Neg instead of the strongest listed baseline | E2Neg · Photo node classification | accuracy: 92.75 ± 0.82 -> 93.36 ± 0.76 | Helped |
| use E2Neg instead of the strongest listed baseline | E2Neg · Computers node classification | accuracy: 88.91 ± 0.98 -> 88.72 ± 0.96 | Hurt |
| use E2Neg instead of the strongest listed baseline | E2Neg · Wiki-CS node classification | accuracy: 80.34 ± 1.01 -> 80.89 ± 1.21 | Helped |
| use E2Neg instead of the strongest listed baseline | E2Neg · Physics node classification | accuracy: 95.77 ± 0.43 -> 95.86 ± 0.30 | Helped |
| replace representative-node sampling with random sampling (ablation) | E2Neg · CS, Photo, Computers, Wiki-CS, and Physics node classification | accuracy: 92.87 ± 0.47 -> 93.48 ± 0.59; 92.42 ± 1.31 -> 93.36 ± 0.76; 87.83 ± 0.70 -> 88.72 ± 0.96; 79.80 ± 1.22 -> 80.89 ± 1.21; | Helped |
| replace representative-node sampling with full sampling (ablation) | E2Neg · CS, Photo, Computers, Wiki-CS, and Physics node classification | accuracy: 92.70 ± 0.74 -> 93.48 ± 0.59; 92.01 ± 0.85 -> 93.36 ± 0.76; 88.17 ± 0.91 -> 88.72 ± 0.96; 79.94 ± 0.68 -> 80.89 ± 1.21; | Helped |
| remove augmentation (ablation) | E2Neg · CS, Photo, Computers, Wiki-CS, and Physics node classification | accuracy: 93.12 ± 0.59 -> 93.48 ± 0.59; 92.54 ± 0.96 -> 93.36 ± 0.76; 88.18 ± 0.74 -> 88.72 ± 0.96; 79.45 ± 1.12 -> 80.89 ± 1.21; | Helped |
| increase the number of clusters substantially beyond the semantic-block count (ablation) | E2Neg · various datasets | accuracy | Hurt |
Surprising findings
- Increasing the number of negative nodes can hinder the model's ability to distinguish nodes with different semantics.
- A very small set of representative negatives (typically fewer than 50) suffices to match or beat full-negative GCL baselines.
Limitations
- Theoretical analysis relies on simplifying assumptions (e.g., treating intra-block similarity as 1) and is not rigorously proven.
- Evaluation limited to node classification on six datasets with a single-layer GCN encoder.
- Number of clusters is a sensitive hyperparameter; large cluster counts degrade performance.
Experimental setup
Datasets: PubMed Amazon-Photo Amazon-Computers Coauthor-CS Coauthor-Physics Wiki-CS
Benchmarks: PubMed Amazon-Photo Amazon-Computers Coauthor-CS Coauthor-Physics Wiki-CS
Metrics: node classification accuracy training time per epoch GPU memory usage
Baselines: DeepWalk Node2Vec GCN BGRL MVGRL DGI GBT GRACE GCA ProGCL
Builds on: InfoNCE GRACE GCA ProGCL GCN
Closest papers by meaning
- ReGCL: Rethinking Message Passing in Graph Contrastive Learning (AAAI 2024 · similarity 0.93)
- A New Mechanism for Eliminating Implicit Conflict in Graph Contrastive Learning (AAAI 2024 · similarity 0.92)
- Improving Graph Contrastive Learning via Adaptive Positive Sampling (CVPR 2024 · similarity 0.92)
- Beyond Homophily: Graph Contrastive Learning with Macro-Micro Message Passing (AAAI 2025 · similarity 0.91)
- S3GCL: Spectral, Swift, Spatial Graph Contrastive Learning (ICML 2024 · similarity 0.91)
- Perfect Alignment May be Poisonous to Graph Contrastive Learning (ICML 2024 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.