On Sampling Collaborative Filtering Datasets

To give a representative sample of typical recommendation scenarios, we consider three different user feedback settings. In explicit feedback, each user $u$ gives a numerical rating $r^{u}_{i}$ to each interacted item $i$; the model must predict these ratings for novel (test) user-item interactions. Models from this class are evaluated in terms of the Mean Squared Error (MSE) of the predicted ratings. Another scenario we consider is implicit feedback, where the interactions for each user are only available for positive items (e.g. clicks or purchases), whilst all non-interacted items are considered as negatives. We employ the AUC, Recall@$100$, and nDCG@$10$ metrics to evaluate model performance for implicit feedback algorithms. Finally, we also consider sequential feedback, where each user $u$ interacts with an ordered sequence of items $\mathcal{S}^{u}=(\mathcal{S}^{u}_{1},\mathcal{S}^{u}_{2},\ldots,\mathcal{S}^{u}_{|\mathcal{S}^{u}|})$ such that $\mathcal{S}^{u}_{i}\in\mathcal{I}$ for all $i\in\{1,\ldots,|\mathcal{S}^{u}|\}$. Given $\mathcal{S}=\{\mathcal{S}^{u}~{}|~{}\forall u\in\mathcal{U}\}$, the goal is to identify the next-item for each sequence $\mathcal{S}^{u}$ that each user $u$ is most likely to interact with. We use the same metrics as in implicit feedback settings. Note that following recent warnings against sampled metrics for evaluating recommendation algorithms (Krichene and Rendle, 2020; Cañamares and Castells, 2020), we compute both Recall and nDCG by ranking all items in the dataset. Further specifics about the datasets used, pre-processing, train/test splits, etc. are discussed in-depth in Section 3.5.

Given the diversity of the scenarios discussed above, there are numerous relevant recommendation algorithms. We use the following seven recommendation algorithms, intended to represent the state-of-the-art and standard baselines:

• •

  PopRec: A naïve baseline that simply ranks items according to overall train-set popularity. Note that this method is unaffected by the user for which items are being recommended, and has the same global ranking of all items.

• •

  Bias-only: Another simple baseline that assumes no interactions between users and items. Formally, it learns: (1) a global bias $\alpha$; (2) scalar biases $\beta_{u}$ for each user $u\in\mathcal{U}$; and (3) scalar biases $\beta_{i}$ for each item $i\in\mathcal{I}$. Ultimately, the rating/relevance for user $u$ and item $i$ is modeled as $\hat{r}^{u}_{i}=\alpha+\beta_{u}+\beta_{i}$.

• •

  Matrix Factorization (MF) (Koren et al., 2009): Represents both users and items in a common, low-dimensional latent-space by factorizing the user-item interaction matrix. Formally, the rating/relevance for user $u$ and item $i$ is modeled as $\hat{r}^{u}_{i}=\alpha+\beta_{u}+\beta_{i}+\gamma_{u}\cdot\gamma_{i}$ where $\gamma_{u},\gamma_{i}\in\mathbb{R}^{d}$ are learned latent representations.

• •

  Neural Matrix Factorization (NeuMF) (He et al., 2017): Leverages the representation power of deep neural-networks to capture non-linear correlations between user and item embeddings. Formally, the rating/relevance for user $u$ and item $i$ is modeled as $\hat{r}^{u}_{i}=\alpha+\beta_{u}+\beta_{i}+f(\gamma_{u}~{}||~{}\gamma_{i}~{}||~{}\gamma_{u}\cdot\gamma_{i})$ where $\gamma_{u},\gamma_{i}\in\mathbb{R}^{d}$, ‘——’ represents the concatenation operation, and $f:\mathbb{R}^{3d}\mapsto\mathbb{R}$ represents an arbitrarily complex neural network.

• •

  Variational Auto-Encoders for Collaborative Filtering (MVAE) (Liang et al., 2018): Builds upon the Variational Auto-Encoder (VAE) (Kingma and Welling, 2014) framework to learn a low-dimensional representation of a user’s consumption history. More specifically, MVAE encodes each user’s bag-of-words consumption history using a VAE and further decodes the latent representation to obtain the completed user preference over all items.

