1 Introduction↩︎

Temporal Knowledge Graphs (TKGs) have emerged as a pivotal graph-based data structure for modeling dynamic relationships that evolve over time. Formally, a TKG is composed of events, and each event is represented in a quadruple (subject, relation, object, timestamp). Compared to static knowledge graphs, TKGs incorporate the temporal information, enabling systems to capture how events change over time. As a result, TKGs have been widely used in downstream applications, such as recommendation systems [1] and question answering [2], [3].

In this work, we focus on TKG reasoning under the extrapolation setting, where the goal is to answer a query \((e_q,r_q,?,t_q)\) by predicting the missing entity using only events with timestamps \(t<t_q\). Prior work has proposed a variety of approaches for this task [4]–[6]; however, these methods are typically less interpretable because they do not explicitly expose the underlying reasoning process. In contrast, multi-hop reasoning methods [7]–[10] output explicit temporal paths as evidence, which can reveal why a prediction is made and provide human-checkable supporting events. As shown in Figure 1, given a query \((\textit{COVID19}, \textit{occur\_at}, ?, \text{2022-10-17})\), a multi-hop reasoner predicts the missing object by outputting a path that starts from the subject entity ("COVID19") and ends at the predicted entity (e.g., "Restaurant A").

However, multi-hop reasoning methods comes with a major optimization challenge. At each time step, the agent must choose from a large set of timestamped outgoing edges, and the number of possible trajectories grows exponentially with the hop budget. Moreover, TKG reasoning usually incorporates temporal validity (e.g., non-decreasing timestamps) so the action space is not only large but also time-dependent: an outgoing edge at one entity may become invalid due to timestamp constraints. As a result, most sampled trajectories terminate without receiving a reward, leading to sparse terminal rewards and slow, unstable reinforcement learning (RL) training.

To address this, we propose RAPTOR, to the best of our knowledge the first self-supervised pretraining method tailored for RL-based multi-hop reasoning on TKGs. RAPTOR injects a reachability-aware inductive bias into the agent by pretraining the policy to estimate whether each candidate action can reach the target entity within the hop budget while satisfying temporal constraints. This pretraining objective directly mitigates the wasted exploration problem: unreachable actions (i.e., those with no temporally valid path to the target entity within \(K\) steps) are down-weighted early, so the subsequent RL phase focuses on feasible parts of the graph.

Our contributions: (i) we introduce a reachability-based self-supervised task for temporal multi-hop reasoning, (ii) we design an efficient labeling procedure to construct reachability supervision under temporal constraints, and (iii) we demonstrate consistent improvements in both convergence speed and final accuracy on ICEWS14, ICEWS05-15, and ICEWS18.

2 Related works↩︎

2.1 Multi-hop Reasoning on Static Knowledge Graphs↩︎

Multi-hop reasoning on static knowledge graphs is often trained with RL, but it typically suffers from sparse terminal rewards and large action spaces. To improve exploration, prior work introduces denser guidance before or during RL. DeepPath [11] mines paths between source and target entities using bidirectional breadth-first search (BFS) and then pretrains the agent via supervised imitation of these paths, which increases the probability of sampling rewarding trajectories during RL. Multi-hop KG [12] performs reward shaping with embedding-based scores, assigning soft rewards to non-target entities to provide more informative feedback. SSRL [13] uses BFS-derived label to identify actions with high-expected-return at each state and pretrains the policy to encourage efficient exploration. However, these methods do not consider temporal constraints and thus cannot be applied to TKG reasoning.

2.2 Temporal Knowledge Graph Reasoning↩︎

Unlike static knowledge graphs, TKGs attach timestamps to events, which leads to different settings (interpolation and extrapolation) in TKG reasoning. The interpolation setting aims to predict missing object entity at historical records [14]–[17]. In contrast, the extrapolation setting focuses on forecasting future events using past observations; in this work, we adopt the extrapolation setting. Previous works explore diverse modeling paradigms for extrapolation. For example, [18] studies explainable TKG reasoning by providing human-interpretable rationales, while [5], [6] model temporal dynamics with recurrent and relational GNN architectures. CyGNet [4] further adopts a generative forecasting framework to predict future events from historical sequences.

2.3 Multi-hop Reasoning on Temporal Knowledge Graphs↩︎

