Relation extraction between entities from text plays an important role in information extraction and knowledge discovery related tasks. Relation extraction systems produce a large number of candidates where many of them are not correct. A relation validation method justifies a claimed relation based on the information provided by a system. In this paper, we propose some features by analyzing the community graphs of entities to account for some sort of world knowledge. The proposed features improve validation of relations significantly when they are combined with voting and some stateof-the-art linguistic features.
Extracting relations from texts is important for different information extraction and knowledge discovery related tasks such as knowledge base population, question-answering, etc. This task requires Natural Language Understanding of pieces of text which is particularly complex when searching for a large number of semantic relations that describe entities in the open domain. The relationship types can be relative to the family of a person (spouse, children, parents etc.) or characteristics of a company (founder, top_members_or_employees etc.), etc. This task, named slot filling, is evaluated in the KBP evaluation1 in which systems must extract instances of around 40 relation types related to several kinds of entities (person, organization, location and their different sub-types). Thus, in order to take advantage of several system’s capabilities and improve results, a final step can be added that enables to validate results of the systems. The method described in this paper is in the framework of the latter task which, given an entity and a response provided by a system (its value and a textsegment that justifies the claimed relation), has to decide whether the value is correct or not. We focus on relations that occur between two entities.
Different approaches have been studied for
validating relations particularly by evaluating the
confidence that a system can have on the source of the
response, i.e. the document that justifies the
response
However, in most cases, the different relation
validation methods do not take into account the
global information, that can be computed on the
collection of text-documents. Collection level
global information about the object of a relation
and words around the mentions have been taken
into account for web relation extraction by
The relation validation method we propose is thus based on three categories of information: linguistic information associated with the expression of the relations in texts, information coming from the graphs of entities built on the collection, and finally information related to the systems and the proposals made. We evaluated our relation validation system on a sub-part of KBP CSSF-2016 corpus and show that the validation step achieves around 5% to 8% higher accuracy over the baseline features when they are combined together with the proposed graph-based features. 2
Relation validation methods have studied different kinds of features to decide if a type of relation exists or not.
Existence and semantic assessment of relation
candidates rely on linguistic features, as
syntactic paths or the existence of trigger words between
the pair of entity-mentions. Dependency tree
Syntactic analysis cannot characterize the type
of a relation. Therefore, words around the
entity mentions in sentences have been analyzed to
characterize the semantics of a relation
It can be difficult to identify the trigger words
for different types of relation in the open
domain. Therefore, recently neural network based
methods have been popular for relation
classification task
A voting method has been proposed by
Several graph based methods
Information-theoretic measurements on graphs
have been successfully used in some related tasks.
Holzinger et al.
Let, a graph G = (E, R), a query relation (slot) rq, a query entity eq✏E, candidate responses ec = {ec1, ec2, . . . , ecn}✏E where rq = r(eq, ec)✏R.
The list of candidates is generated by different relation extraction systems. Suppose, other relations ro✏R where ro 6= rq. We characterize whether a candidate-entity eci of Ec is correct or not for a query relation (rq) by analyzing the communities of Xq and Xc formed by the query entity and each candidate response. A community Xi contains the neighbors of ei, and this up to several possible steps.
X
D Barack Obama
C
Fig. 1 shows an example of such type of graph where the entity of a query, its type and relationship name are Barack Obama, person and spouse accordingly. The candidate responses are Michelle Robinson and Hilary Clinton that are linked to Barack Obama by spouse relation hypothesis. The objective is to classify Michelle Robinson as the correct response based on the community analysis. The communities of Barack Obama (green rectangle), Michelle Robinson (purple circle) and Hilary Clinton (orange ellipse) are defined by in_same_sentence relation which means the pair of entities are mentioned in the same sentence in the text. The graph is thus constructed from untyped semantic relationships based on co-occurrences. It would also be possible to use typed semantic relationships provided by a relation extraction system. 3.2
The graph of entities as illustrated in Fig. 1 is created from a graph representing the knowledge extracted from the texts (lower part of Fig. 2) called knowledge graph. This knowledge graph is generated after applying systems of named entity recognition (NER) and sentence splitting.
Recognition of named entities is done
using Stanford system
The knowledge graph represents documents, sentences, mentions and entities as nodes and the edges between these nodes represent relationships between these elements.
IN_SAME_SENTENCE barack obama michelle obama Barack name.first Michelle name.first Obama name.last Sentence-1
Doc-1
Multiple mentions of the same entity found in the same document are connected to the same entity node in the knowledge graph, based on the textual similarity of the references and their possible components, which corresponds to a first step of entity linking on local criteria. This operation is performed by Luxid. However, an entity can be mentioned in different documents with different forms (eg, Barack Obama, President Barack Obama, President Obama etc.) which creates redundant nodes in the knowledge graph. Entities are then grouped according to the similarity of their names and the similarity of their neighboring entities calculated by Eq. 2. This step groups the similar entities into a single entity in the community graph (upper part of Fig. 2). This latter graph is constructed from the information on the entities and relations present in the knowledge graph and the link with the documents is always maintained. It is thus possible to know the number of occurrences of each entity and each relation. The graph is stored in a Neo4j database, a graph-oriented database, which makes it possible to extract the subgraphs linked to an entity by queries. We only consider as members of the communities the entities of type person, location and organization. 4
In order to predict whether a relationship is correct or not, we consider this problem as a binary classification task based on three categories of information. We calculate a set of features using the graphs (see section 4.1), to which we add features based on a linguistic analysis of the text that justifies the candidate and describes the relationship (see section 4.2) and an estimation of trust on the candidates according to the frequencies of them in the responses of each query (see section 4.3). Table 1 summarizes all the features used for the classification task. 4.1
We assume that a correct candidate of a query is an important member of the community of the query entity. A community Xe of an entity is defined by the sub-graph formed by its neighbors up to several levels. A merging of the communities of two particular entities includes all the neighbors of that pair of entities. We, therefore, define different features related to this hypothesis.
We hypothesize that the network density (Eq. 1) of the community of a correct candidate merged with the community of the query entity must be higher than the density of an incorrect candidate’s community merged with that of the same entity. ⇢ Xe = number of existing edgeswith e number of possible edges (1) According to the Fig. 1 the merged community of Michelle Robinson and Barack Obama is more dense than the merged community of Hilary Clinton and Barack Obama.
We compute the network similarity (Eq. 2) between two communities and hypothesize that the score of the network similarity between the communities of a query entity and a correct candidate would be higher than the score between that query entity and a wrong candidate.
similarity = |Xq \ Xc|
p|Xq||Xc| where, Xq and Xc are the community members of the query entity and of a candidate entity accordingly. (2)
The eigenvector centrality
xi = 1 X ak,ixk k (3) where, 6= 0 is a constant and the equation can be expressed in matrix form: x = xA
We also hypothesize that mutual information (Eq. 4) between the pair of communities of a query-entity and a correct candidate must be higher than that computed between the communities of the query-entity and an incorrect candidate. M I(Xq, Xc) = H(Xq) + H(Xc) H(Xq, Xc) (4) where, H(X) = p(e) =
n X p(ei) log2(p(ei)) i=1 number of edges of e number of edges of X
Xq and Xc are the communities of a queryentity and a candidate respectively.
The community of an entity (query-entity or candidate) is extended up to the third level to measure eigenvector centrality and mutual information. 4.2
For assessing if a relation exists between the pair of entity mentions, we define syntactic features. For characterizing the semantic of the relation, we represent it by seed words and analyze the sentence at the lexical level.
Syntactic features are calculated from
dependency analysis, i.e. the parser
network similarity Minimum edit distance between dependency patterns
Are the query and filler mentions found in the same clause
words of the sentence and the edges between them are labeled by their syntactic role. We collected a list of dependency patterns for each relation from annotated examples. For example, in the sentence Paola, Queen of the Belgians is the wife of King Albert of Belgium. the dependency pattern between Paola and King Albert is [nn, nsubj, prep_of] and the dependencies are nn(Queen, Paola), nsubj(wife, Queen), prep_of(wife, Albert). We simplify the pattern [nn, nsubj, prep_of] to [nsubj, prep_of] by removing leading and following nn for noise reduction. We notice that sometimes the dependency patterns contain consecutive labels like [nsubj, dobj, prep_of, prep_of, poss]. In such cases, we simplify the pattern by substituting the consecutive labels with a single label which leads to simplify [nsubj, dobj, prep_of, prep_of, poss] into [nsubj, dobj, prep_of, poss]. This simplification generalizes the dependency patterns.
The acquired patterns are compared to the simplified dependency path of a sentence by computing edit distances. Suppose a list of pre-annotated dependency patterns are (a,b,c), (a,c,d), (b,c,d) for a relation R and the dependency pattern (a,c,b) is extracted from a relation provenance sentence between the query and the filler mention for a claimed relation to be R. We calculate the edit distance between each pair of [(a,c,b), (a,b,c)], [(a,c,b), (a,c,d)],[(a,c,b), (b,c,d)] and keep the minimum edit distance as a feature.
Since relations are often expressed in short dependency paths, the length of the simplified pattern is considered as a feature.
The semantic analysis is performed based on trigger words associated with the relation types. We consider semantic features as boolean values by defining two types of trigger words: positive trigger and negative trigger. Positive trigger words refer to the keywords that strongly support a particular relation while the negative triggers strongly negate the claimed relations. For example, wife, husband, married are positive triggers while parent, children, brother are negative triggers for a spouse relation. We collected these seed words from the assessed dataset of TAC KBP 2014 slot filling task. In total we collected around 250 triggers and 553 dependency patterns of 41 relations from 3, 579 annotated snippets.
Since the relations are expressed by a variety
of words it is hard to collect all the trigger words
for a relation. Therefore, we associate a word
embedding to each trigger by using a pre-trained
GloVe
Some relations can be expressed without using any trigger word. For example, the snippet Mr. David, from California won the prize expresses the per:city_of_residence relation without explicitly using any trigger word. We classify the relation types in two classes: can be expressed without trigger word or not, and use a boolean flag (is_trigger-based_relation) as a feature. 4.3
We use and calculate the credibility score for candidates based on all the responses given by different systems to a query.
f iller credibility (Fi, Q)
number of occurrences of Fi = # of occurrences of all the candidates (5)
Let F be the candidates of a query Q supplied by the systems S. The credibility of a candidate Fi is computed by the equation 5.
The filler credibility counts the relative vote of
a candidate which indicates the degree of
agreement by different systems to consider the
candidate as correct. Since we can assume that
systems already performed some linguistic and
probabilistic analysis to make the responses, filler
credibility holds strong evidence for a candidate to be
correct. Some slot filling and slot filler
validation methods have used the system credibility
We perform our experiments by using TAC-KBP English cold start slot filling (CSSF) datasets of 2015 and 2016. TAC provided a reference corpus for the English CSSF-2015 evaluation task that consisted of 45, 000 documents. These documents include texts from newswires and discussion_forums. We parsed these texts for building the knowledge graph. We compiled our training data from the assessments of English CSSF2015 responses of slot filling systems. There were 9, 339 round-1 queries for English CSSF2015 and in total 330, 314 round-2 queries were generated by all the slot filling systems based on the responses of round-1 queries. NIST assessed SF responses of around 2, 000 round-1 and 2, 500 round-2 queries. A lot of queries have been answered with only wrong responses. Therefore, we do not take into account these queries for building our training corpus. We selected only queries that have been answered with correct and wrong responses. This subset counted total 1, 296 (1, 080 round-1 and 216 round-2) slot filling queries.
We extracted answers corresponding to those queries from the system assessment file that contains the assessment of the filler values and relation-provenance offsets accordingly. The relation provenance offsets refer to the document ids and begin-end position of the text segments in the evaluation corpus. The values of filler assessment can be correct (C), wrong (W) and inexact (X) while the assessment values of relation provenance can be correct (C), wrong (W), short (S) and long (L) where S and L are considered as inexact. We only take into account the C and W filler assessments and separate the correct and wrong responses according to the relation provenance assessment. When the relation provenance assessment is C the filler assessment can be either C or X but not W. It results in 68, 076 responses. Several features have to be computed on complete sentences, and not on sentence excerpts. As the relation provenance offset of a SF response is not guaranteed to be a complete sentence, we extract the complete sentence corresponding to the relation provenance offset snippet from the source document.
The linguistic features are calculated from the analyzed sentences where the mentions of the pair of entities (query and candidate) must be identified. However, our system cannot find both entries in all selected sentences. This happens when either the query entity or the candidate entity is mentioned by a pronoun or nominal anaphora as we do not use any co-reference resolution. In addition, the named entity detection system, which results from two efficient systems, does not detect all the entity mentions (of queries and candidates) present in the queries and hypotheses. This restriction also applies to the computation of features based on the graph that is constructed over the recognized named entities. This behavior corresponds to a trend generally observed in named entity recognition systems when applied to different documents from those on which they were trained (here web documents and blogs instead of newspaper articles or Wikipedia pages).
Moreover, adding the constraint to finding two entities in the same sentence causes this additional decrease in performance. A total of 55, 276 hypotheses (of the initial 68, 076) could be processed to compute the linguistic features for the responses of 1, 296 queries that have been responded with both correct and wrong candidates. Our system restricts to extract graph based features of limited number of query-responses due to the NER limitation and in_same_sentence constraint. In summary, we can extract both the linguistic and graph features for 4, 321 responses from 260 queries, (213 from round-1 and 47 from round-2). Since there are many wrong responses compared to the number of correct responses, we take a subset of the wrong responses randomly from CSSF-2015 dataset for training the system after removing the duplicate responses where the ratio of correct and wrong responses of each query is 2 : 1 approximately. After applying the filtering process the training dataset contains in total 3, 481 (1, 268 positive and 2, 213 negative) instances.
Similar process has been applied on TAC KBP CSSF-2016 dataset that we use for testing. CSSF2016 dataset consists of around 30, 000 documents. Around 34, 267 responses (of 925 queries) have been assessed as correct or wrong by TAC. Our system could compute graph based features for around 3, 884 responses of 352 queries that have been responded by both correct and wrong answers. There are 699 correct and 3, 185 wrong responses among 3, 884 responses with graph based features in our test dataset. The statistics of the training and test datasets are shown in the columns 1 to 4 of Table 4. We have trained the models by using several classifiers and evaluated relation validation method by standard precision, recall, F-measure and accuracy of different models.
In this experiment we show the contribution of the proposed graph based features for validating relations. Since community-graph based analysis does not account the semantics but holds some evidences of how the entities are associated to each other we expect significant gain of precision by our relation validation method so that a better Fscore can be achieved.
We compare the classification performances of different classifiers e.g. LibLinear, SVM, Naive Bayes, MaxEnt and Random Forest based on the best combination of the features as shown in Table 2. We obtain the best precision (32.2), recall (48.1), F-score (38.5) and accuracy (72.4) by Random Forest classifier. The second highest precision (29.0) and accuracy (72.35) are resulted by MaxEnt while Naive Bayes results the second highest recall (45.8) and F-score (38.5). Since Random Forest results the best scores over other classifiers we observe the performances of different feature sets by this classifier.
Table 3 presents the classification performances
of different feature sets by Random Forest
classifier. Filler credibility as a single feature obtains
the F-score and accuracy of 34.6 and 62.1
accordingly. It represents a strong baseline, as shown in
The best precision (32.2), F-score (38.5) and accuracy (72.4) are achieved by combining filler credibility, linguistic and graph features. This
combination improves the precision, F-score and accuracy by around 7, 4 and 10 points over the filler credibility. The precision is gained because of low false negative that indicates the system classifies a small number of wrong responses as correct. This results strongly signify the contribution of graph based features for validating the claimed relations.
We also investigated the classification performance of Fc+Linguistic+Graph model relation by relation as shown in Table 4.
We notice that the classification performances are not similar for different relations according to the F-score and accuracy although we train a single model with the responses of different relations. However, as we do not have the similar number of training instances for all the relations (e.g. per-city_of_birth and org-subsidiaries), as we see in column 2, it may impact the results. Additionally, in the test data, there are a very small number of positive responses compared to the negative ones (see column 5) for some relations that cause inconsistency in classification performance. For example, the distribution of positive and negative responses of per:top_members_employees, per:city_of_birth and per:parents are more balanced compared to countries_of_residence, org-subsidiaries, employee_or_member_of, country_of_headquarters. Therefore, these two sets of relations make a clear difference between their scores. Also, some relations (org-parents, per-country_of_birth and per-stateorprovince_of_birth) have very small number of positive instances where all of these have been classified as wrong and these relations individually counts zero true positive. Therefore, the precision, recall and F-score become zero. However, most of the negative instances of these relations have been correctly classified as wrong. Moreover, the test dataset contains only negative instances for some relations (per-cities_of_residence, per-schools_attended, per-children, org-alternate_names and orgfounded_by). All of the instances have been correctly classified as wrong that result 100% accuracy for these relations. Interestingly, we notice that proposed relation validation method discards all the wrong instances of per-children relation although the training dataset does not contain any positive or negative instances of this relation. A similar result has also been observed for per-country_of_death relation where the system of relation validation obtains an accuracy of 86.7 to validate the instances. These results justify that the relation validation system trained by the instances of different relations is able to predict correctly whether an instance of a relation is correct or wrong even though the system is not trained by the instances of that particular relation.
Table 5 explains better that our system performs better than the baseline system to discard the negative responses. It presents the confusion matrix Relation Name org-top_members_employees per-city_of_birth statesorprovinces_of_residence org-city_of_headquarters per-parents per-country_of_death per-countries_of_residence org-country_of_headquarters stateorprovince_of_headquarters org-subsidiaries per-employee_or_member_of org-parents per-country_of_birth per-stateorprovince_of_birth per-cities_of_residence per-schools_attended per-children org-alternate_names org-founded_by All Together (true positive (TP), false negative (FN), false positive (FP) and true negative (TN)) of the classification task by different feature sets. The combination, Fc+Linguistic+Graph discards 77.7% wrong responses which is around 14% higher than the baseline. All the experimental results signify the contribution of the proposed features for the task of relation validation. 6
This paper presents a method of validating relationships from the system outputs. We have introduced some features on the linked entities which are computed at the global level of the collection. We have proposed to deal with the community graphs of entities that make it possible to account for general knowledge about the entities having true relationships. Experimental results have shown that our proposed features significantly improve a baseline constructed from the votes on the responses of different systems. The proposed method outperforms the baseline to discard wrong relationships.
The calculation of the different characteristics is dependent on the parsing of the texts, in particular, on the results of the NER system. This part has to be improved in order to evaluate the contribution of community graph on more responses. Although the proposed method results better F-score and accuracy compared to the baseline, the method also discards some positive responses that drops the recall; thus we have to overcome this limitation.