Balancing Distance Regimes, Not Graphs, in Knowledge Graph Foundation Models

Knowledge graph foundation models are graph neural networks that predict missing links in any knowledge graph, including graphs whose entities and relation types they never saw in training. They can work zero-shot because they learn how relations interact structurally rather than what particular relations mean. The leading example, ULTRA, is pre-trained jointly on three graphs and transfers to dozens more. Its authors also found that adding more pre-training graphs stopped helping. The natural reading is that this is negative transfer, the multi-task learning failure in which training signals from different sources pull shared weights in conflicting directions. That reading suggests importing gradient-conflict methods and treating each source graph as a task.

We think the conflict that matters runs along a different axis. A separate benchmark study showed that a large share of inductive link-prediction queries can be solved by graph distance alone. A relation-blind random-walk score, Personalized PageRank, does well because performance tracks the shortest-path gap between true and false answers. Our hypothesis is that each new pre-training graph mostly adds more of these easy short-range queries. Their gradients then crowd out the smaller signal from queries that need multi-hop relational reasoning. If so, the "tasks" in the multi-task sense should be distance regimes inside every graph rather than graphs. Balancing those regimes should lift the ceiling on benchmarks where the distance shortcut has been removed, and balancing graphs should not.

Core Claim

The claim has three parts. First, in multi-graph relational pre-training, gradient conflict and magnitude imbalance are larger between shortest-path-distance strata of training queries than between source graphs. Second, the share of gradient magnitude held by short-range queries grows as the pre-training mixture grows. Third, a cheap regime-level balancing scheme beats both naive pooling and graph-level conflict resolution on shortcut-free zero-shot evaluation. It does this without the information loss that comes from simply discarding easy queries.

The scheme works as follows. Each training query is stratified by the shortest-path distance between its head entity and its true tail. Mini-batches are drawn stratum by stratum, and each stratum's loss is rescaled so that its gradient norm on the shared encoder is equalized. Both claims are falsifiable from training logs and evaluation numbers alone. A null result would also be informative: it would suggest the ULTRA ceiling is a capacity limit or a data-diversity limit rather than an optimization problem.

Positioning Against Prior Work

The proposal starts from ULTRA's design. Towards Foundation Models for Knowledge Graph Reasoning builds a graph whose nodes are relations, linked by four ways of sharing entities. It runs a query-conditioned GNN over that relation graph and feeds the result into an NBFNet link predictor. It pools WN18RR, FB15k-237 and CoDEx-Medium with plain joint training and reports the plateau as more graphs are added. We keep the architecture unchanged and change only how its multi-source loss is organized.

InGram and HYPER extend the same relation-graph idea, to affinity-weighted relation graphs and to n-ary hyperedges respectively. Both use a single link-prediction loss. We treat HYPER only as a later extension.

The motivating constraint comes from Towards Better Benchmark Datasets for Inductive Knowledge Graph Completion. That study finds a 0.87 correlation between the shortest-path gap and PPR performance on standard benchmarks. It proposes partition-based splits on which supervised inductive models drop 40.6% on average and PPR Hits@10 falls from 66.0 to 45.1 on WN18RR. That paper evaluates supervised models. Whether zero-shot foundation models also lean on the shortcut is the open question our evaluation inherits.

The optimization tools come from multi-task learning. RotoGrad separates negative transfer into magnitude imbalance and direction conflict. It fixes the first by reweighting and the second by learned per-task rotations of the shared representation. PARETOGNN shows that a weighted sum of graph self-supervised losses can underperform single-task specialists. It resolves this with the Multiple Gradient Descent Algorithm (MGDA), which finds a common descent direction among task gradients, at a per-step quadratic-program cost. Both papers assume the task partition is given. Our contribution is to argue, and test, that for relational pre-training the useful partition is a latent structural regime rather than the data source.

FedGFM+ and BRIDGE handle multi-domain interference in graph foundation models through codebook anchoring and mixture-of-experts prompting. They do this on node, edge and graph classification, not inductive relational link prediction. They show that domain-level interference is real, but they balance domains, which is the graph-level alternative we compare against.

Research Program

The work has three stages. Each produces a usable result even if the next one fails.

The first stage is a diagnostic. We train ULTRA on nested mixtures that start with ULTRA's three graphs and add further transductive graphs from its evaluation pool one at a time. Graphs used for pre-training are removed from the zero-shot evaluation set. Throughout training we log per-group gradients on the shared relation encoder and entity predictor under two groupings. One grouping is by source graph. The other is by distance stratum, with buckets for distance 1, 2, 3, and 4 or more; unreachable cases, where the head cannot reach the tail, form their own bucket.

