Inductive Matrix Completion: How to Improve Recommendations for Cold Start Users and Items by Incorporating Their Attributes

Rodrigo Alves

Mar 20, 2023

Matrix completion (MC), the problem of recovering the missing entries of a partially observed matrix, has found use in a wide range of domains. Still, its potentially most successful application is as a collaborative filtering technique for recommender systems (RSs). MC techniques are an accurate and efficient approach for recovering a high number of unobserved entries from a small number of observed data. To recover missing entries of a matrix, it is first necessary to make an assumption on the structure of the ground truth matrix. The most common assumption is that the matrix is of low rank; that is, the matrix can be factorized in a space smaller than the number of users and items.

In recommender systems, we model each user as a row, each item as a column, and each user's rating for an item as an entry in that matrix. However, we typically don't observe all the ratings in the matrix - in fact, we might only have a tiny fraction of them. The low-rank assumption is a way to deal with this sparsity. Essentially, it suggests that there are underlying factors that are shared by groups of users and items - for example, if a bunch of users all rate action movies highly, there might be an underlying "action movie" factor that they all respond to. Similarly, if a bunch of movies all have car chases and explosions, there might be an underlying "action movie" factor that they all share. Therefore, this assumption lets us fill in the missing entries in the matrix more accurately, because we can use the known ratings to infer the underlying factors and then use those factors to make predictions for the missing entries. For the sake of simplicity, we will be using movie recommendations as a running example. Hence the data will consist of user and movie ratings. Depending on the application, MC can deal with type1-type2 pairings, such as user-book, user-product, user-user, product-product, etc.

Despite their pervasiveness, theoretical foundations, high accuracy, and efficiency, traditional matrix completion methods unfortunately fail to address the so-called cold-start problem. One of the most fundamental problems in RSs, the cold-start problem consists of profiling movies or users for whom the system has never observed a single interaction. This is a realistic scenario for commercial recommendation systems, where new users and new movies are introduced regularly. To help you understand this, the figure below shows a typical matrix completion method. However, this method would not be able to handle a scenario where there is no prior information or interactions available for new users or movies.

This issue arises because standard MC methods are user- and movie-agnostic: users' and movies' embeddings are learned only based on interactions and do not account for any additional information. As the data lacks some user-i (resp item-j) interactions, the method can't build the i-th (resp. j-th) vector of the user's (resp items') embeddings. However, it is not uncommon for Recommender Systems to have access to side information about users (e.g., browser the user uses, device type, etc.) and movies (e.g., director, genres, etc.).

To address this issue , one can employ Inductive Matrix Completion (IMC) and recommend movies and users without observed interactions. Unlike traditional matrix completion methods, IMC uses side information matrices to induce the learning process in a collaborative filtering approach. Basically, it learns a proxy combining users and item attributes in a low-rank space.

The figure above demonstrates how inductive matrix completion works. Throughout the learning process, the IMC algorithm uses side information from all users and items that so far have interacted with the system. In our toy example, the technique is aware of the users' browser and device type; for the items, we consider that the RS knows if they belong to the action or comedy and the duration of the movie. Then, the method utilizes the side information to learn the matrix in the middle of the figure that serves as a proxy for the side information of users and items. With that learning, IMC can use this matrix to recommend to users that their browser and device type are known but have yet to interact with the system (highlighted in green). Note that IMC can also be used with more complex side information, such as item figures or textual descriptions. In that case, they must be converted to vector representations (e.g., by convolutional neural autoencoders).

Is Inductive Matrix Completion an Accurate Method?

Well... as in any machine learning model, it will highly depend on the side information quality. It's hard to predict someone's favourite movie genre based on their favourite pizza topping. Here is the same: if the side information is related to the interactions, IMC can produce excellent practical results. We clarify that such methods can also be used in a hybrid approach, where traditional matrix factorization is incorporated together with IMC. For reference, see the link.

There is a lot of rigorous theoretical analysis behind IMC, and recently, I was part of a team of researchers from five different institutions who investigated a specific model of IMC. Our work was approved for oral presentation at the AAAI 2023 conference, which is a very prestigious machine learning conference. You can read our paper if you're interested in the details of our approach. We showed through the proof of generalisation bounds that IMC can give excellent results when the side information we use is strongly related to the interactions we observe. In other words, if we have good side information that tells us about the relationships between users and items, we can use that to make very accurate predictions about missing entries in the matrix. This category of research is crucial for comprehending how AI approaches mathematical function and for providing statistical data on the quality of outcomes produced by machine learning techniques.

IMC is a powerful tool that can help solve the problem of cold-start recommendations, where we have limited information about interactions of new users or items. By using additional side information, IMC can enhance the key performance indicators (KPIs) of recommender systems significantly. IMC is just one of several toolkits offered by Recombee that deliver improved content recommendations in cold-start scenarios. If you found our work interesting and helpful, we would greatly appreciate it if you would cite us in your own research, provide feedback or comments, or get in touch with our research team for more technical details.

References

Ledent, Antoine; Alves, Rodrigo; Lei, Yunwen; Guermeur,Yann;Kloft, Marius. Generalization Bounds for Inductive Matrix Completion in Low-noise Settings. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2023 (To appear)

Ledent, Antoine; Alves, Rodrigo; Kloft, Marius. Orthogonal Inductive Matrix Completion. IEEE Transactions on Neural Networks and Learning Systems, 2021