Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: For pair-wise learning-to-rank problems, it often suffers from class imbalance problem when constructing training data where negative class examples are much more frequent then positive class examples. Negative example sampling is an important differentiator on training and classifier performance. this paper proposed a method on negative class sampling by considering the degree of vertexes. It proposed a rejection function in order to sample with higher probability from high degree vertex instead of using edge level random sampling. It provided both theoretical analysis and experiments on real world datasets to demonstrate the effectiveness on the proposed sampling approach.
main_review: 1. the paper studies an important topic on negative sampling for the learning-to-rank problem 
2. the proposed method is based on an intuitive analysis on the vertex level imbalance sampling instead of commonly used edge level sampling. 
3. It provided both theoretical analysis and experiments on real world datasets to demonstrate the effectiveness on the proposed sampling approach.
summary_of_the_review: The paper is marginally innovative. The method it proposed is intuitive and clear. However, it is unclear if the proposed methods is applicable to any form of learning-to-rank problems or it is tied to certain learning-to-rank models, such as MF. It would be very useful to clarify the how generic the proposed sampling approach is applicable explicitly. For the learn-2-rank models mentioned in the paper,  I would recommend it for a poster paper, the writing can also be improved by directly citing the models used in the experiments instead of listing them in appendix.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper investigates personalized ranking from implicit feedback where we leverage a set of positively labeled data (for which interactions exist such as clicking, purchase etc) and use all the items with no explicit feedback as negative instances and aim to learn a ranking model for recommendation. The idea is to minimize a loss over triplets (u,i, j) over users, a positively labeled instance and a negatively labeled instance to learn the embeddings for items and users. 

The main observation in this paper is that in addition to known unbalancedness issue on edge level (proportion of positive instance to negative instance), the existing methods also suffer from vertex-level imbalance problem due to fact that due to sampling, the number of times an item appears as positive and negative is disproportionate. In particular,  popular items with degree (positiveness) greater than average item degree are under-sampled as negative samples, while cold-start items with degree less than average degree are over-sampled as negative instances. This in turn makes the norm of learned embeddings for popular items towards infinite after a certain training iterations. This issue even occurs if one utilizes an under-sampling/oversampling to solve the edge-level imbalance issue. The observations are supported both theoretically and empirically.

main_review: To overcome vertex-level imbalance issue, the authors propose a two-phase sampling approach dubbed as Vital Negative Sampler (VINS), by sampling a negative item with a larger degree (to explicit positive connection between item degree and the learned embeddings) and close prediction score to the given positive sample (to leverage relative rank position of positive and negative items for finding more informative negative samples). 


The paper is well-written and the authors supported the claims made with theoretical and empirical analysis. However there few key issues that prevents me from giving it a high-score and makes me to lean toward rejection:

(1) While the mentioned issues totally make sense and it is appreciated that authors conducted experiments to provide intuition, but in objective (1) the regularization terms are dropped. Focusing on Imbalanced Item Theorem that indicates the embedding of popular items becomes extremely large, but I was left wondering if this issue can not be alleviated via regularization. Note that the number of times the embedding of an item  will be regularized is proportional to the number of times it is sampled, which possibly avoids embedding explosion as claimed. Even more interesting, if we adaptively pick the regularization parameter for each item proportional to its degree, it might resolve the issue.

(2) While the proposed two-stage sampling idea looks interesting, in my opinion it looks incremental and lacks enough novelty. For example this is simply the hard negative sampling in contrastive learning or even utilizing a dynamic weighted loss based on the loss of current model on each negative sample (note that here we can sample a batch of negative samples and avoid the computation burden of VINS). 

(3) The proposed idea can be considered as a sampling variant of ranking with accuracy at top (push-norm) where we try to push as many as possible negative samples below positive items by changing the pairwise ranking loss into a push-norm based loss. It would be interesting to discuss the proposed idea in context of this line of research

Rudin, C. (2009). The P-Norm Push: A Simple Convex Ranking Algorithm that Concentrates at the Top of the List. Journal of Machine Learning Research, 10, 2233-2271.

Li, Nan, Rong Jin, and Zhi-Hua Zhou. "Top Rank Optimization in Linear Time." NIPS. 2014.
summary_of_the_review: Overall, I like the observations made and the proposed sampling idea, but due to issues discussed above I found the contribution incremental and leaning towards rejection.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes to improve the negative sampling process for training pairwise ranking models in personalized recommender systems. Negative sampling plays an important role in the above application, as it can largely impact the model performance in terms of both training efficiency and recommendation accuracy.
Authors first analyze the vertex-level imbalance problem that exists in current sampling-based methods, i.e., popular items are unevenly sampled w.r.t. their chances as positive and negative. They observe that this may cause the imbalanced distribution of embedding norms between popular and long-tailed items, which can possibly harm the training efficacy and efficiency.
To cope with this problem, this paper proposes a simple but effective negative sampling method. The core idea is to choose a negative candidate with larger popularity than the given positive item. To maintain sample quality, the dynamic relative rank position of positive and negative items is also considered, which has already proven to be useful in previous works. Specifically, the proposed VINS method is achieved through a bias sampler with reject probability, which cooperates with an item buffer to enable efficient sampling of informative instances.
Empirical results on several real-world datasets demonstrate its superiority on both efficiency and effectiveness. 
main_review: Strengths:
1.	This paper focuses on an important and practical problem in training pairwise ranking models for recommender systems.
2.	The proposed method is simple but effective, which satisfies the requirements for a suitable negative sampling method.

