Nicolas Marie
email: nicolas.marie@inria.fr

Olivier Corby

Fabien Gandon

Ribière Myriam
email: myriam.ribiere@alcatel-lucent.com

Myriam Ribière

Composite interests' exploration thanks to on-the-fly linked data spreading activation

Keywords: G.2.2 [Mathematics of Computing]: Graph Theory -Graph algorithms; E.1 [Data]: Data Structures -Graphs and networks Algorithms, experimentation Semantic web, linked data, DBpedia, spreading activation, semantic spreading activation, exploratory search system, discovery engine, composite interest query

Exploratory search systems are built specifically to help the user in his cognitive consuming search tasks like learning or topic investigation. Some of these systems are built on the top of linked data and use semantics to provide cognitively-optimized search experiences. Thanks to their richness and to their connected nature linked data datasets can serve as a ground for advanced exploratory search. We propose to address the case of mixed interests' exploration in the form of composite queries (several unitary interests combined) e.g. exploring results and make discoveries related to both The Beatles and Ken Loach. . The main contribution of this paper is the proposition of a novel method that processes linked-data for exploratory search purpose. It makes use of a semantic spreading activation algorithm coupled with a sampling technique. Its particularity is to not require any results preprocessing. Consequently this method offers a high level of flexibility for querying and allows, among others, the expression of composite interests' queries on remote linked data sources. This paper also details the analysis of the algorithm behavior over DBpedia and describes an implementation: the Discovery Hub application. It is an exploratory search engine that notably supports composite queries. Finally the results of a user evaluation are presented.

INTRODUCTION

In 2006, Gary Marchionini [START_REF] Marchionini | Exploratory search: From finding to understanding[END_REF] stressed the distinction between lookup and exploratory search tasks. Lookup tasks refer to search tasks when the user looks for something in particular (e.g. known item search, question answering, fact checking). During lookup tasks the search keywords are well-defined and consequently the number of results is often limited and they are easy to understand.

Exploratory search [START_REF] Marchionini | Exploratory search: From finding to understanding[END_REF] refers to expensive cognitive search tasks when the search objective is fuzzy (e.g. learning or topic investigation). In this case the users manipulate iteratively an evolving set of keywords and have to synthesize an important amount of information coming from a changing results space. According to Gary Marchionini the actual search engines are not very efficient for the exploratory search tasks due to their keyword-based search paradigm [START_REF] Marchionini | Exploratory search: From finding to understanding[END_REF]. He proposed to complete the existing solutions with new approaches that are cognitively optimized for exploratory tasks.

To optimize the search experience some exploratory search systems are built on the top of knowledge bases. Some of them make use of semantic knowledge sources including the linked open data1 datasets. Linked data-based approaches involve the use of (1) the semantic web technologies where the semantic web is the web augmentation by formal metadata giving to software the access to some semantic facets of information. The semantic web data are expressed according to ontologies. An ontology is a partial representation of a world's conceptualization [START_REF] Guarino | Ontologies and Knowledge Bases -Towards a Terminological Clarification[END_REF] or in others words the conceptual vocabulary of a domain. The main semantic web standards include RDF [START_REF] Lassila | RESOURCE DESCRIPTION FRAMEWORK (RDF). W3C proposed Recommendation[END_REF], a graph model with XML syntax to describe resources, SPARQL language [START_REF] Prud | SPARQL query language for RDF[END_REF] allowing querying an RDF base, RDFS [START_REF] Brickley | Rdf vocabulary description language 1[END_REF] and OWL [START_REF] Mcguinness | Owl web ontology language overview[END_REF] for modeling ontologies. They also use [START_REF] Basse | Incremental characterization of RDF Triple Stores[END_REF] linked open data cloud (LOD) dataset(s) where the LOD is a web of interconnected public datasets published in RDF. Among all the LOD datasets DBpedia [START_REF] Auer | DBpedia: A nucleus for a web of open data[END_REF] is the most popular and used one. DBpedia results from the extraction of data from Wikipedia2 then published in RDF following the LOD principles 3 . As it is extracted from an encyclopedia DBpedia contains in a single graph a vast amount of highly heterogeneous resources of various types (e.g. persons, places) belonging to diverse domains (e.g. art, fashion, science, sport).

The graph structure of the LOD datasets like DBpedia offers a great potential to enable composite interests explorations on the following form "knowing my interest for X, Y and Z what can I discover/learn which is related to all these resources?". Using the linked data knowledge to solve such queries gives the possibility to identify complex, indirect, non-trivial paths between the combined interests. It can give a new perspective compared to the keyword-based search engines results which retrieve the web pages containing both strings. The composite queries can be used to get a fast summary of the connections between several resources (e.g. a journalist writing on the relations between Winston Churchill and Charles De Gaulle) or to unveil hidden connections (e.g. a fan of Ken Loach and The Beatles searching for cultural content related to both). It can also be used in some applications to be run without user intervention in order to provide content exploratory search features. In others' words, not all the inputs need to be query; they can also be context, preferences, etc.

The combined inputs are potentially heterogeneous, having diverse types and/or belonging to different domains. An illustration of the power of DBpedia to identify paths between two very different resources is the "everything is connected" application [START_REF] Vander | Everything is Connected: Using Linked Data for Multimedia Narration of Connections between Concepts[END_REF].

In this paper we propose a method allowing composite interests explorations exploiting the knowledge of the LOD. This paper is organized as follows. The section 2 presents the related works. The section 3 details our formal proposition. The section 4 describes the implementation we built on top of DBpedia. It also presents the algorithm behavior analysis' results and motivates the choices of the parameters. The Section 5 presents the hypotheses, the protocols and the results of a user's evaluations. Finally the section 6 concludes. We illustrate our proposition with a query combining The Beatles and Kean Loach. It was the first composite query entered by a user on the Discovery Hub prototype.

RELATED WORK

We present in this part the related works concerning linked data based knowledge exploration and discovery. The applications presented below belong to the broad category of semantic search systems. Semantic search can be defined as "search approaches that broadly speaking, use semantics to improve the search experience" [START_REF] Tran | Semantic Search-Systems, Concepts, Methods and the Communities behind It[END_REF]. These approaches are always based on an explicit semantic processing but they vary a lot in the tackled information needs, the information resources' representation, the query's representation and the results' computation. For an extensive survey about semantic search, the readers may refer to [START_REF] Tran | Semantic Search-Systems, Concepts, Methods and the Communities behind It[END_REF]. We focus on the works sharing the following properties:

-Fuzzy information need for knowledge exploration and discovery in learning or leisure situations. We focus on two categories of systems that are the recommenders and the exploratory search systems. -Graph-based inputs: such systems take one or several resource(s) as input(s) and retrieve others related and meaningful resources. After the computation, the resultresources are rendered and constitute the output or serve to identify the final content that is retrieved. -Linked data based processing: such systems use LOD graphs, mainly DBpedia, as the primary material for the processing.

Seevl4 [START_REF] Passant | dbrec -music recommendations using dbpedia[END_REF] is a band recommender helping the discovery of musical content and artists on Youtube5 thanks to a recommendation algorithm and a faceted browsing functionality. The ranking is processed offline. MORE [START_REF] Di Noia | Linked open data to support content-based recommender systems[END_REF] is a DBpedia-based film recommender accessible in the form of a Facebook6 application 7 . It uses a semantic adaptation of the vector space model called sSVM. The more features two movies share the more similar they are. They can be linked through direct properties (e.g. "subsequentWork") or be the subject of triples having the same property and object ("starring" "Robert de Niro"). The system accepts several films as inputs and retrieves the union of the unitary results. The ranking is also processed offline. These two firsts systems are limited to a defined domains and to defined resource types.

Several cross-domain recommendation systems are based on linked data. In [START_REF] Stankovic | Finding Co-solvers on Twitter , with a Little Help from Linked Data[END_REF] the authors propose to use DBpedia in order to identify new potential collaborators. The objective is to solve industrial problems in an innovative way. A set of entities is first extracted from the description of the targeted problem. Then the hyProximity algorithm tries to find experts coming from others domains that might suggest innovative and unexpected solutions to the initial problem. [START_REF] Stankovic | Finding Co-solvers on Twitter , with a Little Help from Linked Data[END_REF] takes several resources as inputs and performs a cross-domain processing. [START_REF] Kaminskas | Knowledge-based Music Retrieval for Places of Interest[END_REF] proposes a recommendation method starting from a defined domain, with a defined type, which retrieves recommendations in another domain with another defined type. The authors tested it over DBpedia using the scenario of musical recommendations starting from tourists' attractions (e.g. "Vienna State Opera"). The recommendation process is operated offline using a weighted spreading activation algorithm. The positive evaluation of their experimentation confirmed the high potential of Linked data for cross-domain and cross-type recommendations.

