Shortcut-Controlled Curricula for Entity-Free Hierarchical Graph Walkers

When a knowledge graph gains new entities, a model has to predict missing facts about things it never saw during training. Such a graph is a set of (head, relation, tail) facts, and this prediction task is called inductive knowledge graph completion. One appealing way to do it is to train an agent that walks the graph hop by hop until it reaches the answer. The walk itself then serves as the explanation. The agent can also be organized hierarchically: a high-level choice of "what kind of relation to follow next" and a low-level choice of the exact edge. Sparse rewards make such agents hard to train. The textbook remedy is a curriculum: start with answers one hop away, then two, then more. Recent benchmark work shows why this remedy may backfire. On standard inductive splits, answers are systematically closer in the graph than wrong candidates. Personalized PageRank, a training-free random-walk score, matches supervised models on those splits, and it falls to 45.1 Hits@10 on splits that remove this proximity leak (Towards Better Benchmark Datasets for Inductive Knowledge Graph Completion). A hop-length curriculum spends its early stages rewarding exactly this proximity shortcut.

This note proposes and tests a curriculum that controls for the shortcut. Queries are staged by the length of the relational rule that explains the answer, not by graph distance. Within every stage, the answer and the competing candidates are matched in shortest-path distance, so proximity never carries reward signal. The schedule advances using success statistics from the groups of walks that a critic-free policy-gradient update already samples. That makes the curriculum essentially free in compute. The central empirical question is sharp. Does a shortcut-controlled curriculum, unlike a hop-length one, produce walkers that hold up on leak-free partition splits? And is that benefit specific to RL walkers, or does it transfer to supervised message-passing models?

Core Claim

We claim two things. First, an easy-to-hard curriculum over hop length improves graph-walking agents on leaky inductive splits but does not help, and may hurt, on partition-based splits, because it trains reliance on distance. Second, a curriculum staged by rule length with distance-matched sampling closes much of that gap at no extra rollout cost.

The secondary engineering claim makes the walker possible in the inductive setting at all. The hierarchical walker can be built entirely without entity identities. Its high-level action clusters come from a relation-affinity graph recomputed on whatever graph it is deployed on, in place of transductive TransE clusters.

We deliberately do not claim that the walker beats strong supervised graph networks on accuracy. If it does not, the curriculum finding stands on its own, and we test it on those supervised networks too.

Positioning

The closest prior system is RLH (Reasoning Like Human: Hierarchical Reinforcement Learning for Knowledge Graph Reasoning). It uses a high-level history navigator plus a low-level policy that picks a relation cluster and then a relation, reaching 0.460 MRR on transductive FB15k-237. RLH motivates our hierarchy, and it constrains the design in two ways. Its clusters come from TransE and k-means over a fixed vocabulary, so it cannot run on unseen entities. It is also trained by plain REINFORCE on uniformly sampled queries, with no curriculum. We reuse its two-level action structure and replace both the clustering and the training schedule.

For inductive features we borrow from two papers. PathCon (Relational Message Passing for Knowledge Graph Completion) represents an entity only by the types of edges around it and the relation paths between the query nodes. We use this as the walker's state, so no entity ID is ever looked up. InGram (InGram: Inductive Knowledge Graph Embedding via Relation Graphs) builds a relation-affinity graph from entity overlap, which lets it handle unseen relations. We cluster that graph to obtain the high-level macro-actions, recomputing it at test time.

The curriculum ideas come from robotics and theory. CRISP (CRISP: Curriculum inducing Primitive Informed Subgoal Prediction for Hierarchical Reinforcement Learning) and DIPPER (Direct Preference Optimization for Primitive-Enabled Hierarchical RL: A Bilevel Approach) keep high-level goals within what the low-level policy can currently reach. Both rely on continuous states and on demonstrations or fixed preference data. We keep their core idea, that stages should track current low-level competence, but measure competence from the agent's own rollouts on discrete graphs.

