A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs
This work addresses the incomplete understanding of graph neural networks for knowledge graphs, offering foundational insights that could impact researchers and practitioners in machine learning and AI, though it is primarily theoretical and incremental in nature.
The paper tackles the problem of understanding the capabilities and limitations of graph neural networks for link prediction on knowledge graphs, providing a systematic analysis that unifies models and characterizes expressive power via relational Weisfeiler-Leman algorithms, with empirical validation of theoretical findings.
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.