MERIT: Scaling KG Foundation Models with Relation Transformers

Cosimo Gregucci; Daniel Hernandez; Antonio Vergari; Steffen Staab

cs.LGOct 11, 2026

MERIT: Scaling KG Foundation Models with Relation Transformers

Authors: Cosimo Gregucci, Daniel Hernandez, Antonio Vergari, Steffen Staab

Organizations: Institute for Artificial Intelligence, University of Stuttgart, Germany · School of Informatics, University of Edinburgh, UK · University of Southampton

Abstract

Knowledge graph (KG) foundation models (KGFMs) predict links on unseen graphs zero-shot. KGFMs have been pioneered by ULTRA which builds a relation graph from co-occurrences that match motif templates, and passes messages over it to obtain relation representations. More recent KGFMs such as MOTIF and TRIX increase the size of this relation graph, and FLOCK replaces message-passing with probabilistic random-walk ensembles. However, larger relation graphs mean more messages, and more walks mean more sequences to encode, so they improve performance at higher training and inference cost. This cost hinders their use in more complex reasoning tasks, such as complex query answering. To reverse this trend, we design MERIT, the first KGFM with a transformer relation encoder: every relation name attends to every other, and the motifs enter as a soft prior rather than as edges. Over 56 benchmarks, MERIT matches the zero-shot MRR of SoTA KGFMs while being 6x faster than TRIX and over 100x faster than FLOCK at inference. Fine-tuned for complex query answering like UltraQuery, MERITQuery improves over it at matched cost.

Figures & tables

Figure 1: MERIT matches SoTA KGFMs in MRR, with inference and pre-training times performance comparable to those of ULTRA , while TRIX and FLOCK need

6\times

and over

100\times

more inference time and

7\times

and

6\times

more training time, respectively. Each point is the mean MRR (higher is better) over

56

benchmarks, averaged over pre-training runs, five for MERIT, ULTRA and TRIX and three for MOTIF and FLOCK; bars are the sample standard deviation over runs. Panel (a) is inference wall-clock over the whole suite and panel (b) pre-training time per batch, both measured on an H100 GPU and shown on a log scale.

Figure 2: Example inference graph

\mathcal{G}_{\text{{inf}}}

(left) and its ULTRA-derived relation graph

\mathcal{G}^{r}_{\text{{inf}}}

(right). For visual simplification, we omit (i) h2t edges, since they are the reverse of t2h , and (ii) trivial h2h and t2t self-loops.

Figure 3: In MERIT, the query-conditioned relation representations are obtained with the relation transformer. The rest of the pipeline is as in ULTRA ( Section 2 ).

Figure 4: MERIT runs a transformer over all relation tokens and injects the motifs in the token embeddings and as a bias on the attention. The motif tensor

M

b) has the shape of the adjacency tensor of the relation graph

\mathcal{G}^{r}_{\text{{inf}}}

a), with entity occurrence counts in place of edges. This tensor is then used as a prior for the MERIT architecture c), where every token contains the relation signature

\mathrm{s}_{r}

of its relation, followed by random noise

\bm{\varepsilon}

, or by ones for the query relation

p

(

r_{2}

in the example); every arrow is an attention logit

a_{ij}

, and the arrows between co-occurring relations add the bias

f(M_{ij})

, over multiple heads.

Figure 5: MERIT keeps the inference cost of ULTRA at every graph size , while the cost gap to TRIX widens with the number of triples and the gap to MOTIF with the number of relation names; FLOCK stays two to three orders of magnitude above. Markers are medians of the inference wall-clock within log-spaced bins of inference-graph size. Further analysis in Figure B.1 , bin details in Table B.1 . We omit the incomplete bins of MOTIF from the plot.

Model	Family 1		Family 2		Family 3		Total
	(13 graphs)		(18 graphs)		(23 graphs)		(54 graphs)
	MRR	Hits@10	MRR	Hits@10	MRR	Hits@10	MRR	Hits@10
