The ability of graph neural networks (GNNs) for distinguishing nodes in graphs has been recently characterized in terms of the Weisfeiler-Lehman (WL) test for checking graph isomorphism. This characterization, however, does not settle the issue of which Boolean node classifiers (i.e., functions classifying nodes in graphs as true or false) can be expressed by GNNs. We tackle this problem by focusing on Boolean classifiers expressible as formulas in the logic FOC 2 , a well-studied fragment of first order logic. FOC 2 is tightly related to the WL test, and hence to GNNs. We start by studying a popular class of GNNs, which we call AC-GNNs, in which the features of each node in the graph are updated, in successive layers, only in terms of the features of its neighbors. We show that this class of GNNs is too weak to capture all FOC 2 classifiers, and provide a syntactic characterization of the largest subclass of FOC 2 classifiers that can be captured by AC-GNNs. This subclass coincides with a logic heavily used by the knowledge representation community. We then look at what needs to be added to AC-GNNs for capturing all FOC 2 classifiers. We show that it suffices to add readout functions, which allow to update the features of a node not only in terms of its neighbors, but also in terms of a global attribute vector. We call GNNs of this kind ACR-GNNs. We experimentally validate our findings showing that, on synthetic data conforming to FOC 2 formulas, AC-GNNs struggle to fit the training data while ACR-GNNs can generalize even to graphs of sizes not seen during training.
The paper utilizes recent insights into the relationship between the Weisfeiler-Lehman (WL) test for checking graph isomorphism and Graph Neural Networks (GNNs) in order to characterize the class of node classifiers that can be captured by a specific GNN architecture, called aggregate-combine GNN (AC-GNN). 
The primary contribution of this work is the identification of the logical classifiers that can be represented within an AC-GNN, a fragment of first order logic called graded modal logic, as well as an extention of AC-GNNs with the ability to capture a strictly more expressive fragment of first order logic, called ACR-GNN. Both of these results are supported by formal proofs and derivations, adding not only theoretical value to the presented work, but also intuitive insights behind the reasons of the AC-GNN limitations. In addition, the presented experiments demonstrate the practical implications of the results, with the exception of some datasets where no significance difference in performance between AC-GNNs and ACR-GNNs was found.
I believe that the contributions of this paper are significant. On the one hand, studying theoretical properties of GNNs facilitates their transparency and highlights the range of applications they can be used in. On the other hand, although the GNN variant introduced by the author is a special case of an existing class of GNNs, the motivation behind its introduction is different and follows naturally from the discussion within the paper.
The fact that no actual difference in performance between AC-GNNs and ACR-GNNs was noticed in the only non-synthetic dataset used in the experiment should prompt the author to run experiments with more real life datasets, in order to empirically verify the results, but this is a minor point.