# Understanding Negative Sampling in Graph Representation Learning

arXiv: https://arxiv.org/abs/2005.09863 · HTML: https://mlsanity.com/paper/2005.09863/

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2020.

## Built on by (most cited first, 30 of 66)

- [Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks](https://mlsanity.com/paper/2112.14936/) (2021)
- [Towards Better Evaluation for Dynamic Link Prediction](https://mlsanity.com/paper/2207.10128/) (2022)
- [An Empirical Study of Graph Contrastive Learning](https://mlsanity.com/paper/2109.01116/) (2021)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Temporal Knowledge Graph Completion: A Survey](https://mlsanity.com/paper/2201.08236/) (2022)
- [Self-Contrastive Learning with Hard Negative Sampling for Self-supervised Point Cloud Learning](https://mlsanity.com/paper/2107.01886/) (2021)
- [MGAE: Masked Autoencoders for Self-Supervised Learning on Graphs](https://mlsanity.com/paper/2201.02534/) (2022)
- [Contrastive Laplacian Eigenmaps](https://mlsanity.com/paper/2201.05493/) (2022)
- [Self-supervised Contrastive Attributed Graph Clustering](https://mlsanity.com/paper/2110.08264/) (2021)
- [Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling](https://mlsanity.com/paper/2206.11549/) (2022)
- [A Survey on Temporal Knowledge Graph Completion: Taxonomy, Progress, and Prospects](https://mlsanity.com/paper/2308.02457/) (2023)
- [Relation-aware Graph Attention Model With Adaptive Self-adversarial Training](https://mlsanity.com/paper/2102.07186/) (2021)
- [Link Prediction with Non-Contrastive Learning](https://mlsanity.com/paper/2211.14394/) (2022)
- [Learning from the Dark: Boosting Graph Convolutional Neural Networks with Diverse Negative Samples](https://mlsanity.com/paper/2210.00728/) (2022)
- [The Minority Matters: A Diversity-Promoting Collaborative Metric Learning Algorithm](https://mlsanity.com/paper/2209.15292/) (2022)
- [Combating Bilateral Edge Noise for Robust Link Prediction](https://mlsanity.com/paper/2311.01196/) (2023)
- [Negative Sampling in Knowledge Graph Representation Learning: A Review](https://mlsanity.com/paper/2402.19195/) (2024)
- [Diffusion-based Negative Sampling on Graphs for Link Prediction](https://mlsanity.com/paper/2403.17259/) (2024)
- [Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation](https://mlsanity.com/paper/2304.07503/) (2023)
- [RevGNN: Negative Sampling Enhanced Contrastive Graph Learning for Academic Reviewer Recommendation](https://mlsanity.com/paper/2407.20684/) (2024)
- [GraphAgent: Agentic Graph Language Assistant](https://mlsanity.com/paper/2412.17029/) (2024)
- [NuPS: A Parameter Server for Machine Learning with Non-Uniform Parameter Access](https://mlsanity.com/paper/2104.00501/) (2021)
- [Unified Interpretation of Softmax Cross-Entropy and Negative Sampling: With Case Study for Knowledge Graph Embedding](https://mlsanity.com/paper/2106.07250/) (2021)
- [Unsupervised Network Embedding Beyond Homophily](https://mlsanity.com/paper/2203.10866/) (2022)
- [Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processes](https://mlsanity.com/paper/2212.02055/) (2022)
- [BatchSampler: Sampling Mini-Batches for Contrastive Learning in Vision, Language, and Graphs](https://mlsanity.com/paper/2306.03355/) (2023)
- [Layer-diverse Negative Sampling for Graph Neural Networks](https://mlsanity.com/paper/2403.11408/) (2024)
- [Calibrating and Improving Graph Contrastive Learning](https://mlsanity.com/paper/2101.11525/) (2021)
- [CARL-G: Clustering-Accelerated Representation Learning on Graphs](https://mlsanity.com/paper/2306.06936/) (2023)
- [Neighborhood-based Hard Negative Mining for Sequential Recommendation](https://mlsanity.com/paper/2306.10047/) (2023)

## Abstract (arXiv)

Graph representation learning has been extensively studied in recent years. Despite its potential in generating continuous embeddings for various networks, both the effectiveness and efficiency to infer high-quality representations toward large corpus of nodes are still challenging. Sampling is a critical point to achieve the performance goals. Prior arts usually focus on sampling positive node pairs, while the strategy for negative sampling is left insufficiently explored. To bridge the gap, we systematically analyze the role of negative sampling from the perspectives of both objective and risk, theoretically demonstrating that negative sampling is as important as positive sampling in determining the optimization objective and the resulted variance. To the best of our knowledge, we are the first to derive the theory and quantify that the negative sampling distribution should be positively but sub-linearly correlated to their positive sampling distribution. With the guidance of the theory, we propose MCNS, approximating the positive distribution with self-contrast approximation and accelerating negative sampling by Metropolis-Hastings. We evaluate our method on 5 datasets that cover extensive downstream graph learning tasks, including link prediction, node classification and personalized recommendation, on a total of 19 experimental settings. These relatively comprehensive experimental results demonstrate its robustness and superiorities.