On Sampling Collaborative Filtering Datasets

Noveen Sachdeva, Carole-Jean Wu, Julian J. McAuley

TL;DR

Training recommendation systems on massive datasets is slow and environmentally costly, yet common "ad-hoc" sampling methods often distort which algorithms actually perform best. This paper introduces SVP-CF, a sampling strategy that prioritizes "hard" examples to preserve model rankings, and Data-genie, a meta-learning "oracle" that predicts the best sampling scheme for any given dataset, enabling a 5.8x training speedup while maintaining evaluation integrity.

What Problem Does This Paper Address?

In the world of Collaborative Filtering (CF), more data usually means better recommendations, but it also means longer training times and a massive carbon footprint. To iterate quickly, researchers and engineers often sub-sample their data.

However, the authors point out a major pitfall: sampling is rarely neutral. Common methods—like randomly removing interactions or only keeping "power users" (head-sampling)—can fundamentally change the relative ranking of different algorithms. An algorithm that looks like the winner on a 10% sample might actually be mediocre on the full dataset. The challenge is finding a way to discard data such that the relative performance of models remains consistent between the small sample and the full-scale production data.

Methods

The authors tackle this from two angles: a new sampling algorithm and a selection tool.

  1. SVP-CF (Selection-Via-Proxy for CF): Inspired by "Selection-via-Proxy" in computer vision, this method uses a computationally cheap "proxy" model (like simple Matrix Factorization) to score the "importance" of data points. It keeps the "toughest" interactions—those the proxy model struggles with—under the assumption that if a model can rank these difficult cases correctly, it will likely maintain its ranking on the easier ones. They also introduce SVP-CF-Prop, which uses propensity scoring to correct for the "missing-not-at-random" (MNAR) bias inherent in user-item grids.
  2. Data-genie: This is a meta-model (an "oracle") designed to answer: "Which sampling strategy is best for this specific dataset?" It represents a dataset using either handcrafted features (like eigenvalue distributions and graph connectivity) or unsupervised Graph Convolutional Network (GCN) embeddings. It then uses a regression or ranking model to predict which of 16 different sampling strategies will best preserve the original algorithm rankings for that specific data.

Datasets

The study uses six diverse public interaction datasets to ensure their findings aren't specific to one niche:

  • Amazon Reviews: (Magazine, Luxury, and Video Games categories)
  • MovieLens-100k: A classic benchmark for movie recommendations.
  • BeerAdvocate: User-item ratings for various beers.
  • Goodreads Comics: Interaction data from a large book-sharing site.

These datasets cover three feedback scenarios: explicit (ratings), implicit (clicks/purchases), and sequential (ordered interactions).

Key Insights and Ideas

  • The "Head" is a Trap: Strategies that discard the "tail" (like Head-User sampling, which keeps only active users) are consistently the worst at preserving algorithm rankings. This is a warning to practitioners who use dense sub-sampling to make their models run faster.
  • Harder is Better: Sampling the "toughest" portion of a dataset (via SVP-CF) is significantly more effective at maintaining the "ground truth" ranking of algorithms than random sampling.
  • No One-Size-Fits-All: There isn't a single "best" sampler for every dataset. The effectiveness of a sampling strategy depends heavily on the dataset's sparsity and dynamics, which justifies the need for a tool like Data-genie.
  • Overfitting on Small Samples: The authors found that as you sample more aggressively, simpler models (like PopRec) often "move up" in the rankings, while parameter-heavy models (like SASRec or SVAE) "move down," likely due to overfitting on the reduced data.

Key Results

  • Efficiency: By using Data-genie to pick the optimal sampler, researchers can discard up to 5x more data than standard sampling methods while maintaining the same level of confidence in their benchmarks.
  • Speedup: Using only 10% of the original data (selected via Data-genie), the authors achieved a 5.8x training time speedup while accurately predicting which algorithms would have won on the 100% dataset.
  • Environmental Impact: The authors estimate that a typical weekly development cycle for a large-scale recommender system produces ~20,000 lbs of $CO_2$. Using Data-genie could reduce this to ~3,400 lbs—a reduction greater than the annual carbon footprint of an average human.

Limitations and Future Work

The authors acknowledge that while they tested seven diverse algorithms, the "universe" of recommendation models is much larger. Future work could involve testing on even more massive, industry-scale datasets (like the Criteo Ad dataset) and exploring how these sampling strategies affect fairness and bias. For instance, if we only keep "hard" examples, do we inadvertently sacrifice the performance of the model on specific minority demographic groups? This remains an open and critical question for the field.

Summary updated

Abstract

We study the practical consequences of dataset sampling strategies on the ranking performance of recommendation algorithms. Recommender systems are generally trained and evaluated on samples of larger datasets. Samples are often taken in a naïve or ad-hoc fashion: e.g. by sampling a dataset randomly or by selecting users or items with many interactions. As we demonstrate, commonly-used data sampling schemes can have significant consequences on algorithm performance. Following this observation, this paper makes three main contributions: (1) characterizing the effect of sampling on algorithm performance, in terms of algorithm and dataset characteristics (e.g. sparsity characteristics, sequential dynamics, etc.); (2) designing SVP-CF, which is a data-specific sampling strategy, that aims to preserve the relative performance of models after sampling, and is especially suited to long-tailed interaction data; and (3) developing an oracle, Data-genie, which can suggest the sampling scheme that is most likely to preserve model performance for a given dataset. The main benefit of Data-genie is that it will allow recommender system practitioners to quickly prototype and compare various approaches, while remaining confident that algorithm performance will be preserved, once the algorithm is retrained and deployed on the complete data. Detailed experiments show that using Data-genie, we can discard upto 5× more data than any sampling strategy with the same level of performance
BibTeX
@inproceedings{sachdeva2022sampling,
  author = {Noveen Sachdeva and Carole-Jean Wu and Julian J. McAuley},
  title = {{On Sampling Collaborative Filtering Datasets}},
  booktitle = {WSDM},
  year = {2022},
  doi = {10.1145/3488560.3498439},
}

Loading related content...

Figure