PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Knowledge Graph Completion using Box Embeddings

Johannes Messner, Ralph Abboud, İsmail İlkan Ceylan

arXiv:2109.08970v1cs.LGcs.AI

TL;DR

Temporal knowledge graph completion seeks missing facts at particular timestamps, while existing approaches largely extend static embedding models and had not studied temporal inference patterns. This paper introduces BoxTE, a temporal box embedding model, and reports state-of-the-art performance alongside strong temporal inductive capacity.

  • Problem

    TKGC must infer missing timestamped facts, but existing approaches largely extend static embeddings and had not studied temporal inference patterns.

    Source: §1 · p. 1

  • Method

    BoxTE extends the BoxE model with timestamp embeddings and relation-specific scalars that combine to form time bumps.

    Source: §1 · p. 1, The temporal box embedding model BoxTE · p. 3

  • Results

    BoxTE achieves state-of-the-art TKGC performance and is fully expressive, capturing a rich class of temporal inference patterns.

    Source: §1 · p. 1, §7 · p. 7

  • Takeaways & Limitations

    BoxTE's inductive capacity and robustness are reported benefits, and the model naturally applies to higher-arity knowledge bases.

    Source: §7 · p. 7

    Sparse ICEWS datasets contain few temporal patterns, substantially reducing BoxTE's inductive advantage relative to competitors.

    Source: Temporal knowledge graph completion · p. 6

Abstract

from arXiv · show

Knowledge graph completion is the task of inferring missing facts based on existing data in a knowledge graph. Temporal knowledge graph completion (TKGC) is an extension of this task to temporal knowledge graphs, where each fact is additionally associated with a time stamp. Current approaches for TKGC primarily build on existing embedding models which are developed for (static) knowledge graph completion, and extend these models to incorporate time, where the idea is to learn latent representations for entities, relations, and timestamps and then use the learned representations to predict missing facts at various time steps. In this paper, we propose BoxTE, a box embedding model for TKGC, building on the static knowledge graph embedding model BoxE. We show that BoxTE is fully expressive, and possesses strong inductive capacity in the temporal setting. We then empirically evaluate our model and show that it achieves state-of-the-art results on several TKGC benchmarks.

1 Introduction

Knowledge graph completion addresses missing facts, while temporal knowledge graph completion must also represent when facts hold. The paper proposes BoxTE to model temporal inference patterns and reports strong theoretical and benchmark results.

1 Introduction

  • Knowledge graph incompleteness negatively affects downstream applications, motivating methods that infer missing facts.Embedding-based KGC learns entity and relation representations from known facts to score possible facts.Source: §1 · p. 1
  • Static embedding models assume facts are time-independent, although real-world facts can change and temporal graphs attach timestamps to facts.The paper defines a temporal fact as r(h, t|τ).Source: §1 · p. 1
  • TKGC infers missing temporal facts by jointly representing entities, relations, and timestamps, but prior models had not studied temporal inference patterns.Existing approaches build on static embedding models or use dedicated neural architectures.Source: §1 · p. 1
  • BoxTE extends BoxE with relation-specific time embeddings; the paper reports full expressiveness, strong inductive capacity, and state-of-the-art performance on several TKGC benchmarks.The paper also evaluates alternate model variations to assess its temporal mechanism.Source: §1 · pp. 1–2

2 Temporal Knowledge Graph Completion

This section establishes the objects, task, evaluation procedure, and modeling properties used to discuss temporal knowledge graph completion.

2 Temporal Knowledge Graph Completion

  • A temporal knowledge graph is a finite set of temporal binary facts over entities, relations, and timestamps; TKGC predicts unseen facts from those already present.Temporal facts are also called quadruples.Source: §2 · p. 2
  • TKGC models are trained to score known facts above corrupted samples, then evaluated by ranking test facts against possible corruptions using MR, MRR, and Hits@K.Corruptions replace the head or tail entity with a random entity.Source: §2 · p. 2
  • Full expressiveness means a model can classify any disjoint true and false fact sets, while inductive capacity describes the inference patterns it can capture.The section presents expressiveness as supporting input-graph fitting and inductive capacity as providing an inductive bias for generalization.Source: §2 · p. 2

3 Related Work

Related work spans static knowledge graph embedding families, adaptations that incorporate time, and temporal models with dedicated neural architectures.

