What do Graph Neural Networks learn? Insights from Tropical Geometry

Authors: tuan anh pham
vikas  garg
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 13:42:27

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.

Main paper: 
 introduction: 
 Message passing has been a cornerstone of machine learning, from inference in graphical models [1, 2] to embedding of graphs [3, 4, 5, 6, 7] . Message passing neural networks (MPNNs) are easy to implement, and can handle large scale, heterogeneous, and dynamic real world data effectively; so continue to be an active area of research [8, 9, 10] . Indeed, several popular GNNs are usually cast and implemented as MPNNs, see e.g., [11, 12, 13, 14, 15] . Unsurprisingly, GNNs as MPNNs have been analyzed from multiple theoretical perspectives. A major theme is inspired by connections to the so-called 1-WL (Weisfeiler-Leman) 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 [15, 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, most successful GNNs typically use ReLU activations that violate injectivity. Bounding the expressivity of such GNNs via their injective surrogates is theoretically valid; however, it does not illuminate what they learn. Indeed, several fundamental questions remain elusive for these practical models; e.g., (a) We appeal to tropical algebra and geometry to address these questions in the context of 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 to 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 are known to be equivalent to ReLU FNNs [19] , this reveals an equivalence between ReLU MPNNs and ReLU FNNs: they represent exactly the same class of functions, namely, continuous piecewise linear maps (CPLMs).This equivalence in 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 permutationequivariant layers that employ permutation-invariant 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] for 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 as 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. In order to 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-wise 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 hypersurfaces; i.e., the set of points where two or more tropical monomials achieve the same value.We summarize our key contributions in Figure 1 . We now proceed to reviewing some related works.Tropical Geometry and Machine Learning. Tropical geometry [22, 23] provides tools to study the algebraic geometry and combinatorics 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 [25] . The decision boundaries of FNNs through a tropical lens were studied in [26] . Other aspects of deep neural networks have also be analyzed [27, 28, 29, 30, 31, 32] . We refer to [33] for a survey on the current use of tropical geometry in deep learning.Expressivity and WL. Much work on GNNs has been inspired by noticing the parallels between MPNNs and the WL test for isomorphism [15, 34, 35] . Standard MPNNs are 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 as geometric WL [36] , cellular WL [37] ,temporal WL [10] , and persistent WL [38] have been introduced in different contexts. Limited expressivity and symmetry considerations have led to the design of new MPNN architectures [15, 39, 40, 41, 42, 43] , inclusion of different types of features [39, 44] , 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 to be prone to information bottlenecks [50, 51, 52] , oversmoothing and oversquashing [53] , and heterophily [54, 55] . Some works have also established their inability to count substructures, compute graph properties, or learn topology [49, 56, 57] ; connections to algebraic topology [58] , biconnectivity [59] , and communication complexity [60, 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, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75] .However, neither expressivity in terms of WL 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 terms of the number of linear regions [76, 77, 78, 79] , and the intricacy of decision boundary [19] , though other notions such as trajectory length [80] 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. 
