In this paper we study a graph kernel for RDF based on constructing a tree for each instance and counting the number of paths in that tree. In our experiments this kernel shows comparable classication performance to the previously introduced intersection subtree kernel, but is signi cantly faster in terms of computation time. Prediction performance is worse than the state-of-the-art Weisfeiler Lehman RDF kernel, but our kernel is a factor 10 faster to compute. Thus, we consider this kernel a very suitable baseline for learning from RDF data. Furthermore, we extend this kernel to handle RDF literals as bag-ofwords feature vectors, which increases performance in two of the four experiments.
Machine learning and data-mining for linked data is an emerging research eld.
Linked data is represented in the Resource Description Framework (RDF).
Kernel methods [
Since RDF essentially represent a graph, graph kernel methods provide an
attractive solution for machine learning on linked data. Currently there exists
some research on graph kernels for RDF. In [
The advantage of using graph kernel techniques for RDF is that the technique is very generic and can be widely applied, as long as the data is stored as RDF. No understanding of the semantics of the data is required, although such knowledge can be used if available. For example, if the data is modeled using a more expressive formalism such as OWL and RDFS than extra derived triples can be added to the RDF and this information can be exploited as well.
In [
In this paper we introduce a simple graph kernel for RDF data based on
constructing a tree for each instance, starting from the root, i.e. the instance,
vertex, up to a de ned depth. Then we count the number of paths in the tree
starting from the root vertex. This kernel shows comparable classi cation
performance to the intersection subtree kernel de ned in [
The rest of this paper is structured as follows. In Sect. 2 we introduce our graph kernel and its extension to deal with literals. Section 3 contains our experimental evaluation of the kernel performance in terms of prediction and computation time. We end with some conclusions and suggestions for future work. 2
The graph kernel approach to learning from RDF is based on the idea that
instances are represented by their subgraphs. In the classi cation task introduced
in [
Below we present a kernel method for RDF graphs very similar to the intersection
subtree kernels in [
There are two main di erences between the kernel de ned here and the
intersection subtree kernel in [
Our method is presented in Algorithm 1. For each instance we compute a
feature vector using the recursive function processVertex . This recursive function
counts all the paths starting from the instance vertex up to depth d and creates
a feature vector with these counts. Using the map pathMap we track the feature
vector index of each unique occurring path. Furthermore, for e ciency it is
useful to implement the feature vectors as sparse vectors, since the majority of
the indices have zero value. Note that, as in the kernel in [
We count paths instead of subtrees for two reasons. First, it leads to a very straightforward computation of the feature vectors, since we do not have to compute the full tree rst to compute the subtrees. Furthermore, it allows for handling (string) literals separately in a simple manner, as we will see in Sect. 2.2.
Algorithm 1 Intersection Tree Path Kernel Input a set of RDF triples R, a set of instances I and a max depth dmax Output a set of feature vectors F corresponding to the instances I Comments pathMap is a global map between paths of vertices and edges and integers { set pathIdx = 1 { for each i 2 I { create a new feature vector fv { do processVertex (i; i; []; fv ; dmax ) { add fv to F function processVertex (v; root ; path; fv ; d) { if d = 0, return { for each (v; p; o) 2 R { if o is root , set path = [path; p; rootID ] { else, path = [path; p; o] { if pathMap(path) is unde ned { set pathMap(path) = pathIdx { set pathIdx = pathIdx + 1 { set fv (pathMap(path)) = fv (pathMap(path)) + 1 { do processVertex (o; root ; path; fv ; d 1)
Compared to the Weisfeiler-Lehman (WL) graph kernel used in [
Literals in RDF can only occur as objects in triples and therefore have no outgoing edges in the RDF graph. They can contain di erent types of data, but they are often strings. In Algorithm 1 literals are treated as any other vertex and they are only considered equal if they contain exactly the same information. However, for (large) strings this approach can waste potentially useful information. Therefore we introduce an extension to the previous algorithm that treats literals as separate bag-of-words vectors.
Algorithm 2 is essentially Algorithm 1, with a di erent treatment of literal vertices. For each instance we now create a list of feature vectors fvs, which are lled by the function processVertex . If processVertex encounters a literal, then we add a special literal label to the path (similar to how root vertices are treated) and the function processLiteral is executed with that literal. First, processLiteral creates a term vector for the literal, counting all the terms/words occurring in that literal. To compare only literals that have the same path from the root vertex, we use the map litMap to track an index into the list of feature vectors fvs and put the term vector into fvs at that index. For simplicity we treat all literals as strings and we assume that one underlying dictionary is used when creating the term vectors, ensuring that each term has the same index in each vector. Furthermore, for ease of de nition, we assume that the list of feature vectors fvs is long enough. Moreover, the individual term vectors have a xed length that is large enough to t all the possible terms, such that concatenating them results in vectors of the same length for every instance.
When working with text and term vectors it is standard to normalize term vectors by converting them to Term Frequency-Inverse Document Frequency (TF-IDF) vectors. We also apply this normalization to our computed feature vectors. 3
In this section we present a number of experiments with the Intersection Tree
Path (ITP) kernel that we presented above. The rst goal of these experiments
is to compare the performance of the ITP kernel with the Intersection SubTree
kernel in [
Algorithm 2 de nes the Intersection Tree Path with Bag-of-Words kernel (ITP-BoW), a method for dealing with literals by treating them as a term vector. For comparison, we introduce a similar extension to the Weisfeiler-Lehman RDF Algorithm 2 Intersection Tree Path With Bag-of-Words Kernel Input a set of RDF triples R, a set of instances I and a max depth dmax Output a set of feature vectors F corresponding to the instances I Comments pathMap is a global map between paths of vertices and edges and integers { set pathIdx = 1, litIdx = 2 { for each i 2 I { create a list of new feature vectors fvs { do processVertex (i; i; []; fvs; dmax ) { concatenate all feature vectors in fvs to one feature vector fv { add fv to F function processVertex (v; root ; path; fvs; d) { if d = 0, return { for each (v; p; o) 2 R { if o is root , set path = [path; p; rootID ] { if o is a Literal, set path = [path; p; literalID ] { else, set path = [path; p; o] { if pathMap(path) is unde ned { set pathMap(path) = pathIdx { set pathIdx = pathIdx + 1 { set fvs(1)(pathMap(path)) = fvs(1)(pathMap(path)) + 1 { if o is a Literal do processLiteral (o; path; fvs) { else do processVertex (o; root ; path; fvs; d 1) function processLiteral (literal ; path; fvs) { create term vector tf for literal { if litMap(path) is unde ned { set litMap(path) = litIdx { set litIdx = litIdx + 1 add tf to the feature vector fvs(litMap(path)) kernel, dubbed Weisfeiler-Lehman RDF with Bag-of-Words (WL RDF-BoW). The Weisfeiler-Lehman algorithm iteratively rewrites vertex and edge labels by creating a new label using the labels of their neighborhoods. The counts of these rewritten labels introduce a feature vector, similar to the counts of the paths in ITP. To extend WL RDF with term vectors for literals we also introduce a special literal label and create a term vector for the original content of the literal. Just as in Algorithm 2 we need a list of feature vectors at each iteration of WL RDF. Instead of indexing these feature vectors using a map from paths to integers, we use a map from labels to integers, where the labels are the (rewritten) labels of the literal vertices at each iteration.
The Intersection SubTree is implemented as suggested in [
We apply TF-IDF weighting to the ITP-BoW kernel, because that increases performance. However, the WL RDF-BoW kernel performs slightly better without TF-IDF.
All of the kernels and experiments where implemented in Java and the code
is available online.3 The Java version of the LibSVM [
For our rst experiment we repeat the a liation prediction experiment from
[
As we do for the ITP kernel, we set the label of the root vertex for each
instance to an identical special root label for the WL RDF kernel. Furthermore,
for the WL RDF kernel we test the number of iterations setting h with: 0; 2; 4; 6.
The intersection subtree kernel has the discount factor parameter which is set
to best setting as reported in [
We use the C-SVC support vector machine algorithm from LibSVM to train a classi er for each kernel. Per kernel we do a 10-fold cross-validation which is repeated 10 times. Within each fold the C parameter is optimized from the range: f10 3; 10 2; 0:1; 1; 10; 102; 103g by doing 10-fold cross-validation. The different classes are weighted with the inverse of their frequency. All kernels are normalized.
Table 1 presents the average accuracy and the average F15 scores for each class. The best scores and those that have no signi cant di erence with these scores are indicated in bold typeface. The best scores for the two intersection tree path kernels, and those that have no signi cant di erence, are indicated with an italic type face. A Student t-test with p < 0:05 is used as a signi cance test.
The RDF Weisfeiler-Lehman kernel clearly shows the best performance in this task. The intersection tree path kernel performs on a par with the intersection subtree kernel. Adding the bag-of-words representation of the literals to the kernels does not increase performance.
5 This is the average of the F1 scores for each class. depth acc.
F1 acc.
F1
1
2
3
The next experiment is a repeat of the lithogenesis prediction task in [
Table 2 presents the results. As in the previous experiment, the WL RDF kernel shows the best performance. Also, similar to the previous experiment, the intersection tree path kernel shows similar performance to the intersection subtree kernel. Adding the term vectors for the literals does increase performance somewhat, however, it is not signi cant. 3.3
For our third experiment we use data provided for task 2 of the linked data data-mining challenge 2013.7 We use only the dataset provided as training data,8
7 http://keg.vse.cz/dmold2013/data-description.html 8 The test set labels are not available at the time of writing. depth 1 2 3 1 2 3 which contains 208 instances of government contracts. Of these instances 40 are labeled multicontracts. The task is to predict whether a contract has the property that it is a multicontract. The experimental setup is identical to the two tasks presented above. There is one di erence, for this dataset the performance of the WL RDF-BoW kernel could be signi cantly improved by applying TF-IDF normalization.
Table 3 shows the results for this experiment. Because the scores were not normally distributed very well, we used a MannWhitney U test as our signi cance test. This multicontract prediction task is di cult. The baseline for this task is already an accuracy of 0.81 and an F1 score of 0.50 and only somewhat higher scores are obtained. The best results are achieved by the bag-of-words kernels, achieving especially higher F1 scores than the non-bag-of-words kernels. Again, the intersection tree path kernel performs similar to the intersection subtree kernel. 3.4
As our nal prediction experiment we replicate the geological theme prediction
experiment in [
The experimental setup of this experiment is similar to the previous three.
However, instead of repeating the task 10 times on the whole dataset, we take
10 random subsets of 10% of the data. Furthermore, we use the LibLINEAR [
Table 4 present the results. We again use a MannWhitney U test as our signi cance test. The best performance is achieved by the intersection tree path kernel, however, the scores do not di er signi cantly from the best scores for the two WL RDF kernels. Again, the regular intersection tree path kernel performance is similar to the intersection sub tree kernel. 3.5
To test the runtimes of the di erent kernels we computed them with the highest settings (depth 3 and h = 6) on the dataset of the theme prediction experiment. The runtimes are measured on di erent fractions, 0.1 to 1, of the dataset.9 We do not include the kernels with the bag-of-words representation of the literals, since we did not fully optimize the performance of the term vectors, and hence the comparison would not be fair. For the intersection path tree and the WL 9 The fraction 1 is 10% of the total dataset, since we use the datasets from the previous experiment. 0.990 0:996 0:996 depth RDF kernel we show the computation time for computing the feature vectors and for computing the kernel matrix, which includes the feature vectors.
Figure 1 presents the results. The intersection tree path feature vectors are the fastest to compute by a large margin, around 10 times faster than the WL RDF feature vectors. The computation time of the intersection subtree kernel scales quadratically with the number of instances and is also clearly slower than the WL RDF feature vectors for more instances. It is interesting to see that for both the WL RDF kernel and the ITP kernel the computation of the kernel (i.e. taking the dot product of the feature vectors) becomes the largest component of the computation time for large datasets. The computation of the feature vectors scales linearly with the amount of instances, whereas the dot product computation scales quadratically. For large numbers of instances with sparse feature vectors, linear learning algorithms (e.g. LibLINEAR), which work directly on feature vectors, are more e cient than algorithms working with a kernel/dot product (e.g. LibSVM). So for learning with larger numbers of instances there is a large computational bene t in having an explicit feature vector representation, which is both faster to compute and faster to learn with. 0.1
WL RDF FV WL RDF kernel
ITP FV ITP kernel
IST We presented a graph kernel for RDF based on counting the paths in the tree starting from the root instance vertex. In our experiments this kernel has similar performance to the previously introduced intersection subtree kernel, but is much faster to compute. However, in three experiments, the Weisfeiler-Lehman RDF kernel shows better performance. In one experiment the intersection tree path kernel achieves similar scores to the WL RDF kernel. Even though the WL RDF kernel also computes the feature vectors directly, its computation time is around a factor 10 longer than the intersection tree path kernel. Therefore, we think that our kernel is a good baseline kernel for learning from RDF.
Furthermore, we introduced an extension to the intersection tree path kernel to treat literals as separate bag-of-words vectors. In two experiments this does indeed increase performance over the regular intersection tree path kernel.
More research is required into what property of RDF datasets makes that the Weisfeiler-Lehman kernel outperforms the tree type kernels by a large margin in some tasks, but not in others. Manual inspection of the datasets used suggests that the multicontract prediction dataset is relatively hierarchical or tree-like in nature, whereas the a liation prediction dataset has a more graph-like structure, with more cycles. This could be an explanation of the di erence in performance.
We also want to investigate the selection of subsets of predicates and objects to consider during the construction of the trees. There are a large number of predicates and objects that occur very infrequently and are potentially better treated as the same predicate/object or just removed from the tree. Given the fast computation time and relatively low memory requirement of the intersection tree path kernel an obvious next step for research it to test its feasibility on very large datasets, with millions of triples or more.
Acknowledgments This publication was supported by the Dutch national
program COMMIT. We thank the authors of [