# A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 43 references that are in the map.
- First posted on arXiv 4 Feb 2023.

## Builds on (most cited first, 28 of 28)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [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)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs](https://mlsanity.com/paper/1911.00055/) (2019)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Relational Message Passing for Knowledge Graph Completion](https://mlsanity.com/paper/2002.06757/) (2020)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [Geodesic Graph Neural Network for Efficient Graph Representation Learning](https://mlsanity.com/paper/2210.02636/) (2022)
- [Graded modal logic and counting bisimulation](https://mlsanity.com/paper/1910.00039/) (2019)
- [Knowledge Embedding Based Graph Convolutional Network](https://mlsanity.com/paper/2006.07331/) (2020)

## Built on by (most cited first, 30 of 32)

- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [GFM-RAG: Graph Foundation Model for Retrieval Augmented Generation](https://mlsanity.com/paper/2502.01113/) (2025)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning](https://mlsanity.com/paper/2410.12288/) (2024)
- [How Expressive are Knowledge Graph Foundation Models?](https://mlsanity.com/paper/2502.13339/) (2025)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [On the Correspondence Between Monotonic Max-Sum GNNs and Datalog](https://mlsanity.com/paper/2305.18015/) (2023)
- [Link Prediction with Relational Hypergraphs](https://mlsanity.com/paper/2402.04062/) (2024)
- [Flock: A Knowledge Graph Foundation Model via Learning on Random Walks](https://mlsanity.com/paper/2510.01510/) (2025)
- [Understanding Expressivity of GNN in Rule Learning](https://mlsanity.com/paper/2303.12306/) (2023)
- [Understanding Inter-Session Intentions via Complex Logical Reasoning](https://mlsanity.com/paper/2312.13866/) (2023)
- [HYPER: A Foundation Model for Inductive Link Prediction with Knowledge Hypergraphs](https://mlsanity.com/paper/2506.12362/) (2025)
- [On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters](https://mlsanity.com/paper/2309.17053/) (2023)
- [Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphs](https://mlsanity.com/paper/2410.12609/) (2024)
- [The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic](https://mlsanity.com/paper/2505.08021/) (2025)
- [KnowFormer: Revisiting Transformers for Knowledge Graph Reasoning](https://mlsanity.com/paper/2409.12865/) (2024)
- [Improving Graph Neural Networks on Multi-node Tasks with the Labeling Trick](https://mlsanity.com/paper/2304.10074/) (2023)
- [Bridging Theory and Practice in Link Representation with Graph Neural Networks](https://mlsanity.com/paper/2506.24018/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs](https://mlsanity.com/paper/2311.01647/) (2023)
- [PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning](https://mlsanity.com/paper/2405.06418/) (2024)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [Towards Better Benchmark Datasets for Inductive Knowledge Graph Completion](https://mlsanity.com/paper/2406.11898/) (2024)
- [Expanding the Scope: Inductive Knowledge Graph Reasoning with Multi-Starting Progressive Propagation](https://mlsanity.com/paper/2407.10430/) (2024)
- [One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphs](https://mlsanity.com/paper/2409.13959/) (2024)
- [Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation](https://mlsanity.com/paper/2511.07994/) (2025)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [Harnessing Structural Context for Entity Alignment Foundation Models](https://mlsanity.com/paper/2606.06109/) (2026)
- [Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoning](https://mlsanity.com/paper/2608.17443/) (2026)

## Abstract (arXiv)

Graph neural networks are prominent models for representation learning over graph-structured data. While the capabilities and limitations of these models are well-understood for simple graphs, our understanding remains incomplete in the context of knowledge graphs. Our goal is to provide a systematic understanding of the landscape of graph neural networks for knowledge graphs pertaining to the prominent task of link prediction. Our analysis entails a unifying perspective on seemingly unrelated models and unlocks a series of other models. The expressive power of various models is characterized via a corresponding relational Weisfeiler-Leman algorithm. This analysis is extended to provide a precise logical characterization of the class of functions captured by a class of graph neural networks. The theoretical findings presented in this paper explain the benefits of some widely employed practical design choices, which are validated empirically.