Others systems take advantage of linked data semantics to support exploratory search tasks. Aemoo8 [START_REF] Musetti | Aemoo: Exploratory search based on knowledge patterns over the semantic web[END_REF] is an exploratory search system offering a filtered view on the DBpedia graph and giving Wikipedia-based explanations on the resources shown to the user. Yovisto9 [START_REF] Waitelonis | Augmenting Video Search with Linked Open Data[END_REF] is a video platform offering an exploratory search feature that proposes a ranked list of topics related to the search results. It is also noticeable that a major search player, Google10 , launched recently an exploratory search feature ("explore your search", "things not strings" 11 ). This functionality takes advantage of the Google Knowledge Graph 11 semantic network. At the beginning of 2013 it is composed of 570 million objects and more than 18 billion facts. This functionality includes collaborative filtering recommendations ("people also search for"). The exploration is centered on one interest at a time. There is no API available at the moment; the Google Knowledge Graph is not part of the LOD.

The state-of-the-art showed the value of using linked data for knowledge discovery and exploration purpose. As it is a young research area there are many important improvements possible:

- ( 1
)
No work is focused on composite queries solving. The systems that accept several inputs retrieve a combination of the unitary results (e.g. sum). - [START_REF] Basse | Incremental characterization of RDF Triple Stores[END_REF] No work addresses the data freshness issue. Indeed, the linked data datasets are evolving over the time. The continuous update of the data and its impact on the preprocessing is not addressed in the state-of-the-art. -

(3) No work is applied on public SPARQL endpoints. Indeed the preprocessing they use is specific to the knowledge base addressed and often requires a local copy to be performed.

These limitations are mainly due to the preprocessing step used by the aforementioned systems. It is strongly conditioning the type and the range of results that the applications are able to retrieve.

PROPOSITION

On-the-fly linked data processing for composite interest exploration

In this paper we propose an "on-the-fly" processing for linkeddata based exploratory search and we explore more particularly its potential in the context of composite queries. We use the term "on-the-fly" to stress that the method does not need any preprocessing to retrieve the results. It opens new perspectives for exploratory search:

- The absence of preprocessing is a challenge itself due to the complexity of the LOD graphs. Indeed, it requires smart strategies to compute the results on-the-fly starting from a very large and heterogeneous graph. To sum up our requirements we need a method that retrieves relevant results for exploratory search, that is fast but that does not depends on a preprocessing step.

Spreading activation basis

We chose to ground our solution on a spreading activation algorithm for the following reasons. First spreading activation was designed to process semantic networks and proved its value for information and knowledge retrieval purposes. Second it can easily be tuned and integrate various constraints including, for example, semantic sensitive weights. Third it showed efficient response times on large graphs.

Spreading activation is an algorithm family having its roots in cognitive psychology. In 1968, Quillian [START_REF] Quillian | Semantic memory[END_REF] proposed to model the human memory in the form of a semantic network. Then, Collins and Loftus [START_REF] Collins | A spreading activation theory of semantic processing[END_REF] proposed the spreading activation mechanism to simulate the human remembering process. Later it inspired a lot of algorithms in various fields, often uncorrelated with the initial purpose. It was very successful in information and knowledge retrieval. Early and important works include [START_REF] Cohen | Information Retrieval by Constrained Spreading Activation on Semantic Networks[END_REF] and [START_REF] Crestani | Application of Spreading Activation Techniques in Information Retrieval[END_REF]. A lot of variants exist but the core functioning is always the same: first a stimulation value is assigned to one or several node(s) representing the user's interest. Then this value is propagated to neighbor's node(s). The value assigned to the neighbors depends on the settings and heuristics used to reach the algorithm goal. During the next iterations the propagation continues from the newly activated nodes. This process is repeated till a stop condition is reached e.g. maximum number of nodes activated, maximum number of iterations, time limit.

Many researchers applied the spreading activation algorithm to perform information retrieval on RDF graphs. The notable works include [START_REF] Rocha | A Hybrid Approach for Searching in the Semantic Web[END_REF] in which the authors present a hybrid search approach combining a classical search method and an ontology-based weighted spreading activation. [START_REF] Scheir | Improving search on the semantic desktop using associative retrieval techniques[END_REF] uses a spreading activation algorithm to perform information retrieval over a RDF knowledge base. The authors make use of a schema-based similarity measure.

In [START_REF] Lee | An explorative association-based search for the semantic web[END_REF] the authors propose a semantic association search system using two pre-computed weight: a specificity and a generality one.

The LOD also motivated researches on highly fast, robust and scalable algorithms processing RDF data. This was the purpose of the LarKC 14 project: an open-source and distributed semantic computing platform using, among others, spreading activation techniques. In [START_REF] Hs | D2. 4.2 Approximate Activation Spreading -larkc[END_REF] the authors achieved the activation of millions nodes in only few seconds over locally stored LOD graphs. Nevertheless, the approximation strategies proposed are not accurate enough to be used in a knowledge retrieval context. Indeed the method massively activates the nodes, does not rank them and does not exploit finely their semantics.

We propose below a spreading activation adaptation designed to explore the graph by exploiting its semantics on-the-fly.

Algorithm proposition

The algorithm identifies and ranks the results starting from a user interest represented by one or several nodes of the graph (e.g. The Beatles + Ken Loach). At the end of its execution the activation values of the nodes determine their ranks. They are presented to the user in decreasing activation value order. Prior to the algorithm description, we introduce several necessary definitions on RDF triples, (extended from [START_REF] Basse | Incremental characterization of RDF Triple Stores[END_REF]), and the classic graph functions we use: Let KB be the set of all the typing triples asserted and inferred in the triple store (def. 1,2,3).

Definition 4. (Node degree)

+ & is the number of edges involving node (:

+ & / | (, , 1 2 1, , ( 2 |

Definition 5. (Node depth)

3 uses the subsumption schema hierarchy in order to compute the depth of a type . It is used to identify the most precise type(s) available for a node.

S !+3T ! / #1 ; $ !, , 1 2 U 1, , ! 2 ' V W : V 1 *
Here is the formula for a monocentric query i.e. for an interest captured in the form of a unique stimulated resource (e.g. The Beatles). The monocentric formula serves as a basis for the polycentric one used for the composite interest queries: " is the current number of iterations; • X !, " ? 1, is the activation of node ! at iteration " ? 1 for an initial stimulation at ; • !, ", is the stimulation of the node ! at ". The nodes with a positive stimulation are the origin/seeds nodes i.e. here !, ", =1 if ! / and " / 0 and 0 otherwise; • X (, ", is the activation from a neighbor node ( of ! for a propagation origin at iteration "; • degree & returns the degree of the node ( (def. 4); • P !, is a semantic weighting function which takes into account the semantics of the nodes ! and . First, it aims to identify the propagation domain: the nodes are activated or not depending on their types. Second, it encourages the activation of the nodes similar to the origin using others semantics attributes. P i, o is explained in detail below.

Definition 8. (Semantic Spreading Activation algorithm, polycentric query)

The query is polycentric when several nodes of interest are stimulated at a same time. The stimulations correspond to the unitary inputs constituting the composite interest in our case (e.g. The Beatles and Ken Loach). The results of a polycentric query are the product-intersection of several monocentric propagations results (def. 7): X !, " / abX !, ", c/log + _∈M Where:

• O is the set of seeds nodes i.e. the origins of the activations; • X !, " is the aggregated value of the node !, i.e. the product of the activation values of ! for the various propagation spreading at the iteration " (differentiated by their origin ).

The product was chosen instead of the sum in order to avoid a potential disequilibrium introduced by the difference in the monocentric activations distributions. This difference is due to the graph topologies around their respective origin node. The division by log + ) aims to minimize the importance of the highly connected nodes that can be present in the monocentric propagations intersections but not very informative; • X !, ", is the activation value of node ! at iteration " for a spreading activation taking its origin at as in definition 7.

The class-based propagation domain for a polycentric query noted fgh i is the set of types through which the propagation spreads with i the set of all the seeds. To be precise, the propagation spreads through instances which have at least one type present in fgh i . It aims to increase the results quality by focusing the activation distribution on a consistent subset of nodes only. At the same time it improves the performances by narrowing the amount of processed nodes. The propagation domain is identified on-thefly before the propagation starts thanks to the seed nodes neighborhoods' types. In case of polycentric queries it takes into account the neighborhood of all the seeds in order to identify a shared propagation domain.

Definition 9. j)X1 1 is the set of the deepest types t of a given node x according to their 3 (def. 5): Definition 11. fgh i is the classes propagation domain, it constitutes the class-based "semantic pattern" used all along the propagation. A threshold function can be applied to limit the propagation domain size for performance purpose. After this last operation we obtain the classes' propagation domain fgh i i.e. nodes with a type included in fgh i will be activated during the propagation:

j 1 / ; 1, : , 2 j
fgh i / p ; , % Sj i ; % ∑ % r s ,t s [u M m 3 3 v w
In addition to this class-based filtering we use another triple-based measure to improve the algorithm relevance. The more a node is a subject of triples that share a property and an object with triples involving the origin node as a subject, the more it will receive activation:

P !, / x 0 ! y j ! ; fgh i 1 ? |% )) " ! v !, | 3 P! z
Where:

commontriple(i,o)={(i,p,v) KB;∃(o,p,v) KB}

IMPLEMENTATION

This part is dedicated to the implementation of the algorithm in the Discovery Hub application. It describes the general architecture plus the settings and the approximation strategies chosen after analyses. It finally presents the application.

Dataset

We decided to make a first implementation on top of DBpedia. First, DBpedia is cross-domain due to its encyclopedic nature and captures a very heterogeneous knowledge in a single graph. As the stimulation propagates it can potentially reach a very high amount of nodes. The semantic pattern fgh identified by the algorithm helps to manage the graph heterogeneity. We introduce in the next section a sampling process used to apply the algorithm on a limited and selected amount of data only.

Architecture

The algorithm is coded in JAVA. Each time a query is processed a Kgram [START_REF] Corby | The KGRAM abstract machine for knowledge graph querying[END_REF] inference engine instance is created. This local instance manipulates a limited sub-graph replicated from the SPARQL endpoint. Indeed, propagating the activation in the whole DBpedia graph to retrieve the results would very be time consuming and is clearly not compatible with our performance requirements. Thus we transform this processing problem in a local one by performing the spreading activation on a limited subgraph per query. The Kgram instance imports a subpart of DBpedia using INSERT queries. The method used to identify this sub-graph is detailed below. To control and limit the response time we also introduced a triples loading limit (discussed in 4.4.3).

In the case of polycentric queries a two-arc non-oriented SPARQL path query is performed on the endpoint 16 to identify the sub-graph that will be addressed by the spreading activation algorithm. If this query fails we augment the path length. If the queries do not produce any results and the SPARQL endpoint 15 http://dbpedia.org/ontology/wikiPageWikiLink 16 Kgram is able to translate the path queries in their expanded form. This is necessary for some SPARQL endpoints.

starts to refuse them because it is too complex we search oriented paths between the seeds in both directions. This approximation is useful for the queries combining distant nodes. In our actual implementation only the wikiPageWikiLink properties, which are the most current, are taken into account for this step. The wikiPageWikiLink considerably increase the number of connections between the nodes and help to identify more paths. Moreover when two nodes are linked by a well-defined property (e.g. http://dbpedia.org/ontology/) the relation is often mentioned in the Wikipedia plain text. Consequently a corresponding wikiPageWikiLink triple exists. Thus, restraining the path queries to these properties leads to a minor knowledge loss. The path identification can also be replaced by a random walkers-based approach if the SPARQL queries give insufficient results on the endpoint.

The nodes' neighborhoods that have been found by the path query are loaded in increasing degree order till the loading limit is reached. We assume that nodes having a lower degree are more informative about the connections between the seed nodes. To maximize the chance of retrieving results the pivot nodes identified by the SPARQL path query are eligible for activation even if they do not have a type present in fgh i .

select distinct ?x ?y where { service <sparqlEndpoint> { select * where { ?a(<…wikiPageWikiLink>| ^<…wikiPageWikiLink>){0,X} :: $path ?b filter (?a=<resource1> &&?b=<resource2>) } } graph $path {?x ?p ?y} filter(?x!=<resource1> && ?x!=<resource2>) }

Settings

In order to implement our formula and run it over DBpedia, we have to set up some variables: -

The 3 3 v filtering the propagation domain is set to a low value of 0.01. Such value minimizes loss of knowledge.

-

The propagation spreads in both directions i.e. in and out links. As reverse properties are used in RDF, it is preferable to take into account the incoming and outcoming neighbors in order to avoid any loss of knowledge. From a spreading point of view the orientation is arbitrary and depends on a modeling choice.

-

We still need to set the maximum number of iterations. It is discussed in the next part.

We make use of the dcterms:subject properties to compute the % )) " ! v !, value. In DBpedia, the instances are linked to their categories thanks to the % ) : |T( % property. The categories constitute a topic taxonomy which is highly informative on the resources' nature. Thus it constitutes a valuable knowledge for % )) " ! v !, which aim to increase the activation values of nodes having similarities with the activation origin.

