We describe an approach to nd similarities between RDF datasets, which may be applicable to tasks such as link discovery, dataset summarization or dataset understanding. Our approach builds on the assumption that similar datasets should have a similar structure and include semantically similar resources and relationships. It is based on the combination of Frequent Subgraph Mining (FSM) techniques, used to synthesize the datasets and nd similarities among them. The result of this work can be applied for easing the task of data interlinking and for promoting data reusing in the Semantic Web.
Since the creation of Linked Open Data Cloud3 initiative in 2007 with 12 datasets, to its last update in 2014 with 570 datasets, the number of Linked Datasets has grown enormously. This growth trend suggests that in few years, selecting appropriate datasets to link our datasets to, is going to become harder and harder. The same applies to the task of nding the dataset that may contain useful information for us, according to our needs. The work presented in this paper is focused on providing some steps forward into some of the aforementioned limitations: nding datasets to link to, nding datasets that provide support to our needs or understanding or summarizing datasets.
Our main contribution is an approach to nd similarities among RDF datasets
based on their graph structure, which can be used for solving the aforementioned
problems. The main challenge that we have to deal with stems from the fact that,
due to the size of many of the graphs derived from these RDF datasets, a direct
comparison among their complete structure is not applicable. Therefore, a
Frequent Subgraph Mining (FSM) based approach is proposed. FSM techniques,
widely used in the domains of chemistry and biology to nd similarities and
correlations among di erent chemical compounds and molecules [
An example of an application of the work proposed in this paper is related to dataset interlinking. As stated in section 2, when using existing dataset interlinking tools, the user have to select the input datasets whose links are going to be searched. Nowadays, there are two main approaches to select these datasets: applying the brute force for applying all the possible pairs of datasets to the interlinking tool; or requesting the user for selecting the most suitable datasets under her/his beliefs, a task that is becoming harder and harder because of the growth of the Linked Open Data Cloud. Proposed solution can ease this task suggesting a subset of related datasets, with the consequent reduction of the search space.
In summary, in this work a new approach for synthesizing and nding similarities among RDF datasets is presented. Speci cally, this approach proposes the use of FSM techniques to synthesize these datasets. The approach proposed in this work can be used for easing the task of interlinking new datasets, and for improving data reuse through nding similar datasets.
The rest of the paper is organized as follows. In Section 2 the previous works in semantic dataset browsing, interlinking and summarization, and Linked Data source discovery are presented. In Section 3 some de nitions and concepts about graph mining are explained. Section 4 describes our new approach based on FSM. In Section 5 proposed approach is evaluated against a set of datasets from Linked Open Data Cloud. At last, in Section 6, conclusions and future research challenges are explained. 2
There are four research elds related to possibles usages of the work presented in this paper: semantic dataset browsing, interlinking and summarization, and Linked Data source searching.
Semantic Dataset Browsing. Works under this eld provide search
capabilities over linked datasets. From a set of terms, these browsers nd resources in
which these terms appear. Most of these works use techniques given from
information retrieval eld like TF-IDF (term frequency-inverse document frequency),
and some works o er more complex techniques for re ning the results. However,
these works do not apply a previous lter on the datasets against they search the
terms given by the user. Proposed work can be useful in this area when a term
is found in a dataset, for prioritizing related datasets when searching for more
results. In this eld works like Swoogle [
Semantic Dataset Interlinking. The aim of works under this category is
about given a pair of datasets, establishing links between them, based on a set
of rules de ned by the user. Most of these works use di erent properties from
resources within a dataset for establishing owl:sameAs links among them. One
of the most important lacks of works in this area is that the user has to select
the pair of datasets to establish new links between them. The solution proposed
in this paper can be used to select these input datasets. Most remarkable works
in this eld are Silk [
Semantic Dataset Summarization. Although dataset summarization is not
the nal goal of this work, we have considered interesting to analyse most
remarkable works in this eld, although they are oriented for creating human-readable
data summaries, instead of machine-readable summaries that are used in the
proposed work. In [
Linked Data Source Searching These works try to nd candidate datasets
for interlinking. Works under this category are the most related with the work
described in this paper. In [
The main objective of FSM is to extract all frequent subgraphs from a single
graph or a set of graphs. We assume the de nitions from [
Multiple state-of-the-art tools implement FSM. In Table 1 a summary of the
most relevant features of each solution is shown. These features are the following
ones:
{ Single graph/Transactions: according to [
As shown in Table 1 only SUBDUE and DPMine cover all features to be suitable for dealing with the characteristics of RDF graphs. As in this approach we want to extract the most common subgraph from each dataset, the solution that supports single graphs has been selected, i.e. SUBDUE.
Given a single, directed and labeled graph, SUBDUE [
size(G) (size(S) + size(GjS)) (1) size(G) = (jvertex(G)j + jedges(G)j) (2)
SUBDUE can be parameterized to adapt its behavior to the di erent input graphs. To facilitate the understanding of the application of SUBDUE in Section 4 some of these parameters are explained: { inc: this parameter allows the incremental analysis of large graphs, avoiding the consumption of all the memory of the system by large graphs and allowing the preview of partial results. To perform the incremental analysis, the input graph has to be split in di erent and numbered les. SUBDUE analyses these les in order, aggregating results of the les previously analyzed to the current le. { limit: limits the number of candidate substructures that SUBDUE takes in consideration in each iteration. The default value is jedgesj . 2 { prune: prunes the graph discarding useless substructures. 4 4.1
In order to apply the RDF graph synthesis model presented in this paper, some modi cations have been done to the original RDF graph model. It is important to note that these transformations do not preserve the meaning of the RDF model, but we do not consider that property important for our approach. However, after applying these transformations, a proper interpretation of the graph can be done. As can be seen in this section, the aim of these transformations is to simplify the graph for easing the task of extracting the most common substructures. From the triples shown in Listing 1, represented graphically in Figure 1, transformations are applied to ensure the correct understanding of the presented model.
The rst transformation applied to RDF graphs consists in replacing URIs from the subjects of resources from datasets. Since they are unique identi ers of resources, URIs in subjects will generate a large amount of unique nodes which do not belong to any candidate substructure, increasing the di culty of nding frequent subgraphs. To avoid this, these URIs have been replaced by the ontological class (or classes, if it is represented by more than one class) of the resource represented by the rdf:type property if any, as can be seen in Figure 2. If a resource has no a rdf:type predicate associated, this resource is discarded.
The next transformation is about managing interlinked resources. Establishing links among resources from di erent datasets is one of the most important features in Linked Data publication. For this reason, a large amount of internal and external links can be found in linked datasets. Managing external links, adds to the computational cost generated by the analysis of each triple, the delay generated by retrieving the information pointed by them through the Web. Furthermore, one of the challenges of this work was to solve the cold start problem when looking for related datasets. For these reason, external links have been 1 @prefix : <http://example.org/resource/> . 2 @prefix foaf: <http://xmlns.com/foaf/0.1/> . 3 @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> . 4 @prefix dcterms: <http://purl.org/dc/terms/> . 5 @prefix aktors: <http://www.aktors.org/ontology/portal/> . 6 7 :Tim_Berners-Lee rdf:type foaf:Person ; 8 foaf:name "Tim Berners-Lee" ; 9 foaf:mbox "timbl@w3.org" ; 10 foaf:homepage <http://www.w3.org/People/Berners-Lee> . 11 12 :pub1 rdf:type aktors:Article-Reference ; 13 aktors:has-title "The Semantic Web" ; 14 dcterms:creator :Tim_Berners-Lee ; 15 aktors:published-by "Scientific American" .
Listing 1: RDF triples used in the example model. removed. Despite this, in Section 6 the in uence of existing links is brie y analyzed. In Figure 3, the resulting model after elimination of external links can be seen. In this model a structure representing a publication and its author can be seen, as a synthesis of triples presented in Listing 1.
Regarding to the literals, although they have been maintained in proposed model, there are no literals in any of most frequent structures extracted during the evaluation. The explanation of this situation is similar to the explanation given about the URIs in subjects: with so much variety of di erent literals, the probability to form part of a candidate substructure is minimal. foaf:homepage
We apply SUBDUE to the graph obtained as a result of the previous
transformations. According to [
Once the most frequent substructures from di erent datasets are extracted, the comparison among them has been done through SUBDUE's gm (Graph Matcher). Given a pair of graphs, this utility computes the cost of transforming the largest graph into the smallest one, returning the number of transformations done. In this case, all transformations (addition, removal or replacing of a node) have the same cost. As this number of transformations is not normalized by default (it depends on the size of the input graphs), the normalization shown in Equation 3 has been applied to the result. Finally, the similarity between both substructures is calculated as can be seen in Equation 4.
Costnormalized =
Cost jvertexeslargestGraphj + jedgeslargestGraphj Similarity = 1
Costnormalized (3) (4)
This work has been implemented following the work ow explained next. The di erent stages of this work ow have been implemented as independent tasks: { Generation of IDs and replacement of subjects: as can be seen in listing 2, SUBDUE has its own format for representing graphs. This format requires to assign an unique ID to each vertex. At this rst step, the RDF graphs are iterated, replacing the subject of each resource by its ontological class if the property rdf:type is presented and an unique and consecutive IDs are assigned to each generated vertex. { SUBDUE le generation: once the IDs are assigned, the relationships among generated vertices are analysed in order to generate edges. Once these edges are generated, the nal SUBDUE le of each graph is generated. { Most frequent subgraph extraction: at these step the most frequent subgraph of each RDF graph is extracted with SUBDUE and previously generated input les. { Graph matching: at last, similarities among these subgraphs are found with SUBDUE's Graph Matching (gm) tool.
The implementation of this work and baselines (subsection 5.2) can be found at https://github.com/memaldi/lod-fsm. 5
Presented approach has been evaluated against datasets from Linked Open Data
Cloud. The development of the evaluation follows these steps. First, a gold
standard has been created for determining the e ectiveness of both developed system
and baseline solutions in terms of precision and recall. These baseline solutions
(or baselines) are simple solutions that solve proposed problem in a simple way,
with the aim of establishing a baseline to be surpassed by the new solution.
At last, the results given from proposed solution are compared with the results
given by baseline solutions. The evaluation has been done only in terms of e
cacy because the developed work has been designed to be launched in batch and
without the interaction of the end-user, so that, the e ciency is not considered
a key factor to be evaluated.
Listing 2: Representation of the graph from gure 3 in SUBDUE. In les 1-6 the
vertices are represented while in les 7-11 the edges are represented.
For constituting the gold standard, two di erent sources have been checked. The
rst source, inspired by [
To solve this issue, a second source have been used to form the gold standard.
This source consisted on surveying di erent researchers on Semantic Web and
Linked Data for determining the validity of these new relations among datasets.
These surveys have been performed through a web application5 that shows to
researchers di erent pairs of datasets, to determine if there was any possible
relationship between them. These datasets were represented by the title, description
and resources published in their The Datahub's entry. Three options were
allowed for each pair of datasets: \yes" if they consider that there was a possible
relationship between them, \no" if they consider the opposite, and \unde ned"
if they were not sure about the possible relationships. Each pair of datasets have
been evaluated by three di erent researchers. This approach arises another issue:
the number of di erent pairs resulting from the combination of all the datasets
4 http://datahub.io
5 https://github.com/memaldi/ld-similarity-survey
employed during the evaluation ups to 2,3466. Considering that each pair have
to be evaluated three times, this number increases to 7,038 evaluations to be
done by selected researchers. Considering that this number of evaluations is too
high, the number of dataset pairs have been reduced considering the evidence
proposed by [
At the time of writing, an unique gold standard has been created for evaluating the developed system. However, a more suitable solution could be to develop a di erent gold standard depending on the topic of the datasets whose similarities are going to be extracted (biology, statistical government data, academical publications, etc.). This work is going to be attempted in the future work. 5.2
For weighting the results given by proposed solution, three baselines have been developed. The rst baseline is based on the evidence that as more ontologies are shared between a pair of datasets, more related they are. The relation degree between a pair of datasets is calculated as follows, being N the set of ontologies used to describe the dataset D: score(D1; D2) =
N1 \ N2 max(jN1j; jN2j)
The second baseline, similarly to the rst one, takes the common ontologies between a pair of datasets to establish their relation degree, but establishing a ranking based on the usage of the classes and properties of each ontology used within each dataset. The distance between di erent pair of rankings have been calculated through a normalized Kendall's Tau:
K( 1; 2) =
X Ki;j ( 1; 2) i;j2P
At last, the third baseline calculates the relation degree between a pair of datasets calculating the Jaccard distance among all the triples of each dataset. Being T1 and T2 the pair of datasets to be compared, the Jaccard distance is calculated as follows: 6 The complete list of used datasets can be found at http://apps.morelab.deusto. es/iesd2015/datasets.csv (5) (6) In gure 4, the results of both proposed solution and baselines are shown, in terms of precision, recall, F1-score and accuracy. As can be seen, in terms of precision, the proposed solution clearly overcomes the baselines, overpassing a value of 0.8 from a threshold of 0.4; reaching a maximum value of 0.9. On the other hand, the maximum value of recall is about 0.51, decaying from a threshold of 0.3, o ering a result that is not as good as expected and being surpassed by one of the baselines. This situation is promoted by the fact that higher the threshold is, the requested similarity between pair of graphs is higher too. Thus, there are pairs of datasets detected as related by our solution but their relation degree is not as high as expected. These results show that recommendations done by the proposed solution are valid in a high percentage (low number of false positives), although there still are many related datasets that the solution omits.
Regarding to the good results obtained by the rst baseline, there is a
clarication to be done. As can be seen, many datasets used in the evaluation where
produced by the RKB Explorer project [
In this work, a solution for recommending related datasets and easing the task of dataset linking has been presented. As exposed in Section 5, proposed solution provides precise recommendations of candidate datasets to be linked. Although the recall is not as good as expected, given that nowadays the help that a data publisher has at time of selecting related datasets for linking his datasets is very limited, we consider that is more important to recommend valid candidate datasets for interlinking, although these datasets are not all the available datasets. However, the results given by the recall are an issue in which we are currently working. At the present time, for avoiding false negatives provoked by related datasets described by di erent ontologies, string similarity techniques are being introduced, achieving an increase of recall between 0.10 and 0.30 regarding to the work exposed in this paper. Another task to be done in the future work is to analyse how the links generated by the own system can be used for improving the results in an iterative way. At last, regarding to the evaluation, an important future task is to include more diverse datasets in the evaluation set for avoiding the over tting of the proposed model or any of the baselines and developing a di erent topic-based gold standard.
In conclusion, the promising results obtained show that most frequent subgraph mining techniques can be used to ease the task of interlink datasets from the Semantic Web.
Acknowledgments. This work has been developed within WeLive project, founded by the European Union's Horizon 2020 research and innovation programme under grant agreement No 645845.