Simple and effective neural-free soft-cluster embeddings for item cold-start recommendations

Personalized recommender systems assist users in exploring large collections of items efficiently to deal with the problem of information overload by filtering the items into small selections tailored to an individual’s personal preference. This is achieved by inferring the users’ intrinsic preferences for different items. In typical use cases, items can be simple tweet messages, food recipes, electronic gadgets or vehicles. Two popular approaches for recommendation are: (i) content based and (ii) collaborative. Content-based systems recommend items which are similar in content to the ones a user favoured in the past whereas collaborative systems recommend items that users with similar tastes favoured in the past. It is well established in research and practice that collaborative systems tend to outperform content based systems (Adomavicius and Tuzhilin 2005; Saveski and Mantrach 2014). Collaborative algorithms make use of past or observed preference information among collaborating entities (users and items) to recommend top-N items for a user. The preference information among collaborating entities are often represented using a user-item preference or rating matrix where each entry of the matrix stands for a rating score given by a user for an item. The rating information can be due to either explicit or implicit feedback; in explicit feedback settings, users assign a preference score that quantifies the relative degree of favouritism of a user for the item and is often represented as an ordinal number. In implicit feedback settings, preference information is inferred from the implicit user-item interaction like watching a show can be inferred as a positive feedback whereas skipping it is inferred as a negative feedback (Hu et al. 2008). We limit our exposition to the explicit feedback settings as it is very popular with many real world problems. For example, in the Netflix Challenge, movies were rated in the ordinal scale 1, 2, 3, 4, 5, one denoting the least favoured item and five denoting the most favoured.

The collaborative methods for recommendation can be loosely classified under three schemes: (i) user based, (ii) item based and (iii) latent factor based. Setting aside the relative merits and demerits of these three schemes, it is argued that all these approaches work better than content-based systems (Adomavicius and Tuzhilin 2005; Saveski and Mantrach 2014), but it suffers from the cold-start problem. The user and item collaborative algorithms work only in warm-start settings i.e., when past rating data for users and items are available. On the other hand, latent factor models rely on matrix factorization schemes. In the case of matrix factorization based algorithms, user and item features can be extracted only for those users and items for which some rating values are observed. A major challenge in collaborative recommendation is: how to provide top-N recommendations when rating data is completely missing for an item or a user. In the recommendation literature this scenario is termed as cold-start recommendation. The cold-start problem can be either due to a cold-start item i.e. an item is not yet rated by any user (item cold-start problem) or due to a cold-start user i.e. a user did not rate any item (user cold-start problem) or both. In this work, we concentrate on the item cold-start problem, which naturally arises when a new item is added to the items catalogue. Formally, the problem can be defined as: Given a user-item rating matrix containing cold-start items, make a personalized top-N recommendation of items which contains relevant (favoured) cold-start items also, if any.

We propose an efficient two-stage algorithm¹ for item cold-start recommendation within the collaborative matrix factorization framework. Our algorithm starts by extracting vector embeddings for the cold and warm items assuming that the items can be soft-clustered in the space spanned by the enriched side-information. In the second step, the extracted soft-cluster embeddings of the warm items are used to estimate latent user embeddings by approximating a low rank factor model on the observed rating values. Our idea for cold-start recommendation is based on the assumption that an item lying closer to the relevant items cluster is favoured compared to an observed irrelevant item. The intuition behind our algorithm is graphically depicted in Fig. 1.

