Abstract
This paper establishes a rigorous logical framework to characterize the expressive power of Graph Neural Networks (GNNs) employing mean aggregation. While mean aggregation is a staple in practical GNN implementations due to its scale-invariance and robustness to varying node degrees, its theoretical limits were previously less understood than those of sum or max aggregation. The authors demonstrate that mean-based GNNs correspond to specific fragments of modal logic. Notably, they show that while theoretically powerful, practical constraints such as continuity and threshold-based classification restrict Mean-GNNs to a simpler "alternation-free" logic.
Introduction: The Expressivity of Mean Aggregation
Graph Neural Networks (GNNs) typically operate via a message-passing paradigm where information from a node's neighborhood is aggregated to update its state. While sum aggregation (which counts neighbors) and max aggregation (which identifies extreme values) have been extensively studied, mean aggregation has remained a theoretical mystery despite its widespread use. Mean aggregation is particularly valuable in scenarios with high degree variance or when using neighborhood sampling. This research addresses the gap by identifying the exact logical languages equivalent to Mean-GNNs.
Methodology
The study employs tools from formal logic and model theory to characterize GNN architectures. The authors compare GNNs against various extensions of Modal Logic (ML) across two primary settings:
- Non-uniform: A setting where a different GNN can be defined for every possible graph size.
- Uniform: A more stringent setting where a single GNN must generalize across all possible graph structures.
To establish these equivalences, the authors utilize Ehrenfeucht-Fraïssé (EF) games, a technique used to determine if a logic can distinguish between two structures. They also introduce a "constrained" model ($Mean^{c,t}$) that incorporates continuous activation functions and threshold-based classification to better reflect real-world GNN implementations.
Key Theoretical Insights
The "Ratio" Logic of Mean
In the non-uniform setting, Mean-GNNs are shown to be equivalent to Ratio Modal Logic (RML). Unlike standard logic that checks for the existence of a property in the neighborhood, RML can express properties based on proportions (e.g., "at least 30% of neighbors satisfy property X").
The Continuity Gap and AFML
A significant finding is the "continuity gap." While Mean-GNNs can theoretically express standard Modal Logic (ML) in uniform settings, the mathematical proofs often rely on "unnatural" GNNs using non-continuous functions. When restricted to "well-behaved" continuous functions and simple thresholds ($Mean^{c,t}$), the expressive power drops to Alternation-Free Modal Logic (AFML). In AFML, one cannot easily nest existential ($\Diamond$) and universal ($\Box$) operators, suggesting that practical Mean-GNNs are less expressive than Sum-GNNs.
Scale Invariance
The authors formalize mean aggregation's unique property of scale invariance. Unlike Sum-GNNs, which change output if a graph is duplicated (scaled), Mean-GNNs produce identical feature vectors, reflecting their focus on distributions rather than counts.
Key Results
The research establishes a clear hierarchy of expressive power in the non-uniform setting: Max-GNN $\subsetneq$ Mean-GNN $\subsetneq$ Sum-GNN. The specific logical characterizations are summarized in the table below.
These results demonstrate that the choice of aggregation function fundamentally dictates the types of graph properties a network can learn. The equivalences hold for most common activation functions, including ReLU and Sigmoid.
Limitations and Future Directions
The authors identify several avenues for future research:
- Absolute Characterizations: Many uniform results are relative to Monadic Second-Order (MSO) logic; finding absolute characterizations remains an open problem.
- Activation Functions: Extending the proofs to cover all possible continuous non-polynomial activation functions.
- Complex Architectures: Applying these logical frameworks to more advanced layers, such as those found in Graph Transformers or higher-order GNNs.
Summary updated