PaperlayerView exact revision on arXiv

Source-linked AI summary

Simplify and Robustify Negative Sampling for Implicit Collaborative Filtering

Jingtao Ding, Yuhan Quan, Quanming Yao, Yong Li, Depeng Jin

arXiv:2009.03376v1cs.LGcs.IR

TL;DR

Implicit CF needs efficient, high-quality negative sampling from massive unlabeled data, but unobserved interactions can be false negatives and prior hard-negative methods may be complex and overlook that risk. SRNS maintains a memory of promising high-score candidates and alternates score-based memory updates with variance-based sampling to select reliable negatives efficiently. SRNS demonstrates robustness on synthetic and real-world datasets and consistently outperforms seven baselines on three real-world datasets, achieving a relative improvement of 4.71∼8.40% w.r.t. NDCG@1.

  • Problem

    Implicit CF needs efficient, high-quality negative sampling from massive unlabeled data, but unobserved interactions can be false negatives and prior hard-negative methods may be complex and overlook that risk.

    Source: §1 · pp. 1–2

  • Method

    SRNS maintains a memory of promising high-score candidates and alternates score-based memory updates with variance-based sampling to select reliable negatives efficiently.

    Source: §1 · p. 2

  • Results

    SRNS demonstrates robustness on synthetic and real-world datasets and consistently outperforms seven baselines on three real-world datasets, achieving a relative improvement of 4.71∼8.40% w.r.t. NDCG@1.

    Source: §4.3 · p. 8, §5 · p. 9

  • Takeaways & Limitations

    The reported experiments support SRNS’s robustness and superiorities for negative sampling in implicit CF.

    Source: §5 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

Implicit CF learns from positive-only interactions by treating sampled unobserved pairs as negatives, but those pairs can include false negatives. SRNS uses a score-based memory and variance-based sampling to address efficiency, sample quality, and false-negative risk.

1 Introduction

  • In implicit CF, observed interactions are positive labels, and a few unobserved interactions are sampled as negatives to train the model to score positives higher.Source: §1 · p. 1
  • Negative sampling must be efficient over a huge unlabeled interaction pool and effective at selecting useful negatives, even though some unobserved interactions are false negatives.An item may be ignored because of its displayed position or form rather than user dislike.Source: §1 · p. 1
  • Prior hard-negative methods can be inefficient when they use complex GAN structures and overlook false negatives, weakening robustness.Earlier approaches often replace uniform sampling with another distribution, while hard-negative strategies emphasize informative samples.Source: §1 · pp. 1–2
  • The paper frames negative sampling as efficient learning from unlabeled data with noisy labels and identifies challenges in modeling true-negative distributions, measuring sample quality, and sampling efficiently.True negatives are hidden among false negatives in the massive unlabeled data, making informativeness and reliability important together.Source: §1 · p. 2
  • SRNS uses score-based memory to retain promising high-score candidates and variance-based sampling to reduce false-negative risk, alternating these steps to sample efficiently.The method is motivated by the finding that important high-score instances are rare, while false negatives tend to have stable predictions across training iterations.Source: §1 · p. 2
  • Experiments on two synthetic datasets show robustness under varied noise, while three real-world datasets show superior effectiveness and efficiency over state-of-the-art baselines.Source: §1 · p. 2

2 Background

Implicit CF training selects a scoring function, objective, and negative-sampling distribution. The background describes pairwise ranking from observed and sampled interactions and contrasts uniform sampling with harder alternatives.

2 Background

  • Training an implicit CF model involves choosing a scoring function, objective function, and negative-sampling distribution.The scoring function estimates user–item relevance using user and item embeddings; candidates include matrix factorization, multilayer perceptrons, and graph neural networks.Source: §2 · p. 2
  • Table 1 compares SRNS with related methods and defines notation for item rank, popularity, batch size, score-computation cost, lazy-update epoch, and false-negative rate.Source: Table 1 · p. 3
  • The learning objective compares an observed interaction with a sampled unobserved interaction, maximizing the likelihood of the pairwise ranking relation; alternatives include hinge and binary cross-entropy losses.Source: §2 · p. 3
  • Uniform sampling is widely used but yields low-quality samples; prior work instead samples harder instances, including GAN-based approaches, though these approaches are not sufficiently robust to false negatives and GAN structures are more complex.Source: §2 · p. 3

3 SRNS: the Proposed Method

SRNS uses a small, dynamically updated per-user memory and variance-based sampling to target informative negatives while reducing false-negative risk. Its design follows findings that high-scored negatives are rare and false negatives have lower prediction variance than hard negatives.

3.1 Understanding False Negative Instances

  • Only a few negative instances have large scores, while false negatives and hard negatives both score highly but false negatives have lower prediction variance.Harder negative samples are also more likely to be false negatives.Source: §3.1 · pp. 3–4

