T e MP : Temporal Message Passing for Temporal Knowledge Graph Completion (2020)

Abstract: Inferring missing facts in temporal knowledge graphs (TKGs) is a fundamental and challenging task. Previous works have approached this problem by augmenting methods for static knowledge graphs to leverage time-dependent representations. However, these methods do not explicitly leverage multi-hop structural information and temporal facts from recent time steps to enhance their predictions. Additionally, prior work does not explicitly address the temporal sparsity and variability of entity distributions in TKGs. We propose the Temporal Message Passing (TeMP) framework to address these challenges by combining graph neural networks, temporal dynamics models, data imputation and frequency-based gating techniques. Experiments on standard TKG tasks show that our approach provides substantial gains compared to the previous state of the art, achieving a 10.7% average relative improvement in Hits@10 across three standard benchmarks. Our analysis also reveals important sources of variability both within and across TKG datasets, and we introduce several simple but strong baselines that outperform the prior state of the art in certain settings.

## introduction the ability to infer missing facts in temporal knowledge graphs is essential for applications such as event prediction @xcite , question answering @xcite , social network analysis @xcite and recommendation systems @xcite . whereas static knowledge graphs (kgs) represent facts as triples (e.g., (obama, visit, china)), temporal knowledge graphs (tkgs) additionally associate each triple with a timestamp (e.g., @xcite ). figure 1 shows a subgraph of such tkg. usually, tkgs are assumed to consist of discrete timestamps @xcite , meaning that they can be represented as a sequence of static kg snapshots, and the task of inferring missing facts across these snapshots is referred to as temporal knowledge graph completetion (tkgc). recent works on tkgc have largely focused on developing time-dependent scoring functions, which score the likelihood of missing facts and build closely upon popular representation learning methods for static @xcite @xcite @xcite . however, while powerful, these existing methods do not properly account for multi-hop structural information in tkgs, and they lack the ability to explicitly leverage temporal facts in nearby kg snapshots to answer queries. knowing facts like (obama, make agreement with, china, 2013) or @xcite is useful for answering the query @xcite . moreover-and perhaps more importantlythere are also serious challenges regarding temporal variability and temporal sparsity, which previous works fail to address. in real-world tkgs, models have access to variable amounts of reference temporal information in near kg snapshots when answering different queries (figure 2 and figure 6 in the appendix). for example, in a political event dataset, there are likely to be more quadruples with subject-relation pair @xcite than (trump, visit) from 2008 to 2013. 2 hence the model could access more reference information to answer where obama visited in 2014. the temporal sparsity problem reveals that only a small fraction of entities are active foot_2 at each time step (figure 7 in the appendix). previous methods usually assign the same embedding for inactive entities at different time steps, which is not fully representative of the time-sensitive features. present work. to address these issues, we introduce the temporal message passing (temp) framework, which combines neural message passing and temporal dynamic models. we then propose frequency-based gating and data imputation techniques to counter the temporal sparsity and variability issues. we achieve state-of-the-art performance on standard tkgc benchmarks. in particular, on the standard icews14, icews05-15, and gdelt datasets, temp is able to provide an 7.3% average relative improvement in hits@10 compared to the next-best model. fine-grained error analysis on these three datasets demonstrates the unique contributions made by each of the different components of temp. our analysis also highlights important sources of variability, in particular variations in temporal sparsity both within and across tkg datasets, and how effects of different components are affected by such variability. ## related work static kg representation learning much research exists on representation learning methods for static kgs, in which entities and relations are represented as low-dimensional embeddings @xcite @xcite . generally, these methods involve a decoding method, which scores candidate facts based on entity and relation embeddings, and the models are optimized so that valid triples receive higher scores than random negative examples. while these methods typically rely on shallow encoders to generate the embeddingsi.e., single embedding-lookup layers @xcite -message passing (or graph neural network; gnn) approaches have also been proposed @xcite @xcite to leverage multi-hop information around entities. temporal kg representation learning recent works endeavor to extend static kgc models to the temporal domain. typically, such approaches employ embedding methods with a shallow encoder and design time-sensitive quadruple decoding functions @xcite @xcite @xcite . while time-specific information is considered by these methods, entity-level temporal patterns such as event periodicity are not explicitly captured. another line of work on temporal (knowledge) graph reasoning uses message passing networks to capture intra-graph neighborhood information, which is sometimes combined with temporal recurrence or attention mechanisms @xcite @xcite @xcite @xcite . orthogonal to our work, @xcite ; @xcite explore using temporal point processes. however, their focus is on continuous tkgc. the prior works that most resemble our framework are recurrent event networks (re-net) @xcite and dysat @xcite . re-net uses multi-level rnns to model entity interactions, while dysat uses self-attention to learn latent node representations on dynamic graphs. however, both these works were proposed for the task of graph extrapolation (i.e., inferring the next timestep in a sequence), so they are not directly compatible with the tkgc setting. ## proposed approach we first define our key notation and provide an overview of our temp framework, before describing the individual components in detail in the following sections. notation and task definition. our goal is to predict missing facts in a temporal knowledge graph (tkg here, e and r stand for the union of sets of entities and relations across all time steps and are known in advance. d (t) denotes the set of all observed triples (s, r, o) at time t, with subjects @xmath0, objects @xmath1. let d t) denote the set of true triples at time t such that d (t) ⊆ d t) , ∀t, the temporal knowledge graph completion (tkgc) problem is defined as ranking the subject and object entities given object queries (s, r, ? , t) and subject queries (? , r, o, t) where (s, r, o) ∈ d ## conclusion in this work, we present a novel framework named temp for temporal knowledge graph completion (tkgc). temp computes entity representation by jointly modelling multi-hop structural information and temporal facts from nearby time-steps. additionally, we introduce novel frequencybased gating and data imputation techniques to address the temporal variability and sparsity problems in tkgc. we show that our model is able to achieve superior performance (10.7% relative improvement) over the state-of-the-arts on three benchmark datasets. our work is potentially beneficial to other tasks such as temporal information extraction and temporal question answering, by providing beliefs about the likelihood of facts at particular points in time. future work involves exploring the generalization of temp to continuous tkgc and better imputation techniques to induce representations for infrequent and inactive entities.