ItemRank: A Random-Walk Based Scoring Algorithm for Recommender Engines

1 Introduction

A recommender system makes personalized product suggestions by extracting knowledge from the previous user interactions with the system. Such services are particularly useful in the modern electronic marketplace which offers an unprecedented range of products. In fact a recommender system represents an added value both for consumers, who can easily find products they really like, and for sellers, who can focus their offers and advertising efforts. Several recommender systems have been developed that cope with different products, e.g. MovieLens for movies (see [Sarwar et al., 2001]), GroupLens for usenet news [Miller et al., 2002], Ringo for music [Shardanand and Maes, 1995], Jester for jokes [Goldberg et al., 2001] and many other (see e.g. [Schafer et al., 2001] for a review). A recommender system constructs a user profile on the basis of explicit or implicit interactions of the user with the system. The profile is used to find products to recommend to the user. In the simplest approach, the profile is constructed using only features that are related to the user under evaluation and to the products he/she has already considered. In those cases, the profile consists of a parametric model that is adapted according to the customer's behavior. Key issues of collaborative filtering approach are scalability and quality of the results. In fact, real life largescale E-commerce applications must efficiently cope with hundreds of thousands of users. Moreover, the accuracy of the recommendation is crucial in order to offer a service that is appreciated and used by customers. In this paper, we present "ItemRank", a random-walk based scoring algorithm, which can be used to rank products according to expected user preferences, in order to recommend top-rank items to potentially interested users. We tested our algorithm on a popular database, the MovieLens dataset 1 by the GroupLens Research group at University of Minnesota and we compared ItemRank with other state-of-the-art ranking techniques (in particular the algorithms described in [Fouss et al., 2005]). This database contains data collected from a popular recommender system on movies that has been widely exploited as a benchmark for evaluating recently proposed approaches to recommender system (e.g. [Fouss et al., 2005; Sarwar et al., 2002]). The schema of such archive resembles the structure of the data of many other collaborative filtering applications. Our experiments show that ItemRank performs better than the other algorithms we compared to and, at the same time, it is less complex than other proposed algorithms with respect to memory usage and computational cost too. The paper is organized as follows. In the next subsection (1.1) we review the related literature with a special focus on other graph based similarity measure and scoring algorithms applied to recommender systems. Section 2 describes the MovieLens data set (in subsection 2.1) and illustrates the data model we adopted (in subsection 2.2). Section 3 discusses ItemRank algorithm in details and we address ItemRank algorithm complexity issues in subsection 3.1. Section 4 contains the details of the experimentation, while Section 5 draws some conclusions and addresses future aspects of this research.

1 http://www.movielens.umn.edu

1.1 RelatedWork

Many different recommending algorithms have been proposed in literature, for example there are techniques based on Bayesian networks [Breese et al., 1998], Support Vector Machines [Grcar et al., 2005] and factor analysis [Canny, 2002]. The most successful and well-known approach to recommender system design is based on collaborative filtering [Sarwar et al., 2001; Shardanand and Maes, 1995]. In collaborative filtering, each user collaborates with others to establish the quality of products by providing his/her opinion on a set of products. Also, a similarity measure between users is defined by comparing the profiles of different users. In order to suggest a product to an "active user", the recommender system selects the items among those scored by similar customers. The similarity measure is often computed using the Pearson-r correlation coefficient between users (e.g. in [Sarwar et al., 2001]). Recently a graph based approach has been proposed in [Fouss et al., 2005]. Fouss et al. compared different scoring algorithm to compute a preference ranking of products (in that case movies) to suggest to a group of users. In this paper the problem has been modeled as a bipartite graph, where nodes are users (people node) and movies (movie node), and there is a link connecting a people node ui to a movie node mj if and only if ui watched movie mj, in this case arcs are undirected and can be weighted according to user preferences expressed about watched movies. Authors tested many different algorithms using a wide range of similarity measures in order to rank movies according to user preferences, some of the most interesting methods are:

Average Commute Time (CT). This is a distance measure between a pair of nodes i and j in a graph, we denote it as n(i, j), it is defined as the average number of steps that a random walker 2 going across a given graph, starting in the state corresponding to node i, will take to enter state j for the first time and go back to i. If we measure this distance between people and movie nodes in the given bipartite graph, we can use this score to perform the movie ranking.