Similar to knowledge graph reasoning, multi-hop reasoning on TKGs is typically trained with RL, but it must additionally satisfy temporal constraints. As a result, the agent operates in a time-dependent action space, which makes RL optimization challenging under sparse rewards. As a basic RL formulation, TAgent [10] applies the multi-hop agent framework to TKGs without using additional auxiliary signals. Prior work has also attempted to improve training efficiency; for example, TITer [7] incorporates time-shaped rewards, TPath [8] adds a path reward, and DREAM [9] leverages demonstration paths with adversarial imitation learning. However, these techniques introduce additional guidance during RL training, meaning the agent must learn effective exploration behaviors on the fly, which can increase the reliance on careful signal design due to the potential interference with other training objectives.

3 Preliminaries↩︎

3.1 Temporal Knowledge Graphs↩︎

A TKG is a collection of time-stamped events, denoted by graph \(\mathcal{G} = (\mathcal{E}, \mathcal{R}, \mathcal{T}, \mathcal{Q})\), where \(\mathcal{E}\), \(\mathcal{R}\), \(\mathcal{T}\), and \(\mathcal{Q}\) represent the sets of entities, relations, timestamps, and events, respectively. The set of events \(\mathcal{Q} \subseteq \mathcal{E} \times \mathcal{R} \times \mathcal{E} \times \mathcal{T}\) contains quadruples \((e_s, r, e_o, t)\), representing a relation \(r\) between entity \(e_s\) and entity \(e_o\) at timestamp \(t\). In this work, the notation \(t < \hat{t}\) denotes that timestamp \(t\) precedes \(\hat{t}\) (i.e., the event at \(t\) occurs earlier than the one at \(\hat{t}\)).

Following [7], [19], we augment the TKG with inverse edges. For each quadruple \((e_s, r, e_o, t) \in \mathcal{Q}\), we add a corresponding inverse quadruple \((e_o, r^{-1}, e_s, t)\) to the graph, where \(r^{-1}\) denotes the inverse relation of \(r\).

3.2 Temporal Path↩︎

We define a temporal path as a sequence of quadruples that is temporally valid. Following the settings in [7], [18], [20], a temporal path is considered valid only if the timestamps of consecutive quadruples follow a non-decreasing order. Formally, a temporal path of length \(n\) is denoted as a sequence of quadruples: \[\begin{gather} \bigl((e_{i-1}, r_i, e_i, t_i)\bigr)_{i=1}^{n}, \\ \text{where } t_{i-1} \le t_i,\;\forall i \in \{1, \dots, n\}. \end{gather}\] where \(t_0\) is the initial timestamp, \(e_0\) represents the source entity, and \((e_{i-1}, r_i, e_i, t_i) \in \mathcal{Q}\) represents the \(i\)-th quadruple in the path.

3.3 Problem Formulation↩︎

Given a graph \(\mathcal{G}\) and a query \(q = (e_q, r_q, ?, t_q)\), the goal of TKG reasoning is to infer the missing object entity \(o_{q}\). As mentioned in Section 1, we focus on the extrapolation setting. In this setting, for a query at timestamp \(t_q\), the model is restricted to accessing historical events that occurred before the query timestamp. Formally, the set of available historical events \(\mathcal{H}\) is defined as:

\[\mathcal{H} = \{ (e_s, r, e_o, t) \in \mathcal{Q} \mid t < t_q \}\]

Accordingly, we train the model to estimate the conditional probability of candidate entities and maximize the likelihood of the ground-truth entity \(o_q\) given \(q\) and \(\mathcal{H}\): \[\max_{\theta} P(o_{q} \mid e_q, r_q, t_q, \mathcal{H})\]

Specifically, RL-based multi-hop reasoning methods typically formulate the reasoning task as a Markov Decision Process (MDP). We cast the prediction process as a sequential decision-making task, where the agent starts at \(e_q\) and reaches the target \(o_q\) after executing consecutive actions, as illustrated in Figure 1.

3.4 Reinforcement Learning Framework↩︎

In RL phase, we formulate the prediction process as a MDP. The MDP process is represented by a 4-tuple \((S, A, P, R)\), where \(S\), \(A\), \(P\) and \(R\) denote the state space, action space, transition function, and reward function, respectively. Each component is elaborated as follows.

3.4.1 States↩︎

