Addressing the Recommendation Task Through a Different Lens | by Amine Dadoun

Graph-based recommender systems

In recent years, recommender systems have become an integral part of our daily lives. They help us discover new products, services, and information that we may be interested in based on our past behavior and preferences. However, as the amount of available data continues to grow exponentially, traditional recommender systems face several challenges, such as data sparsity, cold-start, and scalability.

To overcome these challenges, researchers and practitioners have turned to knowledge graphs, a type of graph database that organizes data and knowledge in a structured format. Knowledge graph-based recommender systems leverage the relationships between entities and concepts in the graph to provide more accurate and diverse recommendations, while also addressing some of the aforementioned challenges.

In this Medium series, we will explore the world of knowledge graph-based recommender systems and how to approach recommender systems from the angle of graphs. We will dive into the concepts of knowledge graphs and graph databases, explain how to represent data and knowledge as graphs, and explore various algorithms and techniques for building and evaluating knowledge graph-based recommender systems.

Our goal is to provide a comprehensive and practical guide for those interested in leveraging knowledge graphs for their recommender systems, whether you are a researcher, practitioner, or enthusiast. By the end of this series, you will have a solid understanding of the key concepts and techniques in knowledge graph-based recommender systems and how to apply them in real-world scenarios.

This article aims at presenting the recommendation task as a link prediction task in a graph. The objective is to look at recommender systems from a new angle, in order to take advantage of the power of graph-based data representation and benefit from the rise of graph algorithms to improve the performance of recommender systems.

In a social network, sending a recommendation suggestion to Adam to befriend Sophia is equivalent to computing the probability p(Sophia, Adam) of having a new connection between Sophia and Adam.

Recommender systems

A recommender system can be seen as an algorithm to compute the probability that a user (or customer) would like to interact with an item (a product or service). These systems were originally introduced to overcome the problem of information overload that customers face when exposed to a large catalog of products or services. By providing customers with contextualized and personalized recommendations, recommender systems aim at narrowing down the search to a manageable subset of products that are relevant to the customer.

In the terminology of recommender systems, the customers are referred to as users and the products in the catalog are referred to as items. Hence, a recommender system can be seen as a way to compute the probability that a user would like to interact with an item and use this probability to recommend the most relevant subset of items to this user. Depending on the context, an interaction would correspond to the act of searching, buying, visiting, watching, etc.

The above figure is an illustrative example of a bipartite user-item graph G for e-commerce products. The graph contains interactions between users and items (phone, headset, etc.) represented by black arrows. Dash arrows represent recommendations obtained from CF and CB algorithms.

While in CF, the recommendation is based solely on past interaction between the user and the item, in CB, items information are used to build a user profile based on the keywords that characterize users’ favorite items, and then recommend to the users, items that are similar to the ones they like.

In its most simple form, a recommender system is typically built in three consecutive steps: information collection, learning and recommendation. The information collection phase consists in building a weighted graph G = (U,I,E,w), where U, the set of users, and I, the set of items, are the nodes in the graph and E corresponds to the set of edges. These edges represent the past interactions between users and items. There are no edges between the users nor the items, hence the graph is bipartite.

The strength of these past interactions is given by the function w: E → [0, 1]. In the learning phase, a Machine Learning (ML) algorithm is used to train a model W that approximates w in G.

Finally, in the recommendation phase, the trained model is used to predict, for every possible pair (u,i) ∈ (U × I), the strength of the interaction between user u and item i. From these predictions, it is then possible to derive the list of items that could be recommended to the users.

In the remainder of this post, we will present how we can approach the two most used recommender system methods using graphs.

Collaborative Filtering (CF) Recommender Systems

CF algorithms are among the most widely used algorithms in the field of recommender systems [1] and have been applied in industries such as e-commerce or online entertainment to recommend the most relevant products (e.g. movies) to their customers. In the original formulation, a CF algorithm relies only on the interactions present in the graph G without any additional knowledge or information about the items or the users.

The figure below is an illustrative example of the bipartite user-item graph G. The graph contains interactions between users and items (movies) represented by the solid arrows, while the dashed arrow labeled by its strength w₂,₂ represents the recommendation obtained from a CF algorithm. Let us consider the movie m₁ (Titanic) for example. Users u₁ and u₂ both watched this movie. Furthermore, user u₁ also watched the movie m₂ (Romeo+Juliet), thus movie m₂ is recommended to user u₂.

