Summary
This paper explores the impact of rational activation functions in specific classes of Graph Neural Networks (GNNs) on their capacity to uniformly approximate queries from the two-variable guarded fragment with counting (GC2). In this context, uniformly indicates that the number of GNN parameters is dependent solely on the query depth rather than the graph size. While prior studies show that GNNs with ReLU activations can uniformly express GC2, the authors demonstrate that certain GC2 queries cannot be captured by GNNs with rational activations. They further introduce RGC2, a fragment of GC2 expressible by GNNs employing rational activations. The authors conduct experiments demonstrating that approximations for specific queries remain stable as the number of nodes increases.
Strengths
**Novelty and Idea:**
Given the demonstrated advantages of rational activation functions over ReLUs in traditional neural network architectures, the authors propose the compelling idea of extending this approach to Graph Neural Networks (GNNs).
**Theoretical Contribution:**
The authors demonstrate that, in the context of GC2, GNNs with rational activation functions exhibit lower expressivity compared to those using ReLU activations.
**Pedagogical Clarity:**
The authors have made effort to clarify the logical foundations required to understand GC2 and related fragments. Section 2, in particular, is highly accessible and does an excellent job of providing readers with the necessary background in logic. This careful exposition allows the paper to be more approachable to readers who may not have a strong background in formal logic.
Weaknesses
**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.
Questions
**Universe $A$ Notation:**
In graph theory, the symbol $A $ typically denotes the adjacency matrix representing the structure of a graph. However, throughout the paper, $ A $ appears to represent the universe and is set to $ V $ in each definition. Could you clarify whether the choice of $ A $ here is tied to a general logic definition? Additionally, in Example 2 of Section 3, $ A $ is introduced as a matrix. To avoid confusion, would it be preferable to use a different letter for this matrix?
**Clarification in Example 2 of Section 3:**
I would appreciate additional clarification on Example 2 in Section 3. Specifically:
- **Usage of Vector $ c $**: The vector $ c $ is defined, but it appears to go unused. Could you elaborate on its intended purpose?
- **Indices in $ \xi^4(G, v)_i $**: The notation $ \xi^4(G, v)_i $ introduces an index $ i $ whose meaning is unclear. As this may pertain to logical constructs that not all readers are familiar with (like me), additional explanation here would improve clarity.
**Typographical Error in Proof Overview (Line 444):**
In the proof overview, line 444, there appears to be a typographical error. The text suggests that rational GNNs can uniformly express GC2, which is contradictory to Theorem 3. Could you confirm if this is an error or provide clarification?
**Loss Curve Analysis:**
Have you analyzed the training loss curves for both CReLU and rational GNNs on the training set? Examining these curves could provide insight into your theoretical claim. For instance, if rational GNNs indeed struggle to express certain GC2 queries, we might observe a higher or stagnant training loss. Such empirical observations could help substantiate your theoretical findings.
**General typographical error:**
- **line 181**: for **a** some elements of comparison of expressivity of targeted vs standard ones. **a** should be removed.
- **line 309** : $(Q_1,Q_2,Q_3,Q_4)$ instead of $(Q1,Q2,Q3,Q4)$.
- **line 360** : Our approach **and** can easily extend to a large family of GC2 queries. **and** should be removed.
- **line 450** : **Then**, we **then**. One **then** should be removed.