H i SM atch: Historical Structure Matching based Temporal Knowledge Graph Reasoning (2022)

Abstract: A Temporal Knowledge Graph (TKG) is a sequence of KGs with respective timestamps, which adopts quadruples in the form of ( subject , relation , object , timestamp ) to describe dynamic facts. TKG reasoning has facilitated many real-world applications via answering such queries as ( query entity , query relation , ? , future timestamp ) about future. This is actually a matching task between a query and candidate entities based on their historical structures, which reflect behavioral trends of the entities at different timestamps. In addition, recent KGs provide background knowledge of all the entities, which is also helpful for the matching. Thus, in this paper, we propose the Hi storical S tructure Match ing ( HiSMatch ) model. It applies two structure encoders to capture the semantic information contained in the historical structures of the query and candidate entities. Besides, it adopts another encoder to integrate the background knowledge into the model. TKG reasoning experiments on six benchmark datasets demonstrate the significant improvement of the proposed HiSMatch model, with up to 5.6% performance improvement in MRR, compared to the state-of-the-art baselines.

## introduction knowledge graphs (kgs), which store facts as triples in the form of (subject, relation, object), have been widely applied to many nlp applications, such as question answering @xcite , dialogue generation @xcite and recommendation @xcite . however, facts may constantly change over time. temporal knowledge graphs (tkgs) is a kind of kgs that describe such dynamic facts by extending each triple with a timestamp as @xcite . usually, a tkg is represented as a sequence of kg snapshots. the tkg reasoning task is to infer new facts from known ones, which primarily has two settings, interpolation and extrapolation. the former attempts to complete missing facts in history, while the latter aims to predict future facts with historical facts. this paper focuses on the extrapolation setting, which is more challenging and far from being solved @xcite . this task can be seen as answering the query about the future facts (e.g., (covid-19, infect, ?, 2022-8-1)) by selecting from all the candidate entities. the key of answering the queries about future facts is to understand the history thoroughly. all the existing models conduct reasoning based on substructures extracted from the whole history. these substructures can be divided into two types, i.e., query-related history @xcite and candidate-related history @xcite @xcite . the former contains the latest historical facts related to the subject and relation in the query, which reflects the behavioral trends of the subject concerning the query relation. the latter contains all the latest historical facts of the candidates without considering the query, which indicates the behavioral trends of all the entities. both of these two kinds of history are vital to tkg reasoning. take the query (covid-19, infect, ?, 2022-8-1) for example, the query-related history contains facts like (covid-19, infect, *, t), where t is before 2022-8-1. the candidate-related history of a candidate a, includes facts reflecting its own behaviors, like (a, *, *, t) or (*, *, a, t). in the realistic situation, the occurrence of the fact (covid-19, infect, a, 2022-8-1) is caused by the interactions between these two kinds of history. however, existing models only focus on one kind of history and underestimate the other, which limits their performance on tkg reasoning. overall, it still remains a challenge to model both two kinds of history in a unified framework. to reduce the computational cost caused by the enormous facts in history, these two kinds of history usually contain one hop facts of the centered entities. thus, they cannot model the high-order associations among the entities, which is also vital to tkg reasoning. motivated by these, we consider both queryrelated history and candidate-related history under a matching framework and propose the historical structure matching (hismatch) model. specifically, it applies two structure encoders to model the semantic information in the above two kinds of historical structures, respectively. then, it obtains the matching scores. both of these two structure encoders contain three components: (1) a structure semantic component to model the structure dependencies among concurrent facts at the same timestamp; (2) a time semantic component to model the time numerical information of the historical facts; (3) a sequential pattern component to mine the behavioral trends from the temporal order information. additionally, to model the high-order associations among the entities, we consider the most recent kgs as the background knowledge of each query and apply a gcn-based background knowledge encoder to obtain more informative entity representations for the two structure encoders. our contributions are summarized as follows: tkg reasoning under the extrapolation setting aims to predict facts at future timestamps. according to the historical structure the models focus on, the existing models can be categorized into two groups: query-based and candidate-based models. query-based models focus on modeling the query-related history. for example, re-net @xcite ) models the query-related subgraph sequence. ghnn @xcite introduces the temporal point process to model the precise time information and takes the 1-hop subgraphs of the query entity into consideration. cygnet @xcite captures repetitive patterns by modeling repetitive facts with the same subject and relation to the query. xerte @xcite ) learns a dynamic pruning procedure to find the queryrelated subgraphs. cluster @xcite and titer @xcite both adopt reinforcement learning to discover query-related paths in history. candidate-based models encode the latest historical facts of all the candidate entities without considering the query, and query are considered only in the decoding phase. re-gcn and its extension cen @xcite designs an evolutional model to get the representations of all the candidates by modeling history at a few latest timestamps. tango @xcite utilizes neural ordinary differential equations to model the structure information for each candidate entity. glean @xcite introduces unstructured textual information to enrich the candidate-related history. candidate structure encoder query structure encoder sequential pattern component structure semantic component time semantic component sequential pattern component matching function structure semantic component time semantic component -+ + … periodic activation function fcn layer ## problem formulation a tkg @xmath0, ..., g t , ..., g t } is a sequence of kgs, each of which contains facts occurred at timestamp t, i.e., g @xmath1, r, f t }, where e is the set of entities, r is the set of relations and f t is the set of facts that occurred at t. each fact is a quadruple (e s , r, e o , t), where e s , e @xmath2. for each fact in tkg, we add the inverse quadruple (e o , r -1 , e s , t) into tkg, correspondingly. the tkg reasoning task aims to predict the missing object via answering a query @xmath3, r q , ?, t q ) with the historical kgs given. note that, when predicting the missing subject of a query @xmath4, r q , e q , t q }, we can convert the query into @xmath5, r -1 q , ?, t q }. ## the hismatch model hismatch aims to captures the semantic similarity contained in the query-related and candidaterelated historical structures. for each query time, it first embeds the background knowledge into the initial entity representations. with the initial representations as input, it maps the semantic information in these two historical structures into the vectorized representations of structures. based on the structure representations, matching scores are calculated. thus, as shown in figure 1 , hismatch consists of four parts: the query structure encoder, the candidate structure encoder, the background knowledge encoder, and the matching function. first, two kinds of historical structures and a background knowledge graph are derived from the tkg. then, the background knowledge encoder gets the representations of the entities with the background knowledge graph as input (section 4.3). with the learned representations as input, two structure encoders use three components to integrate three kinds of semantic information into the representations of query-related structure and candidate-related structure, respectively (section 4.1 and 4.2). finally, the matching function calculates the scores between the query and candidates based on the representations of their historical structures (section 4.4). ## experiments we compare hismatch with a number of baselines on six datasets to validate its effectiveness. in addition, we conduct ablation study to analyze the importance of its different parts. we also evaluated the effects of different kinds of gcn layers in the candidate structure encoder and the background knowledge encoder. besides, we study the maximum time interval that hismatch models. ## conclusion in this paper, we considered both two kinds of history, namely, the query-related history and the candidate-related history in tkg reasoning and transformed the task into a matching problem between them for the first time. we further proposed the hismatch model, which applies two structure encoders to calculate the representations of historical structures of the queries and candidates, respectively. each encoder contains a structure semantic component to model the concurrent structure among entities, a time semantic component to model the time numerical information of facts, and a sequence pattern component to capture the temporal orders. besides, hismatch integrates the background knowledge into the representations of entities. experimental results on six benchmark datasets demonstrate the superiority of hismatch.