Consider two users \(u_1\) and \(u_2\) and a set of n items. The user \(u_1\) rated \((n-1)\) items \(\{i_1 \ldots i_{n-1} \}\) whereas user \(u_2\) rated \(n-2\) items \(\{i_1 \ldots i_{n-2} \}\). The users have shown identical tastes i.e. the rating profiles for the \((n-2)\) items \(\{i_1 \ldots i_{n-2} \}\) for both users are exactly the same. Both the users favoured the item sets \(\{i_1 \ldots i_{k-1} \}\) and \(\{i_m \ldots i_{n-2} \}\), but disfavoured the items set \(\{i_k \ldots i_{m-1}\}\). The item \(i_n\) is unobserved (represented using) for both the users whereas the item \(i_{n-1}\) is disfavoured by \(u_1\) but unobserved for \(u_2\). This information is represented in Table: (a) of Fig. 1. Table: (a) corresponds exactly to the rating matrix associated with the data. The items \(\{i_1 \ldots i_n \}\) are associated with at most two latent factors \(f_1\) and \(f_2\). In the simplest use case, if we assume that the items \(i_1 \ldots i_n\) are movies and each movie can be associated with at most two genres, \(f_1\) and \(f_2\) represent the genres associated with the movies. In such cases, each movie can be represented as a real vector of genre association values. For example, if the movie titled \(\mathbf {a}\) has genre association values 0.4 and 0.8, it can be represented as the vector \(\begin{bmatrix} 0.4 \\ 0.8 \end{bmatrix}\).

In the example given in Fig. 1, the items \(\{i_1 \ldots i_{k-1} \}\) and \(\{i_k \ldots i_{m-1} \}\) are supported² by the latent factors \(f_2\) and \(f_1\) respectively. The items \(\{i_m \ldots i_n \}\) are supported by both latent factors \(f_1\) and \(f_2\). This information is shown in the Table: (b) of Fig. 1. Table: (b) corresponds exactly to the side-information matrix associated with the data. It turns out that the preferences of \(u_1\) and \(u_2\) are fully defined by the latent factors \(f_1\) and \(f_2\) in the sense that both users disfavor items with support only by \(f_1\) and prefer items with support only by \(f_2\). The items with support by both \(f_1\) and \(f_2\) have mixed preferences. This is represented using the scatter plot in Fig. 1.³ Items with support only by \(f_1\) i.e. the items for which \(f_1 = 1 ~\text {and}~ f_2 = 0\) in the item side-information matrix are plotted around the line labelled \(f_1\) and the items with support only by \(f_2\) i.e. the items for which \(f_1 = 0 ~\text {and}~ f_2 = 1\) in the item side-information matrix are plotted around the line labelled \(f_2\). The cluster of points at the top right corner represents the items with support by both \(f_1\) and \(f_2\). Items relevant to both users i.e. items with high preference scores are colored in blue and irrelevant items are colored in gray.

Given the rating and side-information matrix, the task here is to recommend an unrated item to the user \(u_2\). The possible candidate items are \(i_{n-1}\; \text {and}\; i_n\). Since the item \(i_n\) is not observed by either \(u_1\) or \(u_2\), it is a cold item whereas \(i_{n-1}\) is an irrelevant item for \(u_1\) but an unobserved warm item for \(u_2\). In Fig. 1, and represent the cold and warm unobserved items respectively. Our idea is to rank the cold item ( ), placed nearer to the cluster of relevant items (blue point cloud), ahead of the relatively far placed irrelevant warm item ( ) when recommending for user \(u_2\). To do so, we first extract the cluster association values from the enriched side-information matrix and use it to fit user feature vectors using rating information. Since the cold item has greater association towards the latent factor \(f_2\) or smaller association towards the latent factor \(f_1\), the soft-cluster embeddings for the cold item will reflect it. The rating scores obtained by our algorithm for the cold and warm items are 2.35 and 1.48 respectively.

We advise the readers to keep in mind that similar to item cold-start recommendation algorithms proposed by Vartak et al. (2017) and Saveski and Mantrach (2014), our proposed algorithm can handle item or user cold-start problem only; it cannot handle both the item and user cold-start problems. In addition, we also need the side-information matrix to contain positive correlations between different side-information categories to obtain significant performance improvement over other algorithms (see Sect. 4). We reckon that this might be the case with other content + collaborative based algorithms also. The remainder of this paper is organized as follows: after a brief overview of the state-of-the-art personalized item cold-start recommendation algorithms in Sect. 2, we describe our framework and algorithm in Sect. 3. At the end of Sect. 3, we propose an extension of the algorithm to handle user cold-start problems. In Sect. 4, we report the results of our experimental study on three benchmark datasets against strong non-deep learning based baselines. Though recent studies (Ludewig and Jannach 2018; Lin 2019; Dacrema et al. 2019; Ludewig et al. 2019) showed that deep learning based algorithms perform relatively poorly compared to non-deep learning based baselines in common information retrieval tasks, there is a growing interest within the community to adapt deep learning based models. In this regard, we compare our algorithm against state-of-the-art deep graph embedding models for cold-start recommendations. We conclude the paper in Sect. 5 after describing the results of a qualitative study.

