Research map / Graph learning / Knowledge and temporal graphs
How Expressive are Knowledge Graph Foundation Models?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces MOTIF, a framework for knowledge graph foundation models that lifts KGs to relational hypergraphs over arbitrary graph motifs, proves expressivity hierarchy by motif refinement, and shows richer (3-path) motifs improve zero-shot and fine-tuned link prediction over ULTRA.
Problem
Existing knowledge graph foundation models (KGFMs) that generalize to unseen relations lack a theoretical understanding of their expressive power, and they typically rely only on binary motifs to learn relation invariants.
Approach
Learn relation invariants from arbitrary (k-ary) graph motifs via a Lift operation that builds a relational hypergraph over relations; show separation power depends on motifs, with a necessary core-onto homomorphism condition for when a new motif adds expressivity, and prove ULTRA equals the 2-path motif set.
Key results
- On ConnectHub(k), ULTRA and 2-star motif variants stay at 0.50 accuracy, while the (k+1)-star motif variant reaches 1.00.
- Averaged over 54 KGs end-to-end, MOTIF with 3-path motifs achieves MRR 0.409 and H@10 0.561 versus ULTRA's 0.394 and 0.552.
- On Metafam, MOTIF achieves a 45% MRR improvement over ULTRA in zero-shot setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add 3-path motifs instead of using 2-path motifs (ablation) | MOTIF · 51 KGs, zero-shot, total average | MRR: 0.370 -> 0.378 | Helped |
| Add 3-path motifs instead of using 2-path motifs (ablation) | MOTIF · 51 KGs, fine-tuned, total average | MRR | Helped |
| Add 2-path motifs instead of using only h2t (ablation) | MOTIF · 51 KGs, zero-shot, total average | MRR: 0.361 -> 0.370 | Helped |
| Add motifs instead of removing all motifs (ablation) | MOTIF · 51 KGs, zero-shot, total average | MRR: 0.082 -> 0.378 | Helped |
| Add 3-path motifs | MOTIF · 54 KGs, end-to-end total average | MRR: 0.394 -> 0.409 | Helped |
| Add 3-path motifs | MOTIF · WIKITOPICS-MT, average across 8 datasets | MRR: 0.331 to 0.358 | Helped |
| Add 3-path motifs | MOTIF · WIKITOPICS-MT, average across 8 datasets | Hits@10: 0.442 to 0.481 | Helped |
| Add 3-path motifs | MOTIF · WN-v2, end-to-end | MRR: 0.296 -> 0.684 | Helped |
| Use a star motif wider than the positive-class hub (ablation) | MOTIF · ConnectHub(k) | accuracy: 50% -> 100% | Helped |
| Use 3-star motifs rather than 2-star motifs (ablation) | MOTIF · ConnectHub(2) | accuracy: 0.50 -> 1.00 | Helped |
| Use 4-star motifs rather than 3-star motifs (ablation) | MOTIF · ConnectHub(3) | accuracy: 0.50 -> 1.00 | Helped |
| Use 5-star motifs rather than 4-star motifs (ablation) | MOTIF · ConnectHub(4) | accuracy: 0.50 -> 1.00 | Helped |
Surprising findings
- Under the framework, an instance preserving relation invariance is inherently less expressive than its entity encoder, so NBFNet is strictly more expressive than ULTRA on graphs with the same relation types.
- On WN-v2, ULTRA produces highly similar relation embeddings, giving MRR 0.296 versus 0.684 for the richer-motif model in end-to-end training.
Limitations
- Richer motifs increase computational cost in time and memory, limiting scalability to large graphs.
- Degradation of relation learning observed in end-to-end training on WN-v2 was not seen in pretraining experiments.
- Theoretical results are about separation power, not generalization guarantees.
Experimental setup
Datasets: FB15k237 WN18RR CoDEx Medium WN-v2 Metafam WIKITOPICS-MT ConnectHub (synthetic)
Benchmarks: ConnectHub 51 KGs inductive and transductive link prediction 54 KGs end-to-end Metafam WIKITOPICS-MT
Metrics: MRR Hits@10 accuracy
Baselines: ULTRA InGram TRIX RMPI NBFNet
Builds on: ULTRA NBFNet HCNets InGram C-MPNN
Closest papers by meaning
- Towards Foundation Models for Knowledge Graph Reasoning (ICLR 2024 · similarity 0.88)
- Towards Global-Topology Relation Graph for Inductive Knowledge Graph Completion (AAAI 2025 · similarity 0.86)
- Position: Graph Foundation Models Are Already Here (ICML 2024 · similarity 0.86)
- KG-FIT: Knowledge Graph Fine-Tuning Upon Open-World Knowledge (NeurIPS 2024 · similarity 0.86)
- Toward a Unified Statistical Theory of Unsupervised Pretraining and Supervised Neural Knowledge Graph Learning (NeurIPS 2026 · similarity 0.86)
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.