ULTRA	$0.310{\scriptstyle\pm.005}$	$0.453{\scriptstyle\pm.007}$	$0.434{\scriptstyle\pm.003}$	$0.571{\scriptstyle\pm.003}$	$0.342{\scriptstyle\pm.006}$	$0.519{\scriptstyle\pm.004}$	$0.365{\scriptstyle\pm.003}$	$0.521{\scriptstyle\pm.003}$
MOTIF	$0.306{\scriptstyle\pm.005}$	$0.445{\scriptstyle\pm.007}$	$0.431{\scriptstyle\pm.008}$	$0.575{\scriptstyle\pm.008}$	$0.346{\scriptstyle\pm.004}$	$0.522{\scriptstyle\pm.006}$	$0.365{\scriptstyle\pm.002}$	$0.521{\scriptstyle\pm.001}$
TRIX	$\mathbf{0.329}{\scriptstyle\pm.004}$	$\mathbf{0.484}{\scriptstyle\pm.005}$	$\mathbf{0.451}{\scriptstyle\pm.003}$	$0.589{\scriptstyle\pm.004}$	$\mathbf{0.362}{\scriptstyle\pm.004}$	$0.536{\scriptstyle\pm.004}$	$\mathbf{0.384}{\scriptstyle\pm.002}$	$0.541{\scriptstyle\pm.003}$
FLOCK	$\mathbf{0.331}{\scriptstyle\pm.009}$	$\mathbf{0.493}{\scriptstyle\pm.011}$	$\mathbf{0.448}{\scriptstyle\pm.011}$	$\mathbf{0.602}{\scriptstyle\pm.003}$	$\mathbf{0.364}{\scriptstyle\pm.007}$	$\mathbf{0.548}{\scriptstyle\pm.010}$	$\mathbf{0.384}{\scriptstyle\pm.006}$	$\mathbf{0.552}{\scriptstyle\pm.005}$

Table 1: Zero-shot MERIT matches SoTA KGFMs in every family of benchmarks . Mean MRR and Hits@10 over the benchmarks of each family and over all

54

, averaged over five pre-training runs per model, three for MOTIF and FLOCK, with a single run of MOTIF on AristoV4;

\pm

is the sample standard deviation over runs. Bold marks the best mean of each column and every mean within one standard deviation of it, its own or that of the best.

Model	SQSA	UQSA	SQUA	UQUA
ULTRA	$0.393{\scriptstyle\pm.004}$	$0.546{\scriptstyle\pm.006}$	$0.144{\scriptstyle\pm.006}$	$0.258{\scriptstyle\pm.013}$
MOTIF	$0.382{\scriptstyle\pm.003}$	$0.545{\scriptstyle\pm.006}$	$0.160{\scriptstyle\pm.006}$	$0.255{\scriptstyle\pm.015}$
TRIX	$0.392{\scriptstyle\pm.002}$	$\mathbf{0.564}{\scriptstyle\pm.004}$	$\mathbf{0.183}{\scriptstyle\pm.004}$	$0.260{\scriptstyle\pm.014}$
FLOCK	$\mathbf{0.389}{\scriptstyle\pm.010}$	$\mathbf{0.565}{\scriptstyle\pm.008}$	$\mathbf{0.181}{\scriptstyle\pm.005}$	$\mathbf{0.276}{\scriptstyle\pm.016}$
MERIT (ours)	$\mathbf{0.398}{\scriptstyle\pm.004}$	$\mathbf{0.568}{\scriptstyle\pm.008}$	$0.175{\scriptstyle\pm.005}$	$\mathbf{0.282}{\scriptstyle\pm.010}$

Table 2: The gain of zero-shot MERIT reaches UQUA , and is on par with FLOCK and ahead of the other KGFMs. Mean MRR per half-link scenario over the

50

zero-shot benchmarks; averages and bold as in Table 1 .

Figure 6: Fine-tuning raises the MRR of MERIT on every scenario, UQUA included . Zero-shot (zs) and fine-tuned (ft) mean MRR over the

22

Family 3 benchmarks, one panel per half-link scenario with its own scale.

	All		Conjunctive		Union		Negation
