Graph neural networks and MSO

Graph neural networks (GNNs) are a deep learning architectu re for processing graph-structured data, and they have proven useful in various appl ications. They operate in labeled graphs and assign feature vectors (a vector of reals) to nodes in discrete rounds. Feature updates are carried out in each node by aggregating t he feature vectors of the node's neighbours into a single vector and then combining it with the node's own feature vector. The result we prove in this article concerns recurre nt graph neural networks; while a GNN typically updates node features for a constant number o f rounds, a recurrent GNN can perform updates for an unlimited number of rounds. Moreo ver, we consider two types of recurrent GNNs; ones that use real numbers ( GNN[ R ]s) and ones the use floating-point numbers ( GNN[F]s).