ProSampler: Improving Contrastive Learning by Better Mini-batch Sampling
Authors: Zhen Yang
Tinglin Huang
Ming Ding
Zhitao Ying
Yukuo Cen
Yangliao Geng
Yuxiao Dong
Jie Tang
Venue: Submitted to ICLR 2023 (2023)
Keywords: global hard negative sampling
contrastive learning

Abstract: In-batch contrastive learning has emerged as a state-of-the-art self-supervised learning solution, with the philosophy of bringing semantically similar instances closer while pushing dissimilar instances apart within a mini-batch. However, the in-batch negative sharing strategy is limited by the batch size and falls short of prioritizing the informative negatives (i.e., hard negatives) globally. In this paper, we propose to sample mini-batches with hard negatives on a proximity graph in which the instances (nodes) are connected according to the similarity measurement.  Sampling on the proximity graph can better exploit the hard negatives globally by bridging in similar instances from the entire dataset. The proposed method can flexibly explore the negatives by modulating two parameters, and we show that such flexibility is the key to better exploit hard negative globally. We evaluate the proposed method on three representative contrastive learning algorithms, each of which corresponds to one modality: image, text, and graph. Besides, we also apply it to the variants of the InfoNCE objective to verify its generality. The results show that our method can consistently boost the performance of contrastive methods, with a relative improvement of 2.5% for SimCLR on ImageNet-100, 1.4% for SimCSE on the standard STS task, and 1.2% for GraphCL on the COLLAB dataset.

Under review as a conference paper at ICLR 2023
PROSAMPLER: IMPROVING CONTRASTIVE LEARNING BY BETTER MINI-BATCH SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
In-batch contrastive learning has emerged as a state-of-the-art self-supervised learning solution, with the philosophy of bringing semantically similar instances closer while pushing dissimilar instances apart within mini-batch. However, the in-batch negative sharing strategy limited by the batch size and falls short of prioritizing the informative negatives (i.c., hard negatives) globally. In this paper, we propose to sample mini-batches with hard negatives on proximity graph which the instances (nodes) are connected according to the similarity measurement. Sampling on the proximity graph can better exploit the hard negatives globally by bridging in similar instances from the entire dataset. The proposed method can flexibly explore the negatives by modulating two parameters, and we show that such flexibility is the key to better exploit hard negatives globally. We evaluate the proposed method on three representative contrastive learning algorithms, each which corresponds one modality: image, text, and graph. Besides, also apply it to the variants of the InfoNCE objective to verify its generality. Results show that our method can consistently boost the performance of contrastive methods, with a relative improvement of 2.5% for SimCLR on ImageNet- 100, 1.4% for SimCSE on the standard STS task, and 1.2% for GraphCL on the COLLAB dataset.
INTRODUCTION
Contrastive learning has been the dominant approach in current self-supervised representation learning. which applied in many areas, such as MoCo (Chen al.. 2020) and SimCLR (He et al., 2020) in computer vision, GCC (Qiu et al., 2020) and GraphCL (You et al., 2020) in graph representation learning and SimCSE (Gao et al., 2021) in natural language processing. The basic idea is to decrease the distance between the embeddings of the same instances (positive pair) while increase that of the other instances (negative pair). These important works in contrastive learning generally follow slightly modify the framework of in-batch contrastive learning as follows:
((s)² {(o))
minimize Ea 3B
Σ log f(:)) + Ejer el s(E,)
(1)
where {æI... rB} } a mini-batch of samples (usually) sequentially loaded from the dataset D, and a is an augmented version of z4. The encoder f()) learns to discriminate instances by mapping different data-augmennttioon versions of the same instance (positive pair) to similar embeddings, and mapping different instances in the mini-bane batch (negative pair) to dissimilar embeddings. The key to efficiency in-batch negative sharing strategy that any instance within the mini-batch the other instances' negative, which means we learn to discriminate all B(B 1) pairs of instances in mini-batch while encoding each instance only once. Its advantages of simplicity and efficiency make more popular than pairwise (Mikolov et al., 2013) or triple-based methods (Schroff et al., 2015; Harwood et al., 2017), gradually becoming the dominating framework for contrastive learning.
However, the performance of in-batch contrastive learning is closely related to batch size. It is the target of many important contrastive learning methods to obtain a large (equivalent) batch size under limited computation and memory budget. For example, Memory Bank (Wu et al., 2018) stores the encoded embeddings from previous mini-batches as extra negative samples, and MoCo (He et al., 2020) improves the consistency of the stored negative samples via momentum encoder. SimCLR

---

Under review as a conference paper at ICLR 2023
Posttive
Qlobal Mogatives
Posttive
Easy Negathes
orstion Samplerr
ProSampler
ProSampler for Global Hard Nogatives
Uniform Sampler Easy Negalives
ProSampler
Image Representation Space
Uniform Sampler
Figure 1: A motivating example of ProSampler. The generated image representations form an embedding space where Uniform Sampler randomly samples mini-batch with easy negatives and ProSampler samples mini-batch with hard negatives based on proximity graph.
shows that simply increasing the batch size of the plain in-batch contrastive learning to 8,192 outperforms previous carefully designed methods. Although many works highlight the importance of batch size, further question arises which instances in the mini-batch contribute the most?
Hard negative pair contributes the most a clear answer to this question is well-supported by many efforts in some related studies on negative sampling (Ying et al., 2018; Yang et al., 2020; Huang et al., 2021; Kalantidis et al., 2020; Robinson et al., 2021). An intuitive explanation is that the ef(x)) for casy-to-discriminat negative pairs will become very small after the early period of training, and thus the hard negative pairs contribute the majority of the loss and gradients.
The hard negative sampling already made great success in many real-world applications, e.g. 8% improvement of Facebook search recall (Huang al., 2020) and 15% relative gains of Microsoft retrieval engine (Xiong et al., 2020). The key to these methods is to globally select negatives that are similar to the query one across the whole dataset. However, previous methods for negative sampling of in- nn-batch contrastive learning (Robinson et al., 2021; Chuang et al., 2020) focus on identifying negative samples within the current mini-batchs which is insufficient to mine the meaningful negatives from the entire dataset. Meanwhile, previous global negative samplers apply triplet loss and explore the negatives in pairs (Karpukhin et al., 2020; Xiong et al., 2020), which is inapplicable to in-batch negative sharing strategy, since it cannot guarantee the similarity between every instance pair within a mini-batch.
In this paper, we focus designing global hard negative sampler for in-batch contrastive learning. Since every instance serves as the negative to the other instances in the same batch, the desired sampling strategy should be the one with more objective can be considered as sampling a batch of similar instances from the dataset. But how can identify such batch globally the dataset?
distiiiig pairs in each sampled batch. This
Present Work. Here we propose Proximity Graph- Sampler (ProSampler). a global hard negative sampling strategy that can be plugged into any in-batch contrastive learning method. Prox- imity graph breaks the independence between different instances and captures the relevance among instances to better perform global negative sampling. As shown Figure 1, similar instances form local neighborhood in the proximity graph where ProSampler performs negative sampling as short random walks effectively draw hard negative pairs. Besides, ProSampler can flexibly control the hardness of the sampled mini-batch by modulating two parameters. In practice, we build the proximity graph per fixed iterations, and then apply Random Walk with Restart (RWR) per iteration to sample mini-batch for training.
Our experiments show that ProSampler consistently improves top- oer-perfogming contrastive learning algorithms in different domains, including SimCLR (Chen et al., 2020) and MoCo v3 (Chen et al., 2021) in CV, SimCSE (Gao et al., 2021) in NLP, and GraphCL (You et al., 2020) in graph learning by merely changing the mini-batch sampling step. To the best of our knowledge, ProSampler is the first algorithm to optimize the mini-batch sampling step for better negative sampling in the current in-batch contrastive leamnnng framework.
2

---

