Discrete Matrix Factorization and Extension for Fast Item Recommendation

Binary representation of users and items can dramatically improve efficiency of recommendation and reduce size of recommendation models. However, learning optimal binary codes for them is challenging due to binary constraints, even if squared loss is optimized. In this article, we propose a general framework for discrete matrix factorization based on discrete optimization, which can 1) optimize multiple loss functions; 2) handle both explicit and implicit feedback datasets; and 3) take auxiliary information into account without any hyperparameters. To tackle the challenging discrete optimization problem, we propose block coordinate descent based on semidefinite relaxation of binary quadratic programming. We theoretically show that it is equivalent to discrete coordinate descent when only one coordinate is in each block. We extensively evaluate the proposed algorithms on eight real-world datasets. The results of evaluation show that they outperform the state-of-the-art baselines significantly and that auxiliary information of items improves recommendation performance. For better showing the advantages of binary representation, we further propose a two-stage recommender system, consisting of an item-recalling stage and a subsequent fine-ranking stage. Its extensive evaluation shows hashing can dramatically accelerate item recommendation with little degradation of accuracy.