Enriching and cleaning datasets are tasks relevant to most largescale knowledge graphs, which are known to be noisy and incomplete. In this paper, we propose one approach to fix wrong facts which originate from confusion between entities. This is a common source of errors in Wikipedia, from which DBpedia and YAGO are extracted, and in open information extraction systems, e.g. NELL. Our approach generates candidate subjects and objects to fix triples by exploiting disambiguation links and approximate string matching. We run our approach on DBpedia and NELL and perform a manual evaluation of the generated corrections.
• Information systems → Data cleaning; • Computing methodologies → Semantic networks; Statistical relational learning; Machine learning;
Knowledge graphs are known to be both often incomplete and incorrect. Several link prediction and error detection methods have been proposed, however, few of them explicitly focus on error correction or address the problem of choosing which absent facts should be added to the knowledge graph.
The problem is that the number of possible relation assertions grows quadratically with the number of instances nc = ni2nr − nf , where ni is the number of instances, nr the number of relations and nf the number of existing facts in the graph. For large datasets such as DBpedia, Wikidata and YAGO, computing the confidence score of all these facts is challenging. While pruning possible facts which violate ontology constraints, especially domain and range restrictions of relations, can significantly reduce the search space, the problem is still very challenging. To illustrate the size of the search space, in DBpedia (2016-10) nc ≈ 4.4 × 1017 facts; when ifltering those triples which violate the domain and range restriction the number is reduced to nc ≈ 2.8 × 1017, which is still too large to compute confidence for all those candidates.
A promising approach for enriching a KG with some of its missing facts is the correction of erroneous facts. Some of the wrong facts which exist in a KG can be corrected. The error originates from some problem in the knowledge acquisition process, or in the source data. A good example of the latter are errors in Wikipedia, which serves as the main source of DBpedia and YAGO. If any of the links in the infobox are wrong, the extraction process generates a wrong fact. NELL, on the other hand, has text as main source of information and in many cases the source text has correct information, which cannot be extracted correctly.
In both cases it is common that an instance is confused with another one of a similar name (i.e., label or IRI). For example, the fact formerTeam( Alan_Ricard, Buffalo_Bill) is an erroneous fact from DBpedia which originates from a typo in Wikipedia: when referring to the NFL team Buffalo_Bills, the s was missing, therefore, the NFL team was confused with the character Buffalo_Bill. In NELL the entity insect_raccoon exists because of problems when extracting the fact that raccoons prey on insects, and is confused with mammal_raccoon.
Some relation assertion error detection approaches, such as
PaTyBRED [
Therefore, it is relevant to make a careful analysis of detected errors, identify the source of each error, and if possible correct them. In this paper, we propose CoCKG (Correction of Confusions in Knowledge Graphs), an automatic correction approach which resolves relation assertion errors caused by instance confusion. The approach relies on error detection methods as well as type predictors to asses the confidence of the corrected facts. It uses approximate string matching and exploits both searching for entities with similar IRIs as well as Wikipedia disambiguation pages (if available) to find candidate instances for correcting the facts. 2
In the knowledge graph context, there are mainly error detection and link prediction approaches. Both are closely related to our problem: while error detection deletes wrong triples, link prediction aims at adding new triples. In both cases, the approaches learn a KG model which is capable of assigning confidence values to triples.
KG embedding models [
Rule-based systems, such as AMIE [
Wang et al. [
Our approach consists of first running an error detection algorithm (PaTyBRED in the case of this paper), selecting the top-k facts most likely to be wrong. In the next step, the error is heuristically verified to be an actual relation assertion error and not caused by missing type assertions in the object or subject with a type predictor tp. In the final step, candidate entities are retrieved, and if any of the candidates significantly improves the likelihood of the triple being right, we replace it by that candidate. The function correct_triple in Algorithm 1 gives an overview of how CoCKG works. The parameter K is the set of all triples in the knowledge graph, Ter r is the set of triple and confidence pairs generated by the error detection model (ed), tp is the type predictor, mc is the minimum confidence threshold, and mcд the minimum confidence gain threshold, i.e. the ratio of the new and old triple scores. In the next subsections we discuss the other parts in more details.
After selecting the k triples most likely to be wrong, we first check
if their confidence is low because of missing or wrong instance
types (subject or object). In order to do that, we run a type predictor
tp on the subject and object instances. In this paper, we use as tp
a multilabel random forest classifier based on qualified links (i.e.
ingoing links paired with subject type and outgoing links paired
with object type), as described in [
Combining the type prediction process with the error detection also has the advantage that the newly predicted types can be validated on triples containing the instance whose types were predicted. This can help support, or contradict the type predictor, possibly detecting types which are wrongly predicted by identifying triples where the score is lowered with the new types.
One simple way to find candidate entities to resolve entity confusions is to use the disambiguation links. Since disambiguation pages are only available for Wikipedia-based knowledge graphs, and furthermore are not available for each entity (e.g. Ronaldo has no disambiguation page), and in some cases the disambiguation pages miss important entities (e.g. the page Bluebird_(disambiguation) misses the entity Bluebird_(horse), hence, we cannot correct the fact grandisre(Miss_Potential,Bluebird)), we require an additional source of candidates.
Since in our experiments we consider DBpedia and NELL, which have informative IRIs (in the case of DBpedia extracted from the correspondent Wikipedia’s page), we search for candidate entities which have similar IRIs. Alternatively, it could also be done with entity labels. This would be useful in KGs which have uninformative IRIs (e.g. Wikidata and Freebase). For simplicity, in this paper, we refer to the informative part of an IRI as the “name” of the entity.
Retrieving all the instances of similar names can be a complicated
task. This kind of problem is known as approximate string matching,
and it has been widely researched [
When searching for entities similar to a given entity, we perform queries for every token of the entity’s name and we require that all tokens are matched. That is, for a certain entity to be considered similar, it has to contain tokens similar to all the tokens of the queried entity. A retrieved entity may have more tokens than the queried entity, but not less. The idea is that in general, when entering an entities name manually (e.g., in Wikipedia), it is common to underspecify the entity, but highly unlikely to overspecify it. E.g., it is more likely that Ronaldo is wrongly used instead of Cristiano_Ronaldo than the other way around. Furthermore, it reduces the number of matched entities.
We also perform especial treatment on DBpedia and NELL entity names because of peculiarities in their IRI structures. In DBpedia it is common to have between parentheses information to help disambiguate entities, which we consider unnecessary since the entity types are used in the error detection method. In NELL the ifrst token is always the type of the entity, therefore, for similar reasons, we ignore it. 3.3
At this point, for each assertion identified as erroneous, we have our list of candidate instances for subject and object from the disambiguation links and approximate string matching. We then compute a custom similarity measure s (e1, e2) between an entity e1 and a candidate e2. Each entity ei consists of a set of its tokens. The measure we propose consists of two components. The first is the sum of Levenshtein (dL ) distance of all matched tokens, and the second considers the number of unmatched tokens to capture a diference in specificity. The set of approximately matched token pairs is represented by µ (e1, e2) and the constant c is the weight of the second component. This measure is used to sort the retrieved candidates, to prune them in case there are too many, and to break ties when deciding which of the top-scoring candidates should be chosen. s (e1, e2) =
dL (t1, t2) + c
X (t1,t2) ∈µ (e1,e2) |e1 | − |µ (e1, e2) | |e1| (1)
In case the relation has domain or range restrictions, we remove the candidates which violate these restrictions. Later, for each of the candidates, we generate triples by substituting the subject and object by each of the instances in its candidates lists (first substitute subject only, then object only). That is, the total number of candidate triples is the sum of the size of the subject and object candidates list. We do not create candidate triples by substituting both the subject and object at the same time because, although possible, we assume 58 21
13 8
WC WW CW CC 64 14
8 12 the simultaneous confusion of both instances to be highly unlikely.1 This is also done in order to make the number of candidate triples linear instead of quadratic.
We then remove the candidate triples which are already existent in the KG. We compute the confidence of all candidate triples and select that with highest confidence, given that mc and mcд are satisfied. Our method then outputs a list of triple pairs containing the wrong triple detected and the corrected triple predicted. 4
In our experiments we run CoCKG on DBpedia (2016-10) and NELL (08m-690), then we manually evaluate the triples corrected by our approach. We run PaTyBRED on both datasets and select top-1% facts most likely to be errors to be processed by our correction method. We classify each corrected fact in four diferent categories: (1) WC: wrong fact turned into correct (2) WW: wrong fact turned into another wrong fact (3) CW: correct fact turned into wrong fact (4) CC: correct fact turned into another correct fact
Our approach was run with mc = 0.75, mcд = 2 and entity similarity measure with c = 1.52. That resulted in 24,973 corrections on DBpedia and 616 correction on NELL. It also detected that 873 (569) errors were caused by wrong types in DBpedia (NELL). Since manually evaluating all these corrections would be impossible, we randomly select 100 correction on each to perform the evaluation.
The results of our manual evaluation are shown in Figure 1. The proportion of facts successfully corrected (case 1) was rather low. While our approach can potentially improve the results by tweaking the parameters, and possibly using ensembles of diferent type predictors and error detectors, it currently cannot be used as a fully automatic approach. However, we believe that combining our approach with active learning is a promising direction which, with the help of specialists, could significantly improve results.
When evaluating some relations individually, we notice that some of them achieve good results. E.g., the relations sire, damsire, grandsire and subsequentWork reaching more than 90% of successful corrections (case 1). The results are good for these relations because horses are often named after other entities and artists often have albums named after themselves, which makes confusions easy to happen. 1For that to happen in the case of DBpedia, a Wikipedia user would have to go to the wrong article page and insert a wrong link in the infobox. 2The parameter values were selected based on heuristics and may not be optimal
One of the problems of our approach is that since it relies on
PaTyBRED, which cannot find many relevant path features on
DBpedia and NELL [
The decision to generate candidate triples by corrupting either the subject or object seemed to have worked well for DBpedia, where we could not find a triple where both subject and object were wrong. On the other hand, in NELL such case was observed a few times, e.g. ismultipleof(musicinstrument_herd , musicinstrument_buffalo) whose object was corrected to mammal_buffalo but the subject remained wrong.
Also, our assumption that confusions tend to use a more general IRI instead of a more specific, requiring all tokens of the queried to be matched, does not always hold. One example in DBpedia which contradicts this assumption is language(Paadatha_Thenikkal , Tamil_cinema), whose corrected object would be Tamil_language and could not be retrieved by our approach. While this can be a problem, dropping this assumption also means that more candidates entities will be retrieved, increasing the number of unrelated candidates, resulting in more candidate triples which need to be tested and possibly more occurrences of cases 2 and 3. Further experiments would have to be conducted in order to evaluate the efects of such change. 5
In this paper we proposed CoCKG, an approach for correcting erroneous facts originated from entity confusions. The experiments show that CoCKG is capable of correcting wrong triples with confused instances, with estimated precision of 21% of the produced corrections in DBpedia and 14% in NELL. The low precision values obtained do not allow this process, as of now, to be used for fully automatic KG enrichment. Nevertheless, it works as a proof of concept and can be useful, e.g., as suggestions from which a user would ultimately decide whether to execute.
In the future it would be interesting to adapt this method to support active learning. Since guaranteeing the quality of the newly generated facts is crucial, having input from the user to clarify borderline cases and improve the overall results would be highly valuable. Furthermore, using an ensemble of diferent KG models with diferent characteristics, e.g. KG embeddings, instead of a single model may potentially increase the robustness of the system. Finally, it would be worth adding textual features from entities descriptions to help determine if a pair of entities is related or not.
The work presented in this paper has been partly supported by the Ministry of Science, Research and the Arts Baden-Württemberg in the project SyKo2W2 (Synthesis of Completion and Correction of Knowledge Graphs on the Web).