Under review as a conference paper at ICLR 2023
2
RELATED WORK
Contrastive learning in different modalities. Contrastive learning follows similar paradigm that contrasts similar and dissimilar observations based on noise contrastive estimation (NCE) (Gutmann and Hyvärinen, 2010; Oord al., 2018). The primary distinction between contrastive methods of different modalities is how they augment the data. As for computer vision, MoCo (He et al., 2020), SimCLR (Chen et al., 2020). SwAV (Caron et al., 2020), and BYOL (Grill et al., 2020) augment data with geometric transformation and appearance transformation. Besides simply using data augmentation, WCL (Zheng et al.. 2021) additionally utilizes an affinity graph to construct positive pairs for each example within the mini-batch. As for language, CLEAR (Wu et al., 2020b) and COCO-LM (Meng et al., 2021) augment the text data through word deletion, reordering, and substitution, while SimCSE (Gao et al., 2021) obtains the augmented instances by applying the standard dropout twice. As for graph, DGI (Petar et al., 2018) and InfoGraph (Sun et al., 2019) treat the node representations and corresponding graph representations as positive pairs. Besides, GCC (Qiu et al., 2020) and GraphCL (You et al., 2020) augment the graph data by graph sampling or proximity-oriented methods. Zhu et al. (2021) compares different kinds of graph augmentation strategy. Our proposed ProSampler is a general mini-batch sampler which can directly be applied to any in-batch contrastive learning framework with different modalities.
Negative sampling in contrastive learning. Previous studies about negative sampling in contrastive learning roughly fall into two categories: (1) Memory-based negative sampling strategy, such as MoCo (He et al., 2020), maintains a fixed-size memory bank to store negatives which are updated regularly during the training process. MoCHI (Kalantidis et al., 2020) proposes to mix the hard negative candidates at the feature level to generate more challenging negative pairs. MoCoRing (Wu et al., 2020a) samples hard negatives from defined conditional distribution which keeps lower bound on the mutual information. (2) In-batch negative sharing strategy, such as SimCLR (Chen et al., 2020) and MoCo v3 (Chen et al., 2021), adopts different instances in the current mini-batch as negatives. To mitigate the false negative issue, DCL (Chuang et al., 2020) modifies the original InfoNCE objective reweight the contrastive loss. Huynh et al. (2022) identifies the false negatives within a mini-batch by comparing the similarity between negatives and the anchor image's 's multiple support views. Additionally, HCL (Robinson et al., 2021) revises the original InfoNCE objective by assigning higher weights for hard negatives among the mini-batch. However, such locally sampled hard negatives cannot exploit the hard negatives sufficiently from the dataset.
Global hard negative sampling methods on triplet loss have been widely investigated, which aim to globally sample hard negatives for a given positive pair. For example, Wang et al. (2021) proposes to take rank-k hard negatives from some randomly sampled negatives. Xiong et al. (2020) globally samples hard negatives by an asynchronously-uppee uppdattd approximate nearest neighbor (ANN) index for dense text retrieval. Different from the abovementioned methods which are applied to a triplet loss for given pair, our ProSampler samples mini-batches with hard negatives for InfoNCE loss.
Self-supervised learning without negative sampling. Recently, some attempts on learning without negative sampling achieve promising results, such as BOL (Grill et al., 2020), SWAV (Caron et al., 2020), SimSiam (Chen and He, 2021), and DINO (Caron et al., 2021). These methods apply Siamese network structure, and contrast the output of an online network and target network with different augmented views. The main difference between them is how they prevent model from collapsing.
3
LEARNING WITH PROSAMPLER
3.1 GLOBAL HARD NEGATIVE SAMPLING FOR IN-BATCH CONTRASTIVE LEARNING
Contrastive learning aims to learn proper transformation that maps two semantically similar instances I;, x to two close points in the embedding space. applies NCE objective (Gutmann and Hyvärinen, 2010; Oord et al., 2018) and in-batch negative sharing strategy to boost the training efficiency, which means that every instance serves as a negative to the other instances within the mini-batch. How to sample mini-batch with hard negatives for contrastive learning remains an open problem, and previous methods achieve this by sampling within the mini-batch (Chuang et al., 2020; Robinson al., 2021; Karpukhin et al., 2020). However, the batch size is far smaller than the dataset
3

---

