Expressive Power of Monotonic Graph Neural Networks via Datalog
David J. Tena Cucala, Bernardo Cuenca Grau, Boris Motik, Egor V. Kostylev · Frontiers in artificial intelligence and applications · 2025
Graph Neural Networks (GNNs) are often used to learn transformations of graph data. While effective in practice, GNN-based approaches make predictions via numeric manipulations, and so their expressive power (i.e., a logical description of what they can do) is difficult to understand. In this chapter, we describe our recent research into monotonic max GNNs, a sub-family of GNNs that correspond to a class of programs expressed in Datalog, a well-known rule-based formalism. These GNNs are subject to restrictions ensuring that no prediction made by them is lost when extending or renaming their input. As a result, each monotonic max GNN is equivalent to a round of application of a finite and computable set of tree-shaped Datalog rules. Furthermore, these GNNs can be effectively trained in practice for tasks such as knowledge graph completion, achieving performance similar or superior to other state-of-the-art rule-learning systems.