• •

  Sequential Variational Auto-Encoders for Collaborative Filtering (SVAE) (Sachdeva et al., 2019): A sequential algorithm that combines the temporal modeling capabilities of a GRU (Chung et al., 2014) along with the representation power of VAEs. Unlike MVAE, SVAE uses a GRU to encode the user’s consumption sequence followed by a multinomial VAE at each time-step to model the likelihood of the next item.

• •

  Self-attentive Sequential Recommendation (SASRec) (Kang and McAuley, 2018): Another sequential algorithm that relies on the sequence modeling capabilities of self-attentive neural networks (Vaswani et al., 2017) to predict the occurance of the next item in a user’s consumption sequence. To be precise, given a user $u$ and their time-ordered consumption history $\mathcal{S}^{u}=(\mathcal{S}^{u}_{1},\mathcal{S}^{u}_{2},\ldots,\mathcal{S}^{u}_{|\mathcal{S}^{u}|})$, SASRec first applies self-attention on $\mathcal{S}^{u}$ followed by a series of non-linear feed-forward layers to finally obtain the next item likelihood.

We also list models and metrics for each of the three different CF-scenarios in Table 1. Since bias-only, MF, and NeuMF can be trained for all three CF-scenarios, we optimize them using the regularized least-squares regression loss for explicit feedback, and the pairwise-ranking (BPR (Rendle et al., 2009)) loss for implicit/sequential feedback. Note however that the aforementioned algorithms are only intended to be a representative sample of a wide pool of recommendation algorithms, and in our pursuit to benchmark recommender systems faster, we are primarily concerned with the ranking of different algorithms on the full dataset vs. a smaller sub-sample.

Given a user-item CF dataset $\mathcal{D}$, we aim to create a $p\%$ subset $\mathcal{D}^{s,p}$ according to some sampling strategy $s$. In this paper, to be comprehensive, we consider a sample of eight popular sampling strategies, which can be grouped into the following three categories:

Selection-Via-Proxy (SVP) (Coleman et al., 2020) is a leading coreset mining technique for classification datasets like CIFAR10 (Krizhevsky, 2009) and ImageNet (Deng et al., 2009). The main idea proposed is simple and effective, and proceeds by training a relatively inexpensive base-model as a proxy to define the “importance” of a data-point. However, applying SVP to CF-data can be highly non-trivial because of the following impediments:

• •

  Data heterogeneity: Unlike classification data over some input space $\mathcal{X}$ and label-space $\mathcal{Y}$, CF-data consists of numerous four-tuples $\{u,i,r^{u}_{i},t^{u}_{i}\}$. Such multimodal data adds many different dimensions to sample data from, making it increasingly complex to define meaningful samplers.

• •

  Defining the importance of a data point: Unlike classification, where we can measure the performance of a classifier by its empirical risk on held-out data, for recommendation, there are a variety of different scenarios (Section 3.1) along with a wide list of relevant evaluation metrics. Hence, it becomes challenging to adapt importance-tagging techniques like greedy k-centers (Sener and Savarese, 2018), forgetting-events (Toneva et al., 2019), etc. for recommendation tasks.

• •

  Missing data: CF-data is well-known for (1) its sparsity; (2) skewed and long-tail user/item distributions; and (3) missing-not-at-random (MNAR) properties of the user-item interaction matrix. This results in additional problems as we are now sampling data from skewed, MNAR data, especially using proxy-models trained on the same skewed data. Such sampling in the worst-case might even lead to exacerbating existing biases in the data or even aberrant data samples.

To address these fundamental limitations in applying the SVP philosophy to CF-data, we propose SVP-CF to sample representative subsets from large user-item interaction data. SVP-CF is also specifically devised for our objective of benchmarking different recommendation algorithms, as it relies on the crucial assumption that the “easiest” part of a dataset will generally be easy for all algorithms. Under this assumption, even after removing such data we are still likely to retain the overall algorithms’ ranking.

Because of the inherent data heterogeneity in user-item interaction data, we can sub-sample in a variety of different ways. We design SVP-CF to be versatile in this aspect as it can be applied to sample users, items, interactions, or combinations of them, by marginally adjusting the definition of importance of each data-point. In this paper, we limit the discussion to only sampling users and interactions (separately), but extending SVP-CF for sampling across other data modalities should be relatively straightforward.

