Frame Averaging for Invariant and Equivariant Network Design
Authors: Omri Puny
Matan Atzmon
Edward J. Smith
Ishan Misra
Aditya Grover
Heli Ben-Hamu
Yaron Lipman
Venue: ICLR 2022 Oral (2022)
Keywords: Invariant and equivariant neural network
expressive power

Abstract: Many machine learning tasks involve learning functions that are known to be invariant or equivariant to certain symmetries of the input data. However, it is often challenging to design neural network architectures that respect these symmetries while being expressive and computationally efficient. For example, Euclidean motion invariant/equivariant graph or point cloud neural networks. 
We introduce Frame Averaging (FA), a highly general purpose and systematic framework for adapting known (backbone) architectures to become invariant or equivariant to new symmetry types. Our framework builds on the well known group averaging operator that guarantees invariance or equivariance but is intractable. In contrast, we observe that for many important classes of symmetries, this operator can be replaced with an averaging operator over a small subset of the group elements, called a frame. We show that averaging over a frame guarantees exact invariance or equivariance while often being much simpler to compute than averaging over the entire group. Furthermore, we prove that FA-based models have maximal expressive power in a broad setting and in general preserve the expressive power of their backbone architectures. Using frame averaging, we propose a new class of universal Graph Neural Networks (GNNs), universal Euclidean motion invariant point cloud networks, and Euclidean motion invariant Message Passing (MP) GNNs. We demonstrate the practical effectiveness of FA on several applications including point cloud normal estimation, beyond $2$-WL graph separation, and $n$-body dynamics prediction, achieving state-of-the-art results in all of these benchmarks.

Published as a conference paper at ICLR 2022
FRAME AVERAGING FOR INVARIANT AND EQUIVARIANT NETWORK DESIGN
Omri Puny*1 Matan Atzmon Heli Ben-Hamu"
Ishan Misra
Aditya Grover Edward J. Smith² Yaron Lipman?
Weizmann Institute of Science Facebook Al Research
ABSTRACT
Many machine learning tasks involve learning functions that are known to be invariant equivariant to certain symmetries of the input data. However, it is often challenging to design neural network architectures that respect these symmetries while being expressive and computationally efficient. For example, Euclidean motion invariant/equivariant graph or point cloud neural networks.
We introduce Frame Averaging (FA), a general purpose and systematic framework for adapting known (backbone) architectures to become invariant or equivariant to new symmetry types. Our framework builds on the well known group averaging operator that guarantees invariance or equivariance but is intractable. In contrast, we observe that for many important classes of symmetries, this operator can be replaced with averaging operator over small subset of the group elements, called a frame. We show that averaging over a frame guarantees exact invariance equivariance while often being much simpler to compute than averaging over the entire group. Furthermore, we prove that FA-based models have maximal expressive power in broad setting and in general preserve the expressive power of their backbone architectures. Using frame averaging, we propose a new class universal Graph Neural Networks (GNNs). universal Euclidean motion invari- ant point cloud networks, and Euclidean motion invariant Message Passing (MP) GNNs. We demonstrate the practical effectiveness of FA on several applications cluding point cloud normal estimation, beyond 2-WL graph separation, and n-body dynamics prediction, achieving state-of-the-arr results all of these benchmarks.
INTRODUCTION
Many tasks in machine learning (ML) require learning functions that are invariant equivariant with respect to symmetric transformations of the data. For example, graph classification is invariant to permutation of its nodes, while node prediction tasks are equivariant to node permutations. Consequently, it is important to design expressive neural network architectures that are by construction invariant or equivariant for scalable and efficient learning. This recipe has proven to be successful for many ML tasks including image classification and segmentation (LeCun et al., 1998 Long et al. 2015), set and point-cloud learning (Zaheer al. 2017, Qi et al. 2017a). and graph learning Kipf
Welling 2016 Gilmer et al. 2017 Battaglia et al. 2018).
Nevertheless, for some important instances of symmetries, the design of invariant and/or equivariant networks is either illusive (Thomas et al. [0188] Dym & Maron 2020), computationally expensive
or lacking in expressivity (Xu al.) 2018a| Morris et al. 2019: Maron et al. 2019 Murphy et al.. 2019). In this paper, we propose new general-purpose framework, called Frame Averaging (FA), that can systematically facilitate expressive invariant and equivariant networks with respect to a broad class of groups At the heart of our framework, we build on basic fact that arbitrary functions 6 V RR, Φ W, where V, W are some vector spaces, can be made invariant or equivariant by symmetrizatton,, that is averaging
the group (Yarotsky) 2021 Murphy et al. 2018). i.e.,
1 G
(X)
Σ geG
1. .X) or v(X) G
Σg
g
.X).
geG
Equal contribution

---

Published as a conference paper at ICLR 2022
where G = {g} denotes the group, vb V - R is invariant and v V W is equivariant with respect to G. Furthermore, since invariant and equivariant functions are fixed under group averaging, ie., s 6 for invariant ó and V @ for equivariant 4, the above scheme often leads to universal (i.e., maximally expressive) models (Yarotsky, (021). However, the challenge with equation Dis that when the cardinality of G' is large (e.g., combinatorial groups such permutations) or infinite (e.g., continuous groups such as rotations), then exact averaging is intractable. In such cases, we are forced approximate the sum via heuristics or Monte Carlo (MC), thereby sacrificing the exact awvarianceeeuuivarianee property for computational efficiency, e.g., Murphy et al. 2018)) 2019) define heuristic averaging strategies for approximate permutation invariance in GNNs; similarly, Hu et al.) (202T) and (Suuaibi et al. (202T) use MC averaging for approximate rotation equívariance in GNNs. concurrent approach is to find cases where computing the symmetrization operator can be done more efficiently (Sannai et al. 2021).
The key observation of the current paper is that the group average equation I caa be replaced with an average over a carefully selected subset F()) G' while retaining both exact invariancccequiivriinee and expressive power. Therefore, if can be chosen so that the cardinality [F(X) is mostly small, averaging over F(X) results in both expressive and efficient invariant/equivarian model. We call the set-valued function F : V - 2 a frame, and show that it can successfully replace full group averaging if it satisfies a set equivariance property. We name this framework Frame Averaging (FA) and it serves the basis for the design of invariant/equivarian networks in this paper.
We instantiate the FA framework by considering different choices of symmetry groups G, their actions data spaces V, W (manifested by choices of group representations), and the backbone architectures (or part thereof) Φ, 4 we want to make invariant/equivarian to G. We consider: (i) Multi- Layer Perceptrons (MLP). and Graph Neural Networks (GNNs) with node identification (Murphy et al. 2019: Loukas 2020) adapted to permutation invariant Graph Neural Networks (GNNs); (ii) Message-Passing GNN (Gilmer et al., 2017) adapted to be invarian//equivariant Fuclidean motions, E(d); (iii) Set network, DeepSets and PointNet (Zaheer et al. 2017: Qi et al. 2017a) adapted to be cquivariant or locally equivariant to E(d); (iv) Point cloud network, DGCNN (Wang al. 2018). adapted to be equivariant to E(d).
Theoretically, we prove that the FA framework maintains the expressive power of its original backbone architecture which leads to some interesting corollaries: First, (i) results in invariant universal graph learning models; (ii) is an E(d) invariant/equivarian GNN that maintain the power of message passing (Xu et al.) 201 Sa; Morris et al. 2019); and (iii), (iv) furnish a universal permutation and E(d) /utuiiannt/quivaiinnt models. We note that both the construction and the proofs are arguably considerably simpler than the existing alternative constructions and proofs for this type of symmetry (Thomas et al.) 2018) / Fuchs et al., 20200 Dym & Maron 2020). We experimented with FA on different tasks involving symmetries including: point-cloud normal estimation, beyond 2- --Wisfeiler--ehhme graph separation, and n-body dynamics predictions, reaching state of the art performance in all.
FRAME AVERAGING
In this section we introduce the FA approach using a generic formulation; in the next section we instantiate FA to different problems of interest.
2.1 FRAME AVERAGING FOR FUNCTION SYMMETRIZATION
Let o: V + R and Φ V + W be some arbitrary functions, where V, V.W are normed linear spaces with norms I-lly I..ww. respectively. For example, o, & can be thought of as neural networks. We consider a group G = {g} that describes some symmetry we want incorporate into o, T. The way the symmetries y ε G are applied to vectors in V, W is described by the group's representations Pi : G > GV.(V), and P2 G GT.(W), where GL.(V) is the space of invertible linear maps VVV (automorphisms). A representation P. preserves the group structure by satisfying (g(h)) (h) for all g, l G (see e.g., Fulton & Harris (013))) As customary, we will sometimes refer to the linear spaces V, W as representations.
Our goal is to make o into an imvariant function, namely satisfy o (p) o(X). for all g G and X & V; and & into equivariant function, namely ((p1 ()) p2(0) for all g e G and X E V. We will do that by averaging over group elements, but instead of averaging over the entire group every time (as in equation 1 we will average on subset of the group elements called a frame.
2

---

Published as a conference paper at ICLR 2022
Definition 1. A frame is defined set valued function F: V + 2 x..
1. A frame is G-equivariant if gF(X)= [gh h F(X),, and the equality should be understood as equality of sets.
= gF(),, VX K e G, where as usual,
2. A frame is bounded over domain K V if there exists constant 0 so that (g) lop
c. for all g F(X) and all X K. where I|- lo denotes the induced operator norm over W.
Figure 1 provides an illustration. How are equivariant frames useful? Consider a scenario where an equivariant frame is easy to compute, and furthermore its cardinality, [F(X)). is not too large. Then averaging over the frame, denoted (-)
F
p1(9)
and defined by
(0)s (X)
Σ ((x(())
(2)
F(X)]
gxF(x)
Figure 1: Frame equivariance (sphere shape represents the group G; square represents V).
(0), (X) [F(X)
Σ (2))) geF(x)
provides the required function symmetrization. In Appendix A. Theorem (Frame Averaging). Let F be a G equivariant frame, and Φ V + R, c: V + W some functions. Then, ( is G invariant, while ( is G equivariant.
we prove:
Several comments are in order: First, the invariant case (equation is a particular case of the equivariant case (equation 3 under the choice of W R and the trivial representation (2(g) = 1. Second, in this paper we only consider X and frame choices FF for which F(X) are finite sets. Nevertheless, treating the infinite case is an important future research direction. Third, trivial choice of an equivariant frame is F(X)= G, that is, taking the frame to be the entire group for all X E V (for infinite but compact G the sum in the FA in this case can be replaced with Harr integral). This choice can be readily checked to be equivariant, and turns the FA equations averaging operators, equation]] | The problem with this choice, however, is that it often results in an intractable challenging computation, e.g., when the group is large or infinite. In contrast, show below, in some useful cases one can compute a manageable size frame and can use it to build invariant or equivariant operators in a principled way. Let provide simple example for Frame Averaging: consider V = R", W P, and G = R with addition as the group action. We choose the group actions in this case to be P1 (1(a)== x + a1, and p2(a)b = b+ a, where a, b R. æ R". and 1 e R is the vector of all ones. We can define the frame in this case using the averaging operator F(x) = x) c =G= = R. Note that in this case the frame contains only one element from the group, in other cases finding such small frame is hard or even impossible. One can check that this frame equivariant per Definition] | The FA of o: R" R would be ( (æ) = 6(x 1
3 into standard group
n (1 T xx) 1)
in the invariant case, and (0) (x) = 6(x (1 x 1) 11T x in the equivariant case.
Incorporating G second symmetry. An important use case of frame averaging is with the backbones 6, & already invariann/cqqiivarian w.r.t some symmetry group H and our goal is to make it invariant/equivariaat permutation invariant set or graph functions, i.e., Sn- We will provide sufficient conditions for the FA to provide this desired invariance/equivariance First, let assume /l is acting on V and W by the representations Ti H - GL(V) and 72 H + GL),,, respectively. Assume & is Hl invariant and H equivariant. We say that representations P1 and T commute if p1 (g) T (h)X= TI (h)p1 (g)xx for all g E G, he H, and X V. If p1 and commute then the map : H xG - GL(V) defined by yi (h. 9) = Ti (h) (())))))))))))))))) (g) a representation of the group H G. Second, we would need that the frame F(X) is invariant to H, that is F(r ()) = F(X). We show generalization of Theorem 1 Theorem (Frame Average second symmetry). Assume F is H H-invariant and G-equivariant. Then,
H x G. For example, say
add G F33) equivariance to
1. ch: V + R is Hl invariant and PI.TI commute then (6) is G x H invariant.
2. 1 V + W is H equivariant and Pt. Ts. i 1.2, commmute then (4) is Gx H equivariant.
'Note that since these are affine maps they are technically not representations but have equivalent representation using homogeneous coordinates. Therefore, FA is also valid with affine actions as used here.
3

