The decomposition of tensors has on multiple occasions shown state of the art performance on classical Semantic Web tasks such as link prediction. However, the structure of the LOD cloud has not been taken into account in these developments so far. In particular, the decentralized architecture underlying Linked Data suggests that the incorporation of distributed information into these decompositions might lead to better factorization results. The goal of this thesis is hence to develop and evaluate models for joint tensor factorization on RDF graphs that arise from parameter estimation in statistic models or algebraic approaches. In this paper, we focus on presenting the problem we address formally and on discussing preliminary experiments on semi-synthetic data. Our experiments yield promising results inspite of being derived from an ad-hoc approach.
The Semantic Web landscape is populated by large interlinked RDF graphs containing partly redundant and often complementary knowledge. Since many knowledge graphs contain subgraphs of information on the same entities, we argue that it would be desireable to obtain a more complete picture for the relations between these resources while performing typical semantic tasks like knowledge extraction, entity matching or link prediction. Embedding the entities of those graphs into latent spaces, that consider relations over multiple knowledge bases, opens up new avenues for improvement on established methods for this family of semantic tasks, while simultaniously lending itself to new tasks like the generation of synthetic knowledge graphs for benchmarking or the detection of graph patterns. On the other hand, latent feature models have shown state-of-the-art performance on the aforementioned tasks, especially when processing very large graphs [13][7]. However, the state of the art focuses on one graph at a time and commonly does not take the topology of the Linked Data Web into consideration.
The aim of this thesis is to develop factorization approaches that can efficiently process groups of graphs by performing the decompositions of their adjacency tensors jointly and apply these decompositions in knowledge extraction and enrichment tasks. The intuition underlying this work is that by extracting latent features with respect to several graphs concurrently, we allow implicitly for information to permeate the boundaries of single graphs and thus achieve more accurate factorizations. To achieve this goal and jointly factorize even the largest knowledge bases, we aim to develop scalable and time-efficient approaches that are able to incorporate meta-information like links between entities in different knowledge bases and literals, while also hailing from sensible and interpretable models. Thus, this thesis will focus on the research of joint decompositions of knowledge base adjacency tensors and their applications on semantic tasks like the detection of graph patterns to achieve better results on real world applications like query answering systems. 2
The results of this research could lead to latent feature models that incorporate
information that is spread out globally over multible RDF graphs. A large number of tasks
(especially tasks which require abstract representations of resources) can profit from these
results, including (
The runtime and accuracy of the provided solutions will be the deciding factors pertaining to their adoption by the Semantic Web community and the corresponding industry. Hence, we aim to develop time-efficient methods and apply them to the tasks aforementioned. Furthermore, to reason about these algorithms it would be desireable to derive them explicitly from model hypotheses on the structure of real-world knowedge bases. Thus, we will develop factorization models that abide by the characteristics of Linked Data. We hope that our results will play a key role towards a new generation of tools for processing large amounts of interlinked data. 3
There is a wealth of knowledge on tensor factorization in the literature. For the seminal survey on this topic, see Kolda et al. [6]. On the topic of single tensor factorization, most models are based on either the DEDICOM [2] or the CP [3] family of decompositions. Nickel et al. proposed a relaxed DEDICOM model, refered to as RESCAL [12], that is shown to be highly scalable [13], while still exhibiting state of the art performance on smaller datasets. Building on this London et al. [10] suggested a similar model, adding a bias term and using the learned model as input for a neural network. Kolda et al. [5] proposed a CP Model, to identify citation communitys and measure document similarity. Kuleshov et al. [8] proposed to find the CP factors of their model, via simultaneous matrix diagonalization.
On the topic of joint tensor factorization, Khan. et al. [4] proposed a bayesian model for the problem of multi tensor factorization. They relaxed the constraints of the problem to use normal distributions for inference of the CP factors. Also the joint factorization of matrices and tensors has shown improvements over singular approaches, see [1].
To adress the issues stated above, we plan to analyze and generalize existing approaches and to use the insights gained there to develop new techniques and benchmark their performance on knowledge extraction and integration tasks against the current state of the art. As such, the research questions and corresponding subquestions at the heart of our work are as follows: – ”What existing approaches can be applied to joint factorization?”
What existing approaches can be interpreted as stemming from statistical models? By increasing the sample size one could generalize them to multiple knowledge bases.
Can we derive update rules that are computable on large datasets by combining different cost functions or in a distributed manner? – ”How can we use the resulting embeddings to improve upon existing tasks and what new avenues can be explored?”
Can one improve the performance of the translation of natural-language queries into formal query languages (SPARQL) by using embeddings that respect the spread of RDF data on the web? Can we use these latent embeddings for the generation of synthetic graphs which still capture the structure of RDF Data on the web? This will be useful for benchmarking various querying systems and the like. 5
The basic hypothesis behind our work is that using the architecture underlying the Linked Data Web can lead to the computation of better embeddings latent embeddings. We hence aim to develop novel methods for tensor factorizatiion that make use of distributed information to compute embeddings. The approaches we develop will aim to be time-efficient and easy to distribute so as to scale to billions of triples. Moreover, we will consider datasets that are updated regularly and aim for deriving updates rules or modularization techniques that will ensure a efficient update of latent features. 6
To begin testing the potential of a simple variant of joint decomposition, we chose to use the proven RESCAL-ALS [12] method on a data dump of the Side Effect Resource SIDER.1 From that data, we built an adjacency tensor that does not differentiate between literals and entities. Ee arrived at the full tensor with a shape of 11 30378 30378 and models the complete knowledge contained in the RDF graph. To model delocalized information, we produced two more tensors X; Y of the same shape by deleting a percentage p of entities from the full tensor twice, taking care that entities deleted in 1 http://linkeddatacatalog.dws.informatik.uni-mannheim.de/dataset/fu-berlin
sider/resource/ee6c1709-f2a6-4790-8549-152232dd9d93
The task at hand was to reconstruct the global knowledge contained in the full tensor based exclusively on the partial knowledge contained in X and Y . To that end, we chose to search for solutions of the ”RESCAL”-form, that solve the problem (R~; A~) = arg (mR;iAn) kARAt
Xk22 + kARAt
Y k22 + reg(A; R) with A 2 Rr 30378, R 2 R11 r r for some r < 30378 and reg(A; R) = kAk22 + kRk22
(R~; A~) = arg (mR;iAn) kARAt
X + Y k22 + reg(A; R)
2
This allows us to approximate solutions of (
Xijk + Yijk 2 2 = (ARAt)ijk Xijk 2 + (ARAt)ijk Yijk 2 + 1 2 (Xijk
changes of F1-measure in the joint approach at t = 0:5 can be explained by the fact that
the algorithm tries to approximate the tensor (X + Y )=2. Take note that
X + Y
2
ijk
80
>
<
= 1
>: 12
if Xijk = Yijk = 0
if Xijk = Yijk = 1
if Xijk 6= Yijk
(
To remedy that situation we used the ad-hoc approach of learning the tensor max((X; Y ))ijk = max(Xijk ; Yijk )5 under the same quadratic loss function, using the same RESCAL-ALS algorithm. A sample of the results obtained are contained in the following table 5 take note that, by our synthetic construction of X and Y, max(X,Y) will represent the full knowledge graph, thus the parameter p is irrelevant here.
As one can see, the results improved compared with learning the arithmetic mean. This hints that there is improvement to be had by reweighting the entries in the joint decomposition, which we will explore in our future work. 7
(
S := ( ; P ( )) ; with := Yf0; 1gk n n m equipped with a propability measure
p : P ( ) ! [0; 1]; fX1; : : : ; Xmg 7! p(fX1; : : : ; Xmg): This is the general setting and by choosing different parametric families of propability measures, one can use inference methods to obtain estimates for the parameters. Take note that the choice of S makes this approach novel, because the usual methods for statistical inference on semantic adjacency tensors use measurable spaces of the form (f0; 1gk n n; P (f0; 1gn; p) to model the propabilities for links on a single tensor. This is well known and appears frequently in the Semantic Web literature. For instance in [11], the authors use the propability function p(XjA; R) :=
Y p~(xijkj hAi; RkAj i) i;j;k with p~(xijk = 1j hAi; RkAj i) := (hAi; RkAj i). Then they chose to estimate the parameters A and R by minimizing the log-likelihood. By extending the sample space to multiple tensors, one has a larger sample size for each individual entry and that will lead to better parameter estimations.
Furthermore, if one has to deal with multiple knowledge bases, the question of confidence arises. To solve the problem of observing a link in knowledge base A and not in knowledge base B, one would have to introduce confidence values to the model, to make informed predictions.
Another approach will be modelling the random events in our model as Markov processes. This would be appropriate to model situations where the source of our data are multiple versions of a knowledge graph, at different points in time. The ability to incorporate Markov processes of graphs into our model, is theoretical highly valuable, since they possess an unparalleled modelling power for real world processes. 8
To test our hypotheses, we will apply our derived algorithms in three stages. Stage one will be a test on synthetic or semi-synthetic data, where we will build tensors from real-world data, according to synthetic rules to model the existence of a tensor that contains the global knowledge and measure the performance of the model using the
Stage two will be a test on real world tensors which contain a large amount of related entities, e.g., YAGO [14] and DBPedia [9]. Thus, we are abstracting the existence of a global knowledge tensor, still keeping the same evaluation sheme as in stage one. Finally in stage three, we will test the latent factors we have benchmarked in stage two to fields such as relation extraction, entity linking and question answering to boost their performances. 9
As our preliminary results show, one can expect better latent embeddings by considering multiple sources of relational data. While there is a wealth of knowledge for the factorization of matrices or tensors, there is still relatively little work done on the joint factorization of tensors. Furthermore, by considering quite general propability functions, we can model sophisticated dependencies of different knowledge graphs. This will be the start of this PHD thesis.
Acknowledgements This work has been supported by Eurostars projects DIESEL (E!9367) and QAMEL (E!9725) as well as the European Union’s H2020 research and innovation action HOBBIT (GA 688227).
Also, I want to thank my advisors Dr. Axel-C. Ngonga Ngomo, Ricardo Usbeck and
the whole team at AKSW for all their helpful comments and fruitful coffee-driven
conversations.
6 just as in our ”Preliminary Results” section
9. J. Lehmann, R. Isele, M. Jakob, A. Jentzsch, D. Kontokostas, P. N. Mendes, S. Hellmann,
M. Morsey, P. van Kleef, S. Auer, and C. Bizer. DBpedia - a large-scale, multilingual
knowledge base extracted from wikipedia. Semantic Web Journal, 6(