mlsanityData to 7 Oct 2026

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

arXiv 2302.02209 ↗First posted 4 Feb 2023cs.LG cs.AIcited by 32

Not on the map. Why?

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.

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

Builds on

28 of 43 references.

References · 28

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2016Layer Normalizationcited by 5,579
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  7. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  8. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  9. 2019RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Spacecited by 893
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2018Link Prediction Based on Graph Neural Networkscited by 829
  12. 2017Convolutional 2D Knowledge Graph Embeddingscited by 729
16 more
  1. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  2. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  3. 2019Composition-based Multi-Relational Graph Convolutional Networkscited by 395
  4. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 273
  5. 2019Inductive Relation Prediction by Subgraph Reasoningcited by 237
  6. 2021Identity-aware Graph Neural Networkscited by 197
  7. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  8. 2020Random Features Strengthen Graph Neural Networkscited by 184
  9. 2019DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphscited by 173
  10. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  11. 2021The Logic of Graph Neural Networkscited by 84
  12. 2020Relational Message Passing for Knowledge Graph Completioncited by 61
  13. 2022Weisfeiler and Leman Go Relationalcited by 28
  14. 2022Geodesic Graph Neural Network for Efficient Graph Representation Learningcited by 19
  15. 2019Graded modal logic and counting bisimulationcited by 13
  16. 2020Knowledge Embedding Based Graph Convolutional Networkcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 8; 2024: 11; 2025: 8; 2026: 5.

32 papers.

Sort:

By area:

  1. 2024Position: Graph Foundation Models are Already Herecited by 84
  2. 2023Towards Foundation Models for Knowledge Graph Reasoningcited by 83
  3. 2025GFM-RAG: Graph Foundation Model for Retrieval Augmented Generationcited by 40
  4. 2023Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databasescited by 35
  5. 2024A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoningcited by 25
  6. 2025How Expressive are Knowledge Graph Foundation Models?cited by 22
  7. 2024A Foundation Model for Zero-shot Logical Query Reasoningcited by 13
  8. 2023On the Correspondence Between Monotonic Max-Sum GNNs and Datalogcited by 12
  9. 2024Link Prediction with Relational Hypergraphscited by 9
  10. 2025Flock: A Knowledge Graph Foundation Model via Learning on Random Walkscited by 8
  11. 2023Understanding Expressivity of GNN in Rule Learningcited by 7
  12. 2023Understanding Inter-Session Intentions via Complex Logical Reasoningcited by 7
20 more
  1. 2025HYPER: A Foundation Model for Inductive Link Prediction with Knowledge Hypergraphscited by 7
  2. 2023On the Power of the Weisfeiler-Leman Test for Graph Motif Parameterscited by 6
  3. 2024Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphscited by 6
  4. 2024KnowFormer: Revisiting Transformers for Knowledge Graph Reasoningcited by 5
  5. 2025The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logiccited by 5
  6. 2023Improving Graph Neural Networks on Multi-node Tasks with the Labeling Trickcited by 4
  7. 2025Bridging Theory and Practice in Link Representation with Graph Neural Networkscited by 4
  8. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  9. 2023Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphscited by 2
  10. 2024PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learningcited by 2
  11. 2025Understanding Generalization in Node and Link Predictioncited by 2
  12. 2024Towards Better Benchmark Datasets for Inductive Knowledge Graph Completioncited by 1
  13. 2024Expanding the Scope: Inductive Knowledge Graph Reasoning with Multi-Starting Progressive Propagationcited by 1
  14. 2024One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphscited by 0
  15. 2025Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregationcited by 0
  16. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  17. 2026Harnessing Structural Context for Entity Alignment Foundation Modelscited by 0
  18. 2026Structure-Internalized Rule Language Model for Faithful Knowledge Graph Reasoningcited by 0
  19. 2026A Unifying Relational Perspective on Expressive Lottery Ticketscited by 0
  20. 2026Reification as a Transferable Vocabulary: Zero-Shot Link Prediction with Vanilla GNNscited by 0