Using approximation strategies to control and limit the response time

Two parameters still need to be discussed: the maximum number of iterations and the limit of triples processed by query. As the polycentric queries' results are the product intersection of several monocentric queries we use the analysis we did for monocentric queries' behavior to set these two remaining parameters. We use here an approximation that might require further studies. Indeed for the queries with a single origin node the sampling process we use is different. In the case of monocentric query the graph is loaded iteratively along the iterations regarding the nodes' activation values, following the spreading activation logic. At the beginning the seed node's neighborhood (filtered by classes' propagation domain) is loaded and a first round of propagation is performed. During the next activations the top activated nodes' neighborhoods are loaded into the Kgram instance till the loading limit is reached. Considering the amount of nodes processed during the analysis we reasonably think that the same study with the polycentric loading process would lead to similar results.

Analysis method

To reduce the computational cost of the algorithm behavior study we ran it on a DBpedia sample. According to [START_REF] Leskovec | Sampling from large graphs[END_REF] the best sampling method to preserve a large graph's properties is a random walker. We followed this recommendation and computed a sample17 using this method.

To compare the results lists we obtained with various configurations we notably used the Kendall's tau-b coefficient } O [START_REF] Kendall | Rank Correlation Methods[END_REF]. } O is a rank correlation measure reflecting the concordance of two ranked lists where:

} O / ∑ +"$1 ~1& ' +"$ ~ & ' •& € j • ~j' j • ~jƒ , where j • / " " ~1 2 , j ' / Z † † ~1 2 , and
j ƒ / Z | K | K ~1 2 K †
and the † is the number of tied 1 value in the ‡th group of tied 1 values, | K is the number of tied values in the vth group of tied values, " is the number of observation and +" ˆ :

+" ˆ / k 1 ! ˆ‰ 0 0 ! ˆ/ 0 ~1 ! ˆ 0 n
} O is comprised between -1 and 1: -1 means a total discordance and 1 a total concordance. Thanks to it we observe the similarity of the rankings from iteration to another. It allows observing the algorithm convergence. Our configuration for tests was:

-Application server: 8 proc Intel Xeon CPU E5540 @2.53GHz 48 Go RAM -SPARQL endpoint: 2 cores Intel Xeon CPU X7550 @2.00GHz 16Go RAM

Setting the maximum number of iterations

As spreading activation is an iterative algorithm we have to set a maximum number of iterations. To determine the best settings in our context we observed the algorithm convergence over DBpedia graph. We performed an analysis on 100.000 queries using the sample nodes as inputs. We counted the number of shared results

and measured the Kendall-Tau correlation coefficient between the top 100 results list at iteration n and the top 100 results list at iteration n+1 for the first hundred iterations. The Kendall-Tau is calculated considering the shared results in the two lists. The triple loading limit is not studied yet and is experimentally set to 10.000 for this first analysis.

For clarity purpose the figure 1 shows only the twenty first iterations, after 16 iterations the percentage of average shared results exceeds 99% and the average } O is superior to 0.99. We observe that the top results are quickly converging. The table 1 focuses on the } O variation along the iterations. It is clear that the results change very slowly after few iterations. In others words it becomes very expensive to continue the process after few iterations regarding the very slow evolution of results. We decided to fix the maximum pulse at 6. A propagation visualization video using the Semantic Web Import plug-in for Gephi 18 has been published 19 . The fast convergence is observable on the video.

Setting the triples loading limit

To control the size of the sub-graph processed and consequently the response time we introduce a maximum limit of triples imported per query. When the imported graph overtakes the triples limit no more neighborhoods are loaded anymore. We processed again 100.000 queries using the sample nodes as inputs.

Each query was executed ten times with a limit ranging from 2000 to 20000 triples (step of 2000). The figure 2 shows that the algorithm response time is linear regarding the triples loading limit.

Figure 2: response time regarding the loading limits for monocentric queries

The figure 3 shows the top 100 results Kendall-Tau variation from a loading limit to another, 2000 by 2000. It is clearly observable that after 6000 the convergence starts to be very slow. Thus we chose 6000 as loading limit.

Polycentric behavior analysis

Then we wanted to observe if the polycentric results were specific to the inputs combination. We processed again 100.000 nodes of our sample. For each of them we selected randomly 2 nodes in the 2 arc-max neighbourhood thanks to a random walker. We processed 3 queries: the sample's node only (monocentric) and two polycentric queries by adding each time one of the randomly selected neighbours. The figure 4 shows a histogram of the top 100 shared results percentage between the monocentric and the polycentric queries results. The figure 5 shows it for the 2 polycentric queries amongst themselves. These 2 histograms both point out that the results list similarities are very low. In others words the results are highly specific to the input(s).

Figure 4: Shared top 100 results histogram between the monocentric and polycentric queries results

Figure 5: Shared top 100 results histograms between the first and second polycentric queries results

The response time histogram of polycentric queries (figure 6) shows that a majority of queries are processed in less than 10 seconds. Overall the response time of the polycentric queries is superior to the monocentric ones (figure 2) due to the path queries costs. It is an exploratory search engine helps the user to discover things he might like or might be interested in. It aims to widen his knowledge and cultural horizons. It proposes many redirections to tierce platforms to extend the search process. The third-party services are proposed according to the type of the considered result e.g. music service for a Band or tourism platform for a Museum. Several demonstration videos are available online 21 .