message passing neural networks (mpnns): 
 A general T -layer MPNN χ is defined as a sequence of layers {φ (t) } T t=1 , and takes as input a(directed) graph G = (V, E, X) with vertices v ∈ V , edges (u, v) ∈ E ⊆ V × V , and features X = (X V , X E ) consisting of node attributes X V ∈ R |V |×d0 and edge attributes X E ∈ R |E|×d ′ 0 .It produces as output a refined embedding for each vertex and edge. Formally, χ acts on X asχ(X) = φ (T ) • ... • φ (1) (X) , where each φ (t) : R |V |×dt-1 × R |E|×d ′ t-1 → R |V |×dt × R |E|×d ′ tis permutation-equivariant [20] . Subsequently, depending on the task, the embedding for each node produced by χ is fed into another neural network, e.g., η : R d T → R out for node classification or regression (and similarly for edges). An additional readout step φ Readout : R |V |×d T ×R |E|×d ′ T → R d G is usually required to obtain a single vector from the output of χ for graph-level prediction.We thus proceed to describing the working of each layer φ (t) that yields a representation h(t) v ∈ R dt for each vertex v ∈ V and a representation e (t) uv ∈ R d ′ t for each edge (u, v) ∈ E.Assuming node embeddings are updated before edge embeddings (the converse works analogously), we haveh (t) v = φ (t) Update (h (t-1) v , m (t) v ), where m (t) v = φ (t) Agg (h (t-1) v , {{h (t-1)u , e (t-1)uv , e (t-1) vu |u ∈ Ne(v)}}) .Agg } are typically permutation-invariant, and we use an operator □ such as sum, average, or coordinate-wise max/min to combine the messages [15, 81] : 2 ). On the other hand, the update functions take the formφ (t) Agg (h (t-1) v , {{h (t-1) u , e (t-1) uv , e (t-1) vu }} u∈Ne(v) ) = ϕ (t) 1 (□ (t) u∈Ne(v) ϕ (t) 2 (h (t-1) v , h (t-1) u , e (t-φ (t) Update (h (t-1) v , m (t) v ) = σ (t) Update (W (t) self h (t-1) v + W (t) neigh m (t) v ). Henceforth, we focus on sum and coordinate-wise max, since coordinate-wise min and average can be obtained from coordinate-max and sum respectively. We shall also number the vertices in V with A 1 , ..., A |V | and edges in E with e 1 , ..., e |E| , and use the lexical order for edges, i.e., e uv < e u ′ v ′ ⇔ u < u ′ or (u = u ′ and v < v ′ ) .Here we adopt the notation from [19] . Let T = R ∪ {-∞} be an extended set of real numbers. We equip T with two binary operators tropical sum ⊕ and tropical multiplication ⊙:a ⊕ b = max{a, b} ; a ⊙ b = a + b ; a ⊕ -∞ = -∞ ⊕ a = a ; a ⊙ -∞ = -∞ ⊙ a = -∞ ,where max and + are the usual operators in R. Thus, (T, ⊕, ⊙) is a semi-ring with additive identity -∞ and multiplicative identity 0. We also define the tropical power x ⊙a for each x ∈ R:x ⊙a = x ⊙ ... ⊙ x = a • x if a ∈ N (-x) ⊙(-a) if a ∈ Z \ N , -∞ ⊙a = ∞ if a ∈ N \ {0} 0 if a = 0 ;where • is the standard product over R, and often abbreviate x ⊙a to x a without inducing any confusion. A tropical monomial in m variables takes the form c ⊙ x a1 1 ⊙ ... ⊙ x am m for c ∈ T and a 1 , ..., a m ∈ N, and is often denoted by multi-index shorthand cx α , where α = (a 1 , . . . , a m ) ∈ Z m and x = (x 1 , . . . , x m ) ∈ R m . Note that this may be interpreted as the affine combination x ⊤ α + c.A tropical polynomial f (x) = c 1 x α1 ⊕ ... ⊕ c r x αr is a finite tropical sum of tropical monomials, and amounts to a max over finitely many terms, i.e., f (x) = max r i=1 {x ⊤ α i + c i }. Without loss of generality, we assume α i ̸ = α j for i ̸ = j since we can combine monomials with the same α into one. A tropical rational function f ⊘ g(x) = f (x) -g(x) is the difference between two tropical polynomials. A map F : R m → R p with each component a tropical polynomial [resp. tropical rational function] is called a tropical polynomial map [resp. tropical rational map], and belongs to the set P ol(m, p) [resp. Rat(m, p)].When we allow α i ∈ R m instead of restricting its components to integers (α i ∈ Z m ), we obtain a tropical signomial function/map [resp. tropical rational signomial function/map] instead of a tropical polynomial/map [resp. tropical rational function/map]. It is known that each tropical rational signomial map (TRSM) is a continuous piecewise linear map (CPLM) and vice versa [19] . 
tropical algebra of mpnns: 
 In this section, we characterize the class of functions learned by ReLU MPNNs, whose activation functions for both nodes and edges (i.e., those used for η, ϕ(t) 1 , ϕ (t) 2 , σ (t)Update , etc.) are of the form:σ (l) (x) = max{x, t (l) }, where t (l) ∈ (R ∪ -∞) n l .In particular, note that σ (l) (x) = x when t (l) = -∞. In contrast, t (l) = 0 purges all negative inputs. Let F ReLU MPNN , F ReLU FNN , F CPLM , F TRSM 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 1 ( [19] ). F ReLU FNN = F CPLM = F TRSM .We will now extend this result to establish equivalence with F ReLU MPNN . Equating ReLU MPNNs with CPLMs is rather nuanced, since nodes in each layer share the weights. Therefore, we employ two reductions showing (1) × R |E|×d ′ → R |V |×dout × R |E|×d ′ out ; 2.Tropical rational signomial maps (TRSMs) F ⊘ G : R m → R p ; 3. Continuous piecewise linear maps (CPLMs) ψ : R m → R p ; 4. ReLU FNNs ν : R m → R p . Remark 1. In contrast to the WL test, which exposes the limitations of MPNNs via injective hash functions, Proposition 1 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 1) does not explain the observed empirical discrepancy between ReLU MPNNs and ReLU FNNs in practice. This motivates our subsequent analysis and results (Section 5 and Table 1 ), 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.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 crossreferenced. • All assumptions should be clearly stated or referenced in 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 to provide a 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. 
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 a CPLM f : R m → R p , we define its linear degree N (f ) to be K, where K is the least number of connected regions Ω k of R m such that the restriction f | Ω k is affine. Equivalently, following [82] , we can also define K = N (f ) as follows: f : R m → R p is a CPLM if f is continuous and there exists a set {f k : k ∈ {1, ..., K}} of affine functions and maximal connected subsets (Ω k ) K k=1 satisfying the following conditions:Ω i ∩ Ω j = ∅; K k=1 Ω k = R m ; f | Ω k = f k .Similarly, we define the convex degree N c (f ) where we require additionally that Ω k is convex. We further define N c (f |m ′ ) as the maximum convex degree across restrictions of f to different m ′ -dimensional affine subspaces of R m , m ′ ≤ m. We will analyze general upper and lower bounds on N (χ) for a ReLU MPNN χ. To analyze the number of linear region for a ReLU MPNN χ, we make a simplifying assumption that all input graphs to χ have the same graph structure G. In 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 complexity is building a ReLU FNN that can be applied on the vectorized input H (t-1) of all node embeddings h (t-1) v . Using the notation indicated in Equation 1, we form a ReLU FNN Φ (t) 2 that achieves the same effect as ϕ (t) 2 for every adjacent node embedding. The aggregation operator can be seen as either a matrix multiplication for sum, or a FNN Φ (t) 3 for max aggregation -the difference between these two cases will be discussed in Section 4.3. Similarly, we form a ReLU FNN Φ(t) 1 for ϕ (t) 1 , which in combination with Φ (t) 2 and Φ (t)3 can be seen as a ReLU FNN Φ (t) Agg . Our next proposition is important in the analysis for geometric complexity of χ, as it relates the geometric complexity of the model up to the t + 1-th layer to that of the t-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 H (t) ∈ R |V |dt and show that the result of t-th message aggregation step can be written as a result of a FNN Φ tAgg (H (t) ). 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 4.3). Proposition 2. [Recursive formula for geometric complexity]N (φ (t+1) ) ≤ N c (φ (t+1) ) ≤ N c (φ (t+1) Update ||V |(d t + dt+1 )) N c (Φ (t+1) Agg ||V |d t ) N c (φ (t) ).(EQUATIONThe ideas and proofs for Proposition 2 build on [19] , and the details can be found in the Appendix.We note that the lower bound on the linear degree of χ depends heavily on the choice of weights and biases; e.g., setting their value to 0 trivially results in N (χ) = 0. Thus, a lower bound on the geometric complexity (i.e., maximal linear degree) is of greater interest. In this subsection, we will provide a general lower bound for the maximum number of linear regions for a ReLU MPNN, building on the work of [76] . Theorem 3. [Lower bound on the maximum number of linear regions] Assume for all t, l, we haven t,l 1 , n t,l 2 ≥ d 0 and let n t,l 1,d0 = n t,l 1 d0 d0 and n t,l 2,d0 = n t,l 2 d0 d0then the maximum number of linear regions of functions computed by any ReLU MPNN is lower bounded byS t0 T t=1 L (t) 1 l=1 n t,l 1,d0 L (t) 2 l=1 n t,l 2,d0 n T,L (T ) 1 1,d0 d0 j=0 d T j ,where t 0 is the number of MPNN layer having max as aggregation operator and for each layer t, the index l runs through every layer in ϕEQUATIONWe now sketch some intuition about this result. We can add toΦ (t)1 (constructed in Algorithm 3 in the Appendix) an initial layer to calculate □ (t) = , while the aggregation □ (t) = max can be seen as a FNN-layer with rank S max activation, thus we can identify S input regions (indicated in red). By setting φ(t) Update (h (t-1) v , m (t) v ) = m v ,we can express the whole MPNN χ as a FNN applied to input X (details in Algorithm 1, 2 and 3 in the Supplementary). We build on the analysis in [76] to construct intermediate layers that identify n t,l d0 d0 input regions. Our procedure amounts to sequentially folding the input space until the last layer (indicated in blue), and then replicating the hyperplane arrangement in the last layer (indicated in green).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 integer-weighted ReLU MPNNs. A result similar to Proposition 1 establishes 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 in the following sense: each intermediate dimension n t,l 1 and n t,l 2 of ϕ(t) 1 and ϕ (t)2 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., [19] . Theorem 4. [Upper bound on the geometric complexity] Let χ : R |V |d0 → R |V |d T be an integerweight ReLU MPNN. If φ (t) satisfies the following conditions for all MPNN layer t = 1, .., T• n t,l 2 ≥ D |V | d t-1 for all l = 1, ..., L (t) 2 ; • n t,l 1 ≥ d t-1 for all l = 1, ..., L (t) 1 ; • n t,L (t) 1 1 + d t-1 ≤ d t ;then the linear degree of H (T ) is at mostT t=1   L (t) 1 -1 l=1 |V |dt-1 i=0 |V |n t,l 1 i   from Φ (t) 1   L (t) 2 -1 l=1 |V |×dt-1 i=0 Dn t,l 2 i   from Φ (t) 2   |V |( dt+dt-1) i=0 |V |d t i   from φ (t) Update N c (□ (t) ),whereN c (□ (t) ) ≤ 1 if □ (t) is sum, 1 2 (8S) D dt if □ (t) is coordinate-wise 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-weights) established in [19] and [21] respectively as special cases.Corollary 1. The linear degree of an integer-weight FNN is at mostT t=1 d i=0 dt i . Corollary 2.The linear degree of a GCN χ with T hidden layers, ReLU activation, sum aggregation and integer weight is at mostT t=1|V |dt i .On the other hand, we obtain new bounds for popular GNN models, particularly GraphSAGE [13] and GIN [15] . For GraphSAGE, note that the normalization steps do not change the linear degree.Corollary 3. Let dt be the output dimension of Aggregate t in GraphSAGE [13] . If d t ≥ d t-1 + dt ≥ 2d t-1 for all MPNN layers t = 1, ..., T , then the linear degree of integer-weighted ReLU GraphSAGE described in [13] is upper bounded byN c (φ T ) . . . N c (φ 1 ),whereN c (φ t ) ≤ 2|V |dt-1 i=0 |V |dt iif the aggregation step is mean,|V | d-1 i=0 |D| dt i |V |( dt+dt-1) i=0 |V |dt iif the aggregation step is pooling. Let n t,i be the dimension of each of the intermediate layer in the M LP (t) , then its linear degree N c (χ) ≤ T t=1   L (t) -1 l=1 |V |dt i=0 |V |n t,l i   .N (□ (t) ) = 1 if □ (t) = , S min{|V |,D} dt ≤ N (□ (t) ) ≤ min |D|dt+1 i=0 S 2 |V | dt i , S |V | dt if □ (t) = max .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 thatN (□ (t) ) = S |V | dt if □ (t) = max.In that case, the geometric complexity will grow polynomially with S (maximum degree).Remark 2. Interestingly, in [15] , the authors point out that if ϕ 1 and ϕ 2 are injective, then χ is as powerful as the WL test. Under that assumption, coordinate-wise is less "expressive" than mean, which is less "expressive" than sum.In contrast, ϕ 1 and ϕ 2 are not injective in our case (since ReLU activation is not 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it 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.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• 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 a specific model and empirical evaluation, it may be necessary to either make it 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 NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or 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.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
new relu mpnns architectures and complexity tradeoffs: 
 Note that while both ReLU FNNs and ReLU MPNNs learn TRSMs/CPLMs (Proposition 1), 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 a 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 a 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 on TSFs, i.e., functionsf : R m → R of the form f (x) = ⊕ r i=1 c i ⊙ x ⊙αi , where c i ∈ R, α i ∈ R m .Our idea is to construct as input a clique (i.e., a fully-connected graph) with m nodes A 1 , . . . , A m and distribute the r monomials (almost) evenly such that each node A i contains r ′ = r m monomials (padding with zero monomials if m • r ′ > r). Our construction makes use of a comparison gadget which is already introduced in [19] and [83] , and introduces a 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 i , simultaneously using coordinatewise max aggregation. Now redistribute (using the selection gadget) the resulting O(r ′ ) maximum monomials (each coordinate yields one such monomial) evenly across the nodes, and recur until the maximum across all monomials is obtained.Local comparison: First employ a recursive procedure to compare r ′ monomials assigned to each A i locally in order to find a maximum monomial for A i (breaking ties arbitrarily). Now compare the maximum monomials across the nodes using a single global comparison described above.One limitation of both these architectures is that they can make no more than m comparisons at a time but r can be much larger. Fortunately, a theorem due to [84] , also exploited previously by [83] , motivates our construction of a Constant MPNN consisting only a 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 Φ 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 r tropical monomials and then employ a single layer of MPNN over an r-clique with coordinate-max to learn f . Proposition 6. There exist ReLU MPNN algorithms (Local, Global, Constant, and Hybrid that can learn any TSF f : R m → R with r monomials. Their respective complexity and tradeoffs are summarized in Table 1 .We provide details about these algorithms and proofs of their correctness as well as complexity in the Supplementary. 1 : Complexity of representing any tropical signomial function (TSFs) f : R m → R consisting of r tropical monomials with different architectures. One more layer is required to compute any tropical rational signomial map (TRSM). The four new methods introduced here construct a graph (based on m and r) and leverage message passing to efficiently compare these monomials.Agg applied to H (t-1) 6. Lastly, we obtain H (t) ∈ R |V |×dt by performing the φ (t) Update .We proceed with the first step. (t) 1 , Φ (t) 2 (Φ (t)3 ) are applied to the corresponding stacked vector as a whole.Input: Stacked vector H (t-1) ∈ R |V |dt-1 of embedding of all vertices. We will only describe the construction for weight, the bias could be done analogously. Let W t,l 2 and n t,l 2 be the weight and number of output nodes of the ℓ-th layer of ϕ(t)2 respectively (n t,0 2 = d t-1 ). Thus, W t,l 2 ∈ R n t,l ) respectively.2 ×n t,l-1 2 . For the first layer l = 1, let W t,1 2 = W t,1 2,1 , W t,We now define the weight forΦ (t)2 . In the first layer ofΦ (t) 2 , W t,1 2 ∈ R Dn t(1) 2 ×|V |dt-1 by breaking it into blocks [ W t,1 2 ] κ,κ ′ of size n t,1 2 × d t-1 .For each edge κ-th (according to the ordering of edges), assume it is (A i , A j ), then, we setEQUATIONThe remaining layers ℓ are easy to build: let W ϕ (t) 2 (h (t-1) Ai , h (t-1) Aj ) = W (t),1 2 h (t-1) Ai h (t-1) Aj = W t,1 2,1 h (t-1) Ai + W (t,1 2,2 h (t-1) Aj .There are D edges in total, thusEQUATIONandH (t-1) =    h (t-1) A1 ... h (t-1) A |V |   . For the κ-th edge (A i , A j ), we want X (t) κ = ϕ (t) 2 (h (t-1) Ai , h (t-1) Aj), the formula (3) will yield the desired result.Then applying the following layers Φ Y (t) = M X (t) ,where M is a 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Φ (t) 1 .Proof. We first build M ∈ R |V | dt×D dt , by breaking it into blocks of size dt × dt . Then each blockM κ,κ ′ = Id dt× dt if edge κ ′ = (A κ , A j ) ∈ E 0 otherwise .It is easy to see that Y (t) = M X (t) , since the matrix M is the same as the adjacency matrix A of G replacing 1 with Id dt× dt .On the other hand, when the operator □ (t) is coordinate-wise max-min, the analysis becomes a little bit more complicated. In particular, we can create a neural network Φ (t)3 to represent its effect. In the Algorithm 2, we want to make use of the comparing architecture in [83] . A minor blockage is the appearance of the weight 1/2 in the comparing layer. Fortunately, by scaling the input by a factor of 1/2 (which does not change the number of linear regions) and scaling the weights by a factor of 2, we could solve this problem. We note that Φ Input:X (t) ∈ R D dt .We first scale all entries in the input by 1/2. Then we create a FNN that resembles the construction in [83] , however, we will not compare two consecutive nodes, but the comparison is done according to the edges of the graph. Proposition 11. If □ (t) is coordinate-wise max/min, thenY (t) = Φ (t) 3 (X (t) ),where Φ (t) 3 is built according to Algorithm 2. Remark 4. Here, we surmise that if we have a 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 ϕ (t) 1 to form the transformation of the aggregated message. Similar to step 2, we would want to build Φ (t) 1 that is applied on the whole Y (t) as a vector. However, this is much easier to form ϕEQUATIONEQUATIONInput:EQUATION×|V |n t,l 1 be the weight of the ℓ-th layer of ϕ(t) 2 , Φ (t) 2 respectively. Then W t,l 1 =   W t,l 1 0 ... 0 0 W t,l 1 ... 0 0 0 ... W t,l 1  and applied the activation accordingly.Obviously, since each component is applied separately, we have the following proposition. Proposition 12.([EQUATION)Proof of Theorem 3. By Proposition 9, Proposition 13 and Proposition 11, we note that each Aggregation step φ(t)Agg can be written as a FNNs Φ (t)Agg applied to H (t) . Note that □ (t) = can be absorbed by the first layer of Φ (t)1 (constructed in Algorithm 3). On the other hand, □ (t) = max can be seen as a max-out layer with rank S). Thus, by [76, Theorem 8 proof] , it can identify S regions of the input. Then if φ(t) Update (h v , m v ) = m v then we can write H (t) = Φ (t)Agg (H (t-1) ). Thus, by [76, Theorem 4] , we have the maximum number of linear region of functions computed by any ReLU MPNN is lower bounded byS t0 T t=1 L (t) 1 l=1 n t,l 1,d0 L (t) 2 l=1 n t,l 2,d0 n T,L (T ) 1 1,d0 d0 j=0 d T j ,Upper bound on geometric complexity Remark 5. If the neural network ϕ(t)2 has n t,l 2 output nodes in its ℓ-th hidden layer, then the neural networkΦ (t) 2 have Dn t,l2 nodes in its ℓ-th layer. Therefore, the number of output nodes and hidden layer nodes depend on the connectivity of the network.Proposition 13. If the neural network ϕ (t) 1 , ϕ (t) 2 has n t,l1 , n t,l 2 number of nodes in its ℓ-th hidden layer then the neural networkΦ (t) 1 , Φ (t) 2 have |V |n t,l1 , |D|n t,l 1 number of nodes in its ℓ-th layer. Thus, ifEQUATION• n t,l 1 ≥ d t for all l = 1, ..., Lthen applying [19, Theorem 6.3] , we obtain an upper bound for convex degree:EQUATION)convex linear regions, whereEQUATIONProof. If □ (t) is coordinate-wise max/min, thenΦ (t)3 has ⌈log 2 S⌉ + 1 layers. For ease of analysis, we can assume each hidden layer has D dt nodes (this only increase the convex/linear degree) except for the first layer with at most 2D dt nodes, thus from [19, Theorem 6.3], we have N c (Φ (t) 3 ) ≤   D dt i=0 2D dt i   ⌈log 2 S⌉ l=1 D dt i=0 D dt i = 2 2D dt-1 • 2 D dt⌈log2 S⌉ , as n i=0 2n i = 2= σ (t) Update • ρ (t) Update : R |V |( dt+dt) → R |V |dt . If |V |( dt + d t ) ≤ |V |(d t ), i.e. dt + d t ≤ d t , then N c (σ Update • ρ|( dt + d t )|V |) ≤ |V |( dt+dt) i=0 |V |d t i .The following results together yield an important Proposition that allows us to analyze each component of φ (t) separately before combining them. The following lemma is trivial, but we provide a proof for completeness.EQUATIONProof. We invoke the fact that if F is an affine transformation of R n and A ⊂ R n is convex, then the image F [A] is also convex. Thus, a convex linear region in N c (F |d) is still a convex and linear region in N c (F ), and vice versa. On the other hand, some convex linear regions in R n do not intersect the affine space, resulting in the inequality.We first recall [19, Theorem D.3] : Let F, G in Rat(m, p) and Rat(m ′ , m). Let H = (h 1 , ..., h p ) ∈ Rat(m ′ , p) defined by h i := f i • G for i = 1, .., p. Then N (H) ≤ N c (H) ≤ N c (F |m ′ ) • N c (G).Proof of Proposition 2. We note thatEQUATIONthus using [19, Theorem D.3] , we haveEQUATION) Note that φ (t) (H (t-1) ) = φ (t) Update (φ (t)Agg (H (t-1) ), H (t-1) ) thusEQUATIONWe can further break the terms N c (φ(t)Agg ) down by noticing that φ(t) Agg = Φ (t) 1 • □ (t) • Φ (t)2 , applying in [19, Theorem D.3 ] multiple times and Lemma 4.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, which tells us that we could analyze the model in steps. Thus, bringing the pieces together, we haveT t=1   L (t) 1 -1 l=1 |V | dt i=0 |V |n t,l 1 i   from Φ (t) 1   L (t) 2 -1 l=1 |V |×dt-1 i=0 Dn t,l 2 i   from Φ (t) 2   |V |( dt+dt-1) i=0 |V |d t i   from φ (t) Update N c (□ (t) ),whereN c (□ (t) ) = 1 if □ (t) is sum 1 2 (8S) D dt if □ (t)is coordinate-wise max/min . 
decision boundary: 
 Lastly, we proceed to characterizing the decision boundary of integer-weighted ReLU MPNNs for classification. We focus on binary classification tasks with a single output to keep the exposition transparent and explicit, albeit one can adapt our construction and analysis accordingly to accommodate 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 2 that we need an additional readout step φ readout : R|V |×d T × R |E|×d ′ T → R d G prior to classification η, i.e. χ : R d×|V | × R d ′ ×|E| φ (T ) •...•φ (1) --------→ R d T ×|V | × R d ′ T ×|E| φReadout ----→ R d G η -→ R.Let γ : R → R be an injective score function. For c ∈ R in Im(γ), we define the decision boundary of χ asB = {z ∈ R m : χ(z) = γ -1 (c)}, where m = d|V | + d ′ |E|. The tropical hypersurface T (f )is precisely the set of points x where f is not linear; i.e., two or more monomials in f achieve the value of f at x. We adapt a result from [19, Proposition 6.1] to arrive at the following proposition. B ⊆ T (γ -1 (c) ⊙ g ⊕ f ) .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 η : R d T → R is applied to the embedding of each node simultaneously, and a scoring function γ i : R → R is then employed for each node to predict its class based on its score c i . Generally, different scoring functions γ i 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 Γ :R |V | → R |V | , [Γ(z)] i = γ i (z).However, we immediately hit a roadblock, since choosing a meaningful order for c i is 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|V | i=1 B i , where B i = {z ∈ R m : ν i (z) = γ -1 i (c i )}.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. Then χ can be viewed as a tropical rational map F ⊘ G and its decision boundary is contained in the tropical hypersurface of a specific tropical polynomial, namely,B ⊆ |V | i=1 T (γ -1 (c i ) ⊙ G i ⊕ F i ).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 in the context of ReLU FNNs, our analysis expands the scope to a widely employed class of GNNs, laying the 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 is rather analytical; a 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 ReLU MPNNs (see Remark 2 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 to ReLU FNNs. Remark 3, Proposition 6 and Table 1 show 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 to be able to represent the same CPLMs. We however, sidestepped other important and practical considerations such as the difference in training time, prediction error and the role of optimisation algorithm (e.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 on design and analysis of modern deep architectures through the fruitful machinery of tropical geometry.We first recover the upper bound for FNNs and GCNs (with ReLU activations and integer-weights) established in [19, Theorem 6 ] and [21, Theorem 4] respectively as special cases. The one for FNN is 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 ϕ (t) 1 = Id, □ (t) = sum, and φ (t) Update = Z (t) , where Z (t) is just a stacked vector of m (t)Ai . With this simplification, we can in fact have a stronger version of Proposition 2 (going down to input layer):N c (χ) ≤ T t=1 N c (□ (t) • Φ (t) 2 ||V |d 0 ) ≤ T t=1   |V |d i=0 |V |d t i   (by Proposition 10, □ (t) is just linear transformation).Proof of Corollary 3. In both case, we note that ϕ (t) 1 = id, thus, we can forget the contribution of Φ 1 . If the aggregation operator is mean, we can substitute □ (t) = , then ϕ (t) 2 = id and φ Update stays the same. Thus, we haveEQUATIONIf the aggregation operator is pooling, then ϕ2 is a one-layer FNN, □ (t) = max and φ Update stays the same. Thus, we haveEQUATIONProof of Corollary 4. According to [15, Equation 4.1], by adding a self-edge to each node in the graph, t-th layer of GIN can be written as □ (t) = (or affine transformation -which does not change the geometric complexity), ϕ(t) 2 = id and ϕ (t) 1 = M LP indicated, thus N c (χ) ≤ T t=1   L (t) -1 l=1 |V |dt i=0 |V |n t,l i   .In most of the following architectures, the aggregated message has the following form,EQUATIONi.e., the aggregated message to node A i depends only on the neighboring nodes A j (and not A i itself).Lemma 5. Let F ⊘ G : R m → R p be a TRSM. Suppose each component F i of F can be represented by an FNN/MPNN with L Fi layers, and G i of G by an FNN/MPNN with L Gi layers. Then F ⊘ G can be represented as an L-layer FNN/MPNN with L ≤ max p i=1 {max{L Fi , L Gi }} + 1.Proof. The main idea underlying our proof here is to exploit parallelization. Firstly, for FNNs, we can compute all F i and G i in parallel using max n i=1 {max{L Fi , L Gi }} 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 i ⊘ G i , again in parallel, for all i = 1, .., n. Similarly, for MPNNs, we construct F i and G i 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 ϕ(t) 2 , ϕ (t)1 to zero and W (t) self to identity. Lastly, to compute the difference F i and G i , we just need one additional MPNN layer where aggregation part is 0 (ϕ ) is sum or coordinate-wise max), and(L) 2 , ϕ (L) 1 = 0; □ (LW (L) self = [Id p×p -Id p×p ].We provide an overview and detailed algorithms for the gadgets here. The broadcast gadget sets up an MPNN by replicating its input across nodes of a fully connected graph. It also endows each node with its ROE. The selection and comparison gadgets are implemented as FFNs: the former is used for partitioning the monomials across the nodes, whereas the latter determines the larger of its two input monomials.Broadcast gadget. Given an input vector x ∈ R m , we first construct a fully connected graph with m vertices A 1 , ..., A m . The feature vector for A 1 is constructed as follows: first m coordinates comprise x, the next coordinate is set to 1 (for bias), and the last m coordinates are set to ROE 1 m -e 1 . The feature vectors for all other nodes A i consist of m + 1 zeros followed by 1 m -e i . A parameterized message passing layer with weights determined by a target TSF f is then learned to compute all the r monomials p 1 , p 2 , . . . , p r of f . We provide all the details, including the operators in Algorithm 4. It can be shown that the embedding of node A i after broadcasting is p 1 , p 2 , ..., p r , (1 m -e i ) ⊤ ⊤ .Build an m-clique with vertices A 1 , ..., A m and bidirectional edges, and introduce loops with m self-edges from each vertex A i to itself. Prepare node embeddings. For A 1 , we set its first m coordinates to the input x, the next coordinate to 1 for bias, and then the final m coordinates set to its ROE 1 m -e 1 . For other nodes A i , we instead have a vector with first m coordinates set to 0, followed by a single coordinate 0 for bias and finally their respective ROE 1 m -e i .Finally, we construct a layer of message passing. Specifically, ϕ2 is a 1-layer FNN with identity activation, no bias, and has the form of Equation 14. Its weight matrix isC ∈ R r×(m+1) 0 r×m 0 m×(m+1) 0 m×m ,where each row C i,: = [α i , c i ] ∈ R m+1 . We use the sum aggregation operator and setEQUATIONUpdate has identity activation, WEQUATIONEQUATIONThe following result follows immediately from Algorithm 4. Proposition 14. The embedding of vertex A i after broadcasting with Algorithm 4 is p 1 , p 2 , ..., p r , (1 m -e i ) ⊤ ⊤ , where p i is the i th affine combination (or tropical monomial) of f . Furthermore, the Broadcast Algorithm 4 uses in total 2 FNN layers across 1 layer of message passing and (2m + 1)(r + m) parameters of which (m + 1)(r) = O(rm) are learnable.We now describe the selection gadget that we invoke to distribute r monomials (almost) evenly among the nodes such that the node A i gets monomials pī = {p k : k mod m = i}. Selection gadget. It is a FNN with two layers that acts on the embeddings produced by the Broadcast gadget and utilizesξ ζ 1 -1 -∞ -∞ 1 -1 (a) Gadget for selecting ξ (Lemma 6) p1 p2 max{p1, p2} 1 -1 -1 1 1 -1 1 -1 1 2 -1 2 1 2 1 2(b) Comparison gadget (following [83] )Figure 2 : Orange, green, and magenta nodes represent input, hidden (with activation max{•, 0}) and output (with activation max{•, -∞}) units respectively. (Left) ζ can be used as a control to either let ξ pass or filter it through the network. Note that in practice a sufficiently small negative weight can be used instead of -∞. (Right) A gadget that yields the greater of its two inputs as the output. Proof. If ζ = 0, then the values at the two nodes in the hidden layer are ξ and -ξ respectively before activation, and ξ and 0 after activation. Thus, the final output in this case is ξ.EQUATIONOn the other hand, if ζ = 1, then the two nodes in the hidden layer take values -∞, -∞, respectively before activation, and thus 0 and 0 after activation. Thus, the final output in this case is 0. Proposition 15. Node A i , after selection with Algorithm 5, only contains the monomials pī of f .Proof. Note that this result is just a generalization of Lemma 6, in the sense that we now distribute r monomials into batches of size m (with each monomial playing the role of ξ) across the m nodes with coordinates from ROE playing the role of ζ. The two layers return 0 when ζ = 1 and ξ when ζ = 0. Note that there is only one 0 in the i th position of ROE 1 m -e i for A i , so A i ends up with all the monomials pī after the second layer.We are now ready to describe all the models, namely the Local, Global, Constant and Hybrid algorithms to compute a TSF f : R m → R. The second layer of MPNN is designed as follows. ϕ(2)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 rows with all coordinates set to 0 to the weight matrix for the second layer in Algorithm 5.Thus, the weight matrix is now of dimensions (r ′ + m) × 2r.□ (2) is coordinate-wise max and ϕEQUATIONUpdate uses identity activation, W We then repeat this process (replacing r with r ′ until we are left with only 1 component and the final maximum f ). This requires ⌈log m (r)⌉ additional MPNN layers.the same result for every node A i 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 i=1,...,r p i = f (x). 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 m (r)⌉ + 1 MPNN layers, including the first Broadcast layer.Algorithm 8 Constant MPNN First, we perform a broadcast with Algorithm 4.We only need one additional message passing layer. ϕ2 however needs to be modified since for each node A i , we would want to have l zj,i for each j = 1, .., q suggested by S j instead of lī that Proposition 15 guaranteed. Specifically, in the first layer of ϕ (2) 2 , we now have 2dr hidden nodes (2d nodes for each l i ), ReLU activation, no bias, and a weight matrix ∈ R 2dr×(r+d) with weights.EQUATION)We now choose the linear pieces according to S j . The second layer of ϕ2 has 2q hidden nodes, identity activation, no bias and weights ∈ R 2q×2dr given byw κκ ′ =              1 if κ ′ = 2m(z µ,i -1) + 2i -1 for i = 1, .., m and κ = 2µ + 1, 1 if 2m(z µ-1,m+1 -1) + 1 ≤ κ ′ ≤ 2mz µ-1,m+1 , κ ′ odd, and κ = 2µ -1 if κ ′ = 2m(z µ,i -1) + 2i for i = 1, .., m and κ = 2µ + 1, -1 if 2m(z µ-1,m+1 -1) + 1 ≤ κ ′ ≤ 2mz µ-1,m+1, κ ′ even, and κ = 2µ, 0 otherwise.For the next layers in ϕ(2)2 , we take the maximum of node 2κ + 1 and node 2κ using two layers of the comparison gadget.The aggregation function is coordinate-wise max, ϕEQUATIONUpdate uses identity activation and W • 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-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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is no societal impact of the work performed as the work is purely theoretical.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 out 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 as 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 or unintentional) misuse of the technology. • If 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 ML). 
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 (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.

3. It is unclear how the input graph's spectral properties affect the geometric complexity of ReLU MPNNs within the established bounds.

4. 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.

Other Comments:

1. Line 123: $x_d^{a_m}$ should be $x_m^{a_m}$.

2. What does $D$ stand for in Theorem 4?

3. 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.
questions: questions: Please refer to the Weaknesses.
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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) 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.

