Skip to content

Reachability-Aware Pretraining for Efficient Target-Oriented Path Exploration in Temporal Knowledge Graph Reasoning

🕒 Published (v1): 2026-07-16 11:59 UTC · Source: Arxiv · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

RAPTOR is a self-supervised pretraining method for RL-based multi-hop reasoning on Temporal Knowledge Graphs (TKGs) that injects a reachability-aware inductive bias before RL fine-tuning. By running backward BFS from target entities to label which candidate actions can reach the target within a hop budget under temporal constraints, RAPTOR reduces wasted exploration over infeasible paths. It consistently improves training efficiency and final accuracy over pure-RL baselines on three ICEWS benchmarks.

Problem

RL-based multi-hop TKG reasoning agents face exponentially large, time-dependent action spaces: valid edges must respect non-decreasing timestamp constraints, so most sampled trajectories terminate without reward. This leads to sparse terminal rewards, slow convergence, and unstable training — problems not addressed by existing approaches that apply auxiliary signals (reward shaping, demonstration imitation) during RL itself, potentially interfering with other training objectives.

Method

RAPTOR pretrains the policy network before RL via a self-supervised reachability prediction task. A backward BFS (Algorithm 1) runs from each target entity \(o_q\) at query time \(t_q\), traversing incoming edges in reverse while enforcing \(t' \leq t_{\text{cur}}\) and pruning by keeping only the top-\(N\) most recent incoming edges. This produces a list \(L\) of tuples \((e', \bar{t}, \bar{h})\) — entity, latest timestamp, hop distance — indicating which entities can reach \(o_q\) within \(K\) hops.

At each pretraining step \(k\), each candidate action \(a = (e', r', t')\) receives a binary label \(y(a) = 1\) if \(L\) contains \((e', \bar{t}, \bar{h})\) with \(t' \leq \bar{t}\) and \(K - k > \bar{h}\). The policy's sigmoid-transformed logit \(\hat{y}(a) = \sigma(z(a))\) is trained with binary cross-entropy:

\[\mathcal{L}_{\text{SL}}(\theta) = -\frac{1}{|A_s|} \sum_{a \in A_s} \left[ y(a) \log \hat{y}(a) + (1 - y(a)) \log(1 - \hat{y}(a)) \right]\]

Transitions during pretraining sample from the reachable-action distribution. After pretraining converges, the agent is fine-tuned with actor-critic RL using sparse terminal rewards (\(R = 1\) iff episode ends at \(o_q\)).

The policy network uses a static entity embedding, a time-conditioned relation embedding \(\mathbf{r}(r, \Delta t) = [\text{EmbR}(r); \cos(\mathbf{w}\Delta t + \mathbf{b})]\), and an LSTM path encoder. Action scoring is by dot-product similarity between a two-layer MLP state vector and action embeddings.

Key Contributions

  • First self-supervised pretraining method tailored to RL-based multi-hop TKG reasoning (extrapolation setting).
  • Backward BFS reachable-entity labeling algorithm that respects temporal constraints (non-decreasing timestamps, hop budget \(K\)) with a top-\(N\) pruning to control compute.
  • Binary cross-entropy pretraining objective that steers the policy toward reachable actions before RL, reducing wasted trajectory rollouts.
  • Demonstrated that more pretraining epochs yield faster reward growth and higher early-stage MRR in the subsequent RL phase.

Results

All numbers use time-aware filtered MRR / Hits@{1,3,10}; RL-RAPTOR vs. Pure-RL improvements are statistically significant (\(p < 0.05\)) where marked.

  • ICEWS14: RL-RAPTOR MRR 42.86 vs. Pure-RL 42.41; Hits@1 34.37 vs. 33.78; Hits@3 47.93 vs. 47.58.
  • ICEWS05-15: RL-RAPTOR MRR 48.04 vs. Pure-RL 47.74; Hits@1 38.51 vs. 38.24; Hits@3 53.90 vs. 53.50; Hits@10 66.79 vs. 66.54.
  • ICEWS18: RL-RAPTOR MRR 30.25 vs. Pure-RL 29.87; Hits@1 21.92 vs. 21.64; Hits@3 34.3 vs. 33.79; Hits@10 47.45 vs. 46.85.
  • RL-RAPTOR ranks best or second-best among all baselines on most metrics across all three datasets; second on ICEWS18 behind RE-GCN on MRR.
  • Training efficiency: with 10 RAPTOR pretraining epochs, average RL reward exceeds 0.325 after 60 total epochs; Pure-RL requires >100 epochs to reach the same level.
  • RL-RAPTOR reaches early-stage MRR that exceeds the final performance of TITer and TITer-150 on multiple datasets.

Limitations

  • Reachable entity labeling is run offline for every \((o_q, t_q)\) pair in the training set; scalability to very large TKGs is acknowledged but not benchmarked.
  • Evaluated only with a relatively simple LSTM+MLP backbone to ensure fair comparison; stronger architectures not tested.
  • Top-\(N\) incoming-edge pruning is a heuristic that may miss some reachable entities, producing noisy labels.
  • Hop budget \(K\) is fixed; the reachability label depends on \(K\), coupling pretraining tightly to the RL configuration.
  • Only extrapolation setting evaluated; does not address interpolation or static KGs.

Relevance to Agentic AI / LLM Agents

This paper addresses a core challenge in sequential-decision agents operating over large, structured environments: exploration under sparse reward with a dynamic, constraint-laden action space. The reachability-pretraining paradigm — using backward graph search to label feasible actions before any reward signal is available — is directly analogous to curriculum or hindsight techniques proposed for general RL agents, and the same idea of pruning the agent's action space based on goal-reachability applies to tool-use and planning agents in LLM systems. The work also connects to prompt-free, self-supervised initialization strategies for LLM-based agents, where bootstrapping from structural signals (e.g., graph topology) reduces reliance on dense hand-crafted reward shaping. Researchers tracking agentic reasoning over knowledge structures (retrieval-augmented agents, graph-navigating agents, multi-hop QA pipelines) will find RAPTOR's backward-BFS labeling directly applicable to constraining the search space of any agent that traverses time-stamped relational data.