To enter the queries the user can start with an entity search thanks to a DBpedia lookup 22 or use an import of third-party profile information e.g. Facebook likes. In this last case an entity recognition is performed using the rdfs:label properties and the DBpedia lookup. The composite queries are encouraged thanks to the "search box" in which the user can drag and drop items all along his navigation (figure 7). He can pick resources of interest on the homepage, the results pages or in his profile for instance.

The composition is limited today to 4 resources.

The navigation in the results space is facilitated thanks to various facets and filters allowing a deep exploration. The classes in the When a user is interested or intrigued by an item, he can ask for various explanations thanks to three dedicated features. These features are mandatory for composite heterogeneous queries when some non-trivial and unattended results are retrieved. They need to be explained to receive the user's approval. The following explanatory features are presented in a video 23 :

-A feature showing the common properties that share the results with the query-resource(s). -A feature identifying and highlighting the crossed references between the result and the query-resources in the Wikipedia pages (figure 8).

-

A feature showing the connections between the results and the query-resources in a graph format (figure 9). When the 23 http://semreco.inria.fr/hub/videos/ user goes over a node its abstract appears on the left. It is possible to get even more information with the "see links in Wikipedia" functionality that highlights the graph neighbors in the Wikipedia pages. This graph is built on demand thanks to a SPARQL path query. It is often instantaneous, require few seconds when the graph is dense.

EVALUATION

As mentioned in [START_REF] Kules | Creating exploratory tasks for a faceted search interface[END_REF] the research initiatives in the exploratory search domain suffer from the lack of evaluation standardization. It is even more the case for our composite interest objective as there is no clear baseline available 24 . We wanted to verify the following hypothesizes:

• Hypothesis 1: the composite queries results interest the user. • Hypothesis 2: some results are unattended; they offer a high discovery potential. • Hypothesis 3: the explanatory features help the user to understand the link between the query-resources and the results; thus they support efficiently the results space understanding.

This evaluation was executed using an adaptation of the Discovery Hub interface. The users had to judge 2 results lists of the top 10 algorithm results. Each list was generated starting from 2 of their individual Facebook likes randomly combined. In this way we wanted to simulate a composite interest query that the user was susceptible to enter in the system. The result is unexpected: strongly agree, agree, disagree, strongly disagree.

Concerning the sample characteristics, the survey was filled by 12 persons: 3 females, 9 males from various backgrounds, mainly people who asked an access to the Discovery Hub beta. In the following results 0 corresponds to strongly disagree, 1 to disagree, 2 to agree, 3 to strongly agree for relevance score and discovery scores (respectively question 1 and 2).

To verify the hypothesis 1, we observed the relevance score (question 1). The average relevance score was 1.65, with a standard deviation of 0.94. The figure 10 shows the average relevance scores per query histogram. 71% of queries received a relevance score over the mean (1.5). Thus the hypothesis 1 is verified. It is noticeable that one query received the worst score possible; all its results were rated 0. Its seeds were very distant: Samuel L. Jackson and Grooveshark.

To verify the hypothesis 2, we observed the unexpectedness score (question 2). The average unexpectedness score was 1.90 with a standard deviation of 1. The figure 11 shows the average unexpectedness scores histogram. 58.33% of queries received an average score over the mean (1.5). Thus, the hypothesis 2 is verified. Concerning the discovery potential it is also interesting to observe the recovery between relevance and unexpectedness: -61.6% of the results were rated as strongly relevant or relevant by the participants. -65% of the results were rated as strongly unexpected or unexpected. -35.42% of the results were rated both as strongly relevant or relevant and strongly unexpected or unexpected.

Then we asked the participants to give their opinion about the three explanatory features. For the 3 features we asked "the feature X helped me understand the relation between the result and my interests and to make a choice?" and one more general question "overall, I feel that these three features can help me to make new discoveries". 0 corresponds to strongly disagree, 1 to disagree, 2 to agree and 3 to strongly agree (figure 12). The graph-based explanatory feature which was designed specifically to understand the non-trivial connections between several resources received a very high average score (mean m = 2.92). It is particularly adapted to results explanations for the polycentric queries results as they often unveil indirect links. The Wikipediabased explanatory feature received an average score over the mean (m = 1.83). Participants liked the possibility to use it from the graph explanation. Finally the common property feature received an average score close the mean (m = 1.58). It is often impossible to find common properties between the results and all the different seed nodes constituting the composite interest. This feature is more efficient in the case of monocentric queries. The more general question received the high average score of 2.67 and confirms the interest of these explanatory features to increase the discovery potential of the application. The hypothesis 3 is verified.

Figure 12: users' opinions about the explanatory features

Finally we asked the participants to rank the 3 functionalities regarding their perceived efficiency in terms of results explanations. The rankings confirmed the previous results. The common property feature was perceived as the less efficient (ranked first: 0%, second: 72.7%, third: 27.3%). The Wikipediabased feature was more appreciated (54.5%, 27.3%, and 18.2%). Finally the graph-based received a very large approval (45.45%, 45.45%, and 9%). Nevertheless, the results are not totally uniforms and confirm the interest to propose various strategies.

CONCLUSION

In this paper, we have presented a method for processing linked data graph for exploratory search purposes. It is composed of a semantic spreading activation algorithm associated to a sampling process. Its main particularity regarding the state-of-the-art is to not need any preprocessing step to compute the results. We also detailed its implementation in the Discovery Hub application. We presented extensive analysis of its behavior that helped us to set the main parameters of the implementation. This article was especially focused on composite interests (interests captured in the form of several unitary resources) explorations thanks to polycentric spreading activation. During our analysis a majority of the polycentric queries results were specific to the nodes combination used as inputs. Overall the queries required few seconds to be processed. The participants of the evaluation mostly rated the results as relevant or unexpected. More than one third of the results was rated as both relevant and unexpected. It is encouraging as it reflects a high discovery potential for the application. The evaluation notably showed the high efficiency of the graph-based and Wikipedia-based explanatory features for explaining the polycentric queries results.

We plan to extend this work in several directions. An interesting possibility offered by the architecture is to modify the semantics embedded in the propagation in order to support personalization and contextualization functions, using for example the property semantics. Another possible research direction is to query several SPARQL endpoints at the same times (e.g. French, Spanish, and Italian DBpedias), build one meta-lingual graph and retrieve richer results. Finally we will evaluate the full Discovery Hub system thanks to a qualitative evaluation on a large set of users. We still need to validate the usefulness of applying the algorithm in the context of exploratory search with the interactive dimension. This evaluation will also allows us to determine the quality of the navigational items we propose like the facets, filters and to identify some browsing patterns.

Definition 1 .

 1 (RDF triple, RDF graph). Given U a set of URI, L a set of plain and typing Literal and B a set of blank nodes. An RDF triple is a 3-tuple , , . s is the node subject of the RDF triple, p the predicate of the triple and o the node object of the triple. An RDF graph is a set of RDF triples. Definition 2.(RDF typing triple, RDF non-typing triple.) An RDF typing triple is a 3-tuple , , : . An RDF non-typing triple is a 3-tuple , , \ : . Definition 3. (Infered RDF triples, IRDF triples) Infered RDF triples of an RDF non-typing triple s, p, o is the set of RDF triples , ', 1 ( )* obtained after RDFS closure. To ensure that each node has at least one type we give by default the type rdf:resource to each node.

Figure 1 :

 1 Figure 1: Percentage of shared results and Š ‹ from one iteration to another, top 100 results

Figure 3 :

 3 Figure 3: Š ‹ from one loading limit to another (step: 2000), top 100 results

Figure 6 : polycentric queries response time histogram in ms 4 . 6

 646 Figure 6: polycentric queries response time histogram in ms 4.6 Discovery Hub: an operational prototype Discovery Hub 20 implements the algorithm and the sampling process previously described. It uses DBpedia as knowledge base.It is an exploratory search engine helps the user to discover things he might like or might be interested in. It aims to widen his knowledge and cultural horizons. It proposes many redirections to tierce platforms to extend the search process. The third-party services are proposed according to the type of the considered result e.g. music service for a Band or tourism platform for a Museum. Several demonstration videos are available online21 .

  20 http://semreco.inria.fr/hub/ 21 http://semreco.inria.fr/hub/videos/ 22 http://wiki.dbpedia.org/lookup/ used as navigational items to build the facets e.g. Band, Film. 40 results at maximum are presented by facet on the actual prototype. Discovery Hub also proposes a "top" un-faceted results list showing the 40 most activated resources without any condition on their types.

Figure 7 :

 7 Figure 7: The user is currently dragging The Beatles in the "search box" to complete Ken Loach and launch the query A set of filters per facet is proposed using the DBpedia categories. These filters are retrieved thanks to the query below. For instance on the figure 9 the user filtered the Film facet's results with "2000s comedy-drama films". We put in evidence the categories (i.e. the filters) having a low degree by presenting them with clearer colors. It aims to drive the user in unexpected browsing paths and thus augments the discovery potential of the application. The filters have a cumulative effect. select ?p where { service <sparqlEndpoint> { select ?p (count(?x) as ?count) where { ?x <http://purl.org/dc/terms/subject> ?p filter( ?x = result1Facet1 || ?x= result2Facet1 || ?x = result3Facet1 … ) } order by desc (?count) } filter(?count>1) } To give a real example of results, the composite query The Beatles + Ken Loach provides the following facets (or fgh): Album, Band, Film, Musical Artist, Music Genre, Person, Radio Station, Single, Television show. The Film facet proposes, among others, these filters: British drama films, films associated with the Beatles, films directed by Ken Loach, films set in Liverpool.

Figure 8 :Figure 9 :

 89 Figure 8: Wikipedia-based explanation for "Nowhere Boy"

Figure 10 :Figure 11 :

 1011 Figure 10: average relevance score per query histogram

  Where type t is a class in the hierarchy of the RDFS schema and St is a direct super class of t in this hierarchy before any transitive closure is computed.

	3 depth / 4	3 t / 0 / Τ the root of the hierarchy, / 1 ? @!" A B ; D,EFG:AHIJKLAAMG,A B NO ! 3 P!	3 D	Q
	Definition 6. (Node neighborhood) S !+3T ! is the set of neighbors of node i in the linked data graph:

  It enables cross-domain and cross-type processing and is consequently adapted to our objective of solving composite, potentially heterogeneous, interest queries. Second it can support users' experiments as it contains common-knowledge items such as films or music artists.As we needed to query the SPARQL endpoint millions times during the benchmark we set up a local version of DBpedia. Our version contains the wikiPageWikilink15 triples. The wikiPageWikiLink relations indicate that a hypertext link exists in Wikipedia between the 2 resources, often in the core of articles, but that the semantics of the relation was not captured. It provides a vast amount of extra-links which can increase the relevance of the connectionist algorithms like spreading activation ones.

As previously mentioned the main difficulty to perform spreading activation over a LOD source is due to the graph complexity. Here are some characteristics of DBpedia 3.7 dataset including wikiPageWikiLink triples: -Graph size: 3.64 million nodes, 270 million triples. -Graph heterogeneity: 319 classes in the DBpedia ontology.

Table 1 . Variation of Š ‹ for iterations n and n+1

 1

	It. n	1	2	3	4	5	6	7	8
	} O	.73 .11 .08 .018 .013 .006 .006 .002

http://linkeddata.org

http://wikipedia.org

http://www.w3.org/DesignIssues/LinkedData.html

http://seevl.net/

http://youtube.com

http://www.facebook.com

http://apps.facebook.com/new-more/

http://wit.istc.cnr.it/aemoo

http://www.yovisto.com/

http://www.google.com

www.google.com/insidesearch/features/search/knowledge.html

http://blog.dbpedia.org/2012/08/06/

http://live.dbpedia.org

http://www.larkc.eu/

The code and a 546.000 nodes sample are publicly accessible for reuse: http://semreco.inria.fr/hub/tools

http://wiki.gephi.org/index.php/SemanticWebImport

http://semreco.inria.fr/hub/videos/

We propose an API for comparison purpose.

ACKNOWLEDGMENTS

We thank Julien Cojan (SPARQL endpoint), Damien Legrand (web-design and front-end development), Alain Giboin and Gessica Puri (evaluations) for their precious help.


Nicolas Marie
email: nicolas.marie@inria.fr

Fabien Gandon
email: fabien.gandon@inria.fr

Myriam Ribière

Florentin Rodio

Discovery Hub: on-the-fly linked data exploratory search

Keywords: G.2.2 [Mathematics of Computing]: Graph Theory -Graph algorithms; E.1 [Data]: Data Structures -Graphs and networks Algorithms, experimentation semantic web, linked data, DBpedia, semantic spreading activation, exploratory search system, discovery engine

Exploratory search systems help users learn or investigate a topic. The richness of the linked open data can be used to assist this task. We present a method that selects and ranks linked data resources that are semantically related to the user's interest. The objective is to focus the user's attention on a meaningful subset of highly informative resources. We extended spreading activation to typed graphs and coupled it with a graph sampling technique. The results selection and ranking is performed on-the-fly and doesn't require pre-processing. This allows addressing remote SPARQL endpoints. We describe first implementation on top of DBpedia. It is used by the Discovery Hub exploratory search system to select interesting resources, to support faceted browsing of the results, to provide explanations and to offer redirections to third-party services. Results of a user evaluation conclude the article.

INTRODUCTION

Exploratory search is information-seeking in an open-ended context and following an opportunistic, iterative, and multitactical process [START_REF] White Ryen | Exploratory Search: Beyond the Query-Response Paradigm[END_REF]. [START_REF] Marchionini | Exploratory search: From finding to understanding[END_REF] makes a distinction between lookup and exploratory search activities. The lookup tasks are performed to satisfy precise information needs (e.g. known item search, fact checking). In this case the user's query keywords are welldefined. Exploratory search refers to cognitive consuming search tasks such as learning or topic investigation. In that case the information need is fuzzy: the keywords are a-priori unknown, vague and evolving. The actual search engines are very efficient for lookup queries but less for exploratory search due to their keyword-oriented paradigm. There is a need to complete the existing solutions with systems or functionalities optimized for exploratory search. Some of these systems make use of formal knowledge sources including the linked open data datasets. Linked data-based approaches involve the use of (1) semantic web models, formalisms (RDF/S,OWL) and published schemas [START_REF] Rl Brennan | Generalizability Theory[END_REF] Linked open data cloud 1 (LOD) interconnecting public datasets published using this standards. Among all the LOD datasets DBpedia [START_REF] Auer | DBpedia, A nucleus for a web of open data[END_REF] is the most central one in the LOD cloud and results from the extraction of data from Wikipedia 2 .

We want to ease the exploration of a topic of interest by suggesting related and informative resources. In this paper we propose a novel method for performing this selection in linked data datasets. It relies on extending semantic spreading activation to the typed graphs of the semantic web formalisms and combining it with a sampling technique to compute result "onthe-fly" i.e. without any preprocessing. It allows supporting exploratory search on remote data using their SPARQL endpoints and let users influence the results by specifying their queries or adding serendipity to the process.

The research questions addressed in this paper are the following:

(1) in a dense and heterogeneous linked data graph, how to select and rank a meaningful subset of resources related to the user's interest? [START_REF] Rl Brennan | Generalizability Theory[END_REF] As linked data are distributed, how to perform this selection on remote LOD sources? (3) On the interface side, how to present and explain the selection to the user? Section 2 compares related works. Section 3 details our formal extension of spreading activation to typed graphs. Section 4 describes the implementation and introduces the graph sampling technique we couple to the algorithm. Then it details the algorithm behavior over DBpedia and its configuration. The section 5 presents the Discovery Hub application that makes use of the method and presents the results in an interface optimized for exploratory search. Section 6 presents the hypotheses, protocols and the results of a complete user's evaluations.

RELATED WORK

In the field of exploratory search, the linked-data based faceted search systems have proven to be efficient: important examples are [START_REF] Harth | Visinav: A system for visual search and navigation on web data[END_REF], [START_REF] Heim | gFacet: A Browser for the Web of Data[END_REF] and [START_REF] Huynh | Parallax and companion: set-based browsing for the data web[END_REF]. These systems present a view on the data according to the set of facets currently activated. One drawback of these approaches is that it sometimes necessitates complex interaction sequences that are not adapted to casual users [START_REF] Heim | gFacet: A Browser for the Web of Data[END_REF].

