Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This paper establishes novel theoretical connections between Boolean node classifiers on aggregate-combine Graph Neural Networks (AC-GNNs) and first-order predicate logic (FOC2). It shows that current boolean node classifiers on AC-GNNs can only represent a subset of FOC2 but that a simple extension taking into global information can generalise AC-GNNs to the full FOC2.

The style of the manuscript is mixed: the abstract and introduction are quite dense for non-experts; a motivating real-world example could help here. The other sections, on the other hand, are quite good to follow and most concepts have a good high-level introduction as well as a little example to follow the arguments.

The theoretical connections connection between GNNs and first-order logic strike me as interesting. I did not, however, understand the results reported in table 2: ACR reaches optimal performance only on alpha_1 but not on alpha_2 and alpha_3. Does this happen because the latter two expressions are not part of FOC2?

---
I increased my rating due to the author rebuttal.
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: The paper elaborates on the expressivity of graph neural networks (GNNs). More precisely, the authors show that expressivity of AC-GNNs (aggregate and combine) can only express logical classifiers that can be expressed in graded modal logic. By adding readouts, ACR-GNNs (aggregate, combine and readout) can capture FOC2 which is logical classifiers expressed with 2 variables and counting quantifiers. The second theorem leaves open the question of whether ACR-GNNs can capture logical classifiers beyond FOC2.

The paper is written nicely, its easy on the eyes, and delegates the proofs to the appendix. I was a bit surprised by the lack of a discussion connecting the choice of the aggregate and combine operations to the representation power of GNNs. One has to delve deep into the proofs to find out if the choice of these operations affects expressivity.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: 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.
review_title: Official Blind Review #1

Meta-review: The paper focuses on characterizing the expressiveness of graph neural networks. The reviewers were satisfied that the authors answered their questions suffciiently and uniformly agree that this is a strong paper that should be accepted.
Decision: Accept (Spotlight)