Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit

Eran Rosenbluth, Martin Grohe

We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggreg…