Logical Characterizations of GNNs with Mean Aggregation
This provides theoretical insights into the limitations and capabilities of GNN architectures for researchers in graph machine learning, but it is incremental as it builds on existing logical characterizations.
The paper tackles the problem of characterizing the expressive power of graph neural networks (GNNs) using mean aggregation, showing that in the non-uniform setting, they are equivalent to ratio modal logic, with expressive power higher than max aggregation but lower than sum aggregation, and in the uniform setting, under certain assumptions, they are strictly less expressive than both sum and max GNNs relative to MSO.
We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function. In the non-uniform setting, we show that such GNNs have exactly the same expressive power as ratio modal logic, which has modal operators expressing that at least a certain ratio of the successors of a vertex satisfies a specified property. The non-uniform expressive power of mean GNNs is thus higher than that of GNNs with max aggregation, but lower than for sum aggregation--the latter are characterized by modal logic and graded modal logic, respectively. In the uniform setting, we show that the expressive power relative to MSO is exactly that of alternation-free modal logic, under the natural assumptions that combination functions are continuous and classification functions are thresholds. This implies that, relative to MSO and in the uniform setting, mean GNNs are strictly less expressive than sum GNNs and max GNNs. When any of the assumptions is dropped, the expressive power increases.