A large class of cold-start recommendation algorithms are based on the collective matrix factorization idea proposed by Singh and Gordon (2008). Collective matrix factorization based algorithms assume the existence of a shared subspace between different modalities of the data. The shared item subspace can be approximated using the available side-information and rating data. Typical collective matrix factorization based algorithms optimize a non-convex joint objective function, defined in terms of all the available data modalities, using cyclic block coordinate descent otherwise known as alternating minimization. Saveski and Mantrach (2014) proposed an algorithm based on the collective matrix factorization technique that uses the item metadata and the rating data, and exploits the local geometric structure of the metadata space. The proposed algorithm, called locally collective matrix factorization, decomposes the side-information and the collaborative matrices in a common low-dimensional space while preserving the local geometrical structure of the data. This is done by adding a manifold regularizer (Belkin et al. 2006) to the collective matrix factorization objective function. Very recently, Gouvert et al. (2018) also used the collective matrix factorization ideas to solve the cold-start recommendation in the music recommendation setting. The proposed algorithm learns the feature vectors for the warm and cold songs by jointly optimizing a loss function defined in terms of the listening count data of the songs and the associated tags information. Typical to the collective matrix factorization models, the authors assume the existence of a shared subspace between song listen count and tags.

Factorization machines (Rendle 2010, 2012) based techniques are also very popular for cold-start recommendations. Factorization machines based algorithms also make use of the item side-information to predict the relevance scores for cold items. In specific application settings with abundant item metadata, such as question-answering, many cold-start recommendation algorithms based on the idea of using factorization machines are proposed in the past (Sun et al. 2018; Piazza et al. 2017). In factorization machines, each user-item interaction is represented as a unique feature-label pair where the feature is constructed by using the user and item side-information data. The model parameters are learned using standard supervised learning techniques. The higher order correlations between different available side-information can also be part of the feature vector. Factorization machine based models are particularly suitable in sparse settings when the categorical side-information data is represented using one-hot encoding. Since factorization machine objective function does not make use of the user-user correlations explicitly, algorithms based on factorization machines might lose some collaborative information between different users. Though this problem can be alleviated by encoding observed user-user correlation as part of the feature vector, it might result in an exponential increase in the dimensionality of the feature space.

Gantner et al. (2010) proposed a two-stage algorithm, similar to ours, by estimating attribute-to-feature mappings from the rating matrix using supervised learning techniques. In the first stage, the proposed method learns user and item features by fitting a low rank latent factor model. The extracted user features are used with item metadata to learn item weight vectors for different metadata categories for both cold and warm items in the second stage. In addition to higher computational costs, the above algorithm may result in severe overfitting as the observed rating values are shared in the learning phases of both stages of the algorithm. The proposed algorithm uses the observed rating matrix to learn the user and item features in the first phase and the same observed rating matrix is used to learn the weight matrix in the second phase of the algorithm. Our proposed method learns item embeddings using cluster assumption in an unsupervised manner without making use of the observed rating values with lesser computational cost.

Park and Chu (2009) extended the pairwise preference ranking model to accommodate cold-start items. In the proposed method, the observed rating matrix is assumed to be a weighted cross-product between user and item metadata vectors. The rating scores are estimated by fitting a pairwise loss function in the regression framework. Zhang et al. (2014) extended the collaborative latent factor model to include bias terms for the metadata categories associated with the items. The final recommendation is produced by co-training two regressors learned from the observed user-item rating values and corresponding metadata data.

