# Does Negative Sampling Matter? A Review with Insights into its Theory and
Applications

Zhen Yang, Ming Ding, Tinglin Huang, Yukuo Cen, Junshuai Song, Bin Xu⋆, Yuxiao
Dong, and Jie Tang⋆ Zhen Yang and Ming Ding are with the Department of
Computer Science and Technology, Tsinghua University, Beijing, 100084, China.
E-mail:{yangz21<EMAIL_ADDRESS>
Tinglin Huang is with the Department of Computer Science, Yale University, New
Haven, CT 06511<EMAIL_ADDRESS>
Work was done during his visit to Tsinghua University.
Yukuo Cen is with Zhipu AI, Beijing, China, 100084. E-mail:
<EMAIL_ADDRESS>
Junshuai Song is with the Technology and Engineering Group, Tencent, Beijing,
China, 100080<EMAIL_ADDRESS>
Bin Xu, Yuxiao Dong, and Jie Tang are with the Department of Computer Science
and Technology of Tsinghua University, Beijing, China, 100084. E-mail:{xubin,
yuxiaod<EMAIL_ADDRESS>
⋆Corresponding authors.

###### Abstract

Negative sampling has swiftly risen to prominence as a focal point of
research, with wide-ranging applications spanning machine learning, computer
vision, natural language processing, data mining, and recommender systems.
This growing interest raises several critical questions: Does negative
sampling really matter? Is there a general framework that can incorporate all
existing negative sampling methods? In what fields is it applied? Addressing
these questions, we propose a general framework that leverages negative
sampling. Delving into the history of negative sampling, we trace the
development of negative sampling through five evolutionary paths. We dissect
and categorize the strategies used to select negative sample candidates,
detailing global, local, mini-batch, hop, and memory-based approaches. Our
review categorizes current negative sampling methods into five types: static,
hard, GAN-based, Auxiliary-based, and In-batch methods, providing a clear
structure for understanding negative sampling. Beyond detailed categorization,
we highlight the application of negative sampling in various areas, offering
insights into its practical benefits. Finally, we briefly discuss open
problems and future directions for negative sampling.

###### Index Terms:

Negative Sampling Framework; Negative Sampling Algorithms; Negative Sampling
Applications

##  1 Introduction

Does negative sampling matter? Negative sampling (NS) is a critical technique
used in machine learning, designed to enhance the efficiency of models by
selecting a small subset of negative samples from a vast pool of possible
negative samples (i.e., non-positive samples). A prime example of NS in action
is found in the word2vec [1], particularly within its Skip-Gram architecture.
The Skip-Gram model is designed to predict the likelihood of occurrence of
nearby context words given a target word within a sequence. Formally, for a
given sequence of training words $w_{1},w_{2},\cdots,w_{T}$, the objective is
to maximize the average log probability of context words within a specified
window on either side of the target word, which can be presented as:

$\min-\frac{1}{T}\sum_{t=1}^{T}\sum_{-c\leq j\leq c,j\neq 0}\log
p(w_{t+j}|w_{t})$

where $T$ is the length of the word sequence, $c$ is the size of the training
context (that is a window of words around the target word), $w_{t}$ is the
target word, $w_{t+j}$ are the context words within the window around $w_{t}$.

The probability $p(w_{t+j}|w_{t})$ represents the likelihood of encountering a
context word $w_{t+j}$ given a target word $w_{t}$, defined by the softmax
function:

$p(w_{t+j}|w_{t})=\frac{exp({v^{\prime}_{w_{t+j}}}^{T}v_{w_{t}})}{\sum_{w=1}^{W}exp({v^{\prime}_{w}}^{T}v_{w_{t}})}$

where $v_{w}$ and $v^{\prime}_{w}$ represent the “input” and “output” vector
embeddings of a word $w$, and $W$ denotes the total number of words in the
vocabulary.

The objective of the training process is to optimize these word vector
embeddings to maximize the probability for true context words while minimizing
it for all other words. However, implementing the Skip-Gram model with a
standard softmax function poses significant computational challenges,
particularly with large vocabularies. Each training step requires calculating
and normalizing the probabilities of all words in the vocabulary relative to a
given target word, which is computationally intensive.

Negative sampling is leveraged to simplify this. Rather than considering all
words in the vocabulary, the model only considers a small subset of negative
words (not present in the current context) along with the actual positive
context words. This substantially reduces the computational burden. Besides,
negative sampling changes the training objective. Instead of predicting the
probability distribution across the entire vocabulary for a given input word,
it redefines the problem as a binary classification task. For each pair of
words, the model predicts whether they are likely to appear in the same
context (positive samples) or not (negative samples). The objective of the
Skip-Gram model with negative sampling can be represented as:

$\min-\log\sigma({v^{\prime}_{w_{t+j}}}^{T}v_{w_{t}})-\sum_{i=1}^{k}\mathbb{E}_{w_{i}\sim
p_{n}(w)}[\log\sigma(-{v^{\prime}_{w_{i}}}^{T}v_{w_{t}})]$

where $k$ is the number of negative samples, $w_{i}$ are negative words
sampled for the target word $w_{t}$, $\sigma(\cdot)$ is the sigmoid function
and $p_{n}(w)$ is the negative sampling distribution that is designed as the
3/4 power of word frequencies.

This example demonstrates the importance of negative sampling. Without it, the
model would need to compute the co-occurrence probability with every other
word for each training instance, which is computationally expensive,
particularly for large vocabularies. By employing negative sampling, word2vec
significantly reduces the computational burden and achieves great performance.

In a broader perspective, negative sampling is a critical technique employed
across a variety of fields, such as recommendation systems (RS) [2], graph
representation learning (GRL) [3, 4, 5, 6, 7], knowledge graph learning (KGE)
[8, 9], natural language processing (NLP) [1, 10, 11, 12], and computer vision
(CV) [13, 14, 15, 16, 17, 18]. The core principle of negative sampling –
selecting a representative subset of negative samples to improve the
efficiency and effectiveness of the learning process – remains consistent
across different domains.

To clearly verify the improvements, we compare a basic method with other NS
methods on performance and convergence speed in recommendation system. As
shown in Figure 1, compared with the basic RNS, the method without negative
sampling (Non-NS) achieves a close performance but needs a longer training
time since it uses all negatives for model training. Compared to RNS, other
advanced NS methods can reduce the computational burden, accelerate training
convergence(up to $\sim 48\times$ with Cache-NS), degrade performance bias,
and boost performance ($14\%$ improvement with Mix-NS). Compared with RNS, PNS
(0.75) achieves a faster convergence of $1.6\times$ but reduces performance by
$24\%$. Compared with Mix-NS, DNS (64) shows faster convergence but slightly
degrades performance.

Despite the widespread application of NS, its implementation can differ
greatly across domains. This raises the question: Is there a general framework
that can incorporate all the NS methods and be applicable to different
domains? Our survey aims to answer this by formalizing negative sampling and
introducing a general framework tailored for model training (See Figure 2).
Under this framework, we categorize different NS methods to make them more
accessible and comparable. Besides, we summarize three critical aspects to be
taken into account when designing a better NS method: (1) where to sample
from? (2) how to sample? and (3) in which field should it be applied?

Contributions.  The main contributions of this survey:

  * •

We highlight the importance of negative sampling and propose a general
framework that can incorporate existing NS methods from various domains.

  * •

We identify three aspects that should be considered for designing negative
sampling: negative sample candidates, negative sampling distributions, and
negative sampling applications. We sum up five selection methods for negative
sample candidates and categorize existing negative sampling methods into five
groups.

  * •

We report the characteristics of negative sampling methods in various domains
and demonstrate the pros and cons of each type of negative sampling method. We
summarize several open problems and discuss the future directions for negative
sampling.

Figure 1: Performance and Convergence speed comparison in the RS domain with
the Non-NS and other methods using negative sampling on the Yelp2018 datasets
with LightGCN as an encoder. PNS($\alpha$) denotes popularity-based negative
sampling with various power parameters $\alpha$. DNS($\beta$) represents
dynamic negative sampling with a different number of negative sample
candidates $\beta$. The details of the negative sampling methods can be found
in Section 2.

Survey Organization. The rest of this survey is organized as follows. In
Section 2, we provide the overview of negative sampling, first briefly tracing
back the development history and then giving a general framework. Section 3
reviews existing NS algorithms, as well as the pros and cons of each category.
Section 4 further explores applications of NS in various domains. Finally, we
discuss the open problems, future directions, and our conclusions in Section 5
and Section 6.

Variables Definitions. Here, we elucidate the meanings of the variables
employed in our survey. $x$, $x^{+}$, and $x^{-}$ denote an anchor sample, a
positive sample, and the selected negative sample respectively. $p_{n}$
represents a designed negative sampling distribution. $x^{\prime}$ denotes a
negative candidate within the pool of negative sample candidates
$\mathcal{C}$. These candidates are the potential selections for the negative
sample $x^{-}$, as determined by the negative sampling strategy. $S(\cdot)$ is
a function used to measure the similarity between samples, such as dot product
[19, 6], L1 and L2 norms [20, 21], depending on the specific requirements of
the learning task. $f(\cdot)$ represents the model that maps these input
samples into their respective embeddings.

Figure 2: An illustration of a general framework that uses negative sampling.
Positive and negative pairs are sampled implicitly or explicitly by positive
and negative samplers respectively, both of them composing the training data.
An encoder is applied for latent representation learning in various domains.
In contrastive learning, positive pairs (i.e., Pos-view Pairs) are derived
from data augmentations of the same instance or different perspectives of the
same entity, while in other domains, such as metric learning, positive pairs
(Pos-coexist Pairs) are the other instances in the dataset.

##  2 Negative Sampling

In this section, we provide a comprehensive overview of negative sampling,
detailing its formalization and framework that uses negative sampling for
model training, tracing its historical development from five development
lines, and elaborating its important role in machine learning.

###  2.1 Formalization and Framework

Negative sampling aims to select a subset of negative samples from a larger
pool, which is a technique used to improve the efficiency and effectiveness of
training in machine learning models. The formalization of negative sampling
can be encapsulated in a general loss function, which is designed to maximize
the similarity of positive pairs and minimize it between negative pairs. For
an anchor sample $x$ and a specific positive sample $x^{+}$, negative sampling
selects negative sample $x^{-}$ from a candidate pool $\mathcal{C}$ based on a
negative sampling distribution $p_{n}(x^{-})$ for model training.

$\mathcal{L}={l}(x,x^{+},x^{-}),x^{-}\sim p_{n}(x^{-})$

where $l(\cdot)$ is a specific loss function in various domains.

In different application domains, the specific loss function may vary based on
various tasks and datasets.

  * •

Bayesian Personalized Ranking (BPR) Loss for Pair-based Sampling. For a pair
of positive and negative samples (pos, neg), BPR loss aims to ensure that the
log-likelihood of a positive sample surpasses that of a negative sample.

  * •

Hinge Loss for Triplet-based Sampling. For a triplet of an anchor, a positive
sample, and a negative sample (anchor, pos, neg), hinge loss seeks to maintain
a minimum margin between the similarity of an anchor-positive pair and that of
an anchor-negative pair.

  * •

Cross-Entropy Loss for Single Positive with Multiple Negatives. In cases with
one positive and multiple negatives, cross-entropy loss discriminates the
positive sample from the negatives.

  * •

InfoNCE Loss in Contrastive Learning. InfoNCE loss, common in contrastive
learning frameworks, is designed to contrast positive pairs against negative
pairs.

The core principle underlying the various loss functions associated with
negative sampling is to enhance the model’s ability to distinguish between
positive and negative pairs, effectively pulling positive samples closer and
pushing negative samples apart in the representation space. Detailed
formulations of these functions can be found in Table I. Based on the
formalization of negative sampling, we propose a general framework that uses
negative sampling for model training, which contains a positive sampler, a
negative sampler, and a trainable encoder. The overall framework is
illustrated in Figure 2. The positive sampler is applied to generate positive
training pairs. For example, positive pairs in recommendation are sampled
explicitly from the observed user-item interactions, while these in
contrastive learning are generated implicitly by data augmentations. Negative
training pairs are sampled by different NS strategies via a negative sampler.
The sampled pairs are then processed by a trainable encoder, which is tailored
to the specific application domain. The trainable encoder could be graph
neural networks (GNNs) [22, 23, 24] in graph representation learning, ResNet
[25] in unsupervised visual representation learning, BERT [26] and RoBERTa
[27] in unsupervised sentence embedding learning, Skip-Gram [1] in word
embedding, TransE [20] and TransH [28] in knowledge graph embedding.

Figure 3: The five development lines of negative sampling. Each development
line addresses different challenges and has been adopted and adapted to suit
the specific needs of individual domains, such as RS, NLP, GRL, KGE, and CV.
TABLE I: An overview of loss functions used in a general framework that uses
negative sampling for model training. $\tau$ represents a temperature
parameter that scales the similarity scores. $B$ denotes the batch size. Loss
Formulation
---
$\mathcal{L}_{\text{BPR}}=\text{In}\sigma(f(x^{+})-f(x^{-}))$
$\mathcal{L}_{\text{Hinge}}=\text{max}(0,S(f(x),f(x^{+}))-S(f(x),f(x^{-}))+\gamma)$
$\mathcal{L}_{\text{CE}}=-[\log\sigma(S(f(x),f(x^{+})))+\log(\sigma(-S(f(x),f(x^{-})))]$
$\mathcal{L}_{\text{InfoNCE}}=-\log\frac{exp({S(f(x),f(x^{+}))}/\tau)}{exp({S(f(x),f(x^{+}))/\tau)}+\sum_{k=1}^{B-1}exp({S(f(x),f(x_{k}^{-}))}/\tau)}$

###  2.2 Negative Sampling History

The history of negative sampling is a fascinating development line through the
evolution of machine learning techniques. Here, we delve into the historical
development of negative sampling, highlighting the motivations behind various
negative sampling methods. As shown in Figure 3, the earliest implementation
of negative sampling is random negative sampling (RNS). The basic idea of RNS
is to randomly select a subset of negative samples from the large pool,
thereby reducing the computational requirements of the training process.
Notably in 2008, Pan et al. [29] utilized RNS to prevent the model from
developing a bias towards the majority of negative samples in one-class
collaborative filtering (OCCF) for recommender systems, which effectively
balanced the data. Rendle et al. [2] proposed a pair-wise learning method,
which leveraged pair-wise loss and RNS to solve the lack of negative data in
implicit feedback. Such a RNS method is also applied to graph embedding [20,
30] and GNN-based recommendation [31, 32].

Over time, as machine learning datasets expanded and model complexities
increased, the limitations of RNS became evident. These randomly selected
negative samples might not always be relevant for the model training. This
realization leads to the development of popularity-based negative sampling
(PNS) [1, 3, 5, 4, 24], which selects negative samples based on their
occurrence frequency, popularity, or connectivity within the dataset (i.e.,
degree). This method, predicated on the hypothesis that frequently occurring
negatives are more likely to represent true negatives, attempts to refine the
relevance of negative samples to the dataset. The adoption of a distribution
proportional to the 3/4 power of sample frequency became a hallmark of PNS,
proving its efficacy in domains such as NLP [1] and graph embedding learning
[3, 5, 24].

Nonetheless, both RNS and PNS exhibit a static nature, failing to adapt as
model training, which can lead to suboptimal performance. This challenge paves
the way for hard negative sampling strategies (Hard NS) [33, 34, 35, 19], a
strategy designed to identify and leverage negatives that are difficult for
the model to distinguish accurately. These hard negatives, providing a more
effective learning signal, align the negative sampling more closely with the
model’s current state, enhancing training efficiency and effectiveness.
Additionally, these hard negatives provide more information for gradients in
model optimization, which can accelerate convergence and boost performance.
Hard NS is applied to word embedding [36], answer selection [37], knowledge
graph embedding [38], graph embedding learning [6], GNN-based recommendation
[39, 7, 40], and object detection [41].

The inspiration drawn from Generative Adversarial Networks (GANs) [42] leads
to the development of GAN-based negative sampling (GAN-based NS) [43, 9, 44,
45, 46, 47], a technique where adversarial training and adversarial examples
are leveraged to generate negative samples that closely mirror the
representations of true negative samples not easily found within the dataset.
In this framework, a generator serves as a negative sampler while the training
model acts as the discriminator. Such methods rely on a generator that
adaptively approximates the underlying negative sampling distribution. GAN-
based NS is a general strategy that can be applied to recommendation, graph
learning, knowledge graph learning, and unsupervised visual representation
learning.

Recently, contrastive learning, particularly within unsupervised visual
representation learning, adopts in-batch negative sampling (In-batch NS) as a
strategy to capitalize on the efficiency of using other samples within the
same batch as negatives. This approach obviates the need for external steps to
generate or select negatives, accelerating the training process. For example,
SimCLR [48] utilizes other samples in the current mini-batch as negatives.
MoCo [49] maintains a memory bank to store the past several batches as
negatives for model training, thereby enriching the pool of negatives.
However, the effectiveness of In-batch NS is constrained by the batch size,
where smaller batches might not offer a diverse array of negatives,
potentially limiting the model’s learning capacity. To address this, several
works [16, 17, 18, 50, 51, 52] have focused on introducing hard negatives into
the contrastive learning paradigm.

###  2.3 The Importance of Negative Sampling

Here, we explicitly elaborate on the importance of negative sampling from
three aspects.

  1. 1.

Computational Efficiency. By selecting a representative subset of negative
samples, negative sampling eliminates the need for the model to consider all
possible negative samples during training. Without negative sampling, the
model computes the probability distribution for a sample against the entire
dataset, which is computationally intensive, especially for large datasets
[29, 1]. Negative sampling simplifies this by transforming the task into a
binary classification problem, which allows the model to differentiate between
positive samples and a small number of selected negative samples. Thus,
negative sampling significantly reduces the computational burden and
accelerates the training process.

  2. 2.

Handing Class Imbalance. Real-world datasets often exhibit a significant
imbalance between positive and negative samples, resulting in performance
bias. Negative sampling addresses this issue by curating a more balanced
training dataset, selecting a representative subset of negatives. This method
prevents the model from developing a bias towards the majority class, thereby
improving the model’s ability to accurately predict less frequent classes. In
cases like one-class application scenarios, only target positive samples with
an inherent absence of explicit negative feedback, often indiscriminately
treat all non-positive samples as negatives. By judiciously choosing
negatives, negative sampling ensures more equitable data for the model
training. Thus, negative sampling is a key technique in addressing performance
bias in models dealing with real-world data.

  3. 3.

Improved Model Performance. At the heart of negative sampling’s value is its
ability to improve model performance through the selection of negatives,
particularly those that are closely aligned with positive samples in embedding
space. By focusing on a subset of more informative negative samples, the model
can better capture the subtle distinctions between different samples. As
highlighted in studies [53, 6, 54, 14, 13], negative samples, particularly
more informative or “hard” negatives, contribute significantly to the
gradients during the training process. Hard negatives refer to samples that
closely resemble positive samples in feature space, making the difficult for
the model to distinguish from the positives. Training with these hard negative
samples forces the model to learn finer distinctions because these negatives
contribute more significantly to the gradients, leading to a more effective
optimization process and improvement in the model’s ability to distinguish
between positive and negative samples. Thus, negative sampling, especially
when it involves the strategic use of hard negatives, is an essential
technique for improving the performance of machine learning models.

##  3 Algorithms

TABLE II: An overview of negative sampling methods collected from various domains. For acronyms used, “S” represents Static NS; “H” refers to Hard NS; “G” means GAN-based NS; “A” means Auxiliary-based NS; “B” represents In-batch NS. Cate | Subcategory | Model Recipe | Candidates
---|---|---|---
S | PNS |  Word2Vec [1](NLP), Deepwalk [3](GRL) | Global
LINE [4](GRL),Node2vec [5](GRL)
RNS |  BPR [2](RS), LightGCN [32](RS)
TransE [20](KGE), DISTMULT [55](KGE),RUBER [56](NLP),USR [57](NLP)
H | DNS |  FaceNet [13](CV), Max Sampling [37](NLP), PinSage [39](RS), [41], [58], [59], [60] | Global
SGA [36](NLP),DNS [19],AOBPR [61](RS),BootEA [38],Dual-AMN [62](KGE) | Local
NSCaching [63](KGE),ESimCSE [12](NLP),MoCoSE [64](NLP),MocoRing [18](CV) | Memory-based
Mix-NS |  MoChi [16](CV) | Cache
MixGCF [7](RS), MixKG [65](KGE) | Global
G | Mining |  IRGAN [43](IR),SeqGAN [66](NLP),ACE [67](NLP) | Global
KBGAN [9](KGE),IGAN [68](KGE), NMRN [45](RS)
GraphGAN [44](GEL) ,ProGAN [69](GRL)
Generation |  CFGAN [46](RS),AdvIR [47](IR),HeGAN [70](GRL),SAN [71](NLP)
NDA-GAN [72],AdCo [50], CLAE [73],NEGCUT [74],DAML [75](CV)
A | Graph |  MCNS [6](GRL),SANS [76](KGE) | Hop
GNEG [11](NLP),SamWalker [77],KGPolicy [40], DSKReG [78], MixGCF [7](RS) | Global
Extra |  SBPR [79](RS),PRFMC [80](RS),MF-BPR [81](RS), View-aware NS [82](RS) | Local
ReinforcedNS [83],RecNS [84]
Cache |  Unsupervised Feature Learning [85](CV),NSCaching [63](KGE),SRNS [86](RS) | Cache
MoCo [49], MoCo-V2 [87],MoCoRing [18](CV),GCC [88](GRL),ESimCSE [12],MoCoSE
[64](NLP)
B | Basic |  N.S. [89],$S^{3}$-Rec [90],SGL [91],MHCN [92],DHCN [93] (RS), SimCLR [48](CV) | Mini-batch
MVGRL [94],GRACE [95],GraphCL [96](GRL) ,SimCSE [97],InfoWord [98] (NLP)
Debiased |  DCL [15](CV) ,GDCL [99](GRL)
Hard |  MoCoRing [18](CV) ,CuCo [100],ProGCL [101](GRL) ,VaSCL [102],
SNCSE [103] (NLP), BatchSampler [52] (NLP,GRL,CV)

In this section, we first summarize five categories of selection methods to
form negative sample candidates (i.e., where to sample from?). Next, we
summarize a variety of negative sampling algorithms into five categories
(i.e., how to sample?).

###  3.1 Negative Sample Candidates Construction

The process of constructing negative sample candidates is a critical first
step in the negative sampling pipeline, determining the pool $\mathcal{C}$
from which negatives are drawn for model training. Here, we answer the first
question where should we sample negative examples from? In terms of the
composition of the negative sample candidates, we summarize their selection
methods into the following five categories.

  * •

Global Selection is one of the most common methods for negative sample
candidate selection, where the pool of negative samples is composed of all
possible negatives from the entire dataset. It ensures diversity in the
negative samples but may include less relevant negatives, which could impact
the learning efficiency. For example, word2vec [1] utilizes the whole
vocabulary as the pool of possible negative samples; LightGCN [32] leverages
all unobserved items as the pool.

  * •

Local Selection focuses on sampling a specific subset of the total available
negatives as the pool of negative samples. This method is more selective
compared to Global Selection, aiming to construct a pool that is more relevant
or challenging for a specific query or anchor. For example, ANCE [104] selects
top-k negative samples based on the query as the pool of negative samples.
Besides, the specific subset can reduce the computational complexity that
would be involved in handling the entire set of available negatives. For
example, DNS [19] randomly samples a subset as the pool of negatives for
probability calculations.

  * •

Mini-batch Selection uses other samples in the current mini-batch as the pool
without the additional process of choosing. It leverages already-loaded batch
data, making it computationally efficient. For example, SimCLR [48] and SimCSE
[97] leverage other samples in the same batch as the pool of negatives.

  * •

Hop Selection is a novel selection method for graph-structured data, which
selects $k$-hop neighbors as negative sample candidates. This method
effectively takes advantage of the graph structure where the information
propagation mechanism provides theoretical support. However, matrix operation
for obtaining $k$-hop neighbors is impractical for web-scale datasets.
Therefore, a path obtained from a random walk or DFS is often considered as a
negative sample candidate. For example, RecNS [84] selects the intermediate
region (i.e., k-hop neighbors) as the pool of negatives for graph-based
recommendation; SANS [76] utilizes k-hop neighbors as the pool for knowledge
graph embedding.

  * •

Memory-based Selection maintains a memory bank or a cache as a pool to store
the pool of negative sample candidates. This bank retains a large number of
negatives from past iterations or batches, which are used for subsequent
training steps. The memory bank is typically updated continuously, with new
negatives being added and the oldest ones being removed, ensuring a fresh and
diverse set of negative samples. Memory-based selection is particularly
advantageous for models that benefit from contrasting a wide array of
negatives against positives, such as in contrastive learning scenarios. MoCo
[49] uses a queue bank to store the pool of negative samples.

###  3.2 Negative Sampling Algorithms

Once the negative candidates are constructed, the next step involves negative
sampling algorithms, which aim to design a negative distribution (i.e., a
specific probability distribution) or a sophisticated negative sampling
strategy to sample negative samples from a constructed pool of candidates for
model training.

The design of negative sampling algorithms can be simple, such as random
sampling, or it can be more sophisticated, taking into account factors like
the current state of the model, the difficulty level of the negatives, or
their frequency of occurrence in the dataset. Here, we briefly present an
overview of negative sampling algorithms. Table II summarizes existing
negative sampling algorithms. The general categorization of negative sampling
algorithms and the abbreviated description of each category can be illustrated
as follows:

  * •

Static NS is a static negative sampling method that keeps a fixed negative
sampling distribution throughout the training process. As a basic negative
sampling method, static NS is usually utilized to estimate the performance of
a newly proposed model optimized with negative sampling. In general, static NS
is a simple, fast, and easy-implemented but model-independent method.

  * •

Hard NS is a model-dependent negative sampling method in which the designed
probability of selecting a specific negative sample is related to its
relevance or difficulty. Here, hard negatives are close to the decision
boundary in the feature space, which makes it difficult for the model to
distinguish from positive samples. In summary, Hard NS is a dynamic and
mutually promoting method where the applied negative sampling distribution
varies with model training.

  * •

GAN-based NS is an adversarial negative sampling method that utilizes a
generative adversarial network (GAN) [42] to sample negatives. This method
employs a generator as a negative sampler to select or generate negatives
(fake positives) to confuse the discriminator while a trainable encoder
usually acts as the discriminator to distinguish positive and negative
samples. GAN-based NS engages in a minimax game, mirroring the adversarial
training of GANs to refine the selection of negatives.

  * •

Auxiliary-based NS utilizes some auxiliary information to sample negatives,
such as extra data types, graph structures, or cache mechanisms. Extra-data-
based NS incorporates other types of data into negative sampling, such as view
data and exposure data collected from E-commerce platforms. Graph-based NS
takes advantage of graph information to sample negatives. Cache-based NS
maintains a cache to store important candidate negatives with a fixed
frequency update mechanism.

  * •

In-batch NS is a common negative sampling method that can boost training
efficiency when a large number of negatives are required, which allows for the
sharing of negative samples in a batch. The number of negatives $N$ for each
positive pair is related to the batch size $B$. In dense retrieval domain, the
number of negatives $N$ can be formulated as $N=B-1$ while can be formulated
as $N=2(B-1)$ in contrastive learning. However, this approach must carefully
manage the potential for false negatives, which could adversely affect model
performance.

Next, we successively review each category of negative sampling algorithms in
detail and demonstrate their pros and cons.

####  3.2.1 Static Negative Sampling

Static negative sampling (Static NS) stands as a fundamental approach in the
realm of negative sampling, comprising of random negative sampling (RNS) and
popularity-based negative sampling (PNS). The general distribution can be
represented as:
$p_{n}(x^{-})=(\frac{\\#x^{-}}{\sum_{x^{\prime}\in\mathcal{C}}\\#x^{\prime}})^{\beta}$
where $\beta$ is a hyperparameter that controls the sampling distribution,
$\\#x^{\prime}$ is the frequency of sample $x^{\prime}$.

  * •

Random Negative Sampling (RNS). As the most prevalent negative sampling
method, RNS is widely used as the default sampling method to evaluate the
effectiveness of the proposed model in optimization with negative sampling.
RNS designs uniform sampling weights for each negative sample when deciding
which ones to use during training. Uniform weights mean that every negative
sample has an equal chance of being selected, implying no preference among the
negatives. However, its indiscriminate sampling fails to prioritize
informative negatives, potentially diluting the training signal with less
relevant samples.

  * •

Popularity-based Negative Sampling (PNS). As proposed in previous work [29],
user-oriented and item-oriented sampling methods substitute uniform sampling
by counting the number of interactions of users and items, respectively. It
exploits data properties to sample negatives in early recommendation efforts.
Word2vec [1] empirically sets the negative sampling distribution as the $3/4$
power of word frequency for faster training and better word embedding
learning. Most later studies on network embedding [3, 4, 5] or graph
representation learning [24] also keep this setting for negative sampling.
However, the most appropriate choice of $\beta$ varies with different datasets
and fields (See Figure 4). Results in [54, 11] demonstrate that performance
shows a strong dependency on the choice of $\beta$.

Figure 4: Performance comparison with different choices of $\beta$ on GRL and
RS domains, respectively.

Pros and Cons. Static NS is a simple and easy-implemented negative sampling
method, making it an accessible option for a wide range of applications.
Compared with other heuristic sampling methods, Static NS has the
characteristics of being fast, stable, and model-independent. A significant
limitation of these methods is that the negative sampling distribution remains
static throughout the training process, failing to adjust the selection of
negative samples to suit each positive pair and resulting in sampling low-
quality negatives. In general, performance increases as the number of
negatives increases. However, too many negatives lead to an increase in GPU
memory and training time. Therefore, the number of negative samples should be
further investigated to accomplish the trade-off between performance and time
consumption.

####  3.2.2 Hard Negative Sampling

Hard Negative Sampling (Hard NS) addresses the limitations of static NS by
specifically targeting hard negatives. A concept of hard negative examples was
first proposed in the bootstrapping method [105, 106], which treated
incorrectly classified examples as hard examples. Over time, this idea evolved
to not just include misclassified examples, but also those samples that are
close to the decision boundary in the feature space, irrespective of whether
they have been previously misclassified or not. Thus, hard negatives are close
to the decision boundary in the embedding space, which is difficult for a
model to distinguish from positives.

Hard negative sampling dynamically selects hard negatives based on proximity
in the feature space or based on the confidence level of the model’s
predictions. Based on the source of negatives, hard negative sampling can be
divided into dynamic negative sampling (DNS) and mixture-based DNS. DNS
dynamically mines hard negatives from the raw data while mixture-based DNS
directly synthesizes negative embedding from the embedding space.

  * •

Dynamic Negative Sampling (DNS). In DNS, negative samples are not
predetermined but are selected based on the current state of the model or
specific criteria that evolve as the training progresses. In light of the
criteria, DNS can be divided into three groups, including anchor-based
sampling, positive-based sampling, and anchor-positive sampling.

  1. (1)

Anchor-based DNS. This group focuses on selecting negatives based on their
relationship or similarity to a given anchor. The anchor acts as a reference,
and negatives are chosen based on how they differ from this specific anchor in
the feature space. The general distribution can be represented as
$p_{n}(x^{-})=\frac{S(f(x),f(x^{-}))}{\sum_{x^{\prime}\in\mathcal{C}}S(f(x),f(x^{\prime}))}$.
Rendle et al. [61] developed an adaptive and efficient item sampler to select
informative negative items with a small predicted rank, where the rank is
designed as context-dependent and obtained by the score model among all items.
Chen et al. [36] proposed an alternative sampler to replace word-popularity-
based sampling in the skip-gram model, which prefers to select negative
samples with higher inner product scores. Wu et.al [14] designed a distance-
weighted sampling method to sample informative negatives where the distance
weights between the anchor and negatives are clipped to correct the bias. In
addition to inner product and distance, PageRank score can also be used to
measure similarity in PinSage [39].

  2. (2)

Positive-based DNS. Although anchor-based DNS offers better convergence and
performance, it cannot take the impact of positive samples into consideration.
It may seem intuitive that sampled negatives that are closer to positive
samples will provide a sufficient risk of discrimination in order to
distinguish positive from negative samples. The general distribution can be
represented as
$p_{n}(x^{-})=\frac{S(f(x^{+}),f(x^{-}))}{\sum_{x^{\prime}\in\mathcal{C}}S(f(x^{+}),f(x^{\prime}))}$
. Max Sampling [37] selected the most difficult negative answer by maximizing
the similarities between the positive one and all negatives. Tran et al. [107]
proposed a 2-stage sampling method, which first sampled a small subset of
negative candidates and then selected informative negatives based on the
similarity between a positive item and the candidates. Sun et al. [38]
developed a $\epsilon$-Truncated uniform negative sampling method to mine hard
negative in KGE by using $s$-nearest neighbors of positive entities as
candidates.

  3. (3)

Anchor-Positive DNS. This method involves choosing negatives based on their
joint relationship with both the anchor and the positive samples, which is
valuable in complex learning scenarios like hinge loss frameworks. The general
distribution can be represented as
$p_{n}(x^{-})=\frac{S(f(x),f(x^{+}),f(x^{-}))}{\sum_{x^{\prime}\in\mathcal{C}}S(f(x),f(x^{+}),f(x^{\prime}))}$.
In computer vision, several works [108, 109, 110, 41] selected hard negative
examples based on the triple loss, where negatives are close to the anchor and
incur a high value of the loss. For WARP loss (Weighted Approximate-Rank
Pairwise loss), a myriad of efforts [111, 112] adopted uniform negative
sampling with rejection to mine hard negatives, which uniformly sampled a
negative example until satisfied the constraint of
$1-S(f(x),f(x^{+}))+S(f(x),f(x^{-}))>0$. Guo et al. [113] also designed a
dynamic sampler in word embedding to select informative negative words with
higher ranking scores than positive ones. Faghri et al. [114] combined anchor-
based DNS and positive-based DNS to sample hard negative examples within each
mini-batch in the image-caption retrieval domain. Guo et al. [115] selected
high-ranked negative labels by a rank-invariant transformation for fast
sampling. To improve the robustness, Several works [13, 116] proposed a semi-
hard negative sampling method to select “semi-hard” negatives that were
farther from the anchor-positive pair with a distance margin.

  * •

Mixture-based DNS. Inspired by Mixup [117], the idea of synthesizing hard
negative in embedding space has become one of the popular negative sampling
methods. Unlike methods that select samples existing in the dataset as
negatives, Mixture-based DNS works at the level of embeddings, creating
synthetic negative samples by strategically combining embeddings among several
selected negatives. The synthetic negative samples can be represented as
$\textbf{x}^{-}=\text{Combine}(\\{\textbf{x}_{i}\\})$, where $\textbf{x}_{i}$
is a vector embedding of a selected sample $x_{i}$ and $x_{i}\sim
p_{n}(x^{-})$. The function $\text{Combine}(\cdot)$ is utilized to combine the
selected negatives for synthetic negative samples. In contrastive learning,
MoChi [16] designed a hard negative mixing method to synthesize harder
negatives by mixing the query and the hardest negatives in embedding space
where the hardest ones are generated by anchor-based DNS. MixGCF [7] utilized
the information propagation mechanism to design a hop-mixing strategy to
synthesize negatives from multiple hops in a graph and adopted positive mixing
to enhance negatives. MixKG [65] mixed candidate negative samples via the
convex combination operation where candidate ones were filtered by two
criteria: score-function based sampling and entity similarity correcting.

Figure 5: (a) Performance comparison between Static NS and Hard NS; (b) Impact
of the number of negative candidates in DNS.

Pros and Cons. Hard NS is a model-dependent negative sampling technique that
dynamically samples hard negative examples, which accelerates convergence and
gives a clear gradient update direction for model training. Hard NS achieves
significant performance improvements compared with static NS (e.g. PNS and
RNS) (See Figure 5 (a)). However, such methods have an obvious disadvantage,
namely that require more time to obtain distribution by the current model. To
improve the efficiency, hard negative sampling usually samples a subset or
takes mini-batch examples as negative candidates. Thus, the effectiveness of
Hard NS relies on the number of candidates, which varies largely on different
datasets (See Figure 5 (b)). More importantly, false negatives have gradually
attracted more attention since they are closer to positive samples in
embedding space and are difficult to distinguish from true negative samples.
Many works [15, 86, 118, 119] focus on alleviating the false negative issue
and boosting the robustness of the sampling process. Overall, Hard NS is an
effective negative sampling method to speed up convergence and boost
performance.

####  3.2.3 GAN-based Negative Sampling

GAN-based negative sampling methods utilize generative adversarial networks
(GANs) to mine or generate adversarial negatives, which are widely adopted in
multiple domains. For GAN-based NS, the generator serves as a negative sampler
to mine or generate informative negatives (false positives) to confuse the
discriminator. The trainable models serve as a discriminator to distinguish
the true positives and false positives (negative). GAN-based NS methods can be
roughly divided into two subcategories: GAN-based negative mining and GAN-
based negative generation.

  * •

GAN-based Negative Mining. GAN-based negative mining utilizes GAN to
adaptively mine informative negatives from the dataset. This method relies on
discrete indexes of raw data, with the generator identifying potential
negatives to challenge the discriminator. The general distribution can be
represented as
$p_{n}^{G}(x^{-})=\frac{S(G(x),G(x^{-}))}{\sum_{x^{\prime}\in\mathcal{C}}S(G(x),G(x^{\prime}))}$
where $G$ denotes a generator that generates negatives. SeqGAN [66] is the
first work to utilize the generator to select discrete negatives and directly
apply policy gradient to achieve gradient passing from the discriminator to
the generator. IRGAN [43] utilized the generative information retrieval model
to select the discrete index of samples as negatives, which uses REINFORCE
[120] for model optimization. The abovementioned methods provide a new idea
for negative sampling that designs an adversarial negative sampler and applies
a policy gradient-based reinforcement learning (RL) method for model
optimization. Such negative sampling methods are widely developed in other
fields. For example, GraphGAN [44] employed a GAN-based framework for graph
representation learning, and NMRN [45] proposed an adaptive negative sampler
based on GAN in a streaming recommendation, and ACE [67] adopted GAN to find
harder negatives in word embedding. In knowledge graph embedding, KBGAN [9]
utilized one of the existing knowledge graph embedding models as the generator
to sample high-quality negatives while Wang et al. [68] employed a two-layer
fully-connected neural network as the generator for negative sampling.

  * •

GAN-based Negative Generation. Instead of mining negatives from raw data, GAN-
based negative generation aims to generate synthetic negative embedding
directly from the embedding space for model optimization. This method
generates hard negatives by synthesizing new samples that are specifically
designed to challenge the discriminator. The general distribution can be
represented as
$p_{n}(\textbf{x}^{-})=\frac{S(\textbf{x},\textbf{x}^{-})}{\sum_{x^{\prime}\in\mathcal{C}}S(\textbf{x},\textbf{x'})}$,
where x, $\textbf{x}^{-}$, and x’ are generated vectors by the generator $G$.
CFGAN [46] utilized the generator to generate continuous negative embeddings
composed of real-valued elements in collaborative filtering without using the
RL method for model optimization. DAML [75] employed adversarial learning to
synthesize hard negatives from inputs (anchor, positive, and negative) by the
generator for metric learning. Different from IRGAN comprising of two models,
AdvIR [47] only used a single model to combine adversarial sampling and
adversarial training to generate hard negative examples by adding adversarial
perturbation vectors on negative example vectors. Similar to AdvIR, CLAE [73]
designed an adversarial training algorithm for self-supervised learning that
leveraged adversarial examples to generate harder negatives. HeGAN [70]
extended GAN-based NS into Heterogeneous Information Networks (HIN), which
generates “latent” negative nodes from a continuous distribution rather than
true existing nodes. In dialogue systems, Gupta et al. [71] synthesized
adversarial negative responses. AdCo [50] applied GAN-based NS to contrastive
learning to generate challenging negative examples. Sinha et al. [72] proposed
negative data augmentation (NDA) and integrated it into GAN where NDA acted as
the generator to synthesize hard negatives for the discriminator. Chen et al.
[121] utilized negative data augmentation (NDA) for novelty detection.

Pros and Cons. GAN-based NS leverages adversarial learning to adaptively mine
or generate negative samples, which provides more informative negatives and
achieves faster convergence and better performance. This method adopts an
adaptive negative sampler as a generator for sufficiently exploiting training
samples or embedding space to seek more informative negatives. As shown in
Figure 6, compared to RNS, GAN-based NS achieves better performance on
different domains since it mines more informative negatives for model
training. However, GAN-based NS has an obvious shortcoming of unstable
training. A common method to alleviate this issue is to pretrain the
discriminator and the generator, which violates the original purpose of using
negative sampling to speed up training. Thus, a stable optimization for GAN-
based NS is a core and challenging problem, which leaves much room to
investigate. Besides, GAN-based NS usually requires an additional network as
the generator, which increases the training time and computational load. In
general, GAN-based NS has a promising prospect for discovering hard negative
samples but it is time-consuming, limiting its application to large-scale
datasets.

Figure 6: Performance comparison between different GAN-based NS and RNS on
recommendation system (left), knowledge graph embedding (middle), and computer
vision (right).

####  3.2.4 Auxiliary-based Negative Sampling.

Auxiliary-based negative sampling methods rely on auxiliary information to
sample negatives, comprising extra-data-based NS, graph-based NS, and cache-
based NS. Each subcategory of Auxiliary-based NS possesses its unique
characteristics, which will be demonstrated in detail.

  * •

Extra-data-based NS. This method utilizes external datasets or additional
information beyond primary training set, enriching negative samples with a
broader context or more examples and allowing for the selection of negatives
that are more informative or challenging. For example, within the realm of
recommendation systems, leveraging additional sources of information, such as
social links, view data, and exposure data, can significantly enrich the
negative sampling process. These auxiliary data types are particularly
valuable as they offer insights into user preferences and behaviors that are
not captured by traditional interaction data alone. SBPR [79] incorporated
social links into negative sampling where social feedback served as negatives
for positive items but was regarded as positives for unobserved negative
items. Instead of utilizing a single additional information for negative
sampling, PRFMC [80] leveraged both social links and geography to enhance
negative sampling. MF-BPR [81] utilized multi-feedback data to compose
negative items, which proposed a non-uniform negative sampler that quantified
the impact of different types of feedback. Mix-Exp-NS [82] integrated view
data into negative sampling, which designed a sampling weight to sample
negatives from view and unobserved items. RNS-AS [83] combined exposure data
and adversarial training into negative sampling to select high-quality real
negatives. RecNS [84] mixed negatives from positive-assisted and exposure-
enhanced negative sampling methods to select hard and real negatives.

  * •

Graph-based NS. This method capitalizes on the rich structural information
inherent in graph data to enhance negative sampling. This approach is
particularly pertinent in scenarios where data can be naturally represented as
graphs, such as social networks, citation networks, or any domain where
relationships between entities can be constructed as a graph. GNEG [11]
leveraged random walk on the constructed word co-occurrence network to obtain
negative sampling distribution. SamWalker [77] conducted the personalized
random walk with a walking probability on a social network to obtain the
distribution for sampling informative negative examples. SamWalker++ [122]
designed a pseudo-social network to substitute the additional social network
for random walk-based negative sampling. MCNS [6] leveraged self-contrast
approximation to closely mimic the distribution of positive distribution and
utilized Metropolis-Hastings to accelerate negative sampling based on graph
structure, which adopted DFS to traverse the graph for generating Markov
chain. KGPolicy [40] integrated item knowledge graph into recommendation for
negative sampling, which adopted reinforcement learning framework to select
informative negative samples. MixGCF [7] utilized graph structure to sample
hard negative items from multiple layers and mixed these with the positive
item to obtain the synthetic negatives.

  * •

Cache-based NS. This method employs a cache or memory bank as a dynamic
repository for negative samples. In this way, the model can quickly and
efficiently access these samples during training. This approach significantly
reduces the computational overhead associated with sampling new negatives for
each training iteration. Wu et al. [85] maintained a memory bank for storing
negative samples. NSCaching [63] used a cache to maintain rare hard negative
triplets and uniformly selected negatives from the cache for knowledge graph
embedding learning. SRNS [86] designed a memory-based negative sampler to
store high-variance negative candidates, which can effectively alleviate the
false negative issue in recommendation. In unsupervised visual representation
learning, MoCo [49] utilized a queue to store mini-batches data as negatives
for the next iteration. MoCHi [16] and MoCoRing [18] utilize hard negative
sampling methods to enhance Cache-based NS. GCC [88] maintained a queue to
store negative instances for unsupervised graph representation learning. Cert
[123] utilized a queue to store negative examples for language understanding.
ESimCSE [12] and MoCoSE [64] leveraged a negative sample queue to further
improve sentence embedding learning. Cache-based NS exploits more negatives
during the training but requires more time to update the cache. Thus, a fast
cache update mechanism should be explored to further improve the efficiency of
cache-based NS.

Pros and Cons. Auxiliary-based NS enriches the process of selecting negative
samples by incorporating a variety of auxiliary information, enhancing the
quality of negative samples. However, it’s important to consider the trade-
offs in terms of efficiency and domain-specific applicability. For example,
the need to collect extra data can be a limitation, as it may not be feasible
or practical in all domains. Additionally, the increased data volume can lead
to higher data loading overheads, impacting computational efficiency. Graph-
based NS depends on graph algorithms for traversing and mining negatives,
which may increase the time consumption. Cache-based NS eliminates the
constraint of GPU memory size for In-batch NS, but the update mechanism of the
cache is very time-consuming. Thus, a trade-off between effectiveness and
efficiency should be considered in negative sampling methods.

####  3.2.5 In-batch Negative Sampling

In-batch negative sampling method is a distinct approach within the realm of
negative sampling techniques, primarily relying on the composition of mini-
batch data during training. Unlike other negative sampling methods that
explicitly sample negatives for each positive pair, In-batch NS leverages the
inherent structure of mini-batches to implicitly sample negatives. This method
is particularly notable for its efficiency and simplicity. In-batch NS can be
divided into three subcategories, including basic, debiased, and hard.

  * •

Basic In-batch NS. This method is first proposed for neural network-based
collaborative filtering [89] to utilize the non-linked examples within the
same mini-batch as negatives. It has been effectively adopted in various
domains, from image embedding to dual-encoder models in NLP, where it
significantly increases the number of negative examples with minimal overhead.
Ye et al. [124] leveraged In-batch NS to optimize the negative log-likelihood
objective for unsupervised image embedding learning. In a dual-encoder model,
In-batch NS has been used as a significant and effective trick for model
training where $(B-1)$ examples in the same mini-batch are regarded as
negatives [125, 126, 127], which efficiently boosts the number of negative
training examples. In contrastive learning, SimCLR [48] leveraged In-batch NS
for visual representation learning where $2(B-1)$ examples generated by data
augmentation are treated as negatives. Later, such a simple framework is
widely used in various domains for unsupervised representation learning.
SimCSE [97] follows SimCLR framework for sentence embedding learning. Several
prior works [94, 95, 96, 128] on graph contrastive learning also adapt SimCLR
framework to design augmentation transformations based on graph structure. SGL
[91] incorporated self-supervised graph learning into recommendation and
designed two types of In-batch NS for the auxiliary task.

  * •

Debiased In-batch NS. A primary bias introduced by In-batch NS is false
negatives, which can significantly affect the performance of the model. In
basic In-batch NS, samples within a mini-batch that are not explicitly labeled
as positive are automatically treated as negatives. This assumption can lead
to the inclusion of false negatives – actual positive samples mistakenly
treated as negatives due to the absence of explicit positive labeling in the
batch. DCL [15] proposed a debiased contrastive objective to alleviate
sampling bias, which corrected the weights of negatives with positive examples
in InfoNCE. DCLR [129] designed a debiased objective function that adjusted
the weights of negatives using the complementary model. Huynh et al. [130]
mitigated the effect of false negatives by two approaches: false negative
elimination and attraction, which identified false negatives and removed them
from the original negative candidates and added them into positive pairs set.

  * •

Hard In-batch NS. Basic In-batch NS typically treats all samples within a
mini-batch as negatives, assuming these samples are randomly sampled from the
training data. However, this approach ignores the importance of the difficulty
level of negative samples. Hard In-batch NS method seeks to identify and
utilize hard negatives within the batch. HCL [17] developed a hard negative
sampling method for contrastive learning, which reweights the weights of
negatives in the objective. Xiong et al. [104] globally selected hard negative
samples by an asynchronously updated ANN index, in which negatives were
generated by the dense retrieval (DR) model. Zhan et al. [131] adopted dynamic
hard negatives to boost the training process and the ranking performance of
the DR model. Yang et al. [52] proposed BatchSampler to globally sample hard
negatives for contrastive learning.

Pros and Cons. In-batch NS stands out as an effective and efficient approach,
particularly due to its ability to reuse samples from the current mini-batch
without necessitating additional sampling operations. This method benefits
from larger batch sizes, allowing for a broader range of negative samples to
be included in training, which is crucial for effective learning in
contrastive learning frameworks. However, this means that the effectiveness of
In-batch NS depends on the batch size. As indicated in Figure 7, the
downstream performance exhibits a noticeable variation in relation to the
batch size used during training. There is a clear trend indicating that larger
batch sizes can improve downstream performance. In fact, In-batch NS is
equivalent to random sampling since the data in the mini-batch are generated
randomly. Compared to the basic In-batch NS leveraged by SimCLR, Debiased In-
batch NS and Hard In-batch NS achieve better performance (See Figure 7). Thus,
integrating a hard negative mining strategy into In-batch NS is a huge
challenge, which leaves us a lot of room for exploration. Furthermore, since
In-batch NS is usually applied in contrastive learning for unsupervised
representation learning, the false negative issue is an inevitable problem
that plays a significant effect on the downstream performance.

Figure 7: Classification performance comparison with different In-batch NS on
top-1 accuracy. Taken from [17]

##  4 Applications

Negative sampling is an essential technique, which has been widely used in
various domains(e.g. recommendation, graph representation learning, knowledge
graph embedding, natural language processing, and computer vision).

###  4.1 Negative Sampling in RS

Recommender Systems (RS) have emerged as an indispensable tool for information
filtering across a variety of online platforms, including e-commerce sites,
advertising platforms, and entertainment services. The core challenge in
developing effective RS lies in accurately modeling user preferences, a task
primarily reliant on interpreting historical interaction data. Such data often
records positive user interactions – like purchases, likes, or views – but
seldom includes explicit negative feedback, making it difficult to discern
user dislikes or indifference. To tackle this, negative sampling has been
widely applied in previous works [29, 2, 32, 7].

Figure 8: The process of negative sampling in a recommender system where
negative samples are sampled from non-interaction items.

As shown in Figure 8, negative sampling aims to sample a small portion of
items from the non-interaction items. The most popular negative sampling
method is random negative sampling (RNS) [29, 2], which serves as a basic
negative sampling method to evaluate the performance of the proposed model.
However, RNS assigns equal weights to unobserved items, which usually draws
uninformative negative items for model training. To improve the quality of
negative samples, many previous works mainly focus on popularity-based
negative sampling (PNS) [132, 133, 134], hard negative sampling (hard NS) [19,
61], and GAN-based negative sampling (GAN-based NS) [135, 45]. The high-
quality negative items contribute more to the gradient of the loss function,
increasing its magnitude and accelerating convergence. PNS selects negative
items based on item popularity, which depends on the data distribution.
Intuitively, popular items that are non-interacted with a user are more likely
to be negative. However, results in [54] reveal that the smoothing parameter
for negative sampling has a significant effect on recommendation performances.
Hard NS methods draw negative items based on prediction scores between the
users and candidate negative items. Such methods aim to sample hard negative
items with higher prediction scores. Additionally, GAN-based NS methods use
the generator to obtain the sampling distribution for adaptively sampling
informative negative items. However, the abovementioned methods suffer from
the false negative issue where more hard (informative) negative items are more
likely to be positive items. Synthesizing hard negative items has become an
effective way to address this problem, which synthesizes or generates
negatives in embedding space rather than sampling an existing item from raw
data.

Graph Neural Networks (GNNs) offer a fresh perspective on RS by modeling user-
item interactions as bipartite graphs [39, 136, 31, 32] or session graphs
[137], enabling the leveraging of graph structures for more insightful
recommendations. In light of this, graph learning methods provide a novel
perspective for recommender systems, which incurs a myriad of GNN-based
recommendation models in recent years. Similar to the traditional
recommendation, negative sampling is also applied for model training in GNN-
based recommendation models. Such sampling methods can incorporate graph
information to sample negative items. For example, Pinsage [39] sampled hard
negative items based on personalized PageRank scores for the Pinterest
recommendation. MCNS [6] performed DFS on the graph to generate a Markov chain
for negative sampling. KGPolicy [40] integrated a knowledge graph into
negative sampling for seeking high-quality negative items. MixGCF [7] proposed
hop mixing which mixed negative items sampled from different hops on the
graph. To sum up, negative sampling in GNN-based recommendation can leverage
graph information to design better negative sampling strategies but the
efficiency issue should also be considered.

In summary, negative sampling has been proven to be an effective way to
improve recommendation performance. As it applies to online services,
recommendation systems must seriously consider the efficiency of negative
sampling. In-batch NS is an efficient way that can be applied to large-scale
recommendation. Thus, a challenging direction is how to reduce the sampling
bias for In-batch NS.

###  4.2 Negative Sampling in GRL

Graph representation learning (GRL) has received a myriad of attention in
recent years due to its effectiveness in handling graph-structured data. This
data structure is prevalent across a wide range of applications, including
social networks, biological networks, academic networks, and many other
domain-specific networks. The essence of GRL lies in its ability to encode the
complex structure and features of graphs into low-dimensional embeddings,
facilitating their use in downstream tasks such as node classification, link
prediction, graph classification, and clustering.

Given the computational challenge of processing all nodes within large-scale
graphs, negative sampling emerges as a crucial strategy to enhance efficiency
by selecting a subset of nodes as negatives based on the noise distribution
learned from the graph (See Figure 9). Early implementations in GRL, such as
DeepWalk [3] and Node2vec [5], followed the negative sampling setting in
word2vec, which selected negative nodes according to the empirical unigram
distribution proportional to the 3/4 power. However, this predefined sampling
distribution can not dynamically sample negative nodes according to the
training process. Gao et al. [138] proposed a self-paced negative sampling
strategy to gradually sample the informative negative nodes for model
optimization. Inspired by IRGAN, Gao et al. [138] incorporated generative
adversarial network (GAN) into self-paced negative sampling to form an
extension version of adversarial self-paced negative sampling. Robust-NS [139]
argued that popularity-based negative sampling failed to accurately estimate
the objective of skip-gram due to the popular neighbor problem, which proposed
a distance-based negative sampler to draw negative nodes from candidate nodes
without neighbors. As a most popular GNNs-based method, GraphSage [24]
utilized negative sampling to optimize a graph-based loss function, which also
kept the setting of word2vec. GraphGAN [44] integrated GAN into graph
representation learning where negative samples were sampled by the generator.
Later, MCNS [6] systematically analyzed the role of negative sampling in graph
representation learning and proposed Markov chain Monte Carlo negative
sampling.

Figure 9: The process of negative Sampling in GRL. Taken from [6].

Recently, contrastive learning has attracted a surge of interest for
unsupervised visual representation learning [85, 49, 48]. In terms of the
great success of contrastive learning in computer vision, numerous works
extended it into graph learning [88, 99]. After that, negative sampling in
graph contrastive learning has also achieved tremendous success. Zhao et al.
[99] proposed a graph-debiased contrastive learning framework to alleviate the
false negative issue, which utilized clustering to obtain pseudo labels and
conducted random sampling to sample negatives from the different clusters.
Such a method suffers from expensive computational consumption. CuCo [100]
proposed a curriculum contrastive learning framework that gradually samples
negatives from easy to hard, in which hard negatives are determined by the
score function. Zhu et al. [140] utilized heterogeneous graph structure to
sample hard negatives with the largest similarities and synthesized more
negatives by a mixing operation. ProGCL [101] utilized a beta mixture model
(BMM) to mine true and hard negative examples for graph contrastive learning.
Xiong et al. [104] proposed approximate nearest neighbor negative contrastive
learning (ANCE) for the dense retrieval (DR) model, which globally sampled
hard negatives with top retrieved scores from the current DR model.

In summary, negative sampling in graph representation learning has achieved
some remarkable progress but still leaves a lot of room for improvement. For
example, how to effectively use graph structure for negative sampling; how to
incorporate GNNs propagation mechanism into negative sampling? How to design
an effective negative sampling method for graph contrastive learning?

###  4.3 Negative Sampling in KGE

Knowledge graph embedding (KGE) provides a new way to represent complex human
knowledge in a structured form, encapsulating entities, relationships, and
semantic descriptions within a multi-relational graph framework. Each relation
in a knowledge graph can be represented as a triple of $<head\
entity,relation,tail\ entity>$. The key idea of knowledge graph embedding is
to embed entities and relations in a KG into a continuous embedding space. The
learned embeddings pave the way for many downstream applications, including
knowledge graph completion, relation extraction, entity discovery, question
answering, and recommender systems.

Negative sampling is a fundamental technique in knowledge graph embedding,
which is applied to sample entities from the knowledge graph to replace the
head entity or tail entity for forming a negative triple. A common negative
sampling strategy in KGE is randomly sampling entities from a uniform
distribution. However, such a strategy owns the obvious limitation that the
sampled entities usually do not match the relations with the remaining
entities, which does not provide meaningful information for gradient and
prevents the model from learning better embeddings. To constrain the
correlation of negative triples, [8] drew negative triples within the range
constraints of entity types. PNS [141] proposed a probabilistic negative
sampling to address the skewness issue in the dataset, which leveraged a
tuning parameter to sample negatives from a pre-designed list that contained
semantic possible negative instances. [142] developed two embedding-based
negative sampling strategies: nearest neighbor sampling and near miss
sampling, which aimed to search for negative triples that are close to
positive triples in embedding space. KBGAN [9] developed an adversarial
framework for knowledge graph embeddings, which utilized existing embedding
models as the generator to generate high-quality negative triples. Later,
several works [68, 143, 9] continued to integrate GAN into knowledge graph
embedding for sampling negative triples. For example, IGAN [68] leveraged two-
layer fully-connected neural networks as the generator to search informative
negative triples. These methods sample high-quality negative triples with
large gradients, which avoid the vanishing gradient issue and achieve
performance improvements. However, GAN-based negative sampling methods need an
extra generator and a complex gradient update approach. To efficiently sample
negative triples, RotatE [143] proposed a self-adversarial negative sampling
strategy that selected negatives based on the current model. Similar to DNS,
Shan et al. [144] proposed a confidence-aware negative sampling method to
enhance the confidence-aware knowledge representation learning (CKRL), which
sampled negatives according to the softmax function that calculated by the
current model on the candidate negatives set. SNS [145] utilized a distance-
based score to search for high-quality negatives from a small randomly sampled
candidate negative set in embedding space. NSCaching [63] used extra caches to
store large-gradient negative heads and tails for each positive triplet
respectively, and directly sampled negatives from the caches. To sample valid
negative triples for assist model training, ANS [146] leveraged the K-Means
clustering algorithm to measure the similarity in embedding space and
uniformly sampled negatives from the same cluster for a particular positive
triplet. SANS [76] utilized knowledge graph structure to sample negative
triples where 1-hop neighbors are regarded as positives and the $k$-hop
neighbors $(k>1)$ serve as negatives (See Figure 10). Instead of selecting an
existing entity for negative sampling, MixKG [65] leveraged a mixing operation
to synthesize hard negative samples. Different from the abovementioned methods
of replacing head or tail entities, TransG [30] constructed negative triples
by substituting the relation of triples. To sum up, negative sampling in a
knowledge graph should focus on the validity of negatives satisfied the
semantic relation, which can provide more information for the model to
distinguish between positives and negatives.

Figure 10: Integrating the structure of knowledge graph into negative
sampling. Taken from [76].

In summary, negative sampling in knowledge graph embedding relies heavily on
the triple loss function. Thus, how to design a powerful loss function that
incorporates the characteristics of a knowledge graph? How to develop a
hierarchical negative sampling method by leveraging the hierarchical structure
of the knowledge graph?

###  4.4 Negative Sampling in NLP

Negative sampling plays an important role in the field of natural language
processing (NLP), which is widely used across a spectrum of applications
including word embedding, sentence embedding, dialogue systems, dense
retrieval (DR), and named entity recognition (NER). Word2vec sampled negative
words according to the distribution of word frequency. Goldberg et al.[147]
attempted to explain negative sampling in word2vec. To alleviate the gradient
vanishing issue in the skip-gram model with word-frequency negative sampling,
Chen et al. [36] dynamically selected informative negative samples based on
self-embedded features. Rao et al. [37] proposed three negative sampling
strategies for negative answer selection, comprising random sampling, max
sampling, and mix sampling. These sampling methods also be applied to open-
domain dialogue systems for negative response selection [116]. Besides, Li et
al. [116] also proposed a semi-hard sampling method where negatives satisfied
a margin constraint. Negative sampling is an effective technique for named
entity recognition (NER) models, which suffer greatly from unlabeled entity
problems. Li et al. [148] leveraged negative sampling to randomly sample a
small subset of unlabeled instances rather than the whole set. After that, Li
et al. [149] designed a weighted sampling distribution to replace random
sampling for boosting performance.

In sentence embedding learning [150, 97, 151], negative sampling plays a vital
role in enhancing model performance by facilitating the distinction between
semantically similar and dissimilar sentences. This technique has evolved from
basic random sampling to more sophisticated strategies. Guo et al. [150]
proposed a hard negative mining method for bilingual sentence embedding
learning, in which selected examples are close to the positive translation in
semantic embedding space. Recently, contrastive learning for sentence
embedding learning has achieved tremendous progress. CLEAR [151] proposed
sentence-level data augmentation for contrastive sentence representation
learning, including word deletion, reordering, and substitution. SimCSE [97]
proposed a model-level data augmentation that passed the same sentence twice
with different dropout probabilities. The abovementioned methods focus on the
sampling method for positive pairs where negatives come from the current mini-
batch. CLINE [152] selected semantic negative examples in embedding space.
MoCoSE [64] leveraged negative sample queue to obtain better performance.
VaSCL [102] proposed neighborhood constrained contrastive learning, which
utilized KNN to obtain top-K similar negatives from the current batch as hard
negatives. SNCSE [103] utilized soft negative samples to enhance unsupervised
sentence embedding learning where soft negatives were defined as the negation
of original sentences with similar textual but different semantics. MixCSE
[153] adopted a mixing operation to synthesize hard negatives for unsupervised
sentence representation learning.

In recent years, dense retrieval (DR) models have become a dominant technique
to solve the semantic match problem [154, 127, 126]. Negative sampling is an
indispensable component for training DR models. EBR [155] adopted a random
sampling strategy to select negatives for embedding-based retrieval models,
which leveraged the triplet loss for the recall optimization task. To improve
the efficiency with the demand of a large number of negatives, several works
[154, 126, 127] employed In-batch NS where other examples in the same mini-
batch are treated as negatives. In fact, In-batch NS is approximately
equivalent to random negative sampling. Moreover, the experimental results in
RocketQA [127] demonstrated that it is beneficial to increase the number of
negatives by introducing cross-batch negatives. Another popular direction is
to apply hard negatives to train DR models. Gillick et al. [154] selected the
most similar 10 entities based on the current model as hard negatives.
Karpukhin et al. [126] utilized top passages generated by BM25 as hard
negatives. Xiong et al. [104] proposed Approximate nearest neighbor Negative
Contrastive Learning (ANCE) to select hard negatives by an ANN index.
Different from static hard negative sampling methods, Zhan et al. [131]
designed a dynamic hard negative sampling method, which utilized a trainable
query encoder to retrieve the most challenging documents as hard negatives.

In summary, negative sampling in natural language processing still leaves a
lot of room for exploration. For example, how to develop a better In-batch NS
to mine hard negatives and simultaneously mitigate the false negative issue?

###  4.5 Negative Sampling in CV

After several decades of sustained effort, a large number of supervised
methods have achieved significant improvements in computer vision (CV), which
leveraged large datasets with labeled examples to learn visual
representations. However, large-scale datasets with labels require human
annotation, which is very expensive and hurts applications on the Internet
scale. Contrastive learning for unsupervised visual representation learning
becomes a natural way to address this issue, which aims to learn visual
embeddings on unlabeled data. Recent developments [85, 156, 157, 49, 48] in
unsupervised visual representation learning present a promising potential by
using contrastive loss, which aims to contrastive positive pairs and negative
pairs. Besides, metric learning is one of the basic learning ways for computer
vision.

Generally, negative examples can be obtained either within a mini-batch or
from a memory bank. In-batch negative sampling [48, 156] samples negatives
from the current mini-batch. Memory-based negative sampling [85, 158, 157]
samples negatives from a memory bank that stores mini-batch samples from
previous batches. MoCo [49] argued that larger batch sizes play a significant
role in model learning and maintained a queue to accumulate a large number of
features that serve as negative samples for model training. SimCLR [48]
proposed a simple framework for contrastive learning, which used all other
images in the current batch as negative samples. Without the assistance of
labels, the false negative issue is an inevitable problem in contrastive
learning, which sampled true label examples from the data distribution. To
address this, Chuang et al. [15] proposed a debiased contrastive loss (DCL)
that corrected the weights of negatives in the objective. After that, Huynh et
al. [130] proposed false negative cancellation strategies consisting of
elimination and attraction to improve contrastive learning. Besides, Cai et
al. [53] conducted an empirical study to analyze the importance of negative
samples and concluded that only 5% hardest negatives are necessary for high-
accuracy contrastive learning. Wang et al. [159] investigated the behavior of
contrastive loss and concluded that loss optimization automatically focuses on
hard negative samples which can be controlled by the temperature. To improve
the performance and efficiency of contrastive learning, most strategies focus
on hard negative sampling. MoCHi [16] proposed hard negative mixing strategies
for contrastive learning to boost model learning, which synthesized hard
negatives by mixing the hardest negatives and a positive query in the
embedding space. Wu et al. [18] proposed conditional negative sampling to
sample negatives within a ring where negatives in the ring are close but not
too close to the positive example. Such a method is similar to the semi-hard
negative sampling method. Similarly, Xie et al. [51] proposed four negative
sampling strategies based on the cosine distance criterion between the anchor
and negative candidates, comprised of hard, semi-hard, random, and semi-easy.
HCL [17] proposed an efficient hard negative sampling method that rewrote the
important weights of each negative example, which assigned higher weights to
negatives that are close to the anchor. Different from hard negative sampling
that only selects hard negatives, HCL adopted DCL to alleviate the false
negative issue. Ge et al. [160] designed texture-based and patch-based
negative sampling strategies to generate hard negative from the input images,
which motivated the model to learn more semantics rather than superficial
features. In addition, several works [73, 50] leveraged adversarial learning
to improve contrastive learning. For example, CLAE [73] utilized adversarial
examples and adversarial training for contrastive learning to generate hard
negative examples. AdCo [50] adopted GAN for contrastive learning for sampling
more informative negative samples. In addition, time-contrastive learning
[161, 162, 163] is particularly applied to video data where positive and
negative examples for learning are drawn from different timestamps within
video sequences. In this framework, the same time step across different camera
views is similar (positive samples), while frames from different time steps
are dissimilar (negative samples).

Furthermore, numerous methods [13, 110, 41] in computer vision are designed on
the triple loss based on metric learning by leveraging a max-margin approach
to distinguish positive pairs from negative pairs, which are widely used in
object detection, image classification, and face recognition. The easiest
negative sampling method is random sampling. However, most randomly sampled
negative examples are easy examples that easily satisfy the margin constraint,
which contributes less to the gradients. To address this problem, [108]
focused on mining hard negative examples that are close in embedding space to
enhance the learning process. Wang et al. [110] mined hard negative triples
after 10 epochs of training with randomly sampled negatives. However, mining
hard negatives requires searching the whole training set, which is
computationally expensive. Besides, the results in FaceNet [13] showed that
the hardest negative examples significantly decrease the convergence speed and
proposed a semi-hard negative mining strategy. To reduce the computational
complexity, Mao et al. [164] sampled semi-hard negative examples from a mini-
batch rather than the entire training set. Wu et al. [14] proposed a distance-
weighted negative sampling strategy to optimize the triple loss. Iscen et al.
[165] mined hard negatives for an anchor from its nearest Euclidean neighbors
rather than manifold neighbors defined over the Euclidean nearest neighbor
graph. HDC [166] proposed a hard-aware deeply cascaded embedding to sample
negatives from different hard levels of samples. Harwood et al. [59] proposed
a smart negative sampling strategy for deep metric learning to sample a smart
negative with a tuning variable and approximate positive examples. Although
hard negatives provide large gradients for model optimization, are easy
negatives really useless for metric learning? DAML [75] argued that easy
negatives should not be neglected since these play a supplementary role in
hard negatives, which utilized a hard negative generator to synthesize hard
negatives from easy ones. Here, we plot a figure to intuitively illustrate the
selection of negative examples in metric learning (See Figure 11). Hard
negative mining samples negatives that are too close to the anchor, which
leads to a high variance on the gradient and hinders the model from learning
better representations. Semi-hard negative mining selects negatives that are
challenging yet not overwhelmingly so, promising the similarity of the
positive pair is higher than the negatives.

Figure 11: The selection of negative examples in computer vision based on
metric learning.

In summary, negative sampling in computer vision has left us a lot of room to
explore. For example, how many negative samples are the best choices? Due to
the emergence of negative-free methods, are negative samples really needed?

##  5 Discussion and Future Directions

In this section, we discuss several open problems in negative sampling and
provide future directions for negative sampling to facilitate the development
of this field. Is negative sampling necessary? If not, what kind of training
paradigm is needed, and if so, how many negative samples are needed, and what
quality of negative samples are needed?

Non-Sampling. Despite a myriad of negative sampling methods that have emerged
recently, another hot direction is a non-sampling strategy that takes all
negative samples into consideration in model optimization. Non-sampling
strategy generally assigns lower weights for negative samples compared to
positive ones. Such a setting is consistent with our intuition that positive
samples should be evaluated with higher weights than negative ones. Due to the
efficiency of non-sampling strategy, several efforts [167, 168, 169, 170]
focus on promoting the efficiency of mini-batch Stochastic Gradient Descent
(SGD) based methods. For example, Chen et al. [168] adopted non-sampling
strategies for recommendation. Such a non-sampling strategy is also applicable
for knowledge graph embedding learning [170] and word embedding [167].
Although the non-sampling strategy can provide a more stable way for model
optimization, its efficiency is a non-negligible issue. How to design a more
efficient method for model optimization incorporated with a non-sampling
strategy? Furthermore, a non-sampling strategy for other domains is not fully
explored.

Getting Rid of Negative Sampling. Due to the quality and quantity of negative
samples playing a significant impact on downstream performance, several works
[171, 172, 173, 174] attempt to get rid of negative sampling and adopt other
paradigms for model learning. SwAV [171] adopted online clustering to compare
the consistency between cluster assignments rather than image features, which
did not require explicit negative instances for unsupervised visual learning.
BYOL [172] only utilized positive pairs without negative pairs for self-
supervised learning, which adopted two neural networks to directly achieve
prediction from one view to another view for the same image. SimSiam [173]
presented a simple siamese network for representation learning, which also
discards negative sample pairs. BGRL [174] also alleviates negative sampling
for large-scale graph representation learning. Furthermore, generative self-
supervised learning methods without negative sampling have been successfully
applied in NLP [26], CV [175] and graph [176]. Thus, a promising research
direction is to explore new learning methods or other alternatives to negative
sampling.

The Quantity of Negative Samples. How many negative samples are needed? Arora
et al. [177] proposed a theoretical analysis for contrastive learning to
demonstrate a performance degradation by using larger negative samples. Wu et
al. [178] proposed an adaptive negative sampling (ANS) method to dynamically
adjust the ratio during the training process. Ash et al. [179] continued to
investigate the number of negative examples in contrastive learning and
revealed that the selection of optimal negative example size relies on the
underlying concepts in the data. To address this gap between the theoretical
analysis and empirical results, Nozawa et al. [180] proposed a lower bound for
self-supervised learning, which aimed to adjust collision probability
according to the number of negative samples. Recently, Awasthi et al. [181]
argued that a collision-coverage trade-off is not an inherent property in
contrastive learning, and claimed that the downstream performance does not
degrade with the increasing of negative examples in a simple theoretical
setting. Furthermore, Sohn [182] proposed an N-pair loss by adopting multiple
negative samples for boosting deep metric learning. Although some works
attempt to explain or explore the impact of negative sample size, there is
still no one answer to what is the standard of negative sample size for a
specific domain or even task. In practical applications, the quantity of
negative samples is determined by a large number of trials. In the future, we
are eager to obtain a criterion for a negative sample size.

The Quality of Negative Samples. Are the hardest negative samples the best
ones? Does model optimization really not require easy negative samples?
Results in several efforts demonstrated that easy negative samples play a
crucial role in the early training stage. For example, Wang et al. [110]
conducted random sampling to mine easy negatives in the first 10 epochs before
mining hard negatives. CuCo [100] utilized curriculum learning to mine
negative samples from easy to hard. DAML [75] highlighted the importance of
easy negative samples for early stable training. Furthermore, many works have
demonstrated that the hardest negative samples are not beneficial for model
stability and robustness. For example, FaceNet [13] proposed semi-hard
negative samples. Wu et al. [18] proposed to sample negatives with a ring
constraint. Therefore, hard negative sampling should fully consider easy
negatives and control the hardness of hard negatives. How to naturally and
dynamically add easy negatives into hard negative sampling is a vital and
worth exploring problem. Hardness of negative samples for model optimization
is also a valuable research direction.

False Negative Issue. As a common and inevitable challenge for negative
sampling, the false negative issue mainly comes from two aspects. The first is
derived from unlabeled data in contrastive learning. Negative sampling in
contrastive learning simultaneously focuses on mining hard negatives and
mitigating the false negative issue. The second is that false negative
instances naturally exist in implicit feedback in the recommendation domain.
Although some strategies are employed to alleviate the false negative issue,
it is impossible to eliminate this issue fundamentally under the paradigm of
contrastive learning. Generative self-supervised learning can completely avoid
this issue, which gets rid of negative sampling and becomes a powerful
alternative for contrastive learning in unsupervised representation learning.
In summary, alleviating or even eliminating the false negative issue is a
meaningful research direction.

##  6 Conclusion

In this survey, we have conducted an extensive review of the landscape of
negative sampling techniques across a multitude of domains. Negative sampling
is a fundamental technique in machine learning, which can accelerate the
training process and boost downstream performance. We summarize a general
negative sampling framework and develop a tool that contains many negative
sampling methods among various domains. The selection methods for negative
candidates are summarized, including global, local, mini-batch, hop, and
memory-based. Besides, we categorize all existing negative sampling methods
into five groups (static, hard, GAN-based, Auxiliary-based, and In-batch) and
demonstrate their pros and cons. Furthermore, we illustrate negative sampling
applications in various domains. Finally, open problems and future directions
of negative sampling are presented.

## Acknowledgments

This work is supported by the National Key Research and Development Program of
China 2021YFF1201300, the NSFC for Distinguished Young Scholar 61825602 and
the New Cornerstone Science Foundation through the XPLORER PRIZE.

## References

  * [1] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” _NIPS_ , vol. 26, 2013.
  * [2] S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme, “Bpr: Bayesian personalized ranking from implicit feedback,” _arXiv preprint arXiv:1205.2618_ , 2012.
  * [3] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _KDD_ , 2014, pp. 701–710.
  * [4] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in _WWW_ , 2015, pp. 1067–1077.
  * [5] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _KDD_ , 2016, pp. 855–864.
  * [6] Z. Yang, M. Ding, C. Zhou, H. Yang, J. Zhou, and J. Tang, “Understanding negative sampling in graph representation learning,” in _KDD_ , 2020, pp. 1666–1676.
  * [7] T. Huang, Y. Dong, M. Ding, Z. Yang, W. Feng, X. Wang, and J. Tang, “Mixgcf: An improved training method for graph neural network-based recommender systems,” in _KDD_ , 2021, pp. 665–674.
  * [8] D. Krompaß, S. Baier, and V. Tresp, “Type-constrained representation learning in knowledge graphs,” in _International semantic web conference_. Springer, 2015, pp. 640–655.
  * [9] L. Cai and W. Y. Wang, “Kbgan: Adversarial learning for knowledge graph embeddings,” _arXiv preprint arXiv:1711.04071_ , 2017.
  * [10] M. Grbovic, N. Djuric, V. Radosavljevic, F. Silvestri, and N. Bhamidipati, “Context-and content-aware embeddings for query rewriting in sponsored search,” in _SIGIR_ , 2015, pp. 383–392.
  * [11] Z. Zhang and P. Zweigenbaum, “Gneg: Graph-based negative sampling for word2vec,” in _ACL_ , 2018, pp. 566–571.
  * [12] X. Wu, C. Gao, L. Zang, J. Han, Z. Wang, and S. Hu, “Esimcse: Enhanced sample building method for contrastive learning of unsupervised sentence embedding,” _arXiv preprint arXiv:2109.04380_ , 2021.
  * [13] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in _CVPR_ , 2015, pp. 815–823.
  * [14] C.-Y. Wu, R. Manmatha, A. J. Smola, and P. Krahenbuhl, “Sampling matters in deep embedding learning,” in _ICCV_ , 2017, pp. 2840–2848.
  * [15] C.-Y. Chuang, J. Robinson, Y.-C. Lin, A. Torralba, and S. Jegelka, “Debiased contrastive learning,” _NIPS_ , vol. 33, pp. 8765–8775, 2020.
  * [16] Y. Kalantidis, M. B. Sariyildiz, N. Pion, P. Weinzaepfel, and D. Larlus, “Hard negative mixing for contrastive learning,” _NIPS_ , vol. 33, pp. 21 798–21 809, 2020.
  * [17] J. Robinson, C.-Y. Chuang, S. Sra, and S. Jegelka, “Contrastive learning with hard negative samples,” _arXiv preprint arXiv:2010.04592_ , 2020.
  * [18] M. Wu, M. Mosse, C. Zhuang, D. Yamins, and N. Goodman, “Conditional negative sampling for contrastive learning of visual representations,” _arXiv preprint arXiv:2010.02037_ , 2020.
  * [19] W. Zhang, T. Chen, J. Wang, and Y. Yu, “Optimizing top-n collaborative filtering via dynamic negative item sampling,” in _SIGIR_ , 2013, pp. 785–788.
  * [20] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko, “Translating embeddings for modeling multi-relational data,” _NIPS_ , vol. 26, 2013.
  * [21] T. Kipf, E. Van der Pol, and M. Welling, “Contrastive learning of structured world models,” _arXiv preprint arXiv:1911.12247_ , 2019.
  * [22] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [23] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [24] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _NIPS_ , vol. 30, 2017.
  * [25] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _CVPR_ , 2016, pp. 770–778.
  * [26] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [27] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov, “Roberta: A robustly optimized bert pretraining approach,” _arXiv preprint arXiv:1907.11692_ , 2019.
  * [28] Z. Wang, J. Zhang, J. Feng, and Z. Chen, “Knowledge graph embedding by translating on hyperplanes,” in _AAAI_ , vol. 28, no. 1, 2014.
  * [29] R. Pan, Y. Zhou, B. Cao, N. N. Liu, R. Lukose, M. Scholz, and Q. Yang, “One-class collaborative filtering,” in _ICDM_. IEEE, 2008, pp. 502–511.
  * [30] H. Xiao, M. Huang, Y. Hao, and X. Zhu, “Transg: A generative mixture model for knowledge graph embedding,” _arXiv preprint arXiv:1509.05488_ , 2015.
  * [31] X. Wang, X. He, M. Wang, F. Feng, and T.-S. Chua, “Neural graph collaborative filtering,” in _SIGIR_ , 2019, pp. 165–174.
  * [32] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang, “Lightgcn: Simplifying and powering graph convolution network for recommendation,” in _SIGIR_ , 2020, pp. 639–648.
  * [33] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” in _CVPR_ , vol. 1. Ieee, 2005, pp. 886–893.
  * [34] P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan, “Object detection with discriminatively trained part-based models,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 32, no. 9, pp. 1627–1645, 2009.
  * [35] T. Malisiewicz, A. Gupta, and A. A. Efros, “Ensemble of exemplar-svms for object detection and beyond,” in _2011 International conference on computer vision_. IEEE, 2011, pp. 89–96.
  * [36] L. Chen, F. Yuan, J. M. Jose, and W. Zhang, “Improving negative sampling for word representation using self-embedded features,” in _WSDM_ , 2018, pp. 99–107.
  * [37] J. Rao, H. He, and J. Lin, “Noise-contrastive estimation for answer selection with deep neural networks,” in _CIKM_ , 2016, pp. 1913–1916.
  * [38] Z. Sun, W. Hu, Q. Zhang, and Y. Qu, “Bootstrapping entity alignment with knowledge graph embedding.” in _IJCAI_ , vol. 18, 2018, pp. 4396–4402.
  * [39] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, “Graph convolutional neural networks for web-scale recommender systems,” in _KDD_ , 2018, pp. 974–983.
  * [40] X. Wang, Y. Xu, X. He, Y. Cao, M. Wang, and T.-S. Chua, “Reinforced negative sampling over knowledge graph for recommendation,” in _WWW_ , 2020, pp. 99–109.
  * [41] A. Shrivastava, A. Gupta, and R. Girshick, “Training region-based object detectors with online hard example mining,” in _CVPR_ , 2016, pp. 761–769.
  * [42] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” _NIPS_ , vol. 27, 2014.
  * [43] J. Wang, L. Yu, W. Zhang, Y. Gong, Y. Xu, B. Wang, P. Zhang, and D. Zhang, “Irgan: A minimax game for unifying generative and discriminative information retrieval models,” in _SIGIR_ , 2017, pp. 515–524.
  * [44] H. Wang, J. Wang, J. Wang, M. Zhao, W. Zhang, F. Zhang, W. Li, X. Xie, and M. Guo, “Learning graph representation with generative adversarial nets,” _TKDE_ , vol. 33, no. 8, pp. 3090–3103, 2019.
  * [45] Q. Wang, H. Yin, Z. Hu, D. Lian, H. Wang, and Z. Huang, “Neural memory streaming recommender networks with adversarial training,” in _KDD_ , 2018, pp. 2467–2475.
  * [46] D.-K. Chae, J.-S. Kang, S.-W. Kim, and J.-T. Lee, “Cfgan: A generic collaborative filtering framework based on generative adversarial networks,” in _CIKM_ , 2018, pp. 137–146.
  * [47] D. H. Park and Y. Chang, “Adversarial sampling and training for semi-supervised information retrieval,” in _WWW_ , 2019, pp. 1443–1453.
  * [48] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _ICML_. PMLR, 2020, pp. 1597–1607.
  * [49] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, “Momentum contrast for unsupervised visual representation learning,” in _CVPR_ , 2020, pp. 9729–9738.
  * [50] Q. Hu, X. Wang, W. Hu, and G.-J. Qi, “Adco: Adversarial contrast for efficient learning of unsupervised representations from self-trained negative adversaries,” in _CVPR_ , 2021, pp. 1074–1083.
  * [51] J. Xie, X. Zhan, Z. Liu, Y. S. Ong, and C. C. Loy, “Delving into inter-image invariance for unsupervised visual representations,” _arXiv preprint arXiv:2008.11702_ , 2020.
  * [52] Z. Yang, T. Huang, M. Ding, Y. Dong, R. Ying, Y. Cen, Y. Geng, and J. Tang, “Batchsampler: Sampling mini-batches for contrastive learning in vision, language, and graphs,” _arXiv preprint arXiv:2306.03355_ , 2023.
  * [53] T. T. Cai, J. Frankle, D. J. Schwab, and A. S. Morcos, “Are all negatives created equal in contrastive instance discrimination?” _arXiv preprint arXiv:2010.06682_ , 2020.
  * [54] H. Caselles-Dupré, F. Lesaint, and J. Royo-Letelier, “Word2vec applied to recommendation: Hyperparameters matter,” in _RecSys_ , 2018, pp. 352–356.
  * [55] B. Yang, W.-t. Yih, X. He, J. Gao, and L. Deng, “Embedding entities and relations for learning and inference in knowledge bases,” _arXiv preprint arXiv:1412.6575_ , 2014.
  * [56] C. Tao, L. Mou, D. Zhao, and R. Yan, “Ruber: An unsupervised method for automatic evaluation of open-domain dialog systems,” in _AAAI_ , 2018.
  * [57] S. Ghazarian, J. T.-Z. Wei, A. Galstyan, and N. Peng, “Better automatic evaluation of open-domain dialogue systems with contextualized embeddings,” _arXiv preprint arXiv:1904.10635_ , 2019.
  * [58] M. Bucher, S. Herbin, and F. Jurie, “Hard negative mining for metric learning based zero-shot classification,” in _ECCV_. Springer, 2016, pp. 524–531.
  * [59] B. Harwood, V. Kumar BG, G. Carneiro, I. Reid, and T. Drummond, “Smart mining for deep metric learning,” in _ICCV_ , 2017, pp. 2821–2829.
  * [60] D. Galanopoulos and V. Mezaris, “Hard-negatives or non-negatives? a hard-negative selection strategy for cross-modal retrieval using the improved marginal ranking loss,” in _ICCV_ , 2021, pp. 2312–2316.
  * [61] S. Rendle and C. Freudenthaler, “Improving pairwise learning for item recommendation from implicit feedback,” in _WSDM_ , 2014, pp. 273–282.
  * [62] X. Mao, W. Wang, Y. Wu, and M. Lan, “Boosting the speed of entity alignment 10$\times$: Dual attention matching network with normalized hard sample mining,” in _WWW_ , 2021, pp. 821–832.
  * [63] Y. Zhang, Q. Yao, Y. Shao, and L. Chen, “Nscaching: simple and efficient negative sampling for knowledge graph embedding,” in _ICDE_. IEEE, 2019, pp. 614–625.
  * [64] R. Cao, Y. Wang, Y. Liang, L. Gao, J. Zheng, J. Ren, and Z. Wang, “Exploring the impact of negative samples of contrastive learning: A case study of sentence embedding,” _arXiv preprint arXiv:2202.13093_ , 2022.
  * [65] F. Che, G. Yang, P. Shao, D. Zhang, and J. Tao, “Mixkg: Mixing for harder negative samples in knowledge graph,” _arXiv preprint arXiv:2202.09606_ , 2022.
  * [66] L. Yu, W. Zhang, J. Wang, and Y. Yu, “Seqgan: Sequence generative adversarial nets with policy gradient,” in _AAAI_ , vol. 31, no. 1, 2017.
  * [67] A. J. Bose, H. Ling, and Y. Cao, “Adversarial contrastive estimation,” _arXiv preprint arXiv:1805.03642_ , 2018.
  * [68] P. Wang, S. Li, and R. Pan, “Incorporating gan for negative sampling in knowledge representation learning,” in _AAAI_ , vol. 32, no. 1, 2018.
  * [69] H. Gao, J. Pei, and H. Huang, “Progan: Network embedding via proximity generative adversarial network,” in _KDD_ , 2019, pp. 1308–1316.
  * [70] B. Hu, Y. Fang, and C. Shi, “Adversarial learning on heterogeneous information networks,” in _KDD_ , 2019, pp. 120–129.
  * [71] P. Gupta, Y. Tsvetkov, and J. P. Bigham, “Synthesizing adversarial negative responses for robust response ranking and evaluation,” _arXiv preprint arXiv:2106.05894_ , 2021.
  * [72] A. Sinha, K. Ayush, J. Song, B. Uzkent, H. Jin, and S. Ermon, “Negative data augmentation,” _arXiv preprint arXiv:2102.05113_ , 2021.
  * [73] C.-H. Ho and N. Nvasconcelos, “Contrastive learning with adversarial examples,” _NIPS_ , vol. 33, pp. 17 081–17 093, 2020.
  * [74] W. Wang, W. Zhou, J. Bao, D. Chen, and H. Li, “Instance-wise hard negative example generation for contrastive learning in unpaired image-to-image translation,” in _ICCV_ , 2021, pp. 14 020–14 029.
  * [75] Y. Duan, W. Zheng, X. Lin, J. Lu, and J. Zhou, “Deep adversarial metric learning,” in _CVPR_ , 2018, pp. 2780–2789.
  * [76] K. Ahrabian, A. Feizi, Y. Salehi, W. L. Hamilton, and A. J. Bose, “Structure aware negative sampling in knowledge graphs,” _arXiv preprint arXiv:2009.11355_ , 2020.
  * [77] J. Chen, C. Wang, S. Zhou, Q. Shi, Y. Feng, and C. Chen, “Samwalker: Social recommendation with informative sampling strategy,” in _WWW_ , 2019, pp. 228–239.
  * [78] Y. Wang, Z. Liu, Z. Fan, L. Sun, and P. S. Yu, “Dskreg: Differentiable sampling on knowledge graph for recommendation with relational gnn,” in _CIKM_ , 2021, pp. 3513–3517.
  * [79] T. Zhao, J. McAuley, and I. King, “Leveraging social connections to improve personalized ranking for collaborative filtering,” in _CIKM_ , 2014, pp. 261–270.
  * [80] J. Manotumruksa, C. Macdonald, and I. Ounis, “A personalised ranking framework with multiple sampling criteria for venue recommendation,” in _CIKM_ , 2017, pp. 1469–1478.
  * [81] B. Loni, R. Pagano, M. Larson, and A. Hanjalic, “Bayesian personalized ranking with multi-channel user feedback,” in _RecSys_ , 2016, pp. 361–364.
  * [82] J. Ding, F. Feng, X. He, G. Yu, Y. Li, and D. Jin, “An improved sampler for bayesian personalized ranking by leveraging view data,” in _WWW_ , 2018, pp. 13–14.
  * [83] J. Ding, Y. Quan, X. He, Y. Li, and D. Jin, “Reinforced negative sampling for recommendation with exposure data.” in _IJCAI_ , 2019, pp. 2230–2236.
  * [84] Z. Yang, M. Ding, X. Zou, J. Tang, B. Xu, C. Zhou, and H. Yang, “Region or global a principle for negative sampling in graph-based recommendation,” _TKDE_ , 2022.
  * [85] Z. Wu, Y. Xiong, S. X. Yu, and D. Lin, “Unsupervised feature learning via non-parametric instance discrimination,” in _CVPR_ , 2018, pp. 3733–3742.
  * [86] J. Ding, Y. Quan, Q. Yao, Y. Li, and D. Jin, “Simplify and robustify negative sampling for implicit collaborative filtering,” _NIPS_ , vol. 33, pp. 1094–1105, 2020.
  * [87] X. Chen, H. Fan, R. Girshick, and K. He, “Improved baselines with momentum contrastive learning,” _arXiv preprint arXiv:2003.04297_ , 2020.
  * [88] J. Qiu, Q. Chen, Y. Dong, J. Zhang, H. Yang, M. Ding, K. Wang, and J. Tang, “Gcc: Graph contrastive coding for graph neural network pre-training,” in _KDD_ , 2020, pp. 1150–1160.
  * [89] T. Chen, Y. Sun, Y. Shi, and L. Hong, “On sampling strategies for neural network-based collaborative filtering,” in _KDD_ , 2017, pp. 767–776.
  * [90] K. Zhou, H. Wang, W. X. Zhao, Y. Zhu, S. Wang, F. Zhang, Z. Wang, and J.-R. Wen, “S3-rec: Self-supervised learning for sequential recommendation with mutual information maximization,” in _CIKM_ , 2020, pp. 1893–1902.
  * [91] J. Wu, X. Wang, F. Feng, X. He, L. Chen, J. Lian, and X. Xie, “Self-supervised graph learning for recommendation,” in _SIGIR_ , 2021, pp. 726–735.
  * [92] J. Yu, H. Yin, J. Li, Q. Wang, N. Q. V. Hung, and X. Zhang, “Self-supervised multi-channel hypergraph convolutional network for social recommendation,” in _WWW_ , 2021, pp. 413–424.
  * [93] X. Xia, H. Yin, J. Yu, Q. Wang, L. Cui, and X. Zhang, “Self-supervised hypergraph convolutional networks for session-based recommendation,” in _AAAI_ , vol. 35, no. 5, 2021, pp. 4503–4511.
  * [94] K. Hassani and A. H. Khasahmadi, “Contrastive multi-view representation learning on graphs,” in _ICML_. PMLR, 2020, pp. 4116–4126.
  * [95] Y. Zhu, Y. Xu, F. Yu, Q. Liu, S. Wu, and L. Wang, “Deep graph contrastive representation learning,” _arXiv preprint arXiv:2006.04131_ , 2020.
  * [96] Y. You, T. Chen, Y. Sui, T. Chen, Z. Wang, and Y. Shen, “Graph contrastive learning with augmentations,” _NIPS_ , vol. 33, pp. 5812–5823, 2020.
  * [97] T. Gao, X. Yao, and D. Chen, “Simcse: Simple contrastive learning of sentence embeddings,” _arXiv preprint arXiv:2104.08821_ , 2021.
  * [98] L. Kong, C. d. M. d’Autume, W. Ling, L. Yu, Z. Dai, and D. Yogatama, “A mutual information maximization perspective of language representation learning,” _arXiv preprint arXiv:1910.08350_ , 2019.
  * [99] H. Zhao, X. Yang, Z. Wang, E. Yang, and C. Deng, “Graph debiased contrastive learning with joint representation clustering.” in _IJCAI_ , 2021, pp. 3434–3440.
  * [100] G. Chu, X. Wang, C. Shi, and X. Jiang, “Cuco: Graph representation with curriculum contrastive learning.” in _IJCAI_ , 2021, pp. 2300–2306.
  * [101] J. Xia, L. Wu, G. Wang, J. Chen, and S. Z. Li, “Progcl: Rethinking hard negative mining in graph contrastive learning,” in _ICML_. PMLR, 2022, pp. 24 332–24 346.
  * [102] D. Zhang, W. Xiao, H. Zhu, X. Ma, and A. O. Arnold, “Virtual augmentation supported contrastive learning of sentence representations,” _arXiv preprint arXiv:2110.08552_ , 2021.
  * [103] H. Wang, Y. Li, Z. Huang, Y. Dou, L. Kong, and J. Shao, “Sncse: Contrastive learning for unsupervised sentence embedding with soft negative samples,” _arXiv preprint arXiv:2201.05979_ , 2022.
  * [104] L. Xiong, C. Xiong, Y. Li, K.-F. Tang, J. Liu, P. Bennett, J. Ahmed, and A. Overwijk, “Approximate nearest neighbor negative contrastive learning for dense text retrieval,” _arXiv preprint arXiv:2007.00808_ , 2020.
  * [105] H. Rowley, S. Baluja, and T. Kanade, “Human face detection in visual scenes,” _NIPS_ , vol. 8, 1995.
  * [106] K.-K. Sung and T. Poggio, “Example-based learning for view-based human face detection,” _TPAMI_ , vol. 20, no. 1, pp. 39–51, 1998.
  * [107] V.-A. Tran, R. Hennequin, J. Royo-Letelier, and M. Moussallam, “Improving collaborative metric learning with efficient negative sampling,” in _SIGIR_ , 2019, pp. 1201–1204.
  * [108] E. Simo-Serra, E. Trulls, L. Ferraz, I. Kokkinos, P. Fua, and F. Moreno-Noguer, “Discriminative learning of deep convolutional feature point descriptors,” in _ICCV_ , 2015, pp. 118–126.
  * [109] I. Loshchilov and F. Hutter, “Online batch selection for faster training of neural networks,” _arXiv preprint arXiv:1511.06343_ , 2015.
  * [110] X. Wang and A. Gupta, “Unsupervised learning of visual representations using videos,” in _ICCV_ , 2015, pp. 2794–2802.
  * [111] J. Weston, S. Bengio, and N. Usunier, “Wsabie: Scaling up to large vocabulary image annotation,” in _IJCAI_ , 2011.
  * [112] T. Zhao, J. McAuley, and I. King, “Improving latent factor models via personalized feature projection for one class recommendation,” in _CIKM_ , 2015, pp. 821–830.
  * [113] G. Guo, S. Ouyang, F. Yuan, and X. Wang, “Approximating word ranking and negative sampling for word embedding.” IJCAI, 2018.
  * [114] F. Faghri, D. J. Fleet, J. R. Kiros, and S. Fidler, “Vse++: Improving visual-semantic embeddings with hard negatives,” _arXiv preprint arXiv:1707.05612_ , 2017.
  * [115] G. Guo, S. Zhai, F. Yuan, Y. Liu, and X. Wang, “Vse-ens: Visual-semantic embeddings with efficient negative sampling,” in _AAAI_ , vol. 32, no. 1, 2018.
  * [116] J. Li, C. Tao, W. Wu, Y. Feng, D. Zhao, and R. Yan, “Sampling matters! an empirical study of negative sampling strategies for learning of matching models in retrieval-based dialogue systems,” in _EMNLP-IJCNLP_ , 2019, pp. 1291–1296.
  * [117] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz, “mixup: Beyond empirical risk minimization,” _arXiv preprint arXiv:1710.09412_ , 2017.
  * [118] T.-S. Chen, W.-C. Hung, H.-Y. Tseng, S.-Y. Chien, and M.-H. Yang, “Incremental false negative detection for contrastive learning,” _arXiv preprint arXiv:2106.03719_ , 2021.
  * [119] C. Yang, Q. Wu, J. Jin, X. Gao, J. Pan, and G. Chen, “Trading hard negatives and true negatives: A debiased contrastive collaborative filtering approach,” _arXiv preprint arXiv:2204.11752_ , 2022.
  * [120] R. J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning,” _Machine learning_ , vol. 8, no. 3, pp. 229–256, 1992.
  * [121] C. Chen, Y. Xie, S. Lin, R. Qiao, J. Zhou, X. Tan, Y. Zhang, and L. Ma, “Novelty detection via contrastive learning with negative data augmentation,” _arXiv preprint arXiv:2106.09958_ , 2021.
  * [122] C. Wang, J. Chen, S. Zhou, Q. Shi, Y. Feng, and C. Chen, “Samwalker++: recommendation with informative sampling strategy,” _TKDE_ , 2021.
  * [123] H. Fang, S. Wang, M. Zhou, J. Ding, and P. Xie, “Cert: Contrastive self-supervised learning for language understanding,” _arXiv preprint arXiv:2005.12766_ , 2020.
  * [124] M. Ye, X. Zhang, P. C. Yuen, and S.-F. Chang, “Unsupervised embedding learning via invariant and spreading instance feature,” in _CVPR_ , 2019, pp. 6210–6219.
  * [125] X. Yi, J. Yang, L. Hong, D. Z. Cheng, L. Heldt, A. Kumthekar, Z. Zhao, L. Wei, and E. Chi, “Sampling-bias-corrected neural modeling for large corpus item recommendations,” in _RecSys_ , 2019, pp. 269–277.
  * [126] V. Karpukhin, B. Oğuz, S. Min, P. Lewis, L. Wu, S. Edunov, D. Chen, and W.-t. Yih, “Dense passage retrieval for open-domain question answering,” _arXiv preprint arXiv:2004.04906_ , 2020.
  * [127] Y. Qu, Y. Ding, J. Liu, K. Liu, R. Ren, W. X. Zhao, D. Dong, H. Wu, and H. Wang, “Rocketqa: An optimized training approach to dense passage retrieval for open-domain question answering,” _arXiv preprint arXiv:2010.08191_ , 2020.
  * [128] Y. Zhu, Y. Xu, F. Yu, Q. Liu, S. Wu, and L. Wang, “Graph contrastive learning with adaptive augmentation,” in _WWW_ , 2021, pp. 2069–2080.
  * [129] K. Zhou, B. Zhang, W. X. Zhao, and J.-R. Wen, “Debiased contrastive learning of unsupervised sentence representations,” _arXiv preprint arXiv:2205.00656_ , 2022.
  * [130] T. Huynh, S. Kornblith, M. R. Walter, M. Maire, and M. Khademi, “Boosting contrastive self-supervised learning with false negative cancellation,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2022, pp. 2785–2795.
  * [131] J. Zhan, J. Mao, Y. Liu, J. Guo, M. Zhang, and S. Ma, “Optimizing dense retrieval model training with hard negatives,” in _SIGIR_ , 2021, pp. 1503–1512.
  * [132] O. Barkan and N. Koenigstein, “Item2vec: neural item embedding for collaborative filtering,” in _MLSP_. IEEE, 2016, pp. 1–6.
  * [133] H.-F. Yu, M. Bilenko, and C.-J. Lin, “Selection of negative samples for one-class matrix factorization,” in _ICDM_. SIAM, 2017, pp. 363–371.
  * [134] D. Lian, Q. Liu, and E. Chen, “Personalized ranking with importance sampling,” in _Proceedings of The Web Conference 2020_ , 2020, pp. 1093–1103.
  * [135] B. Jin, D. Lian, Z. Liu, Q. Liu, J. Ma, X. Xie, and E. Chen, “Sampling-decomposable generative adversarial recommender,” _NIPS_ , vol. 33, pp. 22 629–22 639, 2020.
  * [136] R. v. d. Berg, T. N. Kipf, and M. Welling, “Graph convolutional matrix completion,” _arXiv preprint arXiv:1706.02263_ , 2017.
  * [137] S. Wu, Y. Tang, Y. Zhu, L. Wang, X. Xie, and T. Tan, “Session-based recommendation with graph neural networks,” in _AAAI_ , vol. 33, no. 01, 2019, pp. 346–353.
  * [138] H. Gao and H. Huang, “Self-paced network embedding,” in _KDD_ , 2018, pp. 1406–1415.
  * [139] M. Armandpour, P. Ding, J. Huang, and X. Hu, “Robust negative sampling for network embedding,” in _AAAI_ , vol. 33, no. 01, 2019, pp. 3191–3198.
  * [140] Y. Zhu, Y. Xu, H. Cui, C. Yang, Q. Liu, and S. Wu, “Structure-enhanced heterogeneous graph contrastive learning,” in _SDM_. SIAM, 2022, pp. 82–90.
  * [141] V. Kanojia, H. Maeda, R. Togashi, and S. Fujita, “Enhancing knowledge graph embedding with probabilistic negative sampling,” in _WWW_ , 2017, pp. 801–802.
  * [142] B. Kotnis and V. Nastase, “Analysis of the impact of negative sampling on link prediction in knowledge graphs,” _arXiv preprint arXiv:1708.06816_ , 2017.
  * [143] Z. Sun, Z.-H. Deng, J.-Y. Nie, and J. Tang, “Rotate: Knowledge graph embedding by relational rotation in complex space,” _arXiv preprint arXiv:1902.10197_ , 2019.
  * [144] Y. Shan, C. Bu, X. Liu, S. Ji, and L. Li, “Confidence-aware negative sampling method for noisy knowledge graph embedding,” in _ICBK_. IEEE, 2018, pp. 33–40.
  * [145] M. K. Islam, S. Aridhi, and M. Smaïl-Tabbone, “Simple negative sampling for link prediction in knowledge graphs,” in _International Conference on Complex Networks and Their Applications_. Springer, 2021, pp. 549–562.
  * [146] S. Qin, G. Rao, C. Bin, L. Chang, T. Gu, and W. Xuan, “Knowledge graph embedding based on adaptive negative sampling,” in _International Conference of Pioneering Computer Scientists, Engineers and Educators_. Springer, 2019, pp. 551–563.
  * [147] Y. Goldberg and O. Levy, “word2vec explained: deriving mikolov et al.’s negative-sampling word-embedding method,” _arXiv preprint arXiv:1402.3722_ , 2014.
  * [148] Y. Li, L. Liu, and S. Shi, “Empirical analysis of unlabeled entity problem in named entity recognition,” _arXiv preprint arXiv:2012.05426_ , 2020.
  * [149] Y. Li, L. Liu, and S. Shi, “Rethinking negative sampling for handling missing entity annotations,” in _ACL_ , 2022, pp. 7188–7197.
  * [150] M. Guo, Q. Shen, Y. Yang, H. Ge, D. Cer, G. H. Abrego, K. Stevens, N. Constant, Y.-H. Sung, B. Strope _et al._ , “Effective parallel corpus mining using bilingual sentence embeddings,” _arXiv preprint arXiv:1807.11906_ , 2018.
  * [151] Z. Wu, S. Wang, J. Gu, M. Khabsa, F. Sun, and H. Ma, “Clear: Contrastive learning for sentence representation,” _arXiv preprint arXiv:2012.15466_ , 2020.
  * [152] D. Wang, N. Ding, P. Li, and H.-T. Zheng, “Cline: Contrastive learning with semantic negative examples for natural language understanding,” _arXiv preprint arXiv:2107.00440_ , 2021.
  * [153] Y. Zhang, R. Zhang, S. Mensah, X. Liu, and Y. Mao, “Unsupervised sentence representation via contrastive learning with mixing negatives,” 2022.
  * [154] D. Gillick, S. Kulkarni, L. Lansing, A. Presta, J. Baldridge, E. Ie, and D. Garcia-Olano, “Learning dense representations for entity retrieval,” _arXiv preprint arXiv:1909.10506_ , 2019.
  * [155] J.-T. Huang, A. Sharma, S. Sun, L. Xia, D. Zhang, P. Pronin, J. Padmanabhan, G. Ottaviano, and L. Yang, “Embedding-based retrieval in facebook search,” in _KDD_ , 2020, pp. 2553–2561.
  * [156] A. v. d. Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” _arXiv preprint arXiv:1807.03748_ , 2018.
  * [157] Y. Tian, D. Krishnan, and P. Isola, “Contrastive multiview coding,” in _ECCV_. Springer, 2020, pp. 776–794.
  * [158] I. Misra and L. v. d. Maaten, “Self-supervised learning of pretext-invariant representations,” in _CVPR_ , 2020, pp. 6707–6717.
  * [159] F. Wang and H. Liu, “Understanding the behaviour of contrastive loss,” in _CVPR_ , 2021, pp. 2495–2504.
  * [160] S. Ge, S. Mishra, C.-L. Li, H. Wang, and D. Jacobs, “Robust contrastive learning using negative samples with diminished semantics,” _NIPS_ , vol. 34, pp. 27 356–27 368, 2021.
  * [161] P. Sermanet, K. Xu, and S. Levine, “Unsupervised perceptual rewards for imitation learning,” _arXiv preprint arXiv:1612.06699_ , 2016.
  * [162] P. Sermanet, C. Lynch, Y. Chebotar, J. Hsu, E. Jang, S. Schaal, S. Levine, and G. Brain, “Time-contrastive networks: Self-supervised learning from video,” in _2018 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2018, pp. 1134–1141.
  * [163] S. Nair, A. Rajeswaran, V. Kumar, C. Finn, and A. Gupta, “R3m: A universal visual representation for robot manipulation,” _arXiv preprint arXiv:2203.12601_ , 2022.
  * [164] C. Mao, Z. Zhong, J. Yang, C. Vondrick, and B. Ray, “Metric learning for adversarial robustness,” _NIPS_ , vol. 32, 2019.
  * [165] A. Iscen, G. Tolias, Y. Avrithis, and O. Chum, “Mining on manifolds: Metric learning without labels,” in _CVPR_ , 2018, pp. 7642–7651.
  * [166] Y. Yuan, K. Yang, and C. Zhang, “Hard-aware deeply cascaded embedding,” in _ICCV_ , 2017, pp. 814–823.
  * [167] X. Xin, Y. Fajie, H. Xiangnan, and J. Joemon, “Batch is not heavy: Learning word embeddings from all samples,” in _ACL_ , vol. 8, 2018, pp. 107–132.
  * [168] C. Chen, M. Zhang, C. Wang, W. Ma, M. Li, Y. Liu, and S. Ma, “An efficient adaptive transfer neural network for social-aware recommendation,” in _SIGIR_ , 2019, pp. 225–234.
  * [169] C. Chen, M. Zhang, Y. Zhang, Y. Liu, and S. Ma, “Efficient neural matrix factorization without sampling for recommendation,” _TOIS_ , vol. 38, no. 2, pp. 1–28, 2020.
  * [170] C. Chen, M. Zhang, W. Ma, Y. Liu, and S. Ma, “Jointly non-sampling learning for knowledge graph enhanced recommendation,” in _SIGIR_ , 2020, pp. 189–198.
  * [171] M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin, “Unsupervised learning of visual features by contrasting cluster assignments,” _NIPS_ , vol. 33, pp. 9912–9924, 2020.
  * [172] J.-B. Grill, F. Strub, F. Altché, C. Tallec, P. Richemond, E. Buchatskaya, C. Doersch, B. Avila Pires, Z. Guo, M. Gheshlaghi Azar _et al._ , “Bootstrap your own latent-a new approach to self-supervised learning,” _NIPS_ , vol. 33, pp. 21 271–21 284, 2020.
  * [173] X. Chen and K. He, “Exploring simple siamese representation learning,” in _CVPR_ , 2021, pp. 15 750–15 758.
  * [174] S. Thakoor, C. Tallec, M. G. Azar, M. Azabou, E. L. Dyer, R. Munos, P. Veličković, and M. Valko, “Large-scale representation learning on graphs via bootstrapping,” _arXiv preprint arXiv:2102.06514_ , 2021.
  * [175] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick, “Masked autoencoders are scalable vision learners,” in _CVPR_ , 2022, pp. 16 000–16 009.
  * [176] Z. Hou, X. Liu, Y. Dong, C. Wang, J. Tang _et al._ , “Graphmae: Self-supervised masked graph autoencoders,” _arXiv preprint arXiv:2205.10803_ , 2022.
  * [177] S. Arora, H. Khandeparkar, M. Khodak, O. Plevrakis, and N. Saunshi, “A theoretical analysis of contrastive unsupervised representation learning,” _arXiv preprint arXiv:1902.09229_ , 2019.
  * [178] C. Wu, F. Wu, and Y. Huang, “Rethinking infonce: How many negative samples do you need?” _arXiv preprint arXiv:2105.13003_ , 2021.
  * [179] J. T. Ash, S. Goel, A. Krishnamurthy, and D. Misra, “Investigating the role of negatives in contrastive representation learning,” _arXiv preprint arXiv:2106.09943_ , 2021.
  * [180] K. Nozawa and I. Sato, “Understanding negative samples in instance discriminative self-supervised representation learning,” _NIPS_ , vol. 34, pp. 5784–5797, 2021.
  * [181] P. Awasthi, N. Dikkala, and P. Kamath, “Do more negative samples necessarily hurt in contrastive learning?” _arXiv preprint arXiv:2205.01789_ , 2022.
  * [182] K. Sohn, “Improved deep metric learning with multi-class n-pair loss objective,” _NIPS_ , vol. 29, 2016.

|  Zhen Yang is a PhD candidate in the Department of Computer Science and
Technology, Tsinghua University. She got her master’s degree from the
Institute of Microelectronics, Tsinghua University. Her research interests
include graph representation learning, graph-based recommendation, contrastive
learning, and large language models (LLMs). She has published some papers on
top conferences and journals, such as KDD, WWW, AAAI, ICCV and TKDE.
---|---
|  Ming Ding obtained his Ph.D. degree in 2023 from the Department of Computer
Science and Technology, Tsinghua University. He is currently working at Zhipu
AI. His research interests include graph learning, natural language processing
and cognitive artificial intelligence. He has published many papers on top
conferences, such as NeurIPS, KDD, ACL, IJCAI, etc.
---|---
|  Tinglin Huang Tinglin Huang is a PhD candidate in the Department of
Computer Science, Yale University. He got his master’s degree from Zhejiang
University. His research interests include computational biology, geometric
deep learning, and graph learning. He has published some papers at top
conferences, such as NeurIPS, KDD, WWW, etc.
---|---
|  Yukuo Cen obtained his Ph.D. degree in 2023 from the Department of Computer
Science and Technology, Tsinghua University. He also got his bachelor’s degree
from Tsinghua University. He is currently working at Zhipu AI. He has
published several papers on the top international conferences and journals,
including KDD, WWW, and TKDE, on graph representation learning and recommender
systems.
---|---
|  Junshuai Song received his Ph.D. degree from Peking University in 2021. He
has published papers in top conferences and journals, including TKDE, ICDE,
ACL, and AAAI on graph mining, network representation learning, and
recommender systems.
---|---
|  Bin Xu is a Professor of Computer Science at Tsinghua University. He became
ACM Professional member in 2009 and IEEE member in 2007. His research interest
is Knowledge Gragh and Large Language Models (LLMs). He is core member to
develop GLM family of LLMs.
---|---
|  Yuxiao Dong is an associate professor of computer science at Tsinghua
University. His research focuses on data mining, graph machine learning, and
foundation models. Together with collaborators, his recent research includes
GNNs (hetero. graph transformer, GRAND, OGB), network embedding (metapath2vec,
NetMF, NetSMF, SketchNE), graph pre-training (GraphMAE, GPT-GNN, GCC), and
LLMs (GLM-130B, ChatGLM, CodeGeeX). He received the 2022 SIGKDD Rising Star
Award.
---|---
|  Jie Tang is a WeBank Chair Professor of Computer Science at Tsinghua
University. He is a Fellow of the ACM, a Fellow of AAAI, and a Fellow of IEEE.
His research interest is in artificial general intelligence (AGI). His
research has received the SIGKDD Test-of-Time Award (10-year Best Paper). He
also received the SIGKDD Service Award. Recently, he puts all his efforts into
Large Language Models (LLMs). He invented AMiner.org and developed the GLM
family of LLMs, such as ChatGLM, CogVLM, CodeGeeX, and CogView. He served as
general chair of WWW’23, program chair of WWW’22 and WSDM’15, and EiC of IEEE
Trans. on Big Data and AI Open J.
---|---