3.2 SRNS Method Design

  • SRNS assigns each user a small memory of hard-negative candidates, dynamically refreshing it by adding uniformly sampled instances and retaining hard candidates through score-based updating.All positive instances for a user share that memory; the update considers S1 + S2 candidates.Source: §3.2 · pp. 4–5
  • SRNS samples from memory using both prediction score and variance, favoring high-variance candidates to avoid false negatives that maintain high scores across training.The variance weight is warmed up gradually because instances tend to have high variance early in training.Source: §3.1 · p. 4, §3.2 · p. 5
  • SRNS bootstraps by first learning to distinguish easier negative instances, then using its variance criterion to address the remaining harder instances.The authors connect this sequence to deep CF models memorizing easy training instances before hard ones.Source: §3.2 · p. 5

3.3 Complexity Analysis

  • For each positive instance, memory updating and variance-based sampling cost O((S1 + S2)T), reducible to O((S1 + S2)T/E) with lazy updates every E epochs.SRNS's model complexity is about (|U| + |I|)F; the paper describes its time complexity as simpler than related approaches.Source: §3.3 · p. 5

4 Experiments

Experiments first test robustness under controlled synthetic noise, then compare SRNS on real implicit-CF datasets.

4.1 Experimental Settings

  • Synthetic tests inject false negatives into memory at varying rates, while real-data experiments use leave-one-out splits and evaluate Recall and NDCG against sampling and non-sampling baselines.The synthetic datasets are ML-100k and Ecom-toy; real-data baselines include Uniform, NNCF, hard-negative methods, and ENMF.Source: §4.2 · p. 6, §4.1 · p. 6

4.2 Synthetic Noise Experiments

  • Across different synthetic noise levels σ, variance-based sampling consistently improves test Recall and NDCG over difficulty-only sampling.Increasing noise harms model performance overall.Source: §4.2 · p. 7, Figure 2 · p. 7
  • Linearly increasing αt with epoch performs better than flat or decreasing schedules, leveraging variance-based sampling after false negatives become more stable.The increase stops at threshold T0.Source: §4.2 · p. 7
  • Under extreme noise (σ = 1), difficulty-only training first reaches high test NDCG and then declines, indicating early avoidance of false-negative impact.The noise injection extends false negatives to 100% of the original test set on ML-100k and 40% on Ecom-toy.Source: §4.2 · p. 7, Figure 3 · p. 7

4.3 Real Data Experiments

  • SRNS consistently outperforms seven baselines on three real-world datasets, with a 4.71∼8.40% relative improvement in NDCG@1.Table 3 reports test NDCG and Recall; its final row gives relative improvement over the second best.Source: Table 3 · p. 7, §4.3 · p. 8
  • SRNS converges faster and more stably than GAN-based RNS-AS and AdvIR in validation NDCG versus wall-clock time.Training starts from the same pretrained model for a fair efficiency comparison.Source: §4.3 · p. 8
  • Variance-based SRNS remains stable as memory size S1 changes, while difficulty-only sampling degrades sharply at S1=32 or 64.Random sampling from memory is less effective; Ecom may not need variance-based sampling for best NDCG@1, and αt lets SRNS adapt.Source: §4.3 · p. 8
  • SRNS shows similar performance improvement over Uniform with both GMF and MLP scoring functions.The experiments use ML-1m and Ecom; the authors leave GNN-based scoring functions for future study.Source: §4.3 · p. 8

5 Conclusion

SRNS uses a simplified memory-based sampler to efficiently select high-quality true negatives, and the authors identify theoretical convergence guarantees as future work. The appendices contrast this approach with PU/noisy-label learning and negative sampling in other domains.

5 Conclusion

  • SRNS is presented as efficiently sampling high-quality true negatives, while a theoretical convergence guarantee remains future work.The authors propose learning from importance-sampling methods to address that issue.Source: §5 · p. 9

A.1 General Machine Learning Approaches

  • PU learning faces difficult class-prior estimation and inefficient whole-unlabeled-data optimization; noisy-label methods may favor ineffective easy samples or require costly instance weighting.Source: §A.1 · p. 13

A.2 Specific Negative Sampling Approaches

  • SRNS uses memory for promising large-score candidates and emphasizes high-variance samples, addressing false-negative risk in implicit CF sampling.Prior approaches in other domains use simple models for negative-sampling distributions, but the cited review says they do not address false negatives.Source: §A.2 · pp. 13–14

B Implementation Details

The implementation details specify the computing environment, comparison baselines, and the MLP-based scoring function. The baselines range from uniform sampling to adversarial samplers and a non-sampling approach.

B.1 Running Environment

  • Experiments use one Linux server with an AMD Ryzen Threadripper 2990WX, 128 GB RAM, and four NVIDIA GeForce RTX 2080TI GPUs.SRNS is implemented in TensorFlow 1.14 and Python 3.7.Source: §B.1 · p. 14

B.2 Baselines

  • Comparisons include Uniform, popularity-based NNCF, hard-sample AOBPR, adversarial IRGAN/RNS-AS/AdvIR, and weighted non-sampling ENMF.Source: §B.2 · p. 14

B.3 Detail of MLP based r

  • The MLP scoring function concatenates user and item embeddings, passes them through hidden layers, and outputs a prediction score.The hidden-layer weights and biases are learnable parameters.Source: §B.3 · p. 15

B.4 Hyper-parameter Tuning

