Collaborative Filtering with Information-Rich and Information-Sparse Entities

In this paper, we consider a popular model for collabora-tive filtering in recommender systems where some users of a website rate some items, such as movies, and the goal is to recover the ratings of some or all of the unrated items of each user. In particular, we consider both the clustering model, where only users (or items) are clustered, and the co-clustering model, where both users and items are clus-tered, and further, we assume that some users rate many items (information-rich users) and some users rate only a few items (information-sparse users). When users (or items) are clustered, our algorithm can recover the rating matrix with ω(MK logM) noisy entries while MK entries are nec-essary, where K is the number of clusters and M is the number of items. In the case of co-clustering, we prove that K2 entries are necessary for recovering the rating matrix, and our algorithm achieves this lower bound within a loga-rithmic factor when K is sufficiently large. We compare our algorithms with a well-known algorithms called alternating minimization (AM), and a similarity score-based algorithm known as the popularity-among-friends (PAF) algorithm by applying all three to the MovieLens and Netflix data sets. Our co-clustering algorithm and AM have similar overall er-ror rates when recovering the rating matrix, both of which are lower than the error rate under PAF. But more impor-tantly, the error rate of our co-clustering algorithm is signif-icantly lower than AM and PAF in the scenarios of interest in recommender systems: when recommending a few items to each user or when recommending items to users who only rated a few items (these users are the majority of the total user population). The performance difference increases even more when noise is added to the datasets. 1