Separation Power of Equivariant Neural Networks
Authors: Marco Pacini
Xiaowen Dong
Bruno Lepri
Gabriele Santin
Venue: ICLR 2025 Poster (2025)
Keywords: Geometric Deep Learning
Theory for Equivariant Neural Networks
Expressive Power
Primary area: learning on graphs and other geometries & topologies
TL;DR: We present a new theoretical framework to investigate the separation power of equivariant neural networks.

Abstract: The separation power of a machine learning model refers to its ability to distinguish between different inputs and is often used as a proxy for its expressivity. Indeed, knowing the separation power of a family of models is a necessary condition to obtain fine-grained universality results. In this paper, we analyze the separation power of equivariant neural networks, such as convolutional and permutation-invariant networks.
We first present a complete characterization of inputs indistinguishable by models derived by a given architecture. From this results, we derive how separability is influenced by hyperparameters and architectural choices—such as activation functions, depth, hidden layer width, and representation types. Notably, all non-polynomial activations, including ReLU and sigmoid, are equivalent in expressivity and reach maximum separation power. Depth improves separation power up to a threshold, after which further increases have no effect. Adding invariant features to hidden representations does not impact separation power. Finally, block decomposition of hidden representations affects separability, with minimal components forming a hierarchy in separation power that provides a straightforward method for comparing the separation power of models.

Published as a conference paper at ICLR 2025
SEPARATION POWER OF EQUIVARIANT NEURAL NETWORKS
Marco Pacini' Xiaowen Dong Bruno Lepri²
Gabriele Santin*
University of Trento, Fondazione Bruno Kessler, 3 University of Oxford, *University of Venice
ABSTRACT
The separation power of a machine learning model refers to its ability to distinguish between different inputs and is often used as a proxy for its expressivity. Indeed, knowing the separation power of a family of models is necessary condition to ob- tain fine-grained universality results. In this paper, we analyze the separation power of equivariant neural networks, such as convolutional and networks. We first present complete characterization of inputs indistinguish- able by models derived by given architecture. From this results, we derive how separability is influenced by hyperparameters and architectural choices-such as activation functions, depth, hidden layer width, and representation types. Notably, all non-pon ool-ooloomial activations, including ReLU and sigmoid, are equivalent in ex- pressivity and reach maximum separation power. Depth improves separation power up to threshold, after which further increases have no effect. Adding invariant features to hidden representations does not impact separation power. Finally, block decomposition of hidden representations affects separability, with minimal com- ponents forming a hierarchy in separation power that provides a straightforward method for comparing the separation power of models.
-nvvariiannn
INTRODUCTION
Alongside the proliferation and success of equivariant models (Wood Shawe-Taylor 1996 Cohen
Maron et al., (2018), there has been growing interest in understanding the fundamental reasons behind their performances, and in assessing their expressive power (Maron et al., 2019a] Yarotsky 2018). For traditional deep learning approaches, this expressive power is usually quantified in terms of universality (E) 2019), or their ability to approximate any element of given class of functions to arbitrary precision. However, universality is not directly applicable to neural networks that incorporates invariances the data (Bronstein et al. 202T). since they necessarily act by identifying pairs of inputs that equivalent under the given set of transformations. This feature creates a complex interaction between the network's 's ability to discriminate different input data, and the invariant equivariant structure that they are trying preserve. Assessing expressivity thus requires first a fine-grained analysis of the separation power of these families of neural networks, namely their capacity of distinguishing distinct inputs, which is necessary condition for the universality of the models (Joshi et al. (023).
In the graph learning community, which is a paramount domain where invariant and equivariant models are studied (Maron et al. 2018: Puny et al., 2023 Bevilacqua et al.] 2022). networks are required be invariant or equivariant under the group permutations of the graph's nodes. In this domain, the primary methods for comparing separation power are the Weisfeiler-Leman (WL. isomorphism test (Weisfeiler & Leman 1968) and homomorphism counting (Lovász 2012).
Significant attention has been devoted to studying this property for graph learning models such as Graph Neural Networks (GNNs) (Scarselli et al. 2009; Gori et al., 2005 Kipf & Welling 2017).
Invariant Graph Networks (IGNs) (Maron et al. 2018 2020), and subgraph GNNs (Alsentzer et al.) 2020; Bevilacqua et al. 2022). However, the WL test and homomorphism counting, along with their variants, have severe limitations imposed by their combinatorial nature. In particular, recent research (Joshi et al. 2023) has highlighted the necessity of developing expressivity measures applicable to models that process data beyond relational structures, such as geometric graphs.

---

