- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This submission is concerned with the relative expressive power of graph neural networks with different activation functions, and also in relation to certain logics. More precisely, the authors study ReLU, polynomial activation functions, and rational activation functions, all on undirected graphs. The main results are as follows:
-
While ReLU-based GNNs can express all formulas of graded modal logic (here called GC2), this is not the case for polynomial activation-based ones. The separating property is a simple one already known from an earlier paper by Khalife and Tonelli.
-
Under some additional assumptions, the same is also true for rational activation. This is mildly surprising since rational activation outperforms ReLU in function approximation with feed-forward networks.
-
Boolean combinations of positive conjunctive graded modal logic formulas can be expressed by rational activation-based GNNs.
Critical strengths
The effects on expressive power of using different activation functions is an important topic in LLM research.
Critical weaknesses
Two major correctness problems that I verified manually:
Problem 1
The proof of Theorem 3.3 does not work. It claims that the limits of \phi+(m) and \phi-(m) must be finite. But that does not follow from Definition 2.3 which permits \phi+(m) to have limit +\infty and \phi-(m) to have limit -\infty. Maybe Definition 2.3 is supposed to state that 1 \geq \xi(G,v) \geq 1-e and 0 \leq \xi(G,v) \leq e? Unfortunately though, that does not repair the proof. That’s because even finite limits do not imply that a constant change in an aggregate produces a vanishing output difference. As a concrete example, initialize all vertices with 1 and use comb0(a,b)=b and comb1(a,b)=b-2a+1. These are affine, hence rational, and have no poles. On T[x,1,m], after the first iteration:
- the root embedding is m;
- the exceptional child embedding is x+1;
- each regular child embedding is 2. The root output after the second iteration is therefore [x+1+2(m-1)]-2m+1=x. Consequently, \phi+(m)=1 and \phi-(m)=0 for every m. It seems that if Theorem 3.3 is actually true, one needs to choose different trees to prove it.
(It is not entirely clear whether an all 1 initialisation is permitted; the paper is unclear in this respect: Figure 2 shows different vertex colours, but other proofs also assume all-vertices-equal initialisations; in any case, the example can be adapted to different initialisations).
Problem 2
The proof of Theorem 3.4 does not work. In particular, Lemma D.1 is false. The lemma asserts that a globally bounded rational map is Lipschitz in its first argument, uniformly over the unbounded second argument. Consider the scalar rational map f(u,v)=uv / (1+u^2v^2). Its denominator is strictly positive everywhere, and |f(u,v)| <= 1/2, so it satisfies the stated boundedness and domain assumptions.
Take K=[0,1]. For v >= 1, choose u1=1/v and u2=0. Then |f(u1,v)-f(u2,v)|=1/2 and |u1-u2|=1/v. The proposed Lipschitz bound would require L_K >= v/2 for every v. Clearly, no finite L_K has this property. The specific inference at line 1009—boundedness of the function implies boundedness of its gradient on KxR^d is false. Compactness in only one factor does not fix this.
In view of these problems, it seems clear that the paper cannot be accepted. Let me recommend to the authors, though, to run an LLM also on your other proofs. You will find that
- the proof of Theorem 3.4 does not work even if Lemma D.1 is assumed to be true
- Lemma D.2 is false
- the proof of Lemma B.6 is wrong (the degree recursion), although the proof of Theorem 3.1 can probably be repaired
- The induction in Appendix C requires that, for every C>=0, neighborhood sums take only finitely many values below C, across all graphs; but this property is not preserved by the rational interpolation construction. Thus, also Theorem 3.9 is not proved.
- Lemma C.1 has an incorrect partial-fraction formula
Questions for authors
It seems impossible to address all the technical problems in the paper in a rebuttal. But of course I'd be interested in hearing what the authors think.