In its most straightforward form, a recommender system is usually inbuilt three consecutive steps: information collection, learning and advice. The knowledge collection phase consists in constructing a weighted graph G = (U,I,E,w), where U, the set of users, and I, the set of things, are the nodes within the graph and E corresponds to the set of edges. These edges represent the past interactions between users and items. There aren’t any edges between the users nor the items, hence the graph is bipartite.

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

Finally, within the advice phase, the trained model is used to predict, for each possible pair (u,i) ∈ (U × I), the strength of the interaction between user u and item i. From these predictions, it’s then possible to derive the list of things that might be really helpful to the users.

In the rest of this post, we are going to present how we will approach the 2 most used recommender system methods using graphs.

Collaborative Filtering (CF) Recommender Systems

CF algorithms are amongst probably the most widely used algorithms in the sector of recommender systems [1] and have been applied in industries equivalent to e-commerce or online entertainment to recommend probably the most relevant products (e.g. movies) to their customers. In the unique formulation, a CF algorithm relies only on the interactions present within the graph G with none additional knowledge or information in regards to the items or the users.

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

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

Over time, significant progress has been made to enhance CF algorithms, for instance, by way of learning speed [3] or accuracy [4]. Nevertheless, despite their proven overall effectiveness and value, CF algorithms are still limited especially when users interact with a restricted variety of items (data sparsity) or when recent users or recent items continuously enter the system and, consequently, past interactions aren’t available (the user or item cold start problem).

Content-based Filtering (CB) Recommender Systems

CB filtering algorithm [5] goals at constructing user preference profiles based not only on historical user-to-item interactions but in addition on a type of description of this stuff that is commonly represented by a set of keywords or properties. Conversely, additionally it is possible to associate items to user profiles by taking a look at the outline of the users interacting with them.

Within the figure above, we present the graph G enriched with item properties required for the usage of CB recommender system. Each movie is characterised by a set of properties (here movie genre). In this instance, the CB algorithm could recommend “Romeo+Juliet” m₂ or “TOP GUN” m₃ to the user u₂ with different strength. Mainly, if the advice is predicated solely on the 2 keywords represented within the figure, movie m₂ can be really helpful in favor of movie m₃.

With CB filtering, even recent items with none previously observed interactions could have a minimum of an outline that may be utilized by the system to supply recommendations. Hence, the issue of item cold start is mitigated. Nevertheless, CB filtering methods even have some shortcomings. For instance, constructing and maintaining relevant representations for each item can turn right into a heavy feature engineering task. Also, introducing novelty into what’s being really helpful to a given user isn’t possible for the reason that system works only by taking a look at content related to the user’s past interactions.

One in all the alternatives to take care of the above mentioned limitations equivalent to the dearth of novelty consists in mixing CB and CF techniques in what’s known as Hybrid recommender systems within the literature [6]. The shift of predictive models during recent years from using easy linear or logistic regression to models that incorporate deep networks [7] with a purpose to consider many forms of data equivalent to categorical data projecting them into embedding spaces and numerical data in a single model improved drastically models’ performances. Following this trend, many deep learning-based recommender systems [8, 9] have emerged bearing in mind quite a few forms of data. Nevertheless, these models need the information to be pre-processed which is usually a heavy task, especially when there are various features

In this primary 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 ideas related to the sector of recommender systems, illustrating the 2 most used families of algorithms, in addition to their commonest models. We’ve got highlighted the benefits and downsides of the several algorithms.

Currently, the research trend is increasingly towards hybrid systems that mix the most effective of collaborative and content-based filtering through the usage of graph each by way of data representation and the usage of graph-based algorithms. In the following article of this series, we are going to introduce the concept of data graphs and the way they may be utilized in recommender systems to supply more accurate and personalized recommendations to users.