Family	UltraQuery	MERITQuery	UltraQuery	MERITQuery	UltraQuery	MERITQuery	UltraQuery	MERITQuery
Family 1 ( $2$ )	$0.062{\scriptstyle\pm.012}$	$\mathbf{0.077{\scriptstyle\pm.005}}$	$0.080{\scriptstyle\pm.021}$	$\mathbf{0.103{\scriptstyle\pm.006}}$	$0.090{\scriptstyle\pm.007}$	$\mathbf{0.108{\scriptstyle\pm.011}}$	$\mathbf{0.022{\scriptstyle\pm.003}}$	$\mathbf{0.023{\scriptstyle\pm.003}}$
Family 2 ( $9$ )	$\mathbf{0.274{\scriptstyle\pm.003}}$	$\mathbf{0.276{\scriptstyle\pm.004}}$	$\mathbf{0.231{\scriptstyle\pm.003}}$	$0.227{\scriptstyle\pm.003}$	$\mathbf{0.341{\scriptstyle\pm.012}}$	$\mathbf{0.350{\scriptstyle\pm.011}}$	$0.316{\scriptstyle\pm.003}$	$\mathbf{0.326{\scriptstyle\pm.004}}$
Family 3 ( $7$ )	$0.346{\scriptstyle\pm.003}$	$\mathbf{0.368{\scriptstyle\pm.013}}$	$0.357{\scriptstyle\pm.004}$	$\mathbf{0.367{\scriptstyle\pm.009}}$	$0.324{\scriptstyle\pm.007}$	$\mathbf{0.367{\scriptstyle\pm.019}}$	$0.337{\scriptstyle\pm.006}$	$\mathbf{0.370{\scriptstyle\pm.018}}$
All ( $18$ )	$0.278{\scriptstyle\pm.003}$	$\mathbf{0.290{\scriptstyle\pm.006}}$	$0.263{\scriptstyle\pm.004}$	$\mathbf{0.268{\scriptstyle\pm.004}}$	$0.306{\scriptstyle\pm.008}$	$\mathbf{0.330{\scriptstyle\pm.008}}$	$0.291{\scriptstyle\pm.003}$	$\mathbf{0.310{\scriptstyle\pm.009}}$

Table 3: MERITQuery is ahead of UltraQuery over the

18

benchmarks and on Family 1 and Family 3, most on the union and negation types . Mean MRR over the benchmarks of each family and over all

18

, per group of query types, averaged over five fine-tuning runs per method;

\pm

and bold, within each pair, as in Table 1 .

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

axis	bin	$n$	median	benchmarks
relation names	$7$ to $20$	13	11	Wiki MT1 health, WN v1, WN v4, Wiki MT1 tax, WN v2, HM 1k, HM 3k, HM 5k, WN18RR, WN v3, Wiki MT2 org, NELL v1, Wiki MT2 sci
	$20$ to $60$	13	37	Wiki MT4 health, Hetionet, Wiki MT3 infra, Metafam, ConceptNet100k, WK-100, YAGO310, CoDEx Small, Wiki MT4 sci, Wiki MT3 art, ILPC Small, CoDEx Medium, NL-100
	$60$ to $200$	17	112	ILPC Large, WK-75, CoDEx Large, WK-25, NELL v4, FB-100, NELL v2, WK-50, NL-0, NL-75, NL-50, NL-25, WDsinger, NELL v3, FB v1, FBNELL, FB-75
	$200$ to $400$	12	217	FB v2, NELL23k, NELL995, FB-50, FB v3, FB-25, FB v4, IndigoBM, FB15k237, FB15k237_10, FB15k237_20, FB15k237_50
	$400$ to $2k$	2	1.04k	DBpedia100k, AristoV4 ∗
entities	$200$ to $2k$	7	1.09k	NELL v1, Metafam, WN v1, FB v1, NL-75, FB v2, NL-100

Appendix

Table B.1: Details of the bins behind Figures 5 and B.1 . Rows list the benchmarks in each log-spaced bin of relation names, entities and triples of the inference graph, with the bin count

n

and the median size. ∗ no MOTIF run.

Figure B.1: MERIT tracks ULTRA in wall-clock, GPU memory and CPU memory on every size axis , and deviates from it only in dense FLOPs, by the largest factor on the graphs with the most relation names. Rows show inference wall-clock and FLOPs of dense tensor operators as counted by PyTorch, both per batch of

1{,}000