Principal Component Analysis based on Euclidean Commute Time Distance (PCA CT). From the eigenvector decomposition of L+, that is the pseudoinverse of the Laplacian matrix (L) corresponding to the graph, it is possible to map nodes into a new Euclidean space that preserves the Euclidean Commute Time Distance, it is also possible to project to a m-dimensional subspace by performing a PCA and keeping a given number of principal components. Then distances computed between nodes in the reduced space can be used to rank the movies for each person.

Pseudoinverse of the Laplacian Matrix (L+). Matrix L+ is the matrix containing the inner products of the node vectors in the Euclidean space where the nodes are exactly separated by the ECTD, so l+i,j can be used as the similarity measure between node i and j, in order to rank movies according to their similarity with the person.

In literature there are many other examples of algorithms using graphical structures in order to discover relationships between items. Chebotarev and Shamis proposed in [Chebotarev and Shamis, 1997] and [Chebotarev and Shamis, 1998]

2 see [Norris, 1997] for more details

a similarity measure between nodes of a graph integrating indirect paths, based on the matrix-forest theorem. Similarity measures based on random-walk models have been considered in [White and Smyth, 2003], where average first-passage time has been used as a similarity measure between nodes. In collaborative recommendation field is also interesting to consider different metrics described in [Brand, 2005].

2 The Problem

Formally, a recommender system deals with a set of users ui, i = 1, . . . , Un and a set of products pj , j = 1, . . . , Pn, and its goal consists of computing, for each pair: ui, pj, a score ˆ ri,j that measures the expected interest of users ui for product pj on the basis of a knowledge base containing a set of preferences expressed by some users about products. So we need a scoring algorithm to rank products/items for every given user according to its expected preferences, then a recommender system will suggest to a user top-ranked items with respect to personalized ordering. In this section we present the data model we adopted and MovieLens data set, that is a widely used benchmark to evaluate scoring algorithms applied to recommender systems. Our choice with respect to the data model and the data set is not restrictive since it reflect a very common scenario while dealing with recommender systems. In the following we will indifferently make use of terms such as item, product and movie depending on the context, but obviously the proposed algorithm is a general purpose scoring algorithm and it does not matter which kind of items we are ranking in a particular scenario, moreover we will also use the notation mj to refer a product pj in the particular case of movies to be ranked.

2.1 MovieLens Data Set

MovieLens site has over 50, 000 users who have expressed opinions on more than 3, 000 different movies. The MovieLens dataset is a standard dataset constructed from the homonym site archive, by considering only users who rated 20 or more movies, in order to achieve a greater reliability for user profiling. The dataset contains over 100, 000 ratings from 943 users for 1, 682 movies. Every opinion is represented using a tuple: ti,j = (ui,mj, ri,j), where ti,j is the considered tuple, ui ∈ U is an user, mj ∈ M is a movie, and ri,j is a integer score between 1 (bad movie) and 5 (good movie). The database provides a set of features characterizing users and movies which include: the category of the movie, the age, gender, and occupation of the user, and so on. The dataset comes with five predefined splitting, each uses 80% of the ratings for the training set and 20% for the test set (as described in [Sarwar et al., 2002]). For every standard splitting we call L and T respectively the set of tuples used for training and for testing, moreover we refer the set of movies in the training set rated by user ui as Lui and we write Tui for movies in the test set. More formally: Lui = {tk,j ∈ L : k = i} and Tui = {tk,j ∈ T : k = i}.

2.2 DataModel: Correlation Graph

Even from a superficial analysis of the proposed problem, it seems to be clear that there is a different correlation degree between movies, if we could exploit this information from the training set then it would be quite easy to compute user dependent preferences. We define Ui,j ⊆ U the set of users who watched (according to the training set) both movie mi and mj, so:

Now we compute the (|M|×|M|) matrix containing the number of users who watched each pair of movies:

