Source-linked AI summary
TimeTraveler: Reinforcement Learning for Temporal Knowledge Graph Forecasting
Haohai Sun, Jialun Zhong, Yunpu Ma, Zhen Han, Kun He
TL;DR
Forecasting future facts in temporal knowledge graphs requires handling future timestamps and previously unseen entities, challenges that limit existing reasoning approaches. TimeTraveler uses reinforcement learning to traverse historical snapshots with relative time encoding, time-shaped rewards, and unseen-entity representations. Across four benchmark datasets, it outperforms existing methods while using less computation and fewer parameters, with explainable inference and inductive reasoning ability.
Problem
TKG research has focused mainly on completing missing facts at past timestamps, leaving future forecasting with unseen timestamps and entities insufficiently addressed.
Method
TimeTraveler uses temporal-path-based reinforcement learning to traverse historical snapshots, modeling time relatively and representing unseen entities with Inductive Mean.
Results
TITer outperforms state-of-the-art baselines while saving at least 50.3% parameters and 94.9% MACs.
Takeaways & Limitations
The inference process is explainable, and the model has good inductive reasoning ability for unseen entities.
Abstract
from arXiv · showhide
Temporal knowledge graph (TKG) reasoning is a crucial task that has gained increasing research interest in recent years. Most existing methods focus on reasoning at past timestamps to complete the missing facts, and there are only a few works of reasoning on known TKGs to forecast future facts. Compared with the completion task, the forecasting task is more difficult that faces two main challenges: (1) how to effectively model the time information to handle future timestamps? (2) how to make inductive inference to handle previously unseen entities that emerge over time? To address these challenges, we propose the first reinforcement learning method for forecasting. Specifically, the agent travels on historical knowledge graph snapshots to search for the answer. Our method defines a relative time encoding function to capture the timespan information, and we design a novel time-shaped reward based on Dirichlet distribution to guide the model learning. Furthermore, we propose a novel representation method for unseen entities to improve the inductive inference ability of the model. We evaluate our method for this link prediction task at future timestamps. Extensive experiments on four benchmark datasets demonstrate substantial performance improvement meanwhile with higher explainability, less calculation, and fewer parameters when compared with existing state-of-the-art methods.
1 Introduction
The paper targets extrapolated TKG reasoning, which forecasts future facts rather than completing missing facts at past timestamps. It addresses unseen timestamps and entities with an explainable temporal-path-based reinforcement learning model.
- Extrapolated TKG reasoning forecasts future facts, whereas most existing methods complete missing facts at past timestamps.
- Forecasting must handle timestamps absent from training data and newly emerging entities in predicted facts.
- Existing extrapolation methods use random vectors for unseen entities and cannot explicitly indicate how historical facts affect predictions.
- TITer traverses historical KG snapshots from the query subject toward an answer using relative time encoding and a Dirichlet-based time-shaped reward.
- Inductive Mean representation uses query and trained entity embeddings to represent unseen entities without increasing computational cost.
- The authors report substantial gains over existing methods with less calculation and fewer parameters.
2 Related Work
Related work spans embedding-based, deep-learning, path-based, and temporal approaches to knowledge-graph reasoning. Temporal models address interpolation and extrapolation through evolving representations, message passing, point processes, differential equations, recurrent modeling, and repeated historical patterns.
- Embedding-based methods score candidate facts using entity and relation embeddings, while CNNs and GNNs encode deeper semantics or neighborhood information.
- Path-based reinforcement learning frames KG reasoning as a Markov decision process for finding entity paths, offering greater explainability than embedding-based methods.
- Many temporal models redesign embeddings, score functions, or message-passing networks for interpolation over timestamped graph snapshots.
- Extrapolation methods model evolving facts with temporal point processes, neural ordinary differential equations, recurrent networks, or repeated historical patterns.
- The surveyed extrapolation approaches lack explanatory predictions and cannot handle previously unseen entities.
3 Methodology
TITer formulates extrapolated TKG reasoning as temporal walk-based query answering over historical snapshots. It combines relative-time representations, reinforcement-learning search with shaped rewards, and an inductive representation for unseen entities.
- Task and reinforcement-learning framework: TITer models extrapolation as walk-based query answering, starting from the query subject and traversing historical temporal edges toward the target.The agent operates within an MDP whose state includes the current node and the query information.
- Task and reinforcement-learning framework: The temporal graph adds reversed, self-loop, and temporal edges so the agent can reverse queries, stop, and move across historical snapshots.Temporal edges connect a later node to earlier facts whose timestamps precede the query time.
- Task and reinforcement-learning framework: At each step, TITer samples an outgoing action from candidate historical edges, scores transitions with its policy network, and receives a terminal or time-shaped reward.The terminal reward is 1 for reaching the correct target and 0 otherwise; the shaped reward uses a relation-specific Dirichlet distribution over recent snapshots.
- Policy network: Relative time encoding represents each node using the query-time gap, while an LSTM encodes the sequence of relations and visited nodes.The dynamic embedding combines invariant entity features with relation and relative-time representations.
- Inductive Mean representation: Inductive Mean represents unseen entities by aggregating embeddings of trained entities sharing observed co-occurrence relations and updating the representation over time.The mechanism uses query information and trained entity embeddings to assign a more informative initial representation to newly emerging entities.
4 Experiments
Experiments on four temporal knowledge graph datasets evaluate forecasting accuracy, inductive inference, explainability, efficiency, and component contributions. TITer consistently performs strongly, including on future timestamps and queries containing unseen entities, while using fewer parameters and less computation.
- Performance on the TKG datasets: TITer outperforms all baselines on MRR and Hits@1 across four datasets, and leads most other metrics except ICEWS18.Interpolated methods perform worse because they cannot handle unseen timestamps in the test set.
- Inductive inference: TITer addresses unseen-entity queries through temporal-path reinforcement learning and outperforms xERTE with or without the IM mechanism.RE-NET and CyGNet fall below a 3-hop neighborhood random-search baseline, whereas IM further improves TITer’s performance.
- Case study: TITer’s reasoning paths use recent temporal facts, adapt attention between nodes and edges, and support multi-hop reasoning, including cases with unseen entities.The ICEWS18 case study reports different timestamp-based paths for similar queries and combinational reasoning in a multi-hop example.
- Efficiency analysis: TITer reduces parameters by at least 50.3% and MACs by 94.9% versus previous state-of-the-art models while retaining better performance.Compared with xERTE, TITer uses at most half the parameters and 0.225M Multi-Adds operations.
- Ablation study: Relative time encoding improves Hits@1 by 13.19% on ICEWS18 and 18.51% on WIKI over the static variant.The ablation indicates that temporal modeling helps TITer choose the correct answer more precisely.
- Ablation study: Reward shaping improves Hits@1 by 5% over the variant without reward shaping, while weighted action scoring improves evidence-source selection.The reward uses a Dirichlet prior to model the probability distribution of the target’s appearance over the historical time span.
5 Conclusion
TimeTraveler (TITer) is a temporal-path-based reinforcement learning model for temporal knowledge graph forecasting. It searches historical snapshots using time modeling and an inductive mechanism for unseen entities, achieving strong performance with explainability and efficiency.
- TITer searches historical TKG snapshots for temporal evidence chains to answer future forecasting queries.
- TITer models time with relative time encoding and a time-shaped reward.
- TITer updates unseen entities’ representations during testing through the IM mechanism.
- Extensive experiments show that TITer outperforms state-of-the-art baselines with less calculation and fewer parameters.
- TITer provides explainable inference and good inductive reasoning ability.
A.1 Definitions for Evaluation Metrics
The evaluation uses MRR and Hits@k for object and subject prediction, ranking entities searched by beam search. Filtering must account for temporal changes because static filtering can remove valid candidates.
- Performance is evaluated with Mean Reciprocal Rank and Hits@k, using k values of 1, 3, and 10.
- Each test quadruple produces an object query and a subject query for entity ranking.
- Beam search ranks candidate entities according to transition probability, assigning dataset-size rank when the ground truth is absent from the searched set.
- Static filtering can remove entities associated with facts at different timestamps, making it inappropriate for temporal knowledge graphs.
A.2 Dataset Statistics
The datasets comprise event-based and time-span temporal knowledge graphs represented as timestamped quadruples. Timestamp-based splitting creates test cases containing entities unseen during training.
- Dataset statistics report training, validation, and test quadruple counts together with total entity and relation counts.
- ICEWS14 and ICEWS18 are event-based knowledge graphs, while WIKI and YAGO contain temporal facts with time spans.
- WIKI and YAGO time-span facts are converted into one quadruple for each unit time between their start and end timestamps.
- Timestamp-based splitting causes some test entities not to appear in the training set.
- The unseen-entity statistics distinguish new entities and test quadruples with unseen objects, unseen subjects, or both.
A.3 Detailed Implementation
Implementation uses grid-searched hyperparameters, fixed network dimensions, limited recent outgoing-edge actions, beam-search testing, and released code or defaults for comparison methods.
- Hyperparameters search: Grid search varies μ, the number of outgoing edges, path length, and activation functions.
- Details of TITer: TITer uses entity, relation, node, LSTM, and MLP dimensions of 80, 100, 100, 100, and 100, respectively.
- Details of TITer: The agent considers the latest N outgoing edges and uses a reasoning path length of 3.
- Details of Training: Training uses an additive control-variate baseline, entropy regularization, REINFORCE discount factor γ=0.95, and Adam optimization.
- Details of Testing: Testing uses beam search with beam size 100 and retains the highest path score when multiple paths reach the same entity.
- Details of other Methods: Comparison methods are implemented with released code and default parameters, with separate CyGNet models trained for object and subject prediction.
A.4 Model Robustness
TITer is evaluated across four datasets using five random seeds with fixed hyperparameters. The reported results indicate stable performance across runs.
- TITer is run five times on all datasets with fixed hyperparameters and different random seeds.
- Table 9 reports TITer’s mean and standard deviation across the five runs on four datasets.
- TITer demonstrates a small standard deviation, indicating robustness across runs.
A.5 Estimating a Dirichlet Distribution
The section describes estimating Dirichlet-distribution parameters from multinomial samples. It introduces the log-likelihood gradient and notes fixed-point iteration, leave-one-out likelihood, and Newton–Raphson inversion as computational tools.
- A Dirichlet distribution of order k has parameters α = {α1, α2, ..., αk}, with αk > 0 and probabilities summing to one.
- The estimation procedure observes multinomial samples D, where n_k denotes the count for the corresponding category.
- The gradient of the log-likelihood is used to estimate the Dirichlet parameters.
- The maximum can be computed by fixed-point iteration, while leave-one-out likelihood and Newton–Raphson inversion provide additional optimization options.