PaperlayerView exact revision on arXiv

Source-linked AI summary

EvoKG: Jointly Modeling Event Time and Network Structure for Reasoning over Temporal Knowledge Graphs

Namyong Park, Fuchen Liu, Purvanshi Mehta, Dana Cristofor, Christos Faloutsos, Yuxiao Dong

arXiv:2202.07648v2cs.LGcs.AIcs.SI

TL;DR

Many methods focus on static knowledge graphs or do not use the temporal dynamics available in temporal knowledge graphs. EvoKG jointly models event time and evolving network structure, and the authors report gains in prediction accuracy and processing speed over existing methods.

  • Problem

    Many existing methods focus on static knowledge graphs and do not use the rich temporal dynamics available in temporal knowledge graphs.

    Source: §1 · p. 1

  • Method

    EvoKG jointly models event time and evolving network structure using temporal neighborhood aggregation, recurrent event modeling, and neural density estimation.

    Source: §1 · p. 2

  • Results

    EvoKG improves link and event time prediction accuracy by up to 116% and 77%, respectively, and achieves up to 30× training and 291× inference speedups.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Jointly modeling the two terms can enable more accurate reasoning over temporal knowledge graphs.

    Source: §2 · p. 2

    The formulation assumes earlier events inform events at time t and that same-time events are conditionally independent given preceding events.

    Source: §2 · p. 2

Abstract

from arXiv · show

How can we perform knowledge reasoning over temporal knowledge graphs (TKGs)? TKGs represent facts about entities and their relations, where each fact is associated with a timestamp. Reasoning over TKGs, i.e., inferring new facts from time-evolving KGs, is crucial for many applications to provide intelligent services. However, despite the prevalence of real-world data that can be represented as TKGs, most methods focus on reasoning over static knowledge graphs, or cannot predict future events. In this paper, we present a problem formulation that unifies the two major problems that need to be addressed for an effective reasoning over TKGs, namely, modeling the event time and the evolving network structure. Our proposed method EvoKG jointly models both tasks in an effective framework, which captures the ever-changing structural and temporal dynamics in TKGs via recurrent event modeling, and models the interactions between entities based on the temporal neighborhood aggregation framework. Further, EvoKG achieves an accurate modeling of event time, using flexible and efficient mechanisms based on neural density estimation. Experiments show that EvoKG outperforms existing methods in terms of effectiveness (up to 77% and 116% more accurate time and link prediction) and efficiency.

1 INTRODUCTION

EvoKG addresses temporal knowledge graphs, where timestamped facts exhibit evolving entity and relation dynamics that many existing methods do not use. It jointly models event time and network structure, and reports improved prediction effectiveness and efficiency.

1 INTRODUCTION

  • Real-world events and facts often have timestamps, but many existing methods focus on static KGs and do not use TKGs’ rich temporal dynamics.TKGs represent entities connected by timestamped edges, including multiple interactions between the same entities at different times.Source: §1 · p. 1
  • EvoKG unifies modeling event time and evolving network structure, two tasks that most methods address separately.The paper frames this joint modeling as a way to learn rich, complementary information for TKG reasoning.Source: §1 · pp. 1–2
  • EvoKG uses relation- and time-aware neighborhood aggregation, autoregressive recurrent event modeling, and neural density estimation for event time.The paper describes the framework as capturing structural and temporal dynamics while using flexible, efficient mechanisms for event-time modeling.Source: §1 · p. 2
  • Up to 116% and 77% better link and event time prediction accuracy, respectively, and up to 30× training and 291× inference speedups over the best existing method.The accuracy gains are reported against existing KG reasoning methods; the speedups are compared with the best existing method.Source: §1 · p. 2

2 PROBLEM FORMULATION

The formulation treats a temporal knowledge graph as an ordered sequence of timestamped events and models its joint probability. It factors that probability into event-time and evolving-network terms, under assumptions about temporal dependence and simultaneous events.

2 PROBLEM FORMULATION

  • A TKG is a multi-relational directed graph whose timestamped edges encode subject, relation, object, and event time.The formulation allows repeated edges of the same type between two entities when their timestamps differ.Source: §2 · p. 2
  • The problem is to model the probability of a TKG given its sequence of events, ordered by non-decreasing time.The notation distinguishes events observed at time t from all events observed before t.Source: §2 · p. 2
  • The joint model assumes events at time t depend on earlier events, while events at the same time are conditionally independent given preceding events.These assumptions underlie the paper’s factorization of the TKG joint distribution.Source: §2 · p. 2
  • The formulation decomposes event probability into terms for event time and the evolving network structure, which the paper proposes to estimate separately.The two terms model event time given the triple and history, and the event triple given the history.Source: §2 · p. 2
  • The paper argues that modeling only one term omits information from the other, limiting event-time or timestamped-event likelihood estimation.It presents joint modeling as a way to enable more accurate reasoning over TKGs.Source: §2 · p. 2