In 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.
questions: 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?

The 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?

Also, 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: limitations: The limitations were discussed throughout the paper in the form of remarks and a discussion in the concluding remarks.
paper_summary: paper_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.

This 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.
strength_weakness: strength_weakness: 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.

I 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:
- 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?
- How far apart are these bounds from practice? 
- 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?

From 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. 

Proposition 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?

Proposition 2: 
- 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. 
- 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.

Theorem 3: 
- 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.
- 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. 
- Can the authors define the notation $n^{t,l}$ before this and preferably even in the theorem statement itself. 
- 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? 
- 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. 
- Related to the above, how tight is this bound for a random network or one that is found on training?

Theorem 4:
- 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).
- 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? 
- See also notational concerns for theorem 3 that also apply here.


Section 4.4:
- What is PWLM? I assume piecewise linear map? This is not defined though.
- 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.
- Proposition 6 seems like a simple statement, and I wish the authors would explain more why this is nontrivial or useful to know.

Section 4.5:
- 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”?

Conclusion, 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.


Literature 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
neural networks count substructures). 



Smaller comments:
- 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.
- Notation $\mathcal{N}$ is overloaded as defining both linear regions and neighborhood.
- 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. 
- Line 225: what is “noval”?
questions: questions: See prior sections.
limitations: limitations: See prior sections.

