Uncertain Temporal Knowledge Graphs Melisachew Wudage Chekol and Heiner Stuckenschmidt Data and Web Science Group University of Mannheim, Germany {mel|heiner}@informatik.uni-mannheim.de Abstract. Temporal data can be found in various sources from patient histories, purchase histories, employee histories, to web logs. Recent ad- vances in open information extraction have paved the way for automatic construction of knowledge graphs (kgs) from such sources. Often the extraction tools used to construct kgs produce facts and rules along with their confidence scores, leading to the notion of uncertain temporal kgs. The facts and rules contained in these graphs tend to be noisy and erroneous due to either the accuracy of the extraction tools or uncer- tainty in the source data. In this work, we use a numerical extension of Markov logic networks to provide formal syntax and semantics for un- certain temporal kgs. Moreover, we propose a set of datalog constraints with inequalities, that extend the underlying schema of the kgs and help in resolving conflicting facts. Finally, we characterize the complexity of two important queries, maximum a-posteriori and conditional probabil- ity inference, for uncertain temporal kgs. 1 Introduction Open Information Extraction (OIE) or ‘machine reading’ has been announced as a new paradigm for extracting domain independent knowledge from large Web corpora [3, 8]. OIE is of particular interest for the creation of knowledge graphs (kgs) and enriching existing ones. Automated construction of knowledge graphs often results in producing noisy and inaccurate facts and rules. In such graphs, the errors can propagate upon inference or knowledge base expansion as shown in [5]. Hence, it is indispensable to clean kgs at an early stage of their creation in order to avoid maintenance costs and provide clean content. In this work, we propose an approach to tackle this problem. Among others, Google’s Knowledge Graph [6], NELL1 , and ReVerb2 store probabilistic facts – facts along with their confidence scores representing how likely that they are correct. Most of these works have focused on identifying static facts, encoding them as binary relations. However, the vast majority of facts are fluents (dynamic relations whose truth is a function of time), only holding true during an interval of time. Thus, it is very important to extract a fact, for instance coach(ClaudioRanieri, Chelsea), along with its temporal scope 2000–2004. To overcome this, recently, there is an increased interest in temporal information extraction [12, 18, 19]. As research 1 2 http://rtw.ml.cmu.edu/rtw/ http://reverb.cs.washington.edu/ is advancing in building uncertain temporal kgs, it is indispensable to develop efficient techniques and tools to debug and clean such kgs. In this study, we provide a formal characterization of uncertain temporal kgs, and propose a way to debug them. Related work. A limitation of existing methods for debugging automatically created knowledge [20, 24] is the incapability to deal with probabilistic and tem- poral information which leads to situations where statements that refer to ob- jects at different points in time are assumed to be inconsistent. In addition, little has been done in debugging uncertain kgs, with the exception of the prelimi- nary results in [11, 5, 7]. In [11], they use Markov Logic Networks (MLNs) and hand-crafted temporal constraints based on Allen’s interval calculus, to debug RDF facts that contain date and time values. The shortcoming of this study is that: (i) no formal characterization in terms of syntax and semantics is pro- vided, (ii) only a part of RDF(S) inference rules are considered, and (iii) do not provide constraints for debugging numerical attributes as we do here. Dylla et al. [7] have proposed an approach for resolving conflicts in RDF facts that con- tain date and time values. The authors use first-order logic Horn formulas with temporal predicates to express temporal and non-temporal constraints. The ap- proach presented in this paper differs in several aspects: (1) they do not make use of MLNs to model the problem. Using MLNs allows to seamlessly integrate our approach with any reasoning tool that supports MAP inference in MLNs. As a consequence, we will benefit from future progress in developing efficient and scalable MAP inference engines. (2) We do not only support uncertain facts, but also uncertain constraints as this will help us model many common sense rules (“a father does not play in the same soccer club as his son”) that are often not strict constraints, but express soft constraints. (3) Their approach do not allow debugging facts containing numerical attributes such as age, weight, and so on. Chen and Wang [5] debug erroneous facts by using a set of functional constraints however they do not deal with numerical as well as temporal facts as this is not their objective. Despite the general complexity of MLNs, it has been shown that it can be used to reason about extracted facts at Web scale using hand-crafted [21] and extracted inference rules [22]. It has also been shown that MLNs can be used to deal with temporal relations in open information extraction [13]. Besides, MLNs are used to check the consistency of knowledge bases [4, 5, 11]. Consequently, in this study, we make use of an extension of MLNs to clean uncertain temporal kgs. Our contributions are the following: (i) we present a formal syntax and semantics, based on a numerical extension of MLN, for uncertain temporal kgs along with a set of temporal inference rules, (ii) we formalize MAP and condi- tional probability inference problems in uncertain temporal kgs and show that these problems remain NP-hard and #P-hard respectively, and (iii) we propose a set of constraints in order to clean erroneous facts in kgs. Problem. Given an uncertain temporal kg G, a set of temporal inference rules F, and a set of temporal constraints, what is the most probable and error free temporal kg? Problem: Debug Uncertain (temporal) kgs Input: Uncertain (temporal) kg G, a set of inference rules F, and (optionally) a set of constraints C Output: Most probable and conflict-free kg G 0 = clean(G, F, C). Consider for instance the following uncertain temporal kg containing the facts that describe the footballer Cristiano Ronaldo: Fact Validy time Weight bdate(CristianoRonaldo,1951) 0.65 plays(CristianoRonaldo,Manchester) [2003, 2009] 0.85 These facts conflict with each other because when Cristiano joined Manchester in 2003, he was already 52 years old while in fact he is only 31 as of 2016. Hence, it is highly unlike that he was playing for Manchester united at the age of 52. Thus, either the valid time3 of the second fact or his birth date is wrong. In order to identify this kind of conflicts, we can introduce constraints. For instance, ‘every player is at most 40 when playing for a club’, corresponds to the constraint: ∀p, c, t, t1 , t2 : bdate(p, t) ∧ plays(p, c, [t1 , t2 ]) ∧ NC(t, [t1 , t2 ]) → ⊥, NC(t, [t1 , t2 ]) = t1 − t < 40 If this problem is modeled using MLN and inference is done to obtain the most probable state, then we obtain both facts as a result. However, if the above constraint is included, the result contains only the second fact (the one with the higher weight). Note that NC can be encoded into the numerical extension of MLN [4]. 2 Preliminaries We present a brief introductory of knowledge graphs and Markov logic networks along with their temporal and numerical extensions respectively. 2.1 Knowledge Graphs RDF is a language used to express structured information on the Web as graphs. We present a compact formalization of RDF [10]. Let I and L be two disjoint infinite sets denoting the set of IRIs (identifying a resource) and literals (a char- acter string or some other type of data) respectively. We abbreviate the union of these sets as: IL = I ∪ L. A triple of the form (s, p, o) ∈ I × I × IL is called an RDF triple 4 . s is the subject, p is the predicate, and o is the object of the triple. Each triple can be thought of as an edge between the subject and the object labelled by the predicate, hence a set of RDF triples is often referred to as an RDF graph. We use the term knowledge graph loosely to refer to an RDF graph. 3 4 Valid time is the time period in which a fact is considered valid. We do not consider blank nodes. Temporal Knowledge Graphs In [14, 9], it is shown that an RDF graph can be extended with some temporal information by labeling each triple in the graph with some temporal element. The temporal element represents the time period in which the triple is valid, i.e, the valid time of the triple. We consider a discrete time domain T as a linearly ordered finite sequence of time points, for instance, days, minutes, or milliseconds. The finite domain assumption ensures that there are finitely many possible worlds in MLNs (see Section 3). A time interval is an ordered pair [t1 , t2 ] of time points, with t1 ≤ t2 and t1 , t2 ∈ T , which denotes the closed interval from t1 to t2 . We will work with the interval- based temporal domain for defining our data model. Note that time point-based temporal domains can be converted into interval-based by using for every time point t, introduce an interval [t, t]. Definition 1 (Temporal kg). A temporal kg is an kg where each fact (s, p, o) in the graph has a valid time [t1 , t2 ], i.e., tt = (s, p, o, [t1 , t2 ]). We refer to tt as a temporal fact. For a temporal kg G, its snapshot at time t is the graph G(t) (the non- temporal kg): G(t) = {(s, p, o) | (s, S p, o, [t, t]) ∈ G}. The kg associated with a temporal kg, denoted u(G), is t G(t), the union of the graphs G(t). We define temporal entailment as follows: for temporal kgs G1 , G2 , G1 |=t G2 if G1 (t) |= G2 (t) for each t, |=t denotes temporal entailment [9] and |= is the standard RDF(S) entailment [10]. The syntax of temporal kgs is given by reifying temporal facts into non- temporal facts by using the underlying RDF syntax [9]. Another possibility is to extend the RDF syntax and explicitly capture temporal information. In this paper, we do not discuss such implementation details, but instead focus on the conceptual aspects for use in uncertain temporal reasoning (Section 3). The semantics of temporal kgs is given by extending the model theoretic semantics of RDF graphs. The notion of entailment for temporal kgs needs ma- nipulating intervals in order to combine the notion of temporality and deductive properties. A deductive system5 for temporal kgs, based on a sound and com- plete set of deduction rules, is presented in [9]. A modified version of these rules is given below: (a, type, class, T1 ) (a, type, property, T1 ) (a, sc, a, T1 ) (a, sp, a, T1 ) (a, sc, b, T1 ) (x, type, a, T2 ) check(T1 , T2 ) (a, sc, b, T1 ) (b, sc, c, T2 ) check(T1 , T2 ) (x, type, b, T3 ) (a, sc, c, T3 ) (a, sp, b, T1 ) (b, sp, c, T2 ) check(T1 , T2 ) (a, sp, b, T1 ) (x, a, y, T2 ) check(T1 , T2 ) (a, sp, c, T3 ) (x, b, y, T3 ) (a, dom, c, T1 ) (x, a, y, T2 ) check(T1 , T2 ) (a, range, d, T1 ) (x, a, y, T2 ) check(T1 , T2 ) (x, type, c, T3 ) (y, type, d, T3 ) 5 In the rules, we use the following shorthands, sp for rdfs:subPropertyOf, type for rdf:type, property for rdf:Property, sc for rdfs:subClassOf, class for rdfs:Class, dom for rdfs:domain, and range for rdfs:range. Equivalently, the non-temporal de- duction rules are those without valid time argument and the test check(T1 , T2 ). T3 = T1 ./ T2 , and the definition of ./ is given in Figure 1 and T1 , T2 and T3 are time intervals define over T . FOL translations of the above rules are used as hard formulas for probabilistic reasoning in uncertain temporal kgs (see Section 3). We use MLNs to extend temporal kgs with uncertainty. 2.2 Markov Logic Networks Markov Logic Networks (MLNs) can be seen as a first-order template language for log-linear models with binary variables. MLNs combine Markov networks and first-order logic (FOL) by attaching weights to first-order formulas and viewing these as templates for features of Markov networks [17]. Markov Logic networks have been extended with numerical [4] and continuous [25] constraints. In this paper, we will use the numerical extension which is useful for reasoning in uncertain temporal kgs. Definition 2 (MLN with Numerical Constraints). A numerical constraint NC is composed of numerical constants (such as elements of N, I, and so √ on), variables, elementary operators or functions (such as, +, ∗, −, ÷, %, ), standard relations (>, <, =, 6=, ≥, ≤), and boolean operators (∧, ∨, ¬). An MLN L with numerical constraints (simply MLN) is a set of pairs (FCi , wi ) where FCi is a formula in FOL that may contain a NC and wi is a real number representing the weight of formula FCi . Together with a finite set of constants C, it defines a Markov Network ML,C , where ML,C contains one node for each possible grounding of each predicate appearing in L. The value of the node is 1 if the ground predicate is true, and 0 otherwise. The probability distribution over possible worlds x specified by the ground Markov network ML,C is given by: F 1 X  P (X = x) = exp wi ni (x) Z i=1 where F is the number of formulas in the MLN and ni (x) is the number of true groundings of FCi in x. The groundings of a formula are formed simply by replacing its variables with constants in all possible ways. Example 1. Using MLN it is possible to represent the hard constraint: footballers born before 1850 are not alive: {∀a, y : footballer (a) ∧ bdate(a, y) ∧ NC(y) ⇒ dead (y), NC(y) = y < 1850 }. A common inference task over MLNs is finding the most probable state of the world, i.e., finding a complete assignment to all ground atoms which maximizes the probability. This is known as maximum a-posteriori inference (MAP). Find- ing a most likely world of an MLN is a generalization of the (NP-hard) MaxSAT problem. Another equally important inference problem is, conditional probabil- ity inference. This is the task of computing the probability of a set of variables given evidence. The complexity of this problem is known to be #P-hard [17]. 3 Reasoning in Uncertain Temporal KGs Uncertain temporal knowledge graphs (utkgs) are extensions of temporal kgs with log-linear models that are capable of representing uncertainties and rea- soning over temporal knowledge bases. A utkg is a temporal knowledge graph where each triple has a valid-time and an associated weight or confidence. In other words, each triple has an associated timestamp or valid time, in addition to a confidence value. Syntax. A utkg graph G = (G D , G U ) consists of a deterministic (hard ) temporal kg G D and a utkg G U with G D ∩ G U = ∅. An uncertain (soft) temporal kg is defined as G U = {htti , wtti i} where tti is a temporal fact and wtti is a real- valued weight assigned to tti . The syntax of an uncertain temporal fact is similar to the underlying temporal RDF, besides, each fact has an associated weight, written as {(tti , wtti )}. Example 2. Consider the following utkg which represents sport’s personality Claudio Raineri’s courier: Temporal fact Weight (1) (CRanieri, coach, ChelseaFC, [2000,2004]) 0.9 (2) (CRanieri, coach, LeicesterFC, [2015,2016]) 0.7 (3) (CRanieri, playsFor, PalermoFC, [1984,1986]) 0.5 (4) (CRanieri, bdate,1951) 1.0 (5) (CRanieri, coach, NapoliFC, [2001,2003]) 0.6 Before providing semantics to utkgs, we need to extend membership (∈) to (∈∗ ) and subset (⊆) to (⊂∗ ) relations as follows. Given a utkgs G, a tempo- ral fact (s, p, o, [t1 , t01 ]), and a utkg G 0 , we denote by (s, p, o, [t1 , t01 ]) ∈∗ G if ∃(s, p, o, [t2 , t02 ]) ∈ G such that t2 ≤ t1 and t01 ≤ t02 . We denote by G 0 ⊆∗ G if for all tt ∈∗ G 0 , then tt ∈∗ G. Semantics. The semantics of a utkg is based on a joint probability distribution over the uncertain part of the utkg. In particular, the weights of the facts in G U determine a log-linear probability distribution. As mentioned earlier, we assume that the time domain, in which the validity of triples is expressed is finite as well as discrete, hence the set of possible worlds is finite. Formally, for a given utkg G = (G D , G U ) and some G 0 over the same set of IRIs and literals IL, the probability of G 0 is defined as: ! if G 0 |=t G D , 1  P Z exp  wtti 0 {(tt ,w )∈ ∗ G U :G 0 |= tt } P (G ) = i tti t i    0 otherwise  where |=t is a temporal entailment relation, and Z is the normalization constant of the log-linear probability distribution P . Note that in MAP inference (i.e., obtaining the most probable temporal kg) Z is not computed. A utkg can be mapped into a first-order knowledge base as discussed below. Herbrand Models. The set of formulas, denoted by F, listed in Figure 1 are derived from the deduction rules of Section 2.1. Implicitly, F also contains the non-temporal equivalents of the inference rules, i.e., those that do not contain time interval arguments and the check function (more precisely, FOL translations of RDF/S entailment rules [10]). Let C be the set of IRIs and Literals that appear in some utkg G, the Herbrand base of F can be constructed by instantiating all the variables in F using the constants in C. The function θ, given a finite set C and a set of time points T , maps each fact in some utkg into a subset of the Herbrand base HB of F with respect to C and T . Each subset of the Herbrand base is a Herbrand interpretation specifying which ground atoms are true. A Herbrand interpretation H is a Herbrand model of F, denoted as |=H F, iff it satisfies all groundings of the formulas in F. Definition 3 (Mapping utkg into FOL). Given a utkg G over a finite set of IRIs and literals C, a time domain T , and HB the Herbrand base of F with respect to C and T , θ : P(G) → P(HB ) maps G into subsets of HB as follows: [ θ(G) = θ(tt), where θ((s, p, o, T )) = tt(s, p, o, T ). tt∈G The predicate tt is typed, i.e., s, p ∈ I, o ∈ IL and T ∈ T . At this point we need to show that the function θ is bijective, i.e., it induces a one-to-one correspondence between Herbrand models of F and expanded kgs. Applying F repeatedly on an uncertain kg may generate a set of new facts, this results in an expanded kg. Theorem 1. Let C ⊆ IL be a set of IRIs and literals and let T be a set of time points. In addition, let G be a utkg over C and let HB be the Herbrand base of F with respect to C. Then, for any G 0 ⊆ G, G |=t G 0 ⇒ θ(G 0 ) |=H F and for any H ⊆ HB , H |=H F ⇒ θ −1 (H) |= G 00 and G |=t G 00 . 3.1 MAP Inference MAP inference in utkg corresponds to obtaining the most probable, consistent and non-probabilistic temporal kg. Given a utkg G, a set of inference rules F, and a translation function θ, we denote the MAP problem by clean(θ(G), F). Computing clean(θ(G), F) requires to translate G with the function θ into an equivalent Markov logic formalization. Then the inference rules F are added to this translation. The MAP state is computed with the help of a cutting planes algorithm in [4] applied to this input data. To do so, the evidence clauses θ(G) and the grounding of F with respect to θ(G) are given as input to the algorithm. Applying the inverse translation function θ −1 to the MAP state, yields the most probable temporal kg. The MAP problem in MLN can be turned into an integer linear program [15] which allows to integrate extrenal functions (for instance the check function in Figure 1) as already shown in [4]. (r1 ) tt(a, type, property, T1 ) → tt(a, sp, a, T1 ) (r2 ) tt(a, sp, b, T1 ) ∧ tt(b, sp, c, T2 ) ∧ check(T1 , T2 ) → tt(a, sp, c, T3 ) T3 = T1 ./ T2 (r3 ) tt(a, sp, b, T1 ) ∧ tt(x, a, y, T2 ) ∧ check(T1 , T2 ) → tt(x, b, y, T3 ) T3 = T1 ./ T2 (r4 ) tt(a, type, class, T1 ) → tt(a, sc, a, T1 ) (r5 ) tt(a, sc, b, T1 ) ∧ tt(b, sc, c, T2 ) ∧ check(T1 , T2 ) → tt(a, sc, c, T3 ) T3 = T1 ./ T2 (r6 ) tt(a, sc, b, T1 ) ∧ tt(x, type, a, T2 ) ∧ check(T1 , T2 ) → tt(x, type, b, T3 ) T3 = T1 ./ T2 (r7 ) tt(a, dom, c, T1 ) ∧ tt(x, a, y, T2 ) ∧ check(T1 , T2 ) → tt(x, type, c, T3 ) T3 = T1 ./ T2 (r8 ) tt(a, range, d, T1 ) ∧ tt(x, a, y, T2 ) ∧ check(T1 , T2 ) → tt(y, type, d, T3 ) T3 = T1 ./ T2 0 if t1 = t2 ∧ t01 = t02  [t1 , t1 ]  0 if t01 = t2      [t 1 , t 2] 0 [t2 , t1 ] if t1 < t2 ∧ t2 < t01 ∧    t01 < t02   0 0 ( [t1 , t1 ] ./ [t2 , t2 ] = f alse if T1 ./ T2 = ∅   [t1 , t01 ] if t1 < t2 ∧ t01 < t02 check(T1 , T2 ) = [t1 , t0 ]   if t1 = t2 ∧ t01 < t02 true otherwise   1 [t2 , t02 ] if t01 < t1 ∧ t2 = t02    if t01 < t2  ∅  Fig. 1. A set of temporal RDF/S inference rules F. If check(T1 , T2 ) = f alse, then the head of the rules (r1 ) – (r8 ) becomes false (⊥). All of the formulas are universally quantified over all the variables. Theorem 2. Given the following: – a utkg G = (G D , G U ) over a finite set IL of IRIs and literals, and a finite set of time points T , – the Herbrand base HB of the formulas F with respect to IL and T , – the set of ground formulas G1 constructed from G D , and – the set of ground formulas G2 constructed from G U . The most probable, expanded and consistent temporal kg is obtained with:  X  θ −1 (H) = arg max wj HB⊇H|=G1 ∪F (ttj ,wj )∈G2 :H|=H ttj From Theorem 1 and the results in [4] taken together, the problem of computing the most probable temporal kg is NP-hard. Example 3 (MAP state). Given a utkg which contains the uncertain temporal triples (1)–(5) of Example 2 and the hard temporal constraints (6) and (7), its most probable and consistent temporal kg contains the facts (1)–(4) without their associated weights. – A person cannot be a coach of two clubs at the same time. (6) ∀x, y, z, T1 , T2 : tt(x, coach, y, T1 )∧tt(x, coach, z, T2 ) → disjoint(T1 , T2 ) – A person cannot be a coach before he or she was born. (7) ∀x, y, z, T1 , T2 : tt(x, bdate, y, T1 ) ∧ tt(x, coach, z, T2 ) → before(T1 , T2 ) The predicates disjoint and before are Allen’s interval relations [2]. Below, we introduce expressive constraints that allow to identify erroneous facts. 3.2 Debugging numerical attributes in Uncertain KGs Often uncertain knowledge graphs may contain a large number of numerical data which can be dates, times, latitudes/longitudes, numerical values measured in different units, and so on. For instance, Claudio Ranieri is 1.82 meters tall corresponds to the fact (CRanieri , height, 1 .82 ). It contains a numeric datum (1.82). Uncertain facts which contain numerical data can be conflicting. One way of resolving this is to compute a MAP state of a given kg which basi- cally throws out facts which have inferior weights or confidences given some inference rules. However, this is not enough. Consider for instance, if there is an uncertain kg that contains two facts: (1) ((CRanieri , height, 1 .80 ), 0 .3 ) and (2) ((CRanieri , height, 3 .5 ), 0 .9 ). Assume that these facts are translated into an MLN framework along with the constraint that the property ‘height’ is functional, i.e., ∀x, y : tt(x, height, y) ∧ tt(x, height, y 0 ) → y = y 0 . In this setting, performing MAP inference results in a kg containing the certain fact (CRanieri , height, 3 .5 ). However, the correct output should contain only the first triple because normally people cannot be taller than 2.5 meters. In order to remove such conflicts, we can add another constraint as discussed below. Constraints are used in description logics and database systems to ensure data validity. In the following, we introduce such constraints in order to ensure validity of temporal facts in uncertain kgs. Constraints A Datalog [1] constraint is an expression of the form body → head, where the head is an atom (i.e., an expression of the form p(x1 , . . . , xn ) in which each xi is either a constant or a variable) and body is a set of atoms, such that each variable occurring in the head also occurs in some atom in the body. Since our choice of MLN with numerical constraints allows us to use external functions whose truth values are computed outside the MLN setting (see Chekol et al. [4]), we can extend datalog constraints (specifically, inclusion dependencies, equality generating dependencies and negative constraints [1]) with numerical constraints. To debug uncertain kgs we can introduce a set of datalog inspired constraints which become hard (deterministic) or soft (uncertain) formulas in MLNs. For instance, if we want to state that “a person cannot be taller that 2.5 meters”, then we can introduce a rule of the form: ∀x, y : (x, type, person) ∧ (x, height, y) → y < 3.5. In the following, we introduce three different kinds of constraints. Inclusion dependencies with inequalities (IDIs). IDIs are first-order for- mulas of the form ∀X, Y : Φ(X, Y ) ∧ NC(Xi , Yj ) → Ψ (Y ), where Φ(X, Y ) is the body of the formula, it is a conjunction of atoms, Ψ (Y ) is the head of the formula, X, Y are sets of variables, and Xi ⊆ X and Yj ⊆ Y . In addition, NC(Xi , Yj ) de- notes a numerical constraint which is an arithmetic expression (see Definition 2). Example 4. Those who are above the age of 40 are probably retired footballers: ∀x, y : tt(x, type, Footballer ) ∧ tt(x, age, y) ∧ NC(y) → tt(x, type, RFootballer ), NC(y) = y > 40. (In)equality generating dependencies (IGDs). IGDs are first-order formu- las of the form ∀X : Φ(X) → NC(Xi ), where Φ(X) is the body of the formula which is a conjunction of atoms, X is a set of variables, and Xi ⊆ X. In addition, NC(Xi ) denotes a numerical constraint. Example 5. Temperature Celsius tc can be converted into an equivalent Fahren- heit scale tf using the formula tf = 1.8tc + 32: ∀x, tc, tf : tt(x, tempc, tc) ∧ tt(x, tempf, tf ) → NC(tc, tf ), NC(tc, tf ) = 1.8tc + 32. From a practical view- point, this rule can be used for checking if two facts extracted from Wikipedia, one containing temperature in Celsius format and the other in Fahrenheit, are conflicting. Disjointness constraints (DCs). DCs are first-order formulas of the form ∀X : Φ(X) ∧ NC(Xi ) → ⊥, where Φ(X) is the body of the formula which is a conjunction of atoms, X is a set of variables, and Xi ⊆ X. In addition, NC(Xi ) denotes a numerical constraint. Example 6. A valid life span of a person is less than 150 years, can be expressed as DCs formula: ∀bd, dd : tt(x, bdate, bd) ∧ tt(x, ddate, dd) ∧ NC(bd, dd) → ⊥, NC(bd, dd) = (dd − bd) > 0 ∧ (dd − bd) < 150. These constraints are more expressive than RDF schema because they allow to express disjointness, functionality of properties, inverse properties, among others. Once an uncertain kg is translated into an equivalent Markov logic formalism using the formula θ, and sets of IDIs, IGDs, and DCs constraints over the kg have been constructed, we can apply MAP inference in order to retrieve the most probable and conflict-free kg using clean(θ(G), F, C). 3.3 Conditional Probability Inference The conditional probability of a temporal fact tt given a utkg G is the sum of the probabilities of the consistent temporal kgs containing tt. In general, a conditional probability query is conjunction of a set of temporal facts. Given a query q and a utkgs G, the conditional probability of q is obtained using: X Pq (q | G) = P (G 0 ) G 0 :q⊆∗ G 0 0 G is a possible world over the same signature IL and T as G. In order to sum over all G 0 , we need to compare the time intervals in the facts of q with those of G 0 . To do so, we rewite the query q as follows: for each temporal fact tt ∈ q if ∃tt0 ∈ G and that tt ⊆+ tt0 , then we replace tt in q with tt0 . The relation ⊆+ is de- fined as: for two temporal facts tt = (s, p, o, [t1 , t01 ]) and tt0 = (s0 , p0 , o0 , [t2 , t02 ]), tt ⊆ tt0 if s = s0 , p = p0 , o = o0 , t2 ≤ t1 and t01 ≤ t02 . This allows us to compute conditional probabilities on top of current solvers such as MC-SAT [16]. The rewriting can be done in polynomial time in the size of the utkg in the worst case. Since no additional computation is required, the complexity of conditional probability inference remains #P-hard for utkgs. For example the conditional query tt(CRanieri , coach, Chelsea, [2001 , 2003 ] given G (from Example 2), can be rewritten as: Pq (tt(CRanieri , coach, Chelsea, [2000 , 2004 ]) | G). Since condi- tional inference is intractable, computing exact probabilities is hard. Thus, it is usual to resort to sampling methods for approximate inference. The state of the art marginal inference algorithm is MC-SAT. A Monte Carlo algorithm must sample consistent or conflict-free temporal kgs according to the distribution Pq . This is very difficult for three reasons: (i) the complexity of reasoning in MLN, (ii) the size of uncertain kgs (such as NELL, ReVerb), and (iii) the presence of deterministic dependencies in the utkgs. Due to these reasons, we need to use emerging lifted inference techniques for marginal inference [23]. We consider this as a future work. 4 Conclusion and Future Work In this paper, we have presented an MLN based approach for reasoning over uncertain temporal knowledge graphs. In doing so, we proposed a formal syntax and semantics. Besides, we formalized MAP and conditional probability inference problems in utkgs and shown that these problems remain NP-hard and #P-hard respectively. Importantly, we extended the datalog constraints in order to clean erroneous facts in utkgs. Thereby, we are able to apply MAP inference in order to obtain a most probable and conflict-free temporal kg from an uncertain one. Currently, we are in the process of conducting experiments by using an ex- isting implementation, that supports the numerical extension of MLN, called ROCKIT6 . At present, there is no avaiable uncertain temporal dataset. We are preparing a gold standard from Freebase and ReVerb, by converting those facts that contain dates and times into temporal facts. With that, we can test the efficiency and scalability of the proposed approach. Another direction for future work is, to investigate how lifted inference can be applied. This is important because the complexity of reasoning in MLNs is intractable in general. References 1. Serge Abiteboul and Victor Vianu. Datalog extensions for database queries and updates. Journal of Computer and System Sciences, 43(1):62–124, 1991. 2. James F Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832–843, 1983. 3. Michele Banko, Michael J Cafarella, Stephen Soderland, Matthew Broadhead, and Oren Etzioni. Open information extraction for the web. In IJCAI, volume 7, pages 2670–2676, 2007. 4. Melisachew Wudage Chekol, Jakob Huber, Christian Meilicke, and Heiner Stuck- enschmidt. Data interlinking through robust linkkey extraction. In Proc. 22nd european conference on artificial intelligence (ECAI), The Hague (NL), 2016. to appear. 5. Yang Chen and Daisy Zhe Wang. Knowledge expansion over probabilistic knowl- edge bases. In SIGMOD, pages 649–660. ACM, 2014. 6 http://executor.informatik.uni-mannheim.de/systems/n-rockit/ 6. Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. Knowledge vault: A web-scale approach to probabilistic knowledge fusion. In SIGKDD, pages 601–610. ACM, 2014. 7. Maximilian Dylla, Mauro Sozio, and Martin Theobald. Resolving temporal con- flicts in inconsistent rdf knowledge bases. In BTW, pages 474–493, 2011. 8. Oren Etzioni, Michele Banko, Stephen Soderland, and Daniel S Weld. Open in- formation extraction from the web. Communications of the ACM, 51(12):68–74, 2008. 9. Claudio Gutierrez, Carlos Hurtado, and Alejandro Vaisman. Temporal rdf. In The Semantic Web: Research and Applications, pages 93–107. Springer, 2005. 10. Patrick Hayes. RDF semantics. W3C Recommendation, 2004. 11. Jakob Huber, Christian Meilicke, and Heiner Stuckenschmidt. Applying Markov Logic for Debugging Probabilistic Temporal Knowledge Bases. In Proceedings of the 4th Workshop on Automated Knowledge Base Construction (AKBC), 2014. 12. Xiao Ling and Daniel S. Weld. Temporal information extraction. In Proceedings of the AAAI 2010 Conference, pages 1385 – 1390, Atlanta, Georgia, USA, July 11-15 2010. Association for the Advancement of Artificial Intelligence. 13. Xiao Ling and Daniel S Weld. Temporal information extraction. In AAAI, vol- ume 10, pages 1385–1390, 2010. 14. Boris Motik. Representing and querying validity time in rdf and owl: A logic-based approach. Web Semantics: Science, Services and Agents on the World Wide Web, 12:3–21, 2012. 15. Jan Noessner, Mathias Niepert, and Heiner Stuckenschmidt. Rockit: Exploiting parallelism and symmetry for map inference in statistical relational models. In AAAI, 2013. 16. Hoifung Poon and Lucy Vanderwende. Joint inference for knowledge extraction from biomedical literature. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 813–821. Association for Computational Linguistics, 2010. 17. Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learn- ing, 62(1-2):107–136, 2006. 18. Alan Ritter, Oren Etzioni, Sam Clark, et al. Open domain event extraction from twitter. In SIGKDD, pages 1104–1112. ACM, 2012. 19. Anisa Rula, Matteo Palmonari, Axel-Cyrille Ngonga Ngomo, Daniel Gerber, Jens Lehmann, and Lorenz Bühmann. Hybrid acquisition of temporal scopes for rdf data. In European Semantic Web Conference, pages 488–503. Springer, 2014. 20. Stefan Schlobach, Zhisheng Huang, Ronald Cornet, and Frank Van Harmelen. De- bugging incoherent terminologies. Journal of Automated Reasoning, 39(3):317–349, 2007. 21. Stefan Schoenmackers, Oren Etzioni, and Daniel S Weld. Scaling textual inference to the web. In EMNLP, pages 79–88, 2008. 22. Stefan Schoenmackers, Oren Etzioni, Daniel S Weld, and Jesse Davis. Learning first-order horn clauses from web text. In EMNLP, pages 1088–1098, 2010. 23. Parag Singla and Pedro M Domingos. Lifted first-order belief propagation. In AAAI, volume 8, pages 1094–1099, 2008. 24. Evren Sirin, Bijan Parsia, Bernardo Cuenca Grau, Aditya Kalyanpur, and Yarden Katz. Pellet: A practical owl-dl reasoner. Web Semantics: science, services and agents on the World Wide Web, 5(2):51–53, 2007. 25. Jue Wang and Pedro M Domingos. Hybrid markov logic networks. In AAAI, volume 8, pages 1106–1111, 2008.