The Web of Data is an interconnected global dataspace in which discovering resources related to a given resource and recommend relevant ones is still an open research area. This work describes a new recommendation algorithm based on structured data published on the Web (Linked Data). The algorithm exploits existing relationships between resources by dynamically analyzing both the categories to which they belong to and their explicit references to other resources. A user study conducted to evaluate the algorithm showed that our algorithm provides more novel recommendations than other state-of-the-art algorithms and keeps a satisfying prediction accuracy. The algorithm has been applied in a mobile application to recommend movies by relying on DBpedia (the Linked Data version of Wikipedia), although it could be applied to other datasets on the Web of Data. Due to the increase in the amount of structured data pub-
The mobile application presented in Section 5 was done at the Joint Open Lab MobiLAB and was supported by a fellowship from TIM. 1http://linkeddata.org CBRecSys 2016, September 16, 2016, Boston, MA, USA.
Copyright remains with the authors and/or original copyright holders
lished on the Web through the principles of Linked Data,
it is more likely to nd resources that describe or
represent real life concepts. The information provided by these
resources may be used in many di erent domains.
However, nding and recommending related resources is still an
open research area [
We conducted a user study to comparatively evaluate its accuracy and novelty against three state-of-the-art algorithms, which showed that our algorithm provides a higher number of novel recommendations, while keeping a satisfying prediction accuracy. An implementation of our recommendation algorithm has been integrated into a mobile application suggesting movies based on DBpedia, which was developed in collaboration with Telecom Italia, the major network operator in Italy. The paper is organized as follows: Section 2 reviews related works; Section 3 presents our algorithm; Section 4 describes the evaluation method and provides the results; Section 5 shows the application of our algorithm for recommending movies; Section 6 provides conclusions.
This work began by conducting a systematic literature
review [
Damljanovic et al. [
Passant [
Other works combine Linked Data based algorithms with
other techniques of recommendation in order to improve the
results. These techniques include collaborative ltering [
We propose a new recommendation algorithm, which is crossdomain and cross-dataset. It relies only on Linked Data and does not require to reduce the set of resources and links of the dataset to those belonging to a speci c domain.
ReDyAl is a recommendation algorithm which takes into account the di erent types of relationships between the data published according to the Linked Data principles. It aims at discovering related resources from datasets that may contain either well-linked resources as well as poorly-linked resources. A resource is said to be well-linked if it has a number of links higher than the average number of links in the dataset; otherwise it is poorly-linked. The algorithm is able to dynamically adapt its behavior in order to nd a set of candidate resources to be recommended, relying on the implicit knowledge contained in the Linked Data relationships.
Any dataset on the Web of Data may be seen as a tuple (R,
T, L) composed by resources (R), categories (T ), and
relationships (L). Categories denote types, concepts or classes.
Resources are instances of concepts; they are Web resources
or real world resources identi ed by a URI. Relationships are
also known as links or properties; they are the links
connecting resources or categories along the whole dataset graph.
Categories often are hierarchically organized. For example,
DBpedia provides information about hierarchical
relationships in three di erent classi cation schemata: Wikipedia
Categories, YAGO3 [
Category-Category (T-T ) These are hierarchical relationships between categories within a hyponymy structure (a category tree). They can be represented by using the RDFS7 property rdfs:subClassOf or the SKOS8 properties skos:broader (isSubCategoryOf) and skos:narrower (isSuperCategoryOf).
Considering this model of a dataset, ReDyAl consists in
three stages:
1. The rst stage discovers resources by analyzing the
links between the given initial resource and other
resources. Only R-R relationships are considered at this
stage, although they can be indirect, i.e. they can
connect two resources through a third one.
3http://www.mpi-inf.mpg.de/yago-naga/yago/
4https://wordnet.princeton.edu
5http://www.w3.org/TR/rdf11-concepts/
6http://dublincore.org/documents/dcmi-terms/
7http://www.w3.org/TR/rdf-schema/
8https://www.w3.org/TR/skos-reference
2. The second stage analyzes the categorization of the
given initial resource and discovers similar resources
located in the same categories. It nds indirect
relationships between resources through direct R-T and T-T
relationships. It is possible to specify to the algorithm
which speci c R-T and T-T relationships to consider
in this step: the choice for R-T relationships is between
dcterms:subject or rdf:type, while skos:broader and
skos:narrower or rdfs:subClassOf are acceptable
TT relationships.
3. The last stage intersects the results of both the
previous stages and ranks them by giving priority to those
found in the rst stage. The algorithm computes the
similarity of the initial resource with respect to any of
the discovered resources, based on a similarity
function which combines the Linked Data Semantic
Distance (LDSD) [
The algorithm can be applied to any dataset on the Web of Data. In the rst step, it relies only on R-R relationships: any relationship of this kind may be used, independently of the data stored on the dataset. In the second step, the algorithm can be con gured to use the dcterms:subject or rdf:type properties, which are R-T relationships. DBpedia uses both to enable di erent categorizations; for example to rely on the Wikipedia categories, it is necessary to set dcterms:subject as R-T relationship and skos:broader and skos:narrower as T-T relationships. Any other dataset uses at least rdf:type to indicate the class which a resource is instance of. Thus, rdf:type can be used to nd resources in the same class and then rdfs:subClassOf can be used to retrieve more general classes (or skos:broader and skos:narrower, if the categories are organized through SKOS properties).
The algorithm is independent on the application domain because it relies only on R-R, R-T or T-T links. If in the dataset on which the algorithm is applied there are relationships among resources in di erent domains the algorithm may generate cross-domain recommendations. For example, DBpedia is a general dataset which represents resources of di erent kind and there may be a relationship between a song and a city because the song was recorded in that city, or because is about the city. Alternatively, there may be a link between a song and a movie because the song was part of the soundtrack of the movie. Thus, a city or a movie may be recommended starting from a song. Also R-T links may generates cross-domain recommendations if resources which belong to di erent domains are included into the same category.
Additionally, the algorithm may be con gured with a set of forbidden links in order to restrict the kind of links the algorithm should consider. This is useful to prevent the algorithm to obtain resources over links pointing to empty nodes (i.e. resources without a URI), literals that are used to identify values such as numbers and dates, and other nodes that are not desired for the recommendation. In other words, it is a way to limit the results of the algorithm. For example the DBpedia resource dbr:Turin contains the link dbpprop:populationTotal that points to the integer value 911823: we can confgure this link as forbidden link since it does not point to a resource which can be recommended. This is also useful to increase the performance of the algorithm because limiting the number of results decreases the ranking time. All the links which are not explicitly speci ed as forbidden are allowed links and de ne a domain of interest. This may be useful when the algorithm is applied to a generic dataset as DBpedia. This dataset contains millions of links between resources, and if a developer is creating an application in the music domain then he/she may be interested only in resources of that domain, so he/she may want to consider only links pointing to those resources i.e., a set of allowed links. In fact the algorithm is cross-domain, thus it may recommend a city or a movie starting from a song, as we have already explained. While this may be an advantage in some applications, it may be confusing in others, especially if not properly explained to the user. To limit the recommendations to speci c categories of resources (for example to consider only tracks and artists) it is su cient to \allow" only the relationships which point to these kinds of resources, i.e. which have such desired category as range.
ReDyAl receives as input an initial resource by specifying its corresponding URI (inU RI), and three values (minT , minC, maxDistance) for con guring its execution. The selection of minT and minC is arbitrary and depends on the dataset and the convenience of the user who is setting up the algorithm. minT is the minimum number of links (input and output links involving the initial resource) necessary to consider a resource as well-linked. The proper value of minT depends on the dataset: if it contains resources with a high number of links between them it is expected to be higher, while if the resources have only few links it should be set to a lower value. However, this parameter impacts on the algorithm: if the initial resource is well-linked, traversal interlinking has a higher priority in the generation of candidate resources, otherwise the algorithm gives priority to the hierarchical relationships. For example, a user may consider the use of the hierarchical algorithms only if the resources are connected with less than 10 links by setting minT to 10. In a similar way, the user may arbitrary x the value of minC, which is the minimum number of candidate resources that the algorithm is expected to generate, i.e. the number of candidate resources the user is expecting.
The value of maxDistance limits the distance (i.e. the number of hierarchical levels) that the algorithm considers in a category tree. maxDistance may be de ned manually; this is particularly useful when there are not enough candidate resources from the categories found at a certain distance (i.e. the number of candidate resources retrieved is lower than minC). In this case, the algorithm increases the distances in order to nd more resources and if the maxDistance value is reached with less than minC candidate resources, the algorithm ranks only the candidate resources found until that moment. Additionally, the algorithm may receive a list of forbidden links (FL) to avoid searching for candidate resources over a prede ned list of undesired links. ReDyAl (Algorithm 1) starts by retrieving a list of allowed links from the initial resource. Allowed links are those that are not speci ed as forbidden (F L) or that are explicitly dened in the initial resource. If there is a considerable number of allowed links (more than minT , i.e., the initial resource is well-linked) the algorithm obtains a set of candidate resources located through direct (DRlk) or indirect traversal links (IRlk), starting from the links explicitly de ned in the initial resource (Lines 1-8). A resource is indirectly linked to the initial resource if it is linked through another resource. A resource directly linked is located at traversal distance 1 from the initial resource, while a resource indirectly linked is located at traversal distance 2 from the initial resource. With regards to the traversal links, a maximum distance of 2 is considered because for distances higher than 2 (i.e 1 direct heap plus 1 indirect heap) the number of retrieved resources is dramatically increased, therefore increasing also the number of resources that are not relevant or related with the initial resource.
Next, if the current number of candidate resources generated (CRtr) is greater than or equal to minC, the algorithm terminates returning the results (Lines 9-10). Otherwise, the algorithm generates a category graph (Gc) with categories of the rst distance and applies iterative updates over the category graph over n distances from the initial resource, obtaining broader categories (i.e. more generic categories that are located in a higher level in a classi cation) until at least one of two following conditions is ful lled: the number of candidate resources is su cient (jCRj > minC), or the maximum distance is reached (currentDistance > maxDistance). At each iteration, candidate resources (CRhi) are extracted from the broader categories of maximum distance (Lines 14-23). In any case, the algorithm combines these results with the results obtained in Lines 3-8 (adding CRtr and CRhi to CR). Finally, the set of candidate results is returned (Line 23).
The nal operation is ranking the sets of candidate resources. The ranking process receives as input the candidate resources retrieved by the ReDyAl algorithm and ranks them according to their degree of similarity with the initial resource. This similarity is computed based on a combination of two distance measures: LDSD and HyProximity.
The LDSD distance, initially proposed by Passant [
LDSD (c1; c2) =
1
1 + Cdout + Cdin + Ciout + Ciin
(1)
HyProximity is a similarity measure de ned by Stankovic et
al. [
log(jCj) Hybridsim = (1
LDSD) + (hyP (r1; r2)) (3) (4) Finally, the measure that combines LDSD and HyProximity used by ReDyAl is de ned in Equation 4, where and may be set according to the convenience of the user: is the weight for the traversal algorithm and is the weight for the hierarchical algorithm. In this way, resources are ranked in descending order, arranged from the largest to the smallest value of Hybridsim.
We comparatively evaluated the prediction accuracy and the
novelty of the resources recommended with ReDyAl with
respect to three state-of-the-art recommendation algorithms
relying exclusively on Linked Data to produce
recommendations: dbrec [
Although our algorithm is not bound to any particular dataset,
we applied it to DBpedia because it is a general dataset that
o ers the possibility to evaluate the results in a number of
scenarios. DBpedia is one of the biggest datasets in the
Web of Data and the most interlinked [
A user study was conducted involving 109 participants. The
participants were mainly students of Politecnico di Torino
(Italy) and University of Cauca (Colombia) enrolled in IT
courses. The average age of the participants was 24 years old
and they were 91 males, 14 females, and 4 of them did not
provide any information about their sex. Although the
proposed algorithm is not bound to any particular domain, this
evaluation focused on movies because we aimed at applying
our algorithm in the mobile application presented in Section
5 (which suggest movies) and in this domain a quite large
amount of data is available on DBpedia. Additionally, it
was easier to nd participants, since no speci c skills are
required to express an opinion about movies. The algorithms
were compared within subjects [
The evaluation was conducted as follows. A list of 20 recommendations generated from a given initial movie was presented to the participants. For each recommendation two questions were asked: (Q1) Did you already know this recommendation? Possible answers were: yes, yes but I haven't seen it (if it is a movie) and no. (Q2) Is it related to the movie you have chosen? Possible answers were: I strongly agree, I agree, I don't know, I disagree, I strongly disagree. Each answer was assigned respectively a score from 5 to 1. We developed a website9 to collect the answers from the participants. The participants were able to choose an initial movie from a list of 45 movies selected from the IMDB top 250 list10. The rst 50 movies were considered and 5 movies were excluded because they were not available in DBpedia. Choosing these movies ensured participants to know them, but was also a limitation: the corresponding DBpedia resources are very well-linked, thus we could not properly evaluate the algorithm on poorly linked initial movies. The movies were presented to the user in a random order to avoid having most of the participants evaluating recommendations for the same initial movies (e.g. the rst in the lists). When a participant selected an initial movie the tool provided the corresponding list of recommendations with the questions mentioned above. The recommendations were presented in a randomized order. Each participant was able to evaluate recommendations from as many initial movies as he wanted, but he had to answer the questions for all the recommendations, i.e. was not possible to answer only to part of the questions for the initial movie chosen. As a result, the recommendations of the lists for 40 out of 45 initial movies were evaluated by at least one participant and each movie was evaluated by an average of 6.18 participants. The dataset with the initial movies and the lists of recommendations is available online11.
Each list of 20 recommendations was pre-computed. In particular, recommendations were generated for each of the 45 initial movies with each of the four di erent algorithms. Then, the recommendations generated by each algorithm were merged in a list of 20 recommendations to be shown to the participants. To do this, we generated a list of 40 recommendations by selecting the rst 10 pre-computed recommendations for each algorithm and we ordered them by the similarity computed by each algorithms, since each algorithm ranks its recommendations by using its semantic similarity function with values between 0 and 1. Then we eliminated eventual duplicates, since the same recommendation could be provided by more than one algorithm. The nal list was obtained considering the rst 20 recommendations of the merged list.
With regard to the questions stated at the beginning of
this section, to answer RQ1, the Root Mean Squared
Error (RMSE) [
Bad performers
Sweet spot ●
Excellent performers
Algorithm ● dbrec
HyProximity hierarchical HyProximity transversal ReDyAl 0 25
50
Novelty
75
100
Q2 were considered as reference and were normalized in the
interval [
The results of the evaluation are summarized in Figure 1, which compares the algorithms with respect to their RMSE and novelty. The \sweet spot" area represents the conditions in which an algorithm has a good trade-o between novelty and prediction accuracy. In e ect, presenting a high number of recommendations not known to the user is not necessarily good because it may prevent him to assess the quality of the recommendations: for example having in the provided recommendation a movie which he has seen and which he liked may increase the trust of the user in the RS. Regarding RQ1, HyProximity accounts for the lowest RMSE measures (with 25% and about 36% for the hierarchical and traversal versions respectively), but these results are less signi cant due to the low number of answers to Q2 for these algorithms (this means that the RMSE was computed over a low number of recommendations). For both ReDyAl and dbrec the RMSE is roughly 45%. Concerning RQ2, the two versions of HyProximity account for the highest values (hierarchical roughly 99%, while traversal about 97%). However, such a high rate of novel recommendations may confuse the user and prevent him to judge recommendations, as we have already explained. ReDyAl has a larger rate of novel recommendations than dbrec. These two algorithms account respectively for about 60% and 45%.
The recommendations generated by HyProximity in both
traversal and hierarchical version collected a low number of
answers to Q2 because most of the recommendations
generated by these algorithms were unknown as illustrated in
Table 1. Consequently the RMSE was computed over a low
number of recommendations. Thus, the results of these two
algorithms related to RQ1 are less de nitive than for the
others, since for measuring the prediction accuracy only the
evaluations for which the answer to Q1 was either \yes" or
\yes but I haven't seen it (if it is a movie)" were considered.
We computed the Fleiss' kappa [
In conclusion, Figure 1 illustrates that ReDyAl and dbrec provides a good trade-o between prediction accuracy and novelty (sweet spot area), although ReDyAl performs better in novelty. HyProximity hierarchical and HyProximity traversal seem to be excellent performers since the RMSE is low and the novelty is high, but the RMSE was computed on few evaluations. An additional analysis of these two algorithms is needed to verify if the user can bene t from such a high novelty and if novel recommendations are relevant. In addition, further investigation is needed on poorly-linked resources, since the choice of the initial movies focused on selecting well known movies to make easier the evaluation from participants, but the related resources were well-linked. On poorly-linked resources we expect ReDyAl and Hyproximity hierarchical keeping good recommendations since they can rely on categories, while dbrec and HyProximity traversal are likely to provide much less recommendations since they rely on direct links between resources.
An implementation of ReDyAl has been integrated into a mobile application developed in collaboration with Telecom Italia (the major network operator in Italy). This application recommends movies based on DBpedia: when the user enters the title of a movie, the application provides the Wikipedia categories to which the initial movie is related to. In this way, the user may focus on a speci c scope and can receive recommendations of related resources for any category. In addition, it is possible to view any recommendation to obtain additional information.
Our algorithm can provide cross-domain recommendations because it is independent on the domain and is applied on DBpedia, which is a general dataset. Thus, the recommended resources can be movies but also other relevant entities such as actors, directors, places of recording, books on which the movie is inspired, etc. Other advantages of using DBpedia as dataset are the high number of resources that it represents, the variety of domains addressed and the continuous update and growth, since it is extracted from Wikipedia.
For example, given The Matrix as initial movie the
categories which it belongs to are presented. The user may be
more interested in martial arts, post-apocalyptic movies or
he may prefer to consider all the movies from American
directors, thus he can choose a category accordingly. By
selecting Post-apocalyptic lms, a number of resources are
recommended. For each recommendation it is possible to open
Algorithm
ReDyAl
dbrec
HyProximity hierarchical
HyProximity traversal
a detailed view, which contains three tabs: the rst contains
a brief textual description, the second presents a graph view
of the resource in order to show the main properties and the
third summarizes the main information in a tabular form.
The graph view is illustrated in Figure 2. The graph is
paginated and few properties per page are presented in
order to avoid information overload, since the resource can
have a very high number of properties. This view can be
useful also to explain the recommendation: for instance the
user can understand that the recommended resource has the
same director or the same main actor as the initial movie.
The graph view is based on DBpedia Mobile Explorer [
We presented ReDyAl which is a hybrid algorithm that dynamically uses both the traversal and hierarchical approach for discovering resources. It is independent from the application domain and, although we applied it to DBpedia, it could be easily adapted to other dataset in the Web of Data. It relies only on Linked Data and does not require to reduce the set of resources and links of the dataset to those belonging to a speci c domain.
We evaluated and compared our algorithm against three state-of-the-art algorithms by conducting a user study and we also showed a practical application of the algorithm by presenting a mobile application that provides movie recommendations relying on DBpedia. Although the algorithm could be applied to other datasets in the Web of Data, we selected DBpedia because it is a general dataset, thus crossdomain recommendations were possible. In addition, there is a high number of resources represented, a variety of domains addressed and it is continuously updated, since it is extracted from Wikipedia. The user study demonstrated that ReDyAl improves in the novelty of the results discovered, although the accuracy of the algorithm is not the highest (due to its inherent complexity). Although ReDyAl is not bound to any particular domain, the study focused on movies as for this domain there is a quite large amount of data available on DBpedia and participants were not required to have speci c skills.
Future work includes studying the relevance under di erent domains and improving the accuracy of ReDyAl while maintaining its novelty. We plan to conduct other studies to compare it with traditional techniques and with approaches which combine Linked Data with traditional techniques. We are also working on combining ReDyAl with collaborative ltering techniques in order to take user preferences into account while providing recommendations. 14https://www.dropbox.com/sh/0q8d2mcbko9e2oj/ AAASh-YHGz0MmG_Z8hH6mfWOa?dl=0