where | · | denotes the cardinality of a set, obviously ∀i, ˜ Ci,i = 0 and ˜ C is a symmetric matrix. We normalize matrix ˜ C in order to obtain a stochastic matrix Ci,j = ˜ Ci,j ωj where ωj is the sum of entries in j - th column of ˜ C. C is the Correlation Matrix, every entry contains the correlation index between movie pairs. The Correlation Matrix can be also considered as a weighted connectivity matrix for the Correlation Graph GC. Nodes in graph GC correspond to movies inM and there will be an edge (mi,mj) if and only if Ci,j > 0. Moreover the weight associated to link (mi,mj) will be Ci,j, note that while ˜ C is symmetrical, C is not, so the weight associated to (mi,mj) can differ from (mj,mi) weight. The Correlation Graph is a valuable graphical model useful to exploit correlation between movies, weights associated to links provide an approximate measure of movie/movie relative correlation, according to information extracted from ratings expressed by users in the training set.

3 ItemRank Algorithm

The idea underlying the ItemRank algorithm is that we can use the model expressed by the Correlation Graph to forecast user preferences. For every user in the training set we know the ratings he assigned to a certain number of movies, that is Lui , so, thanks to the graph GC we can "spread" user preferences through the Correlation Graph. Obviously we have to properly control the preference flow in order to transfer high score values to movies that are strongly related to movies with good ratings. The spreading algorithm we apply has to possess two key properties: propagation and attenuation. These properties reflect two key assumptions. First of all if a movie mk is related to one or more good movies, with respect to a given user ui, then movie mk will also be a good suggestion for user ui , if we analyse the Correlation Graph we can easily discover relationships between movies and also the strength of these connections, that is the weight associated to every link connecting two movies. The second important factor we have to take into account is attenuation. Good movies have to transfer their positive influence through the Correlation Graph, but this effect decrease its power if we move further and further away from good movies, moreover if a good movie mi is connected to two or more nodes, these have to share the boosting effect from mi according to the weights of their connections as computed in matrix C. PageRank algorithm (see [Page et al., 1998]) has both propagation and attenuation properties we need, furthermore thanks to significant research efforts we can compute PageRank in a very efficient way (see [Kamvar et al., 2003a]). Consider a generic graph G = (V, E), where V is the set of nodes connected by directed links in E, the classic PageRank algorithm computes an importance score PR(n) for every node n ∈ V according to graph connectivity: a node will be important if it is connected to important nodes with a low out-degree. So the PageRank score for node n is defined as:

where ωq is the out-degree of node q, α is a decay factor 3 . The equivalent matrix form of equation 1 is:

where C is the normalized connectivity matrix for graph G and 1|V| is a |V| long vector of ones. PageRank can also be computed iterating equation 2, for example by applying the Jacobi method [Golub and Loan, 1996], even if iteration should be run until PageRank values convergence, we can also use a fixed number I of iterations. Classic PageRank can be extended by generalizing equation 2:

where M is a stochastic matrix, its non-negative entries has to sum up to 1 for every column, and vector d has nonnegative entries summing up to 1. Vector d can be tuned in order to bias the PageRank by boosting nodes corresponding to high value entries and matrix M controls the propagation and attenuation mode. Biased PageRank has been analysed in [Langville and Meyer, 2003] and custom static score distribution vectors d have been applied to compute topic-sensitive PageRank [Haveliwala, 2002], reputation of a node in a peerto-peer network [Kamvar et al., 2003b] and for combating web spam [Gyongyi et al., 2004]. We present the ItemRank algorithm, that is a biased version of PageRank designed to be applied to a recommender system. ItemRank equation can be easily derived from equation 3. We use graph GC to compute a ItemRank value IRui for every movie node and for every user profile. In this case the stochastic matrix M will be the Correlation Matrix C and for every user ui we compute a different IRui by simply choosing a different dui static score distribution vector. The resulting equation is:

where dui has been built according to user ui preferences as recorded in training set Lui . The unnormalized ˜dui , with respect to the j - th component, is defined as:

3 A common choice for α is 0.85

So the normalized dui vector will simply be dui = ˜dui | ˜dui | . ItemRank, as defined in equation 4, can be computed also iteratively in this way:

This dynamic system has to be run for every user, luckily it only needs on average about 20 iterations to converge. The interpretation of IRui score vector for user ui is straightforward, ItemRank scores induce a sorting of movies according to their expected liking for a given user. The higher is the ItemRank for a movie, the higher is the probability that a given user will prefer it to a lower score movie.

