Negative sampling approaches are prevalent in implicit collaborative filtering for obtaining negative labels from massive unlabeled data. As two major concerns in negative sampling, efficiency and effectiveness are still not fully achieved by recent works that use complicate structures and overlook risk of false negative instances. In this paper, we first provide a novel understanding of negative instances by empirically observing that only a few instances are potentially important for model learning, and false negatives tend to have stable predictions over many training iterations. Above findings motivate us to simplify the model by sampling from designed memory that only stores a few important candidates and, more importantly, tackle the untouched false negative problem by favouring high-variance samples stored in memory, which achieves efficient sampling of true negatives with high-quality. Empirical results on two synthetic datasets and three real-world datasets demonstrate both robustness and superiorities of our negative sampling method.

In above examples, each observed interaction normally indicates a user's interest on an item, i.e., a positive label, while the rest unobserved interactions

Weaknesses: I don't think the proposed algorithm to leverage the variance is fully sound. The user memory set Mu is updated on each iteration by first uniformly sampling additional items and then retaining those with higher scores (with probability proportional to softmax of the score). First, for datasets that have lots of items, uniform sampling is very unlikely to produce hard negatives with high scores so this procedure can be highly inefficient. Second, since new samples are likely to have lower scores, one either has to increase the temperature or leave Mu relatively static between iterations. If Mu is static then training can saturate and the model can overfit to these negative examples.

The initial reviews were mixed for this paper. However, during the discussion, a certain consensus emerged regarding the value of this contribution. In particular, the reviews agree that the proposed method is simple and effective. In the proposed study, the method seems to outperform (by a small margin) others consistently. The main negative is the high computational and memory cost of the approach.

Negative sampling approaches are prevalent in implicit collaborative filtering for obtaining negative labels from massive unlabeled data. As two major concerns in negative sampling, efficiency and effectiveness are still not fully achieved by recent works that use complicate structures and overlook risk of false negative instances. In this paper, we first provide a novel understanding of negative instances by empirically observing that only a few instances are potentially important for model learning, and false negatives tend to have stable predictions over many training iterations. Above findings motivate us to simplify the model by sampling from designed memory that only stores a few important candidates and, more importantly, tackle the untouched false negative problem by favouring high-variance samples stored in memory, which achieves efficient sampling of true negatives with high-quality. Empirical results on two synthetic datasets and three real-world datasets demonstrate both robustness and superiorities of our negative sampling method.