While the Weisfeiler-Leman (WL) test has successfully outlined what Graph Neural Networks (GNNs) cannot do—namely, distinguish certain non-isomorphic graphs—characterizing the exact class of functions they can learn has remained an open challenge. Existing theoretical frameworks often assume injective hash functions, yet real-world GNNs predominantly use non-injective ReLU activations.
This paper bridges this theory-practice gap by characterizing the functional space of ReLU Message Passing Neural Networks (MPNNs). Using the lens of tropical geometry, the authors prove that ReLU-based GNNs learn the exact same class of functions as standard feedforward networks, but with vastly different efficiency profiles depending on their aggregation strategies.
The Tropical Geometry Framework
To analyze ReLU networks, the authors appeal to tropical geometry, a branch of mathematics that replaces standard addition and multiplication with "max" and "plus" operations.
Through this framework, they establish a fundamental functional equivalence: ReLU MPNNs are equivalent to Tropical Rational Signomial Maps (TRSMs). Because TRSMs are already known to be equivalent to ReLU Feedforward Networks (FNNs), this proves that both architectures represent the same class of functions: Continuous Piecewise Linear Maps (CPLMs).
At a high level, a GNN is simply a specific way of structuring a piecewise linear function. Any function a ReLU GNN can learn, a ReLU FNN can also learn, and vice versa. The critical difference lies in their geometric complexity and efficiency.
Key Insights: Geometric Complexity and Aggregation
To measure the efficiency of these networks, the authors analyze their "geometric complexity"—the number of distinct linear regions a network can create in the input space. More regions generally imply a more flexible and expressive model.
- The Power of Max Aggregation: One of the most striking findings is that coordinate-wise max aggregation yields significantly higher geometric complexity than sum aggregation. In the tropical geometry framework,
maxallows the geometric complexity to grow exponentially with the graph's degree, whereassumis much more restrictive. This provides a rigorous theoretical justification for the empirical success of max-pooling in GNNs. - Connectivity Matters: The expressive budget of a GNN is directly tied to the graph's structure. Specifically, the complexity bounds are influenced by the maximum degree and the total number of edges in the graph.
- Decision Boundaries as Hypersurfaces: The authors characterize the decision boundaries of GNNs for node and graph classification as tropical hypersurfaces. These are the sets of points where two or more "tropical monomials" (the basic building blocks of these functions) reach a tie for the maximum value.
Architectural Trade-offs and New Bounds
The paper provides the first general upper and lower bounds on the number of linear regions for popular architectures like GraphSAGE and GIN.
By introducing four novel MPNN abstractions (Local, Global, Constant, and Hybrid) designed to represent any tropical signomial function, the authors establish clear architectural trade-offs:
- Layers vs. Parameters: MPNNs generally require fewer layers than FNNs to represent complex tropical functions (especially when using max aggregation). However, FNNs often require fewer total trainable parameters.
- Hybrid Efficiency: A proposed "Hybrid" architecture proves particularly efficient, requiring only one message-passing layer and one feedforward layer to represent any tropical signomial function with a highly optimized parameter count.
Limitations and Open Questions
Because this work is purely theoretical, it focuses on mathematical proofs rather than empirical benchmarks. This leaves several open questions for future research:
- Theoretical Assumptions: The upper bounds for geometric complexity rely on simplifying assumptions, such as input graphs having a fixed structure.
- The Optimization Gap: The paper characterizes what these networks can represent, but not necessarily what they will learn in practice. The role of optimization algorithms (like Adam or SGD) in navigating this complex geometric landscape remains unknown.
- Empirical Validation: It remains to be seen how theoretically efficient architectures, like the proposed Hybrid model, perform on noisy, real-world data.
- Spectral Properties: The authors note that it is still unknown whether spectral properties of the graph (such as the Laplacian spectrum) influence geometric complexity.
Summary updated