We can divide CF algorithms into two different classes of methods: the first one relies on Matrix Factorization (MF) techniques [2] while the second one, named Neighborhood Methods [1], relies on computing the similarity between users or items.

Over the years, significant progress has been made to improve CF algorithms, for example, in terms of learning speed [3] or accuracy [4]. Nevertheless, despite their proven overall effectiveness and usability, CF algorithms are still limited especially when users interact with a restricted number of items (data sparsity) or when new users or new items frequently enter the system and, consequently, past interactions are not available (the user or item cold start problem).

Content-based Filtering (CB) Recommender Systems

CB filtering algorithm [5] aims at building user preference profiles based not only on historical user-to-item interactions but also on a form of description of these items that is often represented by a set of keywords or properties. Conversely, it is also possible to associate items to user profiles by looking at the description of the users interacting with them.

In the figure above, we present the graph G enriched with item properties required for the use of CB recommender system. Each movie is characterized by a set of properties (here movie genre). In this example, the CB algorithm could recommend “Romeo+Juliet” m₂ or “TOP GUN” m₃ to the user u₂ with different strength. Basically, if the recommendation is based solely on the two keywords represented in the figure, movie m₂ would be recommended in favor of movie m₃.

With CB filtering, even new items without any previously observed interactions will have at least a description that can be used by the system to provide recommendations. Hence, the problem of item cold start is mitigated. Nevertheless, CB filtering methods also have some shortcomings. For example, building and maintaining relevant representations for every item can turn into a heavy feature engineering task. Also, introducing novelty into what is being recommended to a given user is not possible since the system works only by looking at content associated with the user’s past interactions.

One of the alternatives to deal with the above mentioned limitations such as the lack of novelty consists in mixing CB and CF techniques in what is referred to as Hybrid recommender systems in the literature [6]. The shift of predictive models during recent years from using simple linear or logistic regression to models that incorporate deep networks [7] in order to consider many types of data such as categorical data projecting them into embedding spaces and numerical data in one model improved drastically models’ performances. Following this trend, many deep learning-based recommender systems [8, 9] have emerged taking into consideration numerous types of data. However, these models need the data to be pre-processed which can be a heavy task, especially when there are many features

In this first episode of this series of blog posts, we first introduced recommender systems using a definition that makes use of graphs. Then, we presented a set of basic notions and concepts related to the field of recommender systems, illustrating the two most used families of algorithms, as well as their most common models. We have highlighted the advantages and disadvantages of the different algorithms.

Currently, the research trend is increasingly towards hybrid systems that combine the best of collaborative and content-based filtering through the use of graph both in terms of data representation and the use of graph-based algorithms. In the next article of this series, we will introduce the concept of knowledge graphs and how they can be used in recommender systems to provide more accurate and personalized recommendations to users.

Note: All images and figures are self-made.

[1] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th International Conference on World Wide Web, WWW ’01, page 285–295, New York, NY, USA, 2001. Association for Computing Machinery.

[2] Y. Hu, Y. Koren, and C. Volinsky. Collaborative Filtering for Implicit Feedback Datasets. In 8 th IEEE International Conference on Data Mining (ICDM), pages 263–272, 2008

[3] Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. Fast Matrix Factorization for Online Recommendation with Implicit Feedback. In 39th International ACM Conference on Research and Development in Information Retrieval (SIGIR), pages 549–558, 2016.

[4] Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural Collaborative Filtering. In 26th International Conference on World Wide Web (WWW), pages 173–182, 2017.

[5] Henry Lieberman. Letizia: An Agent That Assists Web Browsing. In 14th International Joint Conference on Artificial Intelligence (IJCAI), 1995.

[6] Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang. Deep Reinforcement Learning for Page-Wise Recommendations. In 12th ACM Conference on Recommender Systems (RecSys), pages 95 — -103, Vancouver, British Columbia, Canada, 2018.

[7] Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Comput. Surv., 52(1), February 2019.

[8] Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, Rohan Anil, Zakaria Haque, Lichan Hong, Vihan Jain, Xiaobing Liu, and Hemal Shah. Wide & deep learning for recommender systems. In Proceedings of the 1st Workshop on Deep Learning for Recommender Systems, DLRS 2016, pages 7–10, New York, NY, USA, 2016. ACM.

[9] Amine Dadoun, Raphaël Troncy, Olivier Ratier, and Riccardo Petitti. Location embeddings for next trip recommendation. In Companion Proceedings of The 2019 World Wide Web Conference-(LocWeb’19), WWW ’19, page 896–903, New York, NY, USA, 2019. Association for Computing Machinery.