Published as a conference paper at ICLR 2025
In this paper we contribute to this effort by studying the separation power of more general class of equivariant neural networks, which are not covered by previous results but are of significant practical interest. Namely, we focus the family of neural networks with regular convolutions (Cohen & Welling, 2016a), i.e., networks with non-polynomial continuous point-wise activations, hnite-dimensional representations, and equivariance with respect to the action of finite groups acting on representations as permutations. This class is rich enough to comprise many models of common interest, such as IGNs (Maron et al. 2018)) Circular Convolutional Neural Networks (Circular CNNs) (Ravanbakhsh) 2020), and Icosahedral CNNs (Cohen et al.) 2019), even if the proposed approach is not able to address some relevant equivariant models such as Elebsh-Gordin or polynomial approaches
(Kondor et al. 2018 Puny et al. 2023).
Specifically, we precisely describe the set of input pairs identified by relevant families of neural networks. In contrast, other approaches, limited to IGNs and graph processing, provide only upper bounds on expressiveness (Geerts] 2020) or lower bounds that require networks with large hidden feature widths (Maron al., 2019a). Additionally, we show how hyperparameter and architectural choices impact the separation power of equivariant neural network models, both in general settings and in specific cases of practical interest.
To study the separation power of relevant classes of equivariant networks, we show that the set of identified points corresponds to the set of common zeros of modified set of networks (Section [.I] We characterize the set of input pairs identified by these families of neural networks by introducing an explicit formula which, remarkably, is recursive over the networks depth (Section 5.2) This result provides important insights into how different hyperparameters and architectural choices impact the design of practical equivariant neural network models. In particular, we prove that any non-polynomial activation is equivalent in separation power, achieving the maximum separability for networks with a fixed architecture (Section (.3). We show that increasing depth enhances separation up to certain depth, where separation power stabilizes (Section 5.4). Furthermore, we prove that the multiplicity of the blocks in hidden representations or, equivalently, the width of invariant hidden features does not affect the separation power of the networks (Section (555). We demonstrate that the separation power of different block types forms a hierarchy, corresponding to the partial ordering of sub-groups of the symmetry group with respect to which the model is equivariant (Section (.6). We illustrate how these general results apply to practical models (Section 6). Specifically, we strengthen existing results by showing that much broader class of IGNs matches the separation power of WL (Section 6.I). Then, we demonstrate that the separation power of circular CNNs depends on the filter size (Section 6.2p.
All proofs are provided in the Appendix.
Contributions. Our contributions be summarized as follows: (i) We address the separation power of equivariant neural networks by fully characterizing the set of points identified by networks with a fixed architecture (Proposition 2 and Theorem D (ii) We prove that any continuous, real, element-wise, non-polynomial activation is equivalent in separation power, achieving the maximum separability for networks with fixed architecture (Theorem 2). (iii) We show that increasing depth enhances separation power up to a specific threshold, beyond which it stabilizes (Theorem B}. (iv) We illustrate how block decomposition of layers influences separability (Theorem 4 and how separation power is independent of invariant hidden features (Remark []. Notably, this result implies that any k-IGN matches the separation power of (-WL, improving upon previous results that required IGNs to have large hidden feature widths Maron et al. (2019a). (v) Finally, we show that the minimal components from this decomposition form a hierarchy in separation power (Theorem 5)
RELATED WORK
Recently, equivariant deep learning models have gained popularity (Cohen & Welling 2014 201 b).
being successful in diverse fields such as computer graphics (Qi et al., 2017), galaxy morphology prediction (Dieleman et al. 2015). computational biology (Joshi et al. 2024), and computational chemistry [Chanussot et al. 2021). 1). In the case of permutation equivariance, often required in graph
learning, the WL test has been adopted as the fundamental tool to measure the expressivity of GNNs
(Xu et al. 2019; Morris et al.) 2019) and has been used to derive upper bounds (Geerts et al. (02T) and lower bounds (Maron al. 2019a) on the expressiveness of IGNs and GNNs (Geerts & Reutter
2

---

Published as a conference paper at ICLR 2025
2022).
Recently, homomorphism counting has been proposed more fine- tine-grained measure of expressivity for GNNs (Zhang et (024), capable of assessing the separation power of subgraph
GNNs and their variants (Alsentzer et al. 2020: Frasca et al. 2022 Bevilacqua et al. 2022). Other
works that are related to the study of neural network separability ity inc include specific universality results
for equivariant networks (Maron et al. 2019h; Yarotsky [018 Zhou 2020. Ravanbakhsh 2020)]
Keriven & Peyré 2019; Dym & Maron, 2020 Instead, Joshi et al. (2023) addresses the problem of separability by generalizing the WL test from combinatorial structures to geometric graphs. In this paper, we shift from graph and relational domains to the continuous domain, where WL-based approaches are inapplicable, and extend the study of separation power to broader class of equivariant neural networks not explored in previous research but essential for practical applications. Specifically, we examine neural networks utilizing regular G-convolutions (Cohen & Welling 2016a). This class encompasses several widely used models, such as IGNs (Maron et 2018)) Circular CNNs (Ravanbakhsh, 2020), and Icosahedral CNNs (Cohen et al. 2019).
3
THE RELEVANCE OF SEPARABILITY
3.1
SEPARATION- UNIVERSALITY
The universality property of neural networks enables them to approximate any continuous function with arbitrary precision, meaning there exists a sequence of networks that converges pointwise to each continuous function. Equivariant neural networks are designed to handle target functions with specific structures, represented by transformations that recognize equivalent inputs. However, this characteristic necessitates a deeper examination of their separation power. The separation power p(N) of a W C Y) of continuous functions between topological spaces X and Y is defined as follows.
Definition 1. A function f X + Y is said to separate two points a, E X ifa) f(B). A family of functions N from X to Y separates a, B E X if there exists a function f E N that separates and B. If function or family of functions fails to separate two points, we say that it identifies them. The set of pairs of points that are identified by N define on an equivalence relation
p(N) (1a,3) xx
= f(3) for each f T ENN.
When working with spaces of neural networks, which we refer to as neural spaces for brevity, their separation power transfers to the class of functions they can approximate, as shown by the following fact.
Fact, Let (fr)ner be a sequence of functions in N that converges pointwise to f. Ifa, B E X such that fa) for all n E N, then f(a) f().
In particular, / cannot approximate with arbitrary precision functions beyond ones respecting p(N), namely, CдtN) Y) = {f e C(X,Y) f(a) = f(3) V(a, 3) p(N)). Understanding however if the entire set (X,Y) can be approximated leads to the study of separation-comstrainnel universality.
Notably, Maron et al. 2019b) and RRaanbakhshi (2020) illustrate this phenomenon in the context of equivariant neural networks, which are proven to approximate any continuous equivariant function. However, their constructions involve intermediate representations of impractically large dimensions. In contrast, Geerts (2020) and |Maron et al. (2019a) show that permutation equivariant networks commonly used in practice can approximate continuous permutation equivariant functions whose separation power is equivalent to the WL test.
In this work, we address the problem of characterizing p(N) for relevant families of equivariant neural networks, as it is necessary, though not sufficient, to understand universality. Specifically, we focus on how hyperparameter and architecture choices influence separability, as we will discuss in Section 3.2
3.2 THE EFFECT OF HYPERPARAMETER ON SEPARABILITY AND UNIVERSALITY
From a practical viewpoint it is fundamental to understand the hyperparameters and architecture choices that affect the separation approximation power of families of neural networks. For example,
3

---

Published as a conference paper at ICLR 2025
IGN's separation and approximation power are influenced by two hyperparameters (k, w), where is represents the network's 's relational order and w denotes the width of the final multi-layer perceptron. Informally, Maaon al. (2019b) showed that IGN U equivariant functions, while Geerts (020) proved that k-IGN = L.GN,, is universal only within the class of equivariant functions in C,.WL( (X, Y), the set of continuous equivariant functions with the same separation power as k-WL. This example highlights that, in a general equivariant setting, two types of hyperparameters and architecture choices may exist: (i) those like k. which regulate the separation power and, hence, have huge impact on approximation power, but also have a significant impact on the required computational resources, and (ii) hyperparameters like w, which do not affect separability but may impact separation-constraiee computational resources. our work, we aim to identify which hyperparameters and architecture choices control separation power, determining which belong to the first category and which may fall into the second.
is universal for continuous
approximation, often with a limited impact on
4 PRELIMINARIES
4.1 GROUPS AND EQUIVARIANCE
We aim to define functions that are symmetric with respect to specific transformations. Groups, which are particularly useful for computation and technical manipulation, consist of transformations that fulfill certain criteria: the elements can be combined, each element has an inverse, and there is a neutral element with respect to composition. While group theory efficiently studies symmetries and transformations from purely algebraic perspective, it needs to be adapted to the linear algebra framework required for defining neural networks. Representation theory acts as a dictionary for translating between these two languages, showing how abstract groups can be mapped sets of Fulton matrices that themselves form groups. For an overview, see Appendix Fortuuitooo & Harris (arris|(2004) for more complete reference. We will primarily focus on permutation representations. Before defining them, we need to introduce additional notation. Let X be a finite set and G a finite group acting on it. Let RX denote the set of real-val vellev functions defined on X. For each æ E X, let ex F be the function that takes the value at x and 0 everywhere else, and note that the set {ex]zex forms a basis for X permutation representation of G is linear action of G on V R such that for each g E G and E X, we have g(ez) = Cyr- Letting V and W be permutation representations of G. we say that a function & : V + W is G-equivariant ((gv) = go(v) for each v E V and g E G. We denote by Hom(V, W) the set of linear maps between V and W, and by Homa (V, W) the subset of G-equivariant linear maps. Similarly, we refer to the set of affine maps between V and W as Aff(V. W), and the set of G-equivariant affine maps Aff W). Note that Hom V, W). (V, W), and their equivariant counterparts are real vector spaces with respect to addition and scalar multiplication. Moreover, Pacini al. (2024) prove that map f E Aff(V, W) can be uniquely decomposed as T. Φ for some V E V and @ E (V W) and it is equivariant if and only if its linear part é is equivariant and W = (u W gu = c Vig E GJ. the set of G-invariant vectors in W. Thus, we have relevant linear morphisms À Aff W) + Homg W), which projects an affine map onto its linear part, and (V, W) - WC, which projects an affine map onto its translational part.
4.2 EQUIVARIANT NEURAL NETWORKS
With all the necessary definitions in place, we can now introduce the notion of equivariant neural network. Our study will focus on neural networks that equivariant with respect to finite groups, have arbitrary pisnt-wise continuous activation functions, and whose representations are permutation representations.
Definition 2 (Point-wise Activation). Let X be a permutation representation of a group G, and let RR- - R. We define the woiet activation induced by as the function ā R + Rx such that o( azCz) = -Exex ((z))ez- We will often abuse notation and refer to a as the activation function as well.
Definition 3 (Neural Networks and Neural Spaces). Let G be group and Vo...., Va be permutation representations of G, and let Mj be subsets of Afl (V, V.) for 1,...,d d. Given d 2 2, the
4

---

Published as a conference paper at ICLR 2025
neural space with layers in M1.... Ma and activation a is the recursively defined set
(M Ma) f o 1
det l
Ma. n
M
where No M1. A neural network with layers MI...., Ma and activation a is an element M.)- When M, (V Vi) for each 1...., we simply write N (Vo........ Va) instead of (M Ma).
n"t
In Definition 3 we do not impose any additional structure on M, beyond it being a subset of AV- Vo), although we will primarily consider M; to be vector subspace.
We now provide examples relevant models that align with Definition 3
Example 1 (Equivariant Neural Networks). Let G be a group, V = Rx be permutation repre- sentations of G, and M;- cff Vi) the full space of equivariant affine maps from V;-1 to V, for each I....,d. d. The neural space N (M1,.... Ma). or equivalently (Vo...... V2), is the usual space of equivariant neural networks with depth d and representation spaces V, for each i ,....,d.
As discussed in Section 4.1
equivariant affine maps (V, (V, W) can be decomposed into linear part in Homa(V, (V, W) and a translational part in the invariant subspace WG the set of G-invariant vectors of W. In our setting, the symmetry group G is finite, and W is permutation representation, with its invariant part WG characterized by the following result.
Proposition 1. Let XR- be a permutation representation of G with orbit decomposition XIU...UXX, (see Definition 7 in Appendix A.3 let Y S X. Define 1y Evey Cy RX The invariant subspace of Rx XRX + the basis I 1x 1x.
R X", consisting of vectors fixed by the action of G, is generated by
With this further characterization, we present detailed examples of equivariant affine maps and neural spaces relevant machine learning applications, showing how common models be expressed within this formalism. Furthermore, we will revisit these neural spaces in Section 6 highlighting specific properties related their separation power.
Example 2 (Invariant Graph Networks). Invariant Graph Networks of order 2 (2-IGNs)) Maron let al. 2018) are neural network models that ensure equivariance with respect to node ordering, making them particularly effective for graph processing tasks. They process graphs encoded as adjacency matrices A in Rexnxs, where the first two dimensions encode the relational structure, and the third dimension corresponds to the features. In setting, these matrices are defined as elements in R @ RR! where X [n]] x [T]] and IR is the invariant feature space. Each element E G Sw, acts on X jii = (a(i), ( (j)) for each (i,j) X and trivially on IR! To achieve permutation equivariance, the layers of 2-IGNs are maps in Aff S. (R** @ R .R. & R. and thus their associated neural spaces are N (I X R
R @ RJ Proposition 10 in Appendix A.4 x
implies that understanding the structure of Aff (R 59 TR. R 69 TR') reduces to understanding Maron et al. (2018) and Pearce- -remmp (023)), ). which states that dim Homs,, (RX RRX) )- 15 for n > 33 3nd, in accordance with Proposition 1 bias terms can described by noting that = [n] x [n] splits into two orbits,
the structure of Aff s., (R& R.X,, which completely characterized
X, = ii i E [n]} and X₂ = (ii,)) (i f j}. Identifying Rin[x(n]
Rn @ Rn = Raxx
elements in R correspond to diagonal matrices in Bax,, while elements in R X2 are off-diagonal matrices. In particular, invariant vectors in X are linear combinations of
[
0
1
1
1x =
and 1x, =
1
1
1 0
Then,
15
Afss, (R* X)
A
Σ
Ri (A) yn,x, + + x, [....... 175: 1/1 922 R
where 6¹ ...., L55 forms basis of Homs, (R. ) Furthermore, Maron et al. (2019h) show that 2-IGNs can be generalized to k-IGNs, which employ hidden representation of high order, namely elements in b=] RT.
5

---

Published as a conference paper at ICLR 2025
Example 3 (Circular Convolutional Neural Networks). Circular convolutional filters be described in the context of permutation representations, as we will demonstrate using the I-dimensional case for simplicity. Let X [n>] with the cyclic group G Σn acting on it in the standard way, and identify Talnn RR. Linear maps in Homz, (RR". ") are circulant matrices C(x) associated with vector x = (I1...., Fn)) e E R" (Davis 1979. Hence, the linear part and the translational part of
map in Af (R", R²) are written as follows:
T1
In
In-1
22
T2
I1
En
23
C(x) =
F3
22
21
20
and yllx = [n
2n-1
Tn-2
21
Note that (xx) Eis (eC( where e is the canonical basis of I2. Therefore, since convolutional filters with limited support are more commonly used in practice, it appropriate to restrict our choice of layers to maps within
R
M =
U Σ i=1
a C(e)) + ydm LT. Tki y
which are the 1-dimensional counterpart of the k x k 2D convolutional filters widely used in computer vision. In this case, the corresponding neural space will be N (MM,, ..., ....,Mkka for appropriate choices of filter sizes 1 ki.... ka n.
To generalize previous examples, now assume that the layer spaces M, which are subspaces of (V, ) can be written as
M
(0) Σ PEP
Upip 21.... The Ur for all
where o² "......,'' of generate subspace of Home (V, V, and P is partition of X, that may either combine several orbits from the orbit partition X X1 L-- L,,,, into larger subsets, coincide with the orbit partition itself. For further technical details, we refer the interested reader to Definition 12 in Appendix B.I
Now that we have described the structure of layer spaces in detail and explained why neural spaces constructed from these layer spaces more accurately reflect specific architectures used in practice, can proceed to study the separation power of these neural spaces.
MAIN RESULTS
We begin by describing and formulating the twin network trick in Section 5.1 which serves as the primary tool for converting separation problem into zero locus problem, be addressed informally in Section 5.2 the subsequent sections, we will explore the implications of this result and how can be applied to effectively compare the separation power of different neural spaces.
5.1 THE TWIN NETWORK TRICK
In this section, we introduce the twin network trick, which transforms a network separation problem into a locus problem for neural networks. This allows us apply the recursive techniques for solving zero locus problems developed in Section 5.2 Specifically, a zero locus problem involves by all networks within given neural space.
identifying all points that mapped
More precisely, the identification equivalence relation in (1) can be reformulated as the following zero locus problem: (a, 3) E p(Na (M,, .., Ma)) if and only
T(a)= - (B)) = 0 Vn E N (M,...,,
(2)

---

Published as a conference paper at ICLR 2025
We observe that 2 reduces to zero locus prob- lem involving twin netvorks. The twin network n VVBV - W. where 17(a, B) 17(2)-176 itself a neural network with the same depth 7 but with different architecture. Namely, 77 E N [......,... N....,,Ma--. Ma) where we define M (a. 6 ((3) 1 Ma and M, = o (a. (ó(a), ((3) à Mi}.
Ct
77
Thanks to the definition of the twin network, we can restate the identification problem in Equation as an equivalent zero locus problem, where we aim to find all 3 in V @ that satisfy 7 = Vnj E (M Mc)1.M.).
B
The twin network trick illustrated. Eval- uating two copies of 1j on and 3, and subtracting the resulting outputs, is equivalent to evaluating the twin network vi on (a,33) B).
Figure I:
In summary, these observations can be synthe- sized into the following proposition, which di- rectly links the identification relation to a zero locus.
Proposition 2. For family F of functions between set V and a vector space W, let I(F) {B E V (n) 4nn F}.
be the zero locus of F. Then, for any neural space N (MI..... Ma). we have (M,, Ma)) = I (M....., MI M2)).
Our task, then, is determine the zero locus corresponding to the neural space of twin networks.
5.2 THE CHARACTERIZATION THEOREM
In the previous sections, thanks to Proposition 2 we have translated the problem of comput- ing the identification relation p Ma)
into the problem of computing the zero locus IMN 1. ..... Ma M))). More generally, this zero locus be determined using the recursive formula proposed in Theorem I For brevity, we provide an informal version here, and refer the interested reader to Theorem 7 in Appendix B.1 for the complete version.
We begin by recalling and defining the necessary notation to state Theorem I Let M, be vector subspaces of off .R.x.) for i 1, .., d. Recall that X(Ma) denotes the linear part of Ma. and let did.1 ..... 66..2 be linear maps spanning X(Ma), and recall that (Ma)) = (1))) for some partition P of X.. Let Q be another partition of X if Q is finer than P we indicate this relationship as Q < P. Furthermore, for each /t = 1,.... and k E Xa define the family of partitions of Xa
d.A Pki
0, VPEE
Let m. X2xx - IR denote the projection onto the i-th component R2 for each in X 1- For each i E X. define the set (Ma-1) (Ø' scalar-valued layers obtained as the differences between the i-th and j-th part of the (d - 1)-th layer. Theorem 1 (Informal). Using the notation defined above, if is non-polynomial continuous activation finnttion, the following formula, recursive with respect to the depth d, holds
π:δ(x) ,T)((1) ) d M) which represents
(M.... UN U N I(No Ma-2, (Ma-1) PEQ S.EE
(3)
h.1 QEVI.N
The theorem shows that the zero locus of neural space of depth d can be recursively computed as combination of unions and intersections of the zero loci of neural spaces depth - 1. At depth 1, the neural space reduces to subspace of affine maps, and finding its zero locus corresponds to solving a system of linear equations. Although the actual execution of Formula B requires superpolynomial time, this recursive approach is particularly useful for deriving key properties of the identification relation, such as the role of activations, depth, and hidden features on the separation power, as detailed in the following sections.
7

---

Published as a conference paper at ICLR 2025
5.3 THE ROLE OF ACTIVATIONS
The following result shows that the choice of the activation function-and its properties, such as injectivity or monotonicity-is irrelevant separabilityy, long as the activation is non-polynome -on-yolynomaal. Theorem Let and be two continuous activation functions, with being non-polynomial. Then
...,, Ma)) S p
I also non-polee polyyooooa,,,,, equality holds. Thus, non-polyy non-polyommial activations not only yield equivalent separability but also achieve maximal separation power.
Proof outline. The inclusion follows by reconstructing the steps of in the proof of Theorem and applying the first part of Theorem ? To prove the equality in the case T is also non-polynomial, we reduce solve the equivalent zero-locus problem thanks to Proposition
We proceed by induction on d to show that non-polynomial activation functions do not affect the zero-locus. For the base case d 1, we have I(N (M))) = I(M)), which independent of a. Now, assume as the inductive hypothesis that I(N, (M,.... MI,..., Ma-1- Additionally, by definition, h, k and Wn,, are also independent a, which proves that none of the terms in the right-hand side of (3) depend on a, thereby completing the proof. O
is independent of a for any sequence
While non-polynomiality is sufficient for maximal separation, some polynomial activations may also achieve maximal separation power. Identifying these polynomials-or simply some of their properties, such as their degree-remains a complex mathematical problem. For more details, see Kiss & Laczkovich (2014).
5.4 THE ROLE OF DEPTH
Depth is key hyperparameter influencing the separation power of neural spaces. Theorem 3 shows that, while adding layers the same type can initially enhance separation power, this effect stabilizes after finite number of layers.
Let M; be a subspace of Afff@VV-11 Vi) for each i = 1....., d. Suppose that Vn-1 Vn for some integer I h S and that idy, E Mn. If a is continuous non non- con-polynomial activation function, then for m T,,
Theorem 3.
MA-1, Mrs ... Mn M ..... Ma)) 5
times
S P M May..., Mny Mh+ Ma)),
m. times
but there exists repetition threshold R such that for all 2 R the inclusion becomes equality.
Proof outline. To prove the first part of the statement, suffices show the inclusion for n and m = 2. Moreover, Theorem 2 implies that it is sufficient to prove this inclusion for a sin- gle non-polynomial a. Therefore, let be the ReLU activation function, noting that in this case = equivalently ā ē ā ő idgx; o. Thus, each neural network th ő oo... o ē di in A (M,, MM, .., M.) can be written as Φa o.... o ő idgx; o o...... Ō Φ1. which an ele-
ment of (M,, Mn, MA.... Ma). thereby proving the desired inclusion by applying Lemma The stabilization property can be proved by reducing to the equivalent zero-locus problem and ob- serving that descending sequences of finite intersections and unions of finite number of sets, as given by Theorem stabilize thanks to Lemma
The repetition threshold may vary depending the model and representation. For example, k- I-NS, being equivalent to WL, have a repetition threshold proportional to that of k- &-WL itself (Maron al. 2019a Geerts (2000. In contrast, the following proposition shows example of stabilization after just one repetition.
Proposition 3. When the hidden representation spaces are regular representations, stabilization occurs after layer repetition. Namely, p(N (V, RC, RR/)/)) = p(N (V, R RR/H)).
8

---

Published as a conference paper at ICLR 2025
5.5 THE ROLE OF INTERMEDIATE REPRESENTATIONS
In this section, we show that if representation, V can be decomposed as V V", then the separation power of neural spaces with hidden representation V reduces the combined separation power of two distinct neural spaces with hidden representations V' and V In this section, we present Theorem 4 an additional application of Theorem [ which demonstrates that the identification equivalence relation for neural spaces defined on is the intersection of those for neural spaces defined on V" and V This implies that by decomposing each hidden representation V into sum of minimal factors, the study of the separation power of general neural spaces can be reduced to analyzing those defined on minimal representations, as will be explored in Section 5.66
Theorem 4. Let IR + IR be a continuous non- non-polynomial activation function, and let Vo...., Va be permutation representations with V, = =V' @ V." for some O S i S d. Then,
PVV, .... Va)) p(N (Vo........ V.... Va)) n PVNo V.,.... Va)).
Remark Note that if V/ V,", we have
p(Na (Vo, Vi + Vi"" Va)) = a(Na(Vo Vi,.... Va)).
As result,
pNo (Vo. ..... V R ..... Va)) = "
p(No (Vo................... Vg...., Va)),
since V = vaa. Thus, the separability independent of multiplicity and invariant features in intermediate representations.
5.6 THE ROLE OF REPRESENTATION TYPE
Thanks to Theorem we can focus on studying the separation power of neural spaces defined on minimal representations. These minimal representations are of the form R.,, where the group G acts transitively on X. That is, for any pair of points x, E X, there exists an element E G such that gz = y. Basic group theory (Fulton Harris 2004) shows that a set with a transitive action is in bijective correspondence with right cosets G/ll for some subgroup H < G, see Definition in Appendix A.2 Informally, the following theorem allows us to compare representations induced by transitive actions arising from certain subgroups.
Theorem 5. Let K < H < G be finite groups. We have
(V........ RG/K V.V....RG//KK
W)) S PWV.(V .....
R.C.....//.... RG/H W)).
Proof outline. The proof consists showing that R/H is subrrepeseenttaionn of RO/K and prov- ing that this induces embedding of N (V....... RR/H W) into No (V,..., RG/K W). Consequently, the result follows directly from Lemma
Theorem 5 implies that neural spaces with minimal representations in one layer, namely RG/H ..... W)]H&G form separation power hierarchy corresponding the hier- archy of subgroups of G. In particular, if H G, the corresponding representation RG/G has minimal separation power. Furthermore, notice that G/G 2 R is the trivial representation, and this means that invariant layers have the lowest separation power. On the other hand, if H = {e} is the group containing only the identity element, the corresponding representation GG(ee) has maximal separation power, since {e} is contained in every subgroup of G. As ( n is the regular representation, this implies that the regular representation achieves the maximum separation power. In general, if K < H, then dim RG/H < dim RG/K Hence, improving separability requires working in larger space, which, aside from ad-hoc optimizations, leads to additional computational cost. In particular, by applying Theorem M we can prove the following proposition.
Proposition 4. The neural space No (V, ,GGHH) ) of equivariant shallow networks with regular hidden representations identifies inputs if and only if they belong to the same H-orbit, i.e., (3, B²) p(No (V,R",RG/") if and only if there exists some h E H such that h 3'.
This is consistent with the results in Ravanbakhsh al.] which demonstrate that shallow networks with hidden representation blocks isomorphic to R are universal. This universality implies maximal separation power, stated in Theorem 16 of Joshi al. 2023)