test triples, and peak GPU and CPU memory; columns bin the benchmarks by relation names, entities and triples of the inference graph ( Table B.1 ) and markers are medians per bin. MOTIF markers are omitted from the bins that contain AristoV4, which has no MOTIF run, so that every marker in a bin is a median over the same benchmarks.

Figure B.2: The relation stage carries most of the resource consumption of TRIX and MOTIF but a small share for MERIT and ULTRA , whose cost sits in the shared entity GNN. Bars cover the

56

benchmarks of Figure 1 for the four stages of GNN-based KGFMs: precomputation of the relational structure, relation encoder, entity encoder and score computation. Panels show (a) the largest peak GPU memory of each stage on any benchmark, (b) the share of the wall-clock summed over the suite and (c) the share of the FLOPs summed over the suite, both with the sum printed at the end of each bar; labels give the share of the larger segments. Note that TRIX ties its relation computation to a small entity GNN, hence its relation-stage peak closely matches that of the entity stage.

Figure B.3: The resources of MERIT stay almost constant as the number of motif templates grows . As indicated in Section 4 , peak GPU memory increases slightly with

T

on the bins with the most relation names. Median resources of MERIT over the benchmarks in each relation-name bin of Table B.1 , at

T=4

and with the four slices of

M

duplicated to

T=8

and

T=16

. Each line corresponds to a different bin.

Figure B.4: MERIT answers more 4p queries in one hour than TRIX, MOTIF or FLOCK answer 1p queries, and as many queries as ULTRA at every hop .

Model	54 benchmarks		57 benchmarks
	MRR	Hits@10	MRR	Hits@10
ULTRA	$0.365{\scriptstyle\pm.003}$	$0.521{\scriptstyle\pm.003}$	$0.368{\scriptstyle\pm.002}$	$0.523{\scriptstyle\pm.004}$
MOTIF	$0.365{\scriptstyle\pm.002}$	$0.521{\scriptstyle\pm.001}$	$0.368{\scriptstyle\pm.001}$	$0.524{\scriptstyle\pm.001}$
TRIX	$\mathbf{0.384}{\scriptstyle\pm.002}$	$0.541{\scriptstyle\pm.003}$	$0.386{\scriptstyle\pm.002}$	$0.542{\scriptstyle\pm.003}$
FLOCK	$\mathbf{0.384}{\scriptstyle\pm.006}$	$\mathbf{0.552}{\scriptstyle\pm.005}$	$0.382{\scriptstyle\pm.005}$	$\mathbf{0.548}{\scriptstyle\pm.005}$
MERIT (ours)	$\mathbf{0.386}{\scriptstyle\pm.002}$	$\mathbf{0.549}{\scriptstyle\pm.001}$	$\mathbf{0.388}{\scriptstyle\pm.002}$	$\mathbf{0.551}{\scriptstyle\pm.001}$

Appendix

Table C.1: Zero-shot MRR and Hits@10 of MERIT and the SoTA KGFMs on the

54

benchmarks and on all

57

. Mean over the benchmarks of each column, averaged over five pre-training runs per model, three for MOTIF and FLOCK;

\pm

is the sample standard deviation over runs. The single run of MOTIF on AristoV4 enters every run of MOTIF. Bold as in Table 1 .

Model	inference time (h)	MRR
ULTRA	$0.60$	$0.365{\scriptstyle\pm.003}$
MOTIF	$3.69$ ∗	$0.365{\scriptstyle\pm.002}$
TRIX	$3.31$	$0.384{\scriptstyle\pm.002}$
FLOCK	$67.07$	$0.384{\scriptstyle\pm.006}$
MERIT (ours)	$0.58$	$0.386{\scriptstyle\pm.002}$

Appendix

Table C.2: The conclusions of Figure 1 are unchanged on the

54

benchmarks in the inductive transfer setting . Inference time over the

54

benchmarks in hours and MRR averaged over five pre-training runs per model, three for MOTIF and FLOCK;

\pm

is the sample standard deviation over runs. The single run of MOTIF on AristoV4 enters every run of MOTIF, and ∗ marks its time over the

53

benchmarks other than AristoV4.

