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

Reinforcement learning (RL)-based multi-hop reasoning is a popular approach for temporal knowledge graph (TKG) reasoning because it provides interpretable paths. However, these models often struggle with sparse rewards and a vast, time-evolving action space, leading to inefficient training and suboptimal performance. This paper asks whether pretraining an agent with a reachability-aware inductive bias can improve exploration efficiency and downstream reasoning performance.

The authors propose RAPTOR (Reachability-Aware Pretraining for Efficient Target-Oriented Path Exploration). The method consists of two main components:

1. Reachable Entity Labeling: The authors use a backward breadth-first search (BFS) starting from the target entity to identify all entities that can reach the target within a specified hop budget, while strictly adhering to the temporal constraints of the TKG (i.e., non-decreasing timestamps).
2. Self-Supervised Pretraining: The agent is pretrained to predict whether a candidate action is 'reachable' or 'unreachable' based on the labels generated in the first step. This binary classification task acts as an inductive bias, encouraging the agent to focus its exploration on promising paths during the subsequent RL fine-tuning phase.

Experimental results on the ICEWS14, ICEWS05-15, and ICEWS18 datasets show that RAPTOR significantly improves both the convergence speed and the final accuracy of RL-based multi-hop reasoners. By effectively pruning the search space, the pretrained agent avoids unpromising trajectories, leading to more stable and efficient training compared to standard RL baselines that start from scratch.

This work addresses a fundamental bottleneck in RL-based graph reasoning: the inefficiency of exploring massive, dynamic search spaces. By decoupling the task of learning 'what is reachable' from the task of 'finding the optimal path,' RAPTOR provides a practical way to enhance the performance of interpretable reasoning models without requiring complex reward shaping or manual heuristic design.