---

Published as a conference paper at ICLR 2022
Above used left actions for the definition of equivariance. There are other flavors of equivariance, e.g., if one of the actions is right. For example, if g multiplies F(X) from the right, then equivariance will take the form:
Right actions.
x()(()))) - =(X)s gxeV
(4)
and accordingly
(o) (X)=
(0) (()()))), [F(X) gEF(X)
Σ
Σ (2(()))((1(0))1))) geF(X)
(5)
[F(X)
G invariant and equivariant, respectively.
Efficient calculation of invariant frame averaging. There could be instances of the FA framework (indeed we discuss such a case later) where [F(X) is still too large to evaluate equations 2 In the invariant case, there is a more efficient form of FA, that can potentially be applied. To show it, let us start by defining the subgroup of symmetries of X, i.e., its stabilizer. The stabilizer of an element X V is subgroup of G defined by Gx {g e G p1 (g) X X). Gx naturally induces an equivalence relation ~ on F(X), with g g~ = hg E Gx- The equivalence classes (orbits) are [g] (h e F(X)lg ~ h} Gxg F(X), for g F(X), and the quotient set is denoted F(X)/Gx. Theorem 3. Equivariant frame F(X) is a disjoint union of equal size orbits, [o] E F(X)/Gx.
The proof is in A.3 The first immediate consequence of Theorem is that the cardinality of F(X) is at-least that of the stabilizer (intuitively, the inner-symmetries) of X, namely [F(X) 2 |xx] Therefore, there could be cases, such as when describes a symmetric graph, where [F(X) could be too large to average over. A remedy comes from the following observation: for every h [g]. we have that h = rg. r e Gx. and (h) (h)- X)= (p) (r) (x) ((pi X), since also r-1 Gx. Therefore the summands in equations 2 are constant over orbits, and we get
Σ (p ( (X) my [x)=F(X)/xx
(6)
where m, = [F(X)/xx| [ This representation of invariant FA requires only m, = =((() evaluations, compared to [F(X) in the original FA in equation 2
Approximation of invariant frame averaging. Unfortunately, enumerating F(X)/Gx could be challenging in some cases. Nevertheless, equation still very useful: it turns out can easily draw a random element from F /xx with uniform probability. This is an immediate application of the equal orbit size in Theorem
Corollary 1. Let F(X) be an equivariant frame, and g E F(X) be uniform random sample. Then [g] E F(X)/Gx is also uniform.
Therefore, an efficient approximation strategy is averaging over uniform samples, g, F(X), [A].
(0) (x) 1 * k (())))))))))
This approximation is especially useful, compared to the full-blown FA, when my = |F(())// is small, i.e., when |Gx| is large, or X has many symmetries. Intuitively, the smaller my the better the approximation in equation 7 partial explanation to this phenomenon is given in Appendix [A.4] while an empirical validation is provided in Section 5.2
2.2 EXPRESSIVE POWER
Another benefit in frame averaging as presented in equations and is that preserves the expressive power of the base models, a. 4. as exaplined next. Consider some hypothesis function space H = { c C(V, W), where C(V, W) is the set of all continuous functions V + W. As mentioned above, the case of scalar functions ø is special case where W = R. and (2(g) 1. H can be seen as the collection of all functions represented by a certain class of neural networks, e.g., Multilayer Perceptron (MLP), DeepSets (Zaheer et al. (007)), or Message Passing Graph Neural Networks (Gilmer et al. 2017). We denote by (H) the collection of functions E H. after applying the frame averaging in equation
3 (?) { + H).
4

---

Published as a conference paper at ICLR 2022
We set some domain K V over which we would like test the approximation power of (H). To make sure that FA is well defined over K we will assume it is frame- finite, i.c., for every X K. F(X) is finite set. Next, we denote K5 = ( X K, FX)); intuitively, K5 c V contains all the points sampled by the FA operator. Lastly, to quantify approximation error over set A c V let us use the maximum norm | A.W maxxed | [*(X)ll We prove that an arbitrary equivariant function Vr e C(V, W) approximable by a function from H. over K is approximable by an equivariant function from (H) (Proof details are found on Appendix [A.5]. (..5).
Theorem 4 (Expressive power of FA). If IF is bounded G-equivariant frame, defined over frame-finite domain K, then for an arbitrary equivariant function W & C(V, W) we have
inf
(4)= S inf - GEH
2 ky,
DEH
Where e the constant from Definition !
This theorem can be used to prove universality results the backbone model universal, even for non-compact groups (c.g.. the Euclidean motion group). Below we will use it to prove universality of frame averaged architectures for graphs, and point clouds with Euclidean motion symmetry.
3 MODEL INSTANCES
We instantiate the FA framework by specifying: i) The symmetry group G, representations Pl, P2 and the underlying frame F; ii) The backbone architecture for (invariant) or & (equivariant).
3.1 POINT CLOUDS, EUCLIDEAN MOTIONS.
Symmetry. We would like to incorporate Euclidean symmetry to existing permutation invari- ant/equivaraint point cloud networks. The symmetry of interest is G E(d) O(d) x T(d), namely the group of Euclidean motions in Rd defined by rotations and reflections (dd, and translations Td)). We also discuss G SE(d) SO(d) x T()), where SO(d) is the group of rotations in IR4. We define V = Rnnd and the group representation is pi (g) X R² Itt,, where R ((d) or R e SO(d), and t E Rdd denotes the translation. W, P2 are defined similarly, unless translation invariance is desired in which case we use the representation (2(g) X = XR..
Frame. We define the frame F(X) in this case based Principle Component Analysis (PCA), follows. Let t 1 IRd be the centroid of X, and C (X - 1t")² -1"""" E Rdd the covariance matrix computed after removing the centroid from X. In the generic case the < >g-- Let 11 U2,..., U2 be the unit length corresponding
)
22
eigenvalues of C satisfy A >b2 eigenvectors. Then we define F(X) )- {[[a) vI,..., a.tta] ()) a; E 1)] E(d). The size of this frame (when it is defined) is 2d which for typical dimensions d = 2,3 amounts to frames of size 4, 8, respectively. For G = (dd), restrict F(X) ) orthogonal, positive orientation matrices; generically there are 2d-1 such elements, which amounts to 2, elements for d = 2,3. respectively. Proposition 1. F(X) hased on the covariance and centroid are E(d) equivariant and bounded.
This choice of frame is defined for every X V for which the covariance matrix C' has simple spectrum (i.e., non-repeating eigenvalues). It is known that within symmetric matrices, those with repeating eigenvalues are of co-dimension 2 (see e.g., |Breiding et al. (2018)). Therefore, (X) is defined for almost all X' except rare singular points. Where is defined, I continuous direct consequence of perturbation theory of eigenvalues and eigenvectors of normal matrices (see e.g.. Theorem 8.1.12 in Golub & Van Loan (1996)). However, when very close to repeating eigenvalues. small perturbation can lead to large frame change. In Appendix B we present an empirical study of frame stability and likelihood of encountering repeating eigenvalues in practice.
Since we would like to incorporate E(d) symmetries to an already S,, invariant/equivariant archi- tectures, per Theorem 2 we will also need to show that the P1 (and similarly P2) commute with T Sn GL(V) defined by ( = PX, where P Ph. h Sn, is the permutation representa- tion. That Pr. E Raxn is the permutation matrix representing h S., that is, P. = I if i h(j) and 0 otherwise. Indeed p( p1 (g) P(XR + +1t") = p1 p1(g) (h) Furthermore, note that F(r(h)X) F(X), therefore F is also S, invariant.
(R o" 1) acting on X'= [X,1] (=x(d+1)
Technically, this representation defined by matrices
5

---

Published as a conference paper at ICLR 2022
Backbone architectures. We incorporate the FA framework with two existing popular point cloud network layers: i) PointNet (Qi et al. 2017a); and ii) DGCNN (Wang et al. 2018). We denote both architectures by dd.d' : 1 - _n for the S, equivariant version of these models. To simplify the discussion, we omit particular choices of layers and feature dimensions, Appendix C.I provides the full details. We experimented with two design choices: First, consider frame averaged 23,3. i.c., (.,.s)y: yielding universal, E(3) equivariant versions for PointNet and DGCNN, dubbed FA- PointNet and FA-DGCNN. A more complex design choice, taking inspiration from deep architectures with multiple modules, is to compose blocks of FA networks. For example, to build a local E(3)
equivariant version of PointNet, denote also Ta.d" : Rd + Rd an MLP. We decompose the input point cloud to k-nn patches X; E RR i [n], where each patch is sorted by distance. Next, feed each patch into an equivariant FA Tak,3d, each with its own frame F,, resulting in E(3) equivariant features in 3d for every point, Y Rnx3dd then applying equivariant FA D34,3 providing output in I That is, (X)= (P34.) 5 (((T 5. (Xi). (Taa,ad) F. (x,,)). where brackets denote concat in the first dimension. We name this construction HA-Loccl--PimtNNC
Universality. We use Theorem to prove that using a universal set invarian/eeuiivriaat back- bone o, 4 such as DeepSets or PointNet (see e.g., Zaheer et al. (2017); Qi et al. (2017a); (Seool & Lipman (2119) leads to a universal model. Let H. be any such universal set-equivariant function collection. That is, for arbitrary continuous set function V we have (in the notation of Section 2.2
inf || V s,w 0 for arbitrary compact sets c V. If K c V is some bounded domain, then the choice of frame F described above implics that K5 is also bounded and therefore contained in some compact set f2 = V. Consequently, Proposition| I and Theorem 4 4imply Corollary [ A similar results holds for (d)),, which provides a similar expressiveness guarantee as the one from (Dym &
Maron 2020) analyzing Tensor Field Networks (Thomas et al.! 2018 Fuchs et al. 2020)
Corollary (FA- PeeaeeepSett/Pointeeet are universal). Frame Averaging PeepSets/PointNe using the frame F defined above results in universal E(d) Sn invariant/equivarraant model over bounded frame-finite sets K V.
3.2 GRAPHS, PERMUTATIONS
Symmetry and frame. Let G = Sn, and V = Rundd x RR'" where X = :X (Y, E V represents R"*" assume undirected graphs, meaning A = AT Let X V, the representation fr is defined by A Pr x (PY, PAP"). where P= Pg is the permutation matrix representing g Sn, We define F(X) to contain all g e Sn that sort the rows of the matrix S(X) in column lexicographic manner, i.e. PX( is lexicographically sorted; the matrix S is defined as follows. Let L diag( (A1) A be the graph's 's Laplacian. For every eigenspace (traversed in increasing eigenvalue order), spanned by the orthogonal basis .I...., Uz. we add the (equivariant) column diag( diag(E, u, u.u?) S (Fürer 2010). Hence, the number of columns of S equals to the number of unique eigenvalues of L.
a set of node features Y e Ruxd and an adjacency matrix (or some edge attributes)
Proposition 2. F(X) defined by sorting of S(X) is Sn-equivariant and bounded.
Backbone architectures. In this case we perform only invariant tasks, for which we chose two universal backbone architectures for d: (i) MLP applied to vec(Y, A) and (ii) GNN+ID (Murphy al. 2019 Loukas, 2020), denoting a GNN backbone equipped with node identifiers node features. We perform FA with @ according to the frame constructed in Proposition] 2 Note that Theorem 3 implics, [F(X) AAut(G), since the stabilizer Gx is the automorphism group of the graph. i.c., g E Gx = Aut(X X) iff pı (=) X. This means that for symmetric graphs equation
2 can prove too
costly. In this case, we use the approximate invariant FA, equation
Universality. Let us use Theorem to prove FA-MLP and FA-GNN+ID are universal. Again, is enough to consider the equivariant case. Let 7. = C(V, W) denote the collection of functions that can be represented by MLPs or GNN+ID. Universality results in (Pinkus) 1999 Loukas 2020 Puny et al.) 2020) imply that for any continuous graph (i.e., S. equivariant) function V. inf V + aww 0 for any compact Ω = V. Let K = V be some bounded domain, then since G is finite then Ky is also bounded and is contained is some compact set. Proposition 2 and Theorem now imply:
Corollary 3 (FA-MLP and FA-GNN+ID is graph universal). Frame Averaging MLP/GNN+ID using the frame F above results universal Sn equivariant graph model over bounded domains K c V.

---

Published as a conference paper at ICLR 2022
3.3 GRAPHS, EUCLIDEAN MOTIONS.
Symmetry and frame. We consider the group = E(d) acting on graphs, i.e., V Randd R where X = (Y, A) V represents set of node and edge attributes, as described above. The group representation is (1 - P1 (g) A) = (YR" it A). We define the frame F(X) F(Y) using the node features as the point cloud case, Section 3.1 Therefore Proposition implies F is equivariant and bounded. Next, also in this case we would like to incorporate E(d) symmetries to an already Sn invariant/equivarian graph neural network architectures; again per Theorem 2] we will also need to show that the P1 (and similarly (2) commutes with T S,, GL(V) defined by 7 (h)X (PY, PAP"), where P Ph. is the permutation matrix of h e Sa. Indeed T p (g) X = -P Rd + 1t"), PAP") = pi (1)) Furthermore, note that as in the point cloud case F(r(h)X) ( =(X), therefore F is also S, invariant.
Backbone architecture. The backbone architecture we chose for this instantiation is the Message Passing GNN in Gilmer et al. (2017). an Sn equivariant model denoted & R x Raxn
Randd' x IR Ta In this case we constructed model, as suggested above, by composing I equivariant 3d' 3) 3)z x o ...(( 3d' 3. F o ( 6,3w ) (X). The input feature size is 6 since we use velocities in addition to initial position as input (n-body problem). We name this model FA-GNN.
layers (X)=
(
4 PREVIOUS WORKS
Rotation invariant and equivariant point networks. State of the art S, invariant networks, c.g.,
(Qi et al. 2017a Atzmon et al. 2018: Li et al. 2018 Xu al.) 2018h Wang al., 2018 not
invariantequiivaiinn to rotationssreellections by construction (Chen et al. 2019). Invariance to global or local rotations can be achieved by modifying the 3D convolution operator or modifying the input representation. Relative angles and distances across points (Deng et al. 2018 Zhang et al. 2019 or angles and distances w.r.t. normals (Gojeic al. 2019) can be used for rotation invariance. Other works use some local or global frames to achieve invariance to rotations and translations, Xiaoo et al.) (2020); Yu et al. (020);; Deng et al. (2018) also use PCA to define rotation invariance, and can be seen as instances of the FA framework. We augment this line of work by introducing a more general framework that includes equivariance to rotation/reelectioon and translation, more general architectures and symmetries as well as theoretical analysis of the expressive power of such models.
Equivariance is a desirable property for 3D recognition, registration (Ao et al. 2021), and other domains such as complex physical systems (Kondor 2018). A popular line of work utilizes the
theory of spherical harmonics to achieve equivariance (Worrall et al. 2017 Esteves et al. 2018)
Liu et al. 2018; WWiler al., 20188] Cohen al., 2018). Notably, Tensor Field Networks (TFN),
S3(3) transformers, and
Attention (Thomas et al. 2018 Fuchs et al. 2020
Romero & Cordonnier 2021) achieve equivariance to both translation and rotation, i.e., S SF((),
and are maximally expressive (i.e., universal) as shown in Dym & Maron (2020). These methods, however, are specifically adapted to SE(() and require high order SO(3) representations as features. Recently Deng et al. (202T) propose rotation equivariant network by introducing tensor features, linear layers that act equivariantly on them and equivariant non-linearities etc. However, their architecture is not proved to be universal. Discrete convolutions (Cohen et al., 2019; Li et al. 20119] /errolllrr,Chhen& Worrall & Brostow 2018 have also been used for achieving equivariance. In particular, [Chen et al.) (2021) propose point networks that are SE(3) equivariant and use separable discrete convolutions. Lastly, (Finzi et al., 2020) construct equivariant layers using local group convolution, and extends beyond rotations to any Lie group.
Graph neural networks. Message passing (MP) GNNs (Gilmer et al. 2017) are designed to be S,, equivariant. Kondor et al. (2018) introduces a broader set of equivariant operators in MP-GNNs, while Maron et al. (2018) provides full characterization of linear permutation invarian//equivariant GNN layers. In a parallel approach, trying to avoid harming expressively due to restricted architectures (Xu ct al. 201 Sa. Morris et al.] 2019), other works suggested symmetrization of non invariant/equivariant backbones. Ranging from eliminating all symmetries by a canonical ordering (Niepert et al.) (016) to averaging over the entire symmetry group (Murphy et al.) 2019 2018), which amount to the trivial frame F = P(G). with the symmetry group G S,, As we have also shown, this approach comes at a cost of high variance approximations hindering the learning process. Our FA framework reduces the variance both by choosing canonical ordering and addressing the fact that it may not be unique.
Recently, a body of work studies GNNs with invariancee/qquivaiance to E(3) (or a similar group) to deal with symmetries in molecular data dynamical systems. . Many SF(() equivariant con-
7

---

Published as a conference paper at ICLR 2022
structions (Anderson al. 2019 Fuchs et al. 2020 Batzner al., 2021 Klicpera et al. 2021
extend TFN (Thomas et al. 2018) and inherit its expensive higher order feature representations in the intermediate layers. Finally, a recent work by /Satorass et al. (202I) provides efficient message passing construction which is F(d) equivariance but is not shown to he universal, thus far.
EXPERIMENTS
We evaluate our FA framework on a few invariant/equivaraint point cloud and graph learning tasks: point cloud normal estimation (O(3) equivariant and translation invariant); graph separation tasks (S,, invariant); and particles position estimation, i.e., the n-body problem (E(3) equivariant).
5.1 POINT CLOUDS: NORMAL ESTIMATION
Normal estimation is core geometry processing task, where the goal is to estimate normal data from an input point cloud, X & R This task is ((3) equivariant and translation invariant. To test the effect of rotated data on the different models we experimented with three different settings: I/I- training and testing on the original data; ii) (3) training on the original data and testing on randomly rotated data; and iii) SO 3 (SO(3) training and testing with randomly rotated data. We used the ABC dataset (Koch et al. 2019) that contains 3 collections ( (10k, 50k, and 100k models each) of Computer-Aided Design (CAD) models. We follow the protocol of the benchmark suggested in Koch et al. (2019) and quantitatively measure normal estimation quality via 1 - (n² n)² with n being the ground truth normal and ñ the normal prediction. We used the same random train/test splits from Koch et al. 2019). For baselines, chose the PointNet (Qi al. 7017a) and DGCNN (Wang jet al. 2018)) architecture, which are popular permutation equivariant 3D point cloud architectures. In addition, we also compare VN-PointNet and VN-DGCNN (Deng al. (021), a recent state of the art approach for 5O(3) equivariant network design. We also tested our FA models, FA-PointNet and FA-DGCNN model, FA-Loocal-PinttN
described in Section 3.1 In addition, we tested our local 0(3) equivariant See Appendix C. for the further implementation details. The results in Table T showease the advantages of our FA framework: Incorporating FA existing architectures is beneficial in scenarios (ii-iii), outperforming augmentation by a large margin. In contrast to VN models, FA models maintain (and in some cases even improve) the baseline estimation quality (i), attributed to the expressive power of the FA models.
Method
10k
50k
100k
//3
1)50(3)
50(3)/50(3)
1/r
1JS0(3)
50(3)/0(33
I/I
1/50(3)
80(3)/50(3)
PointNet
207=.001
.119:006
258
.188
130=,007
.232=.001
188s=.066
.119:0005
.231=0001
VN-PoimtNer
203-0003
216: 004
.234 0094
.185. 0012
1866-006
0106
1187-006
189
1188
.185. D03
FA-Poimteer
.51
.163..00 001
.161a.002
.01
.18:
.150=.002
.148..002
.147a.001
.149_.00
Fa-Looal-PoiniNe
097=.001
.984 001
008+.001
091+.001
.000=000
0011.001
0011.001
.000 002
001= 002
DGCNN
070
.193.
.121..001
.061
.174:.007
.122-
.058
.173
.112:
VN-DNCNN
.133.0003
.130s
.144..007
.127a.005 0005
.115
.127=0006
.127=0005
.125a.001
.127=.005
FA-DGUNN
.167=.001
.069:002
.071+.003
065+.00)
.067=.004
066--.004
.U73..008
.0674.001
.011-009
Table 1: Normal estimation, ABC dataset (Koch al.
2019 benchmark.
5.2 GRAPHIS: EXPRESSIVE POWER
Model
GRAPHSc EXP EXP-classify
Producing GNNs that are both expressive and computation- ally tractable is a long standing goal of the graph learning community. In this experiment invariant task): the ability of models to separate and clas- sify graphs, a basic trait for graph learning. We use two datasets: GRAPH8c (Balcilar et al. (021) that consists of all non-isomorphic, connected node graphs; and EXP (Abboud) et al. 2021) that consists of 3- distinguishable graphs that are not 2-WL distinguishable. There are two tasks: (i) count pairs of graphs not separated by randomly initialized model in GRAPH8c and EXP: and (ii) learn to classify EXP to two classes. We follow Balcilar al. (2021) experimental setup. As baselines we use Kip/ & Welling (2016), Velikkovovvii
GCN
4755
50%
test graph separation (S,,
GAT
1828
600
50%
GIN
386
50%
CHEBNET
44
71
82%
PPGN
100%
GNNML3
0
100% %
GA-MLP
50%
FA-MLP
0
100% %
GA-GIN+ID
0
50%
FA-GIN+ID
100% %
Table 2: Graph separation (aalcilar
et al. (2018), GIN Xu et al. (2018a). CHEBNET Tang al.
ct al. 2021 Abboud et al. 2021).
8

---

Published as a conference paper at ICLR 2022
(2019), PPGN Maron et al. 2019), and GNNML3 Baleilar al. (202I), all of which equivariant by construction. We compare to our FA-MLP, and FA- FA-GIN+ as described in Section 3.2 that provide tractable option for universal GNNs, We also compare to the trivial (i.e., entire group) frame averaging F G, denoted GA-MIP and GA-GIN+ID as advocated in (Murphy et al. 2019).
Appendix C.2 provides full implementation details.
The two first columns in Tshle the results of the separation task (i). As expected both IAA and GA provide perfect separation, however, are not perfectly invariant unless one computes the full averages on FF and G, respectively. Since for some graphs (with many symmetries) full
8
FA-MPP 90%
GA MLP GA-ME P 00%
Inveriance
m
averages are not feasible, we compare the invari- ance error (see appendix for the exact definition) of GA with that of the approximate FA, equa- tion]] 7 for 50 randomly permuted inputs. Figure 2 left shows the mean, std, and 90% percentile of invariance error for increasing sample size
100
200
mc
Number of samples
Figure 2:
Invariance error (left); - (right).
k. Note that approximate FA is more invariant
even with as little as k = samples, which explains why in the classification task (ii). in Table 2 right column, FA is able learn while GA fails, when both are trained with sample size k == Figure riighht compares m and mg (the maximal number of unique elements in the FA, equation 6 for GRAPH&c dataset. The color and size of the points in the plot represents how many graphs in the dataset have the corresponding (mG, m,) ) values. This demonstrates the benefit (in one example) of FA over GA in view of Theorem and approximation in equation 7 Of course, other, more powerful frames can be chosen, e.g., using higher order WL (Morris et al. 2019) or substructure counting
(Bouritsas et al. 2020) that will further improve the approximation of equation
5.3 GRAPHS: n- R--BODY PROBLEM
In this task we learn to solve the n-body problem (E(3) equiv- ariant). The dataset, created in (Satorras et al. 2021; Fuchs iet al., 2020), consists of a collection of n = 5 particles systems, where each particle is equipped with its initial position in R- and velocity in 1R.3, and each pair of particles (edge) with value indicating their charge difference. The task to predict the particles" locations after fixed time. We follow the protocol of (Satorras et al. 202T). As baselines we use EGNN (Satorras) let al. 1) GNN (Gilmer et al. 2017). TFN (Thomas et al.
Method
MSE
Forward time (s)
Lineur
0,0819
.0001
SE(3) Transformer
0.0244
.1346
TFN
0.0155
.0343
GNN
0.0107
.0032
Radial Field
0.0104
.0039
EGNN
0.0071
.0062
FA-GNN
0.0057
.0041
2018). SE(3) Transformer (Fuchs et al. 2020) and Radial Field
Table 3: n-body experiment (Sator
(Köhler et al. 2019). We test FA-GNN, as described in
ras et al. 2021).
Section 3.3 Table 1oogs the results, where the metric reported
the Mean Squared Error between predicted locations and ground truth. As can be seen, FA-GNN improves over the SOTA by more than 20% Note that the number of parameters used in FA-GNN and EGNN is roughly the same. More details are provided in Appendix
6 CONCLUSIONS
We present Frame Averaging, generic and principled methodology for adapting existing (back- bone) neural architectures to be invariant/equivariat to desired symmetries that appear in the data. We prove the method preserves the expressive power of the backbone model, and is efficient to compute in several cases of interest. We use FA to build universal GNNs, universal point cloud networks that are invariant/equivariant to Euclidean motions F(3), and GNNs invariant/equivariant to Euclidean motions E(3). We empirically validate the effectiveness of these models on several invariant/cqqiivaiian learning tasks. We believe the instantiations presented in the paper are only the first step in exploring the full potential of the FA framework, and there are many other symmetries and scenarios that can benefit from FA. For example, extending the invariance (or equivariance) of model from a subgroup H of G, G. Further Interesting open questions. not answered by this paper are: What would be a way to systematically find efficient/small frames? How the frame choice effects the learning process? How to explore useful FA architectures and modules?
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
OP, MA and HB were supported by the European Research Council (ERC Consolidator Grant, "LiftMatch" 771136) and also by research grant from the Carolito Stiftung (WAIC).
REFERENCES
Ralph Abboud, ismail īlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization, In Proceedings of the Thirtieth International Joint Conference Artifical Intelligence (IJCAI), 2021.
Brandon Anderson, Truong-Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. arXiv preprint arXiv: 190iv:990000000 2019,,
Sheng Ao, Qingyong Hu, Bo Yang, Andrew Markham, and Yulan Guo. Spinnet: Learning general surface descriptor for 3d point cloud registration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11753-1 117-1, 2021.
Matan Atzmon, Haggai Maron, and Yaron Lipman. Point convolutional neural networks by extension operators. arXiv preprint arXiv: 00188003.0001 2018.
Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzule Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprini arXiv: (806.0000001266 2018.
Simon Batzner, Tess E Smidt, Lixin Sun, Jonathan P Mailoa, Mordechai Kornbluth, Nicola Molinari, and Boris Kozinsky. Se (3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials. arXiv preprint arXiv:2101.03166 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09255. 2020.
Paul Breiding, Khazhgali Kozhasov, and Antonio Lerario. On the geometry of the set of symmetric matrices with repeated eigenvalues. Arnold Mathematical Journal, ((3):4234453 2018.
Chao Chen, Guanbin Li, Rujjia Xu, Tianshui Chen, Meng Wang, and Liang Lin. Clusternet: Deep hierarchical cluster network with rigorously rotation- invariant representation for point cloud analysis. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4994-5002, 2019.
Haiwei Chen, Shichen Liu, Weikai Chen, Hao Li, and Randall Hill. Equivariant point network for 3d point cloud analysis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14514-14522 2021.
Taco Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling, Gauge equivariant convolutional networks and the icosahedral cnn. In International Conference on Machine Learning, pp. 1321- 1330. PMLR, 2019.
Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical cnns. In International Conference on Learning Representations, 2018
Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications, volume 38 of Stochastic Modelling and Applied Probability. Springer Berlin Heidelberg, Berlin/Heidelberg. 2010. ISBN 9783642033100.
10

---

Published as a conference paper at ICLR 2022
Congyue Deng, Or Litany, Yueqi Duan, Adrien Poulenard, Andrea Tagliasacchi, and Leonidas Guibas. Vector neurons: A general framework for so (3)-qqiivariant networks. arXiv preprint 12X1: 2021.
Haowen Deng, Tolga Birdal, and Slobodan Ilie. Ppf-foldnet: Unsupervised learning of rotation invariant 3d local descriptors. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 602-618, 2018.
Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks. arXiv preprint urXiv:2010.02449, 2020.
Carlos Esteves, Christine Allen-Blanchete Ameesh Makadia, and Kostas Danilidis. Learning so (3) equivariant representations with spherical enns. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 52-68, 2018.
Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolutional neural networks for equivariance to lie groups on arbitrary continuous data, 2020.
Fabian B Fuchs, Daniel E Worrall, Volker Fischer, and Max Welling. Se (3)- tr-arssfffomrr:: 3d roto-translation equivariant attention networks. arXiv preprint arXiv:2006. 10500, 2020.
William Fulton and Joe Harris. Representation theory: a first course, volume 129. Springer Science & Business Media, 2013.
Martin Fürer. On the power of combinatorial and spectral invariants. Linear algebra and its applications, 432(9):2373 2380, 2010.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Zan Gojeie, Caifa Zhou, Jan D Wegner, and Andreas Wieser. The perfect match: 3d point cloud matching with smoothed densities. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5545-5554, 2019.
Gene H Golub and Charles F Van Loan. Matrix computations. edition, 1996.
Weihua Hu, Muhammed Shuaibi, Abhishek Das, Siddharth Goyal, Anuroop Sriram, Jure Leskovec, Devi Parikh, and C Lawrence Zitnick. Forcenet: A graph neural network for large-scale quantum calculations. arXiv preprint arXiv:2103.01446 2021.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint 1rXiv:109..00 (609002900, 2016.
Johannes Klicpera, Florian Becker, and Stephan Günnemann. Gemnet: Universal directional graph
neural networks for molecules. arXiv preprint arXiv:2106.0890 2021.
Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Mare Alexa, Denis Zorin, and Daniele Panozzo. Abe: A big cad model dataset for geometric deep learning. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2019.
Risi Kondor. N-body networks: covariant hierarchical neural network architecture for learning atomic potentials. arXiv preprint TrX3vv/803..0 2018.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. arXiv preprint arXiv:1801.02144, 2018.
Jonas Köhler, Leon Klein, and Frank Noé. Equivariant flows: sampling configurations for multi-body systems with symmetric energies, 2019.

---

Published as a conference paper at ICLR 2022
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-23 23224, 1998.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Jiaxin Li, Yingeai Bi, and Gim Hee Lee. Discrete rotation equivariance for point cloud recognition. In 2019 International Conference on Robotics and Automation (ICRA). pp. 2019.
IEEE,
Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. Pointenn: Convolution x-transformed points. Advances in neural information processing systems, 31:820-830, 2018.
Min Liu, Fupin Yao, Chiho Choi, Ayan Sinha, and Karthik Ramani. Deep learning 3d shapes using alt-az anisotropic 2-sphere convolution. In International Conference on Learning Representations, 2018.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3431-3440, 2015.
Andreas Loukas.
What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020. URL httpt:tt////o.. /ttp::://peeeeveew..tt nttpssneee/ooooe fformm? Ad-B112bp4YwS
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint 11Xiv:1812.09902,200 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint
2019.
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, volume 33, pp. 4602-4609, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663 4673. PMLR, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pool- ing: Learning deep permutation-invarian functions for variable-size inputs. arXiv preprint arXiv:1811.01900 2018
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2014-2023, New York, New York, USA, 20-22 Jun 2016. PMLR. URL https //proceedings.coo mlr pww.s http:///////e........ html
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta numerica, 8:143-195, 1999.
Yury Polyanskiy and Yihong Wu. Lecture notes on information theory. Lecture Notes for ECE563 (UIUC) and, 6(2012-2016)7,, 2014.
Omri Puny, Heli Ben Ben-Hamu, and Yaron Lipman. Global attention improves graph networks general- ization, 2020.
12

---

Published as a conference paper at ICLR 2022
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652-660, 2017a.
Charles R Qi, Li Yi, Hao Su, and Leonidas Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. arXiv preprint (rXiv:/706.024111 2017b.
David W Romero and Jean-Baptiste Cordonnier. Group equivariant stand-alone self-attention for vision. In ICLR, 2021.
Akiyoshi Sannai, Makoto Kawano, and Wataru Kumagai. Equivariant and invariant reynolds networks, 2021.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. (n) equivariant graph neural networks. arXiv preprint arXiv:2102.09844 2021.
Nimrod Segol and Yaron Lipman. arXiv:1910.02221, 2019.
On universal equivariant set networks. arXiv preprint
Muhammed Shuaibi, Adeesh Kolluru, Abhishek Das, Aditya Grover, Anuroop Sriram, Zachary Ulissi, and C Lawrence Zitnick. Rotation invariant graph neural networks using spin convolutions. arXiv preprint
2021.
Shanshan Tang, Bo Li, and Haijun Yu. Chebnet: Efficient and stable constructions of deep neural networks with rectified power units using chebyshev approximations, 2019.
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang. Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and translation-equivariant neural networks for 3d point clouds. 2018.
arXiv preprint
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018
Yue Wang, Yonghin Sun, Ziwei Liu, Sanjay Sarma, Michael M Bronstein, and Justin Solomon. Dynamic graph enn for learning point c201)s. arXiv preprint arXiv:1801.0788 2018.
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen. 3d steerable cnns: Learning rotationally equivariant features in volumetric data. arXiv preprint arXiv: arrXiv//807, 1000.000700555 2018.
Daniel Worrall and Gabriel Brostow. Cubenet: Equivariance to 3d rotation and translation. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 567-584, 2018.
Daniel E Worrall, Stephan J Garbin, Daniyar Turmukhambetov, and Gabriel J Brostow. Harmonic networks: Deep translation and rotation equivariance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5028-5037, 2017.
Zelin Xiao, Hongxin Lin, Renjie Li, Lishuai Geng, Hongyang Chao, and Shengyong Ding, Endowing deep 3d models with rotation invariance based on principal component analysis. In 2020 IEEE International Conference on Multimedia and Expo (ICME), pp. 1-6. IEEE, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 2018a.
Yifan Xu, Tianqi Fan, Mingye Xu, Long Zeng, and Yu Qiao. Spiderenn: Deep learning on point sets with parameterized convolutional filters. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 87-102, 2018b.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Appreximation, pp. 1-68, 2021.
Ruixuan Yu, Xin Wei, Federico Tombari, and Jian Sun. Deep positional and relational feature learning for cotation-invariian point cloud analysis. European Conference on Computer Vision pp. 217-233. Springer, 2020.
13

---

Published as a conference paper at ICLR 2022
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. arXiv preprint arXiv:1703.06114, 2017.
Zhiyuan Zhang, Binh-Son Hua, David W Rosen, and Sai-Kit Yeung, Rotation invariant convolutions for 3d point clouds deep learning. In 2019 International Conference on 3D Vision (3DV), pp. 204-213. IEEE, 2019.
14

---

Published as a conference paper at ICLR 2022
A PROOFS
A.1 PROOF OF THEOREM 1
Proof. First note that frame equivariance is defined to be F(P((g)X) gF(X) which in particular means (F(p X) [F(X)].
For invariance, let g' G
(0) (pi()())) [F() (FXF(()
E ) [F(X) geF(x)
E (o(((s))
Σ ((1(())1xx) (0) (x)
[F(X)
geF(X)
and for equivariance
(0) (pi())
1
Σ (
= [F(X) (x)
1
E 3ido)ppp1000000000
[F(X) gEF(X)
=22(d') [F(X]
Σ xx))))
gEF(X)
= p2((') (4)) (X)
A.2 PROOF OF THEOREM 2
Proof. The proof above A. of Theorem I is special case of the following where the second symmetry is chosen to be trivial. In principle the proofs are quite similar.
First note that frame equivariance and invariance, together with P1, Ti commuting mean
Font::/)0--T/(000000000000-00000 = =
which in particular implies that
(h', E H x G be arbitrary. Then, geg'F(X)
1
(m
Σ (H))))
[F(X]
Σ
[F(X)
(EF(X)
1
Σ (1)x))
[F(X)
(<F(X)
Σ ((p(())
[F(X) (EF(X)
= =(0) (X)
15

---

Published as a conference paper at ICLR 2022
meaning that ( is H x G invariant. Next,
1
(0) (n (h', (')))))))))-)))
E (1009101000000000000000000
[F(X) geg'F(X)
E P000
[F(X)
geF(X)
Σ (2l
[F(X) (EF(X)
1
Pre
E ((0))((((00)11
[F(X) gEF(X)
- =2( (.), (X)
showing that ($) is H x G equivariant.
A.3 PROOF OF THEOREM
3 AND COROLLARY
Proof. (Theorem 3 First we show Gx acts on F(X). For an arbitrary Gx and equivariant where in the first equality we used the fact that E Gxx and in the second the equivariance of F. This means that g F(X) and Gx then also hg F(X), or in other words F(X) is closed to actions from Gx. Furthermore, since group acts on itself via bijections we have that the cardinality all orbits is the same, [[ ggl = |x for all [9] F(X)/Gx. Lastly, the equivalence relation g h < hg Gx shows that F(X) is union of disjoint orbits of equal cardinality.
frame F, we have (x) = F (pi = hF()),
Proof. (Corollary Theorem asserts that all orbits [9] F(X)/Gx have the same number of elements. Therefore, a random choice & F F(X) will have equal probability to land in each orbit. O
A.4 THE ROLE OF MF IN APPROXIMATION QUALITY OF EQUATION 7
To better understand the role of m approximating equation we first note that equation 7 can be written as (Ø) (X)
(pr (9:) -x), where ji is the empiricial distribution
over F F(X)/Gx, assigning to each element [g] F(X)/Gx the fraction of samples landed in [g].
i.e. M[ = (i e [k:]l [g]) |k- We next present a lower bound on the probability of any particular ji that provides good approximation {
( (X).
Theorem 5. Let F be an equivariant frame. The probability of an arbitrary i e
{ū (uppeel()))0 (X)
(o) se) e is bounded from below as follows,
P()) 2 (1 k)- (op(-2m,ke")
where Q= ( (K(x)) 1, V) the set of bounded, continuous functions V R.
Before providing the proof let us note that this theorem provides a lower bound for each particular "good" empirical distribution j.. The main takeoff is that for fixed l and e, the smaller my the better the lower bound. The counter-intuitive behaviour of this bound w.r.t. is and c stems from the fact that the size of the set of "good" û, namely &Ø C(V, RR) [Ø(X) 1, V V) is increasing with & and e.
Proof. For brevity we denote m my Our setting can be formulated follows. We have the uniform probability distribution, denoted μ. over the discrete space [m] (representing the quotient set F(X)/xx:: Py j [m]] and we have numbers a, = d(p: (h,) (h2)) -Xx), where [hy] E F(X)/Gx j E [m] represent exactly one sample per orbit. In this notation (Ø) (X) Ex-1 % while the approximation in equation takes the form ( (X) Σ uyjū where Ūy = ky/k, where ky is the number of samples [h;j. i [k], i.e., samples that landed in the j-th orbit. Therefore,
As )
1 m
supl (X) (Φ)) (X)1 sup Σ ag de@
Σ
i 211uu i ilTV
|a,/31
16

---

Published as a conference paper at ICLR 2022
where the latter is the total variation norm for discrete measures (Levin & Peres 2017). We denote (Alp) Σj-1 log(Az) log Pg the Kl.-divergence. The Pinsker inequality and its inverse for discrete positive measures are (see e.g., (Polyanskiy & Wu 2014))
i - uPTv s H(App) & ll - ulTTv
(8)
where a minje[m] = m Therefore,
2m
T. T-= P [pl supl( (x) [d)) (X) s = l pl s fAl H(Alp) s o
2
Now, application of Large Deviation Theory (Lemmaa 2.1.9 in Dembo & Zeitouni 2010)) provides that for á so that H (Alp)) s =m:
P()) (1 k)m
Am
A.5 PROOF OF THEOREM
Proof. Let C(V, W) an arbitrary equivariant function, bounded equivariant frame over frame-finite domain K. Let 0 be the constant from Definition For arbitrary X K,
(X) x (X ll 11( (X) (8) (X)Il
pe(o)))(())) -
[F(X gef(X)
max (I
lop TV $ K
(=F(X)
$ c Kr.W
where in the first equality we used the fact that (v) V since v is already equivariant.
A.6 PROOF OF PROPOSITION I
Proof. Let us prove F is equivariant (equation (0,8) e F(X), then
Consider a transformation g= (R, () E G, and let
C OAO s= -11,
where ooO is the eigen decomposition of C. Note that the group product of these transformations
(R, (R.t)(O,s) (RO, Rs t).
We need to show (RO, Rs +)+ e F ()) Indeed, RO 0(3) and consists of eigenvectors of C (I- also RO SO(d). Furthermore
can be verified with direct computation. If O, R SO(d) then
%
1 1 (XR² 1t²)² 1 1 -RXX" +11²) Rs +t
n
as required. We have shown (R, (X) c F (R,
t) for all X and (R, t). To show the other (R,t)-'F(Y) that also holds for all Y
inclusion let X -Ry and get F (R,t) YY) and (R, t). In particular (R, ())(F(())) F( x). The frame F is bounded since for compact K c I nxd the translations n T are compact and therefore uniformly bounded for K, and orthogonal matrices always satisfy R R|
17

---

Published as a conference paper at ICLR 2022
A.7
PROOF OF PROPOSITION 2
Proof. First note that by definition S(X) is equivariant in rows, namely
Therefore if g F Sn, then by definition of the frame pi (g)S is sorted. Therefore, P1 (g)S=
= 01 (1gg)) (pz(h))))))))))))))))))))))))()) (h)- is sorted and we get that gh & ((pr(h) X). We proved F F(X) h = F(1 (h) X) for all h E G and all X E V. Taking X = Pi for an arbitrary F(Y), for all ge G and Y E V. We
p1 (h)-
Y V. and h= g for arbitrary g G, get F(p (g
proved F(X)h F(pi(M) (4) X). which amounts to right action equivariance, see equation 4 The
frame is bounded since P1 (G) is finite set.
B EMPIRICAL FRAME ANALYSIS
Repeating eigenvalues. We empirically the likeli- ness of repeating cigenvalues in the covariance matrix used from the definition of frame in Section [..] We use the data from the n-body dataset (Satorras et al.) 2021). Let X Rax3 represent the set of particles lo- cations (each set centered around 0 and scaled have max,,eX ||2,||2- 1) and Å1 S A2 S X3 be the eigenval- ues, Sorted in increasing order, of the covariance matrix -x-"" (X-1t") In order to measure the the
10
proximity of eigenvalues across the dataset notion of eigenvalues spacing 8; Ai11-d 1,2, where
Smin
3 = h--d is the mean spacing. Furthermore we define 8min min {81, as the minimal normalized spacing, ratio that indicates how close the spectrum is to having repeating eigenvalues. Figure 3 presents a histogram of the minimal spacing over the training set of the n-body dataset (consists of 3000 particles sets). The minimal spacing encountered in this experiment is of order 10-2. This empirically justifies the usage of finite frames for Edd) equivariance.
Figure 3: Minimal spacing histogram over the training set of n-body dataset (Satorras et al. 202T)
2
Frame stability. Here test stability of our O(d) frame defined in Section 3.T By stability we mean the magnitude of change of frame w.r.t. the change in the input X. desired attribute of the constructed frame is be stable, that is, to exhibit small changes if the input is perturbed. We quantify this stability by comparing the dis- tance between our frames frames constructed by a noisy input. As in the previous experiment used the data from the n-body dataset (Satorras et al. 2022). Let X e IR nx3 repre- sent the set of particles locations (each set centered around and scaled to have max,,e x ||a: 12 1) and X, X where 2i.j _N00, σ)) is the noisy input sample. We com- pute F(X) and F(X, xx) and choose representatives from each g (R,t) F(X), 9o (2,,t)) F(X.). We measure the distance between the frames as a function of the representatives.
5%
Figure Distance between original and noisy frames as function of a (we plot average and std). The result reported over the training set of n--ody dataset Satorras et al. 2021).
E(R, (RRRR,) = (R)),,, 3 i-1
Notice that in the case of simple spectrum the distance is invariant to the selection of representatives. In Figure we plot distance of original and noisy frames (and its standard deviation) as function of noise level a. The plot validates the continuity of frames in the simple spectrum case.
18

---

Published as a conference paper at ICLR 2022
3
k x
d 3
3
(T F1
71
71
71
nearest neighbors
(P3,) F.
(T 3d) Fi.
Input
k-nn patchs
Equivariant features
Output
Figure 5:
architecture.
C IMPLEMENTATION DETAILS
C.1
POINT CLOUDS: NORMAL ESTIMATION
Here provide implementation details for the experiment in section 5.1
PointNet architecture. Our backbone PointNet based on the object part segmentation network from Qi al. (2017a). The network consists of layers of the form
FC(n, dma dow) X [ 1b")
MaxPool(n, dm) X 1 1[max Xe,]
where X E nxdd, W R.la,den b Re are the learnable parameters, 1 E RR is the vector of all ones, [-] is the concatenation operator, e; is the standard basis in IR and v is the ReLU activation. In this experiement, for the PointNet baseline and for 33,3 (the backhone in FA-PointNet), used the following architecture:
FC(512,3,64) 4 FC(512, 128) La FC(512, 128, 128) 4 FC(512, 128, 512) L
FC(512,512, 2048) f Max2 2048) Eg [L,, L2, L2, L4, Ls, Lo] 4
(0(512,4025 256) ! FC(512, 256, 128) !g FCC512,, 128,3).
Note that the original PointNet network also contains two T-Net networks, applied to the input and L3 (the output of the third layer). Similarly, our baseline implementation made a use of the same T-Net networks. Note that the T-Net networks were not part of our FA-PointNet backbone architectures 33.33
The FA-Local-PP Pointeet architecture can be seen as a composition of two parts (see Figure 5}. The first part outputs equivariant features by applying the same MLP backbone T3k.3 with FA on each point's k-nn patch. Then, from each point's equivariant features, the second part of the network outputs an equivariant normal estimation. Note that the second part, ( an FA-Pointnet network applied to point cloud of dimensions R For AA-Local-PPintNVe we made the following design choices. Each point patch is constructed as its & nearest neighbors, with A = 20, X; e 2003 Then, the backbone 13420,3+12 is applied to all patches, with the following PointNet layers:
FC(512,3 20,3 21) FC(512, 21,3 * 42) FC(512,3 42, 3+ 42).
The second backbone, 22.42.3, is built from the following PointNet layers:
FC(512, 128, 256) 4 FC(512, 256,256) 4 FC(512, 256 512) 4 FC(512,512, La MaxPool(512,, 2048) fg [[,, Lz, Lg. La. Ls. Lo] 4 Ly FC(512, 256, 128) L FC(512, 128,3).
FC(512,3 32, 128)
FC(512,5248, 256)
19

---

Published as a conference paper at ICLR 2022
DGCNN architecture. mentation network from Wang et al. (2018). consists of EdgeConv(n, d dow). ( dms dou), and MaxPool layers.
Our backbone DGCNN architecture, 33,3, is based on the object part seg-
(51geConv5512,3, 64) 4 EdgeConv(512, 64, 64) 3 EdgeConv(512, 64) "x
FC(512, 64, 1024) + MaxPool(512, 1024) 5 [L1 L2, La, Lr, Ls] fg
FC((12, 1216, 256) 5 FC(512, 256, 128) 4 (5121 128,3)
Note that the DGCNN architecture incorporates T-Net network applied to the input.
Training details. We trained our networks using the ADAM (Kingma & Ba 2014) optimizer, setting the batch size to 32 and 16 for PointNet and DGCNN respectively. We set fixed learning rate of 0.001. All models were trained for 250 epochs. Training was done on a single Nvidia V-100 GPU, using PYTORCH deep learning framework (Paszke et al. 2019).
C.2 GRAPHS: EXPRESSIVE POWER
We provide implementation details for the experiments in 5.2 backbones, MLP and GIN equipped with identifiers. The details of those architectures presented here
We used two different universal
FA/GA GIN+ID architecture. The GIN+ID backbone is based on the GIN (Xu et al., 20 8a) network with an addition of identifiers as node features in order to increase expressiveness. For the experiments we used a three-layer GIN with feature dimension of size 64 and a RcLU activation function. For the added identifiers we defined the imput node features as X [X In], where the number of nodes in the graph, and to handle graphs of different sizes (EXP dataset) we padded node features with zeros to fit the size of the maximal graph. Note that we did not apply the permutation generated by the frame on the identifiers.
FA/GA MLP architecture. We used two different MLP networks for the EXP dataset and the GRAPH8c, due to the different size of graphs in the datasets. In the EXP dataset the maximal graph size is 64 and every node in the graph has one dimensional binary feature, therefore the input for the MIP network a flatten representation of the graph (with additional padding according to the graph size) e [ +64 Our architecture consists of layers of the form
FC(din dout) æ v (Was x b)
where W Ruu b R. are the learnable parameters. The final output of the network is denoted by (dout) where dout is the output dimension.
The MLP network structure for the EXP EXP-classify task:
FC(4160, 2048) 5 FC(2048, 4096) 33 FC(4096, 2048) 5
FC(2048, 10) 4 FC(10, 1) Lo (1)
with ReLU the activation function. For the EXP task, which has 10-dimensional output for each graph we omitted the last layer. The GRAPH8c is composed of all the non-isomorphic connected graphs of size hence we did not used any padding of the input here. The nodes have features and we just used flatten version of the adjacency matrix. The architecture for the GRAPH8c task:
FC(64, 128) 5 FC(128, 64) $3 FC(64, 10) Lg (10)
Training details. We followed the protocol from (alliilar et al. 2021) and trained our model with batch size 100 for 200 epochs. The learning rate set to 0.001 and did not change during training. For optimization we used the ADAM optimizer. Training was done on a single Nvidia RTX-8000 GPU, using PYTORCH deep learning framework.
20

---

Published as a conference paper at ICLR 2022
Invariance Evaluation. We quantify the permutation invariance of model by comparing output
of randomly permuted graphs PI [g))),, 9s & Sn, i [50]. The evaluation metric used is the invariance enror, defined by
1
m Σ
(pi(())))) v
where == 1 E (p)
The permutation invariance error of the models (FA/GA) measured a function of the sample size We iterated over the entire GRAPH&c dataset and for every graph computed the invariance enror for the FA-MLP GA-MMLP and regular MLP models (all with the exact same backbone network). The results presented in Figure (left) are normalized by the error of the regular MLP model. The backbone MLP we used for this experiment of the form:
FC(64, 128) 5 FC(128, 128) 4 FC(128, 128) S FC(128,,1)) 4 (10)
C.3 GRAPHS: N-BODY PROBLEM
This section describes the implementation details for the n-body experiment from Section 5.3
FA-GNN architecture. We use the GNN architecture of Gilmer et al. 2017) our base GNN layer, where for each node i [ni] the update rule follows,
mij &e (h!, n4,, k(s)
m, Σ mij
jCN(s)
1-1 on (h., m.) h
where N(1) the indices of neighbors of vertex i, h is the embedding of node at layer and ag e {-1,1) IR' are edge attributes representing attraction or repelling between pairs of particles and their distance. hd R represents the nodes input features, which this experiment are concatenation of the nodes initial 3D position (rotation and translation equivariant) and velocities (rotation-equivarian and translation-invarinn)) We used node feature dimension of size 60 to maintain fair comparison with the baselines (Satorras et al. [202T. The functions oe and Φ), implemented as a two-layer MLP with the SiLU activation function (also chosen for consistency purposes) with an hidden dimension of 121 and 120 respectively. To maintain fair comparison with (Satorras et al. 2021) our network is composed of 4 GNN layers. 6,34" has an additional linear embedding of the features as a prefix the GNN layers while (f44) is equipped with two-layer MLP (SiLU activation) as a decoder to extract final positions.
Training details. We followed the protocol from (Satorras et al. 202I) and trained our model with batch size 100 for 10000 epochs. The learning rate was set to 0.001 and did not changed during training. For optimization we used the ADAM optimizer. Training was done single Nvidia RTX-6000 GPU, using PYTORCH deep learning framework.
21


Reviews:
[{"review_id": "lj7g6DnolUS", "reviewer": "Reviewer_CToH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n-\tThe paper proposes a very practical strategy of building equivariant nets\n-\tThe universality proof helps convince the reader to use this method\n-\tThe paper considers and experiments on three different instantiations of their method, showing wide applicability.\n-\tThe experimental results show the method performs competitively.\n\nWeaknesses:\n-\tI don’t understand what’s happening in theorem 4. It considers a subsample $\\hat\\mu$ of F(X) to be ‘good’ when the symmetrizer that uses the subsample is epsilon-close to the full F(X) symmetrizer. Then it says that the probability of *one particular* good subsample is bounded below.\nHowever, that bound seems vacuus, as plugging any reasonable number brings the bound quickly close to 0. Also, it’s counter-intuitive why the bound should become looser as epsilon grows or as k grows.\nWhat one would want instead is giving a lower bound of the probability that we get *any* $\\hat\\mu$ that is epsilon-close to the full F(X) symmetrizer. And we want this bound to get higher when epsilon or k increases.\nThe line below theorem 4 draws a conclusion that would follow from a theorem as I propose it above, not from the theorem in the paper.\nAs it is currently stated – and I’m not completely misunderstanding – theorem 4 can best be removed from the paper. \n-\tIt is a bit unclear when the results apply to finite and infinite groups and frames F(X). Everywhere, a summation symbol is used, but in some places, F(X) is infinite. In the infinite cases, which measure should then be used? Can one always use some canonical Haar-like measure? In particular, in the proofs of theorem 1 and theorem 4 this should be discussed.\n-\tThe writing of the paper can be improved. I don’t follow the choice of F(X) for the E(d) case. Which are the 2^d O(d) matrices? Perhaps the authors can elaborate in more detail one of the examples how to construct F(X) in the main paper, and then do the other two in the appendix. \n-\tI would like some more theoretical discussion about the choice of F(X). Does the choice of F(X) affect the output? If so, how? Is F(X) required to be continuous / does a continuous (non-trivial) F(X) always exist? What does the topology on 2^G look like? How does this affect the continuity of the symmetrized function? If it is discontinuous, does that affect the universality? When can F(X) be chosen to be finite?\n \nOther comments:\n-\tWhy does GA-MLP and GA-GIN+ID only get 50% score on EXP-classify? Are you there using a finite subsample of G or F(X)? And could you give any insight into why we’d expect then complete failure for a G subsample and complete success for a F(X) subsample?\n-\tIn the proof of theorem 5, which norm is used for ||rho_2(g)|| ? It can’t be the max K-norm because K is a subset of the input of phi, not the output. Is it the operator norm?\n-\tI would like theorem 1 to be put in the main paper, as it shows why the key construction is correct.\n-\tI think a citation would be appropriate to Finzi et al 2020, “Generalizing Convolutional Neural Networks for Equivariance to Lie Groups on Arbitrary Continuous Data”, as they also consider sampling from the group to build equivariant networks.\n-\tWhy have the authors chosen the name “frame” for F(X)? I know frame as a set of vectors or in the context of a frame bundle.\n", "summary_of_the_paper": "The paper proposes to make any neural network equivariant by symmetrizing over a subset of the group, rather than over whole group. If the subset selection F(X), depending on input X, is equivariant (gFX=FgX), then the symmetrization is equivariant.\nThe authors furthermore prove:\n1)\tWhen interested in invariant prediction, the subset can be chosen in the quotient G/G_X, where G_X is the stabilizer subgroup of X.\n2)\tWhen symmetrizing with a random subsample of F(X), the probability of a particular subsample that deviates from symmetrizing with all of F(X) by less than some epsilon, is bounded below.\n3)\tWhen using the symmetrization of a universal model, the resulting model class is universal in the class of equivariant functions.\n", "summary_of_the_review": "I think this is a great paper, as it proposes a new practical method for building equivariant networks which is broadly applicable, universal and performs well in practice. I have serious concerns about theorem 4. If the authors convince me why it makes sense, or if they remove it, I will increase my score.\n\nI've updated my score after the response and revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fdClrbLgAga", "reviewer": "Reviewer_5HAS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "*Strengths*\n- The idea of replacing the averaging operator over the entire group by the FA is innovative. FA is simpler to compute and has less complexity in comparison with the averaging operator over the entire group.\n\n- The authors prove that the FA-based models preserve the universality property of their backbone architectures. \n\n- The FA framework is then applied to design several invariant and equivariant architectures for point clouds and graphs.\n\n*Weaknesses*\n\n- My concern is mostly about the incompleteness of the framework. It may happen the case that for some $\\mathbf{X}$, $\\mathcal{F}(\\mathbf{X})$ is a small set, but for some other $\\mathbf{X}$, $\\mathcal{F}(\\mathbf{X})$ is large or even infinity. (For example the frame choice in Subsection 3.1 is in this case). In this case, a deeper analysis on how to separate these two cases and how to deal when $\\mathcal{F}(\\mathbf{X})$ is large or even infinity is necessary.\n\n- It is also not clear how the FA is adapted in the DA-Local-PointNet. A detailed explanation here would be helpful.\n\n- No comparison with the previous equivariant architectures are presented. Therefore, it is hard to estimate how novel and efficient the framework is in the world of current group equivariant architectures.\n\n- Some technical parts are quite compact and not easy to read. Maybe the reason is that the paper includes rich contents and the authors tried to fix all of them in 9 pages.", "summary_of_the_paper": "The authors introduce Frame Averaging (FA), a general framework for adapting known architectures to become invariant or equivariant with respect to a general group by using group averaging operator. The idea of FA is to replace the averaging operator over the entire group by the averaging over a smaller set of group elements but still achieve the full invariant/equivariant property.", "summary_of_the_review": "In addition, I have some comments on the technical parts of the paper:\n\n- The definition of the frame $\\mathcal{F}(\\mathbf{X})$ for the case of point clouds and $G=E(d)$ in page 5 is not clear. Why \"$\\mathcal{F}(\\mathbf{X})$ [...] is the collection of E(3) Euclidean transformations defined by [...]\", while in this case, I think, $\\mathcal{F}(\\mathbf{X})$ must be a subset of $E(d)$?\n\n- I am curious to know why \"generically the frame would consist of $2^d$ elements [...], while for rare inputs $\\mathbf{X}$ the frame can be an infinite set\"? I think this remark is crucial for the proposed method as it affects the size of the FA framework.\n\n- I think the proof of Proposition 1 (Appendix A.6) has some flaws:\n\n     -- Line 3: What is $\\Lambda$? It is not defined yet.\n\n     -- Line 6-7: It seems to me that, you need to prove that $\\mathbf{RO}$ consists of eigenvectors of \n$$[(\\mathbf{R},\\mathbf{t})\\mathbf{X}]^T \\cdot (I-\\frac{1}{n} \\mathbf{1} \\mathbf{1}^T) \\cdot [(\\mathbf{R},\\mathbf{t})\\mathbf{X}]$$\nwhich is \n$$(\\mathbf{R}+\\mathbf{t} \\mathbf{1}^T) \\mathbf{X}^T \\cdot (I-\\frac{1}{n} \\mathbf{1} \\mathbf{1}^T) \\cdot \\mathbf{X} (\\mathbf{R}+\\mathbf{t} \\mathbf{1}^T)^T$$\nrather than \n$$C = \\mathbf{R} \\mathbf{X}^T \\cdot (I-\\frac{1}{n} \\mathbf{1} \\mathbf{1}^T) \\cdot \\mathbf{X} \\mathbf{R}^T$$\nas you claimed. If this is exactly the case, I do not know how it can be true.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GeQT-4h5O9", "reviewer": "Reviewer_BhKC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths \nThis paper proposes a general method for transforming existing models into invariant/equivariant models using Reynolds operators.\nCombined with other methods, it provides state-of-the-art experimental results.\n\nWeaknesses & Questions\nFirst of all, I would like to point out that the idea of using Reynolds operators to transform a model into an invariant model is found in Kicki et al. 2021, where the construction is exactly the same except for the use of frames.\nThe authors should be cited for this paper.\nAlso, the name \"frame\" is confusing with the concept of frame in differential geometry and should be given a different name.\n\nTheorem 1: It is proved that if a frame is an equivariant function, then a partial sum over the frame gives a transformation to an invariant/equivariant function, but the fact that the frame is defined depending only on the input space is not appropriate.\nFor example, if we have an invariant model F, the proposed method will sum over frames to convert it to an invariant function, which will increase the computational complexity. The transformation should be done without any transformation for the invariant model F.\nThis leads to the problem of overlapping invariants when combined with other models in the experimental section.\n\nAlso, since calculating the specific frame itself involves mathematical difficulties, I believe that the evaluation should be done on the model for which the frame has been calculated, i.e., for which the experiment has been conducted.\n\nPoint cloud models:\nThe $S_n \\times E(d)$ or $SE(d)$-invariant model is constructed by computing a frame for $E(d)$ or $SE(d)$ and transforming the model of the Deep sets with that frame.\nThe simple question is why don't you construct a frame for $S_n \\times E(d)$ or $SE(d)$?\nIf this method is good enough, the point permutation action should also be subject to the frame averaging model.\nI would like you to explain the rationale reason for not doing so.\n\nGraph models:\nTwo types of models have been proposed: MLP+FA and GNN+FA.\nThe problem with MLP+FA is that it uses the adjacency matrix itself as input, so when the number of nodes is large, the input space is also large, and the number of parameters is significantly larger than, for example, the model in Maron et al.\nIs it possible to train MLP+FA with, say, 50 nodes?\nAlso, in a real task, the number of nodes in a graph can take many different values, is it possible to train MLP+FA for such a case?\nIn GNN+FA, the problem seems to be that invariance is calculated redundantly as described above, and the contribution of this method is not clear.\n\nReference\n\nZaheer et al.\nDeep sets\nNeural Information Processing Systems (NeurIPS) 2017.\n\nMaron et al. Invariant and Equivariant Graph Networks\nInternational Conference on Learning Representations (ICLR) 2019\n\nKicky et al.\nA New Approach to Design Symmetry Invariant Neural Networks\nInternational Joint Conference on Neural Networks (IJCNN) 2021\n\n\n\n", "summary_of_the_paper": "This paper proposes a method to transform a model into an invariant/equivariant model using the Reynolds operator.\nIn addition, they define a notion called the equivariant frame to compute the Reynolds operator efficiently.", "summary_of_the_review": "The structure of the proposed model has already been seen in Kicki et al. 2021 except for the use of frames, and even if frames are used, MLP+FA for example does not seem to be able to handle changes in inputs such as changes in the number of nodes in the graph.\nWhen combined with the existing strong methods, it gives good results, but this could be achieved by, for example, concatting two GNNs and then transforming them with FNN, so we decided that it is not worthy of evaluation.\n\nAfter some discussion, the score was raised because the theoretical uncertainties and doubts were resolved.\n\n\n\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "1o77Q-KAEmD", "reviewer": "Reviewer_57mq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Strengths**:\n\n- *FA is a very simple framework yet it is potentially very useful*. Group equivariance is an important form of inductive bias in deep learning architectures, but designing architectures that has such equivariance is challenging. It would be very useful if we could adapt any back architecture to become invariant/equivariant to a certain group. However, the previously studied group averaging is computationally infeasible when the group is large, so this paper, which greatly reduces the computational cost of group averaging, could be potentially very useful. I really like this work, and will be looking forward to seeing future development of this work.\n- *Technical statements are all sound and proved*. Mathematical statements in this paper all look correct to me, and they have provided proofs. These statements are clear and rigorous.\n- *Impressive results*. Using the simple idea of frame averaging, the paper demonstrates state-of-the-art results on several tasks. The results are impressive, which suggests that the FA framework can be very useful in practice.\n\n**Weaknesses**:\n- *Lack of simple examples*. While it is not hard to check the correctness of all these statements, it takes me some time to form an intuition of what is proposed in this paper. It would help me a lot if the authors could provide a simple example at the beginning to give readers some intuition. For example, it might be good to work through an example to make MLP translation equivariant (with the simplest possible construction of frames)?  \n- *Insufficient study and explanation of the proposed frames*. \n  - The construction of frames in Section 3.1 seems to come out of nowhere. While I could check they are indeed equivariant, I don’t think I understand the motivation or thinking process behind such designs. \n  - Furthermore, can the frames be simplified? As an example, if we let the input $X$ be a function on groups, i.e. $X=f(g),g\\in G$. Can we let $F(f) = \\arg\\max_{g} ||f(g)||$? I might be wrong, but I think this simple construction is also equivariant? \n  - Are the number of elements output by frames the smaller the better, or is there a balance between performance and computational efficiency?\n\n**Questions**:\n*How stable are the proposed frames*? For the proposed frames, I would be interested to know how stable they are? That is to say, if I add noise to the inputs, will the output subset of groups be significantly different? \n", "summary_of_the_paper": "**Summary and Contributions**:\n\nThe paper introduces a framework called Frame Averaging (FA) that can adapt existing backbone architectures to become invariant/equivariant to new symmetry types. It achieves this by averaging over an input-dependent frame which outputs a subset of groups. Frame averaging is often much more efficient to compute than averaging over the entire group, while at the same time, guarantees exact invariance/equivariance.\n\nOn the technical side, the paper also proves that FA-based models have the same expressive power as the original backbone architectures.\n\nOn the empirical side, the paper provides new classes of models using FA such as universal Euclidean motion invariant point cloud networks / Message Passing GNNs, and demonstrates their practical effectiveness on several tasks.\n", "summary_of_the_review": "The paper studies an important problem that could potentially have great impact: How to adapt existing architectures to become invariant/equivariant to a certain group while maintaining the expressive power and computational efficiency of the original backbone model? The paper provides a simple yet effective solution. The technical statements are sound and the empirical results are impressive.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes a method to make a pre-existing model equivariant to desired symmetries: frame averaging. The strategy relies on a significant reduction of the number of symmetries to average over (with respect to the Reynolds operator) and uniform subsampling. The paper also demonstrates the usefulness of this method theoretically (universal approximation result) and practically (competitive performance). The contributions are clear and the core idea is simple.
I recommend this paper for acceptance with spotlight.
Decision: Accept (Oral)