The logic of rational graph neural networks

1. The significance of the contribution is small. It is not clear, either from references or experiments, why we should care about GNNs with rational activation functions - could such references or experiments perhaps be provided?. Thus, these (already minor) theoretical results about what fragments of logic they can and cannot express do not seem substantial.

2. The presentation is lacking.

2.1. The background takes up far too much space, with novel contributions of the paper first appearing on page 7. The background is also too verbose, since anyone who is interested in this work will either already be familiar with much of the background, or can go read some of the literature. I suggest rather summarising the background knowledge and referring the reader to the appendix / related work for a more in-depth explanation. For example, L185 - L205 uses a lot of space to define FOL on graphs. It can be condensed both by cutting whitespace, and by being less verbose.

2.2 The structure makes it difficult to follow: all theoretical results are presented in L335 - 352, with the proof sketches and explanations appearing far below. RGC2 is only defined in L416 but references in a theorem in L351. All technical terms should be defined before they are used and proof sketches / intuitions should appear near one another. Remark 5 is not useful, since it is referencing things that are only in the appendix, and cannot be made sense of without first reading the appendix. If it could be presented more intuitively, or in a way that makes it clearer why it is relevant to the proof, that would help.

2.3 In general, the space is used poorly, and the paper did not need the full 10 pages. Parts of the paper are lacking intuition and explanation (e.g. section 3) whilst others are far too verbose. For example, L250 - L269 ends up repeating much of what was said above.

3. The experiments are small in scope and the results that were obtained seem to undercut the significance of the theoretical contribution, since the theoretical advantage of CReLU GNNs does not transfer to a practical advantage. To better support the work, more substantial experiments should be performed across both artificial datasets (i.e. on more queries) as well as on some standard benchmarks.

Lack of Literature Examples for GNN Types:

In Remark 1, the authors discuss three types of Graph Neural Networks (GNNs); It would be helpful if you could provide specific examples from the literature for each GNN type mentioned. This would give readers a better understanding of how these different GNN architectures have been applied in practice and studied theoretically.

Clarity Issues in Example 2 of Section 3:

Example 2 in Section 3 presents some ambiguities, potentially due to complex logical reasoning. For readers who may not be experts in logic, further clarification or simplification would enhance comprehension. Presenting the example in more accessible terms could improve the paper’s accessibility and impact.

Figure 1 Caption:

To improve Figure 1, consider expanding the caption to provide more context about what the figure represents and how it relates to the main concepts discussed in the paper. This would allow readers to understand the figure's significance without needing to refer back to the main text.

Limited Scope of Experiments:

The experimental evaluation in this paper is restricted to two queries, and the results do not fully corroborate the theoretical assumptions made by the authors. Additionally, the authors claim that a ReLU GNN can approximate CReLU GNN, but no direct comparison is provided in the experiments. Including a comparison with a ReLU GNN would strengthen the experimental results and help substantiate the authors’ claims.

• The main contribution of this work is to point out RGC2 as a subset of GC2 which discribes the uniform logical expressivity of rational MPNNs. However, there is only one theorem (Theorem 4) that states all RGC2 formulas are expressed by rational MPNNs, and for a more complete study of GNN expressivity, it is still necessary to:
  • Show RGC2 completely captures the logical expressivity of rational MPNNs (if this was the case). This can be done by either:
    • Proving that RGC2 is equivalent to rational MPNNs in terms of distinguishability, i.e. for arbitrary graphs $G,H$, rational MPNNs distinguish $G$ and $H\iff$ there is a RGC2 formula that distinguish $G,H$ (which I believe is not the case)
    • Proving that RGC2 is the largest logic set captured by rational MPNNs, i.e. for arbitrary logic formula $Q\notin$RGC2, $Q$ is not uniformly captured by rational MPNNs.
  • If the above statements do not hold for RGC2, discuss why it is not feasible to find the subset of logic formulas that satisfies the above statements, and explain why RGC2 is large enough to cover up important properties of rational MPNNs.

Suggestions:

• This paper focus on a very specific setting of GNNs: MPNNs with rational activations. This paper can be further strengthened by:

  • Discussing why it is important to study rational activations.
  • Extending to more complex GNN variants (i.e., consider higher-order MPNNs, which are direct extensions of MPNNs and are expressed by $\mathrm{FOC}_k$).
  • Extending to different activation functions.

• Other suggestions:

  • The discussion of RGC2 as the main contribution of the paper is short. For example, the authors can discuss the general difference between GC2 and RGC2 (i.e. what kinds of logic formulas are discarded, what patterns GC2 can capture but RGC2 cannot).
  • Theorem 4 is the main theorem of this paper and Section 5 introduces the main constribution. Maybe consider putting Theorem 4 in Section 5?

• Novelty and relevance. My main concern is the novelty and the relevance of the results. NNs with rational activations seems really a niche, and I am unable to understand the motivation to investigate this fragment.
• I maybe mistaken, but it also seems that RGC2 is an arbitrary restriction picked up by authors to show some positive results. I think a better attempt towards providing positive results for a larger fragment, or even completely capturing Rational GNNs could have been attempted.
• I would have been more inclined towards acceptance, if a clear picture of why RGC2 is the best fragment they can capture would have been presented.