The updates on knowledge graphs (KGs) afect the services built on top of them. However, changes are not all the same: some updates drastically change the result of operations based on knowledge graph content; others do not lead to any variation. Estimating the impact of a change ex-ante is highly important, as it might make KG engineers aware of the consequences of their action during KG editing or may be used to highlight the importance of a new fragment of knowledge to be added to the KG for some application. The main goal of this contribution is to ofer a formalization of the problem. Additionally, it presents some preliminary experiments on three diferent datasets considering embeddings as operation. Results show that the estimation can reach AUCs of 0.85, suggesting the feasibility of this research.
Knowledge graphs (KG) and ontologies1 change over time. Such graphs are updated by inserting new knowledge and removing or changing outdated and wrong information. As an example, consider the computation of a (logical) materialization: a small change in the schema can have a big impact on the KG, significantly vary the number of materialized axioms or even its consistency. However, not every change in the KG leads to significant changes in the materialized graph. The computation of the materialization consumes considerable amounts of resources. Consequentially, the indication of a potentially big diference from the old materialization to the new one would signal the necessity for recomputation.
This topic is not at all new, but so far studies come from diferent directions. It relates to stream processing since the process executed over a stream 1 We use the terms knowledge graph and ontology interchangably because of the different datasets used in the case study.
Copyright © 2019 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
"&5
)
("5
&
"&5
of data changes results as the data comes in [
In this poster, we present a formalization of the problem of estimating the
impact on a operation result over an evolving KG. Furthermore, we show first
experiments with three diferent datasets on embeddings operations [
Fig. 1 shows the conceptualization of the impact prediction problem. A
knowledge graph K is a set of triples (s; p; o), where s and o are two resources connected
by a predicate/relation p. We define an evolving knowledge graph K as a sequence
(K1; K2; : : : ; Kt; Kt+1; : : :), where Kt denotes the KG at the time instant t. This
definition of evolving KG is similar to the one of ontology stream proposed by
Ren and Pan in [
We define op( ) as a function which applies to a KG and produces a result R. op( ) takes as arguments a KG and zero or more additional parameters if necessary. When the operation op( ) is applied to K, it will create a sequence of results R = (R1; R2; : : : ; Rt; : : :), where Rt is the result of op( ) on Kt.
Given Kt and Kt+1, the respective results Rt and Rt+1 can be the same (if the changes t do not afect the result of op( )), or they can difer. We model this comparison through the function impactop(Rt; Rt+1), which represents the impact that the evolution had on the results of op( ).
Therefore, the goal of this research is to build an estimator of impactop( ), which does not require the computation of all op( ) results. We indicate the estimator with imdpactop(Kt; t) since it takes as arguments a knowledge graph and the set of changes leading to a new version. Moreover, op( ) should be considered as well, since diferent operations may lead to diferent impact functions.
Toward Predicting Impact of Changes in Evolving Knowledge Graphs
We discuss our model in one case study considering embeddings as op( ).
Definition of Impact. To evaluate embeddings of two snapshots, we make the
comparison using neighborhoods. Taking the 100 closest neighbors of a particular
node, we compare how many of these are also in the neighborhood of the same
node in the embedding of the next version. The aggregation for the whole graph
is then done via the sum and the mean, producing two impact measures.
Definition of Features. 2 Diferent measures have been established in the
network analysis community such as degree centrality or clustering indicators.
Further, we calculate sparseness and graph entropy measures. To use these measures
as features, we calculated a simple diference between the graph measure value in
two versions of the graph. Other features are based on change actions. A change
action is an item in . We used the classification introduced by Hartung, Gross,
and Rahm [
Data. We test the impacts and features defined above through experiments on
three datasets: Bear-B-instant (BB), the Gene Ontology (GO) and an anonymized
and de-identified WebProtege Ontology (WP). The BB dataset was produced
using the 100 most volatile subjects of the DBpedia [
The imdpact estimator. We split the data into a training and testing datasets, where the training dataset contains 70% of the data points. For learning, we use 10-fold cross validation. The area under the receiver operating characteristics curve (AUC; also called c-statistic) is calculated to compare the models after testing. To calculate the AUC for regression, we determine a threshold for the observed impact to turn the regression into a binary classification. Features were selected using Pearson correlation (corr ) and 10-fold Ridge regression (ridge). Results. We test the performance of imdpact by running three experiments on the considered datasets and impact measures. Table 1 reports the AUC results of the experiments. For the BB dataset, performance does not exceed an AUC of 0.63. On the other hand, for WP performance reaches 0.851. With GO, the only dataset including change action features, the performance is 0.8 and higher on multiple occasions. 2 The complete list of the features can be found in the source code at http://tinyurl.
com/y29t77v4
Following the butterfly efect, a small change in a KG can lead to large diferences in operation results. This poster presents the problem setting and definition along with a case study using embeddings over three datasets and two impact measures. The successful experiments show that it is possible to predict the impact. We can therefore decide when an update to the operation is necessary, potentially saving valuable resources.
This study triggers new questions. For instance, is it possible to construct a general model spanning over diferent datasets and operations? We need to gain a deeper understanding of the common factors among datasets and operations. Which is why we plan to run further experiments in this direction.
This study clearly shows that the investigation of KG-evolution and the impact of changes on KGs is fruitful and needs to be intensified.