acceptodds
Withdrawn from ICLR 2027

Are all efficient activations equally expressive? On the logic of rational graph neural networks

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

The expressivity of Graph Neural Networks (GNNs) can be described via appropriate fragments of first-order logic. Among all possible activation functions, ReLU GNNs with a fixed number of parameters attain the maximal uniform expressivity achievable within first-order logic, capturing exactly the GC2 fragment [Barceló & al., 2020]. On the other hand, as neural networks, certain activations such as the rational ones require exponentially fewer parameters than ReLU to approximate smooth functions [Boulle & al., 2020], raising the question of whether this advantage transfers to GNNs. In this article, we establish an expressivity hierarchy among various activation classes for GNNs, including the ReLUs, polynomial and rational ones. We first show that in the uniform setting, polynomial GNNs cannot express all the graph properties that ReLU GNNs can, regardless of embedding dimension or depth. Our main result states that rational GNNs also fail across several settings despite their superior approximation efficiency. On the positive side, we identify a logical sub-fragment that rational GNNs can express, and conjecture this characterization to be tight. We complement these theoretical results with experiments on real-world graphs, where we observe that the expressivity gap between rational and ReLU GNNs is moderate on bounded-order instances but grows consistently with graph order.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Expressivity, Activation Functions, Graph Neural Networks, Computational complexity, Logic

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_QzfLOpenReview ↗
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:

  1. 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.

  2. 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.

  3. 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.

Reviewer_WRk9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper provides negative results regarding the power of GNNs to express certain logical queries (in an uniform way) when activation functions are polynomial or rational functions. These results are important to the design of GNNs: for standard NN rational functions show good approximation properties, but in the case of GNNs this shows they carry less expressive power, as ReLU activations can actually express these queries. This result may be expected from the smoothness of activation functions (so I think it is clear that at least the construction in Barcelo et al wont work), but the proof require fundamentally different techniques. I think these techniques are a welcome addition to the GNN literature.

On a positive note, for the positive fragment of the logic (RGC2) you can express queries using 1/x. This opens up an interesting open question about tightness that deserves further study.

Critical strengths
  • Novel techniques to show negative results regarding the expressive power of GNNS.
  • Leaves an interesting open problem about tightness of RGC2 and rational GNNs
Critical weaknesses
  • While the body of the paper is well written, going into the appendix leaves much claims asserted and proved with sketches, which makes it much more difficult to assert the correctness of proofs. Specifically for D1, D2, It would be better to have proofs written in more detail.
Questions for authors
  • I think my main technical concerns are points D1 and D2. For the proof in D1, I would imagine you need to go back to unfixing k at some point (as there could be several possible values of k), so the proof (or my read) probably misses something. For D2, the lemmas feel very sketchy (for example in Lemma D.1, I don't think globally bounded implies a bounded gradient even in this setting.
Reviewer_uckFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates the expressive power of GNNs with rational activation functions, referred to as rational GNNs. They show that rational GNNs (with some additional assumptions, i.e., polynomial, limited number of iterations, boundedness, or scalar embeddings) are less expressive than ReLU networks in the uniform setting. They also show that RGC2, a proper subfragment of graded model logic with two variables, serves as a lower bound on the expressive power of rational GNNs. They conduct experiments demonstrating that ReLU GNNs obtain lower error than rational GNNs on queries that cannot be expressed in RCG2.

Critical strengths
  • Lower and upper bounds on rational GNNs: While there is a lot of work on the expressive power of different GNN architectures, studying the effect of using different activation functions remains relatively underexplored. The paper contributes to this by showing that sum-aggregation GNNs with rational activation functions are -- with some additional assumptions -- strictly less expressive than ReLU GNNs.
Critical weaknesses
  • Motivation and significance: The paper motivates their investigation by stating that one would expect more efficient GNNs to be more expressive (e.g., lines 44-45, 91-92). The reasoning for this hypothesis is not clear to me. Generally speaking, more expressive architectures are usually less efficient. Beyond that (imo counterintuitive) motivation, the significance of rational GNNs is not clear to me. One aspect that would strengthen the contribution would be to have bounds on the associated costs/parameter counts to better understand the trade-off between efficiency and expressivity.
  • Limitations of assumptions/results: To my current understanding, the paper presents no results on unbounded rational activation functions with any number of iterations and non-scalar embedding size, despite stating (e.g., lines 79-81) that rational GNNs are less expressive than ReLU GNNs. Theorem 3.3 only considers two iterations/layers, Theorem 3.4 assumes boundedness, and Theorem 3.5 restricts embeddings to be scalar. If my understanding is correct, I think the claims of the paper are misleading and not supported by the theoretical results, and should be adapted accordingly.

There are also some issues with respect to clarity (see below and in the Questions), but I think these would be fixable within the rebuttal period.

Minor comments:

  • please consider distinguishing between text and parenthetical citations to improve readability
  • some notation is undefined and thus renders verifying the theoretical results more difficult: e.g., what is Col$_i$ in line 180, Ω0\Omega_0 in line 314, KK and ϵ′\epsilon' in line 330, hh in line 362, R(x)R(x), β\beta, aia_i, sis_i in line 378?
  • the sentence in lines 269-299 is really difficult to parse
  • typo in line 676: (G,v)(G,v) should likely be in a math environment
  • lines 686-688: doesn't Theorem B.3 only hold for injective aggregation/readout functions? And it is not clear which precise Theorems in Morris et al. (2019) and Xu et al. (2018) you refer to
  • the experimental setup is not described in sufficient detail
Questions for authors
  • Could you explain why one would expect more efficient activation functions in the combine step of GNNs to lead to more expressive power?
  • Could you explain the motivation/significance of studying the expressive power of rational GNNs? Are they ever used in practical settings?
  • How exactly does the training in your experiments work? E.g., are the results averaged across all nodes of a graph? Why is it not a classification task (either the query is satisfied, or it is not satisfied)? What is the size of the training vs the test set?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.