What do Graph Neural Networks learn? Insights from Tropical Geometry
Authors: Tuan Anh Pham
Vikas Garg
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Representation Learning
Graph Neural Networks
Geometric Complexity
Message Passing
Learning Theory
Primary area: graph_neural_networks
TL;DR: We leverage tools from tropical geometry to establish several new results about ReLU MPNNs (including commonly used architectures).

Abstract: Graph neural networks (GNNs) have been analyzed from multiple perspectives, including the WL-hierarchy, which exposes limits on their expressivity to distinguish graphs. However, characterizing the class of functions that they learn has remained unresolved. We address this fundamental question for message passing GNNs under ReLU activations, i.e., the de-facto choice for most GNNs.

We first show that such GNNs learn tropical rational signomial maps or continuous piecewise linear functions, establishing an equivalence with feedforward networks (FNNs). We then elucidate the role of the choice of aggregation and update functions, and derive the first general upper and lower bounds on the geometric complexity (i.e., the number of linear regions), establishing new results for popular architectures such as GraphSAGE and GIN. We also introduce and theoretically analyze several new architectures to illuminate the relative merits of the feedforward and the message passing layers, and the tradeoffs involving depth and number of trainable parameters.  Finally, we also characterize the decision boundary for node and graph classification tasks.

What do Graph Neural Networks learn? Insights from Tropical Geometry
Tuan Anh Pham School of Mathematics University of Edinburgh Edinburgh, United Kingdom tuan. pham@ed. ac. uk
Vikas Garg Yai Ltd and Aalto University vgargocsail mit. edu
Abstract
Graph neural networks (GNNs) have been analyzed from multiple perspectives, including the WL-hierarchy, which exposes limits on their expressivity to distin- guish graphs. However, characterizing the class of functions that they learn has remained unresolved. We address this fundamental question for message passing GNNs under ReLU activations, i.c., the de-facto choice for most GNNs.
We first show that such GNNs learn tropical rational signomial maps or continuous piecewise linear functions, establishing an equivalence with feedforward networks (FNNs). We then elucidate the role of the choice of aggregation and update functions, and derive the first general upper and lower bounds on the geometric complexity (i.e., the number of linear regions). establishing new results popular architectures such as GraphSAGi and GIN. We also introduce and theoretically analyze several new architectures illuminate the relative merits of the feedforward and the message passing layers, and the tradeoffs involving depth and number of trainable parameters. Finally, we also characterize the decision boundary for node and graph classification tasks.
Introduction
Message passing has been cornerstone of machine learning, from inference in graphical models 5
2 to embedding of graphs 3 implement, and can handle large scale, heterogeneous, and dynamic real world data effectively; so continue to be active area of research 8
4
6
7 Message passing neural networks (MPNNs) are easy to
9
0 Indeed, several popular GNNs are usually cast [5].
and implemented as MPNNs, see e.g., 11
Unsurprisingly, GNNs MPNNs have been analyzed from multiple theoretical perspectives. A major theme is inspired by connections to the so-called 1-WL Deeisfeilrr-eeman test for group isomorphism and its higher order extensions, where nodes in a (hyper-)graph repeatedly refine their colors based on the messages from their neighbors [16]. MPNNs are known to be bounded in power according to the WL-hierarchy [55 17 18), implying their inability to distinguish some non-isomorphic graphs. Unlike WL that strives to expose what GNNs cannot do, here we seek to unravel what they can.
Notably, the WL formalism implicitly relies on injective hash functions; in contrast, successful GNNs typically use ReLU activations that violate injectivity. Bounding the expressivity of such GNNs via their injective surrogates is theoretically valid: however, does not illuminate what they learn. Indeed, several fundamental questions remain clusive for these practical models; e.g., (a) what class of functions can they represent, (b) how does their expressivity vary with the choice of message aggregation and update functions, (c) what complexity tradeoffs (e.g., in terms of the number of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Theoretical contributions of this work
Characterizing the class functions learned by ReLU MPNNs:
Equivalence with ReLU FNNs, TRSMs and CPLMs
Proposition
Estimating the number of linear regions, and complexity tradeoffs: First general lower bound for ReLU MPNNs
Theorem
3
First general upper bound for ReLU MPNNS
Theorem
Max aggregation has greater geometric complexity than sum
Proposition 5
Recovery of existing upper bounds for FNN and GCN
Corollary
New upper bounds for GraphSAGE and GIN
Corollary
New ReLU MPNNs and complexity tradeoffs:
New architectures that can all learn CPLMs, and their tradcoffs
Proposition
Characterizing the decision boundary:
Decision boundary of ReLU MPNNs for graph classification
Proposition Proposition g
Decision boundary of ReLU MPNNs for node classification
Figure I: Overview of our results. Formulating ReLU MPNNs as tropical geometric objects allows us to shed light several important aspects where WL falls short.
layers or parameters) exist for models of comparable expressivity, and (d) what decision boundary emerges for node and graph classification tasks?
We appeal to tropical algebra and geometry to address these questions the context ReLU MPNNs. Specifically, casting these networks as tropical geometric objects, we analyze their ability to represent different weighted sums of tropical monomials (the basic objects of interest in tropical algebra, akin monomials for standard polynomials) at different nodes. We first show that the family of functions represented by these networks is precisely the family of tropical rational signomial maps (TRSMs). Since TRSMs known to be equivalent to ReLU FNNs [19,, this reveals equivalence between ReLU MPNNs and ReLU FNNs: they represent exactly the same class functions, namely, continuous piecewise linear maps (CPLMs).
This equivalence terms of expressivity does not, however, translate into parity in efficiency, e.g., as quantified in terms of their respective requirements for the number of layers and trainable parameters to represent an arbitrary TRSM. Indeed, MPNNs have some strengths and limitations relative to FNNs. On the positive side, MPNNs benefit from parallel computation and streamlined communication between the nodes and their neighbors. On the flip side, MPNNs are constrained by permutation- equivariant layers that employ permutation- inneitiioniiniiinnt aggregation operators (20), which impedes their ability to represent arbitrary combinations of tropical monomials.
In order to better understand the efficiency of different MPNN architectures, we investigate their geometric complexity, the number of linear regions that they can distinguish. Towards that end, we establish the first general upper and lower bounds on the geometric complexity of ReLU MPNNs, recovering the existing results 19 21 FNNs and graph convolutional networks (GCNs) as special cases. Importantly, we also unravel new results for two of the most prominent MPNNs whose complexity was previously unknown, namely, GraphSAGE [13] and GIN [15].
A particularly attractive aspect of our bounds is manifested in segregation of the contribution from different components, such aggregation and update steps. In particular, they reveal that selecting coordinate- wise max as the aggregation operator affords greater geometric complexity than sum for ReLU MPNNs. order provide further insights about various complexity tradeoffs, we introduce and analyze four novel MPNN abstractions. Notably, they can all represent arbitrary TRSMs, i.e., they are as expressive as ReLU FNNs, but differ in terms of layers as well as total learnable parameters in their corresponding architectures. Fundamentally, we expose a general trend about the relative merits of the feedforward and message passing paradigms: fewer layers for MPNNs (particularly with coordinate- worde max aggregation) but fewer trainable parameters for FNNs.

---

Finally, we study the decision boundaries for node and graph classification, uncovering the underlying connections with tropical hypersufaces; i.e, the set points where two or more tropical monomials achieve the same value.
We summarize our key contributions in Figure
We now proceed to reviewing some related works.
1.1 Related work
Tropical Geometry and Machine Learning. Tropical geometry 22 23 provides tools to study the algebraic geometry and combinatories of continuous piecewise linear functions, and finds several applications (e.g., in optimization). Two seminal works [19] (24) initiated the analysis of deep learning models via tropical geometry, establishing the link between ReLU FNNs and tropical rational functions. The connection was then extended to maxout-layers in 22 The decision boundaries of FNNS through tropical lens were studied in (6).. Other aspects of deep neural networks have also be analyzed [27 (28] 29 30 32
We refer to 33 for survey on the current use of tropical
geometry in deep learning.
Expressivity and WT.. Much work on GNNs has been inspired by noticing the parallels between
MPNNs and the WL test for isomorphism 13 34 35.. Standard MPNNs no more powerful than
1-WL (equivalently, 2WL.), so higher order models that consider tuples of vertices have been proposed
17 18
Several adaptations of WL such geometric WL [36,, cellular WL [37].remporal WL (10),
and persistent WL (38) have been introduced in different contexts. Limited expressivity and symmetry
considerations have led the design of new MPNN architectures [5
39
42
43 inclusion
of different types of features [39 441. and integration with topological descriptors
45
46
47
Other notions of expressivity have also been proposed, e.g., equivariant polynomials
48 and
homomorphism counts [49].
Other results about GNNs. GNNs as MPNNs are also known be prone to information bottle- necks [50] 51 [52]
oversmoothing and oversquashing [53] and heterophily [54] [55]. Some works
have also established their inability count substructures, compute graph properties, or learn topol-
ogy [49 56 57]: connections to algebraic topology [58]. biconnectivity (59), and communication
complexity 660 61], behavior in overparametrized regimes 62 63]; power of recursion in counting
substructures [64] benefits of positional encoding 65 and ability to generalize and achieve universal
approximation 56
69 70
However, neither expressivity in terms of WI. nor these other results characterize the class of functions learned by GNNs, and in this work we bridge this glaring gap for ReLU MPNNs.
Complexity of Neural Networks. The complexity of deep neural networks is typically studied in 77
terms of the number of linear regions [76]
78 79]. and the intricacy of decision boundary [19],
though other notions such as trajectory length [0 have also been considered recently. The number
of linear regions quantifies the flexibility of the function class, thus bounding the number of regions
relates closely to both expressivity and generalization (79). To our knowledge. only the geometric complexity upper bounds for GCNs are known in the context of GNNs [21]. We provide the first general lower and upper bounds for ReLU MPNNs, establishing complexity of popular architectures such as GraphSage and GIN, and recovering the results for GCNs and FNNs as special cases.
2 Preliminaries
2.1 Message Passing Neural Networks (MPNNs)
general T-layer MPNN x is defined as sequence of layers (v TT and takes as input a (directed) graph G (V. E, X) with vertices v E V. edges (u, v) E E C V x V, and features X (Xv, Xg) consisting of node attributes Xv dlo and edge attributes Xg E [ It produces as output a refined embedding for each vertex and edge. Formally, X acts on X as
x(X) = (2) o (00 where each (0)) I V x R Eixd'_ + R Vixde x E xd.
permutation-equivariin 20 Subsequently, depending on the task, the embedding for each node produced by x is fed into another neural network, e.g., 77 dd - goot for node classification or
3

---

regression (and similarly for edges), An additional readout step Reeaouut RR V x xR F|xd' - Rd usually required obtain a single vector from the output of X for graph-level prediction.
thus proceed to describing the working each layer up(t) that yields a representation A, Rd
for each vertex u E V and representation (0) E Rd for each edge (u, E E. Assuming node embeddings are updated before edge embeddings (the converse works analogously). have
h = Updane (h m!!); where
(f)
(0) (t)
( Page (h ((h eell Giu e/ Ne(u))))
Aggregation functions {y (t)
Agg are typically permutation- ionpuaaatiionnnnaannl,,, and we use an operator D such as sum, average, or coordinate-wil wise max/min to combine the messages
15 81
+ (nt (h+-1), ((1 "e
"e " ((t-1))) ( 11 (O (9) uENe(a)
P2 10
(n 1 (tt ())
Con
where {0)0} and (0z ( are usually implemented as FNNs, Ne(u) denotes the set of neighboring vertices of v, and }f-}} denotes a multiset. When there no confusion, we usually write ( instead.
Let ( and T.50) denote, respectively, the number of layers in of and p!!² We use ni (and m²/"
to denote the dimension of layer l (1 (and ( On the other hand, the update functions take the form
(1) Updaaee (h pm
Update (W (t-1) + w-(1)
(c)
neigh m
Henceforth, we focus on sum and coordinate wise max, since coordinate wise min and average can be obtained from coordinate-man and sum respectively. We shall also number the vertices in with A1,... AlvI and edges in E with e1, -..,. EE and use the lexical order for edges, i.e.,
Euv < Eurv + u u' or (u = and v < t').
2.2 Tropical Algebra
Here we adopt the notation from 19 Let T [- be an extended set of real numbers. We equip with two binary operators tropical sum and tropical multiplication @::
a + b = (a, b): a -a b
00 - 20 a a= m0=a;; a; a -00
-oc
where max and + are the usual operators in R. Thus, (T, @, is semi-ring with additive identity -oo and multiplicative identity 0. We also define the tropical power 000 for each r R:
r r 1 Ox= i (-z) (1x))(-a)
fo i (0) {0
-00
ifae
af
where is the standard product over R, and often abbreviate 00 to R without inducing any confusion. tropical monomial in m variables takes the form e x/ @... ④ Gr for e E T and (1,, ..., am E N. and is often denoted by multi-index shorthand cr", where = (aj...., am)) E 7 and a (ZI,..., Fm E Imm Note that this may be interpreted as the affine combination x +
A tropical polynomial f() c + c, is finite tropical sum of tropical monomials, and amounts to a max over finitely many terms, i.e., (xx max far a; + c.). Without loss of generality, we assume a; 전 a, for # since we can combine monomials with the same a into one. A tropical rational function f g(x) f(x) g(x) is the difference between two tropical polynomials. A map ; R + Rº with each component a tropical polynomial [resp. tropical rational function] is called tropical polynomial map [resp. tropical rational map], and belongs to the set (ol(m,,)) p) [resp. (m)
When we allow a; E R. instead of restricting its components to integers (a; E Z we obtain a tropical signomial function/map [resp. tropical rational signomial function/mapi instead of tropical polynomial/map [resp. tropical rational function/map). It is known that each tropical rational signomial map (TRSM) is continuous piecewise linear map (CPLM) and vice versa [1].

---

3 Tropical Algebra of MPNNS
In this section, characterize the class of functions learned by ReLU MPNNs, whose activation functions for both nodes and edges (i.e., those used for v,, Φ1 (1) Updiee etc.) are of the form:
σ (x) max (1. 1 where (0)) (IR U -
In particular, note that of (0) - x when ( = -c., In contrast, ( = 0 purges all negative inputs.
Let FRR. MPNN, R FNN, FCPLM, FRSM be the set of functions represented by all ReLU MPNNs, ReLU FNNS, CPLMs and TRSMs respectively. [19] established the equivalence of ReLU FNNs, CPLMs and TRSMs.
Lemma
(19). FRE.U FNN = FCPIM = FIRSM
We will now extend this result to establish equivalence with F MPNN. Equating ReLU MPNNs with CPLMs is rather nuanced, since nodes in each layer share the weights. Therefore, we employ two reductions showing (1) every ReLU FNN can be cast as a ReLU MPNN, and (2) every ReLU MPNN, in turn, can be expressed as TRSM.
Proposition 1. /Equivalence of ReLU MPNNs, ReLU FNNs, TRSMs and CPLMS] F = FREWU FNN FCPLM FIRSM- In other words, the following families are equivalent (with m [Vld + EE|d and p = [V|dowr |E)ddaa).
1. ReLU MPNNs X RIVixd RRll + R Vi x RIEE m;;
2. Tropical rational signomial maps (TRSMs) F
2
G R RP
3. Continuous piecewise linear maps (CPLMs) &
R -T
4. ReLU FNNs II m I.
Remark 1. In contrast to the WL test, which exposes the limitations of MPNNs via injective hash functions. Proposition 7 characterizes the class of functions that can be represented by MPNNs with ReLU activations (that are non-injective). Note, however, that Proposition [1 does not quantify how effective ReLU MPNNs are in representing CPLMs. Moreover, the equivalence between ReLU MPNNs and ReLU FNNs (according to Proposition T does not explain the observed empirical discrepancy between ReLU MPNNs and ReLU FNNs in practice. This motivates our subsequent analysis and results (Section 3 Jnd Table 7. which investigate the benefits of ReLU MPNNs in terms of both the number of learnable parameters and the number of layers required to represent the same CPLM.
4 Geometric Complexity of ReLU MPNNs
We now invoke tools from tropical algebraic geometry to study the geometric complexity of ReLU MPNNs, and provide some insights into the model architecture. Following [19], for CPLM RR,, we define its linear degree (f) to be K, where K is the least number connected regions S4 of 1 such that the restriction fla, is affine. Equivalently, following [82]. can also
f: R +
define K = (f))) as follows: f: 1m + R" is a CPLM f continuous and there exists a set (f++ l (1, K}) of affine functions and maximal connected subsets (S4 ) satisfying the
following conditions:
K
24 n., = 0;
L = Rm; fla, ft-
Similarly, we define the convex degree Nf) where we require additionally that Q2 is convex. We further define Ne(f Wm' as the maximum convex degree across restrictions of f to different m' d--imensiionl affine subspaces of R m' < m. We will analyze general upper and lower bounds on N(x) for ReLU MPNN x. Recall our setting of MPNN layers from Section 2.1 consisting of
d Ags Update Note that ni 1. and ni denote the intermediate dimensions in Ø and @ Let de
(t) and (2)
and d, be the output dimension of o and Φ1 thus n2. t.
d,-
To analyze the number of linear region for ReLU MPNN x. make simplifying assumption that all input graphs to x have the same graph structure G. particular, we denote the sum of degrees
of all vertices in G by D, and the maximum degree by S. A key step in our analysis of geometric
5

---

complexity is building a ReLU FNN that can be applied on the vectorized imput (tt of all node embeddings - (2-1), Using the notation indicated Equation we form a ReLU FNN 4.2 that achieves the same effect as 02 for every adjacent node embedding. The aggregation operator can be seen as either a matrix multiplication for sum, or a FNN 2 for max aggregation the difference between these two cases will be discussed in Section 4.3 Similarly, we form a ReLU FNN 4/" for (1), which in combination with ( and ( can be seen ReLU FNN (1() "ggg"
Our next proposition is important in the analysis for geometric complexity of X. it relates the geometric complexity of the model up to the t + 1-th layer to that of the t-th th layer, and the update as well as the message components. We define the vectorized concatenated embedding of all the vertices in the t-th layer to be ((() E IR Vid, and show that the result of t-th message aggregation step be written result of a FNN D Aggg (H) Modifying any aggregation or update component thus will affect the bound and in particular, the choice of aggregation operator has an impact on the geometric complexity (which we will discuss in Section
Proposition 2. [Recursive formula for geometric complexity]
(( S (N(( S WellPupaaee [V + de41)) N (1+ [[V
(2)
Agg
The ideas and proof' for Proposition 2 build on 19 and the details can be found in the Appendix.
4.1 Lower bound of geometric complexity
We note that the lower bound on the linear degree of x depends heavily on the choice of weights and biases; e.g., setting their value to 0 trivially results in A((x) 0. Thus, lower bound on the geometric complexity (i.e., maximal linear degree) is of greater interest. this subsection, we will provide general lower bound for the maximum number of linear regions for ReLU MPNN, building on the work of (76).
Theorem 3. [Lower bound the maximum number of linear regions] Assume for all t, we have A. 2 do and let t.l di
t.1 do then the maximum number of linear regions of functions computed by any ReLU MPNN lower bounded by
= =1 do
da and d22,da =
01 .12
%
[TE
[
1.1
(0) I
1.1 (22,
1,,o
do
dr
Sta
T
11,do
1=0
where to is the number of MPNN layer having max as aggregation operator and for each layer t, the index I runs through every layer in (1)
.1
We now sketch some intuition about this result. We can add to " (constructed in Algorithm in the Appendix) an initial layer calculate (+) = E. while the aggregation
(+) max can be seen as a FNN-layer with rank S max activation, thus we can identify S input regions (indicated in express the whole MPNN x as a FNN applied to input X (details in Algorithm 2 and in the Supplementary). We build on the analysis in +.1 do input regions. Our procedure amounts to sequentially folding the input space until the last layer (indicated in blue), and then replicating the
red). By setting PUpdate ! (t-1) m² mp.
(1)
76 to construct intermediate layers that identify
hyperplane arrangement in the last layer (indicated in green).
4.2
Geometric complexity Aggregation and Update steps
We now provide a general upper bound for the geometric complexity of ReLU MPNNs when all the weights take integer values this assumption is mild and holds without loss of generality (details in the Appendix). We call these models anteger-weighted ReLU MPNNs. A result similar to Proposition T esttalishhs the equivalence of integer-weight ReLU MPNNs with tropical rational maps.
For our analysis, we require a technical condition that the network "does not shrink" the representation
f.! f.' in the following sense: each intermediate dimension n2 and n2 of ( and ( should be sufficiently

---

large; and the dimension of the new embedding is at least the dimension of the aggregated message plus the dimension of the previous embedding. These conditions are standard in the analysis using tropical geometry, see e.g., [9].
Theorem 4. [Upper bound on the geometric complexity] Let x RIV do - R be an integer- weight ReLU MPNN. If (p(t satisfies the following conditions for all MPNN layer t L,..." ...
n2 1.1 2 P di for all ..., L
1. 2 for all = 1,.,, _,;
(.1 d de;
11
then the linear degree of H is at most
T
(0)
[Vid
t.!
[.2
[Vix
Dn
vi(d+tdi-1)
Vidde
Σ
II
Σ
Σ 1=0
No(D((),
i
i
i
1=0
from ((
from 42
(t) from & Pipaace
f is sum, (8S)
where (o() <
if (t) is coordinate-wiss max/min
We emphasize that, to the best of our knowledge, this the first upper bound for general ReLU message passing architectures. Furthermore, we recover the upper bounds for FNNs and GCNs (with ReLU activations and integer-weight established in [19 and 21 respectively as special cases.
Corollary 1. The linear degree of an integer-weight FNN is at most IT= (E (1))
Corollary The linear degree of a GCN X with hidden layers, ReLU activation, sum aggregation (Vid
and integer weight is most I Ei (V)())).
On the other hand, we obtain new bounds for popular GNN models, particularly GraphSAGE and GIN For GraphSAGE, note that the normalization steps do not change the linear degree.
Corollary 3. Let de be the output dimension of Aggregate, in GraphSAGE []3]. If 2 di- I + de > 2d.-1 for all MPNN layers ..., T, then the linear degree of integer-weighted ReLU GraphSAGE described in [13] is upper bounded by Vclx")...NNcle))
where
2/dd (1V)d) En= DIVE (Did))
if the aggregation step is mean,
Nc(p')
(D IVId++ 1) (vaa))
if the aggregation step is pooling.
Corollary 4. Node embedding of weighte ReLU GIN can be written as (15] Equation 4.1). Let n be the dimension of each of the intermediate layer in the M ML then its linear degree
T
(1)0) -1 IV
(IV Ine..t
)
N.(x) S II
II
Σ 1=0
i
4.3 Coordinate-wise max vs. sum for aggregation
Proposition 5. (Coordinate-wiss max has greater geometric complexity than sum]
((((9)) =1 (O S min
if ( Σ. T max.
gmiin <
(Dld++ 1
(²Vvar), s
To establish Proposition 5 we again adapt (76). Note that if D > [V| (the graph is not too sparse, and we have enough messages between the vertices), we have that ((()) = glvid if (()) max. In that case, the geometric complexity will grow polynomially with S (maximum degree).
7

---

Remark 2. Interestingly, in (15V, the authors point out that if Φ1 and Φ2 are injective, then is as powerful as the WL test. Under that assumption, coordinate-wiss less "expressive" than mean, which is less "expressive" than sum.
In contrast, du and dhe are injective in our case (since ReLU activation is injective), max is more "expressive" (as measured by the notion of geometric complexity), thus providing another novel insight. Here, the connectivity of the graph plays a particularly important role.
5 New ReLU MPNNs architectures and complexity tradeoffs
Note that while both ReLU FNNs and ReLU MPNNs learn TRSMs/CPLMs (Proposition I they might differ vastly in terms of their resource requirements (e.g., the number of layers and parameters). Therefore, we proceed to comparing the complexity of representing TRSM under the two paradigms (we do not need integer-weight assumption in this section). We simplify our analysis by noting that each component of TRSM results from the difference of two tropical signomial functions (TSFs) and these TSFs can be computed in parallel using shared layers. Thus, hereafter, we shall focus TSFs, i.e., functions f Rm >
of the form f(x) 1 c @ x where & E &,, E R"
Our idea is to construct as imput clique (i..., conneccd graph) with m nodes Ai...., Am and distribute the r monomials (almost) evenly such that each node A, contains r' - monomials (padding with zero monomials if r' r). Our construction makes use of a comparison gadget which is already introduced in [19] and [3 and introduces novel selection gadget (details in the Appendix) which proves to be useful with the permutation equivariance restriction of MPNNS.
The two MPNNs below differ in terms of the way they compare the monomials.
Compare m monomials, one from each A,, simultancously using coordinate- wise max aggregation. Now redistribute (using the selection gadget) the resulting O maximum monomials (each coordinate yields one such monomial) evenly across the nodes, and recur until the maximum across all monomials obtained.
Global comparison:
First employ a recursive procedure to compare r' monomials assigned to each A; locally in order to find maximum monomial for A, (breaking ties arbitrarily). Now compare the maximum monomials across the nodes using a single global comparison described above.
Local comparison:
One limitation of both these architectures is that they can make no more than m comparisons at time but r can be much larger. Fortunately, a theorem due to [84,, also exploited previously by [83], motivates construction of Constant MPNN consisting only constant number of layers to represent any TSF. However, the number of learnable parameters in this MPNN can be exponential in the worst case.
Remark 3 (Nature of MPNN and FNN), Without the equivariance constraint on the message component of MPNN, FNN is much more efficient at constructing affine combinations or tropical monomials. On the other hand, thanks to the parallel MP paradigm of MPNN, it is more effective at comparing these monomials, or in other words, increases the geometric complexity of the model. This benefit of MPNN can be seen in Theorem 4 where one has to build much bigger Tb()) and & to reconstruct the result of the parallel (1) and @2
We therefore proceed to our final algorithm that combines the strengths of these two paradigms. Hybrid MPNN: We first use a layer of FNN to calculate tropical monomials and then employ single layer of MPNN over an r-clique with coordinate-max to learn
Proposition 6. There exist ReLU MPNN algorithms (Local, Global, Constant, and Hybrid that can learn any TSF f 1 - R with monomials. Their respective complexity and tradeoffs are summarized in Table
We provide details about these algorithms and proofs of their correctness as well as complexity in the Supplementary. Local architecture: Algorithm 6 and Proposition T6. Global architecture: Algorithm 7 and Proposition 17 architeette,,, Constant architecture: Algorithm and Proposition [8]
Hybrid architecture: Algorithm and Proposition 19

---

Previously
Message layers Feedforward layers
Learnable parameters
Deep NN in [9
None None
loga
+
(rm
Deep NN in
83
log2 m
+1
((rm)
New (in this work)
Local (Algorithm
2
logg (r/
+5
Orm
Global (Algorithm
log,
+1
glogm (r)
+2
O(rm)
Constant (Algorithm
2
O (mr
Hybrid (Algorithm
((rm)
Table Complexity of representing any tropical signomial function (TSFs) f R E consisting of r tropical monomials with different architectures. One more layer is required compute any
tropical rational signomial map (TRSM). The four new methods introduced here construct graph
(based on m and r) and leverage message passing efficiently compare these monomials.
Decision boundary
Lastly, we proceed to characterizing the decision boundary of integer-weighted ReLU MPNNs for classification. We focus on binary classification tasks with single output keep the exposition transparent and explicit, albeit one can adapt our construction and analysis accordingly to accommo- date multiple classes and outputs. We analyze the decision boundary for both graph and node/edge predictions.
We begin with the analysis for graph classification. Recall from Section that need an additional readout step Preadout RV
IR xdr
Rdo prior to classification 17. i.c.
X dV
Rdd | 10 Do.....
dVV
(Poaaii pdd 34 R.
Let IR - TR be an injective score function. For IR. in Im( we define the decision boundary of x as B = {z E R x(2) 7 }c) where m dBV | + d' EE). The tropical hypersurface T(f) precisely the set of points x where is not linear; i.e., two or more monomials in f achieve the value of f at æ. We adapt result from 19 Proposition 6.1] to arrive at the following proposition.
Proposition 7 (Decision boundary for graph classification). Let X [Rd x 1 x| + R be ReLU MPNN and 7 I + be an injective score function with in range. Then X can be viewed as a tropical rational function, f @ g and the decision boundary B defined above divides TM into at most (f) connected positive regions and at most N(9) connected negative regions. Furthermore, B is contained in the tropical hypersurface of specific tropical polynomial, namely.
B C (c) O
However, the characterization for node and edge classification requires a more nuanced analysis. We focus on node classification, since the treatment for edges is analogous. In this setting the neural network v Rd -> R is applied to the embedding of each node simultaneously, and a scoring function % TR R is then employed for each node to predict its class based its score c-- Generally, different scoring functions 7/ may be applied, but in practice, we often use the same score function for all the nodes. Viewed individually, the decision boundary for each vertex is similar to Proposition 7 so we pursue a more interesting problem, namely, characterizing the decision boundary of the vertices resulting from a vectorized score function I' R + RIV [[())], = (2).. However, immediately hit roadblock, since choosing a meaningful order for e; problematic: the product or subset order is not total whereas the lexical order relies heavily on the ordering of the vertices and thus violates permutation equivariance of the MPNN paradigm. Therefore, we introduce the following notion for the decision boundary.
Definition 1. The decision boundary B is defined as U Bi, where B: {z E R vz(2)= y, (c)).
In order to proceed, we need to generalize the analysis to tropical hypersurfaces. Specifically, we relate B with the tropical hypersurface of the components of the corresponding tropical rational map. Invoking Proposition 6.1 in [19) we establish the following proposition.
Proposition 8 (Decision boundary for node classification). Let x RdxIVI x Rdd x - R be
ReLU MPNN and x IR + R, i 1,2, [V] be injective score functions with c; in their range.

---

Then can be viewed as tropical rational map F @ G and its decision boundary is contained in the tropical hypersurface of a specific tropical polynomial, namely,
v C T(
Conclusion, Broader Impact, and Limitations
In this paper, we characterize the class of functions learned by ReLU MPNNs through the lens of Tropical geometry. Thus, beyond previous works that are limited to utilizing tropical geometry the context of ReLU FNNs, our analysis expands the scope to a widely employed class of GNNs, laying groundwork for further work on the connections with other machine learning models.
We provide both the lower and upper bounds for the number of linear regions of ReLU MPNNs. The upper bound makes some simplifying assumptions; however, Theorem 4 is still general enough to recover existing bounds for FNNs, GCNs, and provide new bounds for widely used GNN architectures such as GraphSAGE and GIN. Our bound rather analytical: numerical approach to counting the number of linear regions can be found in 85]. Adapting the method in [85] for MPNNs, and comparing to our analytical bounds, is an interesting future direction.
We also show that the max aggregation operator is more expressive than the sum operator in terms of geometric complexity of ReLUU MPNNs (see Remark on how this result contrasts with the implications of the WL test for injective aggregation functions). We thus showcase the dependence of expressivity on message aggregation operator, and furthermore, the connectivity of the graph structure (max and total degree). It remains open whether spectral quantities such as the spectrum of Laplacian have any effect on the geoemetric complexity of ReLU MPNNs.
The theoretical result on equivalence of class of functions learned by ReLU MPNNS and ReLU FNNs is usually not reflected in practice, where ReLU MPNNs typically outperform FNNs. This motivates our results in Section 5, where we consider several ReLU MPNN architectures to represent CPLMs and compare them ReLU FNNs. Remark 3 Proposition 6 and Table that ReLU MPNNs can be more efficient in terms of both the number of learnable parameters as well as the number of layers required in order be able represent the same CPLMs. We however, sidestepped other important and practical considerations such as the difference in training time, prediction eπrоr and the role of optimisation algorithm (c.g. SGD/Adam). Our focus here has been purely theoretical, and we believe that (at least some of) proposed new architectures would benefit from a comprehensive empirical evaluation. We also characterize the decision boundary for graph classification and node classification, explaining the difference between the two.
Overall, we hope that this work fosters further research design and analysis of modern deep architectures through the fruitful machinery of tropical geometry.
Acknowledgments
VG acknowledges support from the Research Council of Finland for the project "Human-steered next-generation machine learning for reviving drug design" (grant decision 342077), the Jane and Aatos Erkko Foundation for the project "Biodesign: Use of artificial intelligence in enzyme design for synthetic biology" (grant 7001703), and a Saab-WAr initiative (grant 411025). TAP wants to thank Johanna Immonen, Jannis Halbey, Negar Soltan Mohammadi, Yunseon (Sunnie) Lee, Bruce Nguyen and Nahal Mirzaie for their discussion, support and wonderful experience during his research internship at Aalto University in 2022.
References
[1] Judea Pearl. Reverend bayes on inference engines: A distributed hierarchical approach. In AAAI, pages 133-136, 1982.
[2] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. Adaptive computation and machine learning. MIT Press, 2009.
10

---

[3] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference on Neural Networks (LJCNN), 2005.
[4] Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009.
[5] Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICML' 16, page 2702-2711. JMLR.org, 2016.
[6] Z. Zhang, F. Wu, and W. S. Lee. Factor graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[7] Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
[8] E. Rossi, B. Chamberlain, Frasca, D. Eynard, E. Monti, and M. Bronstein. Temporal graph networks for deep learning dynamic graphs. In ICML 2020 Workshop on Graph Representation Learning, 2020.
[9] Y. Wang, Y. Chang, Y. Liu, J. Leskovec, and P. Li. Inductive representation learning in temporal networks via causal anonymous walks. In International Conference on Learning Representations (ICLR), 2021.
[10] Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg, Provably expressive temporal graph networks. Neural Information Processing Systems (NeurIPS), 2022.
[11] Gilmer, S. S. Schoenholz. Riley, O. Vinyals, and Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
[12] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR), 2017.
[13] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[14] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph Attention Networks. In International Conference on Learning Representations (ICLR), 2018.
[15] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2019.
[16] B. Weisfeiler and A. A. Leman. A reduction of graph canonical form and algebra arising during this reduction. Suuchhno-Teccmiicheskayy Informatsia, 2(9):12-16, 1968.
[17] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence (AAAT), 2019.
[18) H. Maron, H. Han-H H. Serviansky, and Y. Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[19] Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks. In Jennifer G. Dy and Andreas Krause, editors, International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 5819-5827. PMLR. 2018.
[20] Stefanie Jegelka. Theory of graph neural networks: Representation and learning, 2022.
[21] Hao Chen, Yu Guang Wang, and Huan Xiong. Lower and upper bounds for numbers of linear regions of graph convolutional networks, 2022.
[22] D. Maclagan and Sturmfels. Introduction to Tropical Geometry. Graduate Studies in Mathematics. American Mathematical Society, 2015.

---

[23] M. Joswig, Essentials of Tropical Combinatorics. Graduate Studies in Mathematics, American Mathematical Society, 2021.
[24] Vasileios Charisopoulos and Petros Maragos. A tropical approach to neural networks with piecewise linear activations. ArXiv, abs/1805.08749, 2018.
[25] Guido Montúfar, Yue Ren, and Leon Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. SIAM Journal on Applied Algebra and Geometry, 6(4):618-649, 2022.
[26] Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem. On the decision boundaries of neural networks: tropical geometry perspective. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):5027-500 507-577777777 2023.
[27] Georgios Smyrnis and Petros Maragos. Tropical polynomial division and neural networks, 2019.
[28] Marie-Charlotte Brandenburg, Georg Loho, and Guido Montúfar. The real tropical geometry of neural networks, 2024.
[29] Matthew Trager, Kathlén Kohn, and Joan Bruna. Pure and spurious critical points: a geometric study of linear networks, 2020.
[30] Dhagash Mchta, Tianran Chen, Tingting Tang, and Jonathan D. Hauenstein. The loss surface of deep linear networks viewed through the algebraic geometry lens. IEEE Transactions Puttern Analysis and Machine Intelligence, 44(9):5664-568) 2022.
[31] J. Elisenda Grigsby and Kathryn Lindsey. On transversality of bent hyperplane arangeeents and the topological expressiveness of relu neural networks. SIAM Journal on Applied Algebra and Geometry, 6(2):216 242, 2022.
[32] Francis Williams, Matthew Trager, Daniele Panozzo, Cláudio T. Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc, Edward A. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 8376-8385, 2019.
[33] Petros Maragos, Vasileios Charisopoulos, and Emmanouil Theodosis. Tropical geometry and machine learning. Proceedings of the IEEE, 109(5):72--75, 2021.
[34] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: the story so far. J. Mach. Learn. Res., 24(1), mar 2024.
[35] Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for GNN expressiveness. In The Twelfth International Conference on Learning Representations, 2024.
[36] Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, and Pictro Liò. On the expressive power of geometric graph neural networks. In International Conference on Machine Learning, 2023.
[37] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Liò, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 2625-2640. Curran Associates, Inc., 2021.
[38] B. Rieck, C. Bock, and K. Borgwardt. A persistent weisfeiler-lehman procedure for graph classification. In International Conference Machine Learning (ICML), 2019.
[39] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. ICML., 2022.
12

---

[40] Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemnet: Universal direc- tional graph neural networks for molecules. In M. Ranzato, A. Beygelzimer, Y. Dauphin. P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 6790-6802. Curran Associates, Inc., 2021.
[41] Yi Liu, Limei Wang, Meng Liu, Yuchao Lin, Xuan Zhang, Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3d molecular graphs. In International Conference on Learning Representations, 2022.
[42] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference Learning Representations, 2022.
[43] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[44] R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In SIAM International Conference Data Mining (SDM), 2021.
[45] M. Carrière, F. Chazal, Y. Ike, Lacombe, M. Royer, and Y. Umeda. PersLay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[46] Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning on graphs. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 27029-27042. Curran Associates, Inc., 2021.
[47] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In International Conference on Learning Representations, 2022.
[48] Omri Puny, Derek Lim, Bobak T. Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. 23. JMLR.org, 2023.
[49] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? In Advances Neural Information Processing Systems (NeurIPS), 2020.
[50] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
[51] D. Kreuzer, D. Beaini, W. L. Hamilton, V. Letourneau, and Tossou. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[52] Ben Chamberlain, James Rowbottom. Maria Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1407-1418. PMLR, 18-24 Jul 2021.
[53] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
[54] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022.
[55] Yuelin Wang, Kai Yi, Xinliang Liu, Yu Guang Wang, and Shi Jin. ACMP: allen-cahn message passing with attractive and repulsive forces for graph neural networks. In The Eleventh Interna- tional Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.ne., 2023.
13

---

[56] V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), 2020.
[57] Nima Dehmamy, Albert-Laszlo Barabasi, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[58] Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Lio, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[59] Bohang Zhang, Shengjie Luo, Liwei Wang. and Di Hc. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023.
[60] A. Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations (ICLR), 2020.
[61] A. Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[62] S. S. Du, K. Hou, R. Salakhutdinov, kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
B. Póezos, R. Wang, and K. Xu. Graph neural tangent
[63] Sanjukta Krishnagopal and Luana Ruiz. Graph neural tangent kernel: Convergence on large graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 17827-17841. PMLR, 2023.
[64] Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The power of recursion in graph neural networks for counting substructures. In Francisco Ruiz, Jennifer Dy, and Jan-Willen Willem van de Meent, editors, Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 11023-11042. PMLR, 25-27 Apr 2023.
[65] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022.
[66] S. Verma and Z.-L. Zhang. Stability and generalization of graph convolutional neural networks. In International Conference on Knowledge Discovery & Data Mining (KDD), 2019.
[67] R. Liao, R. Urtasun, and R. Zemel. A PAC-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
[68] K. Xu, J. Li, M. Zhang, S. S. Du, K.-I. Kawarabayashi, and S. Jegelka. What can neural networks reason about? International Conference on Learning Representations (ICLR), 2020.
[69] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[70] Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances Neural Information Processing Systems, volume 34, pages 27043-27056. Curran Associates, Inc., 2021.
14

---

[71] Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang R Zhang. Generalization in graph neural networks: Improved pac-bayesian bounds on graph diffusion, Artificial Intelligence and Statistics, 2023.
[72] Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. OOD link prediction generalization capabili- ties of mhessage-psssnng GNNs in larger test graphs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[73] K. Xu, M. Zhang, J. S. S. Du, K.-I. Kawarabayashi, and S. Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
[74] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In Marina Meila and Tong Zhang, editors, International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 837-851. PMLR, 2021.
[75] Andrew Dudzik and Petar Veličković. Graph neural networks are dynamic programmers. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
[76] Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Z.. Ghahramani, M. Welling. C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[77] Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2596-2604. PMLR, 2019.
[78] Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 10514-10523, PMLR, 2020.
[79] Itay Safran, Gal Vardi, and Jason D. Lee. On the effective number of linear regions in shallow univariate reLU networks: Convergence guarantees and implicit bias. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[80] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. Doina Precup and Yee Whye Teh, editors, Pro- ceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2847-2854. PMLR, 06-11 Aug 2017.
[81] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[82] Alexis Goujon, Arian Etemadi, and Michael Unser. On the number of regions of piecewise linear neural networks. Journal of Computational and Applied Mathematics, 441:1 156677, 2024.
[83] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Represen- tations, 2018
[84] Shuning Wang and Xusheng Sun. Generalization of hinging hyperplanes. IEEE Transactions on Information Theory, 51:4425-4431, 12 2005.
[85] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1558-45666 PMLR, 10-15 Jul 2018.
15

---

Technical Appendix Supplementary Material
We now describe in detail all the algorithms introduced in the main paper, as well as proofs for all results. We begin with the results from the section Tropical algebra.
Tropical algebra
Lemma 2. Every ReLU FNN V. R + IP can be represented by a ReLU MPNN X :R Rx R
Proof. This is obvious when we set G to be a one-clique (i.e., one vertex graph with a self-edge) and (1) = with max or sum aggregation, o1 id, will] = 0 and W)(1) neigh
Tdpxp-
Lemma 3. Any ReLU MPNN X R RIE) xd - x x R Elxdaa can be expressed as TRSM 2 G.:." + RR, with m [ El and p [Vldour + |E|d'
Proof. To prove the proposition, we will show that each layer (0()) is a TRSM on its input, thus is TRSM as well. of (t) Rdh-- x R x R4-1 x R4 - Rdd and of R + Rd are ReLU FNNs, hence by [19 Proposition 5.6]. they are TRSMs. The aggregation operators (sum and coordinate-wee wise max for our purpose) are tropical operators pertaining to tropical multiplication
and addition respectively. Thus, each component of Agg is a TRSF. On the other hand, Update is
(t)
ReLU activation, the update function Update and thus, each MPNN layer g(t)) is also TRSM on its input.
(t)
Corollary 5.3] established the equivalence of (2), (3), (4). Lemma 2 and Lemma imply (4) (1), and (1) > (2) respectively and hence are done. C
Proof of Proposition
Note that 19
Bounds on geometric complexity
We here provide more detailed analysis for the Geometric complexity and the proof of Theorem and Theorem 4 To simplify the analysis, will assume that we have edge embedding throughout MPNN layers the analysis for the most general case follows the same idea. this analysis, we also assume that inputs of the model follows the same graph G. Let S and be the maximum and total degree of all vertices of G.
We will consider the input (tt-1) of each message passing layer (p(t) stacked vector of edge node embedding A (t=1)) As we do not want to calculate unused messages between non-adjacency nodes, with the vectorized form (instead matrix form), we could consider each degree separately and thus reduce the dimension of intermediate layers from S to D. Forming the vectorized form requires assumption of an order between the nodes and the induced lexical order for the edges introduced in Section 2 However, we can neutralize this effect by multiplying with the appropriate permutation matrix P. We now outline the changes happen in each layer.
1. The vector (t) IR Vld will be the input to yp()) RIV/411 VId (H(O) = X).
2. We then apply oh [V|dde11 x V - gVV to every pair adjacent node embed- ding A; and Aj to obtain the message from node A; to node Aj. The idea is to form big
FNN T applied on the whole vector (t(-1) to obtain the output (() E Ddd The FNN
(t) $ 2 in general depends depends on D and connectedness of the graph.
3. After that, we perform the operator (4) = (t)
(w) (sum or coordinate-wise max/min)
of all the neighboring messages obtain (t) R We will later that there is a significant difference in the two cases of aggregation operator and suggest that the coordinate-wn wise max/min could indeed increase geometric complexity.
4. Analogously, we then form (()) IR Vld. by forming a bigger network ((() (based on
(0) Rd. + Rdc), applied to (1) i.c. (t)) (()())))
16

---

5. We combine step 2, and 4 to form big FNN (1) applied to Hf(-1)
Agg
6. Lastly, obtain H E RIV by performing the Updaate
(8)
We proceed with the first step. The algorithm | shows us how to build 1 from (1) by replicating the neural network Φ2 (t) for neighboring nodes and putting O for the nodes that are not adjacent.
Without no edge embeddings, our o only depends on the node embedding h (t-1)) and h (, Our notations from now on always indicate that of Φ2 are applied to each (pair of) embeddings whereas T T ) applied to the corresponding stacked vector whole.
Algorithm 1 Building 4/2
Input: Stacked vector (((-1) RIVId of embedding of all vertices.
We will only describe the construction for weight, the bias could be done analogously. Let W. and A.
n2 be the weight and number of output nodes of the f-th layer of Φ!²² respectively (n2 d Thus, W22 E " For the first layer = 1, let W [W21 W2 where W2.1 W E Rn4 xde-1 correspond to the weight the first d--1 nodes (of the embedding 14,1 111111) and last di-1 nodes (of the in 1 (4-1)) respectively.
We now define the weight for (()) In the first layer of (
W E DD x|V|d.-1 by breaking it into blocks [ J,,, of size n² f.1 x di-1. For each edge k-th (according to the ordering of edges),
assume is (Ar, Aj). then, we set
W
+
W
if = =i= if = if
W
[W Ia,e'
2.1
(3)
Wi.1
2,2
0
otherwise.
The remaining layers & are easy to build: let Whr E DDnb"" and W
W t
0
0
Wed
and applied the activation accordingly.
0
Proposition 9. ReLU FNN 3 in Algorithm applied to (t-11), will result in the same output as we apply d separately for neighboring nodes h (t-1), (t-1)) and combine the result.
A,
Proof. We first assume that 2 has only one layer and the action of ReI.U activation applied coordinate-wise. assume that
(t-1)
11-1) (. ((())11
A
= W
+ Wi (t-1)
(1-1)
A
A
[x(()
(t-1)
A1
There are D edges in total, thus (1)
E ER Dn and (t-1)
For the x-th
x(1)
h vi
(t-1)
(t-()) ((-1)) edge AA;, we want x!") = 02 (1(1)) AA
), the formula 3 will yield the desired result.
Then applying the following layers (1) is equivalent to applying the corresponding layers of d on each result.
Proposition 10 (The matrix to take the sum). of (t) (1) (e)
is sum, then
y(1) = (x())
17

---

where M is matrix that generally depends on the adjacency matrix A of G. Thus, it does not change the linear/convex degree and its effect can be absorbed by the first layer of 1
Proof. We first build M E x by breaking into blocks of size de x d.. Then each block if edge n² = (Ax: Aj) E E
Id xd,
Ma.n'
otherwise
It is easy see that y(o) MX()), since the matrix M is the same the adjacency matrix A of G replacing 1 with Id dexds
L
On the other hand, when the operator ( is coordinate-wise max-min, the analysis becomes a little bit more complicated. particular, we can create a neural network $ to represent its effect. the Algorithm 2 we want to make appearance of the weight 1/2 in the comparing layer. Fortumately, by scaling the input by a factor of 1/2 (which does not change the number of linear regions) and scaling the weights by factor of
of the comparing architecture in [83]. A minor blockage is the
we could solve this problem. We note that ø5 ( depends heavily on the graph G.
Algorithm 2 Building (
Input: ( E Dd.
We first scale all entries in the input by 1/2. Then create FNN that resembles the construction in [83], however, we will not compare two consecutive nodes, but the comparison done according to the edges of the graph
Proposition 11. (() is coordinate wise max/min, then
(()) 1 (x(1),,
where 3 is built according to Algorithm
Remark 4. Here, we surmise that if we have coordinate-wise max/min aggregation operator, the geometric complexity of our model grows exponentially with D and polynomially with S.
After that, we continue with step 4, where we apply the neural network of form the transformation of the aggregated message. Similar to step 2, we would want to build (0) that is applied on the
whole (t) as a vector. However, this much easier to form (e()) than that of T5 as
((((0) I (1-1)).++ + sde)) 11 ()-(0)
(i- 1)d++ I....dd )
(4)
Algorithm 3 Building (f)
Input: y0) E RIVId.
Let Wt E go 1 xnf
and Wird 11V be the weight of the L-th layer of (1) (0)
respectively. Then W T.ltt
0
WPd
and applied the activation accordingly.
0 O
Obviously, since each component applied separately, we have the following proposition. Proposition 12.
(1(1)))))))))))))))))))))))))( ( (1s..)) (00 (v((()
(1-1)d++ I....d )T.
(5)
18

---

Lower bound on geometric complexity
Proof of Theorem By Proposition Proposition 13 and Proposition we note that each Ag- gregation step P'ggg can be written as a FNNs $ Agg applied to H()), Note that ( = Σ can be absorbed by the first layer of { (constructed in Algorithm 3 On the other hand, [ = max can be seen as a max-out layer with rank S). Thus, by (76] Theorem proof], it can identify S regions
of the input. Then (p()) Upddne (h. m.) = my then we can write H Φ Age (H((t))), Thus, by [76
Theorem 4], we have the maximum number linear region of functions computed by any ReLU MPNN is lower bounded by
[T Th
1 1,d
10 2.1 I
))
n2,do
dr
Sta
T.L(") Y1 1,4
Upper bound on geometric complexity
(6) has niz outpur nodes in its l-th hidden layer, then the neural network 222 have Dre nodes in its l-th layer. Therefore, the number of output nodes and hidden layer nodes depend on the connectivity of the network.
Remark 5. If the neural network @2
1.l t.l Proposition 13. If the neural network Φ1 22 has ni 122 number of nodes in its t-th hidden layer then the neural network 1 ( have [V|n]" [D]n number of nodes in 8-th layer. Thus, if
(t) (t)
f.l
12 1. 2 D de for all I 1, 1,... 12
2 for all | I,..., 1
then applying 19 Theorem 6.31, obtain upper bound for conver degree:
11 -1
Ivi,
Dnn
1.1
4/
V 1.1
N Age
II
Σ
Nc(O
II
Σ
[i]
(6)
convex linear regions, where
-1
f Σ
N( -
(o(sD (r max.
(
Proof. (f) coordinate-win max/min, then D3 has [log2 Sl 1 layers. For ease of analysis, we can assume each hidden layer has Dd, nodes (this only increase the convex/linear degree) except Theorem 6.3], we have
for the first layer with most 2Dd, nodes, thus from [99
Ddt Σ
2Dd
[log S1 Dd.
Ddd
II
22D -1 Dd. [loga $1,
as Σn (2m) 22n-1 2 Using Propositions and we can write the result of p (i.c. (
as a result of a combined FNN T c 6.3] yields the stated result.
+ applied to (t)-1), Then applying [19 Theorem
3
Thus, we are left with the final step in PPpdate If we stack the two vector together, which now of dimension [V|d + [V]d, apply [19 Lemma D.4] to prove the following Corollary.
(t)
19

---

Corollary 5. Let Upddat
(0) Púpuaae
-RI(((+dd)) IR vld. I5 + de) [V((dd), i.e.
Updatte
de + d S de, then
[vid Σ
(
upduue o pl(d + VI)
The following results together yield an important Proposition that allows us to analyze each component of (l()) separately before combining them. The following lemma is trivial, but we provide proof for completeness.
Lemma 4. Let F Rol(m,p) and m S m, Then
(8)
Proof. We invoke the fact that if F' is an affine transformation of R" and A C I² is convex, then the image [[A] is also convex. Thus, a convex linear region in NN.(lld is still a convex and linear region
in (F)),, , and vice versa. On the other hand, some convex linear regions in RR do not intersect the affine space, resulting in the inequality.
We first recall 19
Theorem D.3]: Let F, G in Rot(m, p) and Rat(m', m). Let H (n. hp)
Rot(m', p) defined by h; == fi G for 1...,. Then
((H) S (N((H) Nc((Flm))
Proof of Proposition
We note that
x = pl1) o (t(-1),
(9)
thus using 19 Theorem D.3], we have
()(x < No((s(111Vdd))) (add)
(10)
Note that (( (H(-11)) UPidate (1 (11(1-1)), (11-111 thus
((t)
No((o ((V]d) S No((p(t)) < No(PUUpaar (d: + d:)l (F
(11)
We further break the terms Na Agg down by noticing that + 1 (0) !0
applying
in 19 Theorem D.3] multiple times and Lemma
Thus, bringing all the corollary together and apply 19 Theorem 6.3] recursively, we obtain the following bound for the geometric complexity:
Proof of Theorem 4 The theorem follows from Proposition 2 the model in steps. Thus, bringing the pieces together, we have
which tells us that we could analyze
[0 -1 [v]de
[Vin
f.1
x
Dnn
II
Σ
Σ
N.((()).
==0
from + (t)
from 9 (t)
from (E)
if ()) is sum
where (())
(8
if (8) is coordinate max/min.
20

---

6.1 Consequences of Theorem
We first recover the upper bound for FNNS and GCNs (with ReLU activations and streger-weighty established in [99] Theorem 6] and [2]] Theorem 4] respectively special cases. The one for FNN
straightforward. On the other hand, the bound for GCNs requires slightly more work.
Proof of Corollary 2 Firstly, note that GCN can be modelled by setting of = Id, O sum, and (t)
(f) Uppaate (*), where z(0) is just a stacked vector of m A;" With this simplification, we can fact have a stronger version Proposition 2 (going down to input layer):
No(x)= - (O (
V(
t=1
Vid
(v(())
(by Proposition
10 0 (1) is just linear transformation).
i=0
Proof of Corollary In both case, we note that o1 id, thus, we can forget the contribution of 11. If the aggregation operator is mean, substitute (t) Σ. then d2 (1) id and (update stays the same. Thus, we have
2|V|de-1 Nc(0') I
Σ 1=0
(12)
i
the aggregation operator is pooling, then 02 is a one-layer FNN, ( max and Updaae stays the same. Thus, have
vidh- Σ
(Vl(d+ddr-1)
Dide
(Vde) )
Ne(p9) S
(13)
Proof of Corollary According to 15 Equation 4.1], by adding self-edge each node in the graph, t-th layer of GIN can be written as (t) Σ (or affine transformation which does not (t)
change the geometric complexity), 2 and @1 MLP indicated, thus
( [Vid l=1
[Vint. t=
Nc(x) $
i
New ReLU MPNNs architectures and complexity tradeoffs
In most of the following architectures, the aggregated message has the following form,
(t) m A.
o (t)) (D (t)
A)EN(A.) 22 ( (h(--")))
(14)
i.e. the aggregated message to node A; depends only on the neighboring nodes A, (and not A itself).
Lemma 5. Let F G Rmm - RP be TRSM. Suppose each component F; of F can be represented by an FNN/MPNN with L.F, layers, and G; of by an FNN/PPN with LG, layers. Then F @ G can be represented as L-layer FNNMPNN with L max {max(LE, Lc.)) + 1.
21

---

Proof. The main idea underlying our proof here is to exploit parallelization. Firstly, for FNNs, we can compute all F; and G; in parallel using max" (max{ LG. }} layers: we set the block matrix for weights between the different components to zero (for the components that require fewer layers. we can add additional dummy layers with their weights set to the identity matrix Id). We then need just one additional layer to compute the difference F, Gú again in parallel, for all 1, Similarly, for MPNNs, we construct F; and G; in parallel following appropriate stacking of the weights of the components. In this case, each additional layer t (for the components with fewer layers) is treated as follows: we set the weights for @ L1 to zero and W self to identity. Lastly, to compute the difference F; and G; we just need one additional MPNN layer where aggregation part (2) 0 (o2) 01
(L) (1.) (.) is sum or coordinate-wel wise max), and W = [Idpxp -Idpxpl-
We provide an overview and detailed algorithms for the gadgets here. The broadeast gadget sets up an MPNN by replicating its input across nodes of a fully connected graph. It also endows each node with ROE. The selection and comparison gadgets are implemented as FFNs: the former used for partitioning the monomials across the nodes, whereas the latter determines the larger of its two input monomials.
6.2 Broadcast gadget
Broadcast gadget. Given input vector R", first construct fully connected graph with m vertices A1, .... Am- The feature vector for A₁ is constructed as follows: first m coordinates comprise F, the next coordinate set to I (for bias), and the last m coordinates are feature vectors for all other nodes A; consist of m + 1 zeros followed by 1m ez. A parameterized message passing layer with weights determined by a target TSF is then learned compute all the monomials P1 P2. .... of f. We provide all the details, including the operators in Algorithm | It
ROE 1. e1. The
can be shown that the embedding of node A, after broadcasting is [P1, [P1,P2,... P2, .... Pr. (Im e,) 7]
Algorithm 4 Broadcast component: MPNN layer
Build an m-clique with vertices A1, .... Am and bidirectional edges, and introduce loops with m self-edges from each vertex A, to itself.
Prepare node embeddings. For A,, we set first m coordinates to the input v, the next coordinate to 1 for bias, and then the final m coordinates set to its ROE 1, e1. For other nodes A, we instead have a vector with first m coordinates set 0, followed by single coordinate for bias and finally their respective ROE 1 64-
Finally, we construct layer of message passing. Specifically, of is 1-layer FNN with identity
[C Rex(m+1)
Opxm
activation, no bias, and has the form of Equation 14 Its weight matrix is
0mx(m+1)
Omxmm
where each row Ct.: [ai, ci] E R=+ We use the sum aggregation operator and set Orxm Tdmxm]
(1) = Id. Moreover, Updante has identity activation, w-(1) self
0 0rx (m++))
and
0mx(m+1)
w-(1) neigh = Id(r+m)x(r+m))
The following result follows immediately from Algorithm 4
f is Proposition 14. The embedding of vertex A after broadcasting with Algorithm
(pi.P2...., Pr. (Im - e] where Ps is the ith affine combination (or tropical monomial) of Furthermore, the Broadcast Algorithm Auses in total 2 FNN layers across layer of message passing and (2m + ()(r + m) parameters of which (m ()) ((r) are learnable.
6.3 Selection gadget
We now describe the selection gadget that we invoke to distribute monomials (almost) evenly among the nodes such that the node A, gets monomials y; = {pk mod m = i). Selection gadget. FNN with two layers that acts on the embeddings produced by the Broadcast gadget and utilizes
22

---

P1
max(pr.PP
P2
0C
(a) Gadget for selecting (Lemmaa
(b) Comparison gadget (following 83
Figure 2: Orange, green, and magenta nodes represent input, hidden (with activation max 0}} and output (with activation max(', -oo}) units respectively. (Left) Ç can be used as a control to either let & pass or filter through the network. Note that in practice a sufficiently small negative weight can be used instead of cco. (Right) A gadget that yields the greater of its two inputs as the output.
211
P1
Pa
22
P2
233
P3
P1
P4
1
0
0
1
(a) Broadcast gadget
(b) Selection gadget for selecting multiple inputs.
Figure 3: (Left) Φ2 in Broadcast gadget (shown here for 3 and 4 for node AA, replicates all the monomials P1..... Pr across the nodes of graph & (not shown). See Algorithm 4 in Appendix for weights and other details. (Right) Selection gadget builds the base gadget from Fig, 2a and filters out specific monomials at each node of G, yielding a partition the monomials across nodes.
the following result (Lemmal6) to filter out monomials such that each vertex A, left with only the monomials P; {P& k mod i}. The coordinates of each ROE serve as the control variables Ç for this purpose. Please see Algorithm[5je details.
Lemma 6. Consider any two-dimensional input with coordinates E 2 0 and Ç E {0, There exists
2-layer NN with ReLU activations (see Figure 2a that outputs & when Ç = 0, and when Ç ş=1 1.
Proof. If Ç = 0, then the values at the two nodes in the hidden layer are Ç and - respectively before activation, and & and after activation. Thus, the final output in this case is &.
On the other hand, Ç = 1, then the two nodes the hidden layer take values -0, oo, respectively before activation, and thus 0 and 0 after activation. Thus, the final output in this case is O.
Proposition 15. Node As, after selection with Algorithm only contains the monomials p; of f.
Proof. Note that this result is just a generalization Lemma 6 the sense that we now distribute r monomials into batches of size (with each monomial playing the role of {) across the nodes with coordinates from ROE playing the role of Ç. The two layers return when ( = and & when {= O. Note that there is only one 0 in the thh position of ROE 1,, e, for A, so A, ends up with all the monomials after the second layer.
We ready describe all the models, namely the Local, Global, Constant and Hybrid algorithms to compute a TSF f Rm + R.
6.4 Local MPNN and its complexity
Proposition 16. Local MPNN can learn any TSF f mh TR with monomials. requires total
[logg(//m)] + 5 FNN layers across 2 layers of MPNN, and O(rm) trainable parameters.
23

---

Algorithm 5 Selection component: FNN layer
Input: any vector with ROE. In our case, is [PI, P2, ...
Pr., Pr, (1m - e
We create 2-layer neural network as described below.
First layer: no bias, ReLU activation max(z, 0), and weight matrix of dimensions 2r x (r + +)) with weights
i'' S and 2x'
if w S and k 2x'
Wae!
(15)
00
if n 2 r and it = 2(1²' -r), -r) -r)-1 - mod 2m
otherwise.
Second layer: bias, identity activation, and weight matrix of dimensions r' 2r with weights
if
and k' odd,
2m
Wiere'
if K
x
and n' even,
(16)
2T
0
otherwise.
Algorithm 6 Local MPNN
Input: m-diimensional input
First, we perform broadcast with Algorithm
We need additional layer of Message Passing. 02 will have the form of [4]. The first two layers
of 02 pertain to the selection gadget from Algorithm
We then resort to [log2(//m) + layers of local comparison (simultancously comparing 2 nodes
each time) according the algorithm in [19 (83) for (
is coordinate-wise max, (3) Id, and Up has identity activation with w 0 and
W (2) neigh
Td.
Proof. As shown in Proposition 14 each node A; has the embedding [Pi, P?,..,. (1m - T] after broadcasting. These embeddings
filtered by the selection gadget, by Proposition 15 each node A; is left with r' = monomials p; {Ps : k mod m i}. Thus, using Tog 11 layers of comparison (see, e.g. (3) we obtain the maximum max Max aggregation (coupled with the fact that have m-clique with self loops) helps compute max;= Pi
max Pt (xx Note that the second MPNN-layer y2(2) involves only fixed parameters, and
comprises (r') + 3 FNN layers.
6.5 Global MPNN and its complexity
Proposition 17. Global MPNN can learn any TSF f: : RT + R with r monomials. It requires in total 3 [log (r) (r)1+2 parameters.
FNN-layers across [logm (7)l + MPNN layers, and O(rm) trainable
Proof. As shown in Proposition 14 after the Broadcast component, each node A, has the embedding (11, P2.....PP Pr. (1m c,) T Then by Proposition 15 the message from A; after of (modified Selection Component) is y. {px k mod = i). appended by ROF. This vector is of dimension + m I + m. Then, max aggregation (coupled with the fact that we have an m-clique with self
loops) helps compute max m Pl, .... Pm, max:=1....m m Pm+1s ... pamz and on, and output

---

Algorithm 7 Global MPNN
First, we perform broadcast with Algorithm
The second layer of MPNN is designed as follows.
(2) implements the selection gadget from 5 and
uses aggregation of the form specified in (14). However, as a placeholder for the ROE, we append m with all coordinates set to 0 to the weight matrix for the second layer in Algorithm Thus, the weight matrix is now of dimensions (r' + m) x 2r.
neigh = Td, and (2) is coordinate-wiss wise max and 212) = Id, Upidatte uses identity activation, W
0
W
0
Idmxm
We then repeat this process (replacing with r' until we left with only 1 component and the final maximum f). This requires [log.. (r) additional MPNN layers.
the same result for every node A, besides the ROE which is different for the nodes. Similarly, in the subsequent MPNN layers, invoking the modified selection component and coordinate- -wise max yields max;=1..... P; f()). Note that, except for the first MPNN, all the subsequent MPNN layers have only fixed, i.e., non-learnable parameters. Thus in total, we would need [log,, (r)] + MPNN layers, including the first Broadcast layer.
6.5.1 Constant MPNN and complexity
Algorithm 8 Constant MPNN
First, we perform broadcast with Algorithm
(2) however needs to be modified since for We only need one additional message passing layer. @2 each node A,, we would want to have 1zy,, for each j ...... suggested by Sj instead of 1 that Proposition guaranteed.
Specifically, the first layer of @2 we now have 2dr hidden nodes (2d nodes for each 4,), ReLU activation, no bias, and a weight matrix E 22drx(++d) with weights.
(2)
if n < k,
16 and x odd,
2m
-1
if < k,
and A even,
Wox!
00
if and 2(x 2() - k)) - mod 2m,
Zym
(17)
otherwise.
We now choose the linear pieces according to Sy. The second layer o. has 2q hidden nodes, identity activation, no bias and weights 2 given by
if R'' = 2m(2p, - 1) + 2i for i = 1, and K = 2p + 1,
1
if 1m2 2 1,,+1 1) 1 K' 2m2 1, k²' odd, and 24c
Where'
n' 2m (2ptt
1) + 2i for 1..., and == 2p
-1
2m + S k' <
even, and k = 2p,
otherwise.
For the next layers in ob(2) take the maximum of node 2x + and node 2x using two layers of the comparison gadget.
The aggregation function is coordinate-we wise max, ((2) = Id, Lpdate uses identity activation and self and [Wr(2) neighti = Sj.
Proposition 18. The Constant algorithm g can learn any TSF f: : Imm R with monomials. requires in total 7 FNN layers across 2 layers of MPNN, and ((mrq) learnable parameters.
25

---

Proof. As before, after broadcasting, each node A, comprises P21.P2.-,,Ps (1m ex) Then, after processing with the first two layers of o the output for node A; is Prom Thus, after processed by the last two layers, the message from [Per. PeL.m 41 P P
e,
node A, [max/Ps.. Par.m J..., max m Pan.mma 31 With the max operation, the aggregated message for nodes maaxes, 4 .... maxies, 4:] Finally, with filling W neigh the resulting embedding for every node becomes = 8y (maxisss, 1;), which is by 84 Theorem 1J, fz). L.
6.5.2 Hybrid Architecture and its complexity
Algorithm 9 Hybrid Architecture
Input: m-ddimensional input æ
We start with a I-layer FNN with m input nodes and r output nodes for the monomials. It has identity activation and its weight matrix W Brxm where each row W [a, E R! and its bias is the
constants the tropical monomials, i.e. b, = c. thus, yielding the output [pr prl
After that, we build an r-cliques AI, Ar, and bidirectional edges, and introduce loops with m self- edges from each vertex A; itself. We then put the initial embeddings X y" [pi ... pr). We
then have 23 2 A, = A, and Aggregation operation to be coordinate- wise max, @1 = Id
(0)
(2)
(1) to form m (1) (which is now), and put PUpdaee m A, f
The following Proposition immediately follows.
Proposition 19. The Hybrid algorithm & can learn any TSF f Rmm -> IR with r monomials. Ir requires in total FNN layer and message passing layer, and ((r)) learnable parameters.
26

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA].
[NA] means either that the question is Not Applicable for that particular paper the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
27

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specing well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tes system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Our work is purely theoretical and does not involve any experimental result.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
28

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our work is purely theoretical and does not any data and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
haapii/guuudee///oeSuunbsssssss sot. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7/
gwwss CCodeSoodieeeeeee ssi mollicyy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
29

---

Answer: [NA]
Justification: Our work is purely theoretical and does not involve any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our work is purely theoretical and does not involve any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгrоr bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our work is purely theoretical and does not involve any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
30

---

Question: Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics htt.ah/.rrrr///aorrr..///o//o//t
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This is no societal impact of the work performed as the work is purely theoretical.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
31

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pappessii thoode wwwccoo//aaooooo datasat has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
32

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "zZpDS8pB3l", "reviewer": "Reviewer_jpJX", "summary": "This paper aims to characterize the class of functions learned by message passing Graph Neural Networks (GNNs) with ReLU activations through the lens of Tropical Geometry. Specifically, it characterizes the functions learned by ReLU-based Message Passing Neural Networks (MPNNs) by establishing their equivalence to ReLU Feedforward Neural Networks (FNNs), Tropical Rational Splines Models (TRSMs), and Continuous Piecewise Linear Maps (CPLMs). The paper provides both lower and upper bounds for the number of linear regions and decision boundaries. Additionally, it compares the expressive power of different aggregation operators, revealing that the coordinate-wise max operator has greater geometric complexity than the sum operator.", "questions": "Please refer to the Weaknesses.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-structured and clear.\n\n2. The theoretical foundation is solid and thorough.\n\n3. It provides the first lower and upper bounds for the number of linear regions in ReLU MPNNs.\n\n4. It demonstrates that the max aggregation operator is more expressive than the sum operator in terms of geometric complexity, highlighting how expressivity varies with different message aggregation operators and update functions.", "weaknesses": "1. The theoretical analysis may not be directly applicable in practice for graph predictions, as it assumes that the ReLU MPNN processes the same graph structure, which is not typically the case in graph classification tasks.\n\n2. The technical condition used in the analysis—that the dimension of the new embedding is at least the sum of the dimensions of the aggregated message and the previous embedding—may be restrictive and not hold for general MPNN architectures.\n\n3. It is unclear how the input graph's spectral properties affect the geometric complexity of ReLU MPNNs within the established bounds.\n\n4. While the theoretical results indicate that ReLU MPNNs are less expressive or as expressive as ReLU FNNs, in practice, ReLU MPNNs significantly outperform FNNs in graph learning tasks. This discrepancy suggests the theoretical results may not fully explain the practical successes of ReLU MPNNs.\n\nOther Comments:\n\n1. Line 123: $x_d^{a_m}$ should be $x_m^{a_m}$.\n\n2. What does $D$ stand for in Theorem 4?\n\n3. It may be better to use different notations to represent the set of neighboring vertices ($\\mathcal{N}(v)$) and the linear degree ($\\mathcal{N}(f)$) for a piecewise linear function to avoid ambiguity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and constructive feedback. We're glad to note your recognition of several contributions and strengths of this paper.  We address your comments, concerns, and suggestions below.\n\n`The theoretical analysis ... assumes that the ReLU MPNN processes the same graph structure, ....`\n\nWe agree with the reviewer. This is a good observation, and indeed we assume the same graph structure for our analysis while deriving the upper bound on geometric complexity. We suspect that this is a technical artefact that somewhat simplifies our analysis (previous work on number of linear regions of GCNs [1] also made a similar assumption), but retains the essential aspects of the typical (i.e., the more general different graph structures) setting with respect to the role played by the aggregation and update steps. We indeed hope that this assumption can be relaxed, or removed altogether, in some future work.  \n\n[1] Chen et al. Lower and upper bounds for numbers of linear regions of graph convolutional networks, 2022. \n\n`The technical condition ... that the dimension of the new embedding is at least the sum of the dimensions of the aggregated message and the previous embedding—may be restrictive ...`\n\nWe agree with the reviewer on this as well.  This restriction generally arises in the analysis of geometric complexity (in particular, it showed up in the analysis of tropical geometry of ReLU FFNs [2] as well)  to ensure an amenable arrangement of hyperplanes, ruling out the pathological possibilities.   \n\n[2] Zhang et al. Tropical geometry of deep neural networks, 2018.\n\n`It is unclear how the input graph's spectral properties affect the geometric complexity of ReLU MPNNs within the established bounds.`\n\nIndeed, while our bounds reveal the dependence of some input graph properties such as max degree, sum etc., they do not involve spectral quantities such as the spectrum of Laplacian. It's an interesting future direction to investigate whether such quantities have any effect on the geometric complexity of ReLU MPNNs.  \n\n`While the theoretical results ... ReLU MPNNs are less expressive or as expressive as ReLU FNNs, in practice, ReLU MPNNs significantly outperform FNNs in graph learning tasks. This discrepancy... may not fully explain the practical successes of ReLU MPNNs.`\n\nThank you for the opportunity to clarify this question that motivated most of the second half of our work, where we consider several ReLU MPNN architectures to represent continuous piecewise linear maps and compare them to ReLU MPNNs. While the first half of our work showed an equivalence between ReLU MPNNS and ReLU FFNs in terms of the class of functions that they can represent,  our subsequent analysis  (especially, Remark 3, Proposition 6,  and Table 1 in the paper) suggests why ReLU MPNNs might be more effective in practice. In particular, as Table 1 summarises, ReLU MPNNs outperform ReLU FNNs in terms of both the number of learnable parameters as well as the number of layers required in order to be able to represent the same continuous piecewise linear map. That said, we sidestepped the role of optimisation algorithm (e.g., SGD/Adam), which is another consideration that might also add to this  discrepancy between ReLU MPNNs and ReLU FNNs in practice.  Based on your feedback, we will make this clear. \n\n`Other Comments:\nLine 123: should be .\nWhat does  stand for in Theorem 4?\nIt may be better to use different notations to represent the set of neighboring vertices () and the linear degree () for a piecewise linear function to avoid ambiguity.`\n\nMany thanks - we'll incorporate all your suggestions. Indeed, in line 123, $x^{a_m}_d$ should be $x^{a_m}_m$. In Theorem 4, $D$ stands for the sum of degrees of all the vertices. We would also modify the notation to avoid confusion.\n\nWe're grateful for your review, and hope our response has satisfactorily addressed your questions and concerns. Thank you very much!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DR8FsRqBjH", "reviewer": "Reviewer_sZYW", "summary": "This paper uses tropical geometry to understand MPNNs in the broader general context of GNNs.  In the face of the WL framework which studies limitations of the GNNs, this paper proposes to use the rich and powerful theory of tropical geometry to uncover their potential.  This paper makes some important contributions in this direction in terms of counts of the number of linear regions analytically and studies particular cases of popular architectures.", "questions": "Analytic bounds were given that build on existing theoretical approaches in the literature.  How would the same question to be approached numerically, for example, under experimental training of the network where it will be likely very difficult to derive analytic solutions?\n\nThe ideas for future directions of research in the conclusion are not very convincing and seem to be unfounded – can more details please be provided on how \"other aspects of tropical geometry\" such as \"tropical cycles, the Chow group, and Tropical Jacobian\" might reveal further insights about the structure of these MPNNs?\n\nAlso, this is likely to be a matter of personal taste, but I found the color-coded theoretical results and presentation quite distracting, is this really necessary?", "limitations": "The limitations were discussed throughout the paper in the form of remarks and a discussion in the concluding remarks.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is quite well-written and well-motivated.  It also lays the ground for further work in this direction where tropical geometry is a powerful tool that has much potential that has so far been limitedly utilized to understand neural networks.\n\nThe paper also provides thorough analyses and considerations of the aspects of their theoretical contributions.", "weaknesses": "I am very familiar with this area of work and so I was able to understand what the authors meant when claiming to establish equivalence between tropical rational signomial maps, but care needs to be taken to phrase this appropriately because the first equivalence between tropical signomial maps and feedforward neural networks was already established in 2018.\n\nA better literature review is needed on the intersection between tropical geometry and machine learning.  This is a new and promising direction (which I believe that the submission has the potential to make an important contribution) and not much work has been done in this area and so it should be relatively easy to do a comprehensive literature review on this and I am surprised that this was not done.\n\nIn general, the references on tropical geometry theory are quite seriously lacking.  It's clear that the proofs of some of the main theoretical contributions rely on known and well-established results from tropical geometry theory and on some of the existing literature at the intersection of tropical geometry and machine learning builds on, I think that it's misleading not to cite these papers and remark explicitly that the approach and idea for the proofs borrow from these existing resources.  It's important that the revision be edited to include this information in order to give appropriate credit where it is due.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for such a detailed, constructive and thoughtful review. We're grateful for your acknowledgment of the contributions of this work, and share your enthusiasm for leveraging tropical geometry to better understand successful modern architectures. \n\nBelow we address all your questions, comments, and suggestions. \n\n`I am very familiar with this area of work... but care needs to be taken to phrase this appropriately because the first equivalence between tropical signomial maps and feedforward neural networks was already established in 2018.`\n\nThank you for an excellent suggestion.  Indeed, the seminal work of Zhang et al. [1] established the equivalence between ReLU FFNs and tropical relational signomial maps, which we crucially leverage in Proposition 1.  Therefore, we acknowledge this result in the introduction (line 41), at the beginning of Section 3 (line 138), as well as the proof of Proposition 1 (line 513 in the Appendix). Based on your feedback we will state this result prominently at the beginning of Section 3 as a Lemma due to Zhang et al [1], clarifying what the equivalence entails, before we proceed to Proposition 1. We also welcome any other suggestions you might have in this context.  \n\n[1] Zhang, Naitzat, and Lim. Tropical geometry of deep neural networks, 2018.\n\n`A better literature review is needed on the intersection between tropical geometry and machine learning. This is a new and promising direction (which I believe that the submission has the potential to make an important contribution) ... it should be ... easy to do a comprehensive literature review. In general, the references on tropical geometry theory are quite seriously lacking.`\n\nThank you for drawing our attention to this! We will be sure to cite more works at the intersection of tropical geometry and machine learning, and position their contributions. In particular, we will include the following references:\n\n[2] Charisopoulos and Maragos. A Tropical Approach to Neural Networks with Piecewise Linear Activations, 2018.\n\n[3] Maragos, Charisopoulos, and Theodosis. Tropical Geometry and Machine Learning, 2021.\n\n[4]  Alfarra, Bibi, Hammoud, Gaafar, and Ghanem. On the Decision Boundaries of Neural Networks. A Tropical Geometry Perspective, 2023.\n\n[5] Brandenburg, Loho, and Montúfar. The Real Tropical Geometry of Neural Networks, 2024.\n\n[6] Smyrnis and Maragos. Tropical Polynomial Division and Neural Networks, 2019. \n\n[7] Montufar, Ren, and Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums, 2022. \n\n[8] Trager, Kohn, and Bruna. Pure and spurious critical points: a geometric study of linear networks, 2019.\n\n[9] Mehta, Chen, Tang, and Hauenstein. The loss surface of deep linear networks viewed through the algebraic geometry lens, 2021.\n\n[10] Grigsby and Lindsey. On transversality of bent hyperplane arrangements and the topological expressiveness of relu neural networks, 2022.\n\n[11] Williams, Trager, Panozzo, Silva, Zorin, and Bruna. Gradient dynamics of shallow univariate relu networks, 2019.\n\nIn addition, we welcome (with gratitude) and will include any other relevant references that the reviewer might be able to recommend. \n\n`...proofs of some... contributions rely on known ... results from tropical geometry ... existing literature at the intersection of tropical geometry and machine learning builds on ... it's misleading not to cite these papers and remark explicitly that the approach and idea for the proofs borrow from these existing resources. It's important ...... to give appropriate credit where it is due.`\n\nThank you for the opportunity to reflect on this. Certainly, as you pointed out, some of our results either invoke directly, or build on, the tools and analysis of influential existing works (e.g., Zhang et al. [1] who laid the foundations for analysis of neural networks via tropical geometry with their pioneering work). This work very much stands on the shoulders of such  giants, and so while we tried our best to acknowledge the contributions of others (e.g., in the proofs in the Appendix), we apologise for any oversights that could potentially be misconstrued in this regard.  We will revisit all the results in this paper, and make sure to acknowledge these contributions in the main text also when we state the propositions.  \n\n`Analytic bounds ... build on existing ... literature. How would the same ... be approached numerically, ..., under experimental training of the network where it will be likely very difficult to derive analytic solutions?`\n\nThis is an interesting topic for further research. For example, in [12], Serra et al. constructed a method for counting and analyzing, practically, the number of linear regions. Adapting their method for MPNN will require more work, but we believe that it is a promising direction.\n\n[12] Serra, Tjandraatmadja, and Ramalingam. Bounding and Counting Linear Regions of Deep Neural Networks, 2018. \n\n`... future directions ... in the conclusion are not very convincing...  can more details please be provided on how ... \"tropical cycles, the Chow group, and Tropical Jacobian\" might reveal further insights about the structure of these MPNNs?`\n\nChow group can be viewed as an analog of homology in algebraic geometry, so we believe it can serve as a type of ”invariance” of a space and its action might  reveal interesting invariants in the setting of ReLU MPNNs.  It also entails questions about tropical cycles and tropical jacobian. However, absent this context (due to space constraints), this might indeed be confusing and unmotivated, so we'd consider removing these directions from the conclusion. \n\n`I found the color-coded theoretical results ... distracting, is this ... necessary?`\nThank you. We used color-coding to emphasize different components, but will consider removing it. \n\nThank you very much again, and please let us know if we've sufficiently addressed your concerns. We're also happy to engage further.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6oshjpSiOI", "reviewer": "Reviewer_pwpt", "summary": "*Disclaimer*: I did not check proofs carefully and did not read the appendix. I am also by no means an expert in tropical geometry.\n\nThis paper studies expressivity of message passing neural networks (MPNNs) through the lens of tropical geometry. The paper has results on equivalences between classes of piecewise linear polynomials, tropical geometric functions, and MPNNs. They also study the expressivity of MPNNs by counting the number of linear regions and expressing types of tropical functions as MPNNs.", "questions": "See prior sections.", "limitations": "See prior sections.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Proposition 2 and theorems 3 and 4 lay out the main results regarding the expressiveness and the number of linear regions expressible by a MPNN. For theorems 3 and 4, these results have dependence on various quantities that depend on both the graph input and the structure of the MPNN. Nonetheless, a reader can plug these in and get explicit outputs which is nice. Later sections give nice corollaries and extensions of these main results to classification boundaries and expressiveness in the number of parameters.\n\nThe paper is largely a theoretical work. Proofs are given in the appendix, but I did not check these. Some of the theory is tied to specific architectures like GraphSAGE and GIN.", "weaknesses": "Overall, the math of this paper is something worth publishing, but I think the paper needs to be placed in context and written better. Especially for someone like me who is not in this particular sub-topic of tropical geometry, I found the paper a rather frustrating read.\n\nI wish the authors took a big step back and gave more background into this area and discussed the main results a bit more from a higher level. Many questions exist from reading this that I couldn’t get from just reading the mathematical statements and the main text:\n- What does understanding geometric complexity tell us? Does it relate to generalization bounds? When do we want to maximize or minimize this quantity? Or is this paper only concerned with expressiveness?\n- How far apart are these bounds from practice? \n- Do the expressiveness bounds tell us anything new about GNNs? Are there important classes of functions that it now excludes or includes which are not given by e.g. the WL hierarchy?\n\nFrom a rhetorical and presentation point of view, I think the authors could benefit greatly from a clearer presentation of mathematical results, a focusing on the main statements, and shortening of key portions of text. I try to outline this in detail in what follows. Much of this is of course my opinion and I am welcome to criticism and feedback. \n\nProposition 1: This statement seems largely intuitive but is missing details. Can the authors formally define what they mean by equivalence? I.e. the function classes are equal? Do we require the width or number of parameters to be arbitrarily large for this to be true?\n\nProposition 2: \n- This statement is hard to parse as it requires understanding objects like \"the maximum convex degree across restrictions of f to different m′-dimensional affine subspaces…” Can the authors explain the importance of this proposition better? All that is stated about its importance is the recursion like property that lets us relate complexity of subsequent layers. \n- If this proposition is used to only prove subsequent theorems, I would recommend to remove it here and place in appendix. Again, I have read this subsection two or three times and still cannot parse completely what is going on and why it is necessary to be in the main paper.\n\nTheorem 3: \n- The notation of $\\mathcal{N}(\\chi)$ is a bit confusing here since it does not state the number of linear regions for a function $\\chi$, but instead the maximum number of regions for any possible function $\\chi$. Perhaps I am missing something though but I feel this notation should be changed if correct to have a maximum in it to be clearer.\n- The text before the theorem, especially lines 167 to 169 are hard to parse. This seems to be giving proof intuition though I could not really follow. E.g. what is a max-out layer? What do the authors mean by absorbed in? I don’t think it’s helpful to the reader to refer them to an algorithm in the appendix to understand what appears to be one of the main statements in the paper. \n- Can the authors define the notation $n^{t,l}$ before this and preferably even in the theorem statement itself. \n- Should the sum in the right hand side in dark green go from $0$ to $d_T$? If correct as is, how does one handle situations where $d_0>d_T$? Also can’t we simplify this part by using the binomial theorem? \n- This theorem I think could use some discussion and clarification. It seems that the bound depends rather strongly on the input itself (e.g. number of nodes).  This is in contrast with standard fully connected nets where I don’t see a bound depending on the input since this is fixed. \n- Related to the above, how tight is this bound for a random network or one that is found on training?\n\nTheorem 4:\n- The integer weight restriction as the authors point out is largely a technical point and I would just state this as a proof technique rather than a whole paragraph to describe it at the start of the section. It is possible I missed the importance of this point here and perhaps it has actual implications or drawbacks that need to be stressed here (I don’t see anything serious though).\n- I wish the authors would spend more time explaining the theorems. Similar concerns exist here as in theorem 2. Details are deferred to appendix to explain what is happening in the theorem. Parsing the theorem requires understanding a rather complicated formula. Can we use some big O notation perhaps to clean this up? \n- See also notational concerns for theorem 3 that also apply here.\n\n\nSection 4.4:\n- What is PWLM? I assume piecewise linear map? This is not defined though.\n- From line 222 and on, I was just lost. Let me try to explain why and perhaps the authors can clear up this section. To begin, the authors say “our idea is to construct a clique (i.e., a fully-connected graph) with m nodes…” What is the purpose of this and why is it even constructed? Then there is a discussion of local and global comparison which I could simply not follow. Words like compare, selection gadget, etc. are used that I do not know what they mean.\n- Proposition 6 seems like a simple statement, and I wish the authors would explain more why this is nontrivial or useful to know.\n\nSection 4.5:\n- These results seem to be corollaries of theorem 3 and 4 from earlier? Perhaps I am missing something? Is the important part here that the boundary \"is contained in the tropical hypersurface of a specific tropical polynomial”?\n\nConclusion, broader impact, and limitations are considerably short. This paper, especially given it is using tools that may be outside the wheelhouse of the community would really benefit from a richer discussion of limitations and future work.\n\n\nLiterature comments: There are other expressivity hierarchies that the authors could look into which appear more relevant than the WL hierarchy. These include equivariant polynomials (see Puny et al. Equivariant Polynomials for Graph Neural Networks) and homomorphism counts (see Chen et al. Can graph\nneural networks count substructures). \n\n\n\nSmaller comments:\n- Proposition 2 is hard to parse without reading the notation in prior sections and before it. I would prefer more that the most important notation be defined within the formal proposition statement so that it is easier to parse.\n- Notation $\\mathcal{N}$ is overloaded as defining both linear regions and neighborhood.\n- Related to the above, I would request the authors more formally define $\\mathcal{N}$ as a number of linear regions in its own definition statement with some discussion about the definition since it seems to be a crucial quantity. \n- Line 225: what is “noval”?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for a detailed review and several excellent suggestions, all of which we will act on. Please see our response below.  \n\n**(Geometric complexity (GC) and generalization)**\nGC characterizes the complexity of a neural network to approximate functions.  In particular, a high value indicates high expressivity of the architecture  (since, each linear region could potentially be assigned any of the class labels, independent of the other regions). While expressivity is desirable, it can be at odds with generalization [1], whence we must strive for a good tradeoff. GC thus also has implications for generalization; e.g., see  [2]  for a  bound in the context of gradient flows. \n\n[1] Garg, Jegelka, and Jaakkola. Generalization and representational limits of graph neural networks, 2020.   \n[2] Safran, Vardi, and Lee. On the effective number of linear regions in shallow univariate reLU networks: Convergence guarantees and implicit bias, 2022.\n\n`How far apart are these bounds from practice?`\n \nIn general, good estimation of GC is non-trivial. That said, we recover the bounds for GCNs [3] as a special case, and [3] had verified empirically that complexity was indeed close to the lower bound.  \n \n[3] Chen, Wang, and Xiong. Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks, 2022. \n\n**(New results about GNNs vis-a-vis WL)**\nYes, the WL hierarchy implicitly assumes that all updates are injective, which does not hold with ReLU activations. Thus, WL fails to characterize the exact class of functions that ReLU MPNNs can represent, which we show to be TRSMs. Moreover,  as we note in Remark 2, we provide a novel insight that max is more expressive than sum wrt GC for ReLU MPNNs (in contrast to  a result in [4] where under some injectivity assumptions, sum is more expressive in distinguishing graphs). \n\n[4] Xu, Hu, Leskovec, and Jegelka.  How powerful are graph neural networks, 2019. \n\n**(Proposition 1)**  Yes, equivalence here means that the function classes are equal. We do not require the width or number of parameters to be arbitrarily large: any TRSM can be realised with explicit ReLU MPNN/FNN architectures with fixed number of layers, width, and parameters (Table 1).\n\n**(Proposition 2)** Indeed it allows us to analyze each component of each layer, and combine them to get a bound on the overall GC.  This is important, as explained in Section 4.3., as the choice of aggregation will have an impact on the bound. Moreover, it makes clear the contribution of each component, and captures how modifying any component will affect the bound.\n\n**(Theorem 3)** By $\\mathcal{N}(\\chi)$ we mean the number of linear region for a particular ReLU MPNN $\\chi$, or equivalently a particular continuous piecewise linear map. We do not take the maximum over all possible functions. \n\nA max-out layer is one where the activation function is the max of the inputs [5]. By ``absorbed in\" we mean that the network can be extended with another layer of $\\Phi$. \n\nWe apologise for having to refer to Appendix due to space constraints. Indeed, we wanted to give some intuition for the proofs, however that requires mentioning the big FNNs $\\Phi^{(t)}_1, \\Phi^{(t)}_2$.  We'll sketch an outline in the main text based on your feedback. We will also define $n^{t, l}$ as suggested. \n\nWe believe the formula is correct as is, it goes from $0$ to $d_0$. It builds on the ``hyperplane arrangement'' and ``space folding'' arguments from [5], Zaslavsky (1975), that an arrangement of $n_1$ hyperplanes in $\\mathbb{R}^{n_0}$ has at most $\\sum_{i=0}^{n_0} \\binom{n_1}{i}$.  \nWe however need to assume that all $n_{1}^{t, l}, n_{2}^{t, l} \\geq d_0$ \n(in particular,   $d_T \\geq d_0$).\n\nPlease note the bound for fully connected nets does depend on the dimension of the input. In our case the dimension of the initial embedding is $|V|d_0$, which explains why the number of nodes shows up in our result.\n\nWe do not know the tightness of the bound for random networks - it is an interesting open problem. \n\n[5] Montufar, Pascanu, Cho, and Bengio. On the Number of Linear Regions of Deep Neural Networks, 2014.  \n\n**(Theorem 4)**  Indeed the assumption of integer weight is a technical condition and can be relegated to Appendix. This would allow us to accommodate other clarifications based on your suggestions. \n\nApologies - we wanted to be explicit about the role of aggregation and update steps. We could use Stirling's formula to clean up a bit. We will see what we can do about this, and fix any other notational concerns. \n\n**(Section 4.4)** Thanks for catching this: it should be CPLM (continuous piecewise linear map) instead. Sorry for the rather rushed description on gadgets and comparisons - we use these to devise new ReLU MPNN architectures that afford different tradeoffs wrt number of layers and/or parameters.  Proposition 6 precisely elucidates these tradeoffs using Table 1. \n\n**(Section 4.5)** Yes, these are indeed corollaries, and the important part is that the boundary is contained in the tropical hypersurface of a specific tropical polynomial.  Tropical hypersurface is a well-studied object in tropical geometry\nand this allows to study the decision boundary from multiple perspectives.\n\n**(Conclusion)** We hear you, and will do as suggested. In particular, we will point out that some of the technical conditions could be possibly relaxed and a detailed empirical study with novel ReLU MPNN architectures for different kinds of graph inputs (e.g., random graphs) would be helpful.  \n\n**(Literature)** Thank you for drawing our attention to these hierarchies. We will be sure to position the mentioned influential works by Puny et al and Chen et al. \n\nWe'll take care of the smaller comments about notation and fixing the typo (\"noval\" should be replaced by novel). \n\nWe are grateful for your extremely valuable inputs, and will act on them. Hope all your comments are satisfactorily addressed - we're happy to engage further as well.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a new and fundamental approach to understanding the expressivity of message-passing Graph Neural Networks (GNNs) using the lence of tropical geometry. The paper establishes an equivalence between ReLU GNNs and various classes of continuous piecewise linear maps, contributing new bounds on the geometric complexity of popular GNN architectures. The paper notably provides general upper and lower bounds on the number of linear regions and decision boundaries in such networks.

While the paper makes solid theoretical contributions, the presentation of the results could benefit from substantial improvement. The material is dense and may be challenging for readers (especially for readers without a strong background in tropical geometry). Moreover, better attribution of previous work in tropical geometry is expected. Additionally, the practical implications of the theoretical results remain unclear, with no experimental validation provided to assess how these theoretical bounds translate to real-world applications.

Despite these shortcomings, the reviewers unanimously recognize the novelty and importance of the results. The authors are encouraged to revise the manuscript to improve clarity. Future work investigating the practical relevance of the results would be very welcome.
Decision: Accept (poster)