How Aggregation Functions Affect the Uniform Expressiveness of Graph Neural Networks

We analyse how the choice of the aggregation function in graph neural networks (GNNs) affects their uniform expressiveness. We show that arbitrary aggregation yields expressiveness of infinitary graded modal logic. Expressiveness strictly decreases when moving from arbitrary aggregation to sum, from sum to mean, and from mean to max. When GNNs are equipped with global readout and arbitrary aggregation, they have the expressiveness of infinitary C2 logic and restricting aggregation to sum does not decrease their expressiveness. However, still, the expressiveness strictly decreases when moving from sum aggregation to mean, and from mean to max. In the case of simple GNNs, where combination functions are linear transformations followed by a non-linearity and the classification function is a threshold function, the landscape differs. In particular GNNs with sum aggregation and readout no longer have the expressiveness of full infinitary C2. These results provide us with new insights on the expressiveness of GNNs, showing that even subtle architectural modifications can significantly influence their expressive power.