TECHS : Temporal Logical Graph Networks for Explainable Extrapolation Reasoning (2023)

Abstract: Extrapolation reasoning on temporal knowledge graphs (TKGs) aims to forecast future facts based on past counterparts. There are two main challenges: (1) incorporating the complex information, including structural dependencies, temporal dynamics, and hidden logical rules; (2) implementing differentiable logical rule learning and reasoning for explainability. To this end, we propose an explainable extrapolation reasoning framework TEemporal logiCal grapH networkS (TECHS), which mainly contains a temporal graph encoder and a logical decoder. The former employs a graph convolutional network with temporal encoding and heterogeneous attention to embed topological structures and temporal dynamics. The latter integrates propositional reasoning and first-order reasoning by introducing a reasoning graph that iteratively expands to find the answer. A forward message-passing mechanism is also proposed to update node representations, and their propositional and first-order attention scores. Experimental results demonstrate that it outperforms state-of-the-art baselines.

## introduction knowledge graphs (kgs) are widely used in intelligent systems @xcite @xcite , where knowledge is commonly represented by triplets in the form of (s, r, o). the limit of conventional kgs is that real-world knowledge usually evolves over time. for example, a fact (donald trump, presidentof, usa) is incorrect now because joe biden has been the new president of the usa since 2021. for more comprehensive representations of knowledge, temporal knowledge graphs (tkgs) @xcite are proposed by introducing time information (time point or interval) via quadruplets, i.e., @xcite . then, the former example is defined as (donald trump, pres-identof, usa, 2017/01/20-2021/01/20). tkgs are usually incomplete @xcite . many studies predicted future facts, based on past facts, namely tkg forecasting or extrapolation reasoning. figure 1a shows the task that predicts facts at time t i with the facts at t i-2 and t i-1 . a model should not only learn topology dependencies, i.e., the neighbor information of an entity (like barack obama at t i-2 ), but also learn temporal dynamics, i.e., the variations of properties of an entity over time (e.g., angela merkel evolves during t i-2 to t i-1 ). thus, temporal embedding methods, e.g., tnt-complex @xcite and cygnet @xcite were proposed. however, these blackbox methods fail to explain their predictions. an explainable method, xerte @xcite conducted instanced propositional reasoning. however, the model is not scalable, as the evidence is entity-dependent, e.g., related to barack obama and other entities in figure 1a . if we can learn the entity-independent rule in figure 1b for the query (barack obama, makestatement, ?, t i ) in figure 1a , the correct answer south korea will be easily obtained after rule grounding. motivated by the fact that tkgs have many hidden logical rules to achieve explainable and accurate predictions, tlogic @xcite searched first-order logical rules and used them for reasoning. however, this two-step pipeline method may cause error propagation issues. generally, there are two main challenges for explainable extrapolation reasoning on tkgs: (1) tkgs contain diverse information, e.g., structural dependencies, temporal dynamics, and hidden logical rules that are difficult to incorporate together and achieve full coverage; to address above issues, we propose a unified framework teemporal logical graph networks (techs). it first utilizes a graph convolutional network (gcn) to embed topological structures and temporal dynamics. to determine the weights of different edges between entities, a generic time encoding and a heterogeneous attention mechanism is introduced. then, a logical decoder is proposed to integrate propositional and first-order reasoning to find the answer. a reasoning graph that contains both query entity and entity-time pair nodes is used to constantly expand over iterations. we update propositional and first-order attention weights as well as node representations via a novel forward message-passing mechanism. finally, nodes' attention weights with the same entity are aggregated as the answer indicator. besides, first-order logical rules can be induced by a novel forward attentive rule induction (fari) algorithm using learned first-order attention weights. our contributions are summarized as follows: (1) a unified framework techs is proposed to conduct explainable extrapolation reasoning on tkgs. to our best knowledge, this is the first study to jointly model structural dependencies, temporal dynamics, and propositional and first-order reasoning. (2) we integrate propositional and first-order reasoning in a logical decoder, where a forward message-passing is proposed to update their attention weights and node representations to achieve explainability. first-order logical rules are induced by a novel fari algorithm. (3) extensive experiments verify the effectiveness of each module and the superiority over state-of-the-art baselines. ## related work the studies of extrapolation reasoning can be categorized into the following three trends. static embedding. by omitting time information in fact quadruplets, general kg embedding methods can be utilized for tkgs, such as transe @xcite , distmult @xcite and complex @xcite . however, these methods simply consider the structural dependency in tkgs and ignore the temporal dynamics. temporal embedding. ttranse @xcite expanded transe to the temporal setting by fusing temporal information in relation embeddings. similarly, ta-distmult and ta-transe @xcite learned relation representations with time information and calculated quadruplet plausibility by distmult and transe. differently, de-simple @xcite proposed diachronic entity embedding which contained static segment and time-varying segment. upon complex, tntcomplex @xcite learned complex-valued embeddings for the entity, relation and time. re-net @xcite learned the global representations of the time subgraph and the local representations of nodes on it. cygnet @xcite introduced a timeaware copy-generation mechanism to model the probability of existing facts, occurring in the future and predicted whether new facts would emerge. however, the aforementioned methods are all in black-box fashion and lack of explainability. explainable reasoning. xerte @xcite proposed a human-understandable reasoning strategy, introducing an expanding query-relevant subgraph to achieve explainability. titer @xcite conducted reasoning from a query node and sequentially transferred to a new node related to the prior on tkgs until the answer was founded. upon anyburl @xcite that sampled paths to learn first-order rules in static kgs, tlogic @xcite learned temporal logical rules with confidences via a temporal random walk. the candidate scores were obtained by rule applications in tkgs. however, xerte and titer conducted propositional reasoning by an end-toend framework that had limited scalability, as its reasoning process was query-specific. although tlogic learned query-independent first-order logical rules, its pipeline method might cause error propagation and performance degradation. ## preliminaries a tkg can be represented as @xmath0, r, t , f}, where e, r and t denote the set of entity, relation and time, respectively. f ⊂ e ×r×e ×t is the fact collection. each fact is a quadruplet, such as (s, r, o, t) where s, @xmath1, @xmath2. for a query (s, r, ?, t) in testing, the model needs to predict an answer entity õ, based on the facts that occur earlier than t, i.e., @xmath3. logical reasoning in kgs can be categorized as: propositional and first-order. propositional reasoning, generally known as multi-hop reasoning @xcite @xcite , is entity-dependent that usually reasons over queryrelated paths to obtain an answer. first-order reasoning is entity-independent, using first-order logical (fol) rules for different entities @xcite , describing causal knowledge in the form of body to head, e.g., premise⇒conclusion, where new facts can be deduced, given observed ones. for efficient and explainable reasoning on tkgs, we define the foth rule and the reasoning graph. definition 1. first-order temporal horn (foth) rule: based on horn rules @xcite on static kgs, atoms in foth rule body are connected transitively by shared variables. meanwhile, rule body and rule head have the same start and end variables. time growth also needs to be satisfied, i.e., time sequence is increasing and the time in the rule head is the maximum. for example, the following rule ϵ, ∃x,y,z r 1 (x, y ) : t 1 ∧r 2 (y,z) : t 2 ⇒ r(x,z) : t is a foth rule with length 2 if t 1 ⩽ t 2 < t. x, y and z are variables that can be instantiated as entities of tkgs by rule grounding. noticeably, for rule learning and reasoning, t 1 , t 2 and t are virtual time variables that are only used to satisfy the time growth and do not have to be instantiated. to represent the rule certainty, each rule is assigned with a confidence value ϵ ∈ [0, 1]. definition 2. reasoning graph: for a query (s, r, ?, t), we introduce a reasoning graph @xmath4, r, f} for propositional and first-order reasoning. o is a node set that consists of nodes in different iteration steps, i.e., o 0 only contains a query entity s and others consist of nodes in the form of entity-time pairs. (n l i , r, n l+1 j ) ∈ f is an edge that links nodes at two neighbor steps, i.e., n l @xmath5, n l+1 @xmath6. the reasoning graph is constantly expanded by searching for posterior neighbor nodes. for start node n 0 = s, its posterior neighbors are n (n 0 ) = {(e i , t i )|(s, r, e i , t i ) ∈ f ∧ t @xmath7. for a node in following steps an example reasoning graph with two steps is shown in figure 1c . to take prior nodes into account at the current step, an extra relation self is added. then, ## methodology there are three key technical parts in techs: temporal graph encoder, logical decoder, and extrapolation prediction. figure 2 shows its architecture. ## conclusion to effectively integrate complex information on tkgs and implement differentiable logical reasoning, this work proposes techs which mainly contains a temporal graph encoder and a logical decoder. the former utilizes the temporal encoding and heterogeneous attention to embed structural dependencies and temporal dynamics. the latter realizes differentiable rule learning and reasoning by continuously conducting forward message-passing in the proposed reasoning graph. finally, foth rules can be easily induced by a novel fari algorithm. in the future, we will explore mining more types of rules on tkgs, such as numerical rules @xcite , and expand to the scenario of inductive reasoning @xcite .