EXP-GNN: Towards expressive propagation function design for graph neural network-based knowledge graph completion

The message-passing process in a graph neural network (GNN)-based knowledge graph completion (KGC) model consists of two key components: propagation path design (PPD) and propagation function design (PFD). Existing GNN-based KGC methods mainly focus on studying the PPD component while lacking in-depth insights into PFD. In this paper, we investigate the expressive power of PFD from both theoretical and empirical perspectives. Specifically, we first generalize the theoretical injectivity principle for highly expressive GNN propagation functions from single-relational graphs to multi-relational ones. Based on this generalization, we theoretically find that existing expressive propagation function designs for GNNs can be directly extended to GNN-based KGC tasks and that a more expressive GNN inherently results in a more expressive GNN-based KGC model. Then, we develop a design space for the PFD component, involving not only injective propagation functions but also many non-injective ones to facilitate a systematic empirical analysis. Finally, we propose a GNN-based KGC framework, EXP-GNN, where we validate our theoretical findings and systematically evaluate the developed design space. The evaluation results offer some interesting empirical findings, from which we derive a practical design principle to help inspire more powerful GNN-based KGC models: a stronger neighborhood feature extraction capability in the propagation functions makes the resulting GNN-based KGC models theoretically and practically more powerful.