Decidability of Graph Neural Networks via Logical Characterizations

Michael Benedikt, Chia-Hsuan Lu, Tony Tan

We present results concerning the expressiveness and decidability of a popular graph learning formalism, graph neural networks (GNNs), exploiting connections with logic. We use a f…