---

Published as a conference paper at ICLR 2025
6 IMPLICATIONS ON PRACTICAL MODELS
6.1 INVARIANT GRAPH NETWORKS
Theorem in Maron al. 2019a) and Theorem 2 in (Geerts 2020) together imply the following fundamental result for the theory of IGNs.
Proposition 5. There exist > and a large f1, Ji,....;Ja > F, the neural space N - ((R") 02 @ R (TR") ( &R ,...., (R*) @ R matches
0 such that for hidden feature dimensions
(
the separation power of k-WL.
However, Remark shows that the dimension of hidden invariant features does not affect separation power, strengthening Pnoposition[]in the following corollary.
feature dimensions fi.... fa > O, the Corollary 1. There exist > O such that for any hidden feature
neural space N, ((R")02 & B/o, (R R R......, )R.) 8ak @ Ria, ()) matches the separation power of k-WL
6.2 CONVOLUTIONAL NEURAL NETWORKS
The separation power of circular CNNs is influenced by the width of the filter's support.
Proposition 6. Let M be the layer space for circular convolutions with filter size k. defined in Example Consider the neural space k-CNN = N (M Affz,, (IR", IR)). This is the space associated with shallow convolutional networks, where the first layer consists of one filter of size followed by an output invariant layer. For nI > 2, we have:
p(n-CNN) & P(1-CNN), and C.. S P(11CNN))
LIMITATIONS
The primary limitations of the proposed framework lie within its initial assumptions. Specifically, only applies to permutation representations and cannot extend to other important equivariant models, such as (lebsch-Gordanl or polynomial approaches (Kondor al. 2018: Puny et al. 2023). While
the techniques used to prove Theorem I could be applied, the functional equation (12 necessary for the proof is substantially different, and no actionable solution known up to our knowledge. Solving these equations would improve our understanding of the separation power in these models. The second key assumption that we consider only intermediate layers with bias, which is standard in many practical models. In cases where bias terms are absent, such as in can only provide a bound on the separation power. Indeed, these models can be reformulated as IGNs (Maron et al. 2018), which belong to broader neural space with bias terms, allowing us analyze their separation power. Our final assumption involves the use of non-polynomial activation functions, commonly employed with examples like ReLU, tanh, and sigmoid. While non-polynomiality is sufficient for separation, some polynomial activations may also achieve maximal separation power. However, identifying these specific polynomials presents a complex mathematical challenge. For further details, we refer readers to (Kiss & Laczkovich 2014).
GNN models, model
8 CONCLUSIONS
The proposed results enhance our understanding of which target functions can be approximated with arbitrary precision by functions in neural network spaces relevant to practical applications. In particular, these target functions must satisfy the identification relation of neural networks spaces, which can now be computed using Theorem [ This result helps us classify hyperparameters and architectural choices into two categories: those that directly influence separation power, significantly impacting both approximation ability and computational cost, and those that do not affect separation power but may influence approximation in ppparation-constrainne setting, potentially with minimal computational cost. Specifically, we prove that all non non-polynomial activations provide maximum separation power, depth enhances separation up to stabilization point, and hidden feature width has no effect on separation power. Lastly, we show how these insights can applied to practical models, such IGNs and standard CNNs.
10

---

Published as a conference paper at ICLR 2025
9
ACKNOLEDGEMENTS
Bruno Lepri acknowledges the support of the PNRR project FAIR Future AI Research (PH00000013), under the NRRP MUR program funded by the NextGenerationEU and the support of the European Union's 's Horizon Europe research and innovation program under grant agreement No. 101 120237 (ELIAS).
REFERENCES
Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, and Marinka Zitnik. Subgraph Neural Networks. Advances in Neural Information Processing Systems, 2022.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant Subgraph Aggregation Networks. International Conference of Learning Representations, 2022.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2 13478 [es, stat], 2021. URLhtttp
7/arxiv. org/ wwwpg//b///ee 2t10/
Lowik Chanussot, Abhishek Das, Siddharth Goyal, Thibaut Lavril, Muhammed Shuaibi, Morgane Riviere, Kevin Tran, Javier Heras- Droras-Domino,, Caleb Ho, Weihua Hu, Aini Palizhati, Anuroop Sriram, Brandon Wood, Junwoong Yoon, Devi Parikh, C. Lawrence Zitnick, and Zachary Ulissi. Open Catalyst 2020 (OC20) Dataset and Community Challenges. ACS Catalysis. 2021.
Taco Cohen. Equivariant convolutional networks. PhD Thesis, 2021.
Taco Cohen and Max Welling. Learning the Irreducible Representations of Commutative Lie Groups. In Proceedings of the 31 International Conference on Machine Learning, PMLR, 2014.
Taco Cohen and Max Welling. Group Equivariant Convolutional Networks. In Proceedings The 33rd International Conference Machine Learning, PMLR, 2016a.
Taco S. Cohen and Max Welling. Steerable CNNs. In International Conference Learning Representations, 2016b.
Taco S. Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge Equivariant Con- volutional Networks and the Icosahedral CNN, 2019. In Proceedings of The 36th International Conference on Machine Learning, PMLR, 2019.
Philip J. Davis. Circulant Matrices. Wiley, 1979.
Sander Dieleman, Kyle W. Willett, and Joni Dambre. Rotation-invariale convolutional neural networks for galaxy morphology prediction. Monthly Notices of the Royal Astronomical Society, 2015.
Nadav Dym and Haggai Maron. On the Universality of Rotation Equivariant Point Cloud Networks. In International Conference on Learning Representations, 2020.
Weinan E. Machine Learning: Mathematical Theory and Scientific Applications. Notices of the American Mathematical Sociery, 2019.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and
Extending Subgraph GNNs by Rethinking Their Symmetries. In Advances in Neural Information Processing Systems, 2022.
William Fulton and Joe Harris. Representation Theory. Graduate Texts in Mathematics, Springer, 2004.
Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv:2007.12035 [cs, math, stat), 2020. Utl/:ttp:://xxx..ooggg/
12035
Floris Geerts and Juan L Reutter. Expressiveness and Approximation Properties of Graph Neural Networks. In International Conference Learning Representations, 2020.

---

Published as a conference paper at ICLR 2025
Floris Geerts, Thomas Muñoz, Cristian Riveros, and Domagoj Vrgoë. Expressive Power of Linear Algebra Query Languages. In Proceedings of the 40th ACM SIGMOD-SIGACTO Symposium on Principles of Database Systems, 2021.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. Proceedings. 2005 IEEE International Joini Conference Neural Networks, 2005., 2005.
Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, and Pietro Lio. On the Ex- pressive Power of Geometrie Graph Neural Networks, In International Conference of Learning Representations, 2023.
Chaitanya Joshi, Arian R. Jamasb, Ramon Viñas, Charles Harris, Simon V. Mathis, Alex Morehead. and Pietro Liò. gRNAde: Geometric Deep Learning for 3D RNA inverse design. Methods Mol. Biol. 2025.
Palaniappan Kannappan. Functional Equations and Inequalities with Applications, Springer, 2009.
Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems, 2019.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference of Learning Representations, 2017.
Gergely Kiss. Linear functional equations, Phd Thesis, 2014.
Risi Kondor and Shubhendu Trivedi. On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups In Proceedings of the 35th International Conference on Machine Learning, PMLR, 2018.
Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch-Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network, November 2018. In Advances Neural Information Processing Systems, 2018.
László Lovász. Large Networks and Graph Limits. American Mathematical Society, 2012.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. International Conference on Learning Representations, 2018
Haggai Maron, Heli Den-H Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. International Conference of Learning Representations, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. In Proceedings of the 36th International Conference on Machine Learning, PMLR, 2019b.
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On Learning Sets of Symmetric Elements. In Proceedings of the 37th International Conference on Machine Learning, PMLR, 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher- Order Graph Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Marco Pacini, Xiaowen Dong, Bruno Lepri, and Gabriele Santin. Characterization Theorem for Equivariant Networks with Point-wise Activations. In International Conference of Learning Representations, 2024.
Edward Pearce-Crump. Connecting Permutation Equivariant Neural Networks and Partition Diagrams. arXiv:2212.08648 [cs, math, stat], 2023.
wttp://wwrr/bb/////////e/ abl// 22tp://222....0//////222222.22 68688
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, PMLR, 2023.
12

---

Published as a conference paper at ICLR 2025
Charles R. Qi, Su, Hao, Mo, Kaichun, and Guibas, Leonidas J. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In 2017 IEEE Conference on Computer Vision and Patter Recognition (CVPR).
Siamak Ravanbakhsh. Universal Equivariant Multilayer Perceptrons. In Proceedings of the 37th International Conference on Machine Learning, PMLR, 2020.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabás Péczos. Equivariance Through Parameter- Sharing. In Proceedings of the 34th International Conference on Machine Learning, PMLR, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 2009.
Yu Weisfeiler and A A Leman. The Reduction of a Graph to Canonical Form and the Algebra Which Appears Therein. 1968.
Jeffrey Wood and John Shawe-Taylor. Representation theory and invariant neural networks. Discrete Applied Mathematics, 1996.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference of Learning Representations, 2019.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. In Constructive Approximation, 2022.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond Weisfeiler- Lehman: A Quantitative Framework for GNN Expressiveness. In International Conference of Learning Representations, 2024.
Ding-Xure Xuan Zhou. Universality deep convolutional neural networks. In Applied and Computational Harmonic Analysis, 2020.
13

---

Published as a conference paper at ICLR 2025
A PRELIMINARIES
A.1 SPACES OF AFFINE TRANSFORMATTIONS
Let V and W be vector spaces, we denote by Hom W) the set linear maps between V and W. and (V, , W) the set of affine maps between V and W. Note that both Hom(V, W) and (V, W) are real vector spaces with respect to addition and scalar multiplication. For each E W define Tv W + W such as (w)
+ for each to in W. Each affine map f V + W has unique decomposition = T₁ o Φ. where á is a linear map and T, is a translation by a vector v E W. Previous observations imply that the map
Hom(V, W) ④ W + W))
(0,0) + T
an isomorphism of vector spaces. Define Tw = (To u E } as clearly Tw W, we will often abuse notation identifying Tw with W. Then,
define the maps
Af, W) - W X: (V, W) - Hom(V, W) and T:
f f(0)
f+).
We call X(f) the linear part of f for each f Aff(V, W) and rff) the translational part of f for each affine map.
Proposition 7. Maps \ and are linear and surjective.
Proof.
The projection on the linear part À is linear since for each a, B E E and f.g E Af((V,) X(af + Bg) = (af + 8g) (af + (g) af - a() Bg(0)
- f()) - ((g-)(0)) = a\(f) 3N()).
Furthermore, surjective since for each á Hom(V, W), we have that A(0) o (00(00)= Φ.
The projection on the translational part 7 is linear since for each a, 3 E R and f.g Aff(V,W)
T(af (g) (af + (0) = (0) + 3g(0) af( Br
Map r is also surjective since fix f Hom V. W) and notice that T(T,f) = v and T.f E Aff(V, W) for each W.
In general, we will be interested in vector sub-spaces M of AIT(V, W). A simple way to construct M is to identify sub-spaces of interest in Hom W) and subspaces of Tww = W and define M 0L + T). We will be interested only is sub-spaces which are possible to construct in this way. Nevertheless, is worth noticing there exist sub-spaces of Af, W) that are not isomorphic through 0 to directed sums of linear and translation parts. An example is given by the space E RJ. Notice that A(M) {ao a E R). r(M) = {av M = {Te e aá
E IR.. and dim M X(M) 7(M) 1. If M ((A(M) @ T(M)), we should have dim M dim X(M)+dim T TMM = 2, which is not possible. Spaces that can be decomposed as M = (LLT)) have the following useful property.
Proposition 8. Let M be subspace of Aff(V. where there exist subspace L of Hom W) and a subspace T of W such that M = =( + T). Let $1...., &. be a basis for L and U1,... Un basis for T. Then, each in M can be written
a
f:8 21) + Σ yz
j=l
for unique parameters x; and yj for each i L,..., and j -....,,
A.2 GROUP THEORY
Definition 4. A group is pair (G,-) where G is a set and : G x G - G is function satisfying the following axioms.
Associativity: for each g, h le G we have(g h) g. (h k))
14

---

Published as a conference paper at ICLR 2025
Identity: there exists element G such that g 9 g 9 for each G. Inverse Element: for each element 9 G, there exists element g 1 E G such that 9-9
g-
A group is finite if contains a finite number of elements. A group is abelian or commutative if gh hg for each g, h G.
Example 4. Here we present some fundamental examples of groups.
Let X be a set and define the set of permutation of X as
= x
is bijective).
With the composition operation form the symmetric group the permutation group of X. Particular attention is devoted to the case X = [nl, we write Sn = Sx and it called symmetric group or the permutation group of n elements.
Let Zn be the group of integers modulo n. with the addition operation, they are called finite cyclic groups of order
Given two groups G and H. the direct product G H of them is still a group. The set of the elements is the Cartesian product of G and H while the sum is defined as
(gi, h1) "GxH (g2, h2) (g) G 92, hy "H h2).
Now, we introduce the notion of group homomorphism, transformation between groups which preserves the operation.
Definition 5. A group homomorphism is a map
G
between G and H groups such that, for each g, h EG
6g h) ((g) o(h).
Definition 6 (Cosets). Let G be group and H be subgroup of G. The set of left cosets of G by H is the set G/H = [gH H. Similarly, we define the of right cosets as H.G subgroup of G, we define the double coset of H and K with respect to an element g E G as the set HgK {hgk h H.k K}. The set of double cosets denoted as H G/K.
E G}, where gH = [gh h E H} are the left cosets of
(Hg g E G}. Let K be second
Example 5. Relevant examples of left cosets include the following:
1. Consider G = and the subgroup H n of integers multiples ofn. n. The quotient G/H is group and is isomorphic to the cyclic group of elements, Z.,.
2. Consider G S3. the symmetric group on three elements, and the subgroup H {(1), (12)}. The quotient G/H is a group and isomorphic to Sz, symmetric group two elements.
3. Consider G Sn, the symmetric group elements, and the subgroup H An the alternating group on elements. The quotient G/ H is a group and is isomorphic to Zz.
A.3 GROUP ACTIONS AND EQUIVARIANT MAPS
Let G be group and X be a set. An action of the group on the set X a function
+ G X,
usually written (2) ()) for each g G and in X, such that:
For the identity element in G. the identity condition de idx holds.
For all g, h E G, the compatibility condition dg o on dygh holds.
15

---

Published as a conference paper at ICLR 2025
In this context, often write g simply gæ instead of 6, A G-ser is set X equipped with a group action G. This means that there is a well-defined action : G x X + X satisfying the properties of group action described above. Throughout the following sections, it will often be convenient to decompose G-sets into a disjoint union of subsets, each minimal (in a sense specified in Definition 7 and equipped with compatible G-action.
Definition 7. Let G be group acting on a sel X. An orbit in X is a subset Y C X such that for each Y, we have Y [g- x 9 E G3. The set X can be decomposed into disjoint union of orbits under the action Gf This is called the orbit decomposition of X, and if X is finite, the decomposition can be written as
x X1 U... Xa.
where XI....,X, Xn are the distinct orbits of X.
Another fundamental concept for our treatment is that of a function between G-sets that preserves actions, which is more formally specified Definition g
Definition 8. Let X and Y be two G-sets, map f X + Y is G-equivariant if
9. fx()z== f((0 xx)
for each in X.
A.4 GROUP REPRESENTATIONS AND EQUIVARIANT AFFINE TRANSFORMATIONS
Let G be a group and be vector space over a field R. G-action V + V on is C-representation if 0g is linear for each in G. Or equivalently,
GL(()
+ 0g
where GL(V) is the general linear group of V, consisting of all invertible linear transformations V. We will usually identify the entire G x V > V action with itself and write gv = ( v).
Let V and W be two G-representations, tween V and W as Homo(V, (V, W) and as Affa(V. W) the set of equivariant affine maps. Note that Home (V, W) is vector space. Indeed, Homo(V, W) and for each f.g Homa W) and each a, 8 E RR af + 3g E Homg (V, W). The same is true for Aff W).
will indicate the set of equivariant linear maps be-
Let V be G-representation, we define the of invariant vectors V {u E ge = Vgg E G).
In Section A. we studied the properties of vector subspaces of affine transformations between vector spaces. Here better understand the structure of such spaces is necessary to remind Theorem 8 in Pacini et al. (2024).
now interested in studying subspaces of equivariant affine transformations. To
Theorem 6. An map o = Tw f belongs to Aff W) if and if f Homm@(, (V, and v is invariant.
We can define restrictions of maps 0G. λg. and TO follows
IG Homo(V, W) WC Affo(V,W) (0,v) + T
Àg (V, W) Homo W) and TE:
Affa W) + WG { f(0).
f f - f(0)
Theorem T (implies that OG an isomorphism and similar proof to the one of Proposition 7 shows that both ÂG and TG are linear, equivariant, and surjective. When it will be clear we are working in the equivariant setting, we will drop the subscript and just write 6, X, and T.
In the main text will often the following results. Proposition 9. Let V1, V2, and V be G-representations. Then, Homg (V1 θ V2, V) = Homg(V1, V) @ Homg (V2, V)
and
Homa (V, Vi @ V/) Hoom Vi) @ Homg V2).
16

---

Let G be a group and Published as a conference paper at ICLR 2025
Proposition 10. Let V and W be G-representations, and let G act trivially on R" and R". Then, and
(o @ RR, W @ I=) = Homg W) & Hom(R",
(V V VOR'CEVV R
In other words, recalling that (V, W) = Homc(V,W) W) W and since Hom R") = Rmxm is the set n x m matrices over R. understanding the structure of Afia(V @ R", . W R") reduces understanding the structure of Aff (V,WW.
A.5 ON PERMUTATION REPRESENTATIONS
The followings are easy and known results from the theory of permutation representations.
We recall the definition of permutation representations as stated in Section
Definition 9. Let X be a finite and G finite group acting on it. A permutation representation of Gs representation of G on R such that g(ez) = Egz for each E G and x E X.
Proposition 11. Let X and Y be two G-sets. We have the two following G-representations isomor- phisms
XRX R @) R and XXY = R & R.Y.
where Y indicate the disjoint union of the sets and
Example 6. Let S [n] and let Sn, act on S in the standard way and note that R$ = R as
representations. From Proposition 11 we obtain that tensors of order 2 are R= @ R" = R5555
Raxx, Let == = [(1, i) E S) and = {(i,j) S + j}. note that S x A LJ A and that S. acts transitively on both A and A. Therefore, R" & R" IR Sxs
R
We say that a group G acts transitively on set X if this action has only one orbit, namely Ge X for each x E X. If X.....--L is the orbit decomposition of X, then Rx = X1 .R.
As the bias terms of equivariant layers are vectors invariant under the action of permutation repre- sentations, it is important characterize the invariant part of permutation representation. Before proceeding, it is necessary to state the following result.
Proposition 12. IfG is a finite group acting transitively on a finite set X, then there exists a subgroup И < G and G-set bijection between X and G/H..
Proposition 12 implies that can restrict our study representations of the form RG for some subgroup H of G. With this result, we can now proceed to prove Proposition | X be finite with action of G. For C X, recall that 1y Eyer Ey.
Proof of Proposition
The Reynolds operator
VG
R:
Σ gu
DEG
projects each G-repressetation V its invariant subspace VG, In the case V RG/H element of the canonical base of G/H
CkH is an
R(CEH) = Σ geeH =
Σ
Ecgkn
CygH =
H
Σ
CgH = HI a/H-
8EG
8EG
gHEG/H
The final observation follows from Proposition
Propositions I1 and 9 together imply that characterizing equivariant maps between permutation representations reduces to characterizing equivariant maps between representations induced by transitive actions finite sets, equivalently, left cosets by Proposition 12 We address this in Proposition [4] To prove this result, we first define the concept of right multiplication lication in Definition I0 and then prove Proposition 13 which characterizes equivariant maps between regular representations.
17

---

Published as a conference paper at ICLR 2025
Definition 10. For each G define the right-mmltiplicaation
R
- R
Rg
Ch
+ Eng
Right actions are a basis for the space of equivariant endomorphisms of the regular representation. In other words, (R. BeG basis for Homg(R RRC).
Proposition 13.
Proof. Each linear application & E (R RCO) is defined by the values Φ(eg) for each g E G by linear extension. If G-equivariant, it is defined just by its value on ee- Indeed, p(eg) ((gea) go(ee) for each g E G. Note that R.g is linear the right action of g RCC. is linear and (e))n) = Ehg 1 == RC and h G. Furthermore, (ee) Eg for each g E G and therefore they generate Homg (TRC, RC).
e..... = It is also equivariant, indeed Rg (hv) hwg = h (v) for each
Suppose that there exist values 0g E R for each g E G such that Egea ag Rg = 0, then
= Σ
og
Re(( = Σ
agCg-1.
9EG
DEG
Since elements Cg are linearly independent, 0g = for each E G. Hence, R2 are linearly independent and form a basis for Homg (R RR).
Now we would like to have a result similar to Proposition G/H. H. To do this we need to define the following injection
13 but for morphisms between G/ and
IR
RG/H
+ R
4G/H
Cgll
H
Egh-
H
bEH
and projection
R
R
G/H
TG/H
Eg EgH.
For an arbitrary representation V. we define two surjective maps
Homa V) - Home (R G/K v)
ca/K:
Φ + @OLGK
and
Homa (V, RR Homo (V, RG/H)
Ta/H==
Φ + TG/H Φ.
We can now generalize the concept of right multiplication to the general case transitive actions, a concept necessary for stating Proposition 14, which will then prove by following the approach used in the proof of Proposition 13
Definition 11. Define RHaK
a R2 where the map = TG/H= o CajK is defined from
Homg (RC RRC) to HR (R/H/ RR.").
Proposition 14. The map RHoK is well-defined and the set Homg G/K (RC/K,BG/1) RG/H). Finally,
is a basis for
(RHak(euk)) =
+ ifsH C Ckg
00
otherwise.
18

---

Published as a conference paper at ICLR 2025
Proof. To prove that RHgK is well-defined, we need to prove that Rg Rugt for each h H and h E K. Indeed,
IG/K (eak) = Σ
TG/H Rigg LG/
Est tg
K
tER
Cosk-1 1-11--1-11-11 1-11111111-1
Σ tEK
estg-1H = GG/H Rg ((sk()s)),
K
K
KEK
where the penultimate equality is true because h-1H H and variable change + fk-1
1 in the sum.
By Proposition 13 the set { Iee is a basis for Homa((R) (R., By the previous observation have shown that the image of {Rg] under [Rug HagKEMG/KK a is surjection, HR ) HyKK generates Homg (RR IC/")..
Proving linear independence is similar to the proof of linear independence in Proposition 13 Indeed, let aHoK E R for each HgK E H/G K such that
Σ
Ollkk RHgk O.
HgKEHGG/K
Hence,
0
E
aHgk RHgK(EK)
E
aagk
Σen esg-it tEK
[
HgKEHNG/K
HgKEM
Note that sets (tg-1 HEEK pairwise disjoint with varying between representatives of HgK. This means that the respective vectors LIEK Ctg ни are linearly independent, hence each aHgK = 0. This proves that the maps RHgK are linearly independent. Finally, observing that
1
RHgK (eak)
Ekig 1H
K
KEK
it is clear that
if HH C Lkg-
(Rag)(ea))) eH
K
otherwise.
Remark 2. In case of interest, in which G is a finite group, the map - v- is equivalent at convolving by w. Proposition [4is just restatement and integration of Theorem Kondor Trivedi (2018) in the restricted case of homogeneous spaces of finite groups.
B MAIN RESULTS
B. THE CHARACTERIZATION THEOREM
To formally state and prove Theorem T need to understand how bias terms in neural spaces transform under the twin network trick. Note that, in general, we have 7 T(Affc(V,W) g (V O V, V.W ④ W)), as illustrated by the following Example Example 7 (Twin Layers in 2-IGNs), Let us consider IGN layers. this case, W x The twin layer takes and has values in R R 2 RXLX' where X' is disjoint copy of X. Hence, the twin IGN layer an affine function I XIXX" + RXXII defined as follows:
(A, (L(A), + vi + v2lx, + tullx;+ + +221x;
(5)
where X1 and X²2 are the copies of Xı and X2 in X', respectively. Note that they share the same parameter for 1x, and 1x; and for 1x, and 1 1xy, while the translational part of Affs, (RXXXX XR-X is y1 1x, + Hy2lx, + +3/ Ix 161x, X;. Alternatively, we have
dim T (Affs, (R2* Rx)) = 2 and dim T(Affs, (R Xux' ,I xxxxX' = 4.
Hence,
T (Afss, (RXX, RRx)) (RX,Rxx) T Allss (R XUX , _xxXX)).
19

---

Published as a conference paper at ICLR 2025
Example 7 shows that we need definition of bias that can describe the bias terms in (5). This will be provided in Definition 12
Definition 12 (Complete Bias). We say that the subspace M of AV has complete bias if X(M) @ (MM) = M through 9 and r(M) = (EP) where P is a partition of X. In this case, say that the bias of M is subordinate to the partition P. In the opposite case, we say that M has incomplete bias. In particular, we say that M has null bias if its translational part r(M) is zero; in other words, M is simply subspace of Home IR*) and M = X(M).
The following observations are necessary to justify this definition. Remark 3. Note that each subspace M of ( Rx* such that M = X(M) @ (M) and T(M) = (V, Rx)) has complete bias. Indeed, in this case have P = (X1,.... X the G-orbit decomposition of X and
7(M) = (Ix,)x.EP
as proven in Proposition Therefore, all examples Section 4.2 have complete bias.
Remark 4. Note that each subspace M of (V, (V, has complete bias and only if there exist $1, , Us in Homa(V,1**) and a partition P of X such that each map in M can be written as
+ ( + x, (3) + Σ yrdr
(6)
YEP
where r; and yp are real parameters for each i 1, .,... and each P in Proposition 15. Let M Ma-1 be subspaces with complete bias, then the space of twin networks
(M (MMM,,.,Ma-11,))) M³)
has intermediate layers with complete bias and output layer with null bias.
The proof of Proposition 15 relies Proposition 16] Lemma D which will be stated shortly.
Definition 13. Let X be a finite set, we define the duplicate set of X as the set X LI X' where X' is disjoint copy of X. Let P be a partition of X, we define the duplicate partition of P as the partition P' of the duplicate of X such that p' = =Y UY" Y E P). For each y E Y, we will usually indicate the respective element in Y' as y', although when it will be clear from the context may abuse notation and call both y.
Proposition 16. If M is a sub-vector space of (V, RR*) with complete bias subordinate to parti- tion P then the twin space M is a subspace of (V @ V, R R-x) = (V @ V, Xux' ) and has complete bias subordinate to the duplicate partition P.
P. In particular, dim 7 (M) dim (M) and dimn (V @ V, X @ Rx)) = dii (V, IR xxx)
= 2 diim R))).
Proof. Trivially, if M = X(M) @ T (M), then M = A (M) o r (M). Noticing that Ç: R- @ X such that (((E,, 0)) = e₂ and (((0, ex)) eg' is an isomorphism. First we show that that AV + V.R. @ x = (V @ V,R If M has complete bias subordinate to P then T(M) (lr) and each v E E(MM) can be written as v = Evep dy ly for some (av) )y E R.. Remember that (MM) = (0(0) o E M}. then TMM) ((((),, (()) é = UEET()))
{ Σ Ly, Eardr) (ar)r e Rp
YEP
YEP
we can write ay Exep = By the isomorphism Ç: R + B XUX',
Evep ay Iv
Lemma 1. The output space of a twin network M' always has null bias, independently of the bias space (M).
Proof. Let Φb u - f()) + y be an affine map in M < AV, W). Then the output layer of the
twin network
p'(u, w) d(v) ((w) f(v) + - f(w) - y= ffu( f(w), which is always linear map in Af @ V, W). Equivalently, r(M') 0.
20

---

Published as a conference paper at ICLR 2025
Proof of Proposition 15
Apply Proposition 1o Mi,.... Ma-1 and Lemma Ma-
Together Remark 3 and Proposition 15 show that we only need to solve zero locus problems for networks with complete bias in the intermediate layers and null bias in the final layer. We are now able to give the complete and formal statement and proof of Theorem !|
Theorem 7. Let MI...., Ma-1 have complete bias and let Ma have null bias. Let od.1...., od be of generators of Ma < Afffg(Rx. Xa, IR. (aNa+)), and let the bias of Ma-1 be subordinate the partition P. Furthermore, for each = 1,...,&, Sa and each E Xd411 define
Vi.k Q P
d.h
non-polynomial activation function, then have the following recursive formula with respect to network depth
I Ma))
U 1.1 QEVA.
n
I(N (M Ma-2, (Ma-1)
PEQ SJEP
where (Ma-1)is fs x 1 ),O(x) - <ソδ()) o A(Ma-1)), n;: n. :R - R is the projection on the i-th component of R for each in X, and ((Ma-1) is the linear part of Ma-1-
Proof. Denote Fd f od.d). We can restrict to compute I(N o (M ........ Ma)1,
since, by Lemma 7 we know
(M, Ma)) I(N Ma)).
Each d-layer neural network thth in
can be written, for each input 8, as
( = Sdhh d (B)
(vh = 1,...,88) sa)
where
The map ddh is the hith element in Fa and is linear since Ma has null bias.
The the map n 1 is (d - 1) layer network belonging to (M, Ma-2. A(Ma-1) 1)).
The vector y is bias term in the translational part of Ma-1, namely the invariant sub-space Xa, and has complete bias subordinate to a partition Q. Hence,
yrlp.
(8)
PEQ
In a similar fashion, define d- in N( some 54-1 2 1. Note that, due to Remark 4
Ma-1, A(Ma-2)) for each 1,..., Sd-1 and
8d-1
d-1
(9)
for some 21, .1...., Fea-1 R. Therefore, by substituting both 8 and
( into 7). get
(M -d
Σ xm
(10)
Recall that ddh. is a linear map from R Xa to IR Xaii, defined by the elements o = 06 od. (es) for each input entry E Xa and output entry à: X
With this notation, we can express 10) in coordinates as follows
d.h T
2.)(3)
Σ
d.h pki
Σ
(1) Vi
(11)
xe
21

---

Published as a conference paper at ICLR 2025
For each Xa. let P be the unique element in Q containing Then y/s yps where yi is the coefficient defined in (IT). and yp is the one defined in
Hence, can write as follows
Sd-1
(B) = Σ
Σ
(3) +
Pki o
3t
PEQ EE P
for each output entry h in TR. Xa-1,
Thus, an element 3 belongs to (M Maa1:Fa)) if and only if
6d-1
Σ
Pii
d.h
Σ
Ftll
d-1.t (1)) + yr = 0
(12)
PEQ
iEP
for each Fe. Vp, h, k, and 1
Assuming that a non non-polynomial and setting a, = Øxs and b; = (B)- the second part of Theorem implies that (1/
d-d-1, (3))s, solves 12 for specific h and & if and only if
(n d (B))
U
n
(n (nr-h(()) (7)) d- (x)
n d (?) 0
QEVA.N L.jEP
PEQ
Note that 3 satisfies
12 for specific h and l if and only if (11--1. (3))e. satisfies it. Hence, 1.t
EE U
{7
1st M d-
(7) fi d- 1, (7) vi..
(13)
QEWA,K KJEP
By the definition of (Ma-1)is, we get
IWN M8-2, (Ma-1) {8 17 (
-11 -n (B) 0}.
Therefore, satisfies 112 for specific and & and only if
e
U
I(N PEQ
n
Ma-2, (Ma-
QEWN, (JEP
Since has to satisfy (12) for each h and k, we finally get
INN .... Ma)) n U QEVAN
n
Ma-2, (Ma-1)ig)).
PEQ
S.EP
Remark Theorem could actually be stated with different activation functions for each layer, as long as they are all non-polynomin However, for readability and simplicity, we have presented the results using single activation function.
Remark 6. Here, we demonstrate that the complete bias assumption necessary for all non- polynomial activations to achieve maximal separation power. Specifically, let us examine the separation power of the set of shallow neural networks where all representation spaces are one- dimensional and the hidden layer has null, and therefore incomplete, bias term. The main concern the separability of opposite inputs B and 3. This reduces to study the identification equation
yo (3x) = y-(33x)
for each æ, y E R. Any even function a, including non-polynomial ones, solves this equation but does not achieve maximal separation power, which could be reached by adding a bias term, as shown in Theorem 2
22

---

Published as a conference paper at ICLR 2025
B.2 THE ROLE OF ACTIVATIONS
Proof of Theorem 2 We prove that non-polynomial activation functions have equivalent separation power by induction d.
d = 1 then I(N((M)) = ((M) which does not depend on a.
Now suppose that (M Md-1)) does not depend for each sequence M1,-.., Md-1-
Then, observing
IM Ma))
n
I(N Ma-2, (Ma-1)is)),
PEVA,A PEP L.jEP
we note that I(N, [M....., Ma)) is independent a as indices such as h, k and i, are independent of o, well I[N (M,,..., Ma-2, (Ma-1) is by inductive hypothesis.
Finally, the first part of Theorem 2 follows directly from the proof of Theorem | and the last part of Theorem
B.3
THE ROLE DEPTH
Proof of Theorem 3
To prove the first part of the statement, by Lemma 5 it suffices to show that
(M M Ma) (M M
M Ma).
(14)
12 villmnes
for each 2 1.
Moreover, Theorem implies that is enough to prove this inclusion for a fixed non pon-pooylomial o; then Theorem 3 will hold for any other pol-polyommill activation as well. Therefore, let be the ReLU activation function, noting that in this case a oa a.
In particular,
δ = 3..0...0ō ė idæx, o . idgx,,
n-times
for each 2 1.
Thus, each neural network Oso . oo o1 in N (M1 ..... Mi.... Ma) can be written as o da ã 0 di+i Jo idgx, o idæx, ő Φi 00 δi
n-times
which is element of Na (M..... Mr
M
Ma), thereby proving (14).
n-times
The final step is to prove the stabilization property. This is achieved by recalling that, by Proposition 2 and Theorem I
IWa((1, Ma-1, Ma) = U n I(Na(M,,... Ma-2 (Ma 1)))
(15)
h PEVI.. PEP JJEP
Define
Cn = I M M
M M
My))
times
for each N. Recursively applying intersections of elements the finite set
15 both On and Om can be represented unions and
C (I(N, o M Mi-1, (Ma))a
We can reformulate the descending sequence (4) follows
Cn C Ca-1 S .... Ci
which stabilizes due Lemma 2
23

---

Published as a conference paper at ICLR 2025
Lemma 2. Let
be finite collection of sets. The following statements true:
Let Cu = {Ci, U...UC, | 1 i1....,y I d, r E MY be the collection of unions of a finite number of sets in C. Then Cu is finite.
Let C- {Ci, n.....CC, Cr 11 11......, iy S d, re NJ be the collection of intersections of finite number of sets in C. Then Cn is finite.
Let ê the smaller collection containing C which is closed by intersection and union. Then
C= (Cn)u (CCu) and, in particular, is finite.
In particular, ascending and descending sequences of inclusions in C stabilize.
Proof. To prove the first point, it is sufficient to note that duplicates in the expression Ci U... C. can removed. Therefore, cardinality of Cu bounded by the number of possible tuples i1 21...., which are 2dd The proof of the second point is analogous.
By the distributive property of intersections with respect to unions we obtain that each element in can be written as
(Ci,,, n Cia.a, U U (Ci.,, Ci..a
Hence, è = (Cn)u- Similarly, using the distributive property of unions with respect to intersections, we get = (Cu)n. In particular, Č is finite as Cu and, hence, (Cu)n are finite.
The repetition threshold may vary depending on the model and representation. For example, k-IGNNs being equivalent to k-WL, have a repetition threshold proportional to that of k-WI itself (Maron jet al.) 2019a] Geerts 2020). In contrast, the Proposition 3 demonstrates an example stabilization after just one repetition.
Proof of Proposition From previous observations, we know that
p(N (V, ,...., CV..,
, ( S P(N (V, RIV G/H))
(16)
Note that the family of equivariant continuous functions Co(V, cannot separate H-orbits in V. CV Indeed, for each E CV(V, RG/H), [hb) hf(v) f(v) for each h E H. Hence, Proposition
implies that No R G has the finer separation power between families of functions in CV(V, RC This implies equality in (16). concluding the proof.
B.4 THE ROLE OF INTERMEDIATE REPRESENTATIONS
For now, we focus on developing the notation necessary to state and prove Theorem of our network of interest is follows:
The structure
7:V 6 V1 3 - V'VV"' 5 V Vi" 64
Va da+1
with E (M, Ma).
To formulate the identification equivalence relation of these networks in terms of the identification relations of simpler architectures with only V and V" as intermediate representations, we need to define the projection map ,' & V" + V and the immersion map é' V' V V", Similarly, we can define x²" and /". Furthermore, for any G-representation W, we define
(W, V' e V") Aff and ! Aff v W) + Aff W)
f for'
Similarly, we define n" and ""* Let M be a subspace of All (W V @ V"), its image n. (M) is subspace of (ff V') and
M = + + +
Indeed, each f E M can be expressed as f r'f x" ff( *ffff, identifying V and V as subspaces of V. Similarly, for M subspace of (V + VV"WW)
M = (') + (M)
24

---

Ma). This is Published as a conference paper at ICLR 2025
Hence, can write
(Mi,,...., - N (MM))
(M++1) + (M++ Ma),
and the problem informally stated above reduces to determining the separation power of the entire family N (M,,,..... Ma) by understanding the separation power of the smaller families (M,,, M,, (M+1),,..... achieved by the following theorem.
and Na (M
Theorem 8. With the notation defined above, we have
(M M.N..MM....MMM..... Ma)) p(N (M
(M.), (M++1),
"M,,, ( (M.
Proof. Note that & 15 c Φ. Indeed, 1h o (Ø, Φ)) (vi Φ) (Φ o U x x)) 2 10 and
ăv' L'ā and Ôn' = n'o. Similarly, for n" and 1".
Furthermore, 1'+ (T' (7+ (")
( + n" since
(L' ( (1) ( -") idv idy a Ov." + 0v: + idv:")
('' + o = (i' n + 11 TT")
(1' + ( o (T'
We now need to prove that (gh' + 111" (T' + x"))
(17)
Indeed,
(1b1l 4h
(T (
To -
= ("+""""))))
Hence, thanks to 17
Na 1, M Md)
No [M 1....... (M, + (M.), (M++1) + (M, M M.
No (M. T. (M.) T"M,),, (M++1)) + 1" (M,-1),
Ma-1,Ma)
By Theorem 1 and the previous observations, can limit to study spaces of the type
(M,) + + (M++)+ + n (M++1) NM (M,) + (M,)), (1 (M++1 Dani No 1,..., 75 (M.) (Mi), (MMM(M) thanks to the linearity of the map ø + (o) Note that
No NM 1
NA NM,,, (M, + (M,), (c' (M++1)) = (M,, (M,((,,.,,, as n' o = and both projections and immersions commute with activations. From Lemma we get I(N (N.,,,,..... T.. (M:) + (M,), (M++1) + e"x (M)+)))))))) IIN,((M,, 7., (M.). (t" (M) n (M.., (X"M Combining all the above results, we conclude the proof of the theorem.
(M.),, (e' (M++1) m
Proof of Theorem Theorem is consequence of Theorem g in the case where M, is the full set Affa(Vi-1, V.). Note that
*.. Aff V @ V/" Aff
and
A' Affa(V e V.", V++1 = Affa
Similarly, for nh and "*
25

---

Published as a conference paper at ICLR 2025
B.5
THE ROLE OF REPRESENTATION TYPE
Proof of Theorem 5
Write H/K = t K. we have the following injection
R
R
6:
(18)
CgHt +
&
i=1
and projection
π RG/K
R R//
(19)
EgK' + CgHt.
Note that T idga/n, indeed,
(((e(H))
Σ ((ggh Σ
chh CyHt,
gh;H- gH for each i 1.....8.
Consider the following diagram
77 V
HG/H nn, HG/H V
W
:/VV V _ RG/K du, RG/K
W.
From network 7j in N (V,...................... .....,RGGHH. RGGH W) composed by d, th and a we want construct new representation 1/ defined as follows. Let o' Φ, v/' 16 and 5' = Loō and note that vi o' o o = & ग. o o o = o Φ. Hence, substituting o o & with v/ o o of inside the definition of do not change the function, and embeds it into parameter space with intermediate representation R instead of RG/H But to prove that 1j is neural network, we need to prove that o' is a point-wise activation function for some real-valued function o'.
is wise activation associated
R + defined on RG/H we have that
T( Σ /HEG/H
agHCgH) = Σ
(agh )ggH
gHEGjH
On the other hand, we have
ō'( Σ gKeG/K
(gKeşk) = LOO0TT
Σ
(gKegk)
gKEG/K
Loā(
Σ
AghKCgH)= =1
E
ol ghKEgH/KK
Σ
aghk)cgH
gHEG/H ghKeg
gHEG/H
o( Σ aghi)
Σ hKEHIK
Cgh
gHEG/H
ghKEgHH/K
Σ of Σ
aghK )
gKEG/K NKEH/K
Note that the map
Σ 0gK H
Σ aghKEyK
a:
gKEG/K
KKEH/K
is linear and G-equivariant. In particular, note that ø' Gx where we denote the standard point-wise activation induced by RG/K ōg. to distinguish it from o, the
26

---

Published as a conference paper at ICLR 2025
point-wise activation induced by but defined on R Hence, substituting th o o with V o' & x// #K a H', we obtain an immersion of 1 in (V. BG/K ..... W). Hence NV ..... (o.(V,..,,RG// RG/H W) S NC.V, ..... W) and p(No(V..... (UNo(V BG/K W)) pVVo(V RG......RGHHH.... RG/H W))
We are now going to develop the tools to prove Proposition 4 Lemma Let M = (V, RC)), then I(Ma,) = I(Mo-la,e) = I(Mav-1,e .)). Moreover, (3,8) E (MMg,e) if and only g3 = B¹.
Proof. Let V + V. where setting H fe), we know that Homg (() = Home (IR C RC) @ ... @ GRKK K, R is
R/ for each i 1, ,,..,, 8. By Proposition 14 and
generated by functions Rg TG/K, for each gi K; E G/K, K for each i ,,...,8. 8, and G//K, is the projection of V onto V; RG/K:, Moreover,
RRy.K, TG/K (3) (Rii TG/K,
Σ KKGGG/K;
BuK,EaK)))
1 [K,] BugiK. K.
For each g E G, we have that
I(Mu,o)
(8, To,K, - -RRg: -VVVg E &G/K)
{(,,3') Bug.K, B.gg = OVVg E G/K,]
{(8,8') 0 v~ BB)
In particular, we have that ((,.,v) = I(Mp-1a,e). Hence, (3,8") E I(Mg,e) if and only g.3 = 8.. Finally, in a similar way, we are able to observe that I(Ma,u) = I(M I(Mae-
Proof of Proposition In what follows we have to consider G LJ G, to distinguish the two distinct copies of G. we denote G' as the second copy of G and, and when g is an element of G, will indicate as g' the analogous element in G'.
Define M = Aff and N Affa (RC, (RC,HRRC < Homg &RC", R.HH). Proposition implies
P(No R)) I(N.
Note that N = RRHg - RHyg where functions RHg are defined as
f1 if e k (Rugles)) sh otherwise.
An element Q in V s H is partition of GU G", where for each P E Q the intersection PO L sH' g have the same number elements in sHg and sH'g. Due to Remark g we can just consider V Hg..s containing the partitions of G U G' whose only parts are P {u,v) v for u E sH and
E sH' g, otherwise P is singleton not containing clements in slg sH''.
Hence, by Theorem M
(M, = n
U
n
I(Mu,v)-
(20)
Hg.eH ne (uNDER
If we prove that for each Hg and sH
U
n
I(Mu,r) = U I(Mne)-
(21)
QE
(u.DEE
KEH
27

---

Published as a conference paper at ICLR 2025
then done. Indeed, thanks to Lemma 3 (3.3") Uneh I(Mr,e) if and only if there exists
some h H such that h3 = 3 Moreover, (1 does not depend on Hg and sH then the outer intersection (20) is trivial.
Now to prove 21 we first show that
U
N o( S U I(Mhe))
Ha (u,UEE
hENl
Note that if {u, v) E and u, v E sHg, then, by Lemma 3
I(M,,)) I(Mang.ann)) I(MAN-1,e)
Therefore,
n I(Ma,e) (I(Ma S UU-H I(Ma,)) (u,+lE
NEH
The right-hand side is independent of Q then the union each Q in Hgg of sets the left-hand side proves the searched inclusion.
To prove the opposite inclusion, for each h define Pa V Hg.s the partition containing the sets {ghls, gts) for each H and the remaining singletons. Then, note that, by Lemma
n
I(Mahtaggta) o(
(ghts.gts)EPh
Hence,
U I(Mnne) =
n
I(M g(Mghts.gta) 5
U
N
I(Ma,))
KEH
hEH (yhts.gts)&Pn
QEV'ng.at ng fu,ulE
This concludes the proof.
C IMPLICATIONS ON PRACTICAL MODELS
Lemma 4. An element (a, () p(1-CNN) if and only there exist a permutation of a E Sn such that a; = -Bo(t) for each i = 1, ,,
Proof. Write [n] LI [n]] = (1...., n, 1' n/}, and notice that A Affz, (IR", TR)" = (1|m) 11 (xp))
hence as defined in Remark g is composed by partitions Q of [n] L [n]] such that
Q = [(tj}}} 1 [n],] / E [n]').
Recall M (idg=gw"') Note that (a, B) E I(M 1.gg) = (idgnaw") and only if a; = By-
Moreover, for given Q in V. we have (0, Nireo I(M if and only if, given the bijection [n] in]' associating i to j', a, Bo(1) for each i I,...,
Notice that, by Theorem
I
(a, 3) p(Na(M Affz, RR
U
n I(M
QE ie'eQ
which is equivalent saying that there exist a permutation of Sn such that a; Bo(i) for each { I.....hh n.
Proof of Proposition Note that p(1-CNN) is characterized by Lemma as follows: (a, 3) p(1-CNN if and only if there exists a permutation E S, such that a₂ = Bo(i) for each = 1,..., In contrast, Proposition 4 shows that (a, 8) E p(Na(M' Affz. (IR" RR)) if and only if there exists an element y En such that a; Bi-g (mod n) for each Z, S,, hence p(n-CNN) P(1-CNN, as desired. The proof of the chain of inclusions p(n-CNNN
1,...,n. Notice that for n
P(2-CNN) P(1-CNN)
direct consequence of Lemma since: 1-CNN 2-CNN ... n-CNN.
28

---

Published as a conference paper at ICLR 2025
D FUNCTIONAL EQUATIONS
In this section, we introduce key results from the theory of functional equations that are necessary to prove Theorem [ functional equation, by definition, is an identity involving unknown functions as variables, and common examples include differential and integral equations (Kannappan 2009). Here, are particularly interested in the class of linear functional equations, which explore greater detail in the following section.
D.1 LINEAR FUNCTIONAL EQUATIONS
Linear functions equations are functional equations which, for given a; E and b; E IRd, are defined
by
(b,0) =0
(Vx E IR
In particular, Theorem 9 is fundamental tool in the proof of Theorem 1 since it characterizes the
set of parameters b1.... b, for which the specific case of linear functional equation in (22 is always
satisfied for a non-polynomial a and arbitrary 01,..., On IR
Theorem 9. Let a IR + R be non-polynomial continuous function and a1 a On E R. Let P be a partition of [m] and define
v= V=125P Σ = Q)-
The set B of elements
E R= which satisfy
ΣΣ PEP EEP
a.a bb x up) =0
(Vxr E RR = (yP) E ERR)
(22)
U [bb..... .bn) bi, =... die vfi E O)
(23)
QEV
Equivalently,
B= B n ((b.......b .,) 11, - b, = 0}.
PEO
I.jPP
For arbitrary continuous funnctoss a, it is only true that the set defined
23 is contained in B.
To prove Theorem 9 we first need prove some auxiliary results. Theorem TO stated below, is reformulation of Theorem 2.27 in Kiss & Laczkovich (2014) adapted here to the context of continuous real functions for convenience. For further discussion, refer to Appendix D.2
Theorem 10. Let ai..... On non-null real values, and let bi....,b bn E R be distinct real vectors. Continuous solutions a IR- + R of
Σajo a ...xty) x))== =0
RRY ER)
(24)
are polynomial.
Moreover, to prove Theorem 9 the following notions and auxiliary results are required.
Definition 14. Let b = (b1....,byy bw)) E Ruxm, the identity pattern of is the coarser partition P of [n] such that b; = by for each i.j E and P.P.
Theorem 11. Let R + I be non-polynomial continuous function, and a1,..., On R. Then
b = (by....,by b..) E Raxm satisfies
Σ a, be + y)) -0
(Ver R" R)
(25)
and only if Eiep 04 0 for each P in the identity pattern
29

---

Published as a conference paper at ICLR 2025
Proof. Let Pi,...,PP Py be the parts in the identity pattern of b such that ΣsEp, ai # 0, define aj = Eiep, Os then we can rewrite the equation in (25) as
Σ ==1
Lajo
x + =0,
-0=
9. the value of b/j is set to the value of the b;s for i E P,. which are all equal to each other. Since the af are non-null and by are distinct, by Theorem 10 have to be polynomial which impossible. To prove the opposite implication, let be the identity pattern of and write
where, for each j = 1,
(be -E aio (b.. + = Σ PEPiEP
Σ iEP
(b. by 1. x
PEP
where the last equality is possible because = by for each i, E P.
Remark 7. Note that the second implication of Theorem 11 holds for any Ø, including polynomial functions.
This theorem gives the following corollary, which is the one actually needed to prove Theorem 9 Corollary Let a IR + be a non-polynomial continuous function and a On E Let P, be the set of all partition of [m] and define
= (PEPn
Σ a; =
VEP
The set B of elements (b....., .a.....,byy bn) Ruxm satisfying 25 is
(tb bn) bi. =... biu Vii it P).
(26)
PEO
Or equivalently,
B B= U n ((b, ((bi....,bo bn) bj =)--
PE PEP JJEP
For arbitrary functiion 0, it is only true that the set defined 26 is contained B.
Proof. Define
B'= ((b... bn) bi, big Vii E
DEB
By Theorem 11 b satisfies (55 if and only if Eiep 0 for each P in the identity pattern of B² then there 0 for each P E P, (55 is
Thus, B B'. To prove the opposite inclusion, note that if b (bI,...,b,, exist P E + such that 6 has identity pattern P, then, as Eiep verified. Finally, note that this implication holds for any a by Remark 7 proving the last claim in Corollary
Proof of Theorem 9 Notice that the problem
Σ
Σ
a.a by +rr)
(Ver RR" (yr)rep E ER))
(27)
PEP iEP
is equivalent to
ΣΣ
0:0 by + yp + =0 (Vx E ER V ERPWEE)
PEP
through the change of variables yp + yp + for each P E P. This problem is in turn equivalent to
Σ a, b, 8 +0) =0 (vā E Rd RRVEER
(28)
30

---

Published as a conference paper at ICLR 2025
due to the following change of variables
bi ep
b, -
for E P. and å +
ypep
where {EP) is the canonical base of IPP. Corollary 2 implies that the solution to (8) is
U (()), QEO
8n) by =... = bin V(i E 2}-
(29)
Note that by = di. if and only if big = ... = bi and (i.....,..)) C P for some P E and only if bi, bi, and (i1,..., ix E Q for some Q s P.
Recall the definitions
[Q Pn Σ a; OYP 2 and v (QSP)
Σ a. OVP 2}.
Noting that V (Q E 2 S P}. equation (29) implies that the solutions of 27 are
U ((b ((b......bbl bn) bis -...= bi. vfh 1x) 2). QEV
The final claim follows directly from the concluding statement in Corollary 2 Remark 8, In Theorem the union
U ((b). .l.,....bbu. bn) bi = =... =...= =b. bic Vii...... (x) E 2] QEV
(30)
has redundancies. Indeed, {bb1,..., bn) | bis = =... = bi Vfdi.... in E 2} is contained in {(b,...., bn.) bis
big Vii in} RJ for each @ R finer partitions of P. Hence, the set defined by (30) is the same
U ((b.....,bb br) by,
bt. V(n , & e Q}
DE
where V is the subset of containing only the minimal partitions with respect to the refinement ordering.
D.2 GENERALIZED POLYNOMIALS THE CONTINUOUS CASE
In Appendix D.I
we employ Theorem I0
reformulation of Theorem 2.27 in Kiss & Laczkovich
(2014), adapted here for convenience to the context of continuous real functions. In particular, the original version of this theorem proves that arbitrary complex functions satisfying (24) are generalized polynomials, defined as follows.
C is generalized monomial function if there exist symmetric function F C > C additive in each of its variables, such that oxx) = F(x....,.2) (.) for each x E C. A function a C C a generalized polynomial if it finite sum of generalized monomials, we say that generalized polynomial a is real if a is real and there exists symmetric function F: C - R. additive each of its variables, such that (x)) F(x....,I) for each x E RR.
Definition 15. function C
Trivially, since complex functions satisfying (24) are generalized polynomials, any real solutions real generalized polynomials.
To conclude the proof of Theorem T0 remains to show that continuous real generalized polynomials
are simply real polynomial functions, as shown by Proposition 17
Proposition 17. real continuous generalized polynomial a real polynomial function.
Proof. The proof of Theorem will be analogous to the proof of the classical proof that any continuous real additive function is linear, see Theorem 1.1 in Kannappan (2009).
First, show that real generalized monomials are monomial functions rational numbers.
31

---

Published as a conference paper at ICLR 2025
Indeed, suppose first that f is real generalized monomial and let F: R= + R be the symmetric function additive in each variable and such that f(x) F(z......)) for each r R. Note that for each r N.
+ Fi Fnl F1.1...... ", ,i,...., +... F Ii....... R.) = r FI11,..... Ii. ,i,...,,tt)
F( ......... p3j ..... Fn) = (111............................
(31)
Note that F(ri...., 1, Fnn) 0, indeed
F I/- .., F(r 2i 0 + 0, 2i+
(32)
kn) Fl 24 Ii+1....,
Eliminating a term 2,-1, 24+ zn) from both the sides of 32 we get the required result.
Furthermore, F(E1,.....
Fnd. Fn) - -F(21.... . Indeed,
Fi Inn) + F(11,.....
Fn) ,.... F(11, ................................ .i...., Fnn 0.
2i,...,,
(33)
Equations 31 and (33) yields
F F(a TTi, ,....., = ( . ,
(34)
for each E Z. Note that by substituting rı; y/: obtain
F(I Yk.
.e...., II)) P PI ....... ,,,...,
Equivalently,
I "i "ii...,, FII............................. F(r......
(35)
Equations 34 and 35 prove
"(Z....,I,,........ = FF(z.....3
(36)
for each E Q Hence,
f(rx) Frr.,....... rx) = F F(F 1.' f(z).
for each E Q In particular set and f(1) = R. f(r) = rr = cr
Hence, a real generalized monomial is monomial on Q
Finally, we can prove the general case where f is real generalized polynomial. Recalling that real generalized polynomials sums of real generalized monomials, they sums of real monomial functions on Q, namely polynomial functions on Q
We conclude by noting that, since f is continuous, it extends polynomial function on R due to continuity.
E TECHNICAL LEMMAS
In what follows, let C, D and be families of functions in C(X, V), where X is topological space and V a real vector space.
Lemma 5. IfC C D, then p(D) P(C).
Lemma 6. Let C and D be two families of real-valued functions such that each of them contains at least constant function. The equivalence relations induced by their identification condition are linked by the following conditions p(C D p(C D) p(C) p(D).
32

---

Published as a conference paper at ICLR 2025
Proof. Let us prove the first equality. Let be the constant function in D. Hence p + D) S +c) = p(C) S p(C) U p(D). To prove the inverse inclusion, suppose there exists a function f either in C or D separating and y. Without loss of generality, suppose C, f c + D would be separating x and This conclude the proof of the first equality. The proof of the second equality follows from the definition of p. Indeed,
((CUD)= - ((x,)) ((x) CWDDE
p(C)
Remark 9. Note that, with slight modifications to the proofs, analogous results to all previous lemmas can be derived by substituting with I.
Lemma 7. If Fa is set spanning null-bias space Md then
(M,..........
Ma-1;Fa)).
Proof. Trivially,
No IM, Ma-1, S Ma)).
For the zero-locus analogous of Lemma
((No(M,... Ma)) S (M Ma)1.Fa)).
To prove the opposite inclusion, write Fa = {01,.... o.) and note that each neural network r7 in No (M,..., Ma) can be written as
" (mid1 for some 21. E R and n EN Ma-1). Moreover, note that
x.D.s) 00 xn (0) (0)00000²
Fa(ds o o 1
0:0ā. 1-1 EN F.)
for each i = I....,8. 8.
8 I(No (M ..... M, then
(B) = 21(01 - . ... +.. 22,0 00000 0.
Thus,
IWN Ma-1, Fa)) S I(N (M).....))
completing the proof.
33


Reviews:
[{"review_id": "aQty1qlsN8", "reviewer": "Reviewer_1QZn", "summary": "This paper considers the separation power of equivariant networks. In the setting of permutation representations and element-wise nonlinearities, this paper charactierizes the set of identified points and then prove (1) all non-polynomial activations equivalently share the same and maximum separation power; (2) larger depth indicates better separation power; and (3) separation power is independent\nof invariant hidden features.", "questions": "It is an interesting and solid paper to me. However, it may not have a significant contribution due to its limited setting. If I understand correctly, this paper considers only feedforward architectures with element-wise activations under finite groups. Moreover, many results seem not superising, which may weaken your contribution to help equivariant architecture design.\n\nFeedforward networks with ReLU activations may only allow generalized permutation representations since equivariance properties require that the activation and group elements are commutative. If it is right and can be extened to general element-wise activations, it will enhance the soundness of your setting. What's more, the network with biases and input $x$ may be equivalent with that without baises and input $(x,1)$, which may further extend your results.\n\nIt may be not surprising to solve the identified set since this paper adopts element-wise activations and permutation representations. While all common activations seem to be monotonously increasing and bijective, the choice of activation would not be assumed to affect the separation power. Besides, the set $\\rho(\\mathcal{N})$ is assumed to have a lower bound. As a result, when we increase the depth to infinity, it is obvious that the identified set $\\rho(\\mathcal{N})$ would not change after a threshold of the depth. So a more explicit result would be more interesting. \n\nTherefore, I think this paper is interesting that may help improve our understanding to equivariant networks but may have relatively limited contributions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* This paper is well-written and easy to follow.\n\n* This paper considers an interesting and important problem in machine learning area and extends our understanding of separation power of specific equivariant architectures.\n\n* This paper's definitions and statments are clear,  and its theoretical analysis is also solid.", "weaknesses": "* The theoretical results in paper are interesting but not so supervising, thus it seems unable to improve equivariant network design.\n\n* The setting in this paper is somehow too specific (finite group, and feedforward architectures with element-wise activation if I understand correctly), which may limit its contribution.\n\nMore detail can be found in Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "l1UgALGj4H", "reviewer": "Reviewer_rxAf", "summary": "This paper develops a theoretical framework for analyzing the separation power of equivariant neural networks, such as convolutional and permutation-invariant networks. The authors present a complete characterization of inputs that are indistinguishable by models derived by a given architecture, and derive how separability is influenced by hyperparameters and architectural choices (activation functions, depth, hidden layer width, and representation types). Key findings include: all non-polynomial activations achieve maximum separation power, depth improves separation up to a threshold, adding invariant features to hidden representations does not impact separation power, and and block decomposition of hidden representations affects separability.", "questions": "Given the superpolynomial complexity of the recursive formula, are there special cases where computation becomes tractable?\nWhat are the trade-offs between separation power and other desirable properties?\nIs there a connection between degree of polynomial and separation power?\nHave you explored connections between separation power and generalization bounds?\nAre there cases where maximum separation power might be undesirable?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The strengths of the paper are numerous. The authors provide a novel theoretical framework for analyzing separation power in equivariant networks, creatively combining group theory and functional analysis. Particularly interesting is the twin network trick which transforms a network separation problem into a zero locus problem for neural networks, allowing the application of recursive techniques for solving zero locus problems. The authors also provide new insights into how architectural choices affect the expressivity of a model – this is extremely valuable for the community.\n\n\nThe authors have provided clear motivations for the paper, rigorous mathematical proofs for all results, and clearly stated assumptions as well as limitations. Authors not only provide theorem statements but also give the reader intuitive understanding. The paper also does a good job of building from first principles which makes the read even more enjoyable!", "weaknesses": "The authors clearly state the limitations of the work. An obvious weakness is the computational complexity, but the goal of this paper is to build theoretical frameworks which is a very challenging task. It is understandable that the computational complexity is not practical. Though efficient computational approximates could be explored.\n\nThe paper could also benefit from experiments showing the effect (or lack thereof) of depth on separation power, as well as the impact of different activation functions. But again, the paper is a theoretical one and does not need to show experiments to be able to stand on its own legs.\n\nIt could be interesting to see the effect of initialization in separation power.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "b9etuUHz4Q", "reviewer": "Reviewer_ceR4", "summary": "This work analyzes the separability of deep learning models with equivariant architectures (that is, architectures that are equivariant to specific group actions on the input and output spaces). Separability in this case means identifying pairs of points that take identical values under all networks of a fixed architecture. The work only considers separability of pairs of points. The paper makes a few assumptions on the network, the most notable being that the network uses a permutation representation (and hence the group $G$ is assumed to be finite). After setting up notation related to equivariant architectures, the work describes the “separation trick”, which essentially shifts perspective from looking for points $\\alpha, \\beta$ where $f(\\alpha) = f(\\beta)$ for all $f$ in the function class and instead looks at pairs of points $\\alpha, \\beta$ where $\\eta(\\alpha,\\beta) = f(\\alpha) – f(\\beta) = 0$. That is, the zero locus of $\\eta$. The paper proves a recursive formula about separability within this framework and then draws some conclusions about how various architecture choices impact separability (e.g., depth, width, etc.).", "questions": "- The reviewer was surprised that despite this being a result about equivariant architectures, group and representation-theoretic machinery featured very little (acknowledging that the reviewer did not go through the supplementary material closely). Is this the case or did the reviewer just miss something?\n- Have the authors thought about separability of more than pairs of points? Can anything be said about this?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Clarity:** The work is clearly written and relatively crisp. The Preliminaries section does a decent job introducing the basic tools needed in the paper (e.g., the notion of equivariance, etc.). An explanation of how the work fits into the current research landscape is provided. Despite being a theory paper, this work should be accessible to a wide range of readers.\n\n**Problem importance:** While there is now a substantial body of work on equivariant architectures, both in terms of architectures for specific symmetry groups and applications, and theory, significant questions remain. Gaining a better mathematical understanding of what we sacrifice by imposing equivariance in our models is an interesting and important question that deserves more research.", "weaknesses": "**Theorem 1 is hard to read:** As this is one of the critical contributions of the work, it would be worth polishing it to make it more readily understandable, especially since the work takes pains in Section 4 to layout the framework for this result. It feels like in the process of trying to make the theorem more “informal” all the explanations were taken out but the mathematical notation was retained. For instance, what is the symbol “\\leq” at line 377? The reviewer can make a guess, but it would be good to state this explicitly. Similarly, there a 6 different indices in (5). Is it possible to either break up this expression or build up to it? It is also a little hard to read since 4 of these indices ($h$, $k$, $\\mathcal{Q}$, and $P$) don’t appear in the argument. This reviewer’s advise would be to cut down on some of the lengthy preliminaries and devote a bit more time to setting up and describing Theorem 1. It was hard for this reviewer to draw much insight from this Theorem.\n\n**CNNs are equivariant to integer translation, $\\mathbb{Z}^2$, not cyclic translation:** As far as this reviewer is aware, it is relatively uncommon to use circular padding in computer vision. For this reason, most CNNs are not equivariant to a product of finite cyclic groups, but rather to $\\mathbb{Z}^2$. It would be worth stating that Example 4 does not represent the majority of CNNs.\n\n**Hints at proof strategy:** While the reviewer appreciates that space constraints mean that the proofs need to be moved to the supplementary material, it would make the work more valuable if a high-level description of how the results were proven were included. After all, it is sometimes the case that the insights in the proof are more valuable than the theorems themselves. Again, the reviewer would advise shortening the preliminary material to provide more space. For instance, the preliminary material discusses group representations but (to this reviewer’s memory) the only place this later appears is a reference to the regular representation.\n\n### Nitpicks:\n\n-\tLine 161: “From a practical viewpoint is fundamental to understand which are the hyperparameters …” $\\mapsto$ “From a practical viewpoint it is fundamental to understand the hyperparameters…”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "FhQBV08g2S", "reviewer": "Reviewer_ESKT", "summary": "The paper proves a number of results about the separation power of equivariant networks. In particular, it focusses on networks equivariant to regular / permutation representations of finite groups. The authors give a recursive formula for the set of pairs of inputs that are indistinguishable by any function in the function class under consideration. Further theorems clarify the role of non-linearities (they don't matter, provided they are non-polynomial), depth (increases separation power, but not indefinitely), multiplicity and invariant features (don't affect separability). Finally, the paper discussed implications for IGNs and CNNs.", "questions": "Typo: Line 162 has a typo; \"ING\" should be \"IGN.\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The paper provides a detailed characterization of input separability for regular equivariant networks.\n+ The theorems shed light on the factors that do and do not affect separability, which is quite insightful.\n+ The theorems seem non-trivial and novel", "weaknesses": "- The paper is rather long-winded, with results starting only on page 7.\n- The \"twin network trick\" is presented as a key insight, but it seems like a rather trivial observation to me. Eta(a) = eta(b) iff eta(a) - eta(b) = 0. \n- Not much intuition is provided, e.g. for theorem 1, which I found hard to understand or see why it must be true. Proofs are all in the appendix. It would be much better to move some background material to the appendix and explain the intuition behind the theorems and perhaps a proof sketch in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)