Family 1 (16)
Benchmark	ULTRA	MOTIF	TRIX	FLOCK	MERIT
CoDEx Small	$0.467{\scriptstyle\pm.011}$	$0.476{\scriptstyle\pm.005}$	$0.478{\scriptstyle\pm.006}$	$0.446{\scriptstyle\pm.006}$	$\mathbf{0.479}{\scriptstyle\pm.007}$
CoDEx Medium	$0.368{\scriptstyle\pm.008}$	$0.369{\scriptstyle\pm.005}$	$0.364{\scriptstyle\pm.003}$	$0.267{\scriptstyle\pm.007}$	$\mathbf{0.374}{\scriptstyle\pm.002}$
CoDEx Large	$0.331{\scriptstyle\pm.004}$	$0.342{\scriptstyle\pm.004}$	$0.338{\scriptstyle\pm.002}$	$0.341{\scriptstyle\pm.002}$	$\mathbf{0.346}{\scriptstyle\pm.002}$
WDsinger	$0.385{\scriptstyle\pm.017}$	$0.395{\scriptstyle\pm.003}$	$0.389{\scriptstyle\pm.012}$	$\mathbf{0.403}{\scriptstyle\pm.010}$	$\mathbf{0.403}{\scriptstyle\pm.012}$
FB15k237_10	$0.237{\scriptstyle\pm.011}$	$0.241{\scriptstyle\pm.005}$	$0.239{\scriptstyle\pm.008}$	$0.216{\scriptstyle\pm.047}$	$\mathbf{0.248}{\scriptstyle\pm.002}$

Appendix

Table C.3: Zero-shot MRR of MERIT and the SoTA KGFMs on each of the

57

benchmarks . Mean MRR over five pre-training runs per model, three for MOTIF and FLOCK;

\pm

is the sample standard deviation over runs; ∗ marks the single run of MOTIF on AristoV4, which enters every run of MOTIF in the last row, the average over all

57

benchmarks. Bold marks the best mean of each row.

Family 1 (16)
Benchmark	ULTRA	MOTIF	TRIX	FLOCK	MERIT
CoDEx Small	$0.664{\scriptstyle\pm.007}$	$\mathbf{0.673}{\scriptstyle\pm.004}$	$\mathbf{0.673}{\scriptstyle\pm.003}$	$0.642{\scriptstyle\pm.004}$	$0.671{\scriptstyle\pm.004}$
CoDEx Medium	$0.520{\scriptstyle\pm.016}$	$0.519{\scriptstyle\pm.005}$	$0.521{\scriptstyle\pm.002}$	$0.399{\scriptstyle\pm.009}$	$\mathbf{0.531}{\scriptstyle\pm.003}$
CoDEx Large	$0.461{\scriptstyle\pm.008}$	$0.471{\scriptstyle\pm.006}$	$0.472{\scriptstyle\pm.002}$	$0.465{\scriptstyle\pm.003}$	$\mathbf{0.479}{\scriptstyle\pm.003}$
WDsinger	$0.496{\scriptstyle\pm.015}$	$0.512{\scriptstyle\pm.003}$	$0.499{\scriptstyle\pm.014}$	$\mathbf{0.526}{\scriptstyle\pm.008}$	$0.513{\scriptstyle\pm.007}$
FB15k237_10	$0.383{\scriptstyle\pm.014}$	$0.390{\scriptstyle\pm.005}$	$0.385{\scriptstyle\pm.012}$	$0.360{\scriptstyle\pm.069}$	$\mathbf{0.400}{\scriptstyle\pm.003}$

Appendix

Table C.4: Zero-shot Hits@10 of MERIT and the SoTA KGFMs on each of the

57

benchmarks . Mean Hits@10 over five pre-training runs per model, three for MOTIF and FLOCK;

\pm

is the sample standard deviation over runs; ∗ marks the single run of MOTIF on AristoV4, which enters every run of MOTIF in the last row, the average over all

57

benchmarks. Bold marks the best mean of each row.