Comments: title: A word of appreciation
Acknowledging authors' reply and responding
Continuation of the clarification thread...
Detailed comments for clarifications
comment: We would like to thank  the reviewers for their constructive feedback, and chairs (area, senior area, program) for their service. 

As detailed below in our individual responses to the reviewers, we've acted on all of the reviewers' comments and suggestions, and tried our best to address their concerns and questions, even the minor ones.  We commit to reflecting the promised edits (e.g., adding related references, fixing a notation in one of the results, etc.) in the updated version.  

We believe acting on the reviewers' feedback has helped us consolidate the contributions, and reinforced the strengths of this work.  

Many thanks!
Thanks - please see our response below. 

`The proposed notation is ok with me as long as it is correct.`
Yes, it is correct. We will update the notation as described in the previous post.  

`I would instead ask you to qualify your statements about generalization since they are to me not convincing and bordering on wrong.`
Could you specify what is wrong with what we said here, or in the paper, about generalization? Only at one place in the main text we mention generalisation in the context of gradient flow [66] (line 91). The referenced paper does use a bound on number of linear regions to get a generalization bound. Do you want us to remove this reference altogether?
The proposed notation is ok with me as long as it is correct. To be clear, this is not about being "willing to update/qualify" the results or "streamline the notation". As the definition is written now, the paper's results are not correct and this must be corrected. 