The state \(s \in S\) is defined as a 5-tuple \((\xi,k,e_k,t_k,v_k)\). Here, \(\xi = (e_q, r_q, t_q)\) is the query information. The scalar \(k \in \{0,\ldots,K\}\) denotes the time step in the MDP and also the current path length, where \(K\) is the maximum path length. The pair \((e_k, t_k)\) denotes the current entity and timestamp. Finally, \(v_k = \{e_0,\ldots,e_k\}\) is the set of visited entities. At initialization, we set \(e_0=e_q\), \(t_0=0\), and \(v_0=\{e_0\}\). We reindex timestamps by shifting the earliest time to 0, so \(t_0=0\) corresponds to the earliest timestamp in the graph. Therefore, the initial state is \((\xi,0,e_0,t_0,v_0)\).

3.4.2 Actions↩︎

The action space \(A\) is defined as a set of all possible actions. The set of candidate actions \(A_s \subseteq A\) is dependent on the current state \(s\). In practice, \(A_s\) corresponds to outgoing edges from \(e_{k}\). To encourage efficiency and non-redundant exploration, we enforce the path to be a simple path by masking actions that revisit previously visited entities, except the self-loop action Stop. Specifically, we define \(A_s = \{(e', r', t') \mid(e_{k}, r', e', t') \in Q, t_k \le t' < t_q,e' \not\in v_k\} \cup \{\mathrm{\small Stop}\}\). The self-loop action Stop \(=(r_{stop}, e_{k}, t_{k})\) allow agent to stay in place.

3.4.3 Transition↩︎

The environment updates the state according to the action selected by the agent. The transition function \(P: S \times A \rightarrow S\) is defined as follows. Given a state \(s\) and an action \(a=(e', r', t') \in A_s\), the next state \(s'\) is \[s' = P(s, a) = (\xi, k+1, e_{k+1}, t_{k+1}, v_{k+1}),\] where \(e_{k+1}=e'\), \(t_{k+1}=t'\), and the visited-entity set is updated as \(v_{k+1}=v_k \cup \{e'\}\). If \(k=K\), the episode terminates without taking the \(K\)-th action.

3.4.4 Rewards↩︎

The agent receives a terminal reward \(R = 1\) if the episode terminates at the ground-truth answer entity \(o_{q}\), and \(0\) otherwise: \[R = \begin{cases} 1, & \text{if episode terminates at } o_q,\\ 0, & \text{otherwise}, \end{cases}\] We train the policy and value networks using the actor-critic algorithm; full optimization details are provided in Appendix 10.

4 Methodology↩︎

We propose RAPTOR, a reachability-aware pretraining framework for temporal multi-hop reasoning. The overall pretraining pipeline (Figure 2) consists of two stages: (i) constructing reachability supervision under temporal constraints via a reachable entity labeling algorithm, (ii) pretraining the policy to identify the candidate actions that can reach the target entity \(o_q\) within the hop budget. After pretraining, we fine-tune the pretrained agent with RL. In this section, we describe the policy network, the reachable-entity labeling algorithm, and the self-supervised pretraining objective.

4.1 Policy Network↩︎

We use a simple policy network with an LSTM path encoder and MLP heads to evaluate RAPTOR. We concatenate the path, query, and step embeddings, then pass the combined vector through a two-layer MLP to form a state representation. This state vector is used to score each candidate action. The detailed architecture is described as follows.

Given a state \(s = (\xi, k, e_k, t_k, v_k)\) and the candidate set \(A_s\), the actor outputs a probability distribution \(\pi_\theta(\cdot\mid s)\) over the candidate actions in \(A_s\), and the critic estimates \(V_\phi(s)\).

4.1.0.1 Embeddings.

We represent each entity \(e\) with a static embedding \(\mathrm{Emb}_\mathcal{E}(e)\in\mathbb{R}^{d_e}\). For relations, we use time-conditioned embeddings. Following [7], we define a temporal encoding \[\boldsymbol{\tau}(\Delta t)=\cos(\mathbf{w}\Delta t+\mathbf{b}),\] where \(\mathbf{w},\mathbf{b}\in\mathbb{R}^{d_t}\) are learnable parameters and \(\Delta t = t_q-t\).

Given a relation \(r\) with timestamp \(t\) and query time \(t_q\), we map \(r\) to its static embedding \(\mathrm{Emb}_\mathcal{R}(r)\) and form a time-conditioned relation embedding by concatenation: \[\mathbf{r}(r,\Delta t)=[\mathrm{Emb}_\mathcal{R}(r);\boldsymbol{\tau}(\Delta t)]\in\mathbb{R}^{d_r}.\]

