  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.
