Logical characterizations of recurrent graph neural networks with reals and floats

Graph Neural Networks (GNNs) are powerful tools for analyzing graph data, but their theoretical properties, particularly those of recurrent GNNs, remain insufficiently understood. This paper tackles the limitations by focusing on the expressive power of recurrent GNNs, investigating the differences between using real numbers and the more practical floating-point numbers in their computations. This exploration is crucial because it directly impacts the types of problems these networks can effectively solve and how they are implemented in practice.

The paper presents exact logical characterizations of recurrent GNNs for both scenarios. For floating-point numbers, a rule-based modal logic with counting capabilities accurately captures the expressive power. For real numbers, a more expressive infinitary modal logic is required. The research also demonstrates that, surprisingly, for properties definable in monadic second-order logic, recurrent GNNs with real and floating-point numbers are equally expressive. These findings are significant because they provide a solid theoretical framework for understanding and further developing recurrent GNNs, moving beyond simple constant-depth analysis.