3.1 Complexity Issues

ItemRank algorithm results to be very efficient both from computational and memory resource usage point of view. We need to store a |M| nodes graph with a limited number of edges. The interesting fact is that graph GC contains edges (mi,mj) and (mj,mi) if and only if ∃uk : tk,i ∈ Luk ∧ tk,j ∈ Luk , so no matter the number of users satisfying the previous condition, ratings information will be compressed in just a couple of links anyway. It is interesting to note that the data structure we use scale very well with the increase of the number of users, in fact GC node set cardinality is independent from |U| and also the number of edges tend to increase very slowly after |U| has exceeded a certain threshold ¯U. That is a very useful property, because in a real applicative scenario the number of users for a certain e-commerce service and the number of expressed preferences about products will rise much faster than the total amount of offered products. Moreover ItemRank computation is very efficient, thanks to its strong relationship with PageRank algorithm, and we only need about 20 iterations of system 5 for every user in order to rank every movie according to every user taste, so if we have |U| users we have to run the algorithm |U| different times. ItemRank is more efficient than similar Random-Walk based approach such as CT and L+ (already introduced in subsection 1.1, see [Fouss et al., 2005] for details), in fact both CT and L+ require to handle a graph containing nodes representing users and products and edges referred to user preferences. So in this graph there are |U| + |M| nodes and two edges (ui, mj),(mj , ui) for every opinion (ui,mj, ri,j), while in the case of ItemRank you have only |M| nodes and ratings information is compressed. CT is used to rank every movie with respect to every system user, so the average commute time (CT) n(ui,mj) referred to any user-movie couple ui,mj has to be computed, but n(ui,mj) = m(ui|mj) + m(mj|ui) where m(ui|mj) denotes the average first-passage time from node ui to node mj . So CT needs 2 · |U| · |M| average first-passage time computations, while ItemRank has to be applied only |U| times to rank every movie with respect to its similarity to every user. The situation is similar also if we consider L+ algorithm, in this case, as stated in [Fouss et al., 2005], the direct computation of the pseudoinverse of the Laplacian matrix L becomes intractable if the number of nodes becomes large (that could easy happen while the number of users increase), some optimized methods to partially overcome these limitations has been proposed in [Brand, 2005].

4 Experimental Results

To evaluate the performances of the ItemRank algorithm, we ran a set of experiments on the MovieLens data set, described in subsection 2.1. The choice of this particular data set is not restrictive, since it is a widely used standard benchmark for recommender system techniques and its structure is typical of the most common applicative scenarios. In fact we can apply ItemRank every time we have a set of users (U) rating a set of items or products (I that is the generic notation for M), if we can model our recommendation problem this way (or in any equivalent form) it will be possible to use ItemRank to rank items according to user preferences. We chose an experimental setup and performance index that is the same as used in [Fouss et al., 2005], this way we can directly compare our algorithm with some of the most promising scoring algorithms we found in related literature (CT, L+ and so on), having many points of contact with ItemRank "philosophy". We split MovieLens data set as described in [Sarwar et al., 2002], in order to obtain 5 different subsets, then we applied ItemRank 5 times (5-fold cross validation). Each time, one of the 5 subsets is used as the test set and the remaining 4 sub sets have been merged to form a training set. At the end we computed the average result across all 5 trials. So we have 5 splittings, each uses 80% of the ratings for the training set (that is 80, 000 ratings) and 20% for the test set (the remaining 20, 000 ratings), that is exactly the same way tests have been performed in [Fouss et al., 2005]. The performance index we used is the degree of agreement (DOA), which is a variant of Somers'D (see [Siegel and Castellan, 1988] for further details). DOA is a way of measuring how good is an item ranking (movie ranking in MovieLens case) for any given user. To compute DOA for a single user ui we need to define a set of movies NWui ⊂M that is the set of movies that are not in the training set, nor in the test set for user ui, so:

Now we define the boolean function check order as:

where IRmj ui is the score assigned to movie mj with respect to user ui preferences, by the algorithmwe are testing. Then we can compute individual DOA for user ui, that is:

