CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features

Semantic Web 0 (2020) 1–0 1 IOS Press 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features Agustín Borrego a,*, Daniel Ayala a, Inma Hernández a, Carlos R. Rivero band David Ruiz a aUniversity of Seville, Av. Reina Mercedes s/n, Seville, Spain E-mails: borre[email protected], [email protected], i[email protected], [email protected] bRochester Institute of Technology, 92 Lomb Memorial Drive, Rochester NY, USA E-mail: [email protected] Abstract. Knowledge Graphs (KGs) currently contain a vast amount of structured information in the form of entities and relations. Because KGs are often constructed automatically by means of information extraction processes, they may miss information that was either not present in the original source or not successfully extracted. As a result, KGs might potentially lack useful and valuable information. Current approaches that aim to complete missing information in KGs either have a dependence on embedded representations, which hinders their scalability and applicability to different KGs; or are based on long random paths that may not cover relevant information by mere chance, since exhaustively analyzing all possible paths of a large length between entities is very time-consuming. In this paper, we present an approach to completing KGs based on evaluating candidate triples using a novel set of features, which exploits the highly relational nature of KGs by analyzing the entities and relations surrounding any given pair of entities. Our results show that our proposal is able to identify correct triples with a higher effectiveness than other state-of-the-art approaches (up to 60% higher precision or 20% higher recall in some datasets). Keywords: Knowledge Graph Completion, Fact Checking, Machine Learning 1. Introduction Knowledge Graphs (KGs) are vast repositories of structured information whose growth over the past years can be related to that of the Web of Data [1]. Large volumes of information about different domains can be found in some well-known KGs such as DBpedia [2], NELL [3], Freebase [4] or the Google Knowledge Vault [5], which can then be used for tasks such as question answering [6]. KGs are most commonly built by extracting nonstructured [3, 5] or semi-structured [2, 7] information from web sources, though some smaller KGs can be manually curated by domain experts [8]. After information extraction systems have been applied to extract knowledge from online sources, said information is then semantized [9, 10] and stored in a KG as entities and relations between those entities. Regardless of the specific process by which a KG is constructed, said KG *Corresponding author. E-mail: [email protected]. usually lacks a certain amount of information, either because said information was not originally present in the original information source, or because it was not extracted or semantized correctly [11]. Because of this inherent incompleteness, KGs operate under the Open World Assumption, i.e., a piece of information that is not contained in a KG is not considered to be incorrect, but rather just unknown [12]. Therefore, it is mandatory to refine KGs after their creation in order to expand the knowledge they contain, so that they contain more accurate information [13]. Such is the example of the Google Knowledge Vault [5], a KG that is commonly used for question answering and that is under constant expansion and refinement. As a motivational example, Figure 1 presents a KG that contains information about fictional works, actors, writers and characters. This KG is incomplete, as it is missing certain information that is true in the real world, such as the fact that Daniel Radcliffe played the character Harry Potter. 1570-0844/20/$35.00 c 2020 – IOS Press and the authors. All rights reserved 2A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51                           !      " #     $ %    &'(    !      " !    $ )*    &'(  + , - ,  .   /  ( 0   "  $$        !      " #    $ %      1  #        112        !     " !    $ )*       !        3   " 3   &'(    !      "   1 $4    &'(  566 7 589:; < =87 5> 7? =875> 7? =875> 7? @8;> 78 5667 589:; < A597?:B<9>5887?:; < 5667 589:; < C59:687 DE 7F C59:687 D E 7F 9>5887?:; < 9>5887?: ; < A 597?:B< 5667 589:; < 9>5887?:; < 9>5887?:; < C59:97 DE 7F 6F 5 G 9 Fig. 1. Example KG describing works, actors, writers and characters Deriving additional knowledge from an existing KG to augment it is a task known as Knowledge Graph completion [13]. KG completion can be approached with two complementary goals in mind: completing information about entity types [14], or completing the relations between entities [15–18]. Furthermore, these techniques can be based either on external features, i.e., features that depend on external information sources, or on purely internal features, i.e., features that are computed using only the KG itself [19, 20]. In this work, we focus in KG completion using only internal features, since this line of work has shown promising results without dependencies to external sources of information. When completing a KG, one has to produce a set of facts that are not contained in said KG but that have a reasonable chance of being true. This is usually done through a prediction model that has been trained beforehand. The task of creating, training and applying such a model is known as fact checking [21, 22]. Thus, it is desirable for these models to achieve a high precision to ensure that the facts that are considered to be correct are actually true in the real world [23]. There are several fact checking proposals in the literature that use solely internal features [12, 15, 18, 20, 24, 25], which we discuss in more detail in Section 2. Unfortunately, these approaches can suffer from a number of drawbacks. Some of them rely on embedded representations of the entities and/or relations, and both these representations and the associated neural models need to be completely recomputed whenever a few new triples, which is a relatively frequent event [3, 5]. Additionally, there exists a number of different, random walk-based proposals that may miss relevant information due to their non-deterministic nature. In this paper we present CAFE, our approach for Fact Checking using Neighborhood-Aware FEatures, which uses a novel feature set that extracts information from the neighborhoods of the entities, i.e., their nearby entities and relations. This feature set is used to transform triples in the KG into feature vectors, which are fed to neural prediction models that discern between correct triples that should be added to the KG, and incorrect ones that should be disregarded. Different than embedding-based proposals, the features CAFE is based on can be directly applied to any KG without the need of computing embedded representations, and do not require to be recomputed as the KG grows. They are also not based on random paths, which ensures that all contextual information is always taken into account. Furthermore, the experimental results show that CAFE is able to predict which relations should be added to a KG with a higher precision than other state-of-the-art approaches. The rest of this paper is organized as follows: Section 2 analyzes the related work in KG completion proposals, Section 3 describes our terminology and the set of features that CAFEuses, Section 4 presents our proposal for training predictive models for triples in a KG, Section 5 reports our experimental results; finally, Section 6 presents our conclusions. 2. Related Work In the field of Fact Checking, there are rule-based, embedding-based and path-based proposals: A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 3 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 Rule-based proposals rely on discovering logical rules that determine when a given triple is correct. In this regard, some authors propose using Inductive Logic Programming to mine Horn rules that express the relations between entities in a KG, and then applying said rules to produce new explicit knowledge [16, 26], under the assumption that all triples that match the rules are correct. The performance of the obtained rules is usually measured using metrics such as rule support or confidence, or a variant of these metrics [12]. Those that are based on embeddings aim to evaluate possible relations in a KG by learning embedded representations of its entities and relations, either by using them as feature vectors for a prediction model [15], or by performing different transformations in an embedding space [18, 20, 25, 27, 28]. The resulting embedding space (or spaces) is subsequently used to evaluate the likelihood of a candidate triple to be correct or incorrect, since entities that are supposed to be related by means of a certain relation are expected to be close to each other in the embedding space. A similar line of work includes representing a KG as a tensor, and then factorizing it to obtain latent, more compact representations of the triples contained within [19, 29]. These proposals usually rank triples by decreasing order of likelihood, according to how close the two entities in the triples are in the generated space. Thus, they are commonly evaluated using metrics that are based on some ranking of likely correct candidate triples [30], however, a likelihood threshold can be set to obtain classical classification measures such as precision, recall and F1 [31]. Finally, those that are path-based exploit the highly relational nature of KGs to learn how to predict new relations between entities. Our approach, CAFE, falls under this category. In this line of work, Lao and Cohen [17] introduce the Path Ranking Algorithm (PRA), a two-step process to find which paths may be useful to predict a certain relation. An evolution of PRA named Subgraph Feature Extraction (SFE) is proposed in [24] by Gardner and Mitchell. SFE achieves a better performance than PRA and produced more expressive results while running faster than PRA. It also introduced a handmade “Alias” relation, which relates entities in the same KG that have different labels but refer to the same element in the real world. In [32], Mazumder and Liu propose a random walk-based approach using neighborhood-guided path finding, where semantic similarities between entities are computed by applying a Word2vec-based embedding model on the names of the entities. Reinforcement learning has also been used to find valuable paths that can help to successfully complete a KG [33]. The evaluation metrics used by these proposals are similar to those used by the proposals based on embeddings. Nowadays, there exist a number of KG completion proposals that combine different approaches. For example, in [34] the authors propose obtaining embeddings of the entities and the relations, and then combining these embeddings in the forms of paths, which can be helpful for determining whether a certain triple is correct. A different way of obtaining embedded representations of the elements in a KG is presented in [30], where they use graph neural networks to capture information pertaining the structure of the graph. Entity embeddings have also been used to aid in the production of KG completion rules [35]. 3. Neighborhood-Aware Features In this Section, we first introduce some preliminary concepts that are necessary to understand our proposal, and then we define our set of neighborhood-aware features. 3.1. Preliminaries We now define some preliminary concepts and the notation that is used throughout the paper. Definition 1. Triple: Let Ebe a set of entities, and let Rbe a set of relations. We define a triple as a 3- tuple that represents the existence of a relation r ∈ R between a source entity s ∈ E and a target entity t ∈ E. We denote triples as (s,r,t). In the example KG depicted in Figure 1, a sample triple is (Emma Watson, starred_in, Beauty and the Beast). Definition 2. Knowledge Graph: Let Ebe a set of entities, let Rbe a set of relations, and let Tbe a set of triples of the form {(s,r,t)|s,t∈ E,r∈ R}. We define a Knowledge Graph as a 3-tuple KG = (E,R, T). Figure 1 graphically represents a KG, with 13 entities and 7 distinct relations. Definition 3. Path between entities: Let KG = (E,R,T)be a Knowledge Graph, and let s,t∈ E be two entities in KG. We define a path p between 4A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 s and t as a sequence of triples of the form p = h(ei,ri,ei+1)ifor i = 1..n, where e1=s, en+1 =t and (ei,ri,ei+1)∈ T for i = 1..n. We define the length of a path as the number of triples it contains, i.e., |p|. We denote a path p of length n between s and t as path(s,t,r1,r2,...,rn), or pathn(s,t)for short. We denote the set of all possible distinct paths of the form path(s,t,r1,r2,...,rn)as P(s,t,r1,r2,...,rn). In the KG depicted in Figure 1, an example path of length 2 between the entities J.K. Rowling and The Cuckoo’s Calling is h(J.K. Rowling, created, Robin Ellacott),(Robin Ellacott, appears_in, The Cuckoo’s Calling)i. Definition 4. Reachability: Let KG = (E,R,T)be a Knowledge Graph, let s,t∈ E be two entities in KG, let r ∈ R be a relation in KG, and let n ⩾1be a natural number. We define reachability as a predicate that determines whether there exists a path of length n between s and t in KG such that the relation r appears in the last triple of the path, i.e., Reach(KG,s, t, r, n)⇐⇒ ∃ pathn(s,t)∧ ∃ a∈ E | last(pathn(s,t)) = (a,r,t). We define the set of entities that can be reached from s through a relation r at distance n as the set of entities that match the predicate Reach under such circumstances, i.e., {t∈ E | Reach(KG,s, t, r, n)}. We denote the previously defined set as Reachable(s,r,n). In the example KG depicted in Figure 1, Reachable(Hermione Granger, writer, 2) = {Hermione Granger, J.K. Rowling}. Definition 5. Neighborhood subgraph: Let KG = (E,R,T)be a Knowledge Graph, let e ∈ E be an entity in KG, and let n ⩾1be a natural number. We define the neighborhood subgraph of e of size n as a Knowledge Graph KGn e= (En e,R,Tn e)that contains the triples whose target entities can be reached from e at a distance of at most n through any relation, and the entity set that can be derived from such triples, where Tn e={(s′,r′,t′)∈ T | Reach(KG, e, t′, r′, i),i = 1..n}and En e=S{{s,t} ⊆ E | (s,r,t)∈ T n e}. Figure 2 illustrates this definition, with two possible neighborhood subgraphs for the KG shown in Figure 1. 3.2. Feature set We devised a neighborhood-aware set of features which takes neighborhood subgraphs, reachable entities and paths into account. Due to the large number HI JKLM NI OPMK Q QL RS TU VW X YI ZZ[ \] ^^ LZ I JO ^ _L \ZK`] JLZ ]Q ab cI dIJ e f]gKL h YI ZZ[ \] ^^LZ I J O ^ _L i] dML^ ] Q j KZL e f] gKL h YI ZZ[ \] ^^LZ I JO ^ _L \ZK`] JLZ ]Q abcIdIJ ed]] ch YI ZZ[ \] ^^ LZ I JO ^ _L i] dML^ ] Q jKZL e d]]ch klmnnopqr s klmnnopqrs tmkqun ovw ox ymkop q z s ymkopq zs (a) Neighborhood subgraph of size 2 for the entity Daniel Radcliffe {| }}~  } |    } }     | |     {| }}~  } |      }      { }    }|  }  | }|  }  {| }}~  }   | }|  }          } }       |     | }|  }  ¡¢£ ¡¤ ¥¦§ ¡ ¨¡§ ¡© ¨¡§ ¡© ¡¦ª   ¡¦ª ¨¡§ ¡© (b) Neighborhood subgraph of size 3 for the entity Harry Potter Fig. 2. Two neighborhood subgraphs for the example KG depicted in Figure 1 of possible variations of each feature, we present our feature set in terms of groups of features, where each group can be parameterized to obtain a specific feature, which we call an instance of the feature group. Definition 6. Feature: Let KG = (E,R,T)be a Knowledge Graph. We define a feature f as a function f:T → Rthat assigns a real number to a triple. For example, a feature fmay convert a triple into the number of entities in the neighborhood subgraph of size 2 of the source entity, i.e., f: (s,r,t)7→ |E2 s|. Definition 7. Feature group: Let KG = (E,R,T)be a Knowledge Graph. We define a feature group fnas a function fn:X → (T → R)that receives a set of parameters Xand returns a feature. For example, a feature group f0may return a feature that converts a triple into the number of entities in the neighborhood subgraph of size nof the source entity, i.e., f0(n) = f: (s,r,t)7→ |En s|, where nis a parameter of the feature group. Thus, f0(2) : (s,r,t)7→ |E2 s|, which is the feature shown in the previous example. A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 5 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 Consequently, feature groups allow us to represent a set of very similar features in a more compact way, where the only distinction between said features is a given set of parameters. In the following, we present the feature groups that CAFE uses. For the sake of clarity, we illustrate a possible instance of every feature group and its value using the example triple example = (Daniel Radcliffe, plays, Harry Potter), the KG shown in Figure 1 and the neighborhood subgraphs described in Figure 2. Feature group f1: Number of entities in the neighborhood subgraph of size n of the source entity in the triple. Features in this group can be computed as f1(n) : (s,r,t)7→ |En s|. In the example shown in Fig. 2(a), f1(2)applied to the example triple is |{Daniel Radcliffe, Harry Potter and the Goblet of Fire (movie), Harry Potter and the Prisoner of Azkaban (movie), Harry Potter and the Goblet of Fire (book), Harry Potter and the Prisoner of Azkaban (book)}| = 5. Feature group f2: Number of entities in the neighborhood subgraph of size n of the target entity in the triple. Features in this group can be computed as f2(n) : (s,r,t)7→ |En t|. In the example shown in Fig. 2(b), f2(3)applied to the example triple is |{Harry Potter, J.K. Rowling, Harry Potter and the Goblet of Fire (book), Harry Potter and the Prisoner of Azkaban (book), Robin Ellacott, Hermione Granger}| = 6. Feature group f3: Number of common entities between the neighborhood subgraph of size n of the source entity and the neighborhood subgraph of size m of the target entity in the triple. Features in this group can be computed as f3(n, m) : (s,r,t)7→ |En s∩ Em t|. In the example shown in Fig. 2, f3(2, 3)applied to the example triple is |{Harry Potter and the Goblet of Fire (book),Harry Potter and the Prisoner of Azkaban (book)}| = 2. Feature group f4: Jaccard index of similarity between the entity sets for the neighborhood subgraph of size n of the source entity and the neighborhood subgraph of size m of the target entity in the triple. Features in this group can be computed as f4(n, m) : (s,r,t)7→ jaccard(En s,Em t). In the example shown in Fig. 2, f4(2, 3)applied to the example triple is |{Harry Potter and the Goblet of Fire (book), Harry Potter and the Prisoner of Azkaban (book)}| /|{Daniel Radcliffe, Harry Potter and the Goblet of Fire (movie), Harry Potter and the Prisoner of Azkaban (movie), Harry Potter and the Goblet of Fire (book), Harry Potter and the Prisoner of Azkaban (book), Harry Potter, J.K. Rowling, Robin Ellacott, Hermione Granger}| = 2 /9 = 0.22. Feature group f5: Number of reachable entities through the relation r at distance n from the source entity in the triple. Features in this group can be computed as f5(r, n) : (s,r,t)7→ |Reachable(s,r,n)|. In the example shown in Fig. 2(a), f5(2, hasPrequel) applied to the example triple is |{Daniel Radcliffe, Harry Potter and the Prisoner of Azkaban (movie)}| = 2. Feature group f6: Number of reachable entities through the relation r at distance n from the target entity in the triple. Features in this group can be computed as f6(r, n) : (s,r,t)7→ |Reachable(t,r,n)|. In the example shown in Fig. 2(b), f6(2, created)applied to the example triple is |{Harry Potter,Hermione Granger, Robin Ellacott}| = 3. Feature group f7: Number of common reachable entities through the relation r from the source entity at distance n and from the target entity at distance m. Features in this group can be computed as f7(r, n, m) : (s,r,t)7→ |Reachable(s,r,n)∩Reachable(t,r,m)|. In the example shown in Fig. 2, f7(2, 3, created)applied to the example triple is |{Daniel Radcliffe} ∩ {Harry Potter, Hermione Granger, Robin Ellacott}| = 0. Feature group f8: Jaccard index of similarity between the reachable entities through the relation r from the source entity at distance n and those reachable through the relation r from the target entity at distance m. Features in this group can be computed as f8(r, n, m) : (s,r,t)7→ jaccard(Reachable(s,r,n),Reachable(t, r,m)). In the example shown in Fig. 2, f8(2, 3, created)applied to the example triple is |∅| /|{Harry Potter, Hermione Granger, Robin Ellacott}| = 0 /3 = 0. 6A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 Feature group f9: Number of distinct paths of length n between the source and the target entity in the triple, using relations r1,...,rn. Features in this group can be computed as f9(n, r1, ...,rn) : (s,r,t)7→ |P(s,t,r1,...,rn)|. In the example shown in Fig. 1, f9(4, starred_in, based_on, writer, created)applied to the example triple is 1, as there is one path of length 4 between the entities Daniel Radcliffe and Harry Potter that matches the given relations. The rationale behind this set of feature groups is mani: first, computing the common entities and indices of similarities of the neighborhood subgraphs for the source and target entities allows CAFE to find out the degree of overlap that exists in the neighborhoods of the two relations, along with detailed information on whether this overlap occurs for different relations. Second, studying all kinds of paths that exist between the entities in a triple allows CAFE to also benefit from path-based information in a deterministic manner. Finally, they can be applied at any time as a KG grows with new entities and relations, without the need of a complete recomputation in opposition to embeddingbased approaches. 4. Our Proposal Our proposal, CAFE, receives a KG and a set of relations from that KG as input, and outputs a classification model for each of the selected relations. These models are able to determine if a given triple that represents an instance of the relation is correct, i.e., if it should belong to the KG. Our workflow is visually depicted in Figure 3 and, in the following subsections, we describe each one of its steps. 4.1. Loading the KG We are interested only in the triples contained in a KG, as both the entities and the relations sets can be derived from them. CAFE internally stores the KG it is given in the form of (s,r,t)triples, using an efficient graph-like structure. The triples that contain relations for which a predictive model does not need to be generated will still be taken into account when computing features, since they may provide valuable predictive information. 4.2. Generating negative examples A KG contains only positive information, i.e., it contains examples of the occurrence of a relation rbetween two entities, but it does not contain explicit information about pairs of entities for which rdoes not hold. Since our proposal relies on a neural prediction model that requires negative examples during its training, a number of them has to be produced. To do this, we follow the same approach as other authors and consider any triple not present in the KG to be a negative example [15, 25, 32]. To train our models, we generate one negative example for each triple existing in the KG by replacing its target entity twith a different one, t′, such that the resulting triple (s,r,t′)does not exist in the KG. To preserve the range of each relation, we randomly choose a t′such that there exists some other triple in the KG where t′appears as the target entity for the relation r. A positive or negative label is then added to every triple, denoting whether it represents positive or negative evidence. In the example depicted in Figure 1, a valid negative example is (Hermione Granger, appears_in, The Cuckoo’s Calling), since we know that The Cuckoo’s Calling is a valid target for the relation appears_in, while (Hermione Granger, appears_in, Daniel Radcliffe) would not be allowed as a negative example, because Daniel Radcliffe never appears as the target of the relation appears_in. It can be argued that generating negative evidence in this manner can produce false negatives by mere chance, i.e., statements that are deemed false because they do not exist in the KG, but that are true in the real world. While this is indeed plausible, we as other authors [15, 18, 20] consider that the chances of this happening are low enough for it to not have a noticeable outcome in our results. Furthermore, it may even prevent our prediction models from overfitting to the available evidence. 4.3. Converting triples into feature vectors Once negative examples have been generated, our feature set is instantiated and applied to all triples. For all feature groups, we obtain all possible feature instances by applying the Cartesian product of its possible parameters but, for efficiency reasons, we limit parameters that represent neighborhood sizes to a maximum value of 3. Each feature instance then assigns each triple a real number, and thus applying several features to a triple results in a feature vector, in which A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 7 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 Generating negative examples Converting triples into feature vectors Loading the Knowledge Graph Grouping feature vectors Training and evaluating the models Relations to predict r1 r2 r3 Features to apply f « f ¬ f  f ® A B C F D E r2 r1 r2 r1 r3 r3 Input KG r2 r4 A r2 B + B C C D E E r2 D + r2 A + r1 B + r3 E + r3 C + r1 F + s r t Label A r2 B + A B B C C C r2 D – r2 D + r2 A – r2 A + r2 D – r1 B + C r1 F – D D E E E E r3 E + r3 C – r3 C + r3 D – r1 F + r1 B – s r t Label f ¯ f ° f ± f ² Label 0.20 2 0.40 4 1 0.10 0.75 0.13 0.53 0.24 0.94 0.64 0.85 0.10 1 0.12 2 0 3 0.63 0 1 0 0.37 0 0 2 0.64 1 1 2 0.41 0 0 3 0.54 2 1 2 0.52 1 0 2 0.50 0 1 4 0.51 1 0 0.34 2 0.43 3 1 0.18 0.68 0.22 2 0.21 2 0 3 0.97 4 1 0 0.42 1 0 Rel. Feature vector Label r1 r2 r3 [0.94, 3, 0.54, 2] [0.64, 2, 0.52, 1] [0.68, 3, 0.97, 4] [0.22, 0, 0.42, 1] [0.20, 2, 0.40, 4] [0.10, 1, 0.12, 2] [0.75, 3, 0.63, 0] [0.13, 0, 0.37, 0] [0.53, 2, 0.64, 1] [0.24, 2, 0.41, 0] [0.85, 2, 0.50, 0] [0.10, 4, 0.51, 0] [0.34, 2, 0.43, 3] [0.18, 2, 0.21, 2] 1 0 1 0 1 0 1 0 1 0 1 0 1 0 r1 train+test Neural model for r1 r2 train+test Neural model for r2 r3 train+test Neural model for r3 Fig. 3. Workflow of CAFE each position represents the value that the corresponding feature assigns to the triple. The labels that were added in the previous step, which indicate if the triple is a positive or a negative example, are converted into a numeric label. It is important to note that, to compute features on a triple, we temporarily remove said triple from the KG (in case it is a positive example and thus exists in the KG), since not doing so would result in trivial prediction models such as “a person plays a character if there exists a triple in the KG stating that the person plays that character”. 4.4. Grouping feature vectors The labeled feature vectors that result from the previous step are grouped by the relation that was present in the original triples, resulting in a group of labeled vectors for every relation for which we train a prediction model. For example, the feature vector produced by the triple (Daniel Radcliffe, plays, Harry Potter) is added to the set of feature vectors for the relation plays alongside its label, which denotes whether it is a positive or a negative example. These groups are then split into training and test sets, resulting in two sets of labeled feature vectors per relation. 4.5. Training and evaluating the models For every relation that we predict, we create one or more neural models (whose hyperparameters can be found in Section 5.2), where each model is fed the features that are obtained from a certain neighborhood size. Thus, using only neighborhood subgraphs of size 1 results in one model, using neighborhood subgraphs of size of up to 2 results in two models, and so on. This allows each model to capture the specific information that every neighborhood size may yield. To combine two or more models, we use an additional layer of three neurons and an output layer of one neuron. Said models are trained using the labeled feature vectors in the training split for the desired relation, where each model receives only the features corresponding to its assigned neighborhood size, and the label or ground truth is shared among them. Prior to training our models, we first remove any individual features that have the exact same value in every feature vector and thus lack any predictive power. This is due to some features being relatively sparse (especially path-based features, since only a small subset of all possible paths of fixed length occur between two given entities), and thus helps the model focus only on potentially useful features. 5. Evaluation In this section, we present our experimental results for several datasets, and we compare our proposal against other state-of-the-art fact checking techniques. In the following, we introduce the datasets that we used for evaluation, our experimental settings and, finally, our results. 8A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 5.1. Datasets We evaluated our proposal using four datasets for KG completion provided by the freely available AYNEC-DataGen [36] tool: FB13-A, WN11-AR, WN18-AR and NELL-AR. These datasets are based on the well-known FB13, WN11 [15], WN18 [37] and a subset of NELL proposed in [24]. However, they have been processed to remove reciprocal relations detected by AYNEC (that is, relations rand r′where if (s,r,t)exists then (t,r′,s)also exists very frequently). Additionally, relations that make up for less than 5% of the total amount of triples in the graph have been removed. These datasets originally contained one negative example per each positive one in both their training and testing splits. In order to study how the KG completion techniques perform when presented with a much higher number of negative evidence, we created versions of these datasets whose testing splits contain, whenever possible, 10 negative examples per each positive one using the AYNEC-DataGen tool. Exceptions may apply for relations where the set of possible target entities is very small, e.g., the relation gender. In these cases we generated as many negative examples as possible, up to 10 per positive example. We believe that this is a more realistic scenario, since a real-world KG completion task would be presented with a much higher number of false candidate triples than true ones [21]. To avoid confusion, we denote these versions as FB13-A-10, WN11-AR-10, WN18-AR-10 and NELL- AR-10. For the sake of reproducibility, our source code is publicly available on GitHub1. For FB13-A-10, WN11-AR-10 and WN18-AR-10, we aimed to predict all possible relations, and for NELL-AR-10 we focused on the same subset of 10 relations that were used to evaluate SFE [24]. However, in the later dataset, one relation was removed by AYNEC for being the reciprocal of another relation, leaving 9 relations for evaluation. In the specific case of FB13-A-10, we transferred some training triples over to the testing set in order to provide testing examples for some relations, as they were not available in the original dataset as introduced in [15]. This was done in a random manner, and 1 in 4 such triples was transferred to the testing set. Table 1 provides an overview on the aforementioned datasets. 1https://github.com/tdg-seville/CAFE 5.2. Evaluation method A neural prediction model is created for every relation of interest and trained using its corresponding training set. Then, the model is applied to all feature vectors in the test set, and we compare the expected label (which denotes whether it represents a valid triple or not) against the label that was produced by our model. We report our results in terms of precision, recall and F1, in order to determine how effective our proposal is when it determines that a triple should be added to the KG. We computed these metrics using the AYNEC-ResTest tool [36]. We evaluated three versions of CAFE, denoted CAFE1to CAFE3, which were limited to using feature instances that exploited neighborhood subgraphs and paths of a maximum size of 1, 2, and 3, respectively. This was done in order to study how using larger neighborhoods affects the performance of CAFE. In the specific case of the NELL dataset, we only used CAFE1and CAFE2. The reason for this is that the larger amount of total relations made it impractical to reach neighborhoods of size 3, as the number of features that would have to be computed was large. We use TransE [38], TransD [20], TransH [25], TransR [18] and ComplEx [39] as baselines for our evaluation, since they are well-known state-of-the-art KG completion proposals. In order to evaluate these different embedding-based proposals in a fair and level manner, we use the OpenKE [31] framework to train and evaluate these proposals using our datasets. Additionally, since these baselines proposals usually employ metrics such as MRR and Precision@N, we used the utilities provided by the OpenKE tool to obtain binary labels for the testing triples by allowing it to set an automatic likelihood threshold. The overall metrics evaluation was carried out using AYNEC-ResTest. To measure how using different neighborhood sizes influences the performance of CAFE, we evaluated CAFE1, CAFE2and CAFE3independently against each other in all proposed metrics. Also, to determine if CAFE is comparable to the previously mentioned state-of-the-art proposals, we used the best-performing variant of CAFE (in terms of better average F1) for comparison against other proposals. We selected the following values for the hyperparameters of our neural models: 3 layers with 1024, 512 and 256 neurons each, learning rate of 0.001, batch size of 8, dropout of 0.1 for all layers, 50 epochs and validation ratio of 10%. When two or more models were to be combined, we joined their results using a A. Borrego et al. / CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features 9 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 Dataset Training triples Test triples Entities Relations FB13-A-10 228,172 481,457 74,998 13 WN11-AR-10 77,948 198,231 38,195 9 WN18-AR-10 71,984 183,051 40,943 11 NELL-AR-10 86,971 219,374 53,934 148 (9) Table 1 Metadata for the datasets we used for evaluation hidden layer with 3 neurons and an output layer with a single neuron. These values for the hyperparameters were chosen using a hold-out or “dev” set for the FB13-A-10 dataset, and all datasets were then evaluated using these hyperparameters. We chose them because they provided satisfactory results in our empirical tests and, to the best of our knowledge, there are no proposals for automatically choosing the optimal parameters for a neural network. Our experiments were conducted on a computer equipped with an Intel Core i9-9900K CPU, 64GB of RAM and an Nvidia RTX 2080 Ti GPU. 5.3. Results and discussion In Figure 4 we show the obtained results in terms of precision, recall and F1 for CAFE1through CAFE3. Those obtained when comparing the embedding-based proposals to the best-performing variant of CAFE for every dataset are shown in Figure 5. This was done by selecting the CAFE variant that achieved a higher average F1 in each dataset. Additionally, in Figure 6 we show the detailed results per every relation in all datasets. Regarding the question of how using different neighborhood sizes affects the performance of CAFE, Fig. 4 shows that performance metrics generally seem to improve for CAFE2with respect to CAFE1, but the same cannot be said for CAFE3and CAFE2. Indeed, metrics appear to remain stagnant or even decrease when using larger neighborhoods in some cases. For example, in FB13-A-10 (Fig. 4(a)) we do not observe a significant increase in effectiveness when using neighborhood subgraphs of size 3 in contrast of those of size 2. Similar remarks can be made for WN11- AR-10 (Fig. 4(c)) and WN18-AR-10 (Fig. 4(d)). A possible conclusion for this is that, at a certain point, larger neighborhood subgraphs do not provide additional value or predictive power over smaller ones. In a worst case scenario, the number of features with little to no predictive power would greatly increase by using larger neighborhood sizes, negatively affecting the performance of CAFE. This effect actually occurs in the case of the NELL-AR-10 dataset, where performance worsens when increasing the size of the neighborhood subgraphs for which we compute features. We believe that a possible explanation for this is that NELL is a noisier dataset [40], and thus taking larger neighborhoods into account significantly increases the amount of noise that our classification model has to deal with, effectively hindering its performance. Our results also show that CAFE is able to match the performance of state-of-the-art embedding-based proposals, and in many cases achieve higher values on the metrics under evaluation. In the case of FB13- A-10 (Fig. 4(a)), CAFE can achieve a wide range of values for the different metrics, however, it is able to reach higher performance values than the embeddingbased proposals under evaluation for all metrics (Fig. 5(a)). In other datasets, such as WN11-AR-10 (Fig. 5(c)) and WN18-AR-10 (Fig. 5(d)), CAFE obtains a more satisfactory performance in a more consistent manner. These results show that CAFE can be more effective than other proposals when presented with a high amount of negative evidence to evaluate. Figure 6 displays that, in general, both a satisfactory precision and recall can be achieved, and thus we consider that CAFE is generally effective. However, there exists a number of relations for which a very high precision value is obtained at the expense of a lower recall, resulting in a typical precision-recall trade-off. We have also observed that, in the specific case of the FB13-A-10 dataset (Fig. 5(a)), one finds an unusually higher number of classification results with a low precision value. We hypothesize that this is due to the dataset in question having relations that are hard to predict using only other information present in it. Such is the case of the relation cause_of_death, since learning to predict the cause of the death of a person with a very high effectiveness would be a remarkable achievement that unfortunately falls out of the scope of this work.