3 Related Work

  • Static KGE models include translational, spatio-translational, bilinear, and neural approaches, but assume facts are static and omit temporal information.Examples include TransE, RotatE, BoxE, RESCAL, TuckER, ComplEx, rGCN, and ConvE.Source: §3 · p. 2
  • Many temporal embedding models extend static models: TTransE, ChronoR, TComplEx, and TNTComplEx adapt translational, rotational, or factorization approaches.TComplEx factorizes the temporal data directly, whereas TNTComplEx separates temporal and non-temporal components.Source: §3 · p. 2
  • Other approaches condition representations on time before static scoring, using rotations, timestamp-specific hyperplanes, or diachronic embeddings.Examples include TeRo, HyTE, and DE-TransE or DE-SimplE.Source: §3 · p. 2
  • Dedicated neural approaches model temporal sequences or graph structure, including recurrent networks and TeMP's message passing and cross-time aggregation.TeMP variants use GRU or self-attention encoders.Source: §3 · pp. 2–3

4 A Temporal Box Embedding Model

BoxTE extends BoxE's box-based fact representation with time bumps that vary by timestamp and relation, enabling temporal scoring and relation-specific dynamics.

The box embedding model BoxE

  • BoxE represents each entity with a base vector and a translational bump, and each relation with head and tail boxes for its entity representations.A fact is considered true when the final head and tail representations lie in their corresponding boxes.Source: The box embedding model BoxE · p. 3
  • BoxE scoring encourages box membership by measuring point-to-box distance.The scoring description also specifies an L-x norm.Source: The box embedding model BoxE · p. 3
  • BoxE is described as fully expressive and able to capture a wide array of inference patterns, providing the static model on which BoxTE builds.The section presents BoxE in the binary setting for this exposition.Source: The box embedding model BoxE · p. 3, §4 · p. 3

The temporal box embedding model BoxTE

  • BoxTE adds timestamp embeddings and relation-specific scalars, combines them into time bumps, and uses the bumps to shift final entity representations before BoxE-style scoring.This yields potentially distinct representations for the same entity pair under different relations at the same timestamp.Source: The temporal box embedding model BoxTE · p. 3
  • The parameter k trades temporal flexibility against parameter sharing: k = 1 restricts relations to varying bump magnitude, while k = |R| gives each relation its own bumps.The latter setting is described as overparameterized and without shared time-bump parameters.Source: The temporal box embedding model BoxTE · p. 3
  • Figure 1 contrasts configurations at τ1 and τ2: r(h, t) changes from true to false, while s(t, h) remains true across both timestamps.The smaller time bumps for s are described as reflecting that relation's temporal stability.Source: The temporal box embedding model BoxTE · pp. 3–4, Figure 1 · p. 4

5 Model Properties

BoxTE is fully expressive and extends BoxE’s inductive capacity to temporal inference patterns. It supports rigid and cross-time patterns, with composition excluded from the reported cross-time set.

Full expressiveness

  • BoxTE is fully expressive at d = min(|R||T||E|, |R||E|^2), and this holds even with k = 1 and α_r = 1 for all relations.The latter setting makes time bumps relation-independent.Source: Full expressiveness · p. 4

Inference patterns

  • Setting all relation scalars equal lets BoxTE emulate BoxE and retain its rigid inference patterns, including beyond known timestamps.A relation can also be static over time when α_r = 0.Source: Inference patterns · p. 4
  • BoxTE captures all listed cross-time patterns except composition; fixed-time patterns are the special case where timestamps coincide.A cross-time pattern can require a relation inclusion at two specified timestamps without constraining the relations at other times.Source: Table 1 · p. 5, Inference patterns · p. 5
  • Comparing time-induced relation boxes supports cross-time hierarchy and intersection patterns; mutual exclusion and inversion follow by analogous arguments.These boxes provide an equivalent view in which time bumps translate relation boxes in the opposite direction.Source: Inference patterns · p. 5
  • BoxTE can represent cross-time rules such as entities negotiating at τ1 and signing an agreement at τ2, alongside behaviors specific to when they hold.It also models relation behavior at single-timestamp granularity.Source: Inference patterns · p. 5

6 Experiments

BoxTE is evaluated on temporal knowledge graph benchmarks in standard and parameter-bounded settings. It performs strongly across datasets, with results varying by dataset density, temporal variability, and the trade-off between flexibility and embedding dimensionality.

6 Experiments

  • The experiments cover ICEWS14, ICEWS5-15, and GDELT, using both standard TKGC and a bounded-parameter setting.ICEWS5-15 spans 2005–2015, while the GDELT benchmark covers April 2015 through March 2016 and uses the 500 most frequent entities and 20 most common relations.Source: §6 · p. 5