Irrespective of whether to sample users or interactions, SVP-CF proceeds by training an inexpensive proxy model $\mathcal{P}$ on the full, original data $\mathcal{D}$ and modifies the forgetting-events approach (Toneva et al., 2019) to retain the points with the highest importance. To be more specific, for explicit feedback, we define the importance of each data-point i.e. $\{u,i,r^{u}_{i},t^{u}_{i}\}$ interaction as $\mathcal{P}$’s average MSE (over epochs) of the specific interaction if we’re sampling interactions or $\mathcal{P}$’s average MSE of $u$ (over epochs) if we’re sampling users. Whereas, for implicit and sequential feedback, we use $\mathcal{P}$’s average inverse-AUC while computing the importance of each data-point. For the sake of completeness, we experiment with both Bias-only and MF as two different kinds of proxy-models for SVP-CF. Since both models can be trained for all three CF-scenarios (Table 1), we can directly use them to tag the importance for each CF-scenario.

Ultimately, to handle the MNAR and long-tail problems, we also propose SVP-CF-Prop which employs user and item propensities to correct the distribution mismatch while estimating the importance of each datapoint. More specifically, let $p_{u,i}=P(r^{u}_{i}=1~{}|~{}\ThisStyle{\ensurestackMath{\stackengine{0pt}{\hbox{$\SavedStyle r$}}{\kern 1.36664pt\smash{\SavedStyle*}}{O}{c}{F}{T}{S}}}^{u}_{i}=1)$ denote the probability of user $u$ and item $i$’s interaction actually being observed (propensity), $E$ be the total number of epochs that $\mathcal{P}$ was trained for, $\mathcal{P}_{e}$ denote the proxy model after the $e^{\mathit{th}}$ epoch, $\mathcal{I}_{u}^{+}\coloneqq\{j~{}|~{}r^{u}_{j}>0\}$ be the set of positive interactions for $u$, and $\mathcal{I}_{u}^{-}\coloneqq\{j~{}|~{}r^{u}_{j}=0\}$ be the set of negative interactions for $u$; then, the importance function for SVP-CF-Prop, $\mathcal{I}_{p}$ is defined as follows:

To quantify the performance of a sampling strategy $s$ on a dataset $\mathcal{D}$, we start by creating various $p\%$ subsets of $\mathcal{D}$ according to $s$ and call them $\mathcal{D}^{s,p}$. Next, we train and evaluate all the relevant recommendation algorithms on both $\mathcal{D}$ and $\mathcal{D}^{s,p}$. Let the ranking of all algorithms according to CF-scenario $f$ and metric $m$ trained on $\mathcal{D}$ and $\mathcal{D}^{s,p}$ be $\mathcal{R}_{f,m}$ and $\mathcal{R}^{s,p}_{f,m}$ respectively, then the performance measure $\Psi(\mathcal{D},s)$ is defined as the average correlation between $\mathcal{R}_{f,m}$ and $\mathcal{R}^{s,p}_{f,m}$ measured through Kendall’s Tau over all possible CF-scenarios, metrics, and sampling percents:

Where $\lambda$ is an appropriate normalizing constant for computing the average, sampling percent $p\in\{80,60,40,20,10,1\}$, CF-scenario $f$, metric $m$ and their pertinence towards each other can all be found in Table 1. $\Psi$ has the same range as Kendall’s Tau i.e. $[-1,1]$ and a higher $\Psi$ indicates strong agreement between the algorithm ranking on the full and sub-sampled datasets, whereas a large negative $\Psi$ implies that the algorithm order was effectively reversed.

Given a dataset $\mathcal{D}$, we aim to gauge how a new sampling strategy will perform in retaining the performance of different recommendation algorithms. Having already experimented with sixteen different sampling strategies on six datasets (Section 3.5), we take a frequentist approach in predicting the performance of any sampling scheme. To be precise, to predict the performance of sampling scheme $s$ on dataset $\mathcal{D}$, we start by creating $\mathcal{D}$’s subset according to $s$ and call it $\mathcal{D}^{s}$. We then represent $\mathcal{D}$ and $\mathcal{D}^{s}$ in a low-dimensional latent space, followed by a powerful regression model to directly estimate the performance of $s$ on $\mathcal{D}$.

We experiment with the following techniques of embedding a user-item interaction dataset into lower dimensions:

Having discussed different representation functions $\mathcal{E}:\mathcal{D}\mapsto\mathbb{R}^{d}$ to embed a CF-dataset in Section 4.2, we now discuss Data-genie’s training framework agnostic to the actual details about $\mathcal{E}$.