For action \(a=(e',r',t')\), we construct the action embedding as \[\label{eq14} \mathbf{a}(a) = \big[\mathbf{e'};\mathbf{r}(r',t_q-t')\big]\in\mathbb{R}^{d_a},\tag{1}\] where \(d_a = d_e + d_r\). We also introduce a static step embedding \(\mathrm{Emb}_{\text{step}}(k) \in \mathbb{R}^{d_{\text{step}}}\) to encode the time step and provide the information of remaining hop budget.

4.1.0.2 Temporal path encoding.

We encode the temporal path into an embedding using a single-layer LSTM. At time step \(k\), we have an ordered sequence of taken actions \(\{a_0,a_1,\ldots,a_{k-1}\}\). For each action \(a_i\) in this sequence, we construct its action embedding \(\mathbf{a}_i = \mathbf{a}(a_i)\) as described in Eq. 1 .

When \(k=0\), there is no executed action yet, so we introduce a learnable initial action input, denoted \(\mathbf{a_{\mathrm{init}}}\). We then define the input sequence as \(\{a_{\mathrm{init}}, a_0,\ldots,a_{k-1}\}\) and use the LSTM to update the temporal path embedding as follows: \[\begin{align} \mathbf{h}_0 &= \operatorname{LSTM}(\mathbf{a}_{\mathrm{init}}, \mathbf{h}_{\mathrm{init}}), \\ \mathbf{h}_{i+1} &= \operatorname{LSTM}(\mathbf{a}_i, \mathbf{h}_i), \forall i \in \{0, \ldots, k - 1\}. \end{align}\] where \(\mathbf{h}_{\mathrm{init}} \in \mathbb{R}^{d_a}\) is initialized as a learnable vector.

4.1.0.3 State vector.

To construct the state vector, we first concatenate the embeddings of the query entity, query relation, temporal path, and time step to form \[\mathbf{u} = \Big[ \mathrm{Emb}_\mathcal{E}(e_s); \mathbf{r}(r_q,0); \mathbf{h}_{k}; \mathrm{Emb}_{\text{step}}(k) \Big].\] We then project \(\mathbf{u}\) to \(\mathbb{R}^{d_a}\) with a two-layer MLP to obtain \(\mathbf{s}\): \[\begin{align} \mathbf{s} &= \mathrm{MLP}(\mathbf{u}) \\ &= \mathbf{W}_{\text{head}}\,\sigma(\mathbf{W}_{\text{hidden}}\mathbf{u}+\mathbf{b}_{\text{hidden}})+\mathbf{b}_{\text{head}}, \end{align}\] where \(\sigma(\cdot)\) denotes \(\mathrm{ReLU}\), and \(\mathbf{s}\in\mathbb{R}^{d_a}\) matches the dimensionality of the action embeddings.

4.1.0.4 Action scoring.

At time step \(k\), we score each candidate action by measuring the similarity between the state vector \(\mathbf{s}\) and the embedding of the corresponding action. Specifically, for each \(a\in A_s\), we define its logit as \[z(a)=\langle \mathbf{s},\mathbf{a}(a)\rangle.\] We then obtain the action distribution by applying a softmax over the logits of all candidate actions: \[\pi_{\theta}(a\mid s)=\frac{\exp\left(z(a)\right)}{\sum_{a'\in A_s}\exp\left(z(a')\right)}.\]

4.1.0.5 Value estimation.

In addition, we learn a critic to estimate the expected return from the current state. Given \(\mathbf{u}\) at time step \(k\), the critic applies a two-layer MLP to produce a prediction of scalar value: \[V_{\phi}(\mathbf{u})=\mathrm{MLP}_{\mathrm{crt}}(\mathbf{u})\in\mathbb{R},\] which serves as an estimate of the expected cumulative return used for advantage computation during training.

4.2 Reachable Entity Labeling↩︎

To label candidate actions during self-supervised pretraining, we perform reachable entity labeling for all \((o_q,t_q)\) pairs in the training set. For each pair, we run a backward BFS from \(o_q\) to find entities that can reach \(o_q\) within the hop limit while respecting temporal constraints. The procedure is summarized in Algorithm 3.