I also do not see the point of a discussion about relations to VC dimension when you do not have formal results and the obvious extension of your results produce far worse bounds on FFNs than existing work. I would instead ask you to qualify your statements about generalization since they are to me not convincing and bordering on wrong.
Thank you for your response. I think my score still accurately reflects my belief in the paper and I retain the score.
Greetings, and thank you for your thoughtful and constructive reply. We're glad to hear that your concerns and comments have been addressed. 

We will remove color-coding and the future direction on Chow group as you kindly suggested. Many thanks for also bringing to our attention the works by (Maclagan, D., & Sturmfels, B, 2021) and (Joswig, M., 2021). We will include, and appropriately position, these references in the updated version. 

We're grateful for your support for this work.
Greetings, and thank you for continuing the discussion - we're grateful for your engagement. We're willing to update/qualify notation pertaining to \mathcal{N}, as well as, appropriately position the work by Bartlett et al. in the context of generalization. 

**(On the definition of complexity)**:  We acknowledge that overloading $\mathcal{N}$ could be confusing. 

One way to take care of this would be as follows. Define $\mathcal{Q}(\mathcal{F}) =  \max_{f \in \mathcal{F}} \mathcal{N}(f)$ for a family of CPLMs $\mathcal{F}$ where each function $f$ corresponds to a different CPLM obtained with a particular choice of the weights. The lower bound in Theorem 3 can then be stated by replacing $\mathcal{N}(\lambda)$ in equation 2 of the paper with $\mathcal{Q}(\mathcal{F_{\lambda}})$ where we define $\mathcal{F}_{\lambda}$ to be the family of functions that can be represented by a specified ReLU MPNN architecture $\lambda$ with all possible settings of the weights. 

