Time in a Box: Advancing Knowledge Graph Completion with Temporal Scopes

Ling Cai, Krzysztof Janowicz, Bo Yan, Rui Zhu, Gengchen Mai

TL;DR

TIME2BOX is a novel framework for Temporal Knowledge Graph Completion (TKGC) that treats time as a filter rather than just another feature. By representing sets of potential answers as "boxes" (axis-aligned hyper-rectangles) in a vector space, the model can naturally handle both atemporal facts and those with complex, often missing, temporal scopes, outperforming current state-of-the-art methods in both link and time prediction.

What Problem Does This Paper Address?

Knowledge Bases (KBs) like Wikidata store facts as triples: (subject, relation, object). However, many facts are only true for a specific time—for example, (Albert Einstein, educatedAt, ETH Zurich, 1896-1900). While Temporal Knowledge Graph Completion (TKGC) aims to fill in missing pieces of these time-aware facts, it faces two major hurdles:

  1. Missing Data: In real-world KBs, temporal information is frequently missing. Prior models often ignore these "messy" cases or assume every statement must have a known time scope, which limits their utility on generic datasets.
  2. Evaluation Flaws: Current metrics for predicting time intervals (like aeIOU) fail to distinguish between "near misses" and "far misses" when a predicted time interval doesn't overlap with the ground truth.

Methods

The authors introduce TIME2BOX, which is built on the intuition that the answers to a temporal query—e.g., "Where did Einstein work in 1933?"—are always a subset of the answers to the broader, time-agnostic query "Where did Einstein work?".

Key Components:

  • Box Embeddings: Instead of representing entities as single points, TIME2BOX represents sets of potential answer entities as boxes (hyper-rectangles) in a high-dimensional space. An entity is considered a valid answer if its point embedding falls inside the box.
  • Time as a Filter: The model uses two types of "projectors":
  • Relation Projector ($OP_r$): Creates a box containing all entities that satisfy the relation (e.g., all places Einstein ever worked).
  • Time Projector ($OP_t$): Creates a box containing all entities relevant to a specific time (e.g., everything relevant to 1933).
  • Intersection Operator: The final answer set is found by calculating the intersection of these boxes. This naturally models the narrowing down of possibilities as more constraints (like specific years) are added.
  • gaeIOU Metric: To better evaluate time prediction, the authors proposed Generalized Affinity Enhanced Intersection Over Union (gaeIOU). Unlike previous metrics, gaeIOU penalizes the "gap" between non-overlapping intervals, providing a more granular look at model performance.

Datasets

The model was evaluated on two Wikidata-based datasets:

  • WIKIDATA12k: A standard benchmark where every statement has a time interval.
  • WIKIDATA114k: A new, larger, and "messier" dataset extracted by the authors. It contains 1.7 million statements, including many that are truly atemporal or are missing their validity information, making it a more realistic test for generic KBC.

Key Insights and Ideas

  • The Subset Intuition: The most powerful idea here is modeling temporal reasoning as a set-filtering process. By using intersections, the model can handle various time types (instants, open intervals, closed intervals) within a single, unified geometric framework.
  • Boxes vs. Points: Traditional point-based embeddings struggle to represent "sets" of answers. Boxes are mathematically elegant for this because the intersection of two axis-aligned boxes is always another axis-aligned box.
  • Learning Entity Classes: Qualitatively, the boxes seem to learn semantic categories. For a query about "education," the model's predicted box naturally encloses entities that are universities, even if they aren't the correct specific answer, showing the model understands the "type" of the expected object.

Key Results

  • Link Prediction: TIME2BOX consistently outperformed SOTA models like TNTComplEx and TIMEPLEX. On WIKIDATA12k, it improved HITS@1 (the accuracy of the top-1 prediction) by over 5 percentage points.
  • Time Prediction: The gains here were even more significant. Using the new gaeIOU metric, TIME2BOX outperformed the baseline by significant margins (e.g., a 15.81 point gain on WIKIDATA114k for gaeIOU@10).
  • Robustness: The model showed a much better Mean Rank (MR). While baselines sometimes produced "extremely bad" predictions (ranking the correct answer in the 300s), TIME2BOX's box constraints kept its guesses much closer to the target.

Limitations and Future Work

  • Parameter Complexity: As shown in the model comparison, TIME2BOX requires more parameters than some simpler point-based models due to the nature of box offsets and intersection attention mechanisms.
  • Spatial Scopes: The authors acknowledge that facts often have spatial scopes (where they are valid) in addition to temporal ones. They suggest that the "Box" framework could be extended to handle geographic constraints in future research.
  • Granularity: The current model operates on a fixed time granularity (e.g., years). Handling mixed granularities (days vs. centuries) remains a challenge for future iterations.

Summary updated

Abstract

Almost all statements in knowledge bases have a temporal scope during which they are valid. Hence, knowledge base completion (KBC) on temporal knowledge bases (TKB), where each statementmay be associated with a temporal scope, has attracted growing attention. Prior works assume that each statement in a TKBmust be associated with a temporal scope. This ignores the fact that the scoping information is commonly missing in a KB. Thus prior work is typically incapable of handling generic use cases where a TKB is composed of temporal statements with/without a known temporal scope. In order to address this issue, we establish a new knowledge base embedding framework, called TIME2BOX, that can deal with atemporal and temporal statements of different types simultaneously. Our main insight is that answers to a temporal query always belong to a subset of answers to a time-agnostic counterpart. Put differently, time is a filter that helps pick out answers to be correct during certain periods. We introduce boxes to represent a set of answer entities to a time-agnostic query. The filtering functionality of time is modeled by intersections over these boxes. In addition, we generalize current evaluation protocols on time interval prediction. We describe experiments on two datasets and show that the proposed method outperforms state-of-the-art (SOTA) methods on both link prediction and time prediction.
BibTeX
@inproceedings{cai2021time,
  author = {Ling Cai and Krzysztof Janowicz and Bo Yan and Rui Zhu and Gengchen Mai},
  title = {{Time in a Box: Advancing Knowledge Graph Completion with Temporal Scopes}},
  booktitle = {K-CAP},
  year = {2021},
  url = {https://openreview.net/forum?id=7eJKT0k2zx},
}

Loading related content...

Figure