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

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.