Hyperparameter tuning separates sampling, scoring-function, and optimization settings. Synthetic and real-data experiments use staged searches, and the comparison baselines are tuned against validation performance.

B.4 Hyper-parameter Tuning

  • SRNS hyperparameters cover sampling, scoring-function, and optimization settings, including memory sizes, temperature, variance weight, warm-start epochs, embedding dimension, learning rate, and regularization.Source: §B.4 · p. 15
  • For synthetic experiments, the authors tune non-sampling settings with Uniform first, then search sampling parameters under different noise settings; Table 4 reports the exploration.They use separate train/test splits for tuning and evaluation, and repeat each experiment five times.Source: §B.4 · p. 15, Table 4 · p. 15
  • For real data, tuning uses validation NDCG@1, first selecting non-sampling parameters and then sampling parameters; MLP reuses GMF’s sampling settings.Other baselines are tuned using validation NDCG@1, and GAN-based methods are initialized from a Uniform-pretrained model.Source: §B.4 · pp. 15–16, Table 5 · p. 16, Table 6 · p. 16

B.5 Evaluation Metrics

The evaluation reports Recall and NDCG at short ranking cutoffs, with fixed-length ranked lists for real-data experiments. The variance computation uses recent prediction history and prunes the item space for large datasets.

B.5 Evaluation Metrics

  • Recall measures whether the ground-truth item appears in the ranked list, while NDCG accounts for the position of a hit.Real-data evaluation ranks lists of length 100 and reports cutoffs k in {1, 3}, reflecting early-list browsing and avoiding an overly easy task.Source: §B.5 · pp. 16–17

B.6 Variance Computation

  • Candidate prediction variance is computed from prior iterations’ predictions, using the latest five epochs without extra forward or backward passes.Source: §B.6 · p. 17
  • For large datasets, the memory update prunes the item space by sampling candidates from var_set_u, which is larger than memory but much smaller than the item set.The reported var_set_u sizes are 3000 for ML-1m and 600 for Pinterest and Ecom.Source: §B.6 · p. 17

C.1 Dataset Description

The experiments use five datasets and examine how negative-instance scores and their variance distinguish hard negatives from false negatives.

C.1 Dataset Description

  • Five evaluation datasets are built from four raw datasets: ML-100k, ML-1m, Pinterest, Ecom, and Ecom-toy.ML ratings are converted to implicit feedback; Ecom-toy retains the top 1,000 users and 2,000 items from Ecom.Source: §C.1 · p. 17

C.2 Details of Figure 1

  • On ML-100k, hard negatives are formed by selecting the highest-scoring item from D sampled candidates, with D controlling difficulty.Uniform negatives correspond to D = 1; false negatives are identified by flipping ground-truth test labels.Source: §C.2 · p. 18
  • False negatives have score distributions similar to positive training instances and lower normalized score variance, while hard negatives generally have large positive-label probabilities.The analysis compares score distributions across five timestamps, uses p50 medians, and measures normalized variance as standard deviation divided by mean.Source: §C.2 · p. 18
  • The study measures negative-instance score distributions with a CCDF and compares false-negative label error ratios across hard-negative sampling strategies.Label error ratio is the fraction of selected negatives that are false negatives.Source: §C.2 · p. 18

C.3 Synthetic Noise Experiments

Synthetic-noise experiments vary false-negative contamination in a candidate memory and examine SRNS performance and warm-start settings.

C.3 Synthetic Noise Experiments

  • Noise is injected by placing one false negative in each user's memory and varying the false-negative-set size; memory size S1 is fixed at 20.σ = 0 denotes the ideal case without influence from the injected set.Source: §C.3 · pp. 18–19
  • Even in the ideal no-explicit-noise case, SRNS largely outperforms on Ecom-toy because the false-negative set cannot cover all false negatives in unlabeled data.The ideal case is defined as memory unaffected by the injected false-negative set.Source: §C.3 · p. 19
  • Warm-starting αt performs better than a fixed value, as it better leverages prediction variance after false negatives become stable.Figure 5 plots test NDCG against epochs on two datasets and highlights standard deviation as shading.Source: Figure 5 · p. 18, §C.3 · p. 19
  • The warm-start investigations cover ML-100k at σ = 1.0 and Ecom-toy at σ = 0.5.These are the conditions specified for Tables 7 and 8, respectively.Source: Table 7 · p. 19, Table 8 · p. 19

C.4 Real Data Experiments

Real-data experiments compare SRNS with Uniform across embedding sizes and report supplementary ranking metrics for memory-size and sampling-strategy settings.

C.4 Real Data Experiments

  • SRNS consistently improves test NDCG over Uniform for embedding sizes F ∈ {8, 16, 32, 64}; F = 16 performs best on Pinterest.The scoring function is GMF; the Pinterest result accords with prior work.Source: §C.4 · p. 19, Figure 6 · p. 20
  • Supplementary NDCG@3 and Recall@3 findings across three datasets and memory sizes S1 are similar to the reported NDCG@1 findings.Figure 7 compares different sampling strategies.Source: §C.4 · p. 19, Figure 7 · p. 20
Loading 2009.03376v1…