Temporal knowledge graph completion

  • On GDELT, BoxTE achieves state-of-the-art performance and surpasses TeMP in MRR; on ICEWS14 it outperforms TeMP and is competitive with TNTComplEx and ChronoR.BoxTE also performs strongly on ICEWS15 despite that dataset’s sparsity.Source: Table 3 · p. 6, Temporal knowledge graph completion · p. 6
  • ICEWS14 and ICEWS5-15 are small and sparse, with few temporal patterns, which substantially reduces BoxTE’s inductive advantage over competitors on those datasets.ICEWS14 has around 70k training facts for 7,000 entities across 365 timestamps.Source: Temporal knowledge graph completion · p. 6
  • In the standard setting, BoxTE performs best with k = 2 on ICEWS14 and k = 5 on ICEWS5-15 and GDELT; it also remains strong without temporal smoothness regularization.The authors associate higher k with greater flexibility for datasets with more timestamps or richer facts, and report that TNTComplEx and ChronoR suffer significantly without regularization.Source: Temporal knowledge graph completion · p. 6

Parameter-bounded experiments for TKGC

  • Under the parameter bound, BoxTE achieves state-of-the-art performance on ICEWS14 and GDELT; its MRR drops by 0.03, 0.10, and 0.09 on ICEWS14, GDELT, and ICEWS5-15, respectively, relative to the standard setup.The authors characterize it as a robust baseline under restricted computational budgets.Source: Table 4 · p. 7, Parameter-bounded experiments for TKGC · p. 7
  • Under the parameter bound, the best k varies by dataset: k = 3 provides strong overall performance on ICEWS5-15, while k = 1 is optimal on GDELT.On ICEWS5-15, MRR improves as k increases even as d drops from 137 at k = 1 to 104 at k = 3; on GDELT, the authors attribute the preference for lower k to the need for greater dimensionality.Source: Parameter-bounded experiments for TKGC · p. 7

7 Summary and Outlook

The paper presents BoxTE as a temporal knowledge graph embedding model with strong expressive and inductive capacity, and reports state-of-the-art TKGC performance. It also identifies higher-arity temporal completion as a future direction because established benchmarks for it are unavailable.

7 Summary and Outlook

  • BoxTE is fully expressive and captures a rich class of temporal inference patterns.The paper also reports that its empirical TKGC performance is state of the art and benefits from inductive capacity and robustness.Source: §7 · p. 7
  • Like BoxE, BoxTE naturally applies to higher-arity knowledge bases, but established higher-arity temporal completion benchmarks are unavailable.The authors identify developing such benchmarks as a future direction.Source: §7 · p. 7
  • The authors expect this work to motivate further research on expressive, inductively rich temporal knowledge graph embedding models.Source: §7 · p. 7

A Proof of Theorem 5.1

The proof establishes full expressiveness through two constructions with different dimensionality bounds. One makes arbitrary true facts false while preserving all other truth values; the other makes arbitrary false facts true while preserving the rest.

A Proof of Theorem 5.1

  • Theorem 5.1 establishes full expressiveness with dimensionality d = min(|R| |T| |E|, |R| |E|^2).The proof obtains the two bounds separately in Lemmas A.1 and A.2.Source: A Proof of Theorem 5.1 · p. 10

Proof of Lemma A.1

  • Lemma A.1 assigns an embedding dimension to each entity–relation–time triple, then makes any target true fact false while preserving every other fact’s truth value.The construction starts with all possible facts true and bumps entities out of target relation boxes; the proof uses a simplifying single-time-bump setup that can be configured within general BoxTE.Source: Proof of Lemma A.1 · pp. 10–11

Proof of Lemma A.2

  • Lemma A.2 constructs a static base graph and uses time bumps to make any target false fact true without changing other facts.This construction yields full expressiveness with d = |R| |E|^2.Source: Proof of Lemma A.2 · pp. 11–12

B Further Experimental Details

The appendix describes BoxTE’s tuning procedure, including temporal smoothing and time-embedding factorization, and points to tables of best configurations and model parameter counts.

Hyper-parameter tuning

  • BoxTE was trained for 1,200 epochs on ICEWS14 and ICEWS5-15 and 500 on GDELT, with validation every 100 epochs using peak MRR.Final embeddings were bounded to [−1, 1]^d using element-wise tanh.Source: Hyper-parameter tuning · p. 12
  • The experiments tuned temporal-smoothness weight λ over {10^-4, 10^-3, 10^-2, 10^-1} and factorization rank b over {20, 40, 80, 200, 400}.The regularizer penalizes dissimilarity between consecutive time representations; factorizing the time-embedding tensor reduces parameters and shares representations across timestamps.Source: Hyper-parameter tuning · p. 12
  • Cross-entropy loss performed slightly better than negative-sampling loss across experiments; other tuned choices included d, k, learning rate, negative samples, and batch size.The appendix reports best configurations across datasets in Table 5.Source: Hyper-parameter tuning · p. 12, Table 5 · p. 13

