Source-linked AI summary
Search from History and Reason for Future: Two-stage Reasoning on Temporal Knowledge Graphs
Zixuan Li, Xiaolong Jin, Saiping Guan, Wei Li, Jiafeng Guo, Yuanzhuo Wang, Xueqi Cheng
TL;DR
Future-fact prediction in temporal knowledge graphs is challenging, and existing approaches may overlook useful historical clues. CluSTeR searches for clues with reinforcement learning and reasons over their temporal organization; it outperforms baselines across ICEWS datasets and its clues provide interpretability.
Problem
Existing temporal-KG models underemphasize finding relevant historical clues, although answers may be reachable through non-repetitive and multi-hop paths.
Source: §1 · p. 2Method
CluSTeR uses reinforcement-learning beam search to find historical clue paths, then applies GCN- and GRU-based temporal reasoning to deduce answers from graphs built from those clues.
Source: §1 · p. 2, §3.3.1 · p. 3Results
CluSTeR consistently outperforms baselines on all ICEWS datasets; on ICEWS14, it improves 7.1% in MRR, 4.5% in Hits@1, and 13.7% in Hits@10 over the best baselines.
Source: §4.2 · p. 6Takeaways & Limitations
Abstract
from arXiv · showhide
Temporal Knowledge Graphs (TKGs) have been developed and used in many different areas. Reasoning on TKGs that predicts potential facts (events) in the future brings great challenges to existing models. When facing a prediction task, human beings usually search useful historical information (i.e., clues) in their memories and then reason for future meticulously. Inspired by this mechanism, we propose CluSTeR to predict future facts in a two-stage manner, Clue Searching and Temporal Reasoning, accordingly. Specifically, at the clue searching stage, CluSTeR learns a beam search policy via reinforcement learning (RL) to induce multiple clues from historical facts. At the temporal reasoning stage, it adopts a graph convolution network based sequence method to deduce answers from clues. Experiments on four datasets demonstrate the substantial advantages of CluSTeR compared with the state-of-the-art methods. Moreover, the clues found by CluSTeR further provide interpretability for the results.
1 Introduction
Future-fact prediction in temporal knowledge graphs calls for finding relevant historical clues and reasoning over their timing. CluSTeR combines reinforcement-learning clue search with temporal reasoning, and its experiments show improved performance and interpretable results.
1 Introduction
- Human prediction is described as first recalling relevant 1-hop and 2-hop historical clues, then reasoning over their temporal information to refine candidate answers.The example rules out the police station because the visit occurred more than two months before the diagnosis.Source: §1 · pp. 1–2
- On ICEWS18, answers are reachable through repetitive 1-hop paths for 41.2% of training queries, through repetitive and non-repetitive 1-hop paths for almost 64.6%, and through 1-hop and 2-hop paths for 86.2%.These figures motivate looking beyond repetitive 1-hop history.Source: §1 · p. 2
- Existing models are described as underemphasizing clue search, while some focus on all historical facts or repetitive 1-hop paths despite other useful historical information.On ICEWS18, the cited path-coverage figures show answers may also be reached through non-repetitive and 2-hop paths.Source: §1 · p. 2
- CluSTeR has two stages: reinforcement-learning clue search induces paths from history, then GCN and GRU process graphs derived from those clues to deduce answers.The authors frame the stages as inspired by human cognition.Source: §1 · p. 2
- The authors report that CluSTeR performs consistently and significantly better on popular TKGs, and that its discovered clues provide interpretability for reasoning results.The stated contributions also include learning an RL beam-search policy to find explicit, reliable clues.Source: §1 · p. 2
2 Related Work
Related work spans static-knowledge-graph reasoning and temporal-knowledge-graph prediction. The paper distinguishes its future-prediction setting from interpolation and highlights limits in temporal modeling, clue coverage, and interpretability.
2 Related Work
- Embedding-based static KG models learn entity and relation representations, while multi-hop methods learn symbolic rules from relation paths; neither group handles temporal dependencies among facts.The paper notes that embedding-based models can underestimate symbolic compositionality, limiting their use in more complex reasoning tasks.Source: §2 · p. 2
- Temporal KG reasoning includes interpolation for missing historical facts and extrapolation for predicting future facts, the setting addressed by this paper.Prior approaches include temporal point processes, continuous-time modeling, and event-summary word graphs.Source: §2 · p. 2
- RE-NET and CyGNet use heuristic clue search and mainly model repetitive facts, potentially missing informative history or including noise; prior models generally offer little interpretability.RE-NET models a sequence of subgraphs of 1-hop facts, while CyGNet models repetitive facts with a sequential copy network.Source: §2 · pp. 2–3
3 The Proposed CluSTeR Model
The section introduces notation before presenting the CluSTeR model and its training procedure.
3 The Proposed CluSTeR Model
- The section begins with notation and then introduces the model and its training procedure.The supplied section passage provides this roadmap only.Source: §3 · p. 3
3.1 Notations
The notation defines temporal knowledge graphs as timestamped relational graphs and specifies the prediction task. It also defines clue paths and how their hops yield historical clue facts.
3.1 Notations
- A temporal knowledge graph is a directed, multi-relational graph with timestamped edges, and a fact is represented as a subject, relation, object, and timestamp quadruple.The task predicts a missing object or subject entity from historical facts before the query timestamp; experiments focus on missing objects.Source: §3.1 · p. 3
- A clue path is a sequence of relation–entity hops from the query subject, and each hop maps to corresponding facts from history before the query timestamp.The path length is bounded by the maximum step number.Source: §3.1 · p. 3
3.2 Model Overview
CluSTeR coordinates clue searching and temporal reasoning as fast and slow thinking to predict future facts.
3.2 Model Overview
- Stage 1 searches historical clue paths whose compositional semantics relate to the query under time constraints.It provides the clue paths and candidate entities to Stage 2.Source: §3.2 · p. 3
- Stage 2 models temporal information among clue facts to produce the final results.The two stages interact during training and jointly decide the answer at inference.Source: §3.2 · p. 3
- The stages are framed as fast and slow thinking, respectively, inspired by human cognition.Source: §3.2 · p. 3
3.3 Stage 1: Clue Searching
CluSTeR treats clue searching as a learnable sequential decision process, using time-constrained search and a semantic policy to find multiple candidate paths.
3.3 Stage 1: Clue Searching
- A learnable, efficient search strategy is needed because heuristic extraction of repetitive 1-hop paths can miss informative historical clues.Source: §3.3 · p. 3
3.3.1 The RL System
- The MDP agent starts at the query subject and traverses outgoing edges by randomized beam search to find B promising clue paths, stopping at maximum step I.States track the visited entity, previous-action timestamp, and shared query; transitions update to an entity incident to the selected action.Source: §3.3.1 · pp. 3–4
- Time-constrained actions limit facts to within m of the query timestamp and within ∆ of the previous action, while a self-loop permits termination.Source: §3.3.1 · p. 4
- At search termination, the agent receives a binary correctness reward and, for a correct target, a real-valued reward from Stage 2.Source: §3.3.1 · p. 4
3.3.2 Semantic Policy Network
- The semantic policy scores actions from the current state and timestamp-free search history, encoding candidate clue paths with an LSTM.The policy does not consider timestamps, although the available actions are time-constrained.Source: §3.3.2 · p. 4
3.3.3 Randomized Beam Search
- Randomized beam search injects noise into beam selection to increase exploration while retaining multiple clue-path candidates.At each step it expands each path with its B most likely actions, then selects paths by scoring or uniform sampling.Source: §3.3.3 · p. 4
3.4 Stage 2: Temporal Reasoning
Stage 2 represents clue facts as timestamp-indexed graphs, models their structure and temporal sequence, and scores candidate entities.
3.4 Stage 2: Temporal Reasoning
- Clue facts are grouped into a sequence of multi-relational graphs, one graph for each timestamp, to capture structure and temporal information.Source: §3.4 · p. 5
- An RGCN models each timestamp graph; mean-pooled entity embeddings are combined with subject and query-relation embeddings and fed to a GRU.The GRU output goes to an MLP decoder that scores all entities.Source: §3.4 · p. 5
- The final entity scores rerank candidates and provide a beam-level reward to Stage 1 equal to the score of the target entity.Source: §3.4 · p. 5
3.5 Training Strategy
The two stages use separate objectives and a phased training procedure before joint optimization.
3.5 Training Strategy
- Stage 1 trains its beam-search policy by maximizing expected reward over training queries with REINFORCE.Source: §3.5 · p. 5
- Stage 2 uses a cross-entropy objective and the Adam optimizer to learn its parameters.Source: §3.5 · p. 5
- Training pretrains Stage 1 with binary reward, trains Stage 2 while Stage 1 is frozen, and then jointly trains both stages.The paper describes the stages as mutually correlated.Source: §3.5 · p. 5
4 Experiment
CluSTeR is evaluated on four TKG datasets against static and temporal baselines, with analyses of its stages, clues, interpretability, and time-aware filtering. It outperforms baselines on all ICEWS datasets, while the reported GDELT results are poor across static and temporal models.
4.2 Results on TKG Reasoning
- On TKG reasoning, CluSTeR consistently outperforms baselines across all ICEWS datasets; on ICEWS14, its gains over the best baselines are 7.1% MRR, 4.5% Hits@1, and 13.7% Hits@10.Source: §4.2 · p. 6
- GDELT results are similarly poor for static and temporal models; 28 of its 50 most frequent entities are abstract concepts, involved in 43.72% of corresponding events.The paper says these abstract concepts make future prediction under the raw setting almost impossible, for example when a president’s country is unknown.Source: §4.2 · pp. 6–7
4.3 Ablation Study
- Using Stage 1 alone reduces results because it ignores temporal information, while Stage 2 with only repetitive clues reduces results on ICEWS but performs best on GDELT.The authors attribute the GDELT result to repetitive clues alleviating noise from abstract concepts.Source: §4.3 · p. 7
- On ICEWS datasets, extending Stage 1 to 2-hop paths reduces performance; the authors report no strong dependencies between query relations and sampled 2-hop paths.They conclude longer paths bring exponential noise clues and leave evaluation on more complex datasets for future work.Source: §4.3 · p. 7, Table 4 · p. 8
4.4 Detail Analysis
- Stage 1 finds non-repetitive clue paths that can encode causal relations, and non-repetitive clues make up more than 93% of Stage 2 clue facts.Repetitive clue facts account for less than 7%; the authors say the abundance of non-repetitive facts helps explain CluSTeR’s stronger performance.Source: Figure 3 · p. 7, §4.4 · p. 8, Figure 4 · p. 8
4.5 Case Study
- In the case studies, Stage 1 can rank a wrong candidate above the correct one, while Stage 2 uses timestamps and temporal patterns to support the answer.For the Congress query, temporal clues favor Iran over China; for the China query, period information supports Japan as the answer.Source: §4.5 · p. 8, Figure 5 · p. 9
4.6 Performance under the Time-aware Filtered Setting
- Under time-aware filtering, only facts occurring at the predicted time are removed, and results are close to the raw setting because few facts are removed.The paper contrasts this with the commonly used filtered setting, which ignores time information and can yield over-optimistic performance.Source: §4.6 · pp. 8–9, Table 5 · p. 9
5 Conclusions
CluSTeR combines RL-based clue searching with GCN-based temporal reasoning on sequences of graphs. The authors report substantial advantages on TKG reasoning and frame the model’s motivation as scientific research.
5 Conclusions
- CluSTeR finds reliable historical clue paths and candidate entities with RL, then organizes clue facts into graph sequences for temporal deduction.The paper reports substantial advantages on TKG reasoning.Source: §5 · p. 9