Knowledge graphs (KGs) are at the core of numerous applications and their importance is increasing. Yet, knowledge evolves and so do KGs. PubMed, a search engine that primarily provides access to medical publications, adds an estimated 500'000 new records per year-each having the potential to require updates to a medical KG, like the National Cancer Institute Thesaurus. Depending on the applications that use such a medical KG, some of these updates have possibly wide ranging impact, while others have only local efects. Estimating the impact of a change ex-ante is highly important, as it might make KG-engineers aware of the consequences of their actions during editing or may be used to highlight the importance of a new fragment of knowledge to be added to the KG for some application. This research description proposes a uniifed methodology for predicting the impact of changes in evolving KGs and introduces an evaluation framework to assess the quality of these predictions.
Knowledge graphs (KGs) or ontologies 1 capture the knowledge of a particular domain. They are at the core of applications, such as search, logic-based reasoning, and inductive model training. KGs represent the knowledge of a universe that evolves. Thus, such KGs capture the current knowledge of a particular domain: their content can change to (1) include new facts or axioms, (2) adhere to the changing world, or (3) correct wrong or imprecise knowledge. It is natural to ask ourselves how this evolution afects the services built on top of it.
Let us consider the following example: National Cancer Institute thesaurus
(NCIt) [
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). updates to existing ones. Therefore, NCIt needs revisions with a subsequent need to also update the recommendation and materialization tasks built on top of it.
The results of operations built on top of KGs, e.g. search results, materialization, machine learning models, can shift strongly due to those changes. Taking actions to adapt to changes may be expensive: in some cases results can be incrementally updated, while in others they must be recomputed from scratch, leading to a potential high usage of resources or costly revisions of previous decisions. It is worth noting that not every change has the same impact, e.g. renaming a concept would have a minimal impact on the materialization, while removing a central node could significantly change the materialization.
Initial research, e.g. [
To enable the study of impact over diferent tasks and KGs, a unified methodology is necessary. This would ensure that the results are comparable to each other. Therefore, the impact prediction should be embedded in a framework enabling consistency in approach and comparison of results. Additionally, adaptation to real world scenarios would be made easier. 2
The challenge I want to address in my PhD studies is the development of a
methodology to predict the impact of KG changes on the results of respective
functions. Using a unified setting, I can develop such methodologies and compare,
evaluate, and improve them iteratively as done in design science approaches [
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. In Fig. 1, I 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 [
As shown in Fig. 1, I define the operation op1( ) as a function which accepts a KG as argument and produces a result R. When the operation op1( ) is applied to K, it creates a sequence of results R = (R1; R2; : : : ; Rt; : : :), where Rt = op(Kt). Examples of such operations might be the materialization, the computation of an embedding space, or some recommendations. Therefore, the Fig. 1 also shows a second operation op2( ) that is defined accordingly.
Given Kt and Kt+1, the respective results Rt and Rt+1 can be the same, i.e. when the changes t do not afect the result of op1( ), or they can difer. I model this comparison through the function impactop1 (Rt; Rt+1), which represents the impact that the evolution had on the results of op1( ). In the case of op1( ) being the calculation of embeddings the impactop1 (Rt; Rt+1) would be the comparison of the embedding of Kt and Kt+1 for example using the overall loss, neighborhood similarity, or link prediction hit rate. In a practical setting, it may be too expensive to compute the impact at every time instance or I may want to know the impact before applying a change.
I indicate the estimator with imdpactop1 (Kt; t), since it takes as arguments a KG and the set of changes leading to the next version. Moreover, op1( ) should be considered as well, since diferent operations may entail diferent impact functions. Ideally, my research would lead to the definition of general impact estimators imdpact( ), which are independent of any specific operation as shown by op1( ) and op2( ) in Fig. 1.
Taking this formal setting, the problem of my research lies in the definition of a general methodology applicably within this setting. Inside the methodology, impact has to be defined together with features describing , the feature selection procedure, and the prediction algorithm. As mentioned before, the methodology will be improved iteratively by applying it to use cases with adjusted factors (impactop1 ( ), op1( ), , K). Each iteration will yield estimators, which performances I can compare and consequently refine the methodology. The performance of predictors is given with the distance between estimation imdpactop1 ( ) and real value impactop1 ( ). The comparison of methodologies is based on the performance of predictors built by them.
">% ) ("% > ">%
" " ) )(" ("= % " 89A(","'%)
≅ 89:(","'%)
≅
/(, )
"
"'%
)
("%
'
%
"'%
"'%
)
("=%'
"'=
"'=
)
("=
'
Many researchers have focused on topics close to my proposed one. Essentially,
they can be split in two groups, those being research on the evolution of KGs
and research about the impact of KG evolution on KG-based tasks.
Evolution of KGs. Zablith et al. [
The related work shows that it is possible to predict the impact of changes for specific tasks and knowledge graphs. My first research question builds on those studies, and generalizes them to define a methodology. The goal is to predict the impact on tasks of KG changes using a general methodology that can be applied on diferent tasks and KGs.
RQ-I: Can I define a unified methodology to develop predictors for the impact of a task on an evolving knowledge graph?
The development of the methodology is a design science task [
The implementation of such a methodology has various requirements. It should be general enough to be applicable over diferent tasks and KGs by allowing the definition of impact metrics for every task. In addition, the definition of features is another factor inside the methodology that can be compared and therefore also improved between interations.
I plan to investigate this question in practical settings by studying: (1) KGs of diferent topics, maintenance processes, size, and structure; (2) features portraying diferent aspects of a change using detailed change information (change action features) or general graph measures; (3) operations op1( ) that difer in complexity, stochasticity, and incremental compatibility; as well as (4) impact measures varying in value range, e.g., Boolean, categorical, or continuous, and nature, e.g., structural or semantic. Implementing and improving the methodology using a broad range of possibilities would set the requirements for a generalized methodology, applicable to a wide number of cases.
Within the settings of these variations and the proposed methodology, I will then investigate the following hypotheses to answer if the said methodology can serve as candidate answer to RQ-I. Please note that this list is not exhaustive: H-I: The impact prediction performance (AUC) of a methodology using change action features is higher than the performance with general graph features. H-II: The impact prediction performance (AUC) of a methodology using a smal l KG is higher compared to the performance using a KG with twice as many axioms.
H-III: The impact prediction performance (AUC) of a methodology using a stochastic operation, such as embedding calculation, is lower compared to the performance with a logical operation, such as materialization. H-IV: The impact prediction performance of a methodology using t of size one is higher compared to the performance with using t of larger size.
The results leading to the answering of the hypotheses and of RQ-I will support my second research question. The methodologies set the foundation to study how features correlate among diferent knowledge graphs, tasks, and impact measures. This is captured in the second research question:
Computation of -.(⋅) ,-.(0, 0) RQ-II: Can I build a generalized model for predicting impact that is as accurate as models specifically built for one knowledge graph, task and impact measure? To arrive at a generalized model, investigating the relationship between change features and the impact is necessary. It would reveal which impact measures interact with which change features. In this interaction, the direction of the relationship between features and impact measures is important. Using a feature that correlates with the first impact measure positively but correlates with the second impact measure negatively would be counterproductive in prediction of a general impact. Therefore, I can identify features that are common among the prediction models of diferent task impacts.
H-V: A feature showing the same coeficient direction between KGs produces a better performance compared to features with coeficients going in opposite directions.
H-VI: A feature showing the same coeficient direction between tasks produces a better performance compared to features with coeficients going in opposite directions.
H-VII: A feature showing the same coeficient direction between tasks and KG produces a better performance compared to features with coeficients going in opposite directions. 5
I propose a first methodology, which I call CHIMP, to initiate investigation of RQ-I. The name is derived from change impact, since at its core it predicts the impact of KG changes on a task. CHIMP will be refined in future iterations. In Fig. 2, CHIMP provides a workflow to predict the impact using the setting shown. It is applicable to individual pairs of KG and operation without imposing requirements.
The bottom section of Fig. 2 shows decisions. These need to be made by one (or more experts) and used as input for CHIMP. An KG expert needs to define how the impact between task results should be measured. Further, a KG expert defines the features later used as input for the learning models. However, the decisions about feature selection and learning algorithm require knowledge about data science and its algorithms.
The middle section of Fig. 2 shows relevant steps of CHIMP: the evolving KG K is used to determine the set of potential features, while the operation op1( ) sets the basis to define impactop1 ( ). First, a training subsequence Ktr of K is used to identify the relevant features and train the prediction model. Secondly, CHIMP computes both (1) the impact impactop1 ( ) for each pair of consecutive KGs in Ktr and (2) the values of the potential features using as input the changes that update every version of Ktr to the successive one. Subsequently, CHIMP selects a set of candidate features by exploiting impact and potential feature values. Each candidate feature set is used to build several prediction models. Finally, CHIMP identifies the best model and feature set to be used for prediction. The upper part of Fig. 2 shows how to estimate impactop1 ( ) at runtime: the model takes an evolving KG Krun and the sets of changes as input. The selected features are calculated and fed into the already trained prediction model. For CHIMP to work, it requires an domain or task expert’s guidance with regard to the (1) definition of impact. The (2) definition of features, (3) choice of feature selection procedure, and (4) selection of prediction algorithms are steps that in future could also be automated. For now, these steps require the knowledge of data mining and machine learning.
To gain insights towards answering RQ-II, predictions from CHIMP over the diferent operations and KGs have to be analyzed in detail. By looking at the interaction between the impact and selected features, similarities between taskspecific and KG-specific predictions models can be identified and used. Ideally, I would find some features that are used across the models and show the same relationship towards the diferent task-specific impact measures. Therefore, the main step in answering the second research question is the thourough analysis of the feature selection inside each implementation of CHIMP. 6
The first part of the evaluation of the predictors built by CHIMP is a closer look
at the distribution of the impact. The distribution is a vital contributor in the
decision of which prediction approach should be used. For a normal distribution
linear regression is appropriate. If normality can not be detected a
transformation, like the log or square-root transformation, needs to be used on the impact
measure. However, I will also apply non-linear regressions, like polynomial or
principal component regressions that do not require a normal distribution, to
widespread data. If there are distinct peaks close to 0 and 1 impact, assuming
that the impact is a value in the range [
Before evaluating the prediction models, I take preventive measures against over-fitting. I split the data into a training and testing datasets, where the training dataset contains 70% of the data points. Additionally, for learning, I use 10-fold cross validation. This is especially beneficial for small datasets. Testing of the learned models is then done on the remaining 30% of the dataset. These are decisions made within Selection of Prediction Algorithm in CHIMP.
I compare the performance of the diferent models and approaches using the area under the receiver operating characteristics curve (AUC). To calculate the AUC for regression, I determine a threshold for the observed impact. I then treat the predicted values as probabilities and calculate the AUC as if it was a classification task. The goal is to only signal the impact (value of 1) when a recalculation of the task is necessary. The detailed comparison of models is part of the last step of CHIMP’s middle section. 7
I began my research by selecting two tasks, materialization and embeddings. Materialization is the calculation of a finite set of additional axioms that can be inferred from the ones that are already present. An embedding is the representation of the entire graph in a vector space of multiple dimensions. The tasks are difer significantly. The former creates a graph following a deterministic process, while the latter produces vectors according to a stochastic process. It follows that comparison is not directly possible. Subsequently, I describe potential impact measures for the two tasks; next, I describe two experiments I performed on them, considering two diferent datasets. Finally, I describe the analysis of the features I extracted for the scenarios.
Impact for Materialization. Since the result of a materialization is a finite
graph, I can define the impact in terms of a graph distance measure. Dehmer,
Emmert-Streib, and Shi [
I(K) = 0R(K) =
X u2V (K)
1
pd(u)
;
where u is a node from the set of nodes V (K) in the graph K and d(u) is the
degree of u. This measure ranges from 0 to 1. I have also considered the Randić
and Wiener impact, which are also proposed in [
Pu2V (K) N (ut) \ N (ut+1) jV (K)j (3) where ut is the node u in Kt and ut+1 is the same node in Kt+1. Nt(u) is the neighborhood of the node u in the embedding of Kt. jV (K)j is the number of nodes in K. The measure is normalized to the range [0; 1].
I investigated the overall loss of embedding and link prediction performance.
In addition, there are common measures to compare embeddings, but they are
usually used to compare diferent embedding approaches over the same KG. I
identified the extension of such approaches to compare embeddings created by
the same techniques on two snapshots of the same KG as future work.
Experiments. I considered three datasets: Bear-B-instant (BB) [
I applied two feature selection procedures: Pearson correlation and ridge regression. Significance was the indicator for a feature to be used in prediction. For materialization, classification was used because of the impact distribution of BB and WP datasets showing peaks at 0 and close to 1. I classified the impact larger than 0.5 as 1 and smaller than 0.5 as 0. The choice of the threshold is based on the meaning of impact. When doing classification, the model decides if there will be impact (1) or if there won’t be any impact (0). Including numbers below 0.5 would give the same attention to changes with lower impact compared to changes with very high impact. Therefore, the cutof was decided at 0.5. However, this number is for now arbitrary and further investigation is necessary to determine if lower or higher thresholds would be suited better.
SVM with a radial kernel, k-Nearest Neighbors, and Random Forest were the three prediction models built using the features sets selected by correlation and ridge regression. With all three algorithms and two feature sets an AUC value of over 0.97 was achieved. For the impact on embeddings, regression was necessary. For the BB dataset, performance does not exceed an AUC of 0.64. On the other hand for WP, prediction models shows a performance of AUC = 0.85.
The prediction of the impact for embeddings performed significantly worse than for materialization. The stochastic nature of embedding computation results in less predictable outcomes compared to deriving a materialization. Hence, impact prediction of comparable consistency cannot be expected. Analyzing Selected Features. Table 1 shows the selected features for sets that were used in the predictions. As mentioned before, the features are common social network features with the addition of entropy and spareness to also include feature outside of this domain. For all these features, the semantics inside the KG was completely ignored and the KG was turned into a directional unnamed graph. The first column shows the names of the features. For Pearson correlation (Corr ), significance was the selection criterion and the correlation value was not considered. However, the +/- sign indicates the direction of the correlation value. For Ridge regression (Ridge, a coeficient determined selection as well as +/- entry in the table. The comparison between the two feature selection procedures Corr and Ridge is not advisable, because the respective approaches are very diferent in nature. In both selection approaches along with both datasets, features between the two operations show the same direction of influence on the impact. Therefore, it can be concluded, that the indicated features describe the impact partially in the same way. For Corr in BB, three features are in common as shown in Table 1. For Corr in WP, only the cluster coeficient is in common between the tasks. Investigating the ridge models, three features are in common for BB and six for WP. These findings are of great importance. They show that the impact measures have common indicators, which could be used in a real world application. Focusing on fewer features allows potential advantages for implementation in e.g. impact detector inside an ontology editor.
I have also analyzed the features which are more concerned with the nodes
that are directly afected by a change. However, I was only able to calculate
such features for GO using COnto-Dif [
As with the butterfly efect, a small change in a KG can lead to large diferences in operation results. The goal is therefore to decide when an operation needs to be recalculated due to the KG evolution. In this research description, I propose the iterative development of a methodology, which can be used to build a predictor for the impact of changes of KGs. This is a crucial step towards understanding the magnitude of changes, making KG engineers aware of the possible impact.
So far, I have used a first version of the methodology to build various prediction models across three diferent datasets and two operations. The experimental results confirmed that CHIMP can be used to study the impact of changes. I will continue by revising this first methodology and by applying it to further operations, diferent impact measures, new features and prediction algorithms.
The biggest challenge so far has been the definition of an appropriate impact measure given an operation. Looking into practical use cases will help to distinguish the respective understanding of impact. At the same time, obtaining suitable datasets has proven dificult. There are many KGs of diferent contexts and sizes, each of them recording and reporting the evolution history in a diferent way. This requires an adaptation of KGs and their evolution before usage.
The recent advances by related studies have shown that the desired research is indeed feasible. In addition, my current results are promising and provide preliminary answers to both research questions. In future, I want to refine the introduced methodology and broaden the research to encompass additional KGs, operations and features.
Acknowledgments. I want to recognize the help of my supervisor Prof. Abraham Bernstein, PhD and Dr. Daniele Dell’Aglio of the University of Zurich.