Weakness:
1.	The novelty of this paper is limited. First, the analysis of the vertex-level imbalance problem is not new, which is a reformulation of the observations in previous works [Rendle and Freudenthaler, 2014; Ding et al., 2019]. Second, the designed negative sampler uses reject sampling to increase the chance of popular items, which is similar to the proposed one in PRIS [Lian et al., 2020].
2.	The paper overclaims on its ability of debiasing sampling. The “debiased” term in the paper title is confusing.
3.	The methodology detail is unclear in Sec. 4.2. The proposed design that improves sampling efficiency seems interesting but the corresponding description is hard to follow given the limited space.
4.	Space complexity of the proposed VINS should also be analyzed and compared in empirical studies, given that each (u, i) corresponds to a $buffer_{ui}$.
5.	Experiment results are not convincing enough to demonstrate the superiority of VINS on effectiveness and efficiency.
-	For effectiveness, the performance comparison in Table 1 is unfair. VINS sets different sample weights $W_{ui}$ in the training process, while most compared baselines like DNS, AOBPR, SA, PRIS set all sample weights as 1. 
-	For efficiency, Table 2 should also include the theoretical analysis for contrast.

summary_of_the_review: As mentioned in the weakness, the limitations on novelty, methodology design, and conducted experiments prohibit its acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This is an interesting and solid paper that theoretically demonstrates the connection between a long-tail distribution and the essentiality of hard negative sampling, proposes a simple yet effective negative sampling method, and conducts sufficient experiments. 
main_review: strength:
1. This work formalizes the class-imbalance problem existing in the contrastive learning loss for recommendation task and gives a simple but effective solution.
2. The theoretical analysis provided by the authors can well support the claims.
3. Sufficient experiment results demonstrate the superiority of the proposed method.

weakness:
1. The proposed method seems to be specialized in recommendation problems.
2. The presentation can be further improved with more discussion of the main content. 

Learning from class-imbalance data has been sufficiently explored during the last few years. However, most of them focus on the imbalance issue caused by the number of labels but discard the same problem existing in the contrastive learning methods. This work attempts to explore the imbalance issue when we optimize the recommender with the help of contrastive loss. We usually extract a contrastive training example with the assumption that the predicted similarity of a pair of nodes in the observed edge (positive) should have larger than the unobserved (negative) one. It's noted that the nodes can appear in both positive and negative edges, and node frequency usually follows a long-tail distribution. Because of that, there exists a significant class-imbalance bias in the contrastive learning method for the recommendation task. As far as I know, this problem has been insufficiently studied. In this work, a completed theoretical analysis is given to reveal an interesting finding that the imbalance degree has a positive relation to the item degree and can lead to the infinite norm of item embeddings, in particular those suffering from the class-imbalance problem. Along with this observation, the authors propose a debiased negative sampling method that can adaptively re-weight the loss according to the ranking position of imbalanced items. The proposed approach defines a conditional probability depending on both the given user and positive items. However, it's usually difficult to obtain an effective hard negative sample from the given probability due to the large size of the item database. In order to deal with this problem, the proposed method combines a biased random walk towards the popular items and an adaptive filtering criterion for efficiently retrieving qualified hard negative samples. Thorough experimental results demonstrate the superiority of the proposed method in real-world data. Overall, this work is clearly presented with sufficient discussion and details for further reproducibility.

concerns:
1. The proposed method seems to greedily select items with a large prediction score. While those items might be the true positive. Could you please give a justification about how to deal with the false negative issue?

2. Is the re-weighting method an essential choice? what if we remove the weight?

3. Could you provide more details on why RejectSampler depends on a biased random walk?


summary_of_the_review: This work gives sufficient theoretical analysis about the class-imbalance problem and provides a simple but effective debiasing method to advance the optimization performance for item recommendation tasks. Sufficient experiments are provided. Overall, it's an interesting, solid and well-organized paper studying an important problem.
review_title: null

Meta-review: The reviewers remained concerned about the overall novelty of the paper, finding the contributions somewhat incremental. The authors are encouraged to better substantiate design choices that they make, to improve the overall presentation, and to contrast with the works/line of research brought up by the reviewers.
Decision: Reject