This would also make everything consistent with the rest of our notation that we adopt from  [Zhang, Naitzat, and Lim. Tropical geometry of deep neural networks, 2018.] 

Would you be fine with updating Theorem 3 as above, or do you have any other suggestions to streamline the notation?

**(On VC-dim)**:  Thank you for drawing our attention to the seminal work by Bartlett et al. We believe that our work has taken an important step by showing equivalence between ReLU MPNNs and ReLU FFNs -  both exactly represent CPLMs (though with different tradeoffs in terms of number of parameters etc. as summarised in Table 1) . The generalization analysis by Bartlett et al applies to piecewise linear networks so could potentially be leveraged (applied/adapted/extended) to exploit this connection of ReLU MPNNs with CPLMs.  

Indeed, we also agree that bounding VC-dim by $r$ can be very loose. In fact, this was the reason why we sidestepped the question of generalization in the current work, instead choosing to focus on other important aspects where our analysis and results made concrete, non-trivial contributions.  

We can add a discussion in the paper along these lines if you think that would be helpful? We also welcome any other suggestions you have in this context.

We hope our response alleviates your concerns. Please do let us know if there's any further clarification we can provide here or update the paper with.  Many thanks!
Dear authors, thank you for your thoughtful and detailed reply to my concerns and comments.  I am happy to read that you have considered them carefully and am satisfied with the proposed changes.  I additionally have read the other reviewers' reports and am satisfied with the authors' responses to them.

