In this paper, we present RDFDigest+, a novel tool that enables e ective and e cient RDF/S Knowledge Base (KB) exploration using summaries. The tool employs a diverse set of algorithms for identifying the most important nodes, o ering a wide range of possibilities to capture importance. The selected nodes can be combined using multiple state of the art algorithms to generate a complete schema summary graph. In addition, we present a new approach enabling the dynamic exploration of summaries through two novel operations zoom and extend. Extend focuses on a speci c subgraph of the initial summary, whereas zoom on the whole graph, both providing granular information access to the end-user.
The recent explosion of the Web data and the associated Linked Open Data
initiative have led to an enormous amount of widely available RDF datasets
[
In our work, we design and develop RDFDigest+(http://rdfdigest.ics.
forth.gr) that focuses on three aspects: a) how to identify the most important
nodes of an RDF/S KB, b) how to link those nodes in order to produce a valid
sub-schema graph and c) how to enable the active exploration of the KB,
presenting various statistical information and enabling zooming operators. Multiple
importance measures [
In this work, we separate between the schema and instances of an RDF/S KB, represented in separate graphs, GS and GI . The schema graph contains all classes and the properties they are associated with. The instance graph contains all individuals, and the instantiations of schema properties.
Identi cation of the most important nodes. For ranking the available
schema nodes based on their importance, we use the following measures: Degree,
Betweeness, Bridging Centrality, Harmonic Centrality, Radiality, Betweenness,
PageRank and HITS [
Linking most important nodes Having a way to rank the schema nodes of an RDF/S KB according to the perceived importance, we then select the top-k ones and focus on the paths that link those nodes, aiming to produce a valid sub-schema graph. RDFDigest+ o ers two methods for achieving this. The rst one focuses on identifying a maximum cost spanning tree (MST) in the graph, and on linking the selected nodes using paths from the selected tree. The corresponding algorithm is computationally e cient. However, although MST identi es the paths with the maximum weight in the whole graph, the paths selected out of the MST might not maximize overall the weight of the selected summary. Moreover, many additional nodes might be introduced in the result, since there is only one path to be selected between two nodes and in this path many other not important nodes might appear as well. Alternatively, we model the problem of linking the most important nodes as a variation of the well-known Graph Steiner-Tree problem where the goal is to minimize the additional nodes introduced for connecting the top-k nodes. However, the problem is NP-hard, and as such approximation algorithms should be explored.
Exploration through summaries. With summaries, users can better understand the KB contents. However, they might nd the presented information overwhelming and may want to see complementary information.
Extend: The extend operator gets as input a subgraph of the summary schema graph and identi es other nodes that depend on the selected nodes. Dependence has not only to do with distance. Like TF-IDF, the basic hypothesis is that the greater the in uence of a property on identifying a corresponding instance is, the less times it is repeated. Speci cally, we de ne the dependence between two classes as a combination of their cardinality closeness CC, the AIM of the classes, and the number of nodes appearing in the path Y connecting these two classes. That is: Dependence(u; v) = AIM(v) PjYiu2;Yvj CCA(I(Mi(1i));i) , where CC is de ned for a pair of classes as the number of distinct edges over the number of all edges between them. As we move away from a node, the dependence becomes smaller by calculating the di erences of AIM across a selected path in the graph. In addition, we penalize dependence dividing by the distance of the two examined nodes. The corresponding algorithm calculates the dependence of the adjacent nodes expanding progressively the range until it reaches a speci ed number of nodes. Then it links the nodes to be added using three approximations: a) CHINS, which in essence starts with a partial solution consisting of a single schema graph node and then nds one additional node each time; b) Shortest Paths, which proceeds similar to CHINS but starts with all nodes available in the summary in the rst partial solution and c) Dependent Paths, which uses the nodes already visited when computing Dependence.
Zoom: Di erently, we focus on zooming, by exploiting the schema graph as a whole. That is, we introduce the zoom-out and zoom-in operators to produce more detailed or coarse summary schema graphs. To this end, we consider the n0 schema nodes with the highest importance in GS, where n0 can be either greater than n, for achieving a zoom-out, or smaller than n, for achieving a zoom-in, where n represents the size of the given summary.
The simplest approach for zooming-in/out, is to calculate from scratch the T OPn0 schema nodes and then to use the Steiner-Tree algorithm from scratch to link the selected nodes. However, since we already have an existing summary as a basis for our zoom operations we explore the following approximations: a) Zoomin: Remove the nodes in T OPnnT OPn0 and their connections without recalculating the Steiner-Tree algorithm for T OPn0 - this might leave additional nodes in the result summary. b) Zoom-out - CHINS : Add the nodes in T OPn0 nT OPn and link them with existing summary using the CHINS approximation algorithm. c) Zoom-out - Shortest Paths: Add the nodes in T OPn0 nT OPn and link them with existing summary using the Shortest Paths approximation algorithm. 3
The high-level architecture of the system is shown in Figure 1 (left). The summarization process starts by uploading an RDF/S le, or by providing the URL of an online le. The le is then stored to a Virtuoso triple store. Our engine preprocesses the available information and stores statistical and metadata information in a di erent Virtuoso graph. As long as existing information is available for a speci c le, it can be reused and not recomputed.
To demonstrate the functionalities of the RDFDigest+, shown in Figure 1 (right)), we will use 5 KBs: the BIOSPHERE ontology, the Financial ontology, the Aktors Portal ontology, the CIDOC-CRM ontology and DBPedia. The variety on the size, the domain and the structure of these ontologies o ers an interesting test case for our demonstration. The demonstration will start by selecting one of the aforementioned ontologies and producing a visual summary identifying and linking the most important nodes in the KB. In the presented summary graph, the size of a node depends on the its importance. By clicking on a node, additional metadata (e.g. the number of instances, and the connected properties and instances) are provided to enhance ontology understanding. Further explo