Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strengths:

(1) The proposed method is simple and effective.

(2) The authors provide a detailed theoretical analysis.

(3) The authors conduct extensive experiments for validation, including several large datasets and different modalities.

Weaknesses:

(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?

(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. 

(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.

(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.

(5) According to Table 9, the improvement is marginal on these small datasets.


[1] Weakly Supervised Contrastive Learning, ICCV 2021
[2] Graph Contrastive Clustering, ICCV 2021


clarity,_quality,_novelty_and_reproducibility: Please refer to my detailed comments above.
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: ### Strength 
- The paper is well-organized and easy to follow. The motivation is clarified and the sampling of hard negative pairs is a promising topic. 
- The experiments are sufficient for me. 

### Weakness
My 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: 
- Randomly (Uniformly) select multiple points,
- Choose the k nearest ones.
It 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.

Although some theoretical analyses are provided, they are not attractive to me. 
clarity,_quality,_novelty_and_reproducibility: - The paper is quite well-written and well-organized. The motivation is clear and convincing. 

- The novelty, however, is limited for me. 

- The source code is provided in supplementary. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: **Strength**
- creating more informative mini-batches.
- selecting hard negatives examples "globally".
- time complexity and time cost of mini-batch sampling and proximity graph construction (*)


**Weaknesses**

- what is the space complexity? can a graph representing imagenet-20K be kept in memory?

- "Sampling on the proximity graph can better exploit the hard negatives "globally" by bridging in similar instances from the entire dataset."

1. **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.
 
2. Looks like "that the candidate set for each instance is formed by randomly picking a number of neighbor candidates"
  - if the candidates are drawn at random how is it possible to say that the method can "exploit the hard negatives globally"?
  - 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?




clarity,_quality,_novelty_and_reproducibility: The paper is clear, well written and easy to read. It introduces a novelty in terms of creating more informative and effective mini-bacthes for training contrastive learning methods. 
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

Brief 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. 

 
strength_and_weaknesses: **Strengths**

- 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. 

- 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). 

- 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.

**Weaknesses**

- 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. 

- 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  



clarity,_quality,_novelty_and_reproducibility: The novelty lies in the problem framing: there are many hard negative sampling methods for contrastive leanring, but many either 1) work by mixing, reweighing etc. samples from a uniformly sampled mini-batch, or 2) add some additional mechanism such as a memory bank. The proposed method is well distinguished from these approaches, by keeping the SimCLR-style in-batch negative sampling, but more intelligently sampling the batch itself to ensure harder samples.

Approach comes with adequate implementation details. I **strongly encourage** the authors to release their code, which they do not currently state that they plan to do. 

Clarity is also good, but can always be improved. Take some care to make sure all details are explained sequentially and clearly. For instance one silly thing that tripped me up for a bit was the line "for each instance $v_i$ by randomly picking $M(M < N)$ neighbor candidates." I wasn't clear how these $M$ samples were being picked - was it uniformly? Or using some other sampling algorithm? After searching and finding no further description of how this sampling is done I concluded it was uniformly. But you can save the reader this time by being precise and stating that it is uniform.
summary_of_the_review: Congratulations on a nice paper. The approach is:

- well motivated: global methods for generating hard negatives are likely to work better that in-batch methods.
- 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. 
- 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. 


In all this is a solid piece of work and I can't see any major flaw that could justify rejection.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Thanks for your submission to ICLR. 

This paper ultimately had two positive and two negative reviews, which continued to be the case after discussion.  On the positive side, reviewers noted that the method was simple, with a theoretical analysis, and solid experiments.  On the negative side, two reviewers noted that the approach was incremental and similar to existing techniques, as well as having unclear practicality.

The reviewers both commented during the discussion phase that their initial concerns were still present even after the rebuttal.  With only two of the four reviewers advocating for accepting the paper, and lingering questions remaining about the novelty and the method's incremental nature, I am going to recommend a reject.
justification_for_why_not_higher_score: There is just not enough here to warrant recommendation to accept.  Two of the reviewers are positive but the issues raised by the negative reviewers did not seem to be adequately addressed.
Decision: Reject