As mentioned in my review, I would prefer the color-coded theoretical results to be removed.  I also think it is important to remove the directions for future research if more context/details cannot be given (perhaps due to space constraints), because, upon rereading the paper as it stands, these ideas appear to be an ungrounded list of concepts from tropical geometry.

I would also add the following references on tropical geometry to the references list:
[1] Maclagan, D., & Sturmfels, B. (2021). Introduction to tropical geometry (Vol. 161). American Mathematical Society.
[2] Joswig, M. (2021). Essentials of tropical combinatorics (Vol. 219). American Mathematical Society.
As long as these changes are implemented, I am happy to keep my positive rating of the paper.
Thank you for your clarifications. I appreciate your attempts to render all these equations in markdown. No problem that they did not all render correctly.

I still have concerns about your answers.

**On the definition of complexity:** Your definition of $\mathcal{N}(f)$ does not seem to agree with the later statements. You state that the input of $\mathcal{N}$ is a continuous piecewise linear map (CPLM), but later on, your definitions apply to a family of such CPLMs since you take a maximum over all possible weights of the function. So the input to $\mathcal{N}$ should be a family of CPLMs. The way you phrase it here and in the paper is very confusing and simply not correct as far as I can tell.


**On VC dimension:** The VC dimension you describe bounded by $r$ is correct but incredibly loose. This bound can grow exponentially with the dimension or number of parameters. In contrast, standard VC bounds for neural networks of bounded width are typically on the order of the number of parameters. E.g. see work by Bartlett et al. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. So I am still very unconvinced this is a more informative notion of generalization.
Consider any ReLU MPNN $\mathbb{R}^{|V |\times d} \to  \mathbb{R}^{|V |\times d_T}$ such that 
  
  (1)  for $t = 1, \dots, T$, $\phi^{(t)}_1$ has $L^{(t)}_1$ layers: intermediate dimension is $n^{(t, l)}_1$ for the $l$-layer ;

  (2) for $t = 1, \dots, T$, $\phi^{(t)}_2$ has $L^{(t)}_2$ layers: intermediate dimension is $n^{(t, l)}_2$ for the $l$-layer;
   
(3) $t_0$ MPNN-layers have max as the aggregation operator. 
  
Then, the maximal number of linear regions of functions computed by any such ReLU MPNN  is lower bounded by 
    
$S^{t_0}  \left (  \prod_{t=1}^{T-1} \left ( \prod_{l=1}^{L_1^{(t)}}  \left \lfloor \frac{n^{t, l}_1}{d_0} \right \rfloor^{d_0} \prod_{l=1}^{L_2^{(t)}} \left\lfloor \frac{n^{t, l}_2}{d_0} \right\rfloor^{d_0} \right ) \right ) \left (\prod_{l=1}^{L^{(T)}-1} \left\lfloor \frac{n^{T, l}_1}{d_{0}} \right \rfloor^{d_0} \prod_{l=1}^{L^{(T)}-1} \left\lfloor \frac{n^{T, l}_2}{d_{0}} \right \rfloor^{d_0} \right ) \sum_{j=0}^{d_0} \binom{d_T}{j}$, 

where $S$ is the maximum degree of input graph $G$. 

(Apologies, despite our best efforts, the latex for the above equation does not render here in this environment). 

We will update the description of Theorem 3 as above to avoid any possible misinterpretations. 

Finally, we sketch below an argument that clarifies the connection of Geometric Complexity (GC) with generalization. We did not include this connection in the original submission, but provide it here based on your comments. 

**Geometric complexity and Generalization:** 
We claim that if the geometric complexity is upper bounded by $r$, then the VC-dimension is at most $r$. This immediately translates into a generalization bound (which can be loose though as we explain below) using a classical result from the statistical learning theory for the binary classification setting.   

Here's a proof sketch. Since there are (at most) $r$ linear regions, we can select one instance from each linear region to obtain a set of (at most) $r$ instances. We can assign a label for each region independently of others, and moreover, this label can be any of the two possibilities. That is we can "shatter" this set of instances. 

Moreover, we cannot shatter $r+1$ (or more) instances. This follows since, otherwise, by pigeonhole principle, at least one region will have two instances.  As a result, we cannot get perfect classification  for this region when these two instances have different labels. Thus, the VC-dimension cannot exceed $r$ (it can, however, be lower than $r$ since the upper bound for the geometric complexity can be loose).    