3 MODELING A TEMPORAL KNOWLEDGE GRAPH

EvoKG models event timing as a history- and event-conditioned density while updating entity representations from temporal interactions. It combines flexible density estimation with time-aware neighborhood aggregation and recurrent updates.

3 MODELING A TEMPORAL KNOWLEDGE GRAPH

  • Event time is modeled as a random variable using temporal point processes, with event time and inter-event time used interchangeably.The inter-event time is the difference between successive event times.Source: §3.1 · p. 3

3.1 Modeling Event Time

  • The model considers recency between the event’s two entities and recency of either entity’s latest interaction as alternative inter-event times.Experiments report the entity-recency measure as most effective for event-time prediction and pairwise interaction recency for temporal-link prediction.Source: §3.1 · p. 3
  • Direct conditional-density estimation avoids intensity integration; log-normal mixtures offer flexible distributions with closed-form likelihood and expectation.The paper contrasts this with simpler intensity functions’ limited expressiveness and neural intensity approaches’ need for Monte Carlo approximation.Source: §3.1 · p. 3
  • EvoKG parameterizes inter-event-time density with a log-normal mixture conditioned on the event triple and past history.The mixture’s weights, means, and standard deviations are derived from the temporal embeddings of the subject, relation, and object.Source: §3.1 · p. 3
  • Temporal embeddings aggregate relation-aware neighbors while accounting for elapsed inter-event time, then recurrently update interaction patterns in both directions.The neighborhood aggregation and recurrent updates provide context for estimating inter-event time.Source: §3.1 · pp. 3–4

𝑟 . 3.2 Modeling Evolving Network Structure

EvoKG represents evolving network structure with time-updated structural embeddings and models event triples from those representations. Its learning procedure jointly optimizes event-time and event-triple likelihoods while processing concurrent events in parallel.

𝑟 . 3.2 Modeling Evolving Network Structure

  • Structural embeddings combine static entity and relation representations with event-updated representations, and summarize past events through a graph-level representation.The graph-level representation is obtained by elementwise max pooling over entity structural embeddings.Source: §3.2 · p. 4
  • EvoKG adapts neighborhood aggregation and recurrent event modeling to learn structural embeddings that reflect changes over time.The structural embeddings are learned by aggregating concurrent events with R-GCN layers and processing evolving representations with recurrent networks.Source: §3.2 · p. 4

3.3 Parameter Learning

  • The training objective minimizes both inter-event-time and event-triple negative log-likelihoods across training events.Events are organized by timestamp and processed concurrently, with backpropagation truncated every b time steps to limit history-related computation and memory costs.Source: §3.3 · pp. 4–5

4 EXPERIMENTS

The experiments evaluate event-time and temporal-link prediction, runtime, and parameter sensitivity on real-world temporal knowledge graphs. Results compare EvoKG with existing methods and test the contribution of event-time modeling.

4 EXPERIMENTS

  • The experiments address event-time and temporal-link accuracy, training and inference efficiency, and the effects of parameter settings and event-time modeling.Experimental settings are provided in the appendix.Source: §4 · p. 5

4.2 Event Time Prediction (RQ1)

  • Up to 77% less MAE than the second-best method, EvoKG achieves the best event-time prediction on ICEWS-500 and GDELT, with all improvements statistically significant at p-value < 0.05.Many TKG methods cannot predict event time, and some baseline results are unavailable.Source: Figure 3 · p. 5, §4.2 · p. 6

4.1 Temporal Knowledge Graph Data

  • The evaluation uses ICEWS18, ICEWS14, GDELT, WIKI, and YAGO, plus ICEWS-500 for event-time prediction.The datasets are ordered by timestamps and split into training, validation, and test sets.Source: §4.1 · p. 5

4 EXPERIMENTS

  • Event-time prediction estimates an event triple’s expected occurrence time given history and uses MAE; link prediction ranks candidate objects and reports MRR and Hits@3,10.Lower MAE and higher link-prediction metrics indicate better results.Source: §4.2 · p. 5, §4.3 · p. 6

4.3 Temporal Link Prediction (RQ2)

  • Up to 116% higher MRR than the best baseline, EvoKG outperforms existing approaches across TKG datasets, except on GDELT, where it achieves similar performance to the best baseline.The link-prediction evaluation covers five real-world TKGs.Source: §4.1 · p. 5, §4.3 · p. 6, Table 4 · p. 7

