  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 family of recently-discovered decidable logics
involving "Presburger quantifiers". We show how to use these logics to measure
the expressiveness of classes of GNNs, in some cases getting exact
correspondences between the expressiveness of logics and GNNs. We also employ
the logics, and the techniques used to analyze them, to obtain decision
procedures for verification problems over GNNs. We complement this with
undecidability results for static analysis problems involving the logics, as
well as for GNN verification problems.
