In this paper, we propose an approach for searching large RDF graphs, using advanced vector space models, and in particular, Random Indexing (RI). We first generate documents from an RDF Graph, and then index them using RI in order to generate a semantic index, which is then used to find similarities between URIs, literals, and RDF subgraphs. We have experimented with large RDF graphs in the domain of life sciences and engaged the domain experts in two stages: firstly, to generate a set of keywords of interest to them, and secondly to judge on the quality of the output of the Random Indexing method, which generated a set of similar terms (literals and URIs) for each keyword of interest.
Recent years have seen a massive increase of highly structured data being made available in the form of RDF triple representations. Both legacy data and new data have been made available in RDF triple format and this representation has also made it worthwhile and feasible to create mappings between RDF data that originates from different legacy sources, leading to potentially very large RDF repositories. Initiatives such as Linked Open Data5 are working on creation, publication and interlinking of huge RDF graphs.
Traditionally, RDF spaces are being searched using an RDF query language
such as SeRQL [
In this paper we investigate whether advanced Information Retrieval (IR)
methods can bring a new dimension to the task of searching huge RDF graphs.
We propose a complementary approach based on word space model, more
concretely Random Indexing (RI) [
We evaluate our approach on subsets of the Linked Life Data (LLD) repository – a large integrated repository which contains 5 billion RDF statements from various sources covering the biomedical domain, including UniProt8, PubMed9, EntrezGene10 and many more11. Our evaluation is based on human judgment by clinical research scientists (from AstraZeneca pharmaceutical company) who were involved in two stages: firstly, to generate a set of keywords of interest to them, and secondly to judge on the quality of the output of the Random Indexing method, which generated a set of similar terms (literals and URIs) for each topic of interest. 2
A considerable amount of work has been done in the area of using Information
Retrieval methods for the task of selecting and retrieving RDF triples. However,
most of these approaches do not take advantage of the latent semantics included
in an RDF Graph, as their primary intention is finding the RDF files on the
Web relevant to the given keyword and/or a URI. These systems are semantic
search engines such as Swoogle [
In comparison to these approaches we use the neighbouring nodes as semantic context for each node in an RDF graph. The nodes and their contexts are used as virtual documents for Random Indexing.
In [
Finally, to the best of our knowledge, none of the similar approaches investigate the usage of methods that can discover latent semantics, such as Random Indexing. 3
Latent Semantic Analysis (LSA) [
RI can be seen as an approximation to LSA which is shown to be able to
reach similar results (see [
Random Indexing relies on the Johnson-Lindenstrauss lemma:
Lemma 1. Given 0 < ! < 1, a set X of m points in RN , and a number n >
n0 = O( log!(2m) ), there exists a mapping f : RN → Rn such that (1 − !)||u − v|| ≤
||f (u) − f (v)|| ≤ (1 + !)||u − v||, for all u, v ∈ X.
and particularly on the proof provided by Johnson and Lindenstrauss in their
1984 article [
In order to apply RI to an RDF graph we first generate a set of documents which represent this graph, by generating one virtual document for each URI in the graph (Section 3.1). Then, we generate a semantic index from the virtual documents (Section 3.2). This semantic index is then being searched in order to retrieve similar literals/URIs (Section 3.3). 3.1
The task of deriving a set of documents from a huge RDF graph starts with generating a representative subgraph for each URI of interest. We shall refer to such an URI as a representative URI.
A representative subgraph represents the context of a URI i.e. the set of other URIs and literals directly or indirectly connected to that URI. For a representative URI S, the representative subgraph of order N is a set of all paths of triples (S, P1, O1; O1, P2, O2; · · · ; ON−1, PN , ON ). If ON is not a literal we also include all triples ON , PN+1, LJ where LJ is a literal. In other words, we apply the Breadth-First-Search starting with the representative node, and extend this to the Depth Search which is defined by N. In addition, we include or exclude certain parts of the TBox: direct classes for instances are excluded (PN ! = rdf : type), while other annotation properties such as rdf s : label are included. In the experiments reported in this paper, the representative subgraphs are of order 1 (N = 1).
We create virtual documents by including all paths from representative subgraphs where: – all URIs of nodes or appearing inside literals are included unchanged; – for literals we remove punctuation and stop words, and then lowercase the text; we also remove number literals, gene and protein sequences, complex names, and HTML tags. 3.2
There are several parameters which can influence the process of generating semantic index, or vectors using the RI method: – Seed length Number of +1 and -1 entries in a sparse random vector. – Dimensionality Dimension of the semantic vector space – predefined number of dimensions to use for the sparse random vectors. – Minimum term frequency Minimum frequency of a term to get included in the index.
Our experiments study how variations of these parameters influence the quality of the results and how sensitive the method is to that variation. 3.3
Once the semantic index has been created, it can be used to find similarities
between URIs, literals, and RDF subgraphs. We use the cosine function to calculate
the similarity between the input term (literal or URI) vector and the existing
vectors in the generated vector space model. We can perform the following kinds
of searches:
1. finding similarities between two terms: given a keyword, find similar literals
and URIs; this can be used in several ways for example for refinement of
SPARQL queries (see [
While in the context of large RDF graphs such as LLD, we find all of these searches useful, in the experiments we present next, we focus on term-term search (Item 1) only. As the LLD dataset covers the life sciences domain, we have conducted a study with the clinicians from AstraZeneca, who are domain experts and understand the knowledge available in this large dataset.
Our goal in using the Random Indexing method is to investigate whether it can offer an alternative way of searching large RDF spaces, by suggesting literals or URIs which are similar to the topic of interest. We conduct an evaluation experiment with clinical research scientists from AstraZeneca, with the aim to assess this. 4.1
Linked Life Data is a dataset covering the life sciences domain, and the latest version 0.6 contains 5,052,047,661 statements in total (for a comparison, one year ago it contained 4,179,999,703 statements). Advanced IR methods based on Vector Space Model (VSM) are computationally expensive, and therefore, before we apply the Random Indexing method on the whole dataset, we evaluate it on two smaller subsets of LLD.
We have generated the two subsets as follows. For 1528 seed URIs (the URIs representing all MEDLINE articles from December 2009) we retrieve neighbouring subgraphs (of order 1) recursively until we reach certain predefined limit of statements, and we refer to these as LLD1 and LLD2. Table 1 shows the sizes of LLD1 and LLD2. number of statements number of virtual documents number of terms In order to calculate the correctness of the retrieved terms, there are standard Information Retrieval measures such as precision, recall and Mean Average Precision (MAP). Precision is defined as the number of relevant documents retrieved divided by the total number of documents retrieved and is usually calculated for certain number of retrieved documents (e.g., Precision@10, Precision@20). Recall is the number of relevant documents retrieved divided by the total number of existing relevant documents (which should have been retrieved).
Mean Average Precision (MAP) is by far one of the most popular measures
in IR evaluation because, for each system and set of topics, it provides a
single value to measure its performance [
As our task is to retrieve most relevant literals and URIs first, we used MAP@10. Recall is extremely difficult to measure due to the number of terms in our datasets (see Table 1). In addition, our task is to help domain experts explore large RDF graphs, which is similar to Web search in the sense that there is a vast amount of terms to be searched through, and also a significant number which is relevant for each input term. Hence, for these kinds of tasks, users care more about precision than about recall. Indeed, they care most about the top ranked results, which is exactly what is captured by MAP.
Relevance of retrieved terms was evaluated by two clinical research scientists. All scientists looked at all retrieved terms. Relevant were considered only those terms which both scientists marked as relevant. In order to measure agreement between scientists on this particular task, we measured the Inter Annotator Agreement (IAA) between the two clinicians based on the words which both of them marked as relevant/irrelevant.
IAA has been used mainly in the classification tasks, where two or more
annotators are given a set of instances and are asked to classify those instances
into some pre-defined categories. The two commonly used IAA measures are
observed agreement and Kappa (κ) [
Observed agreement is the portion of the instances on which the annotators agree. For our case, with the two annotators and two categories (relevant and irrelevant), it is defined as
Ao =
a + d a + b + c + d (1) (2) where a refers to the number of terms both annotators agreed as relevant, d refers to the number of terms both agreed as irrelevant, b refers to the number of terms annotator 1 marked as relevant, and annotator 2 as irrelevant, c refer to the number of terms annotator 1 marked as irrelevant, and annotator 2 as relevant.
A certain amount of agreement is expected by chance which is not captured by the observed agreement. The Kappa measure is a chance-corrected agreement. Kappa is defined as the observed agreements Ao minus the agreement expected by chance Ae and is normalized as a number between -1 and 1.
k =
Ao − Ae 1 − Ae k = 1 means perfect agreement, k = 0 means the agreement is equal to chance, k = −1 means ‘perfect’ disagreement.
There are two different methods for estimating Ae: in Cohen’s Kappa, each
annotator has a personal distribution, based on his distribution of categories.
In Siegel & Castellans Kappa, there is one distribution for all annotators,
derived from the total proportion of categories assigned to all annotators (see
[
We have performed our experiment through the following steps: 1. Extracting topics of interest represented as query terms which are present in both LLD1 and LLD2. In order to avoid exposing the scientists to learning SPARQL, we have formed a team of one computer scientist and one clinical research scientist. The computer scientist was executing the SPARQL query and browsing through the links and URIs, while the clinical research scientist was only looking at the abstracts which the computer scientist selected. As a result, we obtained 18 keywords which all appeared in both LLD1 and LLD2 datasets. We split this set into two halves as shown in Table 2 , and then perform the following two steps in two iterations: first, Group 1 is used for training the model, and Group 2 for testing it. In the second iteration, the two sets are swapped. 2. Training the model: we generated RI models for several variations of the following RI parameters for both LLD1 and LLD2: – vector dimension: 500, 1000, 1500, 1800, 2500 – seed length: 10, 50, 100, 300, 500, 1000 – term frequency: 1, 2, 5, 8, 10 This resulted in 290 runs (145 per dataset12). We then searched for similar words for each topic of interest from the training set, and presented them to clinicians who accessed the relevance. The combinations for parameters which lead to the best results (measured through MAP) were considered as the optimal setting for testing the method in the next step. 3. Testing the model: for the models generated using the optimal parameters retrieved in the previous step, we retrieved 10 similar words for each topic 12 5 runs are missing from this count, corresponding to the situation where the seed size is 1000, and the vector dimensionality is 500, which is impossible of interest from the testing set and calculated MAP. The correctness of the retrieved terms was assessed by clinical research scientists to whom we gave the terms in the form of a survey (see below).
Human assessment The retrieved keywords for each topic of interest in both training and testing sets were assessed by humans. We merged the results from all searches into one pool, and gave this list to the scientists in the form of a survey. When the similar term was a URI, we have extracted the label from LLD and showed it in brackets. This is to ensure that the scientists can concentrate on meaning of these rather than looking and searching LLD in order to find the label. An example task looked similar to this: ----------------------------------------------------------------Is ’trauma’ related to (delete URIs/words which are not related): ----------------------------------------------------------------arteriopathy back-projection barotraumas gunshot http://linkedlifedata.com/resource/umls/id/C0003048 (Animal Experimentation) http://linkedlifedata.com/resource/umls/id/C0004601 (Back Injuries) http://linkedlifedata.com/resource/umls/id/C0005604 (Birth trauma) ............
The most difficult task when designing this experiment was to define the meaning of relevant. Relevant, in this context, is any word related to the given keyword. This is a quite broad definition, which has, as it has been reported by clinical research scientists who were involved in this experiment, posed a number of difficulties due to many different levels of relevance. One of them stated that it would not be easy to repeat the same tasks and mark the same words as relevant if they had to repeat the same task again. We consider those that are not deleted as relevant. Only those words which have been marked as relevant twice (by two different clinicians) were eventually used when evaluating our results. 4.4
In this section we first look into the results of training the model and finding the best parameters with two separate groups independently. Then, we look at the results of testing the RI method using these best parameters.
Training the model We expect to see variations of MAP, for different values of dimensionality, seed length, and minimum term frequency parameters. Our goal is to find the combination of parameters for which MAP is highest, so as to use those in the testing phase.
Figure 1 shows the distribution of MAP across all cases, and for each group used for training. It seems that the keywords from Group 1 were more challenging for the method, as MAP values are much lower on average. However, as we can
The variation of seed length parameter value seems not to cause any significant changes to MAP across both datasets, and hence, we consider the lowest value of this parameter as the optimal one, due to the fact that the the computational resources required to build and search the semantic space are proportional to the value of seed length. Table 4 outlines optimal parameters: those that we chose to use in the testing phase.
Finally, the size of the dataset had a significant influence on MAP (MannWhitney U Test, p < 0.0001) for both Group 1 and 2 meaning that the larger set (LLD2) resulted in producing the higher value of MAP for Group 1, while for Group 2 the results were better with the smaller dataset (LLD1).
Testing the model In what follows we explore whether the model built using the optimal parameters just presented can be used to effectively test the model. In our context, testing the model means evaluating the set of related terms (literals and URIs) returned by our method for the set of testing keywords given as input.
We ran the search method using Group 2 as a testing set against the RI model trained with Group 1, and then Group 1 as a testing set against the RI model trained with Group 2. Results are shown in Table 5. The RI method results in as good or better MAP for Group 2 in comparison to MAP for the best trained model (Group 1 column in Table 4), while for Group 1 the resulting MAP for LLD2 is as good as that of the best trained model (Group 2 column in Table 4), while for LLD1 it is lower for 0.15. This is due to the distribution of keywords in Group 1, due to which MAP for the RI model with optimal parameters is only 0.05 higher (0.55).
In the testing phase, MAP across both groups reached 0.565 and 0.61 for LLD1, and LLD2 respectively.
Also important to observe is the fact that when the data corpus increases (e.g. LLD2 vs LLD1) the method becomes very stable, and observed MAP values in the training process are reproduced in the subsequent test phase. Arguably this is due to the small difference in MAP across parameters, but it still shows that RI is a stable method even in this unusual use-case we are dealing with.
Human assessment. In order to assess overall difficulty of the tasks which we solve using the RI method, we calculated Inter-annotator agreement, and indeed Observed agreement and Cohen’s Kappa agreement (see Section 4.2). The observed agreement across all keywords was 0.81, and the Cohen’s Kappa was 0.61 which indicates that the given task of selecting relevant keywords for a topic of interest was indeed difficult for domain experts.
The code and datasets from the described experiment, including generated virtual documents and semantic spaces, can be downloaded from the LarKC Wiki13.
Performance The parameter values affect not only the quality of results
but also the required resources and the indexing time. Increasing the value of
dimensionality and seed length almost exponentially increases the time to
generate the semantic space (from 0.67 minutes for 500 dimensions to 3 minutes
for 2500, LLD1; from 3.78 minutes for 500 to 11.5 minutes for 2500 dimensions,
LLD2). The higher the value for seed length and dimensionality, the higher the
requirements for the computational resources and RAM in particular14.
Application of RI to the whole LLD dataset poses the scalability issues related to the
size of our corpus. While indexing is a one-off operation (that takes 1˜6 hours
on MDC computer with 256G RAM), the search for ‘lung’ after the space is
generated takes 14 minutes. Therefore, in our related work reported elsewhere
([
We described the application of the Random Indexing method for the task of searching large and unknown RDF graphs. We tested our method on the subsets of the Linked Life Data, by training it using the variation of parameters, and then involving domain experts to judge on the relevance of retrieved terms. None of the parameters had a significant influence on MAP, apart from the size of the dataset. However, the values of MAP reaching 0.565 and 0.61 for LLD1, and LLD2 datasets respectively, indicate that the generation of virtual documents as described in this paper and generating the semantic index using the RI method has promising results. The reason for the stability of the RI method might have been the span of the parameters which we used, and hence in our future work we will expand the variation span and also repeat the runs across the same parameter variations in order to increase the significance of results. Acknowledgments We would like to thank creators of SemanticVectors15 library which is used in the experiments reported in this paper. This research has been supported by the EU-funded LarKC16 (FP7-215535) project.