Fact-checking via Path Embedding and Aggregation

Abstract

Knowledge graphs (KGs) are a useful source of background knowledge to (dis)prove facts of the form (s, p, o). The goal of this paper is to present the Fact checking via path Embedding and Aggregation (FEA) system. FEA starts by carefully collecting the paths between s and o that are most semantically related to the domain of p. It learns vectorized path representations, aggregates them according to di erent strategies, and use them to nally (dis)prove a fact. Our experiments show that our hybrid solution brings bene ts in terms of performance.

Introduction

1 We live in a digital era, where both false and true rumors spread at an unprecedented speed. In this open context, having a way to assess the reliability of individual facts is of utmost importance. How could one quickly verify the reliability of statements like (Dune, directed, D. Lynch)? Related Work. Existing approaches, can roughly been categorized in three main categories. First, text-based approaches based on a variety of learning models; these can use probability and logics (e.g., [ 2 ]), deep-learning (e.g., [ 12 ]), and also include multi-modal (e.g., text and video) information (e.g., [ 5 ]). While these approaches can rely on large amounts of text and/or mutimedia sources like audio and video, there are di culties in automatically understanding such pieces of information to (dis)prove a fact. This makes it di cult to give precise semantics to the fact being checked and contextualize it. On one hand, giving semantics boils down to understanding the fact itself rather than relying on statistical indicators like the popularity of a tweet about the fact. For instance, to (dis)prove the fact (Dune, director, D. Lynch), it is crucial to understand that the predicate director relates a Film and a Director and that Director is a subclass of Person. On the other hand, contextualizing facts and gaining insights from (chains of) related facts can represent a valuable source of knowledge [ 20 ]. As an example, the fact (Jaguar, owner, Tata Motors) provides more insights when understanding that it is about the car brand instead of the animal; the additional fact (Tata Motors, type, Company) can help in shedding light on this aspect.

Second, approaches that leverage structured knowledge (e.g., knowledge graphs) instead of unstructured text (e.g., [ 16, 7, 14, 18 ]). In this case, structured background knowledge allows for more precise forms of reasoning for fact-checking. For instance, it has been shown that the paths between the subject and object of a targeted fact, that include other entities and predicates, form a valuable body of semantic evidence (see e.g., [ 15, 7 ]). These approaches o er advantages in terms of semantic interpretation and contextualization of a statement. For instance, the statement (Dune, director, D. Lynch) can be given both a semantic characterization and put into context by retrieving information from KGs like DBpedia. For instance, we understand that the domain of the fact is that of movies and that there are frequently occurring semantic relations between D. Lynch and actors (e.g., K. Mclaughlin) that also acted in Dune. Moreover, the usage of paths or entire portions of a KG of interest for the target statement can provide (visual) evidence about why the fact is true or false. Nevertheless, KGbased approaches lack mechanisms to automatically di erentiate the importance of the collected paths. Third, a more recent strand of research has considered the usage of entity and predicate embeddings for fact-checking (e.g., [ 17, 3 ]). The idea of these approaches is to treat fact-checking as a link prediction problem. While these approaches have the advantage of working with vectorized representations of entities and predicates to automatically identify and extract salient features, they are sub-optimal as they do not directly tackle the problem of vectorizing entire facts, paths, and their aggregation.

Contributions. The goal of this paper is to present the Fact checking via path Embedding and Aggregation (FEA) system. FEA carefully collects paths from a KG between the subject and object of a fact to be checked that are most semantically relevant to it. However, instead of directly working with this subset of all paths, it learns vectorized path representations, aggregates them according to di erent strategies, and use them to nally (dis)prove a fact. To the best of our knowledge, this is the rst work combining triple and path embedding and aggregation for fact checking. 2

Preliminaries