Barjasteh et al. (2015) proposed an algorithm based on decoupling the rating estimation and item feature vector estimation into two separate steps. The algorithm extracts a representative item subspace from the item similarity matrix after estimating the entries of a fully recoverable submatrix of the original observed rating matrix using standard matrix completion techniques. The full rating matrix is estimated using the extracted representative subspace and the information contained in the completed submatrix. Chou et al. (2016) proposed a cold-start next-song recommendation algorithm in sequential data settings. The proposed algorithm predicts the next-song using tensor factorization that exploits content features extracted from music audio. Recently, Sedhain et al. (2017) proposed a Low-Rank Linear model for user cold-start recommendation settings. In the proposed algorithm, the observed rating values are used to estimate a low-dimensional weight matrix from a subset of parametrized low-rank matrices. This is a generalization of the pure content based cold-start recommendation algorithm and the proposed algorithm is equivalent to the pure content based algorithm when the weight matrix is replaced with the one-hot encoded side-information matrix of the items. This approach can also be considered as a special case of the factorization machines (Rendle 2010) with only a single order of interactions used for feature engineering.

Clustering based approaches are also used for collaborative filtering in the past (Ungar and Foster 1998; Salah et al. 2016; Verstrepen et al. 2017). The majority of the clustering algorithms work by co-clustering the users and items based on the rating values. Recently, Vlachos et al. (2019) proposed a co-clustering based algorithm for cold-start recommendation algorithm in the presence of positive only ratings. As in the case of our algorithm, the proposed algorithm makes use of any side-information data, but assumes that all the items are either preferred or the preference status is not known. The side-information data is incorporated into the co-clustering objective to form a joint optimization objective, and the model parameters are estimated using alternating minimization techniques typical to the collective matrix factorization based approaches.

Recently, many item representation learning models have been proposed. Kula (2015) proposed learning item embeddings by aggregating the embeddings for each category of the side-information. These embeddings are extracted by fitting a low rank matrix model on the rating data. With the advent of deep representation learning methods, many deep-neural network based architectures have been proposed to solve the item cold-start problem. Vasile et al. (2016) proposed learning item embeddings from the text data associated with the product co-purchase details and item side-information using deep neural networks. Wei et al. (2016) proposed a 2-stage approach where the item embeddings for both cold and warm items are learned using deep neural networks, from the side-information in the first stage and are used in the second stage where SVD based matrix factorization techniques are used to estimate the unobserved rating values. This work considers recommendation as a rating prediction task whereas we pose recommendation as a top-N ranking problem. Similarly, Vartak et al. (2017) proposed a meta-learning item cold-start recommendation algorithm using deep neural networks. The proposed method works in implicit feedback settings and recommendation is considered as a binary classification task. Our proposed method differs from the above methods as our embeddings are soft-cluster embeddings which are not constrained to work only with the textual description of the items. It is generally believed that the subpar performance of the deep learning models for information retrieval tasks as opposed to the language processing and vision tasks is due to the sparsity in the input features (Sun et al. 2018; McMahan et al. 2013). Moreover, in light of recent studies on the efficacy of deep learning methods for recommendation tasks, one should be sceptical about the use of these methods (Dacrema et al. 2019; Ludewig et al. 2019). In spite of that, deep architecture models are the backbone of many large scale industrial recommender systems like YouTube (Covington et al. 2016). Unlike the settings we study in this paper, the majority of the deep learning models for cold-start recommendation do not consider the extreme cold-start scenario. Recent advances in deep learning models for cold-start recommendation make use of the graph embedding techniques and learn user and item embeddings by injecting higher order connectivity relations between users and items using the Laplacian of the user-item implicit interaction matrix (Zheng et al. 2018; Wang et al. 2019b).