4.4 Efficiency (RQ3)

  • Across four TKGs, EvoKG trains 23× faster on average and up to 30× faster than RE-Net, while inference is 177× faster on average and up to 291× faster.EvoKG processes concurrent events simultaneously, reducing redundant operations.Source: §4.4 · pp. 6–7

4.5.1 Parameter Sensitivity.

  • Two R-GCN layers outperform one for both tasks; the best reported settings are 100-dimensional embeddings, 16 mixture components for links, 64 for time, and truncation lengths of 40 and 10, respectively.Larger embeddings can overfit, additional layers can oversmooth, and truncation that is too short or too long can hurt accuracy.Source: §4.5.1 · p. 7, Figure 5 · p. 7

4.5 Ablation Study (RQ4)

  • Event-time modeling consistently improves link-prediction accuracy across all datasets, by up to 61%.The comparison is between EvoKG with both modeled terms and with only the network-structure term.Source: Figure 6 · p. 8, §4.5.2 · p. 8

5 RELATED WORK

Prior work addresses static knowledge graphs, dynamic homogeneous graphs, and temporal knowledge graphs through different modeling approaches. EvoKG unifies event-time and evolving-network modeling to address limits in existing dynamic-graph reasoning.

Reasoning over Static Graphs

  • Static KG methods include tensor factorization, relational scoring models, and relation-aware GNNs, but are not designed to model temporally evolving dynamics.The cited examples include TransE, RotatE, RESCAL, DistMult, ConvE, R-GCN, and HAN.Source: §5 · p. 8

Reasoning over Dynamic Homogeneous Graphs

  • Dynamic homogeneous-graph methods use recurrent models, GNN-RNN combinations, temporal attention, autoencoders, smooth embeddings, or temporal random walks, but lack mechanisms for TKG multi-relational structure.The review cites examples including RNN-based methods and temporal-order attention.Source: §5 · p. 8

Reasoning over Dynamic Heterogeneous Graphs

  • Temporal KG embeddings such as TA-DistMult, TTransE, and HyTE address interpolation, while extrapolation methods vary in how they model event structure and timing.RE-Net models events autoregressively but not event time; Know-Evolve, DyRep, and GHNN use temporal point processes, whereas EvoKG estimates conditional event-time density.Source: §5 · p. 8

Summary

  • EvoKG unifies event-time and evolving-network modeling, addressing the limitations of methods that model only one of these tasks.The related-work review notes that some methods cannot predict when events occur, while others do not model evolving network structure.Source: §5 · p. 8

6 CONCLUSION

The paper presents EvoKG and a unified formulation for reasoning over temporal knowledge graphs by modeling event timing and evolving network structure. Experiments report improved prediction accuracy and training speed, and the authors identify explainability and anomaly detection as future directions.

Conclusion

  • Link and time prediction accuracy improved by up to 116%, and training speed improved by up to 30× over the best baseline.The conclusion reports these as the method’s effectiveness and efficiency results.Source: §6 · p. 8
  • The paper formulates TKG reasoning around event timing and evolving network structure, then develops EvoKG to model both jointly.TKG reasoning is described as important for applications including question answering and recommender systems.Source: §6 · p. 8

Reproducibility

  • The code and data are available at the project website.The paper provides the project URL for reproducibility.Source: §6 · p. 8

Future Work

  • The authors plan to improve EvoKG’s explainability and transparency and extend it to anomaly detection in dynamic networks.The proposed explainability goal includes identifying past events that influenced an estimated relationship.Source: §6 · p. 8

A.1 Experimental Settings

The experimental setup uses chronological data splits, specifies model and optimizer settings, and reports baseline references and compute and software resources.

Data Split

  • Datasets were split into training, validation, and test sets chronologically, with early stopping based on validation performance and patience five.The best-validation model was used for testing.Source: §A.1 · p. 10

Hyperparameters

  • EvoKG used a two-layer R-GCN with block diagonal decomposition (BDD), 200-dimensional entity and relation embeddings (192 for WIKI), and a single-layer Elman RNN with tanh non-linearity.Initial dynamic embeddings were zero-initialized. AdamW was used with learning rate 0.001.Source: §A.1 · p. 10
  • Training began with λ1=0 and λ2=1 before optimizing the full model with λ1=λ2=1; RNN backpropagation was truncated every 40 steps for GDELT and 20 for other datasets.The mixture model used K=128 components.Source: §A.1 · p. 10

Baselines and Resources

  • Baseline descriptions are referenced to prior papers, and experiments ran on a Linux machine with 8 CPUs, 30GB RAM, and an NVIDIA Quadro P6000 GPU.The implementation used Python, Deep Graph Library, PyTorch, NumPy, and pandas.Source: §A.1 · p. 10
Loading 2202.07648v2…