zero-shot
model	Orig	SQSA	UQSA	SQUA	UQUA
ULTRA	$0.342_{\pm 0.004}$	$\mathbf{0.381}_{\pm 0.006}$	$0.543_{\pm 0.011}$	$0.113_{\pm 0.007}$	$\mathbf{0.221}_{\pm 0.013}$
MOTIF	$0.345_{\pm 0.006}$	$0.370_{\pm 0.003}$	$0.547_{\pm 0.010}$	$0.132_{\pm 0.009}$	$0.214_{\pm 0.017}$
TRIX	$\mathbf{0.364}_{\pm 0.003}$	$0.372_{\pm 0.004}$	$\mathbf{0.573}_{\pm 0.006}$	$\mathbf{0.163}_{\pm 0.007}$	$\mathbf{0.221}_{\pm 0.014}$
FLOCK	$\mathbf{0.359}_{\pm 0.008}$	$\mathbf{0.373}_{\pm 0.011}$	$0.561_{\pm 0.009}$	$0.155_{\pm 0.004}$	$\mathbf{0.231}_{\pm 0.017}$
MERIT	$0.358_{\pm 0.005}$	$\mathbf{0.380}_{\pm 0.004}$	$\mathbf{0.568}_{\pm 0.014}$	$0.144_{\pm 0.008}$	$\mathbf{0.233}_{\pm 0.011}$

Appendix

Table C.5: Fine-tuning does not lower the MRR of MERIT on SQUA and UQUA, as it does for TRIX . Mean MRR over the

22

Family 3 benchmarks of Section 5.1 , zero-shot and after per-benchmark fine-tuning, averaged over five pre-training runs per model, three for FLOCK and MOTIF;

\pm

is the sample standard deviation over runs. Bold as in Table 1 .

Benchmark	ULTRA	MOTIF	TRIX	FLOCK	MERIT
FB-25	$0.387{\scriptstyle\pm.003}$	$0.386{\scriptstyle\pm.004}$	$0.379{\scriptstyle\pm.003}$	$\mathbf{0.404}{\scriptstyle\pm.000}$	$0.394{\scriptstyle\pm.004}$
FB-50	$0.337{\scriptstyle\pm.002}$	$0.335{\scriptstyle\pm.003}$	$0.323{\scriptstyle\pm.007}$	$\mathbf{0.357}{\scriptstyle\pm.004}$	$0.339{\scriptstyle\pm.002}$
FB-75	$0.406{\scriptstyle\pm.004}$	$0.400{\scriptstyle\pm.003}$	$0.390{\scriptstyle\pm.003}$	$\mathbf{0.423}{\scriptstyle\pm.002}$	$0.409{\scriptstyle\pm.004}$
FB-100	$0.439{\scriptstyle\pm.004}$	$0.438{\scriptstyle\pm.003}$	$0.433{\scriptstyle\pm.011}$	$\mathbf{0.458}{\scriptstyle\pm.001}$	$0.453{\scriptstyle\pm.003}$
WK-25	$0.308{\scriptstyle\pm.005}$	$\mathbf{0.316}{\scriptstyle\pm.004}$	$0.291{\scriptstyle\pm.002}$	$0.290{\scriptstyle\pm.006}$	$0.307{\scriptstyle\pm.004}$
WK-50	$0.146{\scriptstyle\pm.004}$	$\mathbf{0.153}{\scriptstyle\pm.011}$	$0.147{\scriptstyle\pm.008}$	$0.136{\scriptstyle\pm.002}$	$0.149{\scriptstyle\pm.010}$

Appendix

Table C.6: Fine-tuned MRR of MERIT and the SoTA KGFMs on each of the

23

Family 3 benchmarks . Mean MRR after per-benchmark fine-tuning, averaged over five pre-training runs per model, three for MOTIF and FLOCK;

\pm

is the sample standard deviation over runs. Bold marks the best mean of each row.

Benchmark	ULTRA	MOTIF	TRIX	FLOCK	MERIT
FB-25	$0.640{\scriptstyle\pm.005}$	$0.633{\scriptstyle\pm.006}$	$0.629{\scriptstyle\pm.006}$	$\mathbf{0.664}{\scriptstyle\pm.001}$	$0.645{\scriptstyle\pm.004}$
FB-50	$0.543{\scriptstyle\pm.003}$	$0.538{\scriptstyle\pm.007}$	$0.526{\scriptstyle\pm.008}$	$\mathbf{0.570}{\scriptstyle\pm.002}$	$0.547{\scriptstyle\pm.005}$
FB-75	$0.610{\scriptstyle\pm.002}$	$0.599{\scriptstyle\pm.007}$	$0.586{\scriptstyle\pm.006}$	$\mathbf{0.631}{\scriptstyle\pm.001}$	$0.611{\scriptstyle\pm.004}$
FB-100	$0.642{\scriptstyle\pm.005}$	$0.635{\scriptstyle\pm.006}$	$0.628{\scriptstyle\pm.010}$	$\mathbf{0.666}{\scriptstyle\pm.006}$	$0.648{\scriptstyle\pm.004}$
WK-25	$0.497{\scriptstyle\pm.010}$	$0.505{\scriptstyle\pm.004}$	$0.491{\scriptstyle\pm.009}$	$0.465{\scriptstyle\pm.013}$	$\mathbf{0.513}{\scriptstyle\pm.005}$
WK-50	$\mathbf{0.298}{\scriptstyle\pm.003}$	$0.289{\scriptstyle\pm.007}$	$0.288{\scriptstyle\pm.010}$	$0.270{\scriptstyle\pm.022}$	$0.290{\scriptstyle\pm.018}$

Appendix

Table C.7: Fine-tuned Hits@10 of MERIT and the SoTA KGFMs on each of the

23

Family 3 benchmarks . Mean Hits@10 after per-benchmark fine-tuning, averaged over five pre-training runs per model, three for MOTIF and FLOCK;

\pm

is the sample standard deviation over runs. Bold marks the best mean of each row.

Model	runs	MRR
MERIT (motif bias and relation signature)	5	$0.386{\scriptstyle\pm.002}$
motif bias only	3	$0.379{\scriptstyle\pm.002}$
relation signature only	1	$0.292{\scriptstyle\pm.000}$
neither (plain transformer)	1	$0.312{\scriptstyle\pm.000}$
ULTRA	5	$0.365{\scriptstyle\pm.003}$
masked MERIT	3	$0.368{\scriptstyle\pm.007}$

Appendix

Table C.8: Both the attention over all relation names and the motifs as a soft prior contribute to the MRR of MERIT . Mean MRR over the

54

benchmarks of Section 5.1 , averaged over the pre-training runs in the second column;

\pm

is the sample standard deviation over runs.

Panel of Figure 23 — Figure D.1: The $15$ complex query types on which we evaluate CQA , grouped as in Tables 3 and E.3 . Structures adapted from Ren & Leskovec (2020) , with the 4p and 4i types of Gregucci et al. (2025) .

Figure D.2: MERITQuery is ahead of UltraQuery on every query type of Family 3, and on

12

and

11

of the

16

of Family 1 and Family 2 . Mean MRR over the benchmarks of each family per query type, averaged over the five fine-tuning runs per method of Section 5.2 , with FB15k237+H in Family 1; error bars are the sample standard deviation over runs. 1p appears only here.

Family 1 (16)
Benchmark	Entities	Relation names	Triples	Test triples
CoDEx Small	$2{,}034$	$42$	$32{,}888$	$1{,}828$
CoDEx Medium	$17{,}050$	$51$	$185{,}584$	$10{,}311$
CoDEx Large	$77{,}951$	$69$	$551{,}193$	$30{,}622$
WDsinger	$10{,}282$	$135$	$16{,}142$	$2{,}203$
FB15k237_10	$11{,}512$	$237$	$27{,}211$	$18{,}150$

Appendix

Table E.1: The

57

link-prediction benchmarks . Entities, relation names and triples of the inference graph, and the number of test triples, as reported by Galkin et al. (2024b) .

Family 1
Dataset	Entities	Relation names	Training triples	Inference triples	Test triples
FB15k237+H	$14{,}505$	$237$	$272{,}115$	–	$20{,}438$
NELL995+H	$63{,}361$	$200$	$114{,}213$	–	$14{,}267$
ICEWS18+H	$20{,}840$	$250$	$213{,}304$	–	$24{,}689$
Family 2
FB 106%+H	$13{,}802$	$233$	$246{,}713$	$269{,}449$	$4{,}012$

Appendix

Table E.2: The graphs behind the

19

CQA benchmarks , those of Gregucci et al. (2025) for Family 1 and of UltraQuery ( Galkin et al., 2024a ) for Family 2 and Family 3. Entities and relation names are those of the inference graph.

FB15k237, the fine-tuning dataset
	conjunction									union		negation
Dataset	1p	2p	3p	4p	2i	3i	4i	1p2i	2i1p	2u	2u1p	2in	3in	2in1p	2pi1pn	2nu1p
Training	$149{,}689$	$149{,}689$	$149{,}689$	–	$149{,}689$	$149{,}689$	–	–	–	–	–	$14{,}968$	$14{,}968$	$14{,}968$	$14{,}968$	$14{,}968$
Validation	$20{,}094$	$5{,}000$	$5{,}000$	–	$5{,}000$	$5{,}000$	–	$5{,}000$	$5{,}000$	$5{,}000$	$5{,}000$	$5{,}000$	$5{,}000$	$5{,}000$	$5{,}000$	$5{,}000$
Family 1
FB15k237+H	$22{,}804$	$936$	$1{,}461$	$2{,}670$	$6{,}692$	$9{,}615$	$20{,}189$	$1{,}586$	$604$	$6{,}695$	$473$	$5{,}000$	$3{,}057$	$2{,}663$	$2{,}093$	$5{,}000$

Appendix

Table E.3: The queries of the

19

CQA benchmarks . Number of test queries per query type, and of training and validation queries of FB15k237, the fine-tuning dataset of UltraQuery and MERITQuery; – marks a query type without queries in the split.

Graph Foundation Models

Graph Foundation Models are pretrained graph-learning systems designed to transfer across datasets, tasks, and domains with different structures and features.

See all 96 papers

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning
Jul 20, 2026Jia Ao Sun, Hao Yu, Fengran Mo +4LLM Reasoning with Graphs RL for Language Model Reasoning
Université de Montréal · Mila – Québec AI Institute · McGill University +2
KGFR: A Foundation Retriever for Generalized Knowledge Graph Question Answering
Nov 6, 2025Yuanning Cui, Zequn Sun, Wei Hu +1Multi-Hop QA LLM Grounding
School of Computer Science, Nanjing University of Information Science and Technology, Nanjing 210044, China · State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China · National Institute of Healthcare Data Science, Nanjing University, Nanjing 210093, China +2
Every Little Helps: Building Knowledge Graph Foundation Model with Fine-grained Transferable Multi-modal Tokens
Feb 11, 2026Yichi Zhang, Zhuo Chen, Lingbing Guo +2Multimodal KGs Graph Foundation Models
Zhejiang University, Zhejiang, China.

Jul 20, 2026J/K move · Enter open · S save

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

Jia Ao Sun, Hao Yu, Fengran Mo, Zhan Su+3

Université de Montréal · Mila – Québec AI Institute · McGill University+2

LLM Reasoning with Graphs RL for Language Model Reasoning Graph-Based Retrieval LLM Tool Use Knowledge Graph Question Answering

Open paper AskPDF arXiv

Knowledge graph question answering (KGQA) requires navigating from topic entities to an answer several relations away. Recent methods prompt a frontier LLM to explore the graph through a retrieval tool, but their reliance on frontier-scale inference makes them costly to deploy. We present Search-on-Graph-R1 (\sogrone{}), which internalizes this navigation into a compact 8B model through supervised fine-tuning (SFT) followed by reinforcement learning (RL). Our central idea is to scaffold a frontier teacher with each question's gold SPARQL query, so the teacher traverses a known answer-bearing path with a live Search tool rather than having to discover the path itself. Since every call executes against a live Freebase server, the resulting trajectories are grounded in the knowledge graph by construction. On WebQSP, CWQ, and GrailQA, \sogrone{} at 8B surpasses every frozen frontier-LLM system in our comparison and posts the strongest results on CWQ of any system we compare against. It does so using no auxiliary module at inference and no LLM judge during training. Isolating each training stage shows that SFT and RL contribute complementary gains, our approach transfers across model families, and RL learns to reach answers in fewer Search calls than its SFT initialization.

Abstract

Graph Foundation Models

Explore similar work

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

KGFR: A Foundation Retriever for Generalized Knowledge Graph Question Answering

Every Little Helps: Building Knowledge Graph Foundation Model with Fine-grained Transferable Multi-modal Tokens