Improving Collaborative Metric Learning with Efficient Negative Sampling

Viet-Anh Tran, Romain Hennequin, Jimena Royo-Letelier, Manuel MoussallamSIGIR 2019 · DOI · OpenReview

Abstract

Distance metric learning based on triplet loss has been applied with success in a wide range of applications such as face recognition, image retrieval, speaker change detection and recently recommendation with the Collaborative Metric Learning (CML) model. However, as we show in this article, CML requires large batches to work reasonably well because of a too simplistic uniform negative sampling strategy for selecting triplets. Due to memory limitations, this makes it difficult to scale in high-dimensional scenarios. To alleviate this problem, we propose here a 2-stage negative sampling strategy which finds triplets that are highly informative for learning. Our strategy allows CML to work effectively in terms of accuracy and popularity bias, even when the batch size is an order of magnitude smaller than what would be needed with the default uniform sampling. We demonstrate the suitability of the proposed strategy for recommendation and exhibit consistent positive results across various datasets.

Introduction

Collaborative Metric Learning (CML) is a powerful framework for recommendation systems that maps users and items into a shared low-dimensional embedding space. By utilizing a triplet loss, CML aims to minimize the distance between a user and their preferred items (positives) while maximizing the distance to items they have not interacted with (negatives).

A significant bottleneck in CML is the selection of negative samples. Standard implementations rely on uniform sampling, which often selects "easy" negatives—items already far from the user in the embedding space. These samples provide minimal gradient signal, necessitating massive batch sizes (e.g., 4096 or more) to ensure enough "informative" negatives are encountered. This requirement leads to high memory overhead, hindering scalability for high-dimensional content like audio or images.

Proposed Methodology

To address these efficiency and scalability issues, the authors introduce two key components:

  1. Global Orthogonal Regularization (GOR): This technique prevents embedding collapse by encouraging latent vectors to be spread out and nearly orthogonal, maximizing the expressive capacity of the latent space.
  2. 2-Stage Negative Sampling Strategy:
    • Stage 1 (Popularity-based): A candidate pool of size $C$ is selected based on item frequency. Since popular items often dominate recommendations and cluster together, treating them as negatives helps the model learn to distinguish genuine relevance from mere popularity.
  3. Stage 2 (Distance-based): From the candidate pool, final negatives are sampled based on their proximity to the positive item (specifically, those with a high dot product). These represent the most informative "hard" negatives that the model currently struggles to distinguish.

Experimental Setup

The researchers evaluated the proposed strategy across three diverse real-world datasets, summarized below:

Summary of datasets used for evaluation, including user, item, and rating counts.
  • Amazon Movies: User-movie ratings binarized for implicit feedback.
  • Book Crossing: A dataset of book ratings.
  • Echonest: User playcounts for songs from the Million Song Dataset.

Key Results and Insights

The experimental results demonstrate that the 2-stage sampling strategy significantly outperforms standard uniform sampling while requiring far fewer resources.

Experimental results comparing Uniform (Uni), Popularity (Pop), and 2-Stage (2st) sampling strategies across different batch sizes.

Efficiency and Accuracy

The 2-stage strategy (2st) achieves superior performance with a batch size of only 256, outperforming uniform sampling (Uni) even when the latter uses a batch size of 4096. On the Echonest dataset, the 2-stage approach yielded a 52% improvement in MAP and a 33.6% increase in NDCG compared to the best uniform sampling results.

Reducing Popularity Bias

The Mean of Median Rank (MMR) metric highlights the strategy's ability to mitigate popularity bias. Lower MMR values indicate that recommendations are less skewed toward "blockbusters" and more tailored to niche user interests. The 2-stage strategy consistently achieved lower MMR scores than the uniform baseline across all datasets.

Conclusion

By replacing simple uniform sampling with a targeted 2-stage approach, Collaborative Metric Learning can be trained more effectively with significantly smaller batch sizes. This not only improves recommendation accuracy and reduces popularity bias but also paves the way for scaling CML to high-dimensional, content-rich recommendation scenarios.

Summary updated

Abstract

Distance metric learning based on triplet loss has been applied with success in a wide range of applications such as face recognition, image retrieval, speaker change detection and recently recommendation with the CML model. However, as we show in this article, CML requires large batches to work reasonably well because of a too simplistic uniform negative sampling strategy for selecting triplets. Due to memory limitations, this makes it difficult to scale in high-dimensional scenarios. To alleviate this problem, we propose here a 2-stage negative sampling strategy which finds triplets that are highly informative for learning. Our strategy allows CML to work effectively in terms of accuracy and popularity bias, even when the batch size is an order of magnitude smaller than what would be needed with the default uniform sampling. We demonstrate the suitability of the proposed strategy for recommendation and exhibit consistent positive results across various datasets.
BibTeX
@inproceedings{tran2019improving,
  author = {Viet-Anh Tran and Romain Hennequin and Jimena Royo-Letelier and Manuel Moussallam},
  title = {{Improving Collaborative Metric Learning with Efficient Negative Sampling}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2019},
  doi = {10.1145/3331184.3331337},
}
Figure