In this paper we present SPrank, a novel hybrid recommendation algorithm able to compute top-N item recommendations from implicit feedback exploiting the information available in the so called Web of Data. We leverage DBpedia, a well-known knowledge base in the LOD (Linked Open Data) compass, to extract semantic path-based features and to eventually compute recommendations using a learning to rank algorithm. Experiments with datasets on two di erent domains show that the proposed approach outperforms in terms of prediction accuracy several stateof-the-art top-N recommendation algorithms for implicit feedback in situations a ected by di erent degrees of data sparsity.
{ formulation of a hybrid recommendation problem in a learning to rank setting; { mining of the semantic graph of LOD datasets through path-based features to capture complex and not trivial relationships between items. 2
The common graph-based nature of the data models for both content-based recommender systems exploiting LOD and collaborative ltering recommender systems, suggests interesting ways to model a hybrid recommendation engine. We can merge these two graphs obtaining a new graph G = (V; R) as shown in Fig. 1, where V denotes the set of vertices and R the set of relationships. Due to the nature of the problem we identify three relevant subsets of V : U , I and E representing users, items and entities, respectively. Moreover, in our model the two following relations hold: I E and V = U [ E. Similarly, R contains two categories of relationships. In fact, we have R = S [ P where S = U I and P E E. More precisely, an edge s 2 S links a user u 2 U to his/her relevant items i 2 I while an edge p 2 P connects either an item i to another entity e 2 E in the graph or an entity ej 2 E n I to another entity ek 2 E. In the rest of the paper we will use u, i, e and v to represent a node belonging to U , I, E and V , respectively. Analogously, we will denote with s, p and r the edges in S, P and R. Thanks to this graph-based formulation of the problem we consider both collaborative and content aspects in a uni ed representation and hence a uni ed feature space. The purpose is recommending relevant items i to users u leveraging the knowledge encoded in the graph G. In the rest of the paper, in our data model we will always consider G as undirected.
Let S^ be the matrix of implicit feedback, where s^ui = 1 if item i is relevant for user u (i.e., there is an edge of type s between u and i), 0 otherwise. Looking at the graph in Fig. 1, for user u1 we have s^u1i1 = 1, s^u1i2 = 1 while s^u1i3 = 0, s^u1i4 = 0.
Starting from S^ we de ne Iu+ = fi 2 Ijs^ui = 1g as the set of relevant items for u and Iu = fi 2 Ijs^ui = 0g as the set of unknown items for u. We call Iu+ the user pro le of u. In Fig. 1, with reference to user u1, we have Iu+1 = fi1; i2g and Iu1 = fi3; i4g. The unobserved items Iu are exactly the items that have to be ranked. The ultimate goal of the system is to rank in the top-N positions items likely to be relevant for the user.
We formulate the problem of computing the top-N recommendations in a
learning to rank fashion similar to the document ranking problem adopted in Web
search [
Now we have all the elements to formally de ne the training set T R as: T R = [fhxui; s^uiiji 2 (Iu+ [ Iu )g
u Given the training set T R, computing the top-N recommendations for user u can be formulated as the task of generating a ranking function f : RD ! R such that f (xui) s^ui. Eventually, we use f ( ) to rank the items in Iu and getting the top-N recommendation list for u. Given a graph G as the one represented in Fig. 1, we want to extract features able to characterize the interactions between users, items and entities capturing the complex relationships between them. The basic idea is to consider all the paths that connect the user to an item in order to have a relevance score for that item. The more paths between user and item, the more the item is relevant for the user. However, in this formulation of the problem there are several types of paths and not all of them have the same relevance. Moreover, some paths that involve useless properties can be noisy for the purpose of recommendation. Based on these assumptions, we leverage a supervised approach and we delegate to the learning to rank algorithm the task of nding what paths are most relevant for computing top-N recommendations. Given an undirected graph G as previously de ned, we de ne a path as the acylic sequence of edges of the form (s; : : : ; rl; : : : ; rL) where s = (u; i) and rL = (v; i0) with i 6= i0. We also de ne the length of a path as the number of edges contained within such path. We consider paths having length greater than 1 and less than or equal than a given L. We collect all the possible paths in G to build a P ath index. P ath(j) represents the j-th component in the index and it corresponds to a speci c sequence of edge labels (i.e., to a path disregarding the actual nodes). Considering a user-item pair (u; i), we denote #pathui(j) as the number of paths between u and i corresponding to the speci c P ath(j) entry in the index. In other words, it represents how many paths of type P ath(j) connect u and i. This aggregate information corresponds to the frequency of P ath(j) in the sub-graph composed by all paths between u and i. We are now ready to de ne the path-based features. We de ne the j-th component in the feature vector xui as: xui(j) =
#pathui(j) PD d=1 #pathui(d) (1) Equation (1) represents the importance of the speci c sequence of edge labels P ath(j) between u and i in the sub-graph constituted by all the associations between these two nodes. Speci cally, it is the frequency of the speci c path P ath(j) normalized with respect to the frequencies of all the existing paths between u and i.
Depending on the type of links composing a path there are di erent types of
paths. In particular, such paths can be: (I) collaborative if only links in S are
involved as for (s; s; s); (II) content-based if there are only rl 62 S with l =
2; : : : ; L as for (s; p1; p2) or (s; p4; p2; p1); (III) hybrid if there is more than one
link in S and at least one link in P as for (s; p4; s; s) or (s; s; s; p4).
In order to predict the ranking and form the top-N recommendation lists we deal
with the learning to rank problem by adopting a point-wise approach. Point-wise
methods have shown to be very e ective in Web search ranking [
The experiments to evaluate the e ectiveness of SPrank in terms of accuracy for top-N recommendations have been carried out on two datasets belonging to two di erent domains: MovieLens (movies) and Last.fm (musical artists). The datasets that have been used are available at: http://sisinflab.poliba.it/ semanticweb/lod/recsys/datasets/.
From the original matrix S^, we built two new matrices: S^train and S^test. We
used the former for producing the sets Iu+, Iu and T R (used for training the
model), the latter for evaluating the trained model. To create S^test we randomly
selected ten positive feedback for each user from the initial matrix S^. In order to
assess the performance of SPrank in situations a ected by di erent level of data
sparsity, we evaluated our algorithm considering di erent sizes of user pro les.
Speci cally, for each user we randomly considered at most m positive feedback
from the original matrix S^ (denoted with \given m" in Tables 1 and 2) to form
^
Strain, and we discarded all the others. We say at most m because some users
can actually have less than m positive feedback. Di erent values of m correspond
to di erent matrices S^train, di erent sets Iu+, Iu and then di erent training sets
T R. For di erent sizes of the user pro le, we learned the model on the training
set T R and we applied the learned model to predict the unknown values
(0entries) in S^train. We got the full recommendation lists by sorting the predicted
values for each user and then we evaluated the accuracy for the top-N items.
We repeated the procedure 5 times for each condition by randomly drawing
new training/test sets in each round and at the end we averaged the results.
To evaluate the accuracy of the system we measured the recall@N , widely used
for evaluating top-N recommender systems [
For each s^ui in S^test, from the full recommendation list computed for u, we
randomly selected 100 items appearing neither in the test set related to that
user nor in the user pro le. We got a ranked list consisting of these 101 items.
The top-N recommendation list is obtained by considering just the rst N items
(N = 5; 10; 20) in this ranked list. Being pos the position of the test item i within
the ranked list, we have a hit if pos N , otherwise we have a miss. We note
that for any single test case, we have just one relevant item (i.e., the tested item
i). The recall for a single test case is either 0 (in case of a miss) or 1 (in case of
a hit). The overall recall on all users is de ned by averaging over all test cases:
#hits
j S^test j
(2)
The formula for precision@N di ers from Equation 2 just by a multiplicative
term N appearing at the denominator [
E ectiveness of the learning to rank algorithm. To understand whether the chosen learning to rank algorithm is e ective, we compared BagBoo, the learning to rank algorithm used in SPrank, with two other algorithms: Sum and GBRT . In Sum, the ranking function f (xui) is the arithmetic sum of all the path-based feature values. On the one side, the comparison with Sum gives us a baseline for semantic-based recommendation algorithm where all associations are equally considered. This allows us to evaluate our learning to rank algorithm against a basic not ranking-oriented semantic recommender. On the other side, the comparison with GBRT is useful to prove the e ectiveness of combining bagging and boosting. We recall that BagBoo is an extension of GBRT as it is an ensemble of gradient boosting regression trees.
Table 1 summarizes the accuracy results obtained on the two datasets. For the MovieLens dataset we observe that BagBoo outperforms both GBRT and Sum in all the di erent conditions of sparsity degree, even when there are few positive examples for each user. For example, if we analyze the recall@5, the improvement of BagBoo over Sum goes from +6:6% to +11% respectively for the two limit conditions (given 5 and given All). We also see that for the condition given 5 the improvement with respect to GBRT is very marked (+15:8%), but it decreases with the increasing of positive examples (+2% for given 30 and +3:2% for given All). For this dataset we observe that when there are only a few positive training examples for each user, GBRT is not able to learn an e ective ranking function. This is not the case for the bagging of several GBRT s. Looking at the results for Last.fm we observe again BagBoo outperforms the other algorithms but for the condition given 5.
From the results on the two datasets we can draw the following conclusions:
SPrank bene ts from learning to rank, both GBRT and BagBoo show
substantial improvements with respect to the Sum baseline, particularly when the
number of positive examples, and then the training data, increases; due to bagging,
BagBoo outperforms GBRT in all the analyzed situations. Hence, BagBoo is a
valid candidate for learning the ranking function in SPrank.
Comparison with other Algorithms. In order to evaluate SPrank we
compared it both with a hybrid algorithm proposed to address cold-start scenarios
and with ranking oriented collaborative ltering algorithms. All of these
approaches are state-of-the-art methods for positive implicit feedback scenarios.
BPRLinearMap (BPRLin) [10] adopts a Bayesian Personalized Ranking (BPR)
criterion for optimizing a ranking loss. For BPRLinearMap we built the
itemattribute matrix using the same content data used for SPrank. BPRMF [
From these experimental results, we can conclude that SPrank is able to compute accurate top-N recommendations even when there are few positive feedback where instead collaborative ltering algorithms have showed lower accuracy. On both datasets SPrank has also outperformed BPRLin, the other hybrid recommendation method proposed to address cold start and sparsity problems. the user pro le size.
Springer Series in Statistics. Springer New York Inc., New York, NY, USA, 2001. 7. X. Ning and G. Karypis. Slim: Sparse linear methods for top-n recommender systems. In Proceedings of the 2011 IEEE 11th International Conference on Data Mining, ICDM '11, pages 497{506. IEEE Computer Society, 2011. from implicit feedback leveraging linked open data. In 7th ACM Conference on 9. D. Y. Pavlov, A. Gorodilov, and C. A. Brunk. Bagboo: a scalable hybrid bagging