Model parameter counts

C Additional Experiments

The YAGO experiment examines whether BoxTE’s learned relation scalars reflect temporal variability. Its reported scalars differ across relations in ways the authors associate with their temporal behavior.

Learned scalars on a subset of YAGO

  • YAGO49k-temp was built from temporal YAGO15k facts, unfolding occursSince/occursUntil pairs into facts true throughout their timestamp range.These range-based facts differ from the shorter-lived facts in GDELT, ICEWS14, and ICEWS5-15.Source: Learned scalars on a subset of YAGO · p. 13
  • playsFor learned an average scalar of 3.15, while isMarriedTo learned 0.61; their entities averaged 5.45 team changes and 1.05 distinct spouses, respectively.The authors characterize playsFor as temporally unstable and isMarriedTo as more stable.Source: Table 7 · p. 13, Learned scalars on a subset of YAGO · p. 13
  • Relations allowing multiple simultaneous tails, participatedIn and isAffiliatedTo, were less temporally variable than playsFor but still variable, and learned intermediate average scalars.The passage does not provide the intermediate scalar values.Source: Learned scalars on a subset of YAGO · p. 13
  • For graduatedFrom, created, wroteMusicFor, and hasWonPrize, the reported average scalars were 0.74, 0.59, 0.86, and 1.27, respectively.Their facts hold at single distinct moments rather than over time ranges; the authors conclude learned scalars reflect relation-level temporal variability.Source: Learned scalars on a subset of YAGO · pp. 13–14

Robustness analysis

The dimensionality analysis reports robust BoxTE performance across tested dimensions on ICEWS14 and ICEWS5-15, while GDELT MRR kept rising throughout the feasible range.

Robustness analysis

  • On ICEWS14, BoxTE reached state-of-the-art results in the constrained-parameter setting at d = 154, came within 1% of its best performance at d = 500, and peaked at d = 1000.Performance decreased slightly at higher dimensions.Source: Robustness analysis · p. 14
  • On ICEWS5-15, d = 500 came within 0.02 MRR of the best result, and no overfitting was observed even at d = 2000.The authors characterize performance as strong across settings from 500 to 2000 dimensions on ICEWS14 and ICEWS5-15.Source: Robustness analysis · p. 14
  • On GDELT, MRR increased across the tested computationally feasible dimensionalities, suggesting BoxTE may not have reached its best performance there.The authors also note GDELT’s complexity and information density.Source: Robustness analysis · p. 14

Ablation studies

The ablations examine temporal regularization, alternative time representations, relation-specific temporal scalars, and loss functions. BoxTE performs strongly without regularization, while the comparisons also show the importance of its time representation, relation scaling, and cross-entropy training.

Temporal regulariser

  • Without temporal regularization, BoxTE becomes best-performing, reaching MRR 0.608 on ICEWS14 and 0.657 on ICEWS5-15; regularization is detrimental on GDELT.ChronoR and TeLM each report below 0.6 on ICEWS14, and TNTComplEx below 0.65 on ICEWS5-15; Figure 3 says regularization prevents overfitting at large k.Source: Ablation studies · p. 14, Figure 3 · p. 15

Model variants

  • TBoxE and DE-BoxE significantly underperform BoxTE, indicating its gains stem from the novel time representation rather than BoxE expressiveness alone.The passage attributes difficulty to sine's periodic and sigmoid's monotonic assumptions, which may not match the data and make fitting all relevant timestamps difficult.Source: Table 9 · p. 15, Ablation studies · p. 15

Temporal scalars

  • Disabling relation scaling lowers ICEWS14 MRR by .043, while using k = 1 alone causes no significant ICEWS14 drop, unlike on ICEWS5-15.The comparison tests default modular time bumps, scaling only, and relation-independent bumps.Source: Ablation studies · p. 15, Table 10 · p. 15

Loss function

  • Cross-entropy consistently beats adversarial negative sampling on ICEWS14; its MRR advantage shrinks from 4.2% (.023 points) at dim 154 to 0.5% (.003 MRR points) at dim 1000.Adversarial negative sampling also requires tuning the margin γ and adversarial temperature α.Source: Figure 4 · p. 16, Ablation studies · p. 16
Loading 2109.08970v1…