For each grouping we record two quantities: the average pairwise gradient cosine, and the share of total gradient norm held by each group. The prediction is that strata show more negative cosines than graphs, and that the short-range share rises with mixture size while the reasoning-stratum share falls.

The second stage is the method. With strata as tasks, we compare three increasingly heavy treatments. The lightest is stratified sampling with gradient-norm equalization, which corresponds to RotoGrad's magnitude half. The middle option adds conflict projection between strata. The heaviest is an MGDA descent direction over strata. If the lightest treatment captures most of the gain, the practical message is simple and cheap. A model of about 177k parameters makes all three affordable.

The third stage is evaluation designed to separate genuine relational transfer from distance-heuristic transfer. We use the partition-based WN18RR and FB15k-237 splits from the benchmark study alongside ULTRA's original 54-graph suite and the twelve InGram datasets with 25–100% unseen relations. Test queries are also stratified by distance, so improvements can be traced to the regime where they occur.

Baselines

The naive reference point is PPR scored on the same test queries. It has no parameters and no relation information, so any learned model that fails to beat it on partition-based splits has learned only distance. The reported value is Hits@10 of 45.1 on partition-based WN18RR, from the benchmark study. We will also report PPR's MRR and its per-stratum Hits@10 ourselves.

The strongest existing method is ULTRA with standard pooled pre-training, retrained by us on each nested mixture. This is necessary because the mixtures differ from the published checkpoint. Its reported result is an average zero-shot MRR of 0.395 across 54 unseen graphs, against 0.344 for supervised per-graph baselines, as reported in Towards Foundation Models for Knowledge Graph Reasoning. On the fully unseen-relation NL-100 split, the reference is InGram's reported MRR of 0.309. We found no reported result on Lacuna for ULTRA on the partition-based inductive benchmarks, so we will produce that number ourselves. Beating ULTRA means a higher MRR on partition-based splits and on the hard strata (distance 3 or more, plus unreachable). The improvement must exceed seed variance across five seeds, while staying within one standard deviation of pooled ULTRA on the original 54-graph average. A method that helps only on shortcut-prone benchmarks does not count.

The ablation that isolates the key ingredient is graph-level balancing. It uses exactly the same three balancing treatments, but with source graphs as tasks, in the style of PARETOGNN and RotoGrad. If graph-level balancing matches regime-level balancing, our central claim is wrong.

All methods share the architecture, the pre-training graphs, the number of gradient steps, and an identical hyperparameter search budget of twelve configurations each, selected on a held-out validation graph that is excluded from testing.

Why not just…?

Why not just make ULTRA bigger? The original authors attribute the plateau to architectural capacity, so this is a genuine competing explanation. We run pooled ULTRA at roughly two and four times the parameter count, and compare against our method at the base size. If the wider model lifts the ceiling on partition-based splits as much as regime balancing does, the optimization story is unnecessary and we will say so. The diagnostic gives an independent check. If capacity is the bottleneck, gradient conflicts between strata should shrink as the model widens. If optimization is the bottleneck, they should persist.

Why not just apply PCGrad or MGDA with each graph as a task? This is the obvious import from multi-task learning, and it is our main ablation rather than a straw man. PARETOGNN shows that resolving conflict among pretext tasks helps on single graphs. The question here is whether source graphs are the right grouping at all. Each graph contains every distance regime, so balancing graphs may leave the within-graph imbalance between regimes untouched. The paired comparison in stage two settles this directly.

Why not just drop or downweight short-range training queries? This is the most serious threat, because it is simpler than anything in stage two. Short-range queries still teach local relation composition, which multi-hop reasoning builds on. Removing them may hurt both the easy strata and the composition skills the hard queries depend on. We include two curation baselines. One deletes all queries at distance 1. The other uses static inverse-frequency stratum weights. If static reweighting matches adaptive norm equalization, the honest conclusion is that the contribution is the diagnosis plus a data-sampling recipe, and we will report it that way.

Why not just rely on PPR or other heuristics? On partition-based splits PPR's Hits@10 falls to 45.1, and it cannot tell relation types apart. Its role here is a floor, not a competitor.

Decisive Checks

The proposal stands or falls on three observations. The first is whether gradient cosines between distance strata are more negative than those between graphs. The second is whether the short-range share of gradient norm grows with mixture size, tracking ULTRA's plateau. The third is whether regime-balanced pre-training converts additional graphs into gains on partition-based, hard-stratum queries where pooled, widened, graph-balanced and curated variants do not.

A positive result would show that the ULTRA scaling ceiling is mainly an optimization artifact of the distance shortcut. A negative result on the first two checks would rule out the optimization explanation and redirect effort toward capacity and data diversity.