Under review as a conference paper at ICLR 2023
size and sampling within the mini-batch cannot effectively explore the hard negatives from the whole dataset (Xiong et al., 2020; Zhang et al., 2013).
In this work, we delve deeper into learning with the global hard negative sampler, which picks batch of instances containing considerable -oddstidist pairs. Besides, a desired mini-batch sampling strategy should be general and adaptable the datasets with various modalities and different scales. We formulate the problem as:
Problem 1. Given a set of data instances f-....., INJ. our goal to design a modality- independent sampler (D)) {Ir.... (i)+ to sample mini-batch of instances where any instance pair are hard to distinguish across the dataset.
3.2 TWO EXTREME STRATEGIES: UNIFORM SAMPLER AND KNN SAMPLER
Here we discuss two extreme mini-batch sampling strategies for in-batch contrastive learning: Uniform Sampler and KNN Sampler, which represent extreme scenarios in terms of the hardness of mini-batch they construct.
Uniform Sampler is the most common strategy used in contrastive learning (Chen et al., 2020; Gao et al., 2021; You et al., 2020), which is general, easy to implement, and model-indepenel The overall pipeline is to first randomly sample a batch of instances for each training step, then feed them into the objective function.
KNN Sampler can globally sample a mini-batch with many hard negative examples. As its name indicates, kNN Sampler would pick an instance at random and retrieve a set of nearest neighbors to construct batch. Figure shows that the mini-batch sampled by kNN Sampler has a high percentage of similar instance pairs.
However, the abovementioned two methods suffer from the following limitations:
Uniform Sampler neglects the effect of hard negatives (Kalantidis et al., 2020; Robinson et al., 2021), and will select negatives with low gradients that contribute little to optimization. As shown in Figure 4, Uniform Sampler results in a low percentage of similar instance pairs in a mini-bated Yang et al. (2020) and Xiong et al. (2020) also theoretically prove that the suggested sampled negative should be similar to the query instance since it can provide a meaningful gradient to the model.
During the self-supervised training, the instances of the same class will cluster together in the embedding space (Chen et al., 2020; Caron et al., 2020). Hence the kNN Sampler can first retrieve the hard negatives but they will be replaced by false negatives (FN) the training epochs increase. Figure 4 also demonstrates that KNN Sampler exhibits a very high percentage of FN a mini-batch.
In conclusion, Uniform Sampler cannot leverage hard negatives to guide the optimization of the model; whereas kNN Sampler explicitly samples hard negatives but suffers from the false negative issue. Both of them will result in sub-optimal performance. A better global hard negative sampler for in-batch contrastive learning should trade-off these two sampling styles, and balance the exploitation of hard negatives and the FN issue. Building on the above observations, we propose ProSampler, flexible global mini-batch sampler which allows us to smoothly interpolate between the kNN Sampler and the Uniform Sampler.
3.3 PROSAMPI.ER
As discussed in Section 3.1, desired mini-batch should be the one where any example is the hard negative of the other examples. This objective can also be seen as sampling group of instances which are close to one another in the embedding space. But how to identify such groups globally from the dataset? As shown in Figure 2, we propose to capture similarity relationships among instances by proximity graph. Proximity graph connects the instances by the similarity measurement, and in this way, instances that appear to be close to each other form a local community in the graph. We perform the mini-batch sampling sampling results. To modulate the hardness of a sampled batch, we introduce two parameters M and control the behaviors of proximity graph construction and sampling respectively.
walk in the proximity graph, which collects the visited instances as
4

---

Under review as a conference paper at ICLR 2023
Views
Representations
e:
Contrastive
ej
Proximity Graph Construction Proximity Graph Sampling
Batch
In-batch Contrastive Learning
Figure 2: The framework of ProSampler. The proximity graph is first constructed based generated image representations and will be updated every training steps. Next, a proximity graph- negative sampler is applied generate batch with hard negatives for in-batch contrastive learning.
Proximity graph construction. Recall that in training dataset, we have N observations {uzli 1,... .N. and their corresponding representations {e, 1, ,, ,N generated by the current encoder f(()). We formulate the proximity graph as:
-=
where the node set V [U1,... UN denotes the data examples and & S {(1,, 1y) v E V) is collection of node pairs. Let M₁ be the neighbor set of instances u; in the proximity graph. To
construct Mi, we first form a candidate set C; = {Um } for each instance es by uniformly picking M(M < N) neighbor candidates. Then select the K nearest ones from the candidate set:
N TopK (e; em))
(3)
EC,
where- is the inner product operation. M controls the similarity between the center node and its immediate neighbor nodes, which can be demonstrated by the following proposition:
Proposition 1. Given an observation v; with the corresponding representation e, assume that there at least S observations whose inner product similarity with v is larger than s, i.e.,
{uy e >>>}
(4)
Then in the proximity graph G, the similarity between and its neighbors is larger than with proximate probubility at least:
K P (e: ek > 8, VeR E E 2 >
(5)
where = N-S and is the number of neighbors.
-N- N
The proof is deferred to Appendix B. The insight of Proposition is to relate candidate size M to the similarity between a node pair. Higher M indicates a greater probability that two adjacent nodes are similar, and proximity graph will be more like the kNN graph. On the other hand, if M is low, some randomly chosen instances are more likely to be neighbors, improving the diversity of the negatives around the center node.
Proximity graph sampling. Breadth freadth-first Sampling (BFS) and Depth- first Sampling (DFS) are two straightforward graph sampling methods (Grover and Leskovee, 2016), representing extreme scenarios terms of the search space:
Breadth-first Sampling (BFS) collects all of the current node's immediate neighbors, then moves its neighbors and repeats the procedure until the number of collected instances reaches batch size.
Depth-first Sampling (DFS) randomly explores the node branch as far as possible before the number of the visited nodes reaches batch size.
To flexibly explore the negatives in proximity graph, we propose to apply Random Walk with Restart (RWR) which can exhibit mixture of both. As shown in Algorithm 3, beginning node,
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1: In-batch Contrastive Framework with ProSampler
Input: Dataset D {zylé = -..... .N.. Encoder f(.), Batchsize B, Graph update step t, specifc augmentation functions T.
for äter +- 0, 1, ..... do
11 PrPoSampler if' iter"Kt == 0 then
// Proximity Graph Construction
Build the proximity graph G by Algorithm end
// Proximity Graph Sampling
Randomly select start node and get the mini-batch {r:}n by Algorithm 3.
Obtain positive pairs {(x., ( ) by augmentation functions Sang (.) ~ T.
Generate representations {(e,, e," }e by Encoder f(-).
Compute the loss by Eq. 1, where ((),,,,) e)) are treated as negative pairs.
Update the parameters of f(-).
end
the sampler iteratively teleports back to the start point with probability travels to neighbor of the current position with the probability proportional to the edge weight. The process continues until it collects fixed number of vertices which will be taken the sampled batch.
The key insight using RWR is that it can modulate the probability of sampling within a neighbor- hood by adjusting a, which can be demonstrated by the following proposition:
For all 0 < a S 1 and S V, the probability that Lazy Random Walk with Restart starting from a node u E S escapes S satisfies Eve(V-s) Pu(U) S 1-a ((S), where Pu is the stationary distribution, and ((S) is the graph conductance of S.
Proposition 2.
2a
The proof is deferred to Appendix B. Proposition 2 indicates that the probability of RWR escaping from local cluster (Andersen al., 2006; Spielman and Teng, 2013) can be bounded by the graph conductance (Síma and Schaeffer., 2006) and the restart probability a. In other words, higher indicates that the walker will approximate BFS behavior and sample within a small locality. Lower encourages the walker visit the nodes which are further away from the center node.
ProSampler pipeline. As shown in Algorithm 1, ProSampler serves as a mini-batch sampler and can be easily plugged into any in-batch contrastive learning method, such as SimCLR (Chen et al., 2020), MoCo v3 (Chen et al., 2021), SimCSE (Gao al., 2021) and GraphCL (You al., 2020). Specifically, during the training process, ProSampler first constructs the proximity graph, which will be updated after training steps, then selects a start node at random and samples a mini-bated on proximity graph by RWR. ProSampler is orthogonal to the contrastive methods.
As shown in Figure 3, the number of candidates M and the restart probability a are the key to flexibly control the hardness of a sampled batch. When set M the size of dataset and 1, proximity graph is equivalent to kNN graph and graph sampler will only collect the immediate neighbors around center node, which behaves similarly is set to 0, the RWR degenerates into the DFS and chooses the neighbors that are linked at random, which indicates that ProSampler performs Uniform Sampler. We provide an empirical criterion of choosing M and a in Section 4.3.
kNN Sampler. On the other hand, if M is
and
Complexity. The time complexity of building a proximity graph is O(NMd) where N is the dataset size, . the candidate set size and d denotes the embedding size. practically efficient since usually M is much smaller than N, and the process can be accelerated by embedding retrieval libraries such as Faiss (Johnson et al., 2019). More analysis on efficiency can be found in Appendix F.5. Besides, the space cost of ProSampler mainly comes from graph construction and graph storage. The total space complexity of ProSampler is O(Nd + KK) where is the number neighbors in the proximity graph.

---

Under review as a conference paper at ICLR 2023
4 EXPERIMENTS
To show the effectiveness of ProSampler in a variety of scenarios, we apply it to the representative contrastive learning algorithms three data modalities, including image. text, and graph. Further- more, to investigate ProSampler's generality, we equip two variants of InfoNCE objective with our model, including DCL (Chuang al., 2020) and HCL (Robinson et al., 2021). InfoNCE objective and its variants are described in Appendix C. The statistics of the datasets are summarized in Appendix D, and the detailed experimental setting can be found in Appendix E.
4.1 BENCHMARKING RESULTS
Results on Image Modality. We first adopt Sim- CLR (Chen et al., 2020) and MoCo v3 (Chen et al., 2021) as the backbone based on ResNet-50 (He et al., 2016). We start with training the model for 800 epochs with a batch size of 2048 for SimCLR and 4096 for MoCo v3, respec- tively. We then use linear probing to evaluate the repre- sentations on ImageNet. We also compare the ProSampler with the two tate-of-the-art self-supervised learning meth- ods without negative sampling, including SwAV (Caron et al., 2020) and BYOL (Grill et al., 2020). As shown in Table I, our proposed model can consistently boost the performance of original SimCLR and MoCo v3, and out- performs all the baselines without negatives, demonstrat- ing the superiority of ProSampler. Besides, we evaluate ProSampler on the other benchmark datasets, which can be found in Appendix F.1.
Table Top-1 accuracy under the lin- ear evaluation with the ResNet-50 back- bone on ImageNet.
Method
100 ep
800 ep
SwAV" BYOL
66.5
71.8
66.5
74.3
SimCLR
64.0
68.7
w/ ProSampler
64.7 (1 0.7)
69.2 (1 0.5)
MoCo v3 ProSampler
68.9
73.8
69.5 (1 0.6) 74.2 (f 0.4)
without multi-crop augmentations.
Results on Text Modality. We evaluate ProSampler on learning the sentence representations by SimCSE (Gao al., 2021) framework with pretrained BERT (Devlin et al., 2018) as backbone. The results of Table 2 suggest that ProSampler consistently improves the baseline models with an absolute gain of 1.09%~2..914 % on 7 semantic textual similarity (STS) tasks (Agirre al., 2012; 2013; 2014; 2015; 2016; Tian et al., 2017; Marelli et al., 2014). Specifically, we observe that when applying DCL and HCL,, the performance of the self-supervised language model averagely drops by 2.45% and 3.08% respectively. As shown in Zhou et al. (2022) and Appendix F.2, the pretrained language model offers a prior distribution over the sentences, leading to a high cosine similarity of both positive pairs and negative pairs. So DCL and HCL, which leverage the similarity of positive and negative scores to tune the weight of negatives, are inapplicable because the high similarity scores of positives and negatives will result in homogeneous weighting. However, the hard negatives explicitly sampled by our proposed ProSampler can alleviate it, with an absolute improvement of 1.64% on DCL and 2.64% on HCL. The results of RoBERTa (Liu al., 2019) reported in Appendix F.3.
Table 2: Overall performance comparison with different negative sampling methods on STS tasks.
Method
STS12
STS13
STS14
STSI5
STS16
STS-B
SICK-R
Avg.
SimCSE-BERT base
68.62
80.89
73.74
80.88
77.66
77.79
69.64
75.60
w/ ProSampler
72.37
82.08
75.24
83.10
78.43
77.54
68.05
76.69
DCL-BERT base
65.22
77.89
68.94
79.88
76.72
73.89
69.54
73.15
w/ ProSampler
69.55
82.66
73.37
80.40
75.37
75.43
66.76
74.79
HCL-BERT base
62.57
79.12
69.70
78.00
75.11
73.38
69.74
72.52
w/ ProSampler
66.87
81.38
72.96
80.11
77.99
75.95
70.89
75.16
Results on Graph Modality. We test ProSampler with graph-level classification task based on GraphCL (You et al., 2020) framework, which uses GIN (Xu et al., 2018) as the backbone. Table reports the detailed performance comparison four benchmark datasets: IMDB-B, IMDB-M, COLLAB, and REDDIT-B (Yanardag and Vishwanathan, 2015). The result shows that ProSampler consistently boost the performance of GraphCI., with an average absolute improvement of
7

---

Under review as a conference paper at ICLR 2023
0.89% across all the datasets. Besides, equipped with ProSampler, DCL and HCL can achieve better performance in 6 out of 8 cases. It can also be found that ProSampler can reduce variance in most cases, demonstrating that the hard negatives exploited by ProSampler can enforce the model to learn more robust representations.
Table 3: Accuracy on graph classification task under LIBSVM (Chang and Lin, 201 classifier.
Method
IMDB-B
IMDB-M
COLLAB
REDDIT-B
GraphCL
7..3
08.48
70.62+0.23
00.5
w/ ProSampler
71.90 0.46
48.93 0.28
90.88 7..28
DCL
71.07+0..6
0.32
71.06:10.51
90.66+0.29
w/ ProSampler
7113
08.26:10.25
70.44:0.35
90.7310.34
HCL
4..54 0..24
71.03+0.45
90,40+0.42
w/ ProSampler
71.20:10.38
48.76.10.39
71.70-L0.35 0.22
4.2
WHY PROSAMPLER PERFORMS BETTER?
In this section, we apply SimCLR on CIFARIO and CIFAR 100, and compare the Uniform Sam- pler, KNN Sampler and ProSampler in terms of performance and the false negatives to deepen the understanding of ProSampler. We show the performance of ProSampler with different M and settings in Figure 3, and use the name convention ProSampler (M, a). Besides, we illustrate the histogram of cosine similarity for all pairs from sampled batch, and the percentage of false negatives within the mini-bated during training in Figure 4. We can observe that although kNN Sampler can explicitly draw data batch with similar pairs, it introduces substantially higher number of false negatives, degrading performance significantly. Uniform Sampler is independent of the model so the percentage of FN within the sampled batch remains consistent during training. However, ProSampler can modulate M, to find the best balance between these two sampling methods. We can observe that ProSampler can sample hard mini- but only exhibits slightly higher percentage of false negatives than Uniform Sampler with optimal parameter setting, which enables ProSampler to achieve the best performance. Similar phenomenon on CIFAR 100 can be found Appendix F.4.
$3.0
Kuepler
0.24
size Kamplerr
92.5
3.5
surfor Sampler
0.22
beifor Sangter
62.0
Accurscy
91.5
56
0.19
91.0
0.16
50.5
64
1.5
0.14
00.0
0.5
0.10
89.0
CIPARLO
60
CIPAR1D0
0.0
0.2
Caeine Similartty
Training Stmplx1080)
Figure 3: Performance comparison of different in-batch samplers on image classification task.
Figure 4: Cosine similarity and false negative ratio on CIFAR1O dataset.
4.3 EMPIRICAL CRITERION FOR PROSAMPLER
To analyze the impact of the size of neighbor candidate M and the random walk restart probability a. we vary the M and a in range of (500, 1000, 2000, 4000, 6000} and {0.1, 0.3, 0.5, 0.7) respectively. and apply SimCLR, SimCSE and GraphCL as backone. We summarize the results in Table 4 and Table 5. Table 4 shows that in most cases, the performance of the model peaks when M M 1000 but plumbs quickly with the increasing of M. Such phenomena are consistent with the intuition that higher M raises the probability of selecting similar instances as neighbors, but the sampler will be more likely to draw the mini-batch with false negatives, degrading the performance.
Table 5 shows the performance of ProSampler with different Besides, to better understand the effect of a, we illustrate the histograms of cosine similarity for all pairs from a sampled batch after training in Figure 5, and plot the percentage of false negatives in the mini-batch during training in Figure 6. We can observe that a moving from 0.1 through 0.2 to 0.7 causes cosine similarities to gradually skew left, but introduces more false negatives in the batch, creating trade-off. This phenomenon indicates
8

---

Under review as a conference paper at ICLR 2023
Table 4: Impact of neighbor candidates M.
Table 5: Impact of restart probability a.
500
1000
2000
4000
6000
0.1
0.3
0.7
0.2~0.055
CIFARIO
92.54
92,49
91.83
91.72
91.43
CIFARIO
92.41
92.26
92.12
92.06
92.54
CIFARI00
67.92
68.68
67.05
66.19
65.55
CIFARIO0
68,31
67.98
68.20
68.00
68.68
STL10
84.16
84.38
82.80
81.91
80.92
STL10
83.01
80.69
83.93
82.56
84.38
ImageNet- 100
59.6
60.8
60.1
59.1
58.4
ImageNet- 100
60.8
59.6
58.1
57.7
60.8
Wikipedia
71.36
76.69
76.09
75.76
75.11
Wikipedia
71.74
72.13
72.41
76.69
COLLAB
70.44 71.48
70.93
70.46
70.24
COLLAB
70.36 70.63 70.63 70.31
71.48
that the sampler with a higher a sample more frequently within local neighborhood, which is more likely to yield similar pairs. However, training progresses, the instances of the same class tend to group together, increasing the probability of collecting false negatives. To find the best balance, we linearly decay a from 0.2 to 0.05 the training epoch increases, which is presented as 0.2 0.05 in Table 5. It can be found that this dynamic strategy achieves the best performance in all cases except SimCSE which only trains for one epoch. Interestingly, SimCSE achieves the best performance by large margin when a = 0.7 since hard negatives can alleviate the distribution issue brought by the pre-trained language model. More analysis can be found in Section 4.1 and Appendix F.2.
To sum up, the suggested M would be 500 for the small-scale dataset, and 1000 for the larger dataset. The suggested a should be relatively high, e.g., 0.7, for the pre-trained language model-based method. Besides. dynamic decay e.g., 0.2 to 0.05, is the best strategy for the other methods.
2.30
0.1
0.15
2.17
2.30
00033
0004
0.013
2.
10
3.2
0.13
35
233
Casine Simiarity
24
30
322
0.4
5.6 0.5
Training Steptx1600)
12
Training Steptx1000)
(a) CIFARIO
(b) CIFAR100
(a) CIFARIO
(b) CIFAR100
Figure 5: Cosine similarities between the pairs.
Figure 6: Percentage of false negatives.
4.4 DISCUSSIONS
Due to the page limit, some additional experiments are reported in Appendix F. Appendix F.5 studies the efficiency of ProSampler. Appendix F.6 compares different graph sampling methods in terms of performance, cosine similarity, and false negatives. Appendix F.7 compares the performance of ProSampler with proximity graph and kNN graph. Appendix F.8 discusses the influence of some parameters, including batchsize B, neighbor number K, and proximity graph update interval t. Appendix F.9 presents the training curves. Appendix F. 10 includes case studies where we show some real cases of the mini-bated sampled by ProSampler and Uniform Sampler.
5 CONCLUSION
In this paper, study the problem of global hard negative sampling for in-batch contrastive learning. We reformulate the original mini-batch sampling problem to the proximity graph sampling problem. Based on this, we propose proximity graph-based sampling framework, ProSampler, which can sample a mini-batch with hard negative pairs for in-batch contrastive learning at each training step. Besides, conduct experiments three tate-of-the-art contrastive methods with different modalities and two variants of InfoNCE objective to evaluate our proposed ProSampler, which shows that ProSampler consistently improve the these models.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Eneko Agirre, Daniel Cer. Mona Diab, and Aitor Gonzalez-Agine. Semeval-2012 task 6: pilot on semantic textual similarity. In * SEM 2012: The First Joint Conference on Lexical and Computational Semantics- Volume I: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation (SemEval 2012), pages 385-393, 2012.
Eneko Agirre, Daniel Cor, Mona Diab, Aitor Gonzalez-Agire, and Weiwei Guo. sem 2013 shared task: Semantic textual similarity. In Second joint conference on lexical and computational semantics (* SEM), volume 1: proceedings of the Muin conference and the shared task: semantic textual similarity, pages 32-43, 2013.
Encko Agirre, Carmen Banea, Claire Cardie, Damiel M Cer, Mona T Diah, Aitor Gonzalez-Agirre, Weiwei Guo, Rada Mihalcea, German Rigau, and Janyce Wiebe. Semeval-2014 task 10: Multilingual semantic textual similarity. In SemEval@ COLING, pages 81-91, 2014.
Eneko Agirre, Carmen Banea, Claire Cardie, Daniel Cer, Mona Diab, Aitor Gonzalez- Weiwei Guo, Inigo Lopez- Gazpio, Montse Maritxalar, Rada Mihalcea, et al. Semeval-201 task 2: Semantic textual similarity, english, spanish and pilot interpretability. In Proceedings of the 9th international workshop on semantic evaluation (SemEval 20/5), pages 252-263, 2015.
Encko Agine, Carmen Banea, Daniel Cer, Mona Diab, Aitor Gonzalez Agimr,, Rada Mihaleea, German Rigau Claramunt, and Janyce Wiebe. Semeval-201e task I: Semantic textual similarity, monolingual and gross-lingur evaluation. In sanEvvll-206. 10th International Workshop on Semantic Evaluation; 2016 Jun 16-17; 17; San Diego, CA. Stroudsburg (PA): ACI,; 2016. p. 497-511. ACI. (Association for Computational Linguistics), 2016.
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. 2006.
Konstantin Avrachenkov, Remeo van der Hofstad, and Marina Sokol. Personalized pagerank with node-dependent restart. In International Workshop on Algorithms and Models for the Web-Graph, pages 23-33, 2014.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learming of visual features by contrasting cluster assignments. In Advances in Neural Information Processing Systems, pages 9912-9924, 2020.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties sule-super vision transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages
2021.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector, ACM transactions on intelligent xystems and technology. pages 1-27, 2011.
Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint #xxx:2002.05709 2020.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 15750-15558, 2021.
Xinlei Chen, Saining Xie, and Kaiming He. An empirical study of training self-supervised vision transformers. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 9640-9649, 2021.
Ching- Yao Chuang, Joshua Robinson, Lin Yen-Chen Antonio Torralba, and Stefanic Jegelka. Debiased contrastive learning. In Advances in neural information processing systems, 2020.
Fan Chung and Alexander Tsiatas. Finding and visualizing graph clusters using pagerank optimization. In International Workshop on Algorithmss and Models for the Web-Graph, pages 86-97, 2010.
Fan Chung and Wenbo Zhao. Pagerank and random walks on graphs. In Fete of combinatorics and computer science, pages 43-62, 2010.
Jacob Devlin, Ming- Wei Chang, Kenton Lec, and Kristina Toutanova. Bert: Pre-training of deep bidircctional transformers for language understanding, arXiv preprint arX0v:1810.04805, 2018.
Tianyu Gao, Xingeheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint MXXi::210400822 2021.
Lean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, and Carl Doersch et al. Bootstrap your own latent-a new approach to self-supervised learning. In Advances in Neural Information Processing Systems, pages 21271-21284, 2020.
10

---

Under review as a conference paper at ICLR 2023
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855 864, 2016.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: new estimation principle for unnormal- ized statistical models. In Proceedings of i=International Conference on Artificial Intelligence and Statistics, pages 297-304, 2010.
Ben Harwood, Vijay Kumar BG, Gustavo Careiir, Ian Reid, and Tom Drummond. Smart mining for deep metric learning. In Proceedings of the IEEE International Conference on Computer Vision, pages 2821-2829, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. Proceedings of the IEEE conference on computer vision and pattern recognition, 2020.
Jui-Ting Huang, Ashish Sharma, Shuying Sun, Xia, David Zhang. Philip Pronin, Janani Padmanabhan. Giuseppe Ottaviano, and Linjun Yang. Embedding- retrieval in facebook search. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2553 2561, 2020.
Tinglin Huang, Yuxiao Dong, Ming Ding, Zhen Yang. Wenzheng Feng, Xinyu Wang, and Jie Tang. MixGCF: An improved training method for graph neural network-based recommender systems. In Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 665-674 674, 2021.
Tri Huynh, Simon Kornblith, Matthew R Walter, Michael Maire, and Maryam Khademi. Boosting contrastive self-supervised learning with false negative cancellation. In Proceedings of the IEEF/CVF Winter Conference on Applications of Computer Vision, pages 2785-2795, 2022.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):335-544 557, 2019.
Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus. Hard negative mixing for contrastive learning. In Advances in neural information processing systems, 2020.
Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04900 2020.
Diederik Kingma and Jimmy lei Ba. Colorful image colorization. In International Conference on Learning Representations, 2015.
Donald Ervin Knuth. The art of computer programming: Fundamental AlaudammntlAlgorrtimmn volume 1. Pearson Education, 1997.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer I Levy, Mike Lewis, Luke Zettlemoyer. and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692. 2019.
Marco Marelli, Stefano Mcnini, Marco Baroni, Luisa Bentivogli. Raffaella Bernardi, and Roberto Zamparelli. sick cure for the evaluation of compositional distributional semantic models, In Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC' 14), pages 216-223, 2014.
Yu Meng, Chenyan Xiong, Payal Bajaj. Paul Bennett, Jiawei Han, and Xia Song. Coco-Im: Correcting and contrasting text sequences for language model pretraining, In Advances in Neural Information Processing Systems, 2021
Tomas Mikoloy, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionallty. In Advances in neural information processing systems, 2013.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: 0107180733747 2018
I Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order the web. Storford University Technical Report,, 1999.

---

Under review as a conference paper at ICLR 2023
Veličković Petar, William Fedus, William L. Hamilton, Pietro Lio, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. arXiv preprint arXiv: 1awp::180900000 10341, 2018.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding, Kuansan Wang. and Jie Tang. Gec: Graph contrastive coding for graph neural network pre-training- Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1150-1160, 2020.
Joshua Robinson, Ching-Yas Yao Chuang, Suvrit Sra, and Stefanic Jegelka. Contrastive lcarning with hard negative samples. In International Conference on Learning Representations, 2021.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Adiyy Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3)2111-2555 2015.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unitied embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815-823, 2015.
Daniel A Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and application to nearly linear time graph partitioning. SIAM Journal on computing, 2013.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv: 1008,000800000 2019.
Junfeng Tian, Zhiheng Zhou, Man Lan, and Yuanbin Wu. Ecnu at semeval-2017 task I: Leverage kernel- traditional nlp features and neural networks to build universal model for multilingual and cross cross-lingen lingull semantic textual similarity. Proceedings of the 1 11th international workshop on semantic evaluation (SemEval 2017), pages 191- 197, 2017.
Hanghang Tong. Christos Faloutsos, and Jia- Yu Pan. Fast random walk with restart and its applications. In Sixth international conference on data mining, 2006.
Guangrun Wang. Keze Wang, Guangcong Wang, Philip HS Torr, and Liang Lin. Solving inefficiency of self- supervised representation learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9505-9515, 2021.
Mike Wu, Milan Mosse, Chengxu Zhuang, Daniel Yamins, and Noah Goodman. Conditional negative sampling for contrastive learning of visual representations. arXiv preprint arXiv:2010.02037. 2020a.
Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733-3742, 2018.
Zhuofeng Wu, Sinong Wang, Jiatao Gu, Madian Khabsa, Fei Sun, and Hao Ma. Clear: Contrastive learning for sentence representation. arXiv preprint (Xiv:2012.15466. 2020b.
Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang. Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighhor negative contrastive learning for dense text retrieval. arXiv preprint 2.Xiv:0007000808 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1800000866...... 2018
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD interna- tional conference on Knowledge discovery and data mining, 2015.
Zhen Yang. Ming Ding. Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Understanding negative sampling in graph representation learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1666-1676, 2020.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining, 2018
Yang You. Jing Li. Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song. James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large hatch optimization for deep learning: Training hert in 76 minutes. arXiv preprint arXiv: / 1944000622 2019.
12

---

Under review as a conference paper at ICLR 2023
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang. and Yang Shen. Graph contrastive learning with augmentations. Advances neural information processing systems, pages 5812-508 5823, 2020.
Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu. Optimizing top-n collaborative filtering via dynamic negative item sampling. In Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval, pages 785-788, 2013.
Mingkai Zheng, Fei Wang, Shan You, Chen Qian, Changshui Zhang, Xiaogang Wang, and Chang Weakly supervised contrastive learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages
2021.
Kun Zhou, Beichen Zhang, Wayne Xin Zhao, and Ji-Rong Wen. Debiased contrastive learning of unsupervised sentence representations. arXiv preprint arXiv:2205.080 000666 2022.
Yanqiao Zhu, Yichen Xu. Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. arXiv preprint arXiv:2109 D.Xix:2109001116 01116, 2021.
Jifí Šíma and Satu Elisa Schaeffer. On the up-compleseness of some graph cluster measures. In International Conference on Current Trends in Theory and Practice of Computer Science, 2006.
13

---

Under review as a conference paper at ICLR 2023
A ALGORITHM DETAIL
Here we present the detail of Proximity Graph Construction and Random Walk with Restart, as shown in Algorithm 2 and Algorithm 3 respectively.
Algorithm 2: Proximity Graph Construction
Input: Dataset D { Candidate set size M, Neighbor number K; Output: A proximity graph G;
for v in do
Randomly select M neighbor candidates from D; Select the K closest candidates N₁ by Eq. 3;
G[u] + No;
end
return G
Algorithm 3: Random Walk with Restart(RWR)
Input: Proximity graph EV,E), seed node u, restart probability a, number of sampled
node B;
Output: sampled node set S: S O}.
while len(S) < B do
if v not in S then S.insert(v) end
Sample from Uniform distribution (0, 1):
ifr < a then 1 uufu,
end
else
Randomly sample from v's neighbors;
U + 0;
end end return S
B THEORETICAL PROOF
Proposition 1. Given observation v, with the corresponding representation e,, assume that there are at least S observations whose inner product similarity with v is larger than s, i.e.,
[v, le,eVVee.,,,xx. 2 S.
(1)
Then in the proximity graph G. the similarity between V; and neighbors is larger than s with proximate probubility at least:
P (e: e > s, Veu E N. (M))((1-p))))) (1-p"r)
(2)
where p
N-S. and K is the number of neighbors.
Proof. Since M & N, we can approximately assume that the sampling is with replacement. In this case, have
K
M M-
PP (e: es > 8, Vok E = 1
Σ
1-p))* p²*
(3)
h:
R=
Then let prove (2) by induction. When K 1, the conclusion clearly holds.
14

---

Under review as a conference paper at ICLR 2023
Assuming that the conclusion holds when K L 1, let consider the case when K L. We have
L-1
1- (
-p--pp p)* (1-D")
1-11
M ((--) (
p pM- (1 (1-p)
(4)
k=0
To prove the conclusion, only need to show
L-1
M
(1-p") pK) pd 2 --1
M- M-Ltt (1 (1-p) (1-
(5)
or equivalently
(1 (1-pa) - (1-1²²( L-1
pl-
(1 (1-pa
L-1
N 5 L-1
(6)
M
8
L-1
( M
L (L-1) (1 (1-p)(-1
1-11
L
N
On the other hand, according to Knuth (1997), we have
(L-1)
M
$ L (--1) (1-))² 4-1
(7)
where e denotes the Euler's number. Substituting (7) into (6), we only need show
(N - () (1-p") pM 2 eMS.
The above relation holds depending on the choices of M, S and which can be approximately satisfied in our scenario.
For all 0 < a S 1 and S V. the probability that a Lazy Random Walk with Restart starting from node E 8 escapes S satisfies Eve(V-s) Pu(v) S 1- ((S), where Pu is the stationary distribution, and (SS) the graph conductance of S.
Proposition 2.
Proof. We first introduce the definition of graph conductance (Šíma and Schaeffer. 2006) and Lazy Random Walk (Spielman and Teng, 2013):
Graph Conductance For undirected graph G (V,&), the graph volume of node set S C V is defined as vol(S) = Eves d(v), where d(v) is the degree of node v. The edge boundary of node set is defined to be A(S) = ((x, y) E E|æ E S, y & S}. The conductance of S is calculated as followed:
[0(S) ((S) min( vol(V - S))
Lazy Random Walk Lazy Random Walk (LRW) is a variant of Random Walk, which first starts at node, then stays at the current position with a probability 1/2 travels neighbor. The transition matrix of a lazy random walk is M & (I+AD AD AD--11/ 1)/2, is the adjacent matrix, and D is the degree matrix. The K-th step Lazy Random Walk distribution starting from a node u is defined as ( + 1
where the denotes the identity matrix, A
We then present theorem which relates the Lazy Random Walk to graph conductance, which has been proved in Spielman and Teng (2013):
Theorem 1.
For all K > 0 and S V, the probability that K-step Lazy Random Walk starting at u E S escapes S satisfies q (K) (V- - S) s K2(
Theorem 1 guarantees that given non-empty node set S C V and start node S, the Lazy Random Walker will be more likely stuck at S. Here we extend the LRW to Lazy Random Walk with Restart (LRWR)) which will return to the start node with probability perform Lazy Random
15

---

Under review as a conference paper at ICLR 2023
Walk. According to the previous studies (Page et al., 1999; Avrachenkov et al., 2014; Chung and Zhao, 2010; Tong et al., 2006), we can obtain a stationary distribution Pu by recursively performing Lazy Random Walk with Restart, which can be formulated a linear system:
Pu = al + (1 Mp.
(10)
where a denotes the restart probability. The element Pa represents the probability of the walker starting at and ending at Ps. can be expressed by geometric sum of Lazy Random Walk (Chung and Tsiatas, 2010):
20
Pu 2 (1-a)
( M'
Σ (1 a) 1=0
(11)
Applying the Theorem 1, we have:
Σ (v( = Σ Σ (1 (1-) S Σ (1110)0(8))
1 a ((S)
(12)
2a
NE(V-S)
1=0 (E(-S8)
1=0
The desired result is obtained by comparing the two sides of (12).
In particular, the only difference between Lazy Random with Restart and Random Walk with Restart is that the former has a probability of remaining in the current position without taking any action. They are equivalent when sampling predetermined number of nodes.
C INFONCE OBJECTIVE AND ITS VARIANTS
Here we describe in detail the objective functions three in-batch contrastive learning methods, including SimCLR (Chen al., 2020), GraphCL. (You et al., 2020) and SimCSE (Gao et al., 2021). Besides, we cover two variants, i.c., DCL (Chuang et al., 2020) and HCL (Robinson et al., 2021). which are also applied in the experiments.
C.I SIMCLR
SimCLR (Chen et al., 2020) first uniformly draws mini-batch of instances (#)... FB D, then
augments the instances by two randomly sampled augmentation strategies Saug (.), laug (.) ~ T. resulting in 2B data points. Two augmented views (Ii, (14, of the same image treated positive pair, while the other 2(B 1) examples are negatives. The objective function applied in SimCLR for a positive pair (It,, xT) is formulated as:
(a,) f(zur))/
4 - llog
(13)
2B ((
where 7 is the temperature and f(-) is the encoder. The loss is calculated for all positive pairs in mini-batch, including (z,, (B) and (z;) can found that SimCLR takes all 2(B - 1) augmented instances within mini-batch negatives.
C.2 GRAPHICL AND SIMCSE
Similar SimCLR, the objective function of GraphCL (You al., 2020) and SimCSE (Gao et al., 2021) is defined on the augmented instance pairs within a mini-batch. Given a sampled mini- batch { FR} D. both GraphCL and SimCSE apply data augmentation obtain positive pairs, be formulated as:
and the loss function for positive pair (x; .xft)
16

---

Under review as a conference paper at ICLR 2023
(as) 1(07)/+
4 = log
(14)
Σラ=1 [(xx))((x3)/-
Compared with the SimCLR, GraphCL and SimCSE only take the other augmented instances as negatives.
C.3 DCL AND HCL
DCL (Robinson et al., 2021) and HCL (Robinson al., 2021) are two variants InfoNCE objective function, which aim to alleviate the false negative issue or mine the hard negatives by reweighting the negatives the objective. The main idea behind them is using the positive distribution to correct for the negative distribution.
For simplicity, we annotate the positive score e [(x) 1/T as pos, and negative score f(x)" as negij. Given a mini-batch and positive pair (x,,2;), the reweighting nega- tive distribution proposed in DCL and HCL are:
B
-Nngg X T x pos Aig x negij 1/7
max
(15)
+
where Nneg is the number of the negatives in mini-batch, 7 is the class probability, is the temperature, and Xig concentration parameter which simply set as in DCL or calculated as Bxnegy Xig "Enggy//Wae in HCL. All of of Fff+t,, B are tunable hyperparameters. The insight of Eq. is that the negative pair with the score closer positive score will be assigned lower weight in loss function. In other words, the similarity difference between positive and negative pairs dominates the weighting function.
D DATASET DETAILS
For image representation learning, we adopt five benchmark datasets, comprising of CIFAR1O, CIFAR100, STL10. ImageNet- and ImageNet ILSVRC-2012 (Russakovsky al., 2015). Infor- mation on the statistics of these datasets is summarized in Table 6. For graph-level representation learning, we conduct experiments on IMDB-B, IMDB-M, COLLAB and REDDIT-B (Yanardag and Vishwanathan, 2015), the details of which presented in Table 7. For text representation learning, we evaluate the method on one-million English Wikipedia dataset which is used the SimCSE and can be downloaded from HuggingFace repository
Table 6: Statistics of datasets for image classification task.
Datasets CIFARIO CIFARI00 STL10 ImageNet-100 ImageNet
#Train
50,000
50,000
105,000
130,000
1,281,167
#Test
10,000
10,000
8,000
50,00
50,000
#Classes
10
100
10
100
1,000
E EXPERIMENTAL DETAILS
E.1 IMAGE REPRESENTATIONS
In image domain, we apply SimCLR (Chen et al., 2020) and MoCo v3 (Chen et al., 2021) as the baseline method, with Re (He al., 2016) an encoder lear image representations. The
1ttpps: / www.hgggnggaaaaa..oom co/ datasets pppiincooo-nn -n h datassess for- s simase/
resolve/ma n/wiki Im_ for mose. txt
17

---

Under review as a conference paper at ICLR 2023
Table Statisties of datasets for graph-level classification task.
Datasets
IMDB-B IMDB-M COLLAB REDDIT-B
#Graphs
1,000
1,500
5,000
2,000
#Classes
2
3
Avg. #nodes
19.8
13.0
74.5
429.7
feature map generated by ResNet-50 block is projected to 128-D image embedding via a two-layer MLP (2048-D hidden layer with ReLU activation function). Besides, the output vector is normalized by la normalization (Wu al., 2018). We employ two sampled data augmentation strategies to generate positive pairs, and implicitly use other examples in the same mini-batch as negative samples.
For CIFARIO, CIFARIOO and STL10, all models are trained for 1000 epochs with the default batch size B of 256. We use the Adam optimizer (Kingma and Ba, 2015) with learning rate of 0.001 for optimization. The temperature parameter set as 0.5 and the dimension of image embedding is set as 128. For ImageNet- 100 and ImageNet, we train the models with 100 and 400 epochs respectively, and use LARS optimizer (You et al., 2019) with learning rate of 0.3 x B/25 3/256 and weight decay of 10 Here, the batch size is set as 2048 for ImageNet and 512 for ImageNet- 100. respectively. We fix the temperature parameter as 0.1 and the image embedding dimension as 128. After the unsupervised learning, we train supervised linear classifier for 100 epochs on the top of the frozen learned representations.
As for ProSampler, we update the proximity graph per 100 training iterations. We fix the number of neighbors K as 100 for CIFARIO, I0, CIFAR 100 and STL10. The size of neighbor candidate set M is set as 1000 for CIFAR and STL10, and 500 for CIFARIO. Besides, the initial restart probability of RWR (Random Walk with Restart) is set to 0.2 and decays linearly to 0.05 with the training process. For ImageNet- 100 and ImageNet, we keep M as 1000 and K as 500. The restart probability is fixed as 0.1.
E.2 GRAPH REPRESENTATIONS
In graph domain, we use the GraphCL (You et al., 2020) framework as the baseline and GIN (Xu al.. 2018) as the backone. We run ProSampler 5 times with different random seeds and report the mean 10-fold cross-validation accuracy with variance. We apply Adam optimizer (Kingma and Ba, 2015) with learning rate of 0.01, and 3-layer GIN with fixed hidden size of 32. We set the temperature 0.2 and gradually decay the restart probability of RWR (0.2 0.05). Proximity graph will be updated after iterations. The overall hyperparameter settings on different datasets are summarized in Table 8.
Table Hyperparameter settings for graph-level representation learning.
Datasets
IMDB-B IMDB-M COLLAB REDDIT-B
Batchsize Epoch
256
128
128
128
100
50
20
50
t
25
25
50
50
M
300
300
1,000
500
K
100
100
100
100
E.3 TEXT REPRESENTATIONS
In text domain, we use SimCSE (Gao et al., 2021) as baseline method and adopt the pretrained BERT and RoBERTa provided by HuggingFace" for sentence embedding learning. Following the training setting of SimCSE, we train the model for one epoch in an unsupervised manner and evaluate it
Phttps: httr:p::/hhuggingte www.nnginngaaooo wwt.c/..ccoooooooooooooooooooooo co/mode1.
18

---

Under review as a conference paper at ICLR 2023
on STS tasks. Proximity graph will be only built once based the pretrained language models before training. For BERT. we set the batch size to 64 and learning rate to 10 10 For RoBERTa, the batch size is set as 512 and learning rate is fixed as 10 We keep the temperature 0.05, the number neighbor candidates M as 1000, the number of neighbors as 500, and the restart probability 0.7 for both BERT and RoBERTa.
F ADDITIONAL EXPERIMENTS
F. EXTENSIVE STUDIES COMPUTER VISION
and two medium- benchmark datasets, and equip DCL (Chuang al., 2020) and HCL (Robinson et al., 2021)² with ProSampler to investigate its generality. Experimental results in Table 9 show that ProSampler can consistently improve SimCLR and its variants on all the datasets, with an absolute gain of 0.3%~2.5%. We also can observe that the improvement is greater on medium-scale datasets than on small-scale datasets. Specifically, the model equipped with HCL and ProSampler achieves significant improvement (6.23%) STL10 over the original SimCLR.
Here we evaluate the ProSampler on two small-scale (CIFARIO,CIFAL scale (STL.1.,maaeeett-10
Table 9: Overall performance comparison image classification task in term of Top-1 Accuracy.
Method
CIFAR10
CIFAR100
STL10
ImageNet-100
SimCLR
92.13
68.14
83.26
59.30
w/ ProSampler
92.54
68.68
84.38
60.80
DCL
92.28
68.52
84.92
59.90
w/ ProSampler
92.74
68.91
86.39
60.14
HCL
92.39
68.92
88.20
60.60
w/ ProSampler
92.41
69.13
89.49
61.50
F.2 SIMILARITY COMPARISON BETWEEN POSITIVE AND NEGATIVE PAIRS
To explain the performance degradation of DCL and HCL objectives, we select 12 representative banibe and plot the cosine similarity histogram of positive and negative pairs on BERT (top) and RoBERTa (bottom) in Figure 7. We observe the following: (1) At the start of and throughout the training, the positive pairs are assigned a high cosine similarity (around 0.9) by the pretrained language model; (2) The negative similarities begin with relative high score and gradually skew left because of the self-supervised learning. Such phenomenon is consistent to Zhou et al. (2022). DCL and HCL which leverage the difference between positive and negative similarity to reweight the negative scores are inapplicable since the low distribution gap between positive and negative similarities will lead to homogeneous weighting in the objective.
F.3 TEXT REPRESENTATIONS WITH ROBERTA
We also apply ProSampler to the SimCSE with the pretrained RoBERTa, and present the results in Table 10. Similar as the results of BERT, ProSampler can consistently improve the performance of the baseline model. Besides, as discussed in Section 4.1 and Section F.2, the hard negative sampled by ProSampler explicitly can alleviate the low distribution gap between positive score and negative score distribution caused by the pretrained language model, alleviating the performance degradation of DCL and HCL.
PDCL and HCL are more like variants of InfoNCE loss, which adjust the weights of negative samples in the original InfoNCE loss.
19

---

Under review as a conference paper at ICLR 2023
neg pm
Propoct
-035 62 04 0.
Smilrrty
codle Sirarry
Coste Semilrtty
Colkeee Siilerty
Ubrre Sietanty
Costre barty
(a) Batch-1 1
(b) Batch-5
(c) Batch-10
(d) Batch-3125
(e) Batch-9375
(1)
Batch- Batch-15625
60
pOIJAT
Prsuery
Corrs Similrtty
Cosiee Seniarity
CaSie Sania
Cosine Sirvirty
Caskee Sindaity
Coltss Similatty
(g) Batch-1
(hi Batch-5
①
Batch-10 10
(j) Betch-390
(k) Batch- 1172
() Batch-1954
Figure 7: Histograms of cosine similarity BERT (top) and RoBERTa (bottom).
Table 10: Performance comparison for sentence embedding learning based on RoBERTa.
Method
STS12
STS13 STS 14 STS15 STS16 STS-B SICK-R Avg.
SimCSE-RoBERTaaac.
67.90
80.91
73.14
80.58
80.74
80.26
69.87
76.20
w/ ProSampler
68.29
81.96
73.86
82.16
80.94
80.77
69.30
76.75
DCL-RoBERTaanse
66.60
79.16
71.05
80.40
77.76
77.94
67.57
74.35
w/ ProSampler
65.53
80.09
71.00
80.64
78.35
77.75
67.52
74.41
HCI-RoBETTaaae
67.20
80.47
72.44
80.88
80.57
78.79
67.98
75.49
w/ ProSampler
66.01
80.79
73.58
81.25
80.66
79.22
68.52
75.72
F.4 COSINE SIMILARITY AND FALSE NEGATIVE RATIO ON CIFAR100
Here compare the Uniform Sampler, kNN Sampler, and ProSampler in terms of cosine similarity and false negatives on CIFAR 100. Specifically, we show the histogram of cosine similarity for all pairs in sampled batch, and the false negative ratio of the mini-batch in Figure 8. It can be found that ProSampler exhibits a balance of Uniform Sampler and kNN Sampler, which can sample the hard negative pair but only brings slightly greater number of false negatives than Uniform Sampler. More analysis can be found in Section 4.2.
0.035
4.0
Sampler
Sampler PreSampler
ProSamples
3.5
Uniform Sampler
0.030
Uniform Sampler Di
3.0
2.5
FN ratio
0.025
2.0
0.020
1.5
1.0
0.015
0.5
0.010
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0
50
1.00
350
200
Cosine Similarity
Training (x10000
Figure 8: Cosine similarity and false negative ratio on CIFAR100.
F.5 EFFICIENCY ANALYSIS
To further investigate the efficiency of ProSampler, we analyze the wall-clock time performance. Here, we introduce three metrics to analyze the time cost of mini-batch sampling by ProSampler: (1) Batch Sampling Cost (Costs) is the average time of RWR taken to sample mini-batch from a proximity graph; (2) Proximity Graph Construction Cost (Coste) refers to the time consumption of ProSampler for constructing a proximity graph; (3) Batch Training Cost (Costy) is the average time taken by the encoder to forward and backward; (4) Proximity Graph Construction Amortized
20

---

Under review as a conference paper at ICLR 2023
Cost (Costa/s) /t) is the ratio of Coste to the graph update interval t. The time cost of ProSampler is shown Table 11, from which we make the following observations: (1) Sampling a mini-batch Costs takes order of magnitude less time than training with batch Costr at most cases. (2) Although takes 100s for ProSampler to construct a proximity graph in ImageNet, the cost shares across t training steps, which take only Coste/: = 0.2 per batch. A similar phenomenon can be found in the other datasets as well. In particular, SimCSE only trains for one epoch, and proximity graph is only built once.
Table 11: Time cost of mini-batch sampling by ProSampler on a NVIDIA V100 GPU.
Metric
STL10
ImageNet-100
Wikipedia
ImageNet
Costs
0.013s
0.015s
0.005
0.15s
Costa
2s
3s
79s
100s
Costr
0.55s
1.1s
0.08s
1.1s
Costa/t
0.02(t = 100)
0.03(t = 100)
0.005(t 15625)
0.2(t 500)
F.6 COMPREHENSIVE ANALYSIS ABOUT STRATEGIES OF PROXIMITY GRAPH SAMPLING
We conduct an experiment to explore different choices of graph sampling methods, including (1) Depth First Search (DFS); (2) Breadth First Search (BFS); (3) Random Walk (RW); (4) Ran- dom Walk with Restart (RWR). Table 12 presents overall performance comparison with different graph sampling methods. Besides, we illustrate the histograms cosine similarity for all pairs from sampled batch after finishing training and plot the percentage of false negatives in the mini-batch during training in Figure 9. It can be observed that although BFS brings the most similar pairs the mini-batch, it performs worse than the original SimCLR since it introduces substantial false negatives. While having a slightly lower percentage of false negatives than RWR, DFS and RW do not exhibit higher performance since they are unable collect the hard negatives in the mini-batch. The restart property allows RWR to exhibit a mixture of DFS and BFS, which can flexibly modulate the hardness of the sampled batch and find the best balance between hard negatives and false negatives. Benefiting from it, RWR achieves the best performance over the other sampling methods.
Table 12: Overall performance comparison with different graph sampling methods.
Table 13: The performance comparison of different batchsize B.
Method
BFS
DFS
RW
RWR
B
16
32
64
128
256
CIFAR1O
91.03
92.14
92.28
92.54
CIFARIO
79.36
84.64
89.09
91.03
92.54
CIFARI00
65.15
68.29
68.33
68.68
CIFAR100
46.59
56.24
61.30
65.96
68.68
STLIO
77.08
83.05
83.54
84.38
STL10
56.31
68.61
74.24
82.56
84.38
8r5
6620
BF5
RP5 KWI
BFS KWA
6004
DF5
0022
Freqquency
Frequeecy
914
0.50
Training Stsptx1000)
Training Stepic1000
Cootin Similartty
Coolne Similaryy
(a)
(b)
(c)
(d)
Figure 9: (a,b) Percentage of false negative a batch sampled from CIFARIO and CIFAR100 over the training step using different graph sampling methods. (c,d) Histograms of cosine similarity of all pairs in a batch for embeddings trained on CIFARIO and CIFAR 100 using different sampling methods.
21

---

Under review as a conference paper at ICLR 2023
F.7 COMPARISON BETWEEN PROXIMITY GRAPH AND KNN GRAPH
To demonstrate the effectiveness of proximity graph, we do an ablation study by replacing proximity graph with kNN graph which directly selects neighbors with the highest scores for each instance from the whole dataset. The neighbor number is 100 by default. The comparison results are shown Table 14, from which we can observe that proximity graph outperforms the kNN graph by a margin. ProSampler with kNN graph even performs worse than the original contrastive learning method because of the false negatives.
Method
SimCLR
kNN graph
proximity graph
CIFAR-10
92.13 68.14
90.47 62.67
92.54
CIFAR-100
68.68
Table 14: Performance comparison of different graph construction methods.
To develop a intuitive understanding of how Proximity graph alleviates the false negative issue, Figure 10 plots the changing curve of false negative ratio in batch. The results show that Proximity graph could discard the false negative significantly: by the end of the training, kNN will introduce more than 22% false negatives in batch, while Proximity graph brings about 13% the CIFARIO dataset. Similar phenomenon can also be found on CIFAR 100 dataset.
0.035
0.24
kNN graph Proximity graph
kNN graph Proximity graph
0.22
0.030
0.20
FN ratio
FN ratlo
0.025
0.18
0.16
0.020
0.14
0.015
0.12
0.10
0.010
50
100
150
200
0
50
100
150
200
Training Step(x1000)
Training Step(x1000)
(a) CIFAR10
(b) CIFARI00
Figure 10: Percentage of false negative using different graph building methods over the training step.
F.8 PARAMETER ANALYSIS
F.8.1 BATCHSIZE
To analyze the impact of the batchsize B, we vary B in the range of (16, 32, 64, 128, 256} and summarize the results in Table can be found that larger batchsize leads to better results, which is consistent with the previous studies (Chen et al., 2020; He et al., 2020; Kalantidis et al., 2020).
F.8.2 IMPACT OF NEIGHBOR NUMBER K
In Figure 11, we investigate the impact of the neighbor number K on ImageNet- 100 dataset with the default ProSampler setting. We observe that an absolute improvement of 1.1% 1 with the increasing size neighbors. Specifically, model achieves an absolute performance gain of 0.9% from K 100 to K = 300, while only obtains 0.2% from K 300 to K 500. Such experimental results are consistent with our prior philosophy, in which sampling more neighbors always increase the scale of proximity graph and urging ProSampler to explore smaller-scope scope local cluster (i.e. sample harder negatives within batch). leading to a significant improvement in performance at first. However, performance degrades after reaching the optimum, because larger K introduces more easy negatives.
22

---

Under review as a conference paper at ICLR 2023
61.0
60.8
60.8
60.5
60.6
60.5
Top-1 Accuracy
60.0
59.8
59.7
59.5
100
200
300
400
500
600
Neighbar Number K
Figure 11: Impact of neighbor number K,
F.8.3 PROXIMITY GRAPH UPDATE INTERVAL.
Proximity graph will updated per & training iterations, and analyze the impact of f, we vary t in the range of [50,100,72)) 10,,100,2004440 ,400) and summarize the results in Table 15. It can be observed that update intervals that are too short (t 50) or too long (t = 400) will degrade the performance. The proximity graph that is frequently updated results in unstable
possible reason is that sampling learning the model. Besides, the distribution of instances in the embedding space will change during the training process, resulting in shift in hard negatives. As result, after few iterations, the aay-edd graph cannot adequately capture the similarity relationship.
Table 15: Performance comparison with different update interval CIFAR10 and CIFAR
Update Interval
50
100
200
400
CIFARIO
92.29
92.54
92.34
92.26
CIFARION
68.37
68.68
67.83
68.59
F.9 TRAINING CURVE
We plot the training curves on STLI0 and ImageNet- 100 respectively. As shown Figure 12, on STL10 dataset, ProSampler takes only about 600 epochs to achieve the similar performance as the original SimCLR, which takes 1000 epochs. A similar phenomenon can be seen on ImageNet-100 All these results manifest that ProSampler can bring model better and faster learning.
60
02
Accuracy
84
82.5
$3.04
81.81
23.5
10.39
07.89
01.28
5294
$1.25
Top-1 Accuracy
53
52.6
58.0
57.5
78.44
42.0
31.4
BinCLRiPrSSemok
2003
160
Epochs
Epochs
(a) STLIO
(b) ImageNet-100
Figure 12: Training curves for image classification task on STL10 and ImageNet-100..
23

---

Under review as a conference paper at ICLR 2023
F.10 CASE STUDY
To give an intuitive impression of the mini-batch sampled by ProSampler, we show some real cases of the negatives sampled by ProSampler and Uniform Sampler in Figure 13. For given anchor (a cat or a dog), we apply ProSampler and Uniform Sampler to draw a mini-batch images, and pick the images with the highest inner product with anchor. Obviously, compared with Uniform Sampler, the images sampled by ProSampler are more semantically relevant to the anchor in terms of texture, background or appearance.
Anchor
(a) Uniform Sampler
Anchor
(b) ProSampler
Anchor
(c) Uniform Sampler
Anchor
(d) ProSampler
Figure 13: Case study of the negatives sampled by ProSampler and Uniform Sampler based on the encoder trained for 100 epochs on ImageNet. Given an anchor image (Cat or Dog), (a,c) select 10 images with the highest similarity from mini-batch sampled by ProSampler, and (b,d) randomly select 10 images from mini-batch sampled by Uniform Sampler.
24


Reviews:
[{"review_id": "tcHYl5OUSp7", "reviewer": "Reviewer_FNA5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a negative sampling strategy for contrastive learning, which many contrastive learning-related frameworks can incorporate to improve performance. Instead of the uniform sampler and kNN sampler, the proposed proximity graph could well capture the similarity relationships among instances. Random walks among the proximity graph can ﬂexibly explore the negatives. Experiments on several datasets demonstrate the superiority.", "summary_of_the_review": "The proposed method is quite simple and is highly related to existing graph-based positive sample selection methods. The overall novelty and contribution are incremental. Besides, the experimental improvement is also marginal.", "strength_and_weaknesses": "Strengths:\n\n(1) The proposed method is simple and effective.\n\n(2) The authors provide a detailed theoretical analysis.\n\n(3) The authors conduct extensive experiments for validation, including several large datasets and different modalities.\n\nWeaknesses:\n\n(1) The proposed method is very simple, which is similar to searching hard negative samples from a top knn graph constructed by different similarity computation strategies. The overall contribution is incremental from this point. I wonder why the authors pick M neighbors by distance and select K nearest ones by inner product operation. And why do not you directly select the K nearest neighbors?\n\n(2) To a certain extent, the construction of a mini-batch with hard negative samples is similar to filtering out the positive samples from the original mini-batch. There are already several methods [1,2] that adopt affinity graphs to select positive pairs from the original mini-batch and achieve much better results on contrastive feature learning and clustering tasks. In this case, the novelty of this paper is unsatisfying. \n\n(3) The main motivation of this paper lies in the influence of batch size on existing contrastive learning methods. According to MoCo v2 and MoCo V2+, the influence of batch size is marginal. I wonder whether the proposed sampling strategy still works for such a situation and please give more explanations.\n\n(4) According to Table 1, the authors only present results of 100 and 400 epochs. I wonder whether the final results can be improved by the ProSampler, such as the results after 800 or 1,000 epochs. Besides, compared with SimCLR, SwAV, and BYOL, the improvement on ImageNet by [1] is much more significant than the proposed method. Please compare the results with [1] in detail.\n\n(5) According to Table 9, the improvement is marginal on these small datasets.\n\n\n[1] Weakly Supervised Contrastive Learning, ICCV 2021\n[2] Graph Contrastive Clustering, ICCV 2021\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LxT0PjeyzN", "reviewer": "Reviewer_4epo", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on how to sample hard negative pairs in every batch, which is an important topic in contrastive learning. The paper motivates by the defects of uniform and KNN strategies, and then the authors propose to construct a proximity graph and employ the random walk to generate each batch. According to the construction of the proximity graph (selecting samples randomly and then choosing the k nearest ones), the sampling method can be regarded as a combination of uniform sampling and KNN.", "summary_of_the_review": "The paper is well-written and I admit that the topic is meaningful. However, I concern whether the novelty of the sampling is significant enough for ICLR. I would like to update my score during the discussion period. ", "strength_and_weaknesses": "### Strength \n- The paper is well-organized and easy to follow. The motivation is clarified and the sampling of hard negative pairs is a promising topic. \n- The experiments are sufficient for me. \n\n### Weakness\nMy main concern is the limitation of the novelty of the sampling strategy. The proximity graph, the core of the proposed sampling, is constructed through two steps: \n- Randomly (Uniformly) select multiple points,\n- Choose the k nearest ones.\nIt seems like the method to introduce randomness to KNN. In other words, it seems like a combination of the two existing strategies. The subsequent random walk step is another step to introduce further stochasticity.\n\nAlthough some theoretical analyses are provided, they are not attractive to me. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LHGTUc8ePl", "reviewer": "Reviewer_nXV4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a new sampling strategy for the construction of batches containing hard-negatives (avoiding false negatives in the batch) for contrastive learning methods. According to previous studies, it is legitimate to assume that hard negative pairs contribute the most in training the network. The method is based on a proximity graph and the sampling is performed by short random walks (-with restart). Results show improvements over a set of different tasks and datasets.", "summary_of_the_review": "The authors propose a new solution to the problem of selecting hard-negatives from a dataset without including high percentages of false negatives (as it happens in the KNN-sampler). The solution seems to be not expensive in computational terms, some details are missing that could clarify any doubts about the cost required for the construction of the sampler (graph-based) and memory required.\n", "strength_and_weaknesses": "**Strength**\n- creating more informative mini-batches.\n- selecting hard negatives examples \"globally\".\n- time complexity and time cost of mini-batch sampling and proximity graph construction (*)\n\n\n**Weaknesses**\n\n- what is the space complexity? can a graph representing imagenet-20K be kept in memory?\n\n- \"Sampling on the proximity graph can better exploit the hard negatives \"globally\" by bridging in similar instances from the entire dataset.\"\n\n1. **Proximity Graph Construction**: it is not clear if the construction of the graph is based on all the examples of the dataset or if there is a random selection of the examples.\n \n2. Looks like \"that the candidate set for each instance is formed by randomly picking a number of neighbor candidates\"\n  - if the candidates are drawn at random how is it possible to say that the method can \"exploit the hard negatives globally\"?\n  - if the neighbors are given, it means that there's an additional cost about knowing which neighbors of a certain node are? how are neighbors found?\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IUqg9oeU3ub", "reviewer": "Reviewer_uJHq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a batch sampling method aimed at generating harder negative samples for contrastive learning methods that use other samples in a batch as negatives, for instance SimCLR.\n\nBrief description of the method: the approach builds a graph whose nodes are training datapoints, and each node is connected to the $k$ nearest neighbors (distances measured using stale embeddings) of a uniformly subsampled graph (the subsampling stochastically ensures there is some connections between less similar samples). A batch of size $B$ is generated by selecting a random starting node, and running a random walk until $B$ distinct nodes have been visited. In order to ensure the sampling process doesn't drift too far from the starting point, each random walk step has a fixed probability of returning to the starting node. \n\n ", "summary_of_the_review": "Congratulations on a nice paper. The approach is:\n\n- well motivated: global methods for generating hard negatives are likely to work better that in-batch methods.\n- sensibly executed: the proposed algorithm, based on constructing a similarity graph and running a random walk, is a natural approach building on core graph algorithms. There will be many many other possible implementations people could test too. For instance, simply define the weight $w_{ij}$ of edge $(i,j)$ to be the similarity score $e_i \\cdot e_j$ between the embeddings of points $i$ and $j$. Then run a random walk where at. node i, the next node is sampled from the distribution Softmax($w_{ij}$) (softmax over all $j$'s). Probably keeping the chance of returning to the starting node at each step. My point here is that the proposed ProSampler is just a single example of many similar algorithms based on random walks on similarity graphs, many of whom will probably work well too. This is good in my books since it means that the paper hasn't just proposed a single fiddly algorithm that they managed to get to work, but that there is a core underlying idea, which is robust to many different possible implementations. \n- thoroughly evaluated: downstream performance improves. on lots of tasks across three modalities. Visualizations (e.g., Fig 12) and comparisons of negative similarities (e.g., Fig 5) give good sanity checks that the method is working as hoped. \n\n\nIn all this is a solid piece of work and I can't see any major flaw that could justify rejection.\n", "strength_and_weaknesses": "**Strengths**\n\n- A good, broad set of experiments show that the approach, called ProSampler, lead to better downstream performance on many tasks (images, text, graphs). They also show that ProSampler can be successfully combined with existing in-batch hard negative sampling methods such as that of Robinson et al. \n\n- Methodological studies show that ProSampler behaves as expected in a number of ways: for instance it samples negatives that are harder (higher cosine similarity) than uniform sampling, but less similar than the $k$ nearest neighbors (hardest negatives possible). \n\n- My personal main strength is the proposal to use graphs based on input similarities for batch sampling. Many other alternative such methods could be tried too.\n\n**Weaknesses**\n\n- the two additional hyperparameters will probably be a bother to users. At least they appear to be reasonably robust, so decent default choices can be used. \n\n- the paper probably could have been made more enlightening by focusing more on proposing a more general underlying principle (graphs build from input similarities) and talking more about how this graph should be built. At the moment, the proposed method is simply given, and it is very believable. But more work is left to the reader than is necessary terms of  \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject