acceptodds
Under review as a conference paper at ICLR 2027

MERIT: Scaling KG Foundation Models with Relation Transformers

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
knowledge graph foundation models, link prediction, complex query answering, zero-shot, transformers, knowledge graph reasoning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gwqCOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes, MERIT, a knowledge graph foundation models for inductive link prediction, where the main contributions is to replace the relational NBFNets in ULTRA by a variant of transformer. The entity encoder and the overall link prediction framework, including the extension to complex query answering, are borrowed from ULTRA and ULTRAQuery. The authors motivate MERIT through the computational costs of recent KGFMs and the improvement of the overall acrruacy.

Critical strengths

The empirical results are promising, and the evaluations are standard and extensive. The author also motivates over the complex query answering, unlike most of the KGFM literature. Additionally, I also appreciate the effort to report computational costs, including runtime, FLOPs, and memory consumption. Such comparisons are useful for understanding the practical trade-offs among existing KG foundation models.

Critical weaknesses

As described in the paper summary, MERIT largely retains the architecture of ULTRA, including the four relational motif types, query-conditioned relation representations, the entity-level NBFNet encoder, and the overall link prediction procedure. The only difference between ULTRA and MERIT is only the relation encoders. This, by itself, is not an issue, as existing KGFM such as MOTIF are also the same. However, the motivations of MERIT are not convincing. The authors motivate MERIT by arguing that motif-constrained message passing restricts interactions between relation types and that dense attention can overcome these limitations. First, the relation-level MPNN in ULTRA already allows information to propagate between relations through multiple message-passing layers. The absence of a direct motif connection does not necessarily prevent two relations from exchanging information. Second, MERIT continues to rely on exactly the same four handcrafted relational motifs as ULTRA. Although dense attention relaxes the connectivity restrictions, the structural information available to the relation encoder is still derived from these motifs. As a result, the claimed expressivity gain is precisely MPNN v.s. Graph Transformer, which is not limited to KGFM but a general graph learning property that is well-studied and does not only limited to MPNN here. I would appreciate a more precise explanation of what structural or relational patterns MERIT can capture that ULTRA cannot, ideally supported by theoretical analysis or controlled experiments demonstrating the limitations of motif-constrained message passing, i.e., by presenting counter-examples over expressivity limitations similar to MOTIF or TRIX, or even by creating synthetics datasets similar to FLOCK.

Another major concern is the computational efficiency motivation. Replacing sparse relation-level message passing with dense self-attention does not inherently improve computational scalability (it actually makes it worse theoretically!). The complexity of relation-level message passing depends on the number of edges in the relation graph, while dense self-attention introduces quadratic complexity in the number of relation types. The empirical efficiency of MERIT appears to depend substantially on the relatively small relation vocabularies of the evaluated benchmarks and the availability of highly optimized attention implementations, such as FlexAttention. These implementation advantages do not establish an algorithmic improvement in computational complexity over ULTRA. In fact, Figure B.2 reports that MERIT requires approximately 5.5 PFLOPs compared with 5.2 PFLOPs for ULTRA, despite their similar inference times. As a result, the motivation for efficiency is hardly convincing to me.

Questions for authors

Beyond replacing ULTRA's relation-level MPNN with a structurally biased Transformer, what is the main new methodological contribution of MERIT? How does it differ conceptually from existing graph Transformer architectures?

Since MERIT still uses the same four relational motifs as ULTRA, what additional structural information can it capture? Can the authors provide concrete examples or theoretical analysis showing limitations of ULTRA that MERIT overcomes?

Can the authors provide controlled scaling experiments with larger relation vocabularies and varying relation-graph sparsity? How much of the observed efficiency comes from optimized attention kernels rather than reduced computational work?

Reviewer_6tkGOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes MERIT, a knowledge graph foundation model for zero-shot link prediction on unseen graphs. Unlike ULTRA and follow-up methods that propagate messages over motif-derived relation graphs, MERIT replaces the relation encoder with a Transformer whose relation tokens attend globally to one another. Four relation co-occurrence motifs are encoded through additive attention biases and permutation-invariant relation signatures, while an NBFNet entity encoder is retained. Extensive experiments on zero-shot link prediction benchmarks demonstrate that MERIT achieves competitive performance while substantially reducing training and inference costs. The paper further adapts MERIT to complex query answering (MERITQuery) and introduces hardness-balanced +H evaluations for additional dataset families. Experimental results show that MERITQuery outperforms UltraQuery on complex query answering benchmarks with comparable computational costs.

Critical strengths
  1. The paper proposes a concise, reusable model architecture and validates it through relevant downstream tasks. Representing relation co-occurrence patterns through soft attention biases and relation signatures is an appealing alternative to expanding motif-constrained relation graphs. The CQA adaptation, matched UltraQuery fine-tuning recipe, and attempts to balance reasoning hardness go beyond a single-task link-prediction demonstration.

  2. The experiments in the paper are convincing, and the trade-off between accuracy and efficiency has been thoroughly empirically validated. MERIT matches the strongest zero-shot link-prediction baselines while requiring roughly ULTRA-level inference time. The comparisons cover many graphs and report multiple pretraining runs, wall-clock inference, per-batch training time, and stage-level profiling on a common H100 system. This makes the efficiency contribution practically meaningful rather than merely asymptotic.

Critical weaknesses
  1. The ablation study does not provide rigorous proof that all-to-all attention is the key reason for the performance improvement. The paper compares a standard Transformer, masked MERIT, and full MERIT. However, masked MERIT not only restricts attention connections but also sets the query-key logits to zero. Consequently, the observed performance differences reflect changes to both the scope of attention and the content-dependent attention mechanism, making it impossible to accurately isolate the individual contributions of each.

  2. Some conclusions have limited experimental support. For CQA, the improvement on Family 2 is only 0.002 MRR, with a slight performance degradation on conjunctive queries. Furthermore, the authors evaluate the computational overhead of additional motifs by duplicating existing motif tensor slices rather than constructing genuinely new higher-order motifs. Therefore, the experimental evidence supporting the end-to-end scalability of the proposed approach remains limited.

Questions for authors
  1. Could the authors report a masked version of full MERIT that retains its query–key attention logits, relation signatures, and all other settings, changing only the allowed attention pairs? A breakdown by motif-connected versus motif-unconnected pairs would also help directly test the proposed advantage of communicating beyond the predefined motifs.

  2. Given the O(R^2) complexity of all-to-all attention in MERIT, how do inference latency, peak memory, and motif precomputation costs scale with larger relation vocabularies and genuinely higher-order motifs? Could the authors also report training throughput or time to a matched validation MRR for a fairer efficiency comparison?

  3. The T = 8 and T = 16 experiments only duplicate existing motif slices, without evaluating the cost of extracting genuinely higher-order motifs. Could the authors report the end-to-end inference cost, including motif precomputation, when using actual higher-order motifs? Additionally, could the authors report total pretraining GPU-hours to reach a matched validation MRR, rather than only per-batch training time?

Reviewer_iJMHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper addresses the computational cost of knowledge graph foundation models. Models such as TRIX and FLOCK improve prediction accuracy over ULTRA but require substantially more inference time. MERIT replaces ULTRA’s relation encoder with a transformer that allows all relation pairs to interact. Information from four graph motifs enters both as an attention bias and as a summary in each relation’s token, guiding attention without restricting which relations can communicate.

The contributions include detailed cost measurements of existing models, the MERIT architecture, its extension to complex query answering, MERITQuery, and new hardness-balanced benchmarks. Across 56 benchmarks, MERIT requires 0.55 hours of inference, compared with ULTRA’s 0.58, TRIX’s 3.31, and FLOCK’s 61.86. On the 54-benchmark accuracy evaluation, it achieves 0.386 MRR, comparable to TRIX and FLOCK at 0.384. MERITQuery also improves over UltraQuery at comparable inference cost. Ablations support the combined design, although they do not fully separate the benefits of unrestricted interaction from content-based attention. Additional motif features have little measured runtime cost after preprocessing, but this experiment duplicates existing features rather than computing richer motifs. It also remains unclear how richer motifs would be represented. For example, a motif involving three relations may require preserving their joint connection, which could be lost when summarised into features for relation pairs. Thus, the experiment does not establish the full cost or adequacy of extending MERIT to such motifs.

Critical strengths
  1. Competitive accuracy at substantially lower cost, i.e, MERIT achieves accuracy comparable to TRIX and FLOCK while requiring about 6x and over 100x less inference time, respectively, on the reported benchmark suite. Detailed measurements of runtime, memory, and computational cost also help explain these savings. This makes competitive knowledge-graph prediction substantially more practical.

  2. Broad evaluation, including complex query answering: The paper evaluates link prediction across 54 benchmarks and multiple training runs, including transfer to unseen entities and relations. MERITQuery also improves over UltraQuery at comparable inference cost on benchmarks balanced across query difficulty.

Critical weaknesses

The ablations show that MERIT’s full design works better than its simplified versions, but the authors do not clearly identify why. In masked MERIT, the authors both restrict which relations can communicate and remove the part of attention that weights relations based on their current representations. Because both changes happen together, the lower accuracy could result from either change or their combination. This does not undermine the reported performance, but it leaves uncertainty about the claim that allowing relations without a connecting motif to communicate is responsible for the improvement.

Questions for authors

Have the authors tested a version that restricts attention to motif-connected relations while keeping the full attention-scoring formula? This comparison would help determine whether allowing additional relations to communicate improves accuracy independently of how their attention weights are computed.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.