The easy-to-hard self-improvement theory (A Task-centric Theory for Iterative Self-Improvement with Easy-to-Hard Curricula) gives conditions under which a curriculum should help: moderate separation in difficulty between stages, and a starting model that can already solve the first stage. It also shows regression when the start is infeasible. This tells us to gate stage advancement on measured success, not on a fixed schedule.

On cost, GRPO-style group-relative advantages remove the separate value network (ProRL: Prolonged Reinforcement Learning Expands Reasoning Boundaries in Large Language Models). We reuse that, and we reuse the same groups to drive the curriculum. This directly addresses the concern in the file that building a curriculum often costs as much as training, as with the tree search used in SAGE (Self-Guided Hierarchical Exploration for Generalist Foundation Model Web Agents).

Research Program

The walker. At each step the state is the PathCon-style relational context of the current node, the query relation, and a recurrent summary of the relations followed so far.

The high-level policy picks one of $K$ relation clusters from the deployed graph's affinity graph, or picks "stop". The low-level policy picks an outgoing edge whose relation lies in that cluster. This masks the action set much as NLPO masks unlikely tokens (Is Reinforcement Learning (Not) for Natural Language Processing: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization).

The reward is 1 if the walk stops at the true tail and 0 otherwise. At test time we run $G$ walks per query and rank candidates by how often walks stop on them, which yields MRR and Hits@k.

The update. For a query $q$ we sample $G$ walks with returns $R_1,\dots,R_G$. Each walk's advantage is $A_i = (R_i - \bar R_q)/(\sigma_q + \epsilon)$, where $\bar R_q$ and $\sigma_q$ are the group mean and standard deviation and $\epsilon$ is a small constant. Both levels are trained on these advantages, with no critic.

The group success rate $\bar R_q$ is the quantity the curriculum reads. It is already computed for the update, so the curriculum adds no rollouts.

The curriculum. Before training, we mine relation-path rules from the training graph and assign each training query a stage $s(q)$. The stage is the length of the shortest rule that has high support and entails the query's answer.

Within each stage, we sample queries so that the answer's shortest-path distance from the head matches the distribution of distances to the candidates the walker would otherwise stop on. Any reward obtainable by stopping "nearby" is then uncorrelated with correctness.

Stage $s$ opens when the running mean of $\bar R_q$ on stage $s-1$ passes a threshold. Starting from stage 1 is our operational test of the "feasible start" condition from the self-improvement theory.

The hop-length curriculum we compare against uses the same machinery. It replaces rule length with shortest-path distance to the answer and drops the matching.

Shortcut diagnostics. For every trained model we report the correlation between its candidate scores and Personalized PageRank scores on test queries. We also report how accuracy changes when the leaky split is swapped for the partition split. If a model scores well on leaky splits while closely tracking PageRank, we treat that as evidence it learned the shortcut rather than relational structure.

Baselines

The naive reference point is Personalized PageRank with no training. On the partition-based WN18RR (E) split it scores 45.1 Hits@10, down from 66.0 on the old split (Towards Better Benchmark Datasets for Inductive Knowledge Graph Completion). Any learned model that does not clearly exceed it on partition splits has learned nothing beyond proximity. We run it on all our splits with the restart probability tuned on validation.

The strongest existing method is NBFNet (Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction). It learns generalized path sums over the whole graph from the query's head in one pass. It reports a 22% relative Hits@10 gain over GraIL on inductive benchmarks and 4.0-minute evaluation on FB15k-237. The file gives no reported result for NBFNet on the partition-based splits. Chen et al. report only an average 40.6% drop for supervised models on WN18RR (E). We will therefore run NBFNet ourselves, using the TorchDrug implementation (TorchDrug), on identical splits with the same hyperparameter search budget as our walker.

PathCon is a second supervised baseline, because it uses exactly our state features. InGram is the baseline on the unseen-relation splits. Its reported NL-100 MRR is 0.309, against 0.220 for RMPI (InGram: Inductive Knowledge Graph Embedding via Relation Graphs).

Crucially, we also train NBFNet and PathCon with the same shortcut-controlled curriculum, implemented as staged reweighting of training queries. This separates "the curriculum helps" from "RL helps."

There are four ablations:

  • the same hierarchical walker with no curriculum;
  • the walker with the hop-length curriculum;
  • a flat walker that picks edges directly, with no cluster level;
  • the hierarchical walker trained with a learned critic in place of group-relative advantages.

The fourth isolates the cost claim through peak GPU memory and wall-clock time. On entity-inductive splits only, we add RLH-style TransE clusters fit on relations, to test whether our recomputed affinity clusters lose anything.

"Beating" has a specific meaning for each claim.

  • Curriculum claim: the shortcut-controlled walker beats the hop-length walker on partition-split MRR beyond seed variance, while correlating less with PageRank.
  • Transfer finding: the same holds for NBFNet with versus without the curriculum.
  • Walker claim: the walker matches NBFNet within a few MRR points while touching far fewer edges per query.

We will report the walker-versus-NBFNet gap whichever way it falls.

Why not just…?

Why not just use NBFNet and forget RL? This is the real threat to the walker, and we do not argue around it. NBFNet's single full-graph pass is fast and accurate, and a sampled walker may never match it on small graphs. We therefore structure the work so that the curriculum finding does not depend on the walker winning: the same curriculum is applied to NBFNet.

What the walker could offer is per-query cost that grows with the number of edges explored rather than with total graph size, plus a readable path. We measure both: edges touched per query, and how often the walker's paths match mined rules. If NBFNet with the curriculum dominates on accuracy and the edge savings are small on these graphs, we will report that the contribution is the curriculum, not the agent.

Why not just use a hop-length curriculum, the obvious easy-to-hard scheme? Because the proximity leak documented by Chen et al. means short hops are exactly where the answer is guessable by closeness. A hop-length curriculum is the direct test of our hypothesis, not a straw man. If it matches our curriculum on partition splits, the shortcut-matching component is unnecessary, and we will say so.

Why not just train a flat walker longer with critic-free RL? Prolonged flat RL does extend what models can do. But ProRL's 1.5B run took about 16,000 H100 hours (ProRL: Prolonged Reinforcement Learning Expands Reasoning Boundaries in Large Language Models). Separating high-level from low-level decisions gave roughly 100x better sample efficiency than flat PPO in multi-turn language tasks (ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL). Neither result is about graphs, so we test the question directly. The flat walker ablation gets the same curriculum and a compute budget matched by wall-clock time. We plot accuracy against training cost for both.

Why not just use a text bi-encoder such as SimKGC? SimKGC reaches 71.4 inductive MRR on Wikidata5M (SimKGC: Simple Contrastive Knowledge Graph Completion with Pre-trained Language Models). However, it depends on entity descriptions and answers a different question. The partition benchmarks and the NL splits are structural, and our claim concerns how training schedules interact with structural shortcuts. We include SimKGC only where text exists, as a reference point, not as a competitor for the curriculum claim.

Proposed Experiments

The main experiment trains each model on both versions of every entity-inductive benchmark: the old leaky inductive split and the partition-based split from Chen et al., including WN18RR (E). We use five seeds and equal tuning budgets. We report MRR, Hits@1 and Hits@10, and the correlation with PageRank scores.

The decisive check is the interaction between curriculum type and split type. Our hypothesis predicts that the hop-length curriculum helps on the leaky split and fails to help on the partition split. It also predicts that the shortcut-controlled curriculum helps on both. If both curricula behave the same way on partition splits, the core claim is false.

The second experiment runs the walker and InGram on NL-25 through NL-100. This tests whether clusters recomputed on the test graph's affinity graph let the hierarchy survive entirely unseen relations, which RLH's design cannot do.

The third experiment covers cost. On FB15k-237-derived and DDB14 graphs, we record GPU-hours to reach a fixed validation MRR, peak memory, and edges touched per test query. We compare the critic-free walker, the critic-based walker, and NBFNet. We also confirm that curriculum scheduling adds less than a few percent to wall-clock time, since it reads statistics the update already computes.

A final sanity check covers the "feasible start" condition. We deliberately start training at stage 3 and expect early group success rates to collapse, mirroring the regression the self-improvement theory reports when the starting model cannot solve the first tasks it is given.