In this paper we compare several techniques to automatically feed a graph-based recommender system with features extracted from the Linked Open Data (LOD) cloud. Specifically, we investigated whether the integration of LOD-based features can improve the e↵ectiveness of a graph-based recommender system and to what extent the choice of the features selection technique can influence the behavior of the algorithm by endogenously inducing a higher accuracy or a higher diversity. The experimental evaluation showed a clear correlation between the choice of the feature selection technique and the ability of the algorithm to maximize a specific evaluation metric. Moreover, our algorithm fed with LODbased features was able to overcome several state-of-the-art baselines: this confirmed the e↵ectiveness of our approach and suggested to further investigate this research line.
The Linked Open Data (LOD) cloud is a huge set of
interconnected RDF statements covering many topical domains,
ranging from government and geographical data to
structured information about media (movies, books, etc.) and
life sciences. The typical entry point to all this plethora of
data is DBpedia [
Recent attempts towards the exploitation of Linked Open
Data to build RSs are due to Passant [
To this end, in this paper we propose a methodology to
automatically feed a graph-based recommendation algorithm
with features extracted from the LOD cloud. We focused
our attention on graph-based approaches since they use a
uniform formalism to represent both collaborative features
(connections between users and items, expressed through
ratings) and LOD-based ones (connections between di↵erent
items, expressed through RDF statements). As graph-based
algorithm we adopted PageRank with Priors [
The rest of the paper is organized as follows: the description of our recommendation methodology is the core of Section 2, while the details of the experimental evaluation we carried out along with the discussion of the results are provided in Section 3. Finally, Section 4 sketches conclusions and future work. 2.
The main idea behind our graph-based model is to represent users and items as nodes in a graph. Formally, given a set of users U = {u1 . . . un} and a set of items I = {i1 . . . um}, a graph G = hV, Ei is instantiated. Given that for each user and for each item a node is created, |V | = |U | + |I|. Next, an edge connecting a user ui with an item ij is created for each positive feedback expressed by that user, so E = {(ui, ij )|likes(ui, ij ) = true}.
Given this basic formulation, built on the ground of
simple collaborative2 data points, each item i 2 I can be
provided with a relevance score. To calculate the relevance of
each item, we used a well-known variant of the PageRank
called PageRank with Priors [
N
ank with Priors adopts a non-uniform personalization vector
assigning die↵rent weights to di↵erent nodes to get a bias
towards some nodes (specifically, the preferences of a specific
user). In our algorithm the probability was distributed by
defining a simple heuristics, set after a rough tuning: 80%
of the total weight is evenly distributed among items liked
by the users (0% assigned to items disliked by the users),
while 20% is evenly distributed among the remaining nodes.
Damping factor was set equal to 0.85, as in [
Given this setting, the PageRank with Priors is executed for each user (this is mandatory, since the prior probabilities change according to user’s feedbacks), and nodes are ranked according to their PageRank score which is in turn calculated on the ground of the connectivity in the graph. The output of the PageRank is a list of nodes ranked according to PageRank scores, labeled as L. Given L, recommendations are built by extracting from L only those nodes i1 . . . in 2 I. 2.1
As stated above, our basic formulation does not take into account any data point di↵erent from users’ ratings. The insight behind this work is to enrich the above described graph by introducing some extra nodes and some extra edges, defined on the ground of the information available in the LOD cloud. Formally, we want to define an extended graph GLOD = hVLOD ALL, ELOD ALLi, where VLOD ALL = V [ VLOD and ELOD ALL = E [ ELOD. VLOD and ELOD represent the extra nodes and the extra edges instantiated by analyzing the data gathered from the LOD cloud, respectively.
As an example, if we consider the movie The Matrix, the property http://dbpedia.org/property/director encoding the information about the director of the movie is available in the LOD cloud. Consequently, an extra node The Wachowski Brothers is added in VLOD and an extra edge, labeled with the name of the property, is instantiated in ELOD to connect the movie with its director. Similarly, if we consider the property http://dbpedia.org/property/starring, new nodes and new edges are defined, in order to model the relationship between The Matrix and the main actors, as Keanu Reeves, for example. In turn, given that Keanu Reeves acted in several movies, many new edges are added in the graph and many new paths now connect di↵erent movies: these paths would not have been available if the only collaborative data points were instantiated.
It immediately emerges that, due to this novel enriched representation, the structure of the graph tremendously changes since many new nodes and many new edges are added to the model: the first goal of our experimental session will be to investigate whether graph-based RSs can benefit of the introduction of novel LOD-based features. 2.2
Thanks to the data points available in the LOD cloud, many new information can be encoded in our graph. How2We just modeled user-items couples, as in collaborative filtering algorithms ever, as the number of extra nodes and extra edges grows, the computational load of the PageRank with Priors grows as well, so it necessary to identify the subset of the most useful properties gathered from the LOD cloud and to investigate to what extent (if any) each of them improves the accuracy of our recommendation strategy.
A very naive approach may be to manually select the most relevant LOD-based features, according to simple heuristics or to domain knowledge (e.g. properties as director, starring, composer may be considered as relevant for the Movie domain, whereas properties as runtime or country may be not). This basic approach has several drawbacks, since it requires a manual e↵ort, but it is also strictly domain-dependent.
To avoid this, we employed features selection techniques to automatically select the most promising LOD-based features. Formally, our idea is to take as input ELOD, the overall set of LOD-based properties, and to produce as output ELOD F ST ✓ ELOD, the set of properties a specific feature selection technique T returned as relevant. Clearly, the exploitation of a feature selection technique T also produces a set VLOD F ST ✓ VLOD, containing all the LOD-based nodes connected to the properties in ELOD F ST .
In this setting, given a FS technique T , PageRank will be
executed against the graph GLOD T = hVLOD T , ELOD T i,
where VLOD T = V [ VLOD F ST and ELOD T = E [
ELOD F ST . In the experimental session the e↵ectiveness of
seven di↵erent techniques for automatic selection of
LODbased features: PageRank, Principal Component Analysis
(PCA), Support Vector Machines (SVM), Chi-Squared Test
(CHI), Information Gain (IG), Information Gain Ratio (GR)
and Mininum Redundancy Maximum Relevance (MRMR)
[
Our experiments were designed on the ground of four different research questions: 1. Do graph-based recommender systems benefit of the introduction of LOD-based features? 2. Do graph-based recommender systems exploiting LOD features benefit of the adoption of FS techniques? 3. Is there any correlation between the choice of the FS technique and the behavior of the algorithm? 4. How does our methodology perform with respect to state-of-the-art techniques?
Experimental design: experiments were performed by exploiting MovieLens3 dataset, consisting of 100,000 ratings provided by 943 users on 1,682 movies. The dataset is positively balanced (55.17% of positive ratings) and shows an high sparsity (93.69%). Each user voted 84.83 items on average and each item was voted by 48.48 users, on average.
Experiments were performed by carrying out a 5-folds cross validation. Given that MovieLens preferences are expressed on a 5-point discrete scale, we decided to consider as positive ratings only those equal to 4 and 5. As recommendation algorithms we used the previously described PageRank 3http://grouplens.org/datasets/movielens/ metrics. Another interesting outcome which follows the use of FS techniques is the saving of computational resources to run PageRank with Priors on graph GLOD P CA. As shown in Table 1, the adoption of FS caused a huge decrease of the run time of the algorithms equal to 33.9% for MovieLens (from 880 to 581 minutes). This is due to the smaller number of information which are modeled in the graphs (-8.6% nodes and -4.8% edges).
MovieLens
Edges
Run (min.)
with Priors, set as explained in Section 2. We compared the ee↵ctiveness of our graph-based recommendation methodology by considering three di↵erent graph topologies: G, modeling the basics collaborative information about user ratings; GLOD, which enrichs G by introducing LOD-based features gathered from DBpedia, and GLOD T which lighten the load of PageRank with Priors by relying on the features selected by a FS technique T . In order to enrich the graph G, each item in the dataset was mapped to a DBpedia entry. In our experiments 1,600 MovieLens entries (95.06% of the movies) were successfully mapped to a DBpedia node. The items for which a DBpedia entry was not found were only represented by using collaborative data points. Overall, MovieLens entries were described through 60 di↵erent DBpedia properties. As feature selection techniques all the approaches previously mentioned were employed, while for the parameter K (the number of LOD-based features) three di↵erent values were compared: 10, 30 and 50. The performance of each graph topology was evaluated in terms of F1-measure. Moreover, we also calculated the overall running time4 of each experiment. To answer the third research questions we also evaluated the diversity of the recommendations, calculated by exploiting the classical Intra-List Diversity (ILD). Statistical significance was assessed by exploiting Wilcoxon and Friedman tests.
Discussion of the Results: in the first experiment we evaluated the introduction of LOD-based features in graphbased recommender systems. Results are depicted in the first two columns of Table 1. As regards MovieLens, a statistically significant improvement (p << 0.0001, assessed through a Wilcoxon test) was obtained for all the metrics. As expected, the expansion of the graph caused an exponential growth of the run time of the algorithm. This is due to the fact that the expansion stage introduced many new nodes and many new edges in the graph (see Table 1). The growth is particularly significant since 50,000 new nodes and 78,000 new edges were added to the graph.
Next, we evaluated the impact of all the previously presented feature selection techniques in such recommendation setting. By analyzing the results provided in Table 2, it emerged that our graph-based recommendation strategy does not often benefit of the application of FS techniques. Indeed, when a very small number of properties is chosen (K=10 ), none of the configurations is able to overcome the baseline. By slightly increasing the value of parameter K (K=30 ), only three out of seven techniques (PageRank, PCA and mRMR) improve the F1-measure. Next, when more data points are introduced (with K=50 ) better results are obtained and the F1-measure of the baseline is always overcame. Given that the overall number of LOD-based properties was equal to 60, it is possible to state that most of the properties encoded in the extended graph GLOD can be considered as relevant. Clearly, this is a very domain-specific outcome, which needs to be confirmed by more thorough analysis on die↵rent datasets. However, it is possible to state that the adoption of FS techniques requires a complete analysis of the usefulness of each of the properties encoded in the LOD. Overall, the best performing configuration was PCA, which was the only technique always overcoming the baseline with K = 50. A Friedman test also showed that PCA statistically overcomes the other techniques for all the 4Experiments were run on an Intel-i7-3770 CPU3.40 gHZ, with 32GB RAM.
In Experiment 3 we shifted the attention from F1-measure to die↵rent evaluation metrics, and we investigate whether the adoption of a specific FS technique can endogenously induce a higher diversity at the expense of a little F1. Results of the experiments are provided in Figure 1a. Due to space reasons, only the results for F1@10 are provided. In both charts we used four di↵erent symbols to identify the di↵erent behaviors of each technique. It emerged that CHI was the less useful technique, since it did not provide any significant benefit to neither F1 nor diversity. Next, PageRank provided a (small) improvement on F1 and it did not significantly change the diversity of the recommendations. It is noteworth that the larger increase in accuracy of PCA is balanced by a decrease in terms of diversity. On the other side, Gain Ratio obtained the overall best diversity of the recommendation but it decreases the F1 of the algorithm. To sum up, these results show that the choice of a particular FS technique has a significant impact on the overall behavior of the recommendation algorithm. As shown in the experiment, some techniques have the ability of inducing a higher diversity (or F1) at the expense of a little of F1 (or diversity, respectively), wheres other can provide a good compromise between both metrics. Clearly, more investigation is needed to deeply analyze the behavior of each technique, but these results already give some general guidelines which can drive the choice of the FS technique which best fits the requirements of a specific recommendation scenario.
Finally, we compared the e↵ectiveness of our methodology to the current state of the art. As baselines User-toUser CF (U2U-KNN), Item-to-Item CF (I2I-KNN), a simple popularity-based approach, a random baseline and the Bayesian Personalized Ranking Matrix Factorization (BPRMF) were used. We adopted the implementations available in MyMediaLite Recommender System library5. As regards 5http://www.mymedialite.net/
U2U and I2I, neighborhood size was set to 80, while BPRMF was run by setting the factor parameter equal to 100. Results are depicted in Figure 1b. As shown in the plots, our graph-based RS outperforms all the baselines for all the metrics taken into account. It is worth to note that our approach obtained a higher F1 also when compared to a wellperfoming matrix factorization algorithm as BPRMF, thus this definitely confirmed the e↵ectiveness of our approach.
In this work we proposed a graph-based recommendation methodology based on PageRank with Priors, and we evaluated di↵erent techniques to automatically feed such a representation with features extracted from the LOD cloud. Results showed that graph-based RSs can benefit of the infusion of novel knowledge coming from the LOD cloud and that a clear correlation between the adoption of a specific FS technique with the overall results of the recommender exitss, since some techniques endogenously showed the ability of increasing also the diversity of the recommendations generated by the algorithm. We also showed that our methodology was able to overcome several state-of-the-art baselines on both datasets. As future work, we will validate the approach by evaluating it on di↵erent dataset, and we will investigate the impact of LOD-based features with di↵erent learning approaches as Random Forest or SVM. (a) Trade-o↵ between F1 and Diversity