A Knowledge Graph (KG) contains facts (aka statements) that can be divided into an ABox and a TBox. We see the ABox as a node and edge-labeled directed multi-graph G=(V; E; T ) where V is a set of uniquely identi ed vertices representing entities (e.g., D. Lynch), E a set of predicates or properties (e.g., director) and T a set of facts of the form (s, p, o), where s, o 2 V and p 2 E. The TBox is another multi-graph de ned as T = (Ct; Pt; Lt; Tt), where Ct is the set of all class names, Pt is the set of all property names, Lt is a set of properties de ned in some ontological language, and Tf is a set of triples of the form (u; p; v) where u; v 2 Ct [ Pt and p 2 Lt. In this paper, we consider Lt to be the subset of the RDFS ontological language de ned as follows: Lt=frdfs:subClassOf, rdfs:subPropertyOf, rdfs:domain, rdfs:rangeg. We use the notation domain(p) (resp., range(p)) to indicate the domains (resp., ranges) of a l between the domain(s) and range(s) of p treating the input graph as undirected. To reduce the search space, this module only extracts the patterns most relevant to p, where relevance is de ned in terms of the extent to which the path is semantically related to p. As an example, for the predicate director, paths including predicates like director, starring producer are intuitively more relevant than paths including birthDate or college. To quantify the relevance between a predicate and a schema-level pattern, the Path Extractor relies on a predicate relatedness measure. Given a pair of predicates (pi; pj ) their relatedness is:

Rel(pi; pj ) = Cosine(Emb(pi); Emb(pj )) (2) where Emb( ) is an embedding function (e.g., RotatE [ 19 ]) and Cosine is the cosine operation between the vector embeddings of pi and pj . Finally, the relatedness between a path and a predicate p is computed as the average relatedness between p and all predicates in the path. The algorithm to extract patterns, not reported for sake of space, proceeds with a BFS traversal of the TBox graph conditioned on the top-k predicates.

Data-level paths. The Path Extractor has available a set of schema-level patterns Pp, for each predicate p, found in the previous step. Hence, given an input fact (s, p, o), the goal is to nd data-level paths from the ABox for each schema-level pattern i 2 Pp. We adopt an algorithm based on a variant of Depth-First-Search (DFS), which starts from s and at each traversal step of the graph ensures the compliance with i in terms of predicate traversed and entity types toward reaching the entity o. Consider the fact (Dune, director, D. Lynch), the schema-level-path = Work starrin!g Actor starring Work directo!r Person and the DBpedia KG. The algorithm starts from the node Dune and traverses the edge starring (as per ) reaching the nodes J. Nance, K. Mclaughlin, and E. McGill. From each of these nodes, it traverses edges labeled as starring in reverse direction (again as per ) and reaches the nodes Eraserhead, Twin Peaks and Twin Peaks Fire Walks with Me. Finally, according to the last step of , the algorithm traverses edges labeled as director thus closing the paths between the subject Dune and the object D. Lynch of the input fact. When considering the pattern = Film cinematograph!y Person director Film editin!g Person, it is not possible to nd in the ABox. If no path any path between Dune and D. Lynch complying with can be found, FEA performs an unconstrained DFS. 3.2

Path Embedder

To be processed by the learning model at the core of FEA, paths found by the Path Extractor are given a numerical representation. This is done by vectorizing each fact (triple) in a path, which can be done in di erent ways. One way is to consider techniques like TransE [ 3 ] or DistMult [ 21 ] to rst learn entity and predicate embeddings via a generic function Emb( ), which given an entity or a predicate, returns its corresponding vector embedding. Hence, to compute the embedding of a fact t=(s, p, o), one can perform some operation op (e.g., concatenation) on its constituents vectors, that is, Emb(t)=op( Emb(s), Emb(p), Emb(o)). Note that we do not consider one-hot encodings since these techniques do not take into account the structure of the KG. Another way to learn fact embeddings is to rely on approaches like triple2vec [ 8 ], which instead of learning embeddings for entities and predicates separately directly learns fact embeddings. For the time being, given a fact t=(s; p; o), we de ne its embedding as tE =EmbF(t). Building upon the embedding of facts, a path =ft1; t2; : : : tlg of length l including l facts is encoded as a sequence E =[t1E ; t2E ; : : : ; tlE ]. 3.3

Path Aggregator and Fact Checker

Paths converted into their vector form by the Path Embedder are then passed to the Path Aggregator. The Aggregator implements a variety of aggregation strategies. We can see the aggregator as another learning module, which takes the paths from the Path Embedder and provides an overall vector representation for them. We considered the following aggregation strategies: 1. Average Pool. It combines the di erent representations of paths by concatenating the vector representations of the facts in a path. Then on the set of paths obtained, the aggregator performs a 1D average pooling operation. The nal combined path representation is a single vector obtained by averaging the paths between s and o. This can be summarized as follows: PVl = AvgP ool([ ( il); 8 i 2 Pl]) l (3) where AvgP ool is the one-dimensional average pooling operation, and ( ) is the vector concatenation operation. This representation relies on the embeddings of the facts in each path. 2. Max Pool. What changes wrt the AvgPool is the nal vector of the path; instead of being the average, it is now computed by using a dense neural network layer. The resulting activations are then passed through a maxpooling operation which helps to derive a single vector representation for the paths of length l. The whole operation can be summarized as follows: PVl = M axP ool([ (Wl ( il) + bl); 8 i 2 Pl]) l (4) where M axP ool is the one-dimension max pool operation (which selects bitwise the maximum value from multiple vectors to derive a single nal vector.), Wl are the weights to be learned, bl the bias, and the activation function. 3. LSTM Max Pool. The idea is to treat a (vectorized) path as a sequence an employ an LSTM network to cater for sequential dependencies between facts in a path. With this reasoning, each fact in a path represents a point of a sequence. At each step l 1, the LSTM layer outputs a hidden state vector hl 1, consuming subsequence of embedded facts [f1; :::; fl 1]. In other words, xl 1=fl 1. The input xl 1 and the hidden state hl 1 are used to learn the hidden state of the next path step l. After processing all of them via the LSTM, the aggregator employs another LSTM followed by a max pool operation to produce the combined representation PV . As the Path Extractor groups paths according to their di erent lengths, the Path Aggregator processes each length-speci c set of paths separately. Finally, the path representations for each length are concatenated together to give the nal length-speci c path representation PV (see Fig. 1). The last step of the FEA framework consists in providing the nal truthfulness score about the input fact. This is done by the Fact Checker, which takes as input the output of the Path Aggregator (i.e., the vector representation PV ) and feeds it into a classi er. We treat the fact-checking problem as a binary classi cation problem, where a true fact and a false fact are assigned 1 and 0 as target values, respectively. The nal goal is to optimize the negative log-likelihood objective function, which de ned as follows:

L = log y^f+ + log(1 y^f ) (5)

X f+2F+

X f 2F

=ff + j yf =0g are the true (resp., false) facts. 4

Evaluation

We tested the ability of our approach to check facts considering both existing and not existing facts in a given KG. We use the Area Under the Receiver Operating Characteristic curve (AUC) as the primary quality indicator because it is independent from thresholds and has been used previously (e.g., [ 18, 7 ]). All experiments have been carried out on a machine with a 4 core 2.7 GHz CPU and 16 GB RAM. We considered DBpedia as underlying KG.

Embedding and relatedness computation. To compute fact embeddings we used triple2vec [ 8 ], which directly computes fact embeddings by leveraging the notion of line graph of a KG. We tested other indirect approaches based on the embedding of the triple elements (see Section 3.2) but obtained less competitive results. Predicate embeddings were used to obtain a predicate relatedness matrix, where the relatedness of each pair of predicates is computed as per equation (2) for all datasets but DBpedia. In this case, we obtained the predicate relatedness matrix from KStream2. This was necessary since neither DistMult nor ComplEx could run on this dataset on our machine. 4.1

Comparison with related work

We considered the following competitors: (i) CHEEP [ 7 ], an approach, which leverages paths to come up with a truthfulness score for an input fact; (ii) PredPath [ 15 ], which exploits frequent anchored predicate paths between pair of entities in the KG; (iii) Path Ranking Algorithm (PRA) [ 9 ], which extracts (positive and negative) training set of triples via a two-sided unconstrained random walk starting from the fact endpoints to retrieve paths between them; (iv) KStream [ 18 ], which reduces the fact-checking problem to the problem of maximizing the ow between the subject and the object of the fact; (v) Klinker

2 https://github.com/shiralkarprashant/knowledgestream

[ 4 ], which relies on a single short, speci c path to di erentiate between a true and a false fact; (vi) LEAP [ 1 ], which tackles the problem of link prediction on unlabeled graphs. We included LEAP as we took inspiration from it for the path aggregation strategies, although FEA tackles the more challenging problem of fact-checking. For LEAP, paths were generated ignoring the edge labels and we report the best results obtained with its aggregation strategies; (vii) we could not run experiments with DistMult and ComplEx because of memory issues. Nevertheless, we report the results for TransE [ 3 ] obtained by Shiralkar et al. [ 18 ]. We did not consider approaches based on logical rules learned from the KG (e.g., [ 13 ]) since it is not completely clear how to obtain high-quality rules. Benchmarks. We compared the various systems on two benchmarks de ned on DBpedia. The rst de ned in Shiralkar et al. [ 18 ] and available online3. It includes 5 real-world datasets derived from Google Relation Extraction Corpora and WSDM Cup Triple Scoring challenge and 5 synthetic datasets mix a-priori known true and false facts. The number of true/false facts for each benchmark is reported below the predicate name in Table 2. The second benchmark4 re

3 https://github.com/shiralkarprashant/knowledgestream/

4 https://github.com/huynhvp/BUCKLE-Fact checking/ leased by Huynh and Papotti [ 11 ] takes into account popularity, transparency, homogeneity, and functionality properties of the facts to cover a broader variety of scenarios than previous benchmarks.

Evaluation results. We observe that on the rst benchmark (Fig. 2), FEA performs quite well for all predicates considered. In particular, it brings some improvement wrt CHEEP, the second-best performing system, when considering the LSTMMaxPool aggregator. We note that approaches like PredPath, which only consider one path perform worse; perhaps a single path is not able to capture all needed semantic evidence. As expected, the worst-performing system is LEAP, which, however, has not been designed to work on labeled graphs as it aims to solve the link prediction problem in unlabeled graphs. We observe that TransE, which also tackles the link prediction problem performs better than LEAP; although worse than the other systems. This could be because it does not consider paths. Results are more interesting in the second benchmark (Table 1), which has carefully been designed to test the behavior of fact-checking systems on (non)popular (NP) and random entities (R). On this benchmark, we ran experiments for FEA, LEAP, and CHEEP while for TransE, KLinker, and PredPath we report results from [ 11 ]. Here we observe that FEA performs particularly well on non-popular entities with both LSTMMaxPool and Avg aggregators. This may be explained by the fact that even when the number of paths is smaller than between popular entities, the Path Aggregator can correctly capture the necessary evidence, which passed to the other modules of the FEA framework (after embedding) captures the truthfulness of facts eventually. FEA leverages deep-learning techniques for the embedding of paths providing a strategy that can capture dependencies between the facts in a path and aggregate them. Moreover, we remark the importance of considering the semantics of paths for fact-checking but, most importantly, the need to correctly relate the semantics of such paths with the fact to be checked in order to only consider the most relevant ones. Indeed, even if LEAP uses node embedding and path aggregation strategies, it is the worst performing system. We noted that the system fails to especially recognize false facts since even if the existence of a link is correctly predicted, this is not enough as for fact-checking it is necessary to establish the existence of a speci c link. 5

Conclusions and Future Work

We describe a fact-checking approach that combines path-based approaches and embedding based approaches. Our experiments showed that rst embedding whole facts in a path and then aggregating them is a viable solution. Investigating other aggregation strategies, the usage of adversarial learning techniques [ 10 ], and temporal information [ 6 ] is in our research agenda.

References

1. Agrawal , R., de Alfaro, L.: Learning edge properties in graphs from path aggregations . In: WWW . pp. 15 { 25 . ACM ( 2019 )

2. Ahmadi , N. , Lee , J. , Papotti , P. , Saeed , M. : Explainable fact checking with probabilistic answer set programming . arXiv preprint arXiv:1906 . 09198 ( 2019 )

3. Bordes , A. , Usunier , N. , Garcia-Duran , A. , Weston , J. , Yakhnenko , O. : Translating embeddings for modeling multi-relational data . In: NIPS . pp. 2787 { 2795 ( 2013 )

4. Ciampaglia , G.L. , Shiralkar , P. , Rocha , L.M. , Bollen , J. , Menczer , F. , Flammini , A. : Computational Fact Checking from Knowledge Networks . PloS one 10(6) ( 2015 )

5. ar Dhruv, K. , Singh , G.J. , Manish , G. , Vasudeva , V. : Mvae: Multimodal variational autoencoder for fake news detection . In: WWW ( 2019 )

6. Ercan , G. , Elbassuoni , S. , Hose , K. : Retrieving textual evidence for knowledge graph facts . In: ESWC . pp. 52 { 67 . Springer ( 2019 )

7. Fionda , V. , Pirro , G.: Fact checking via evidence patterns . In: IJCAI . pp. 3755 { 3761 ( 2018 )

8. Fionda , V. , Pirro , G. : Learning triple embeddings from knowledge graphs . In: AAAI , pp. 3874 { 3881 ( 2020 )

9. Gardner , M. , Talukdar , P. , Krishnamurthy , J., Mitchell, T.: Incorporating vector space similarity in random walk inference over knowledge bases . In: ENLMP . pp. 397 { 406 ( 2014 )

10. Goodfellow , I. , Pouget-Abadie , J. , Mirza , M. , Xu , B. , Warde-Farley , D. , Ozair , S. , Courville , A. , Bengio , Y. : Generative adversarial nets . In: NIPS . pp. 2672 { 2680 ( 2014 )

11. Huynh , V.P. , Papotti , P.: A benchmark for fact checking algorithms built on knowledge bases . In: CIKM ( 2019 )

12. Karadzhov , G. , Nakov , P. , Marquez , L. , Barron-Ceden~o, A. , Koychev , I. : Fully automated fact checking using external sources . In: RANLP . pp. 344 { 353 ( 2017 )

13. Leblay , J.: A declarative approach to data-driven fact checking . In: AAAI . pp. 147 { 153 ( 2017 )

14. Pan , J.Z. , Pavlova , S. , Li , C. , Li , N. , Li , Y. , Liu , J.: Content based fake news detection using knowledge graphs . In: ISWC . pp. 669 { 683 . Springer ( 2018 )

15. Shi , B. , Weninger , T. : Discriminative Predicate Path Mining for Fact Checking in Knowledge Graphs . Knowledge-Based Systems 104 , 123 { 133 ( 2016 )

16. Shi , B. , Weninger , T. : Fact checking in heterogeneous information networks . In: WWW companion . pp. 101 { 102 ( 2016 )

17. Shi , B. , Weninger , T. : Proje: Embedding projection for knowledge graph completion . In: Thirty-First AAAI Conference on Arti cial Intelligence ( 2017 )

18. Shiralkar , P. , Flammini , A. , Menczer , F. , Ciampaglia , G.L. : Finding Streams in Knowledge Graphs to Support Fact Checking . In: ICDM. pp. 859 { 864 ( 2017 )

19. Sun , Z. , Deng , Z.H. , Nie , J.Y. , Tang , J.: RotatE: Knowledge graph embedding by relational rotation in complex space . In: ICLR ( 2019 )

20. Voskarides , N. , Meij , E. , Reinanda , R. , Khaitan , A. , Osborne , M. , Stefanoni , G. , Kambadur , P., de Rijke, M.: Weakly-supervised contextualization of knowledge graph facts . In: SIGR . pp. 765 { 774 . ACM ( 2018 )

21. Yang , B. , Yih , W.t., He , X. , Gao , J. , Deng , L. : Embedding entities and relations for learning and inference in knowledge bases . In: ICLR ( 2015 )