User feedback elicitation based cold-start recommendation algorithms are mostly used in online learning settings and work by eliciting new items or new user preferences by actively querying preference information. A typical workflow in such an approach can be described as: whenever a new item is introduced, the system initiates many trials and at each trial the new item is presented to a seed user for her opinion, thus gradually building a rating profile for the item. Zhou et al. (2011) proposed functional matrix factorization within the active learning framework, employing a decision tree model for selecting the seed users for each new item and the decision tree model was combined with the low-rank matrix factorization to fit a prediction model. Feature vectors for the cold-start items were adaptively built by the seed users’ responses by modeling the cold-start item feature vector as a function of user response. The decision tree outputs were mapped to the item feature space and these item features were used in the subsequent low-rank approximation. The proposed method alternatively learns the best mapping function and item features. Aharon et al. (2015) proposed a smart exploration strategy to identify a set of users for rating the cold-start items in online settings. Similarly, Anava et al. (2015) proposed an algorithm to recruit a set of users to rate the cold-start items with constraints on the number of users to recruit.

We are given a set \({\mathcal {I}}\) of n items and a set \({\mathcal {U}}\) of m users. Each user is assumed to have an inherent personal preference over the set of items \({\mathcal {I}}\) i.e. each item \(i \in {\mathcal {I}}\) might be favoured differently by different users. Users’ personal preferences for the items are represented using a preference score in the form of ordinal rating values, typically in the range \(\{1\cdots 5\}\) with higher values indicating favored items and lower values indicating unfavoured items. We also assume that a user may have the same preference score for different items and the preference relation is rational. The rating values are tabulated as a \(m \times n\) user-item rating matrix \({\mathbf {R}}\) where each entry \({\mathbf {R}}_{ij}\) represents the rating values by the user i for the item j. The unobserved rating values are denoted using zeroes i.e. \({\mathbf {R}}_{ij} = 0\) if user i did not rate item j.

In addition to the above standard collaborative settings assumption, we also assume that some side-information related to the items is available. We refer to any attribute or metadata associated with items other than ratings as side-information. We represent the available side-information associated with the items set \({\mathcal {I}}\) using a \(n \times p\) characteristic matrix called item side-information matrix \({\mathbf {A}}\) where p is the number of available side-information categories. For example, if items are movies, then attributes such as genre, cast, director etc. are referred to as side-information, which can be represented as a one-hot encoded characteristic matrix. The subspace spanned by the rows of the characteristic matrix forms side-information space. In the standard item cold-start scenario, we assume that the item set \({\mathcal {I}}\) is a union of two disjoint sets \({\mathcal {I}}_w\) and \({\mathcal {I}}_c\) i.e. \({\mathcal {I}}= {\mathcal {I}}_w \cup {\mathcal {I}}_c\) and \({\mathcal {I}}_w \cap {\mathcal {I}}_c = \varnothing \), where \({\mathcal {I}}_w\) is the set of warm items and \({\mathcal {I}}_c\) is the set of cold items i.e. items for which no rating values are observed (\({\mathbf {R}}_{ij} = 0\; \forall j\in \{1\ldots n\}\)). In the item cold-start recommendation problem, one is interested in recommending potentially relevant unobserved items to users such that recommendation contains relevant cold-start items from \({\mathcal {I}}_c\) also, if any.

The main purpose of this section is to compare the performance of different state-of-the-art algorithms against the proposed one. Though many recent studies (Yang et al. 2019; Dacrema et al. 2019; Ludewig et al. 2019) demonstrated that deep learning based algorithms perform inferior to content + collaborative algorithms in recommendation tasks, there is a growing interest within the community to adapt deep learning based models. Hence, we carry out two sets of experiments: in the first set of experiments we compare our algorithms against state-of-the-art content + collaborative algorithms and in the second set of experiments we compare the proposed algorithm against recent graph embeddings based deep learning algorithms. In both cases, we evaluate different approaches in a movie cold-start recommendation setting. We also perform qualitative analysis of our results to explain the recommendations provided by the proposed algorithm.

We presented a new method to solve the item cold-start recommendation problem. The algorithm can be applied in any item cold-start recommendation scenario with access to item side-information. Our exhaustive experiments on benchmark datasets showed that the algorithm performs well in terms of popular relevance metrics compared to strong content, content + collaborative and deep learning based baselines. Qualitative analysis of the experimental results explains the recommendation provided by the proposed algorithm.