A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs
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.
Code (1)
Tasks
Knowledge GraphsLink PredictionRepresentation LearningSimilar Papers 제목 키워드 기반
Link Prediction with Relational Hypergraphs
Link prediction with knowledge graphs has been thoroughly studied in graph machine learning, leading to a rich landscape of graph neural network architectures with successful applications. Nonetheless, it remains challen…
Graph Neural NetworkInductive Link PredictionKnowledge GraphsLink Prediction+1The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs
In recent years, algorithms and neural architectures based on the Weisfeiler-Leman algorithm, a well-known heuristic for the graph isomorphism problem, emerged as a powerful tool for (supervised) machine learning with gr…
BIG-bench Machine LearningNode ClassificationWeisfeiler and Leman go Machine Learning: The Story so far
In recent years, algorithms and neural architectures based on the Weisfeiler--Leman algorithm, a well-known heuristic for the graph isomorphism problem, have emerged as a powerful tool for machine learning with graphs an…
BIG-bench Machine LearningRepresentation LearningWeisfeiler and Leman Go Relational
Knowledge graphs, modeling multi-relational data, improve numerous applications such as question answering or graph logical reasoning. Many graph neural networks for such data emerged recently, often outperforming shallo…
Knowledge GraphsLogical ReasoningQuestion AnsweringWeisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Random walk kernels have been introduced in seminal work on graph learning and were later largely superseded by kernels based on the Weisfeiler-Leman test for graph isomorphism. We give a unified view on both classes of …
Graph Learning