Given a graph \(\mathcal{G}\), a training example \((e_q, r_q, o_q, t_q)\), max path length \(K\), and max in-edges \(N\), we initialize a queue with \((o_q, t_q, v, 0)\), where \(v\) is the visited set (initialized as \(\{o_q\}\)) and the hop count is \(0\). We then repeatedly dequeue a tuple \((e_\mathrm{cur}, t_\mathrm{cur}, v_\mathrm{cur}, \ell)\) and examine its incoming edges. For each incoming edge \((e', r', e_\mathrm{cur}, t')\), we discard it if \(e'\) has been visited or if \(t' > t_\mathrm{cur}\) which violates temporal constraints. To reduce computation, we keep only the top-\(N\) incoming edges with the largest timestamps using . If \(e'\) passes these checks, it is reachable: we update the visited set, enqueue \((e', t', v_{new}, \ell+1)\), and record \((\text{entity}, \text{latest timestamp}, \text{hop distance}) = (e', t', \ell+1)\) in \(L\). To avoid duplicate records for the same entity at the same hop distance from \(o_q\), checks whether \(t'\) is the latest timestamp associated with \(e'\) at that hop distance, and removes any existing record of \(e'\) with an earlier timestamp at that hop distance.

4.3 Self-Supervised Pretraining↩︎

The goal of this self-supervised pretraining is to push the predicted score of reachable actions toward 1 and unreachable actions toward 0. For a training example \((e_q, r_q, o_q, t_q)\), we first construct the reachable entity list \(L\) for the pair \((o_q, t_q)\). At time step \(k\), each candidate action \(a = (e', r', t') \in A_s\) is labeled as reachable if \(L\) contains a tuple \((e', \bar{t}, \bar{h})\) such that \(t' \le \bar{t}\) and \(K - k > \bar{h}\); otherwise, it is labeled as unreachable. This produces a binary label \(y(a) \in \{0, 1\}\) for each candidate action.

We then train the policy network to align with \(\boldsymbol{y}\) using a binary cross-entropy loss. The reachability of each candidate action is estimated by applying a sigmoid function to its logit: \[\hat{y}(a) = \operatorname{sigmoid}\big(z(a)\big), \quad \forall a \in A_s,\] where \(\hat{y}(a)\) is the predicted reachability of action \(a\). The self-supervised loss at time step \(k\) is defined as \[\begin{align} \mathcal{L}_{\mathrm{SL}}(\theta) = - \frac{1}{|A_s|} \sum_{a \in A_s} \Big[ y(a) \log \hat{y}(a) \\ + (1 - y(a)) \log (1 - \hat{y}(a)) \Big]. \end{align}\]

During pretraining, we transition to the next time step \(k+1\) by sampling from the output distribution over reachable actions, and repeat this process until reaching the maximum path length. The overall self-supervised loss for an episode is \[\mathcal{L}_{\mathrm{SL}}^{\mathrm{ep}}(\theta) = \mathbb{E}\left[\sum_{k=0}^{K-1} \mathcal{L}_{\mathrm{SL}}^{(k)}(\theta)\right].\]

We optimize the policy network by minimizing \(\mathcal{L}_{\mathrm{SL}}^{\mathrm{ep}}(\theta)\) with stochastic gradient descent.

5 Experiments↩︎

max width=

5.1 Experimental Setup↩︎

We describe the datasets, evaluation metrics, and baselines in this section; implementation details are provided in Appendix 9.

5.1.1 Datasets↩︎

We evaluate RAPTOR on three standard TKG benchmarks: ICEWS14, ICEWS05-15 [21], and ICEWS18 [5]. All are derived from ICEWS and cover events in 2014, 2005–2015, and 2018; statistics are reported in Appendix 8 (Table ¿tbl:tab:dataset95statistics?). Following prior work, we split each dataset into train/validation/test sets by timestamp.

5.1.2 Evaluation Metrics↩︎

We use the following two common metrics in TKG reasoning to evaluate performance:

• Mean Reciprocal Rank (MRR): The average of the reciprocal ranks of the ground-truth entities.

• Hits@k: The proportion of test queries for which the ground-truth entity appears in the top-\(k\) predictions. We report Hits@1, Hits@3, and Hits@10.

Prior work suggests that the time-aware filtered setting [7], [18] is more appropriate than the standard filtered setting [22] or the raw setting [23], because it filters only quadruples that occur at the same timestamp as the query when computing ranks. Therefore, we adopt the time-aware filtered setting for evaluation in all experiments.

5.1.3 Baseline Methods↩︎

We compare our method with several conventional baselines, including xERTE [18], TLogic [19], CyGNet [4], RE-NET [5], and RE-GCN [6].

We also compare with prior multi-hop reasoning methods. To make the comparison focused and fair, we keep model capacity comparable and emphasize differences in training procedures rather than architectural choices; the compared agents mainly use LSTM and MLP components. Specifically, we include TITer [7], TAgent [10], TPath [8], and our ablated variant trained without RAPTOR pretraining (denoted as Pure-RL). To align with our setting, we additionally report a TITer variant with the maximum action size set to 150 (denoted as TITer-150). Aside from these two in-house baselines, the remaining results are taken from previous work [9], [24].

5.2 Experimental Results↩︎

The results are summarized in Table ¿tbl:tab:main95results?. RL-RAPTOR consistently outperforms Pure-RL across all datasets, highlighting the benefit of reachability pretraining. Compared with prior multi-hop reasoning methods, RL-RAPTOR achieves higher scores on most metrics, suggesting that RAPTOR helps the agent learn better multi-hop reasoning strategies during RL. Among the extrapolation baselines, RL-RAPTOR achieves the best performance on ICEWS14 and ICEWS05-15 on most metrics, while ranking second on ICEWS18 behind RE-GCN. Although Hits@10 is not the best on any of the three datasets, RAPTOR still demonstrates strong and stable improvements over competitive baselines overall.

5.2.1 Training Efficiency Analysis↩︎

We compare training efficiency using validation MRR, Hits@k, and the RL reward curve against Pure-RL and TITer-150. Figure 4 shows that RL-RAPTOR converges earlier and achieves better performance on most metrics. RL-RAPTOR remains best overall and the advantage is more pronounced on harder datasets such as ICEWS18, particularly in MRR.

For Hits@k, RL-RAPTOR is stronger on Hits@1 and Hits@3 across most datasets and attains better score early while staying stable. TITer-150 surpasses RL-RAPTOR in Hits@1 on ICEWS05-15 late in training but declines in Hits@3 and Hits@10 as reward increases, suggesting a shift toward a few high-probability paths. By contrast, RL-RAPTOR maintains stronger Hits@3 and Hits@10 later in training, indicating a more robust action-selection policy. Overall, RAPTOR pretraining improves both training efficiency and final performance, and reaches an early-stage MRR that exceeds the final performance of other baselines.

5.3 Ablation Studies↩︎

To assess RAPTOR pretraining, we conduct an ablation study on ICEWS14 and vary the number of pretraining epochs (10, 20, 30, 40, 50). All other hyperparameters in the subsequent RL fine-tuning stage are kept the same as in Appendix 9. Figure 5 reports the average training reward curve and validation MRR bar chart.

5.3.1 Analysis of training efficiency and performance↩︎

The reward curves show that longer pretraining benefits the RL stage: models pretrained for more epochs start at higher reward levels, improving sample efficiency. Without pretraining, reward growth is substantially slower. For example, with only 10 epochs of RAPTOR pretraining, the average reward exceeds \(0.325\) after 50 epochs (60 total epochs including pretraining), whereas Pure-RL needs more than 100 epochs to reach the same level. These results suggest that RAPTOR pretraining steers the agent toward more promising actions and accelerates learning during RL.

For validation MRR, using more pretraining epochs leads to higher MRR in the early stage of RL training. Although this gap gradually narrows as RL training proceeds, even 10 pretraining epochs already yield a clear improvement over no pretraining, and increasing the number of pretraining epochs further strengthens this advantage. Overall, these results suggest that RAPTOR provides a better initialization, improving both training efficiency and final performance.

6 Conclusion↩︎

We propose RAPTOR, a self-supervised pretraining method for multi-hop TKG reasoning. By injecting reachability signals, RAPTOR helps the model filter infeasible actions before RL fine-tuning. We also introduce a reachable entity labeling algorithm to identify reachable entities with timestamps and hop distances. Experiments on three benchmarks show improved training efficiency and final performance over conventional baselines. We hope RAPTOR encourages further advances in self-supervised TKG reasoning.

7 Limitations↩︎

We acknowledge several limitations of this study. First, RAPTOR is currently developed for RL-based multi-hop reasoning frameworks, and its applicability to other paradigms remains underexplored. Second, the reachable entity labeling stage introduces extra preprocessing cost, which may become non-trivial for larger-scale TKGs. Third, due to the limited availability of fully open-source RL-based multi-hop TKG baselines, we use a common and relatively simple backbone to ensure fair and reproducible comparisons. We identify two important and feasible directions for future work: improving the efficiency of the reachable labeling stage, and evaluating RAPTOR with stronger model backbones and more advanced RL training strategies.

8 Dataset Statistics↩︎

Our datasets are aligned with [24] and [9]; the dataset statistics are shown in Table ¿tbl:tab:dataset95statistics?.

max width=

9 Implementation Details↩︎

In our experiments, the entity and relation embedding dimensions are set to \(128\), with a temporal component of size \(d_t=48\) in the relation embedding. The step embedding dimension is \(d_{\text{step}}=32\), and the maximum path length is \(K=3\) for all datasets. Before self-supervised pretraining, we perform reachable-entity labeling with hop limit \(K\) and retain the top-\(N=200\) reachable entities.

We use RAPTOR to pretrain the agent for 40 epochs and then fine-tune with RL for 400 epochs. During RL, the initial entropy coefficient is \(\beta_0=0.01\) with exponential decay factor \(\zeta=0.9\), and the discount factor is \(\gamma=0.95\). We use a batch size of 512 in both phases and optimize with Adam at a learning rate of \(10^{-3}\). At each time step, we keep the top-150 candidate actions sorted by timestamp during both pretraining and RL.

For checkpoint selection, we evaluate every 20 epochs using beam search with beam size 100 and select the checkpoint with the best validation performance. All experiments use five random seeds, and we report the mean across seeds.

10 Actor-Critic Optimization Details↩︎

We train the policy (actor) and value (critic) networks using an actor-critic algorithm. The actor parameterizes a stochastic policy \(\pi_\theta(a \mid s)\), while the critic estimates the state value \(V_\phi(s)\). The value function serves as a baseline to estimate the expected return from \(s\) and reduces the variance of policy gradients.

For time step \(k \in \{0, \ldots, K-1\}\) in an episode, we compute the discounted return at time step \(k\) as \[g_k = \gamma^{(K-1)-k} R, \label{eq:return}\tag{2}\] where \(\gamma \in (0,1]\) is the discount factor. The advantage is defined by \[Adv_k = g_k - V_\phi(s). \label{eq:advantage}\tag{3}\]

We update the actor by maximizing the expected advantage: \[\mathcal{L}_{\mathrm{actor}}(\theta) = \mathbb{E}\left[\sum_{k=0}^{K-1} \log \pi_\theta(a_{k} \mid s)\, Adv_k \right]. \label{eq:actor}\tag{4}\] The critic is trained by minimizing the squared error between the predicted value and return: \[\mathcal{L}_{\mathrm{critic}}(\phi) = \mathbb{E}\left[\sum_{k=0}^{K-1} \left(V_\phi(s) - g_k\right)^2\right]. \label{eq:critic}\tag{5}\]

In addition, we incorporate an entropy regularization term to encourage exploration: \[\mathcal{L}_{\mathrm{entropy}}(\theta) = \mathbb{E}\left[\sum_{k=0}^{K-1} H\!\left(\pi_\theta(\cdot \mid s)\right)\right], \label{eq:entropy}\tag{6}\] where \(H(\cdot)\) denotes the entropy of the action distribution.

The overall objective is \[\max_{\theta}\mathcal{L}_{\mathrm{actor}}(\theta) + \beta_n\, \mathcal{L}_{\mathrm{entropy}}(\theta), \; \min_{\phi}\mathcal{L}_{\mathrm{critic}}(\phi), \label{eq:overall}\tag{7}\] where \(\beta_n\) is an entropy coefficient at training epoch \(n\). We apply an exponential decay schedule \(\beta_n = \beta_0 \zeta^{\,n}\) with decay factor \(\zeta \in (0,1)\). We optimize \(\theta\) and \(\phi\) jointly using stochastic gradient descent.

11 Disclosure of AI Use↩︎

The authors used GitHub Copilot as a coding assistant during implementation. ChatGPT and Gemini were used during manuscript preparation for writing support, including improving clarity, grammar, and phrasing. These tools were not used to generate the core scientific contributions, make research decisions, or determine the experimental results. All methods, experiments, analyses, and conclusions were developed, verified, and approved by the authors, who take full responsibility for the content of the paper.

References↩︎