We will add a discussion in the paper to point this out as well. 

Thanks for your patience and for your constructive remarks that have helped us elucidate some subtle aspects of this work. We hope that this clarification thread has satisfactorily addressed your concerns. Please let us know if there's something else we can address or elaborate.
Thank you for the discussion, and apologies for any confusion. Indeed, we were hampered by the space constraints, which it seems led to some crucial misunderstandings. Below we provide detailed responses to address these.  We will also update the paper accordingly.

Let's first start with what we mean by the equivalence of functions. 

**Equivalence.** Consider the following sets of functions. 

 $\mathcal{F}_{\text{ReLU MPNN}}$ : the set of functions represented by all ReLU MPNNs. 

$\mathcal{F}_{\text{ReLU FNN}}$ : the set of functions represented by all ReLU FNNs.

$\mathcal{F}_{\text{CPLM}}$ : the set of all continuous piecewise linear maps.

$\mathcal{F}_{\text{TRSM}}$ : the set of all tropical rational signomial maps. 

By equivalence, we mean that (apologies for having to break the equations and mathematical descriptions below into separate lines due to math formatting issues here)

$\mathcal{F}_{\text{ReLU MPNN}}$
  
 $= \mathcal{F}_{\text{ReLU FNN}} $

$=\mathcal{F}_{\text{CPLM}}$ 

 $=\mathcal{F}_{\text{TRSM}}$

In other words, $f: \mathbb{R}^{m} \to \mathbb{R}^{p}$ is a CPLM
 
--- iff $f$ is a tropical rational signomial map 

--- iff $f$ can be represented by a ReLU FNN $\nu: \mathbb{R}^{m} \to \mathbb{R}^{p}$

--- iff $f$ can be represented by a ReLU MPNN

 $\chi:\mathbb{R}^{|V| \times d} \times \mathbb{R}^{|E| \times d'} \to  \mathbb{R}^{|V| \times d_\text{out}} \times \mathbb{R}^{|E| \times d'_\text{out}}$, 

where $m = |V|d +  |E|d'$ and $p=|V|d_\text{out} + |E|d'_\text{out}$

Now, with this equivalence, we can proceed to addressing the following:

`ReLU FNN are universal so this cannot make sense that any ReLU MPNN architecture can be realized with fixed parameters just by a counting argument. There has to be some dependence of these on the problem parameters (e.g. input/output dimension).`

Indeed, as Table 1 in the paper summarises, in order to learn any TRSM with specified input and output dimension, which  consists of $r$ monomials, the complexity (in terms of number of layers, and parameters) of the different ReLU FNN architectures as well as ReLU MPNN architectures depends on the problem parameters (such as input dimension as well as $r$).  By 'fixed' we simply meant that we know the (respective) exact specifications for the proposed ReLU MPNN architectures that realize any TRSM with given input and output dimensions and $r$. In particular, we did not mean that by fixing a particular ReLU MPNN architecture, we can realize all TRSMs independent of input/output dimension or $r$.  Please revisit Proposition 6 and Table 1 for the precise claim apropos of this discussion.

 We next address the concern about $\mathcal{N}(f)$ and  $\mathcal{N}(\chi)$, pertaining to  the following comment

`This does not make sense. E.g., set all the weights of the neural network to 0 and there is only one linear region. The theorem cannot possibly hold then.`

**Clarifying $\mathcal{N}(f)$ and $\mathcal{N}(\chi)$**: 
Apologies, the confusion here does seem to stem from our poor choice of (overloaded) notation, which we will fix as you suggested. For now, to make the argument precise, we first define $\mathcal{N}(f)$.

For a continuous piecewise linear map (CPLM) $f: \mathbb{R}^{m} \to \mathbb{R}^{p}$, we define $\mathcal{N}(f)$ to be the least number of connected regions $C_i$ of $\mathbb{R}^{m}$ such that $F \oslash G|_{C_i}$ is linear. Equivalently, following [1], we can also define $K = \mathcal{N}(f)$ as follows.  

$f: \mathbb{R}^{m} \to \mathbb{R}^{p}$ is a continuous piecewise linear map if $f$ is continuous and  there exists a set $\\{f_k: k \in \\{ 1, . . . , K \\}\\}$ of affine functions and nonempty closed subsets $(\Omega_k)_{k=1}^K$ satisfying the following conditions:

$\Omega_i \cap \Omega_j = \emptyset; \quad \bigsqcup_{i=1}^K \Omega_i = \mathbb{R}^m; \quad  
f|_{\Omega_k} = f_k. $

[1]  Alexis Goujon, Arian Etemadi and Michael Unser, On the Number of Regions of Piecewise Linear Neural Networks, 2023.

Now as we claimed above (and proved in the paper), any such CPLM $f$ can be realized by some ReLU MPNN $\chi$ with a particular setting of weights (parameters). However, if we change the weights, the function represented by $\chi$, as well as the number of linear regions, also changes correspondingly.  

The particular result gives a lower bound on the maximal number of regions of functions - obtained with different possible settings of weights - that can be represented by a ReLU MPNN. We state this bound below to make things precise:
 
(Contd...)
I am at times left more confused with the authors’ answers; so much so that I worry the authors’ results are incomplete and/or wrong. I think the authors were space limited in their responses so let me ask them to expand their response.


Let me give a few examples of my confusion and concerns:

> [Theorem 3]: By $\mathcal{N}(\chi)$ we mean the number of linear region for a particular ReLU MPNN , or equivalently a particular continuous piecewise linear map. We do not take the maximum over all possible functions.

This does not make sense. E.g., set all the weights of the neural network to 0 and there is only one linear region. The theorem cannot possibly hold then.


> any TRSM can be realised with explicit ReLU MPNN/FNN architectures with fixed number of layers, width, and parameters (Table 1).

ReLU FNN are universal so this cannot make sense that any ReLU MPNN architecture can be realized with fixed parameters just by a counting argument. There has to be some dependence of these on the problem parameters (e.g. input/output dimension).

> GC 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. 

I do not see the connection of generalization to geometric complexity which I assume refers to $\mathcal{N}$. This notion of complexity counts linear regions. Why should I believe this is anything more than a statement about expressivity? This is a worst-case statement as far as I can tell (bounds say at most how many regions there are) and bounds do not seem tight. For example, this quantity can grow exponentially with dimension for example. 

To argue otherwise for example: is there a nontrivial generalization bound that follows from this notion of complexity?

___
I would ask that the authors do the following both in the comments here (and update paper accordingly):
- Give formal definitions of $\mathcal{N}(\chi)$ - the in-line description in the text now at line 154 does not make sense to me as mentioned above
- Give formal definition of what the authors mean by equivalence of functions
- State explicitly relations of geometric complexity and its relations to generalization
___
Separate from the examples above, in many places, I also could not follow the authors’ rebuttal and its relation to my comments and questions. I understand this may be due to space limitations, but since the comments are not space limited, I would ask the authors to go back and answer the questions/comments in full.