# How Expressive are Knowledge Graph Foundation Models?

arXiv: https://arxiv.org/abs/2502.13339 · HTML: https://mlsanity.com/paper/2502.13339/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 46 references that are in the map.
- First posted on arXiv 18 Feb 2025.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [BoxE: A Box Embedding Model for Knowledge Base Completion](https://mlsanity.com/paper/2007.06267/) (2020)
- [CoDEx: A Comprehensive Knowledge Graph Completion Benchmark](https://mlsanity.com/paper/2009.07810/) (2020)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs](https://mlsanity.com/paper/2106.12144/) (2021)
- [On the representation and embedding of knowledge bases beyond binary relations](https://mlsanity.com/paper/1604.08642/) (2016)
- [InGram: Inductive Knowledge Graph Embedding via Relation Graphs](https://mlsanity.com/paper/2305.19987/) (2023)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [Generalizing Tensor Decomposition for N-ary Relational Knowledge Bases](https://mlsanity.com/paper/2007.03988/) (2020)
- [A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs](https://mlsanity.com/paper/2302.02209/) (2023)
- [Relational Message Passing for Fully Inductive Knowledge Graph Completion](https://mlsanity.com/paper/2210.03994/) (2022)
- [AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning](https://mlsanity.com/paper/2205.15319/) (2022)
- [Dynamic Anticipation and Completion for Multi-Hop Reasoning over Sparse Knowledge Graph](https://mlsanity.com/paper/2010.01899/) (2020)
- [A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning](https://mlsanity.com/paper/2410.12288/) (2024)
- [A Multi-Task Perspective for Link Prediction with New Relation Types and Nodes](https://mlsanity.com/paper/2307.06046/) (2023)
- [Double Equivariance for Inductive Link Prediction for Both New Nodes and New Relation Types](https://mlsanity.com/paper/2302.01313/) (2023)

## Built on by (most cited first, 23 of 23)

- [Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models](https://mlsanity.com/paper/2506.14291/) (2025)
- [Bringing Graphs to the Table: Zero-shot Node Classification via Tabular Foundation Models](https://mlsanity.com/paper/2509.07143/) (2025)
- [Flock: A Knowledge Graph Foundation Model via Learning on Random Walks](https://mlsanity.com/paper/2510.01510/) (2025)
- [SEMMA: A Semantic Aware Knowledge Graph Foundation Model](https://mlsanity.com/paper/2505.20422/) (2025)
- [HYPER: A Foundation Model for Inductive Link Prediction with Knowledge Hypergraphs](https://mlsanity.com/paper/2506.12362/) (2025)
- [Multi-Domain Riemannian Graph Gluing for Building Graph Foundation Models](https://mlsanity.com/paper/2603.00618/) (2026)
- [Modality-free Graph In-context Alignment](https://mlsanity.com/paper/2603.13434/) (2026)
- [Bridging Input Feature Spaces Towards Graph Foundation Models](https://mlsanity.com/paper/2605.04834/) (2026)
- [RelAgent: LLM Agents as Data Scientists for Relational Learning](https://mlsanity.com/paper/2605.07840/) (2026)
- [KGPFN: Unlocking the Potential of Knowledge Graph Foundation Model via In-Context Learning](https://mlsanity.com/paper/2605.14907/) (2026)
- [Knowledge Reasoning Language Model: Unifying Knowledge and Language for Inductive Knowledge Graph Reasoning](https://mlsanity.com/paper/2510.13909/) (2025)
- [Geometric Structural Knowledge Graph Foundation Model](https://mlsanity.com/paper/2512.22931/) (2025)
- [Breaking the Reasoning Horizon in Entity Alignment Foundation Models](https://mlsanity.com/paper/2601.21174/) (2026)
- [Graphlets as Building Blocks for Structural Vocabulary in Knowledge Graph Foundation Models](https://mlsanity.com/paper/2605.06154/) (2026)
- [Every Little Helps: Building Knowledge Graph Foundation Model with Fine-grained Transferable Multi-modal Tokens](https://mlsanity.com/paper/2602.15896/) (2026)
- [UltRAG: a Universal Simple Scalable Recipe for Knowledge Graph RAG](https://mlsanity.com/paper/2603.28773/) (2026)
- [Boosting Knowledge Graph Foundation Models via Enhanced Negative Sampling](https://mlsanity.com/paper/2605.27023/) (2026)
- [Harnessing Structural Context for Entity Alignment Foundation Models](https://mlsanity.com/paper/2606.06109/) (2026)
- [Neural Message Passing on Structural Interaction Graphs for Fully-Inductive Graph Neural Networks](https://mlsanity.com/paper/2608.08567/) (2026)
- [Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoning](https://mlsanity.com/paper/2608.17443/) (2026)
- [Reification as a Transferable Vocabulary: Zero-Shot Link Prediction with Vanilla GNNs](https://mlsanity.com/paper/2609.11347/) (2026)
- [The Universal Classifier for Graph Learning](https://mlsanity.com/paper/2609.36302/) (2026)
- [MERIT: Scaling KG Foundation Models with Relation Transformers](https://mlsanity.com/paper/2610.15638/) (2026)

## Abstract (arXiv)

Knowledge Graph Foundation Models (KGFMs) are at the frontier for deep learning on knowledge graphs (KGs), as they can generalize to completely novel knowledge graphs with different relational vocabularies. Despite their empirical success, our theoretical understanding of KGFMs remains very limited. In this paper, we conduct a rigorous study of the expressive power of KGFMs. Specifically, we show that the expressive power of KGFMs directly depends on the motifs that are used to learn the relation representations. We then observe that the most typical motifs used in the existing literature are binary, as the representations are learned based on how pairs of relations interact, which limits the model's expressiveness. As part of our study, we design more expressive KGFMs using richer motifs, which necessitate learning relation representations based on, e.g., how triples of relations interact with each other. Finally, we empirically validate our theoretical findings, showing that the use of richer motifs results in better performance on a wide range of datasets drawn from different domains.