Year: 2021

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

heading: 1 INTRODUCTION
text: Many tasks in machine learning (ML) require learning functions that are invariant or equivariant with respect to symmetric transformations of the data. For example, graph classification is invariant to a 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 et 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., 2018; Dym & Maron, 2020), computationally expensive or lacking in expressivity (Xu et al., 2018a; Morris et al., 2019; Maron et al., 2019; Murphy et al., 2019). In this paper, we propose a 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 a basic fact that arbitrary functions φ ∶ V → R, Φ ∶ V →W , where V,W are some vector spaces, can be made invariant or equivariant by symmetrization, that is averaging over the group (Yarotsky, 2021; Murphy et al., 2018), i.e.,
ψ(X) = 1 ∣G∣ ∑g∈G φ(g−1 ⋅X) or Ψ(X) = 1 ∣G∣ ∑g∈G g ⋅Φ(g−1 ⋅X). (1)
where G = {g} denotes the group, ψ ∶ V → R is invariant and Ψ ∶ V → W is equivariant with respect to G. Furthermore, since invariant and equivariant functions are fixed under group averaging,
i.e., ψ = φ for invariant φ and Ψ = Φ for equivariant Φ, the above scheme often leads to universal (i.e., maximally expressive) models (Yarotsky, 2021). However, the challenge with equation 1 is that when the cardinality of G is large (e.g., combinatorial groups such as permutations) or infinite (e.g., continuous groups such as rotations), then exact averaging is intractable. In such cases, we are forced to approximate the sum via heuristics or Monte Carlo (MC), thereby sacrificing the exact invariance/equivariance 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. (2021) and Shuaibi et al. (2021) use MC averaging for approximate rotation equivariance in GNNs.
The key observation of the current paper is that the group average in equation 1 can be replaced with an average over a carefully selected subsetF(X) ⊂ G while retaining both exact invariance/equivariance and expressive power. Therefore, if F can be chosen so that the cardinality ∣F(X)∣ is mostly small, averaging over F(X) results in both expressive and efficient invariant/equivariant model. We call the set-valued function F ∶ V → 2G, 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 as the basis for the design of invariant/equivariant networks in this paper.
We instantiate the FA framework by considering different choices of symmetry groups G, their actions on data spaces V,W (manifested by choices of group representations), and the backbone architectures (or part thereof) φ,Φ we want to make invariant/equivariant toG. We consider: (i) MultiLayer 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 invariant/equivariant to Euclidean motions, E(d); (iii) Set network, DeepSets and PointNet (Zaheer et al., 2017; Qi et al., 2017a) adapted to be equivariant or locally equivariant to E(d); (iv) Point cloud network, DGCNN (Wang et 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/equivariant GNN that maintain the power of message passing (Xu et al., 2018a; Morris et al., 2019); and (iii), (iv) furnish a universal permutation and E(d) invariant/equivariant 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., 2020; Dym & Maron, 2020). We experimented with FA on different tasks involving symmetries including: point-cloud normal estimation, beyond 2-Weisfeiler-Lehman graph separation, and n-body dynamics predictions, reaching state of the art performance in all.

heading: 2 FRAME AVERAGING
text: In this section we introduce the FA approach and theory in generic formulation, while in the next section we show the power of this general approach by instantiating it to (seemingly different) problems of interest.

