Thanks for going through our rebuttal! We answer your question below in two parts:
***What does the logical characterization achieve?*** When studying the expressive power of neural networks, one is typically interested in characterizing the class of functions that can be captured (or, approximated) by the neural network. In the context of graph machine learning, we are interested in the exact same question with the difference that the functions are defined over graphs. For the task of link prediction, this means the following: for each knowledge graph G, we are interested in functions of the form $f(G): R \times V \times V \to$ {0,1} , because we want to quantify whether a link $r(a,b)$ is true or not, where $r \in R$, and $a,b \in V$.
This is precisely what is achieved by logical characterizations: if we can show that a GNN architecture can capture a logic L, then it means that this GNN architecture can capture all functions which can be expressed in this logic. This is very important, because if a GNN architecture A captures a *strictly larger logic* than another GNN architecture B, then we can conclude that A is *more expressive than* B. One implication is indeed regarding the use of global readout: specifically, we obtain that C-MPNNs with global readout are strictly more powerful than standard C-MPNNs. This means that there is *at least* one function that the former can capture but the latter cannot which is empirically confirmed in Appendix B.1.
***How does this compare to WL-based characterizations?*** Logical characterizations of GNNs date back to the work of Barceló et al [1]. Unlike the characterizations of GNNs based on the WL test, these logical characterizations are uniform, in the sense that they hold over the set of all graphs. Therefore, these studies are harder to obtain and yield more powerful characterizations, because they require a single parametrized model which would apply uniformly to all graphs. Uniformity condition is much more realistic, as it applies to all graphs of all size/structure, and hence desired in theoretical analysis. Non-uniform WL characterisations are indeed weaker than logical characterisations: one example is that they cannot recognise the expressiveness gain of using of global readout which is recognised by the logical characterization, as shown in Barceló et al [1].
Please let us know if this answers your question. These technical differences are intricate and easy to overlook, and we are happy to explain these more in our paper, if you agree these explanations are useful.
[1] Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks., ICLR, 2020.