Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic

Authors

  • Maximilian Pflueger University of Oxford
  • David Tena Cucala University of Oxford
  • Egor V. Kostylev University of Oslo

DOI:

https://doi.org/10.1609/aaai.v38i13.29377

Keywords:

ML: Graph-based Machine Learning, KRR: Other Foundations of Knowledge Representation & Reasoning

Abstract

The success of Graph Neural Networks (GNNs) in practice has motivated extensive research on their theoretical properties. This includes recent results that characterise node classifiers expressible by GNNs in terms of first order logic. Most of the analysis, however, has been focused on GNNs with fixed number of message-passing iterations (i.e., layers), which cannot realise many simple classifiers such as reachability of a node with a given label. In this paper, we start to fill this gap and study the foundations of GNNs that can perform more than a fixed number of message-passing iterations. We first formalise two generalisations of the basic GNNs: recurrent GNNs (RecGNNs), which repeatedly apply message-passing iterations until the node classifications become stable, and graph-size GNNs (GSGNNs), which exploit a built-in function of the input graph size to decide the number of message-passings. We then formally prove that GNN classifiers are strictly less expressive than RecGNN ones, and RecGNN classifiers are strictly less expressive than GSGNN ones. To get this result, we identify novel semantic characterisations of the three formalisms in terms of suitable variants of bisimulation, which we believe have their own value for our understanding of GNNs. Finally, we prove syntactic logical characterisations of RecGNNs and GSGNNs analogous to the logical characterisation of plain GNNs, where we connect the two formalisms to monadic monotone fixpoint logic---a generalisation of first-order logic that supports recursion.

Published

2024-03-24

How to Cite

Pflueger, M., Tena Cucala, D., & Kostylev, E. V. (2024). Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic. Proceedings of the AAAI Conference on Artificial Intelligence, 38(13), 14608-14616. https://doi.org/10.1609/aaai.v38i13.29377

Issue

Section

AAAI Technical Track on Machine Learning IV