heading: 2.1 FRAME AVERAGING FOR FUNCTION SYMMETRIZATION
text: Let φ ∶ V → R and Φ ∶ V →W be some arbitrary functions, where V,W are normed linear spaces with norms ∥⋅∥V , ∥⋅∥W , respectively. For example, φ,Φ can be thought of as neural networks. We consider a group G = {g} that describes some symmetry we want to incorporate into φ,Φ. The way the symmetries g ∈ G are applied to vectors in V,W is described by the group’s representations ρ1 ∶ G → GL(V ), and ρ2 ∶ G → GL(W ), where GL(V ) is the space of invertible linear maps V → V (automorphisms). A representation ρi preserves the group structure by satisfying ρi(gh) = ρi(g)ρi(h) for all g, h ∈ G (see e.g., Fulton & Harris (2013)). As customary, we will sometimes refer to the linear spaces V,W as representations.
Our goal is to make φ into an invariant function, namely satisfy φ(ρ1(g)X) = φ(X), for all g ∈ G and X ∈ V ; and Φ into an equivariant function, namely Φ(ρ1(g)X) = ρ2(g)Φ(X), for all g ∈ G and X ∈ 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 a subset of the group elements called a frame.
Definition 1. A frame is defined as a set valued function F ∶ V → 2G ∖ ∅.
1. A frame is G-equivariant if F(ρ1(g)X) = gF(X), ∀X ∈ V, g ∈ G, (2)
where as usual, gF(X) = {gh ∣ h ∈ F(X)}, and the equality in equation 2 should be understood as equality of sets.
2. A frame is bounded over a domainK ⊂ V if there exists a constant c > 0 so that ∥ρ2(g)∥op ≤ c, for all g ∈ F(X) and all X ∈K, where ∥⋅∥op 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 and defined by
⟨φ⟩F (X) = 1 ∣F(X)∣ ∑g∈F(X) φ(ρ1(g)−1X) (3)
⟨Φ⟩F (X) = 1 ∣F(X)∣ ∑g∈F(X) ρ2(g)Φ(ρ1(g)−1X) (4)
provides the required function symmetrization. In Appendix A.1 we prove: Theorem 1 (Frame Averaging). Let F be a G equivariant frame, and φ ∶ V → R, Φ ∶ V →W some functions. Then, ⟨φ⟩F is G invariant, while ⟨Φ⟩F is G equivariant.
Several comments are in order: First, the invariant case (equation 3) is a particular case of the equivariant case (equation 4) under the choice of W = R and the trivial representation ρ2(g) ≡ 1. Second, in this paper we only consider X and frame choices F for which F(X) are finite sets. Nevertheless, treating the infinite case is an important future research direction. Third, a trivial choice of an equivariant frame is F(X) ≡ G, that is, taking the frame to be the entire group for all X ∈ 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 3, 4 into standard group averaging operators, equation 1. The problem with this choice, however, is that it often results in an intractable or challenging computation, e.g., when the group is large or infinite. In contrast, as we 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 us provide a simple example for Frame Averaging: consider V = Rn, W = R, and G = R with addition as the group action. We choose the group actions1 in this case to be ρ1(a)x = x + a1, and ρ2(a)b = b + a, where a, b ∈ R, x ∈ Rn, and 1 ∈ Rn is the vector of all ones. We can define the frame in this case using the averaging operator F(x) = { 1
n 1Tx} ⊂ G = R. Note that in this case the frame contains only one element from the
group, in other cases finding such a small frame is hard or even impossible. One can check that this frame is equivariant per Definition 1. The FA of φ ∶ Rn → R would be ⟨φ⟩F (x) = φ(x− 1 n (1Tx)1) in the invariant case, and ⟨φ⟩F (x) = φ(x − 1 n (1Tx)1) + 1 n 1Tx in the equivariant case.
Incorporating G as a second symmetry. An important use case of frame averaging is with the backbones φ,Φ already invariant/equivariant w.r.t. some symmetry group H and our goal is to make it invariant/equivariant to H ×G. For example, say we want to add G = E(3) equivariance to permutation invariant set or graph functions, i.e.,H = Sn. We will provide sufficient conditions for the FA to provide this desired invariance/equivariance. First, let us assumeH is acting on V andW by the representations τ1 ∶H → GL(V ) and τ2 ∶H → GL(W ), respectively. Assume φ is H invariant and Φ is H equivariant. We say that representations ρ1 and τ1 commute if ρ1(g)τ1(h)X = τ1(h)ρ1(g)X for all g ∈ G, h ∈H , andX ∈ V . If ρ1 and τ1 commute then the map γ1 ∶H ×G→ GL(V ) defined by γ1(h, g) = τ1(h)ρ1(g) is a representation of the group H ×G. Second, we would need that the frame F(X) is invariant to H , that is F(τ1(h)X) = F(X). We show a generalization of Theorem 1: Theorem 2 (Frame Average second symmetry). Assume F is H-invariant and G-equivariant. Then,
1. If φ ∶ V → R is H invariant and ρ1, τ1 commute then ⟨φ⟩F is G ×H invariant.
2. If Φ ∶ V →W isH equivariant and ρi, τi, i = 1,2, commmute then ⟨Φ⟩F isG×H equivariant. 1Note that since these are affine maps they are technically not representations but have an equivalent
representation using homogeneous coordinates. Therefore, FA is also valid with affine actions as used here.
Right actions. Above we 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:
F(ρ1(g)X) = F(X)g−1, ∀X ∈ V, g ∈ G (5) and accordingly
⟨φ⟩F (X) = 1
∣F(X)∣ ∑g∈F(X) φ(ρ1(g)X), ⟨Φ⟩F (X) =
1
∣F(X)∣ ∑g∈F(X) ρ2(g)−1Φ(ρ1(g)X) (6)
are 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 3,4. 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 elementX ∈ V is a subgroup ofG defined byGX = {g ∈ G ∣ ρ1(g)X =X}. GX naturally induces an equivalence relation ∼ on F(X), with g ∼ h ⇐⇒ hg−1 ∈ GX . The equivalence classes (orbits) are [g] = {h ∈ F(X)∣g ∼ 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, [g] ∈ F(X)/GX .
The proof is in A.3. The first immediate consequence of Theorem 3 is that the cardinality of F(X) is at-least that of the stabilizer (intuitively, the inner-symmetries) of X , namely ∣F(X)∣ ≥ ∣GX ∣. Therefore, there could be cases, such as when X 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 ∈ GX , and φ(ρ1(h)−1X) = φ(ρ1(g)−1ρ1(r)−1X) = φ(ρ1(g)−1X), since also r−1 ∈ GX . Therefore the summands in equations 3 are constant over orbits, and we get
⟨φ⟩F (X) = 1
mF ∑ [g]∈F(X)/GX φ(ρ1(g)−1X), (7)
where mF = ∣F(X)/GX ∣ = ∣F(X)∣ / ∣GX ∣. This representation of invariant FA requires only mF = ∣F(X)∣/∣GX ∣ evaluations, compared to ∣F(X)∣ in the original FA in equation 3.
Approximation of invariant frame averaging. Unfortunately, enumerating F(X)/GX could be challenging in some cases. Nevertheless, equation 7 is still very useful: it turns out we can easily draw a random element from F(X)/GX with uniform probability. This is an immediate application of the equal orbit size in Theorem 3: Corollary 1. Let F(X) be an equivariant frame, and g ∈ F(X) be a uniform random sample. Then [g] ∈ F(X)/GX is also uniform.
Therefore, an efficient approximation strategy is averaging over uniform samples, gi ∈ F(X), i ∈ [k],
⟪φ⟫F (X) = 1
k
k
∑ i=1 φ(ρ1(gi)−1X). (8)
This approximation is especially useful, compared to the full-blown FA, when mF = ∣F(X)∣/∣GX ∣ is small, i.e., when ∣GX ∣ is large, or X has many symmetries. Intuitively, the smaller mF the better the approximation in equation 8. A partial explanation to this phenomenon is given in Appendix A.4, while an empirical validation is provided in Section 5.2.

heading: 2.2 EXPRESSIVE POWER
text: Another benefit in frame averaging as presented in equations 3 and 4 is that it preserves the expressive power of the base models, φ, Φ, as exaplined next. Consider some hypothesis function space H = {Φ} ⊂ 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 a 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), or DeepSets (Zaheer et al., 2017), or Message Passing Graph Neural Networks (Gilmer et al., 2017). We denote by ⟨H⟩ the collection of functions Φ ∈H after applying the frame averaging in equation 4, ⟨H⟩ = {⟨Φ⟩F ∣ Φ ∈H} .
We set some domain K ⊂ V over which we would like to test the approximation power of ⟨H⟩. To make sure that FA is well defined over K we will assume it is frame-finite, i.e., for every X ∈ K, F(X) is a finite set. Next, we denote KF = {ρ1(g)−1X ∣ X ∈K,g ∈ F(X)}; intuitively, KF ⊂ V contains all the points sampled by the FA operator. Lastly, to quantify approximation error over a set A ⊂ V let us use the maximum norm ∥Φ∥A,W = maxX∈A ∥Φ(X)∥W . We prove that an arbitrary equivariant function Ψ ∈ C(V,W ) approximable by a function fromH over KF is approximable by an equivariant function from ⟨H⟩ (Proof details are found on Appendix A.5). Theorem 4 (Expressive power of FA). If F is a bounded G-equivariant frame, defined over a frame-finite domain K, then for an arbitrary equivariant function Ψ ∈ C(V,W ) we have
inf Φ∈H ∥Ψ − ⟨Φ⟩F∥K,W ≤ c infΦ∈H ∥Ψ −Φ∥KF ,W ,
Where c is the constant from Definition 1.
This theorem can be used to prove universality results if the backbone model is universal, even for non-compact groups (e.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.

heading: 3 MODEL INSTANCES
text: In this section we instantiate the frame averaging framework for the design of several invariant/equivariant architectures. We will consider the following variants of the framework: i) The symmetry group G, representations ρ1, ρ2 and the underlying frame F ; ii) The backbone network architecture for φ (invariant case) or Φ (equivariant case), based on components from existing models.

heading: 3.1 POINT CLOUDS, EUCLIDEAN MOTIONS.
text: Symmetry. We would like to incorporate Euclidean symmetry to existing permutation invariant/equivaraint point cloud networks. The symmetry of interest is G = E(d) = O(d) ⋉ T (d), namely the group of Euclidean motions in Rd defined by rotations and reflections O(d), and translations T (d). We also discuss G = SE(d) = SO(d) ⋉ T (d), where SO(d) is the group of rotations in Rd. We define V = Rn×d, and the group representation2 is ρ1(g)X = XRT + 1tT , where R ∈ O(d) or R ∈ SO(d), and t ∈ Rd denotes the translation. W,ρ2 are defined similarly, unless translation invariance is desired in which case we use the representation ρ2(g)X =XRT . Frame. We define the frame F(X) in this case based on Principle Component Analysis (PCA), as follows. Let t = 1
n XT1 ∈ Rd be the centroid of X , and C = (X − 1tT )T (X − 1tT ) ∈ Rd×d
the covariance matrix computed after removing the centroid from X . In the generic case the eigenvalues of C satisfy λ1 < λ2 < ⋯ < λd. Let v1,v2, . . . ,vd be the unit length corresponding eigenvectors. Then we define F(X) = {([α1v1, . . . , αdvd] , t) ∣ αi ∈ {−1,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 = SE(d), we restrict F(X) to orthogonal, positive orientation matrices; generically there are 2d−1 such elements, which amounts to 2,4 elements for d = 2,3, respectively. Proposition 1. F(X) based 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, F(X) is defined for almost all X except rare singular points. Where it is defined, F is continuous as a 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 Sn invariant/equivariant architectures, per Theorem 2, we will also need to show that the ρ1 (and similarly ρ2) commute with τ ∶ Sn → GL(V ) defined by τ(h)X = PX , where P = Ph, h ∈ Sn, is the permutation representation. That is Ph ∈ Rn×n is the permutation matrix representing h ∈ Sn, that is, Pij = 1 if i = h(j) and
2Technically, this representation is defined by matrices ( R t 0T 1 ) acting on X ′ = [X,1] ∈ Rn×(d+1).
0 otherwise. Indeed τ(h)ρ1(g)X = PXRT +P1tT = ρ1(g)τ(h)X (P 1tT = 1tT ). Furthermore, note that F(τ(h)X) = F(X), therefore F is also Sn invariant. 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 Φd,d′ ∶ Rn×d → Rn×d ′ for the Sn equivariant version of these models. To simplify the discussion, we omit particular choices of layers and feature dimensions, Appendix C.1 provides the full details. We experimented with two design choices: First, consider frame averaged Φ3,3, i.e., ⟨Φ3,3⟩F , yielding a universal, E(3) equivariant versions for PointNet and DGCNN, dubbed FAPointNet 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 Υd,d′ ∶ Rd → Rd ′ an MLP. We decompose the input point cloud to k-nn patches Xi ∈ Rk×3, i ∈ [n], where each patch is sorted by distance. Next, feed each patch into an equivariant FA Υ3k,3d, each with its own frame Fi, resulting in E(3) equivariant features in R3d for every point, Y ∈ Rn×3d; then applying equivariant FA Φ3d,3 providing output in Rn×3. That is, Ψ(X) = ⟨Φ3d,3⟩F ([⟨Υ3k,3d⟩F1 (X1), . . . , ⟨Υ3k,3d⟩Fn (Xn)]), where brackets denote concat in the first dimension. We name this construction FA-Local-PointNet.
Universality. We use Theorem 4 to prove that using a universal set invariant/equivariant backbone φ,Φ, such as DeepSets or PointNet (see e.g., Zaheer et al. (2017); Qi et al. (2017a); Segol & Lipman (2019)) leads to a universal model. Let H be any such universal set-equivariant function collection. That is, for arbitrary continuous set function Ψ we have (in the notation of Section 2.2) infΦ∈H ∥Ψ −Φ∥Ω,W = 0 for arbitrary compact sets Ω ⊂ V . If K ⊂ V is some bounded domain, then the choice of frame F described above implies that KF is also bounded and therefore contained in some compact set Ω ⊂ V . Consequently, Proposition 1 and Theorem 4 imply Corollary 2. A similar results holds for SE(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 2 (FA-DeepSets/PointNet are universal). Frame Averaging DeepSets/PointNet using the frame F defined above results in a universal E(d) × Sn invariant/equivariant model over bounded frame-finite sets K ⊂ V .

heading: 3.2 GRAPHS, PERMUTATIONS
text: Symmetry and frame. Let G = Sn, and V = Rn×d × Rn×n, where X = (Y ,A) ∈ V represents a set of node features Y ∈ Rn×d, and an adjacency matrix (or some edge attributes) A ∈ Rn×n; we assume undirected graphs, meaning A = AT . Let X ∈ V , the representation ρ1 is defined by ρ1(g)X = (PY ,PAP T ), where P = Pg is the permutation matrix representing g ∈ Sn. We define F(X) to contain all g ∈ Sn that sort the rows of the matrix S(X) in column lexicographic manner, i.e., PS(X) is lexicographically sorted; the matrix S is defined as follows. Let L = diag(A1) −A be the graph’s Laplacian. For every eigenspace (traversed in increasing eigenvalue order), spanned by the orthogonal basis u1, . . . ,uk, we add the (equivariant) column diag(∑ki=1 uiuTi ) to S (Fürer, 2010). Hence, the number of columns of S equals to the number of unique eigenvalues of L. 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 φ: (i) MLP applied to vec(Y ,A) and (ii) GNN+ID (Murphy et al., 2019; Loukas, 2020), denoting a GNN backbone equipped with node identifiers as node features. We perform FA with φ according to the frame constructed in Proposition 2. Note that Theorem 3 implies, ∣F(X)∣ ≥ ∣Aut(G)∣, since the stabilizer GX is the automorphism group of the graph, i.e., g ∈ GX = Aut(X) iff ρ1(g)X = X. This means that for symmetric graphs equation 3 can prove too costly. In this case, we use the approximate invariant FA, equation 8.
Universality. Let us use Theorem 4 to prove FA-MLP and FA-GNN+ID are universal. Again, it is enough to consider the equivariant case. LetH ⊂ 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., Sn equivariant) function Ψ, infΦ∈H ∥Ψ −Φ∥Ω,W = 0 for any compact Ω ⊂ V . Let K ⊂ V be some bounded domain, then since G is finite then KF is also bounded and is contained is some compact set. Proposition 2 and Theorem 4 now imply: Corollary 3 (FA-MLP and FA-GNN+ID is graph universal). Frame Averaging MLP/GNN+ID using the frame F above results in a universal Sn equivariant graph model over bounded domains K ⊂ V .

heading: 3.3 GRAPHS, EUCLIDEAN MOTIONS.
text: Symmetry and frame. We consider the group G = E(d) acting on graphs, i.e., V = Rn×d ×Rn×n, where X = (Y ,A) ∈ V represents a set of node and edge attributes, as described above. The group representation is ρ1(g)X = ρ1(g)(Y ,A) = (Y RT + 1tT ,A). We define the frame F(X) = F(Y ) using the node features as in the point cloud case, Section 3.1. Therefore Proposition 1 implies F is equivariant and bounded. Next, also in this case we would like to incorporate E(d) symmetries to an already Sn invariant/equivariant graph neural network architectures; again per Theorem 2, we will also need to show that the ρ1 (and similarly ρ2) commutes with τ ∶ Sn → GL(V ) defined by τ(h)X = (PY ,PAP T ), where P = Ph is the permutation matrix of h ∈ Sn. Indeed τ(h)ρ1(g)X = (PY RT +P1tT ,PAP T ) = ρ1(g)τ(h)X. Furthermore, note that as in the point cloud case F(τ(h)X) = F(X), therefore F is also Sn 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 Φd,d′ ∶ Rn×d × Rn×n → Rn×d ′ ×Rn×n. In this case we constructed a model, as suggested above, by composing two equivariant blocks, Ψ(X) = ⟨Φ(2)3d′,3⟩F ○ ⟨Φ (1) 6,3d′⟩F(X). The input feature size is 6 since we use this network to learn point clouds with velocities (n-body problem). We name this model FA-GNN.

heading: 4 PREVIOUS WORKS
text: Rotation invariant and equivariant point networks. State of the art Sn invariant networks, e.g., (Qi et al., 2017a;b; Atzmon et al., 2018; Li et al., 2018; Xu et al., 2018b; Wang et al., 2019) are not invariant/equivariant to rotations/reflections 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 (Gojcic et al., 2019) can be used for rotation invariance. Other works use some local or global frames to achieve invariance to rotations and translations. Xiao et al. (2020); Yu et al. (2020); 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/reflection 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; Weiler et al., 2018; Cohen et al., 2018). Notably, Tensor Field Networks (TFN), SE(3) transformers, and Group-Equivariant Attention (Thomas et al., 2018; Fuchs et al., 2020; Romero & Cordonnier, 2021) achieve equivariance to both translation and rotation, i.e., SE(3), and are maximally expressive (i.e., universal) as shown in Dym & Maron (2020). These methods, however, are specifically adapted to SE(3) and require high order SO(3) representations as features. Recently Deng et al. (2021) propose a 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., 2019; 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 Sn equivariant. Kondor et al. (2018) introduces a broader set of equivariant operators in MP-GNNs, while Maron et al. (2018) provides a full characterization of linear permutation invariant/equivariant GNN layers. In a parallel approach, trying to avoid harming expressively due to restricted architectures (Xu et al., 2018a; 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., 2016) to averaging over the entire symmetry group (Murphy et al., 2019; 2018), which amount to the trivial frame F ≡ ρ(G), with the symmetry group G = Sn. 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 a canonical ordering and addressing the fact that it may not be unique.
Recently, a body of work studies GNNs with invariance/equivariance to E(3) (or a similar group) to deal with symmetries in molecular data or dynamical systems . Many SE(3) equivariant con-
structions (Anderson et al., 2019; Fuchs et al., 2020; Batzner et 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 Satorras et al. (2021) provides an efficient message passing construction which is E(d) equivariance but is not shown to be universal, thus far.

heading: 5 EXPERIMENTS
text: 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 (Sn invariant); and particles position estimation, i.e., the n-body problem (E(3) equivariant).

heading: 5.1 POINT CLOUDS: NORMAL ESTIMATION
text: Normal estimation is a core geometry processing task, where the goal is to estimate normal data from an input point cloud, X ∈ Rn×3. This task is O(3) equivariant and translation invariant. To test the effect of rotated data on the different models we experimented with three different settings: i) I/I - training and testing on the original data; ii) I/SO(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 − (nT n̂)2, with n being the ground truth normal and n̂ the normal prediction. We used the same random train/test splits from Koch et al. (2019). For baselines, we chose the PointNet (Qi et al., 2017a) and DGCNN (Wang et al., 2019) architectures, which are popular permutation equivariant 3D point cloud architectures. In addition, we also compare to VN-PointNet and VN-DGCNN (Deng et al., 2021), a recent state of the art approach for SO(3) equivariant network design. We also tested our FA models, FA-PointNet and FA-DGCNN as described in Section 3.1. In addition, we tested our local O(3) equivariant model, FA-Local-PointNet. See Appendix C.1 for the further implementation details. The results in Table 1 showcase the advantages of our FA framework: Incorporating FA to 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.
5.2 GRAPHS: EXPRESSIVE POWER
Producing GNNs that are both expressive and computationally tractable is a long standing goal of the graph learning community. In this experiment we test graph separation (Sn invariant task): the ability of models to separate and classify graphs, a basic trait for graph learning. We use two datasets: GRAPH8c (Balcilar et al., 2021) that consists of all non-isomorphic, connected 8 node graphs; and EXP (Abboud et al., 2021) that consists of 3-WL distinguishable graphs that are not 2-WL distinguishable. There are two tasks: (i) count pairs of graphs not separated by a randomly initialized model in GRAPH8c and EXP; and (ii) learn to classify EXP to two classes. We follow Balcilar et al. (2021) experimental setup. As baselines we use GCN Kipf & Welling (2016), GAT Veličković et al. (2018), GIN Xu et al. (2018a), CHEBNET Tang et al.
(2019), PPGN Maron et al. (2019), and GNNML3 Balcilar et al. (2021), all of which are equivariant by construction. We compare to our FA-MLP, and FA-GIN+ID, 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-MLP and GA-GIN+ID as advocated in (Murphy et al., 2019). Appendix C.2 provides full implementation details.
The two first columns in Table 2 show the results of the separation task (i). As expected both FA and GA provide perfect separation, however, are not perfectly invariant unless one computes the full averages on F and G, respectively. Since for some graphs (with many symmetries) full averages are not feasible, we compare the invariance error (see appendix for the exact definition) of GA with that of the approximate FA, equation 8, for 50 randomly permuted inputs. Figure 2-left shows the mean, std, and 90% percentile of invariance error for increasing sample size k. Note that approximate FA is more invariant
even with as little as k = 1 samples, which explains why in the classification task (ii), in Table 2, right column, FA is able to learn while GA fails, when both are trained with sample size k = 1. Figure 2-right compares mF and mG (the maximal number of unique elements in the FA, equation 7) for GRAPH8c dataset. The color and size of the points in the plot represents how many graphs in the dataset have the corresponding (mG,mF) values. This demonstrates the benefit (in one example) of FA over GA in view of Theorem 5 and approximation in equation 8. 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 8.
5.3 GRAPHS: n-BODY PROBLEM
In this task we learn to solve the n-body problem (E(3) equivariant). The dataset, created in (Satorras et al., 2021; Fuchs et al., 2020), consists of a collection of n = 5 particles systems, where each particle is equipped with its initial position in R3 and velocity in R3, and each pair of particles (edge) with a value indicating their charge difference. The task is to predict the particles’ locations after a fixed time. We follow the protocol of (Satorras et al., 2021). As baselines we use EGNN (Satorras et al., 2021), GNN (Gilmer et al., 2017), TFN (Thomas et al., 2018), SE(3)-Transformer (Fuchs et al., 2020) and Radial Field (Köhler et al., 2019). We test our FA-GNN, as described in Section 3.3. Table 3 logs the results, where the metric reported
is the Mean Squared Error between predicted locations and ground truth. As can be seen, FA-GNN improves over the SOTA by more than 10%. Note that the number of parameters used in FA-GNN and EGNN is roughly the same. More details are provided in Appendix C.3

heading: 6 CONCLUSIONS
text: We present Frame Averaging, a generic and principled methodology for adapting existing (backbone) neural architectures to be invariant/equivariant 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 E(3), and GNNs invariant/equivariant to Euclidean motions E(3). We empirically validate the effectiveness of these models on several invariant/equivariant learning tasks. We believe the instantiations presented in the paper are only the first step in exploring the full potential of the FA framework. Interesting open questions, not answered by this paper are: What other symmetries and scenarios can benefit from FA? 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?

heading: A PROOFS

heading: A.1 PROOF OF THEOREM 1
text: Proof. First note that frame equivariance is defined to be F(ρ1(g)X) = gF(X) which in particular means ∣F(ρ1(g)X)∣ = ∣F(X)∣. For invariance, let g′ ∈ G
⟨φ⟩F (ρ1(g ′)X) = 1 ∣F(X)∣ ∑g∈g′F(X) φ(ρ1(g)−1ρ1(g′)X) =
1
∣F(X)∣ ∑g∈F(X) φ(ρ1(g′g)−1ρ1(g′)X)
= 1 ∣F(X)∣ ∑g∈F(X) φ(ρ1(g)−1X) = ⟨φ⟩F (X)
and for equivariance
⟨Φ⟩F (ρ1(g ′)X) = 1 ∣F(X)∣ ∑g∈g′F(X) ρ2(g)Φ(ρ1(g)−1ρ1(g′)X)
= 1 ∣F(X)∣ ∑g∈F(X) ρ2(g′g)Φ(ρ1(g′g)−1ρ1(g′)X)
= ρ2(g′) 1 ∣F(X)∣ ∑g∈F(X) ρ2(g)Φ(ρ1(g)−1X) = ρ2(g′) ⟨Φ⟩F (X)

heading: A.2 PROOF OF THEOREM 2
text: Proof. The proof above A.1, of Theorem 1, is a 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 ρ1, τ1 commuting mean
F(γ1(h, g)X) = F(τ1(h)ρ1(g)X) = F(ρ1(g)τ1(h)X) = gF(τ1(h)X) = gF(X),
which in particular implies that ∣F(γ1(h, g)X)∣ = ∣F(X)∣. Let (h′, g′) ∈H ×G be arbitrary. Then,
⟨φ⟩F (γ1(h ′, g′)X) = 1 ∣F(X)∣ ∑g∈g′F(X) φ(ρ1(g)−1τ1(h′)ρ1(g′)X)
= 1 ∣F(X)∣ ∑g∈F(X) φ(ρ1(g′g)−1τ1(h′)ρ1(g′)X)
= 1 ∣F(X)∣ ∑g∈F(X) φ(ρ1(g)−1τ1(h′)X)
= 1 ∣F(X)∣ ∑g∈F(X) φ(ρ1(g)−1X)
= ⟨φ⟩F (X)
meaning that ⟨φ⟩F is H ×G invariant. Next,
⟨Φ⟩F (γ1(h ′, g′)X) = 1 ∣F(X)∣ ∑g∈g′F(X) ρ2(g)Φ(ρ1(g)−1τ1(h′)ρ1(g′)X)
= 1 ∣F(X)∣ ∑g∈F(X) ρ2(g′g)Φ(ρ1(g′g)−1τ1(h′)ρ1(g′)X)
= 1 ∣F(X)∣ ∑g∈F(X) ρ2(g′g)Φ(ρ1(g)−1τ1(h′)X)
= τ2(h′)ρ2(g′) 1 ∣F(X)∣ ∑g∈F(X) ρ2(g)Φ(ρ1(g)−1X)
= γ2(h′, g′) ⟨Φ⟩F (X) showing that ⟨Φ⟩F is H ×G equivariant.

heading: A.3 PROOF OF THEOREM 3 AND COROLLARY 1
text: Proof. (Theorem 3) First we show GX acts on F(X). For an arbitrary h ∈ GX and equivariant frame F , we have F(X) = F(ρ1(h)X) = hF(X), where in the first equality we used the fact that h ∈ GX and in the second the equivariance of F . This means that if g ∈ F(X) and h ∈ GX then also hg ∈ F(X), or in other words F(X) is closed to actions from GX . Furthermore, since a group acts on itself via bijections we have that the cardinality of all orbits is the same, ∣[g]∣ = ∣GXg∣ = ∣GX ∣, for all [g] ∈ F(X)/GX . Lastly, the equivalence relation g ∼ h⇐⇒ hg−1 ∈ GX shows that F(X) is a union of disjoint orbits of equal cardinality.
Proof. (Corollary 1) Theorem 3 asserts that all orbits [g] ∈ F(X)/GX have the same number of elements. Therefore, a random choice g ∈ F(X) will have equal probability to land in each orbit.
A.4 THE ROLE OF mF IN APPROXIMATION QUALITY OF EQUATION 8
To better understand the role of mF in approximating equation 7 we first note that equation 8 can be written as ⟪φ⟫F (X) = ∑[g]∈F(X)/GX µ̂[g]φ(ρ1(gi)
−1X), where µ̂ is the empiricial distribution over F(X)/GX , assigning to each element [g] ∈ F(X)/GX the fraction of samples landed in [g], i.e., µ̂[g] = ∣ {i ∈ [k]∣gi ∈ [g]} ∣k−1. We next present a lower bound on the probability of any particular µ̂ that provides a good approximation ⟪φ⟫F (X) ≈ ⟨φ⟩F (X). Theorem 5. Let F be an equivariant frame. The probability of an arbitrary µ̂ ∈ {µ̂ ∣ supφ∈Q ∣⟨φ⟩F (X) − ⟪φ⟫F (X)∣ ≤ } is bounded from below as follows,
P (µ̂) ≥ (1 + k)−mF exp(−2mFk 2),
where Q = {φ ∈ C(V,R) ∣ ∣φ(X)∣ ≤ 1,∀X ∈ 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 µ̂. The main takeoff is that for fixed k and , the smaller mF the better the lower bound. The counter-intuitive behaviour of this bound w.r.t. k and stems from the fact that the size of the set of "good" µ̂, namely {φ ∈ C(V,R) ∣ ∣φ(X)∣ ≤ 1,∀X ∈ V } is increasing with k and .
Proof. For brevity we denote m = mF . Our setting can be formulated as follows. We have the uniform probability distribution, denoted µ, over the discrete space [m] (representing the qoutient set F(X)/GX ); µj = 1m , j ∈ [m], and we have numbers aj = φ(ρ1(hj)
−1X), where [hj] ∈ F(X)/GX , j ∈ [m] represent exactly one sample per orbit. In this notation ⟨φ⟩F (X) = ∑ m j=1 aj m
, while the approximation in equation 8 takes the form ⟪φ⟫F (X) = ∑ m j=1 µ̂jaj , where µ̂j = kj/k, where kj is the number of samples gi ∈ [hj], i ∈ [k], i.e., samples that landed in the j-th orbit. Therefore,
sup φ∈Q ∣⟨φ⟩F (X) − ⟪φ⟫F (X)∣ = sup∣aj ∣≤1 RRRRRRRRRRR m ∑ j=1 aj ( 1 m − µ̂j) RRRRRRRRRRR = m ∑ j=1 ∣ 1 m − µ̂j ∣ = 2 ∥µ − µ̂∥TV ,
where the latter is the total variation norm for discrete measures (Levin & Peres, 2017). We denote H(µ̂∣µ) = ∑mj=1 log(µ̂j) log ( µ̂j µj
) the KL-divergence. The Pinsker inequality and its inverse for discrete positive measures are (see e.g., (Polyanskiy & Wu, 2014)):
1 2 ∥µ̂ − µ∥2TV ≤H(µ̂∣µ) ≤ 2 α ∥µ̂ − µ∥2TV , (9)
where α = minj∈[m] µj =m−1. Therefore,
Γ = {µ̂ ∣ sup φ∈Q
∣⟨φ⟩F (X) − ⟪φ⟫F (X)∣ ≤ } = {µ̂ ∣ 2 ∥µ̂ − µ∥TV ≤ } ⊂ {µ̂ ∣ H(µ̄∣µ) ≤ 2m
2 }
Now, application of Large Deviation Theory (Lemma 2.1.9 in Dembo & Zeitouni (2010)) provides that for µ̂ so that H(µ̂∣µ) ≤
2m 2 :
P (µ̂) ≥ 1 (1 + k)m e− km 2 2 .

heading: A.5 PROOF OF THEOREM 4
text: Proof. Let Ψ ∈ C(V,W ) be an arbitrary G equivariant function, F a bounded G equivariant frame over a frame-finite domain K. Let c > 0 be the constant from Definition 1. For arbitrary X ∈K,
∥Ψ(X) − ⟨Φ⟩F (X)∥W = ∥⟨Ψ⟩F (X) − ⟨Φ⟩F (X)∥W
≤ 1 ∣F(X)∣ ∑g∈F(X) ∥ρ2(g)Ψ(ρ1(g)−1X) − ρ2(g)Φ(ρ1(g)−1X)∥W
≤ max g∈F(X) ∥ρ2(g)∥op ∥Ψ −Φ∥KF ,W
≤ c ∥Ψ −Φ∥KF ,W
where in the first equality we used the fact that ⟨Ψ⟩F = Ψ since Ψ is already equivariant.

heading: A.6 PROOF OF PROPOSITION 1
text: Proof. Let us prove F is equivariant (equation 4). Consider a transformation g = (R, t) ∈ G, and let (O,s) ∈ F(X), then
C =OΛOT , s = 1 n XT1,
where OΛOT is the eigen decomposition of C. Note that the group product of these transformations is
(R, t)(O,s) = (RO,Rs + t). We need to show (RO,Rs + t) ∈ F ((R, t)X). Indeed, RO ∈ O(3) and consists of eigenvectors of C =RXT (I − 1
n 11T )XRT as can be verified with a direct computation. If O,R ∈ SO(d) then
also RO ∈ SO(d). Furthermore
1 n (XRT + 1tT )T 1 = 1 n (RXT + t1T )1 =Rs + t
as required. We have shown (R, t)F(X) ⊂ F((R, t)X) for all X and (R, t). To show the other inclusion let X = (R, t)−1Y and get F((R, t)−1Y ) ⊂ (R, t)−1F(Y ) that also holds for all Y and (R, t). In particular (R, t)F(X) ⊃ F((R, t)X). The frame F is bounded since for compact K ⊂ Rn×d, the translations n−1XT1 are compact and therefore uniformly bounded for X ∈K, and orthogonal matrices always satisfy ∥R∥2 = 1.

heading: A.7 PROOF OF PROPOSITION 2
text: Proof. First note that by definition S(X) is equivariant in rows, namely S(ρ1(g)X) = ρ1(g)S(X). Therefore if g ∈ F(X) ⊂ Sn, then by definition of the frame ρ1(g)S is sorted. Therefore, ρ1(g)S = ρ1(gh)ρ1(h)−1S(X) = ρ1(gh)S(ρ1(h)−1X) is sorted and we get that gh ∈ F(ρ1(h)−1X). We proved F(X)h ⊂ F(ρ1(h)−1X) for all h ∈ G and all X ∈ V . Taking X = ρ1(h)Y for an arbitrary Y ∈ V , and h = g−1 for arbitrary g ∈ G, we get F(ρ1(g−1)Y) ⊂ F(Y)g, for all g ∈ G and Y ∈ V . We proved F(X)h = F(ρ1(h)−1X), which amounts to right action equivariance, see equation 5. The frame is bounded since ρ1(G) is a finite set.
B EMPIRICAL FRAME ANALYSIS
Repeating eigenvalues. We empirically test the likeliness of repeating eigenvalues in the covariance matrix used from the definition of frame in Section 3.1. We use the data from the n-body dataset (Satorras et al., 2021). Let X ∈ Rn×3 represent the set of particles locations (each set centered around 0 and scaled to have maxxi∈X ∥xi∥2 = 1) and λ1 ≤ λ2 ≤ λ3 be the eigenvalues, sorted in increasing order, of the covariance matrix C = (X − 1tT )T (X − 1tT ) . In order to measure the proximity of eigenvalues across the dataset we use the notion of eigenvalues spacing si = λi+1−λis̄ , i = 1,2, where s̄ = λ3−λ1
2 is the mean spacing. Furthermore we define
smin = min{s1, s2} as the minimal normalized spacing, a 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 E(d) equivariance.
Frame stability. Here we test stability of our O(d) frame defined in Section 3.1. By stability we mean the magnitude of change of a frame w.r.t. the change in the input X . A desired attribute of the constructed frame is to be stable, that is, to exhibit small changes if the input is perturbed. We quantify this stability by comparing the distance between our frames to frames constructed by a noisy input. As in the previous experiment used the data from the n-body dataset (Satorras et al., 2021). Let X ∈ Rn×3 represent the set of particles locations (each set centered around 0 and scaled to have maxxi∈X ∥xi∥2 = 1) and Xσ =X+Z where zi,j ∼ N (0, σ) is the noisy input sample . We compute F(X) and F(Xσ) and choose representatives from each set g = (R, t) ∈ F(X), gσ = (Rσ, tσ) ∈ F(Xσ). We measure the distance between the frames as a function of the representatives -
E(R,Rσ) = 1
3
3
∑ i=1
√ 1 − ⟨R∶,i, (Rσ)∶,i⟩2
Notice that in the case of simple spectrum the distance is invariant to the selection of representatives. In Figure 4 we plot distance of original and noisy frames (and its standard deviation) as function of noise level σ. The plot validates the continuity of frames in the simple spectrum case.
C IMPLEMENTATION DETAILS

heading: C.1 POINT CLOUDS: NORMAL ESTIMATION
text: Here we provide implementation details for the experiment in section 5.1.
PointNet architecture. Our backbone PointNet is based on the object part segmentation network from Qi et al. (2017a). The network consists of layers of the form
FC(n, din, dout) ∶X ↦ ν (XW + 1bT ) MaxPool(n, din) ∶X ↦ 1[maxXei]
where X ∈ Rn×din , W ∈ Rdin×dout , b ∈ Rdout are the learnable parameters, 1 ∈ Rn is the vector of all ones, [⋅] is the concatenation operator, ei is the standard basis in Rdin , and ν is the ReLU activation. In this experiement, for the PointNet baseline and for Φ3,3 (the backbone in FA-PointNet), we used the following architecture:
FC(512,3,64) L1→ FC(512,64,128) L2→ FC(512,128,128) L3→ FC(512,128,512) L4→
FC(512,512,2048) L5→ MaxPool(512,2048) L6→ [L1, L2, L3, L4, L5, L6] L7→
FC(512,4028,256) L8→ FC(512,256,128) L9→ FC(512,128,3).
Note that the original PointNet network also contains two T-Net networks, applied to the input and to 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 Φ3,3.
The FA-Local-Pointnet 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 Υ3k,3d 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, ⟨Φ⟩F , is an FA-Pointnet network applied to a point cloud of dimensions Rn×3d. For FA-Local-PointNet we made the following design choices. Each point patch is constructed as its k nearest neighbors, with k = 20, Xi ∈ R20×3. Then, the backbone Υ3∗20,3∗42 is applied to all patches, with the following PointNet layers:
FC(512,3 ∗ 20,3 ∗ 21)→ FC(512,3 ∗ 21,3 ∗ 42)→ FC(512,3 ∗ 42,3 ∗ 42).
The second backbone, Φ3∗42,3, is built from the following PointNet layers:
FC(512,3 ∗ 32,128) L1→ FC(512,128,256) L2→ FC(512,256,256) L3→ FC(512,256,512) L4→
FC(512,512,2048) L5→ MaxPool(512,2048) L6→ [L1, L2, L3, L4, L5, L6] L7→
FC(512,5248,256) L8→ FC(512,256,128) L9→ FC(512,128,3).
DGCNN architecture. Our backbone DGCNN architecture, Φ3,3, is based on the object part segmentation network from Wang et al. (2018). It consists of EdgeConv(n, din, dout), FC(n, din, dout), and MaxPool layers.
EdgeConv(512,3,64) L1→ EdgeConv(512,64,64) L2→ EdgeConv(512,64,64) L3→
FC(512,64,1024) L4→ MaxPool(512,1024) L5→ [L1, L2, L3, L4, L5] L6→
FC(512,1216,256) L7→ FC(512,256,128) L8→ FC(512,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 a 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).

heading: C.2 GRAPHS: EXPRESSIVE POWER
text: We provide implementation details for the experiments in 5.2. We used two different universal backbones, MLP and GIN equipped with identifiers. The details of those architectures are presented here.
FA/GA GIN+ID architecture. The GIN+ID backbone is based on the GIN (Xu et al., 2018a) network with an addition of identifiers as node features in order to increase expressiveness. For the experiments we used a three-layer GIN with a feature dimension of size 64 and a ReLU activation function. For the added identifiers we defined the input node features as X0 = [X0,In], where n is the number of nodes in the graph, and to handle graphs of different sizes (EXP dataset) we padded the 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 a one dimensional binary feature, therefore the input for the MLP network is a flatten representation of the graph (with additional padding according to the graph size) x ∈ R64 2+64. Our architecture consists of layers of the form
FC(din, dout) ∶ x↦ ν (Wx + b)
where W ∈ Rdout×din , b ∈ Rdout 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-classify task:
FC(4160,2048) L1→ FC(2048,4096) L2→ FC(4096,2048) L3→
FC(2048,10) L4→ FC(10,1) L5→ (1)
with ReLU as 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 8, hence we did not used any padding of the input here. The nodes have no features and we just used a flatten version of the adjacency matrix. The architecture for the GRAPH8c task:
FC(64,128) L1→ FC(128,64) L2→ FC(64,10) L3→ (10)
Training details. We followed the protocol from (Balcilar et al., 2021) and trained our model with batch size 100 for 200 epochs. The learning rate was 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.
Invariance Evaluation. We quantify the permutation invariance of a model φ by comparing output of randomly permuted graphs ρ1(gi)X, gi ∈ Sn, i ∈ [50]. The evaluation metric used is the invariance error, defined by
1
m
m ∑ i=1 ∥φ(ρ1(gi)X) − v∥2 ,
where v = 1 m ∑ m i=1 φ(ρ1(gi)X).
The permutation invariance error of the models (FA/GA) was measured as a function of the sample size k. We iterated over the entire GRAPH8c dataset and for every graph computed the invariance error for the FA-MLP ,GA-MLP and regular MLP models (all with the exact same backbone network). The results presented in Figure 2 (left) are normalized by the error of the regular MLP model. The backbone MLP we used for this experiment is of the form:
FC(64,128) L1→ FC(128,128) L2→ FC(128,128) L3→ FC(128,10) L4→ (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, whhere for each node i ∈ [n] the update rule follows,
mij = φe(hli,hlj , aij)
mi = ∑ j∈N (i) mij
hl+1i = φh(hli,mi) where N (i) are the indices of neighbors of vertex i, hli is the embedding of node i at layer l and aij ∈ {−1,1} are edge attributes representing attraction or repelling between pairs of particles. h0 ∈ Rn×6 represents the nodes input features, which in this experiment are a concatenation of the nodes initial 3D position (rotation and translation equivariant) and velocities (rotation-equivariant and translation-invariant). We used node feature dimension of size 60 to maintain a fair comparison with the baselines (Satorras et al., 2021). The functions φe and φh are 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.
Our backbone architectures Φ(2)3d′,3 and Φ (1) 6,3d′ , are both composed of two GNN layers; Φ (2) 3d′,3 has an additional linear embedding of the features as a prefix to the GNN layers while Φ(2)3d′,3 is equipped with a two-layer MLP (SiLU activation) as a decoder to extract final positions.
Training details. We followed the protocol from (Satorras et al., 2021) 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 on a single Nvidia RTX-6000 GPU, using PYTORCH deep learning framework.

Review summaries:
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. The authors furthermore prove: 1)	When interested in invariant prediction, the subset can be chosen in the quotient G/G_X, where G_X is the stabilizer subgroup of X. 2)	When 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. 3)	When using the symmetrization of a universal model, the resulting model class is universal in the class of equivariant functions. 

**Summary and Contributions**:  The 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.  On the technical side, the paper also proves that FA-based models have the same expressive power as the original backbone architectures.  On 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.