  Rule learning is critical to improving knowledge graph (KG) reasoning due to
their ability to provide logical and interpretable explanations. Recently,
Graph Neural Networks (GNNs) with tail entity scoring achieve the
state-of-the-art performance on KG reasoning. However, the theoretical
understandings for these GNNs are either lacking or focusing on
single-relational graphs, leaving what the kind of rules these GNNs can learn
an open problem. We propose to fill the above gap in this paper. Specifically,
GNNs with tail entity scoring are unified into a common framework. Then, we
analyze their expressivity by formally describing the rule structures they can
learn and theoretically demonstrating their superiority. These results further
inspire us to propose a novel labeling strategy to learn more rules in KG
reasoning. Experimental results are consistent with our theoretical findings
and verify the effectiveness of our proposed method. The code is publicly
available at https://github.com/LARS-research/Rule-learning-expressivity.