So DOAui measures for user ui the percentage of movie pairs ranked in the correct order with respect to the total number of pairs, in fact a good scoring algorithm should rank the movies that have indeed been watched in higher positions than movies that have not been watched. A random ranking produces a degree of agreement of 50%, half of all the pairs are in correct order and the other half in bad order. An ideal ranking correspond to a 100% DOA. Two different global degree of agreement can be computed considering ranking for individual users: Macro-averaged DOA and micro-averaged DOA. The Macro-averaged DOA (or shortly Macro DOA) will be the average of individual degree of agreement for every user, so:

The micro-averaged DOA (or shortly micro DOA) is the ratio between the number of movie pairs in the right order (for every user) and the total number of movie pairs checked (for every user), so it can be computed as:

Then micro DOA is something like a weighted averaging of individual DOA values. In fact the bigger is set Tui for a given user ui, the more important is the individual DOAui contribution to micro DOA global computation. Macro DOA and micro DOA have been evaluated for every experiment we ran. We summarize experimental results in table 1 and 2. In table 1 we compare ItemRank performances to a simplified version of the same algorithm, in order to highlight the importance of the information hidden in the Correlation Matrix C. ItemRank with the binary graph is identical to classical ItemRank (described in section 3) but there is a key difference in the way we build matrix C (we denote the simplified version as C bin ), in this case it is obtained by normalizing a binary version of ˜ C ( ˜ C bin ), so we have: C bin i,j = ˜ Cbin i,j ωj where ˜ C bin i,j can be computed as:

In other words if we compute ItemRank with binary graph, we are weighting every correlation edge connecting two items in the same way, no matter the number of co-occurrences in user preference lists for these items, since C bin i,j correspond to the weight of edge (mi,mj) in the Correlation Graph GC we use for information propagation.

Table 1 clearly shows the usefulness of a properly weighted Correlation Matrix C compared to C bin . This table provides both Macro and micro DOA for every split and for ItemRank and its simplified version with binary graph: ItemRank clearly works much better when we use a proper Correlation Matrix. For example, if we look at Macro DOA mean values, ItemRank with Correlation Matrix C obtain +15.43 points (in %) with respect to C bin version. These are interesting results because they confirm our main hypothesis: ItemRank algorithm ranks items according to the information extracted from the Correlation Matrix (that is equivalent to the weighted Correlation Graph) and the way we compute C entries is really able to properly model relationships among evaluated items. Finally table 2 shows a performance comparison among different scoring algorithm applied to MovieLens data set. We briefly described some of these algorithms in subsection 1.1, for further details see [Fouss et al., 2005]. For every tested algorithm we provide Macro DOA index, that has been computed for every technique as the average result across all 5 trials of 5-fold cross-validation. Moreover we provide the difference (in %) with performance obtained by the trivial MaxF algorithm and the standard deviation (STD) of this quantity. MaxF is our baseline for the task, it is a user independent scoring algorithm, it simply ranks the movies by the number of persons who watched them, movies are suggested to each person in order of decreasing popularity. So MaxF produces the same ranking for all the users. ItemRank performs better than any other considered technique obtaining +3.69 with respect to the baseline and a very good standard deviation (0.31). In this test ItemRank also perform better than L+ algorithm by obtaining a Macro DOA value of 87.76 versus 87.23 for L+ and also a better standard deviation. In addition it is worth to note that ItemRank is less complex than other proposed algorithms with respect to memory usage and computational cost too, as already argued in subsection 3.1.

5 Conclusions

In this paper, we present a random-walk based scoring algorithm, which can be used to recommend products according to user preferences. We compared our algorithm with other state-of-the-art ranking techniques on MovieLens data set. ItemRank performs better than the other algorithms we compared to and, at the same time, it is less complex than other proposed algorithms with respect to memory usage and computational cost too. Future research topics include the experimentation of the algorithm on different applications. We are now working on a extension of ItemRank. The version presented so far is able to handle the recommendation task as a item scoring/ranking problem. But we can face the problem from the regression point of view too. So we expect ItemRank 2.0 will also be able to produce expected satisfaction prediction for a given recommendation, other than product ranking.

Acknowledgments

Many thanks to Giuliano Testa for running the experiments.