Research map / Graph learning / GNN architectures
What do Graph Neural Networks learn? Insights from Tropical Geometry
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses tropical geometry to show that ReLU message passing GNNs represent exactly the continuous piecewise linear maps of ReLU FNNs, derives general upper and lower bounds on their linear regions, and proposes new MPNN architectures with depth/parameter tradeoffs.
Problem
What class of functions do message passing GNNs with ReLU activations learn, and how do aggregation choice, depth, and parameter count affect their geometric complexity (number of linear regions) and decision boundaries?
Approach
Casts ReLU MPNNs as tropical rational signomial maps, showing equivalence with ReLU FNNs (CPLMs); derives recursive general upper and lower bounds on linear regions, shows coordinate-wise max aggregation yields greater complexity than sum, and introduces Local, Global, Constant and Hybrid MPNN constructions with tradeoffs.
Key results
- Proves ReLU MPNNs, ReLU FNNs, TRSMs and CPLMs represent the same function class (Proposition 1).
- Gives the first general upper and lower bounds on the number of linear regions of ReLU MPNNs, recovering FNN and GCN bounds and giving new bounds for GraphSAGE and GIN (Theorems 3-4, Corollaries 1-4).
- Shows coordinate-wise max aggregation can yield exponentially more linear regions than sum in the max degree S, N ~ S^{|V|d}, while sum gives one region (Proposition 5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use coordinate-wise max instead of sum for aggregation | ReLU MPNNs · Graphs with maximum degree S and total degree D | geometric complexity (linear regions): N(□(t)) = 1 if □(t) = P; Smin{|V |,D} ˜dt ≤ N(□(t)) ≤ min{∑i=0|D|dt+1 (S2|V | ˜dt i), S|V | ˜dt} if □(t) = max | Helped |
| Use message passing architectures rather than FNNs | Representation of arbitrary CPLMs · TSFs with r monomials in m variables | number of layers | Mixed |
| Use the Hybrid architecture to compute monomials with an FNN and compare them with an MPNN | Representation of any TSF · TSFs with r monomials in m variables | message layers: 1 | Helped |
| Use the Constant architecture | Representation of any TSF · TSFs with r monomials in m variables | feedforward layers: 7 | Helped |
Surprising findings
- Max aggregation is more expressive than sum in terms of geometric complexity, contrary to the WL-based ordering where injective sum is most expressive.
- Hybrid MPNN can represent any tropical signomial function with a single message layer and one feedforward layer, whereas FNN needs about log2(r) layers.
Limitations
- Upper bound assumes integer weights and a non-shrinking-dimension condition on layer widths.
- Purely theoretical; no empirical evaluation of the proposed architectures or bounds.
- Node and edge decision boundary analysis is more nuanced and given only as containment in tropical hypersurfaces.
Experimental setup
Metrics: number of linear regions (linear degree) upper and lower bou parameter and layer counts
Baselines: ReLU FNN GCN GraphSAGE GIN
Builds on: tropical geometry of ReLU networks (Zhang et al. 2018) Weisfeiler-Leman expressivity framework linear region bounds (Serra et al.) GCN GIN
Closest papers by meaning
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.91)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.90)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.90)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.89)
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.89)
- Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.