A different or complementary approach is to directly suggest resources that are strongly related to the user's interest using a relatedness or similarity measure. The aim is to ease the exploratory search tasks by focusing user's attention on resources and associations that convey a lot of knowledge. It can also unveil unknown and unexpected results. In the past 3 years several research initiatives demonstrated the value of using DBpedia to Seevl [START_REF] Passant | dbrec -music recommendations using dbpedia[END_REF] is a DBpedia-based band recommender for Youtube based on the DBrec algorithm. The DBrec algorithm ranks the similar bands according to shared direct and indirect properties. The ranking is processed offline and stored in RDF. MORE [START_REF] Di Noia | Linked open data to support content-based recommender systems[END_REF] is a DBpedia-based film recommender. It uses a semantic adaptation of the vector space model called sVSM . The more features two movies share the more similar they are. The ranking is processed offline. [START_REF] Kaminskas | Knowledge-based Music Retrieval for Places of Interest[END_REF] proposed a method to perform crossrecommendations on at least two chosen domains (e.g. recommending musical artists starting from tourists' attractions). The recommendation computation is operated offline and uses a weighted spreading activation algorithm. The positive results of the users' evaluation confirm the potential of DBpedia to perform cross-domain and cross-type recommendations.

Yovisto [START_REF] Waitelonis | Augmenting Video Search with Linked Open Data[END_REF] is an academic video platform providing an exploratory search feature. It proposes a ranked list of related topics besides the search results. The selection and the ranking of the resources (corresponding to topics) are computed offline thanks to a set of eleven heuristics. A user evaluation showed that the exploratory search feature significantly improved the search experience. Aemoo [START_REF] Musetti | Aemoo: Exploratory search based on knowledge patterns over the semantic web[END_REF] is a DBpedia-based exploratory search system making use of Encyclopedic Knowledge Patterns (EKP) which identify typical classes used to describe instances of a specific class. Starting from a resource of interest, Aemoo presents its neighborhood filtered with its corresponding EKP or inverted EKP using the curiosity function. In [START_REF] Mirizzi | From exploratory search to web search and back[END_REF] the authors present the Lookup Explore Discover exploratory search system. The application recommends a set of tags that are strongly related to the named entities recognized in the user query (e.g. RDFa, micro-data for the microformat query).The user is assisted by the tags during the exploration and can use it to refine the query.

In table 1, we observe that the approaches all use an offline preprocessing step. It considerably limits the type and the range of retrieved results. It narrows the range of information needs that can be supported by the applications. Such approaches are then sufficient for building domain-specific applications but do not fully exploit the potential of linked data for exploratory search:

-They give results for a subset of chosen resources only ([6][11][19] [START_REF] Passant | dbrec -music recommendations using dbpedia[END_REF]): there is only a limited sub-set of resources that are pre-processed and stored locally. -They exclude the user from the results computation and propose a fixed ranking scheme ([19][20][21] [START_REF] Waitelonis | Augmenting Video Search with Linked Open Data[END_REF]). The user might want to influence the recommendations/results.

-They compute the results by addressing only one local dataset replicated from public LOD sources. They might also retrieve outdated results: the preprocessing needs to be performed regularly if the knowledge base evolves. This is an issue for some uses such as data journalism.

PROPOSITION

On-the-fly linked data based exploration

We propose a method that selects and ranks on-the-fly a meaningful subset of resources in a targeted LOD dataset:

-Every resource available in the targeted dataset can constitute a potential topic for exploration/discovery, not only a type or domain-dependant subset. -As the results are not pre-computed the users can influence them by tuning several parameters (e.g. for advanced search, customization, contextualization). -It is possible to address remote SPARQL endpoints to retrieve results. By querying the public SPARQL endpoints and not a local replica we also ensure the freshest data.

The method has to be sufficiently fast to be performed on-the-fly (in few seconds maximum). To reach this goal we propose a semantic spreading activation algorithm and a sampling technique that makes it applicable on remote LOD graphs.

Spreading activation basis

Spreading activation comes from cognitive psychology and works related to the memory [START_REF] Collins | A spreading activation theory of semantic processing[END_REF]. Later it inspired a lot of algorithms in various fields and was successfully employed in information retrieval. Early and important works include [START_REF] Cohen | Information Retrieval by Constrained Spreading Activation on Semantic Networks[END_REF] and [START_REF] Crestani | Application of Spreading Activation Techniques in Information Retrieval[END_REF].

The core functioning is always the same: first a stimulation value is assigned to one or several node(s) of interest. Then this value is propagated to the neighbor's node(s). The value assigned to neighbors depends on the algorithm purpose and settings. During the next iterations the propagation continues from newly activated nodes. This process is repeated till a stop condition is reached e.g. maximum number of nodes activated or iterations.

The spreading activation technique was applied over RDF for creating context-inference models, extending and refining ontologies, predicting social annotations [START_REF] Rodríguez | An Extensible Framework to Sort out Nodes in Graph-Based Structures Powered by the Spreading Activation Technique: The ONTOSPREAD Approach[END_REF]. It was also studied in the context of semantic search. [START_REF] Rocha | A Hybrid Approach for Searching in the Semantic Web[END_REF] proposes a hybrid search approach combining a classical keyword-based search method with a spreading activation over a domain ontology. [START_REF] Scheir | Improving search on the semantic desktop using associative retrieval techniques[END_REF] is combining concepts-based similarity, text-based similarity and spreading activation for document retrieval. [START_REF] Kinsella | Navigating and annotating semantically-enabled networks of people and associated objects[END_REF] retrieves content associated to one or several resources in a socio-semantic network. [START_REF] Kules | Users can change their web search tactics: Design guidelines for categorized overviews[END_REF] performs semantic association based search over an ontology thanks to specificity and generality measures. [START_REF] Freitas | Querying Linked Data using semantic relatedness: A vocabulary independent approach[END_REF] answers natural language queries with DBpedia.

These works rely on a weight mapping step applied on nodes or properties using local and global graph measures [7][15][22] [START_REF] Scheir | Improving search on the semantic desktop using associative retrieval techniques[END_REF] or manual intervention [START_REF] Kinsella | Navigating and annotating semantically-enabled networks of people and associated objects[END_REF]. Our approach differs as the propagation controlling pattern is a type-based semantic weight that is function of the stimulated origin node. In other words the origin node semantic pattern plays a significant role in the distribution of activation even in "distant" parts of the graph. It is particularly adapted to dense and strongly typed graphs that are common in the LOD context. Indeed in linked data sources there is a strong need to constraint the propagation in order to target relevant part of the graph only and minimize the amount of data processed. In our approach the types of the nodes is a fundamental criteria taken in account for the propagation distribution. The fact the semantic pattern can be easily computed on the fly is leveraged in our implementation to address remote LOD data sources (section 4).

Formal proposition

The algorithm presented below aims to explore the graph obtained from one or more SPARQL end-points of the linked data cloud. It identifies a meaningful of resources strongly related to the user's interest (e.g. The Rolling Stones). Then these results are presented and explained to the user through an interface optimized for exploratory search (section 5).

The graph semantics is exploited thanks to a weight that is function of the origin node. Where:

o is the origin node i.e. the instance of interest initially stimulated (e.g. The Rolling Stones); i is an arbitrary instance node of the graph; j iterates over the neighbors of i ; n is the current number of iterations; -, , is the activation of node at iteration for an initial stimulation at ; -, , is the stimulation value of the node at , the value that is redistributed to its neighbor's. The node having a positive stimulation at initial time is the origin/seed node i.e. here , , =1 if and ; -, , is the activation from a neighbor node of for a propagation origin at iteration ; degree returns the degree of the node (def. 3); -, is a semantic weighting function which takes into account the semantics of the nodes and . First, it aims to identify the propagation domain: the nodes are activated or not depending on their types (def. 9). Second, it encourages the activation of the nodes that are similar to the origin using others semantics attributes (def.10). i, o is explained below.

The class-based propagation domain

is the set of types through which the propagation spreads. To be precise, the propagation spreads through all the nodes which have at least one type present in . It aims to increase the results relevance by focusing the activation distribution on a consistent subset of nodes and limit the amount of data processed. The propagation domain is identified on run-time before the propagation starts and is based on types of the origin node's neighbors.

Definition 7.

is the set of the deepest types t of a given node x according to their (def. is the classes propagation domain, it constitutes the class-based "semantic pattern" used all along the propagation. A threshold-based filtering can be applied to exclude the less prevalent types present in . This threshold can be used to restrains the propagation domain size for performance purpose. After this last operation we obtain the classes' propagation domain i.e. the nodes with a type included in and that will be activated during the propagation. It allows limiting the propagation to a subset of types that are consistent with the activation origin:

; , ∈ ; ∑ , ∈ Definition 10.
, is an additional measure that aims to improve the algorithm relevance by favoring activation of node having similar properties with the origin . It is a triplebased comparison: the more a node is a subject of triples that share a property p and an object v with triples involving the origin node as a subject, the more it will receive activation: Where r is the level of serendipity, comprised between 0 and 1, and produces a random value between 0 and 1.

, ∈ ; ∈ | , | Where

IMPLEMENTATION

In this section we present the first implementation of the algorithm using DBpedia. We notably detail the sampling technique that is a key component. It is coupled with the spreading activation algorithm and makes it applicable "on-thefly" over remote LOD datasets using their SPARQL endpoints.

Dataset

We decided to set up a first implementation on top of DBpedia due to the amount of topics it covers. It also offers an interesting ground for user evaluations as it contains common-knowledge items such as films or musical artists.

For comparative purpose we used the DBpedia 3.

Architecture

The algorithm is coded in JAVA. Each time a query is processed a Kgram4 inference engine instance is created. This local instance imports a limited sub-graph sampled from the targeted SPARQL endpoint. In other words, we apply the spreading activation algorithm only on a limited and defined sub-graph per query. The Kgram instance iteratively imports subparts of DBpedia using INSERT queries and SPARQL <service>.

The samples are imported iteratively according to the nodes activation values. At the beginning the neighborhood of the origin node (filtered by its CPD) is loaded and a first round of propagation is performed. During the next iterations the neighborhoods of the top activated nodes are imported into the Kgram instance till a maximum limit of triples is reached (such limit is discussed further).

Settings

We set up some variables in order to implement our formula:

-The propagation spreads in both directions to take into account incoming and outcoming neighbors. From a spreading activation point of view the orientation is arbitrary and depends on a modeling choice. -The filtering the propagation domain is set to a low value of 0.01, as we do not want to restrain too much the in our exploratory search context.

-In DBpedia, instances are linked to their category through the : 5 property. We make use of this property to compute , . The categories constitute a topic taxonomy which is very informative on the resources. It constitutes a valuable basis for computing , . The nodes reached by the propagation and belonging to the same categories as the origin receive a greater amount of activation.

-The maximum number of iterations has still to be fixed and is discussed further.

Limiting the response time

At this point two parameters still need to be discussed: (1) the maximum number of iterations and (2) the size of the sample imported. To set up these variables we observed the behavior of the algorithm over DBpedia. We processed a large amount of queries and analyzed the results lists variations along the iterations and according to the sample size. We needed to know (1) if the results converge quickly and ( 2) what is the impact of the sample size on the retrieved result lists. For the system to remain usable, the response time cannot exceed a few seconds.

Analysis method

According to [START_REF] Leskovec | Sampling from large graphs[END_REF] the best method to select a representative subset of a large graph is a random walk. We followed these recommendations and computed a 100 000 nodes sample from DBpedia. To compare the rankings of the results lists obtained with various configurations we used the Kendall's tau-b coefficient . is comprised between -1 and 1 where -1 means a total rank discordance and 1 a total concordance [START_REF] Kendall | Rank Correlation Methods[END_REF]. Our configuration for the tests was an application server (8 Intel Xeons CPU E5540 @2.53GHz 48 Go RAM) and a SPARQL endpoint (2 Intel Xeons CPU X7550 @2.00GHz 16Go RAM)

Setting the maximum number of iterations

As spreading activation is an iterative algorithm we have to set a stop condition. To determine this parameter we studied the algorithm convergence on DBpedia data. We processed 100 000 queries taking as inputs the nodes of the DBpedia subset. We measured the correlation coefficient and the number of common results between the top 100 results at iteration and at iteration ( being comprised between 1 and 99). The Kendall-Tau is calculated by considering the common results in the two lists. The triples loaded limit has not been studied yet and is experimentally fixed to 10.000.

For clarity purpose the figure 1 shows only the twenty first iterations, after 16 iterations the percentage of average shared results exceeds 99% and the average is superior to 0.99 from one iteration to another. It is visible that the results change very slowly after a few iterations. Thus we decided to fix the maximum pulse at 6 to obtain a good trade-off between response time and results stability. A propagation visualization video using Web Import plugin for Gephi6 has been published 7 .

Figure 1:

and percentage of shared results from one iteration to another, top 100 results

Setting the triples loading limit

In order to control the size of the sub-graph imported and consequently the response time, we introduce a limit of triples loaded per query. Along the iterations the neighbors of the most activated nodes are imported in the Kgram instance. When the imported graph overtakes the triples limit, no more neighborhoods of nodes are imported, the sample is considered complete. We also introduce an experimental loading threshold of 0.1 i.e. nodes having an activation value under 0.1 are not taken into account during the loading process. This threshold allows distributing the loading process among the iterations and reaching distant nodes. In order to set this limit we used again the DBpedia subset. For each node we processed 10 times the query with a loading limit ranging from 2000 to 20000 (by steps of 2000). It allowed comparing the variations of the response time as well as the changes in the top 100 results list according to the triples limit. We wanted to observe the cost of importing more triples and its impact on the results.

The figure 2 shows that the algorithm response time is linear to the triples loading limit. It also presents the top 100 results Kendall-Tau variation from one loading limit to another (2000 by 2000). After 6000 triples the top results evolve slowly from one sample size to another. In other words, loading more triples does not impact very much the top results list compared to its cost. The figure 3 shows the response times for the 6000 triples loading limit. A large proportion of queries are processed in less than 4 seconds with this configuration.

Multilingualism

Being able to address remote SPARQL endpoint is very interesting to deal with the LOD in general but also in the context of DBpedia as more and more local chapters emerge 8 . These chapters are related to a language and considerably differ in what they describe and how it is described. In august 2012 there were already 20.8 million of resources described in the local chapters but only 10.5 million overlaps with concepts from the English DBpedia 9 . The interest of enabling exploratory search on these knowledge bases is obvious.

We tested the response time of our method when applied to the French and Italian SPARQL endpoints. We run 10000 queries corresponding to the 10000 first resources of the DBpedia subset that are described in the English, French and Italian versions of DBpedia. The equivalence among resources in the different DBpedia chapters is declared thanks to the wikiPageInterLanguageLink properties. We applied the same parameters as described above for the English-speaking version. The response times were satisfying for all the SPARQL endpoints: an average of 2.05, 1.63 and 1.99 seconds for respectively the English, French and Italian endpoints 10 .

DISCOVERY HUB PROTOTYPE

Discovery Hub 11 (Figure 4) uses the algorithm and the sampling method previously described to suggest resources of interest. It is an exploratory search engine which helps the user to discover things he might like or might be interested in starting from one or 8 http://dbpedia.org/internationalization 9 http://blog.dbpedia.org/2012/08/06 10 Will be fully available in the V2, currently in development

MS

several topics of interest. It proposes redirections to third-party platforms for extending the search process: services are proposed according to the type of the resource e.g. music services for a Band or tourism platforms for a Museum. Online videos are available 12 .

The exploration starts after selecting the topic of interest thanks to a DBpedia lookup 13 . Then the algorithm proposes a set of highly related and informative resources (section 3 and 4). Discovery Hub enables faceted browsing over these results. The classes identified in are used to build the facets proposed on the left (e.g. Album, Band, Film). A set of 20 filters (or sub-facets) is also proposed per facet. For instance the filters "american rock music film" and "films directed by Martin Scorsese" are proposed in the Film facet of The Rolling Stones results. These filters correspond to prevalent DBpedia categories that have been identified in the facet's results. The filters having a lower degree are put in evidence and presented with clearer colors. It aims to drive the user in unexpected browsing paths and consequently augments the discovery potential of the application.

Explaining the results is fundamental in our approach. The resources selection is valuable only if users can deeply understand their relation to their initial interest (query). When a user is interested or intrigued by an item he can use 3 different explanatory features 14 . The first one shows the common properties shared by the query-resource and the result. The second one identifies and highlights the crossed references in Wikipedia pages between them (when existing). The third one presents a set of direct and indirect connections between the result and the query in a graph format. From this graph it is possible to use the second functionality to get more explicit information on the nodes connections thanks to their Wikipedia pages.

Figure 4: Discovery Hub mosaic results page

The user can influence the results in Discovery Hub thanks to the advanced search mode. First, he has the possibility to select the aspects that interest him the most about the query-resource. These aspects are the categories the query-resource belongs to (e.g. Blues-rock musicians, Musical_groups_from_London for The Rolling Stones). In this case the , (def. 10) is not computed by taking in account all the categories of the queryresource but only the subset explicitly specified by the user.

The user can also add randomness in the results selection by manipulating the "surprise" mode slide bar (from 0 to 1). 0 means that there is no randomness in the processing; it corresponds to a normal query. The closer the value is to 1 the more the results will be influenced by randomness (def 11). It can be very useful and playful for users that already have knowledge on the topic explored and that want to retrieve unexpected, surprising information about it.

EVALUATION

As mentioned in [START_REF] Kules | Users can change their web search tactics: Design guidelines for categorized overviews[END_REF] and [START_REF] Waitelonis | Augmenting Video Search with Linked Open Data[END_REF] the research initiatives in the exploratory search domain suffer from the lack of evaluation standardization. We evaluated the interest of the users towards the results selected by the algorithm. Indeed, this selection step is critical in our approach. A full evaluation of the application through task-based scenarios will be envisioned in future work.

First, we performed an evaluation on a neutral interface. Second we evaluated the influence of the Discovery Hub explanatory features on the user's judgments. We evaluated the results of our semantic spreading activation algorithm (SSA) against the sVSM algorithm used in the MORE recommender. The main reason of this choice is that MORE is the only linked-data based system of the related works list that has been compared to another: Seevl [START_REF] Di Noia | Linked open data to support content-based recommender systems[END_REF]. As MORE only recommends films, only the Film results were taken into account during the comparison.

Resources recommendation evaluation

During the first round of evaluation we evaluated both the relevance and the discovery potential of our proposition regarding the sVSM baseline. We wanted to verify the following hypothesizes:

-Hypothesis 1: SSA gives results at least as relevant as sVSM (even if it is not dedicated to the cinema domain). -Hypothesis 2: the SSA algorithm has a less strong degradation than sVSM algorithm. In other words, the endlist results are better for SSA. -Hypothesis 3: there is a greater chance that results are less relevant but newer to users at the end of the lists. -Hypothesis 4: the advanced search functionality gives better results compared to the standard query ones.

The hypothesis 1 and 2 aim to verify that the SSA algorithm retrieves relevant results compared to a domain specific approach. The hypothesis 3 aims to verify that the algorithm correctly ranks the results by retrieving the most relevant first. The hypothesis 4 aims to verify that the advanced search functionalities help the user to find more interesting resources.

The participants evaluated alone both algorithms on a neutral interface set up with the online tool Limesurvey 14 . They had to judge 5 lists of films' recommendations. These lists were composed of the top 20 results from the 2 algorithms. Each list was generated starting from one seed-film. The lists were fully randomized, the participants were not aware of the results provenance. The seed films used to generate the lists were randomly chosen in the « 50 films to see before you die »15 list. It was chosen because of its diversity:"each film was chosen as a paragon of a particular genre or style" To analyze the relevance and the discovery potential a 2 (SSA vs sVSM ) * 5(Film 1 vs Film 2 vs Film 3 vs Film 4 vs Film 5) * 2 (1-10 ranks vs 11-20 ranks) analysis of variance (ANOVA) test was realized. In statistics, an ANOVA [START_REF] Sprinthall | Basic Statistical Analysis[END_REF] is a method used to compare more than two means simultaneously and determine if their differences are substantial or reflects natural sampling fluctuation. As we study several factors at the same time and as the users participate in all conditions, we performed a factorial ANOVA with repeated measure. The survey was filled by 15 persons (i.e. 3750 votes): 13 males, 2 females, average age of 31.7 years, mainly computer scientists. The average number of movies seen on any support monthly was 10.4 (standard deviation = 8.66). In the following results 0 corresponds to strongly disagree, 1 to disagree, 2 to agree, 3 to strongly agree for the relevance score. 0 corresponds to seen, 1 to known but not seen, 2 to not known for the discovery score. The score for each user were very stable because it was computed over a large number of user responses (250 per user) and over two identified major sources of variation (ranking and film). This procedure allows us to increase the reliability on our measurement setting and thus had a positive impact on the power of our statistical testing [START_REF] Rl Brennan | Generalizability Theory[END_REF].

Hypothesis 1. To verify the hypothesis 1, we observed the difference between the SSA and the sVSM recommendation relevance scores. The figure 5 shows that overall SSA (mean m = 1.42, standard deviation sd = 0.27) outperforms sVSM (m = 1.18, sd = 0.24 The discovery score difference between the beginning and the end of the results lists is slight for SSA. One explanation is that the algorithm computes a relatedness which does not reflect any kind of popularity. It is noticeable that sVSM has a better discovery score than SSA at the end of the list but at the same time its relevance decreases considerably. SSA can be considered as more balanced.

Hypothesis 4. To validate the hypothesis 4 we performed a complementary experimentation. We asked to the users to choose the 3 most interesting aspects (DBpedia categories) and the less interesting ones about Fight Club. Fight Club was chosen because it was the most viewed by 86.66% of the participants (it was the highest rate). Ten persons participated to this experimentation extension. The participants showed interest in narrow categories (e.g. American black comedy films) and disinterested in broad ones (e.g. 1999 films). The 3 specified criteria of interest were used to compute the results using the advanced search mode. We asked the participants to judge the ten first results. The average relevance score of the top ten results significantly raised compared to the "classic" queries ones: 1.94 (sd=0.55) versus 1.42 (sd=0.39) previously. The hypothesis 4 is validated.

Explanatory features evaluation

We also evaluated the influence of the explanatory features on the users' judgments:  Hypothesis 5: explanatory features increase user's overall judgments positivity.

To analyze the impact of the explanatory features on the users' perception of the results, the participants of the first experimentation were asked to evaluate again 20 results with the Discovery Hub interface. These 20 results were randomly selected in the SSA results list of the first evaluation. We wanted to estimate if the explanatory features are efficient to increase the users' interest. compared [START_REF] Sprinthall | Basic Statistical Analysis[END_REF]. The Student test being statistically significant (t(14) = 3.872), p = 0.002) the hypothesis 5 is verified.

We asked the participants to give their opinion about the three explanations. For the 3 features we asked "the feature X helped me understand the relation between the films and to make a choice?" and one more general question: "overall, I feel that these three features can help me to make new discoveries". 0 corresponds to strongly disagree, 1 to disagree, 2 to agree and 3 to strongly agree.

The common properties and graph-based features helped significantly the participants (average scores: 2.13 for both) whereas the benefit of the Wikipedia-based feature was less evident (average score: 1.86). The more general question received the high average score of 2.53. The results are not uniform and show the interest to propose different explanatory features.

CONCLUSION

To ease the exploratory search tasks we propose to draw users' attention to resources and associations that convey a lot of knowledge regarding their initial interest. Therefore the research questions addressed in this paper are: (1) in a dense and heterogeneous linked data graph, how to select and rank a meaningful subset of resources related to the user's interest? [START_REF] Rl Brennan | Generalizability Theory[END_REF] As linked data are distributed, how to perform this selection on remote LOD sources? (3) On the interface side, how to present and explain the selection to the user? To select and rank a set of meaningful resources related to the user's interest we proposed a novel method based on a semantic spreading activation. To address remote SPARQL endpoints we coupled it with a graph sampling technique. We studied its behavior over DBpedia in order to set its main parameters. Finally we introduced the Discovery Hub application that offers faceted browsing and explanation features that help the user understand the results.

We observed that the results converged quickly and that processing a limited amount of triples was sufficient. The queries were processed in a few second and confirmed the validity of the approach implemented in the Discovery Hub prototype available online. Our user's evaluations showed the method efficiency for the suggestion of resources of interest against the sVSM baseline. They also confirmed the efficiency of explanatory features and of the advanced search functionality.

Definition 3 .Definition 4 .Definition 5 .Definition 6 .

 3456 It constrains the propagation to certain node types (see definition 9) and integrates a triple-based similarity measure (see definition 10). At the end of the algorithm execution the activation values of the nodes determine their ranks. Prior to the algorithm presentation, we introduce several necessary definitions on RDF triples and the classic graph functions we used: Definition 1. (RDF triple, RDF graph). Given U a set of URI, L a set of plain and typed Literal and B a set of blank nodes. An RDF triple is a 3-tuple , , ∈ ∪ ∪ ∪ . s is the node subject of the triple, p the predicate of the triple and o the node object of the triple. An RDF graph is a set of triples. Definition 2.(RDF typing triple, RDF non-typing triple.) An RDF typing triple is a 3-tuple , , ∈ ∪ : ∪ ∪ . An non-typing triple is a 3-tuple , , ∈ ∪ \ : ∪ ∪ .Let KB be the set of all the triples in the triple store: The node degree is the number of edges involving (Type depth) uses the subsumption schema hierarchy (as in RDFS or OWL) to compute the depth of a type and identify the most precise type(s) available for a node.Where type t is a class in the hierarchy of the RDFS schema and St is a direct super class of t in this hierarchy before any transitive closure is computed. (Node neighborhood) is the set of neighbors of the node i in the graph retrieved from the targeted linked data sources: (Semantic Spreading Activation algorithm,) The following formula determines the nodes' ranks along the iterations:

Figure 2 :Figure 3 :

 23 Figure 2: response time and correlation coefficient from one loading limit to another, top 100 results

  11 http://semreco.inria.fr 0

Figure 5 :

 5 Figure 5: relevance score of algorithms (between 0 and 3)

Hypothesis 5 .

 5 To verify the hypothesis 5, we observed the difference between the relevance scores obtained with and without the explanatory features. The relevance score rose significantly: previously m = 1.26, sd = 0.40, with the features: m = 1.50, sd = 0.26. The average number of positive judgments reached 9.4 versus 7.34 previously. A Student test[START_REF] Sprinthall | Basic Statistical Analysis[END_REF] was performed. It is used instead of the ANOVA in the case of only two mean are

Table 1 . Related works summary compute

 1 relatedness and similarity measures for recommendation and exploratory search purposes (summarized in the table1).

  7 version (section 6). As we needed to query the endpoint millions of times during the analysis we set up a local version. Our version contains the wikiPageWikilink 3 triples. This property indicates that a hypertext link exists in Wikipedia between the 2 resources but that the semantics of the relation was not captured. It provides an amount of valuable extra-links for connectionist methods like spreading activation. DBpedia 3.7 graph with wikiPageWikiLink triples is large (3.64 million nodes, 270 million triples) and heterogeneous since there are 319 classes in the DBpedia 3.7 ontology schema.

  20 . The selected films were: 2001: a space odyssey, Erin Brockovich, Terminator 2: judgment day, Princess Mononoke and Fight club. Two Likert scale[START_REF] Likert | A technique for the measurement of attitudes[END_REF] questions were asked:

		With the film [result] I think I will live a similar cinematic
		experience as with [seed film]? Strongly agree, agree,
		disagree, strongly disagree.
		You and [result]? Seen, Known but not seen, Not known
	This formulation was chosen because similarity is a very
	important factor of relevance for Discovery Hub (def. 10). Thus it
	can be used to get recommendations.

Table 2 : scores for partial lists

 2

http://linkeddata.org

http://wikipedia.org (c) 2013 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only. ISEM '13, September 04 -06 2013, Graz, Austria Copyright 2013 ACM 978-1-4503-1972-0/13/09 $15.00

http://dbpedia.org/ontology/wikiPageWikiLink

http://wimmics.inria.fr/node/26

http://purl.org/dc/terms/subject

http://wiki.gephi.org/index.php/SemanticWebImport

http://semreco.inria.fr/hub/videos/

http://semreco.inria.fr/hub/videos/

http://lookup.dbpedia.org

http://www.limesurvey.org

http://en.wikipedia.org/wiki/50_Films_to_See_Before_You_Die

We now want to study the behavior of the algorithm on graphs having diverse properties (e.g. structure, degree, size, diameter) in order to determine to what extend the parameters used for DBpedia are generic and can be reused for others data sources. We will also study how several linked data sources can be combined with the proposed approach. Finally we intend to take into account the learning process in the exploratory for instace declaring as new interests and seeds as the users explore.