A Canonicalization Perspective on Invariant and Equivariant Learning

Authors: george  ma
yifei  wang
derek  lim
stefanie  jegelka
yisen  wang
berkeley  uc
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:10:29

Abstract: In many applications, we desire neural networks to exhibit invariance or equivariance to certain groups due to symmetries inherent in the data. Recently, frame-averaging methods emerged to be a unified framework for attaining symmetries efficiently by averaging over input-dependent subsets of the group, i.e., frames. What we currently lack is a principled understanding of the design of frames. In this work, we introduce a canonicalization perspective that provides an essential and complete view of the design of frames. Canonicalization is a classic approach for attaining invariance by mapping inputs to their canonical forms. We show that there exists an inherent connection between frames and canonical forms. Leveraging this connection, we can efficiently compare the complexity of frames as well as determine the optimality of certain frames. Guided by this principle, we design novel frames for eigenvectors that are strictly superior to existing methods --- some are even optimal --- both theoretically and empirically. The reduction to the canonicalization perspective further uncovers equivalences between previous methods. These observations suggest that canonicalization provides a fundamental understanding of existing frame-averaging methods and unifies existing equivariant and invariant learning methods. Code is available at https://github.com/PKU-ML/canonicalization.

Main paper: 
 introduction: 
 When designing machine learning models, incorporating data symmetry provides a strong inductive bias that facilitates learning and generalization [55, 57, 64] , as evidenced in multiple applications like convolutional neural networks [30] , graph neural networks [52] , point clouds [47, 48] , etc. Often these symmetry priors require models to be invariant or equivariant to certain groups G. Among these approaches, model-specific methods restrict every model component to respect data symmetries, which, however, often sacrifices expressive power [68, 39] . On the other hand, model-agnostic methods allow the use of arbitrary (non-invariant) base models, and ensure invariance or equivariance through averaging over group actions [40, 69, 45] . This approach can attain universal expressive power with first-order backbones, but comes with high computation cost for exponentially large groups (e.g., permutation).To alleviate the latter challenge, frame averaging (FA) [45] has been recognized to be a general framework that can achieve invariance and equivariance efficiently by averaging over a small (inputdependent) subset of the group F(X) ⊂ G, known as a frame. Frame averaging can improve the averaging complexity of orders of magnitude, and has found wide applications in multiple fields such as graph neural networks [43] , materials modeling [13] , antibodies generation [38] , etc. Nevertheless, existing frames are still computationally prohibitive in many domains, in particular, exponentially large for graphs [45] and eigenvectors [36] , making it an intriguing problem to explore the design of more efficient frames of lower complexity.However, a key challenge in this direction is a lack of rigorous ways to characterize the complexity of frames, since existing frames in the literature are still heuristically designed. Although it sounds like a being only of theoretical interest, the ability to characterize the complexity and expressiveness of algorithms has played a vital role in the development of modern algorithms and deep learning models [27] . As an example, the WL hierarchies [65, 54, 72, 71, 73] , alongside other complexity measures [46] , have been the guideline for developing expressive graph neural networks [17, 39, 74] . However, for averaging methods, we still lack a formal language to quantify, compare, and improve different approaches, which hinders principled development in this area.In this paper, we propose canonicalization as an essential view of frame averaging and a practical yet principled measure for the complexity of frames. Canonicalization is a classical technique with wide applications in graph theory [5] , algebra [41] and geometry [4] , and it has also recently been explored for learning with symmetry [36] . The key idea of a canonicalization C is to map all inputs that are equivalent under a group G to the same canonical form C(X). With the canonical input C(X), any (non-invariant) base neural network ϕ will give a G-invariant mapping. We show that for a given group, the differences between any frames can be reduced to the differences of their corresponding canonicalizations. Moreover, in contrast to frames that are generally hard to analyze, we show that the canonicalization perspective is much more fertile, leading to a set of theoretical conditions and practical principles for quantifying the complexity and expressiveness of different frames.To illustrate the benefits of this canonicalization framework, we focus on the symmetries of eigenvectors (sign and basis group), which covers a wide range of applications like graph learning [36, 33] , PCA methods [32] and spectral clustering [3] . In this domain, we show that the canonicalization perspective now allows us to answer some long-standing theoretical questions and derive some better or even optimal frames. Specifically, we reveal that for sign invariance (a major concern for eigenvectors), any sign-invariant network, including the popular SignNet [33] , can be reduced to the same input canonicalization, equivalently. Building on this fundamental result, we easily resolve the open problem of SignNet's universality, by showing that it is not a universal approximator of functions that are sign invariant and permutation equivariant; we also show how to modify SignNet to be universal with minimal changes. Moreover, as a concrete, practical application, we develop new canonicalizations and frames for eigenvectors, named Orthogonal Axis Projection (OAP), which attain optimal or at least better-than-prior complexities for unconstrained and constrained scenarios.At last, we validate our theoretical findings on the EXP dataset, showing that our canonicalization and frames indeed yield orders of lower complexity while demonstrating expressive power beyond 1-WL for distinguishing non-isomorphic graphs. We also show that permutation-equivariant OAP canonicalizes more eigenvectors than previous methods, resulting in better performance on the ZINC and OGBG molecular graph tasks. 
preliminaries: 
 Let f : X → Y be a function and G be a group acting on X and Y. We say f is invariant to G (or G-invariant) if for all g ∈ G and X ∈ X , we have f (g • X) = f (X). Similarly, we say f is equivariant to G (or G-equivariant) if for all g ∈ G and X ∈ X we have f (g • X) = g • f (X). We treat invariance as a special case of equivariance by letting G act on Y as the identity transformation. Existing research has developed neural networks with specific equivariance properties, such as permutation invariance/equivariance [70, 53] , rotation invariance/equivariance [62, 60, 63] , sign/basis invariance [33] , sign equivariance [32] , and multi-set equivariance [75] .In the rest of the paper, we define V, W to be vector spaces with norms ∥•∥ V , ∥•∥ W , and G be a group. The elements g ∈ G act on vectors in V, W with 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 . The group G induces an equivalence relation on V , such that u ∼ v if and only if there exists g ∈ G such that u = ρ 1 (g)v.For each input X, we denote its orbit or equivalence class by V G (X) = {ρ 1 (g) -1 X | g ∈ G}, and its automorphism group as G X = {g ∈ G | ρ 1 (g)X = X}.Given a network ϕ : V → W , the naïve way to achieve invariance is through group averaging:Φ GA (X) = 1 |G| g∈G ϕ ρ 1 (g) -1 X .The resulting Φ is G-invariant, and preserves universal expressive power if ϕ is itself universal. Some existing works adopt this approach [40, 69] . However, exact averaging becomes intractable if the cardinality of G is large, for example, the permutation group of graphs. In such cases, random sampling of the group is necessary [40, 14] , at the sacrifice of exact symmetry.Frame averaging [45] is another approach to achieve exact invariance by averaging over a subset of the group on an input X, i.e., a frame F(X) ⊂ G that maintains G-equivariance: F(ρ 1 (g)X) = gF(X) = {gh | h ∈ F(X)}. If an equivariant frame F is easy to compute, and its cardinality |F(X)| is not too large, then the following frame averaging schemeEQUATIONalso provides the required function symmetrization. Φ FA is G-invariant, and universally approximates G-invariant functions that are approximable by ϕ. Equivariance can be achieved similarly by multiplying ρ 2 (g) with each term. Puny et al. [45] also proposed a variant called invariant frame averaging by averaging over the cosets F(X)/G X to achieve invariance. Since there is no established way to find the representatives of F(X)/G X , they adopt uniform sampling from F(X) to approximate Φ FA . In Section 3.1, the proposed canonicalization achieves the same complexity without sampling.Kaba et al. [26] proposed to learn an equivariant canonicalization function for equivariance. They define the canonicalization function to be h : V → G that is G-equivariant. Let ϕ be the backbone network, then the network taking form ρ 2 (h(X))ϕ(ρ 1 (h(X)) -1 X) is equivariant and universal. The canonicalization h can be seen as a frame whose output has size 1. However, such a G-equivariant h that outputs a single group element does not exist for inputs X with non-trivial automorphism (they introduce a relaxed version of equivariance in this case). Following the classic literature, we define canonicalization on the input space V instead of the group space G, which also avoids the problem above.Denote the Laplacian matrix of a graph as L = I -Â, where Â is the normalized adjacency matrix. Laplacian Positional Encoding (LapPE) uses the eigenvectors of L as positional encoding. LapPE enjoys the benefits of having permutation equivariance and universal expressive power [36] , but also suffers from two well-known ambiguity problems. The first one, known as sign ambiguity, captures that for a unit-norm eigenvector u λi corresponding to eigenvalue λ i , the sign flipped -u λi is also a unit-norm eigenvector of the same eigenvalue. The second one, termed basis ambiguity, captures that eigenvalues with multiplicity degree d i > 1 can have any orthogonal basis in its eigenspace as valid eigenvectors. Because of these ambiguities, we can get distinct GNN outputs for the same graph, resulting in unstable and sub-optimal performance [14, 29, 33] . Besides, sign and basis ambiguities also exist in general eigenvectors that do not require permutation equivariance, which are also widely used in real-world applications, such as PCA methods [32] and spectral clustering [3] . We defer more background to Appendix D. 
canonicalization: a unified and essential view of equivariant learning: 
 In this section, we reduce existing averaging methods to canonicalization and show canonicalization can serve as a unified perspective of these methods. Then, using insights from canonicalization theory, we show how SignNet and BasisNet-two invariant networks on eigenvectors-are equivalent to their underlying canonicalizations, while solving the open problem regarding their expressivity.Frame averaging reduces the number of forward passes in the averaging step compared with group averaging. However, a major obstacle in analyzing the complexity of frames are the automorphisms of the input: G X = {g ∈ G | ρ 1 (g)X = X}, which can be exponentially large and intractable to compute. For instance, consider defining a frame of a graph as the set of all permutations that sort its node features in increasing order. If there are m nodes in the graph with identical node features, then the frame size is at least m!, which grows exponentially. However, all permutations in the frame actually result in the same graph, indicating room for improvement in the efficiency of frame averaging.In this work, we propose an alternative view to design frames that overcome the difficulties above.For each X ∈ V , instead of averaging over the group elements as in FA (Eq. 1), one can directly average over the output elements of the transformations, which is not affected by the complexity of automorphisms since all automorphisms in G X yield the same output. This converts the problem of finding a G-equivariant subset of the group to finding a G-invariant set of inputs. In fact, in the classic literature, this problem is known as canonicalization, that achieves invariance by mapping inputs in the same equivalence class to the same canonical form. Formally, we define a canonicalization as a set-valued functionC : V → 2 V \∅, such that it is G-invariant: C(ρ 1 (g)X) = C(X), ∀X ∈ V, g ∈ G.We call its output C(X) the canonical form of X. Among possible canonicalizations, we are most interested in orbit canonicalization, where the canonical form falls back into the equivalence class: C(X) ⊂ V G (X) for all X ∈ V . With a canonical form, one can instead perform canonical averaging (CA) over C(X) to obtain invariant3 representations:EQUATIONThe following theorem establishes the equivalence between canonicalizations and frames. Theorem 3.1. For any frame F there exists an orbit canonicalization C F s.t. for all X ∈ V , g ∈ G, and backbone ϕ, we have Φ FA (X; F, ϕ) = Φ CA (X; C F , ϕ) and|C F (X)| = |F(X)|/|G X | ≤ |F(X)|.In turn, for any orbit canonicalization C there exists a frame F C s.t. for all X ∈ V , g ∈ G, and backbone ϕ, we have Φ CA (X; C, ϕ) = Φ FA (X; F C , ϕ) and|F C (X)| = |G X | • |C(X)| ≥ |C(X)|.Theorem 3.1 reveals that frames and canonicalizations have a fundamental equivalence. In other words, a frame is built upon a canonicalization, and a canonicalization induces a frame. Henceforth, we can reduce the difficult problem of designing (equivariant) frames to designing canonicalizations. This simple change of perspective also allows us to have a better theoretical characterization of the complexity and optimality of frames. From now on, we adopt a canonicalization language and reveal some key properties of canonicalization that provide principled guidelines for frame/canonicalization design.Here, we examine the theoretical properties of canonicalization in terms of its expressiveness and efficiency. Subsequently, we present unique insights provided by the canonicalization perspective that are not found in the existing literature on frames.For expressiveness, we define the universality of canonicalization as follows. A canonicalization C is universal if for any G-invariant function f : V → W , there exists a well-defined function ϕ : 2 V → W such that f (X) = ϕ(C(X)) for all X ∈ V . The following theorem shows that a canonicalization is universal iff it corresponds to an orbit canonicalization. Theorem 3.2. A canonicalization C is universal iff there exists an orbit canonicalization C c and an injective mapping g :2 V → 2 V such that g(C(X)) = C c (X), ∀X ∈ V .For a formal analysis of efficiency, we refer to |C(X)| as the complexity of a canonicalization on X ∈ V . A canonicalization C is superior to another canonicalization C ′ if it has smaller complexity on all elements: |C(X)| ≤ |C ′ (X)|, ∀X ∈ V . A canonicalization C is optimal if it is superior to any canonicalization. The proposition below establishes the universality and invariance of canonical averaging. Theorem 3.3. Let C be an orbit canonicalization. The canonical average Φ CA is G-invariant. As long as the backbone network ϕ is universal, Φ CA is universal in the sense that it can approximate any continuous G-invariant function f : V → W up to arbitrary precision.The canonicalization size |C(X)| may differ for different inputs. In the most ideal case, an input X admits a single canonical form with |C(X)| = 1, which we call X a canonicalizable element.Formally, an element X ∈ V is canonicalizable if there exists an orbit canonicalization C such that |C(X)| = 1. Otherwise, we call it uncanonicalizable, which may happen under additional constraints on the canonicalization. For example, one cannot determine a canonical sign for [-1, 1] when the canonicalization is required to be permutation equivariant, according to Ma et al. [36] .In fact, a major advantage of transforming frames into canonicalization lies in identifying uncanonicalizable inputs when additional constraints are imposed, a feature absent in existing literature on frames. In particular, the canonicalizability of inputs offers novel insights into the expressive power of invariant networks with equivariance constraints. As will be demonstrated in Section 3.3, invariant networks like SignNet lose expressive power on uncanonicalizable inputs. This enables us to prove the non-universality of SignNet, resolving an open problem in the literature [33, 32] .Canonicalizability is a property of inputs, making it sensible to describe it using canonicalization rather than frames. We refer to Appendix A for a comprehensive discussion on the advantages of the canonicalization perspective.In this section we show how canonicalization can be applied to the eigenvector ambiguity problem, and solve an open question regarding the expressiveness of invariant networks.There are two general methods to attain exact sign and basis invariance for eigenvectors: SignNet and BasisNet [33] and Laplacian Canonicalization [36] . SignNet is parameterized as the network f : R n×k → R d on eigenvectors u 1 , . . . , u k asf (u 1 , . . . , u k ) = ρ [ϕ(u i ) + ϕ(-u i )] k i=1, where ϕ and ρ are unrestricted neural networks and [•] i denotes concatenation of vectors. Ma et al. [36] instead achieved sign invariance on canonicalizable input withf (u 1 , . . . , u k ) = ρ [MAP(u i )] k i=1, where MAP denotes their canonicalization algorithm MAP, which leverages the sign-invariant and permutation-equivariant projection operator to find a canonical sign. Empirically, the two approaches attain comparable performance in practice. Meanwhile, MAP enjoys better computational efficiency because it only requires input pre-processing while SignNet requires two-branch encoding. Although the two algorithms seem rather different, we prove that any permutation-equivariant and sign-invariant function, including SignNet, is equivalent to a close variant of MAP, which we call MAP ++ . Theorem 3.4. A function h : R n → R n×dout is permutation equivariant and sign invariant iff there exists a permutation equivariant (w.r.t. its first input) function ϕ :R n × {0, 1} → R n×dout such that h(u) = ϕ MAP ++ (u), 1 u , ∀u ∈ R n , where MAP ++ (u) = MAP(u), if u is canonicalizable, |u|,otherwise, and 1 u ∈ {0, 1} indicates whether u is canonicalizable. Here |u| denotes element-wise absolute value.Theorem 3.4 indicates that any sign invariant and permutation equivariant function on a single eigenvector can be reduced to a certain mapping based on the MAP++ canonicalization, which allows a unified characterization for such functions. However, when taking the entire eigenvector matrix as input, processing each eigenvector alone (as in SignNet) will take their absolute values (Theorem 3.4), which inevitably loses relative position information between different eigenvectors. As a result, both SignNet and MAP++ are not universally expressive. The same result also holds for BasisNet, since SignNet is a special case of first-order BasisNet with multiplicity d = 1. 4 The universality of SignNet has been an open problem in the literature [33, 32] and we show that a reduction to the canonicalization perspective can provide a fundamental solution to such problems. Concretely, we also construct two non-isomorphic graphs that SignNet fails to distinguish in Appendix E.5. Corollary 3.5. SignNet and BasisNet with first-order permutation equivariant ϕ [37] cannot universally approximate all permutation-equivariant and sign/basis-invariant functions.i 1 < • • • < i d such that ∥Px ij ∥ > 0 and Px ij are linearly independent, 1 ≤ j ≤ d.4. Apply GS to {Px i1 , . . . , Px i d } to obtain the final canonical form.In this algorithm we mainly make use of the permutation equivariance property of GS to construct an overall permutation equivariant canonicalization, while the basis invariance of this canonicalization relies on the basis invariance of projections themselves. We prove that Algorithm 3 is permutation equivariant.Theorem B.2. The OAP canonicalization in Algorithm 3 is permutation equivariant.Proof. Consider the canonical forms of U and U ′ = P U , where P is an arbitrary permutation matrix. We analyze each step of this algorithm. The permutation P acts on the eigenspace by P ′ = P PP ⊤ , as well as on the standard basis vectors by e ′ i = P e i .1. In step 1, since each projection p ′ i = P ′ e ′ i = P PP ⊤ P e i = P p i is permutation equivariant, the value vector α = (α 1 , . . . , α n ) is also permutation equivariant.2. In step 2, we summed vectors e i with the same corresponding α i to get the summary vectors, while the summary vectors themselves are arranged in descending order of the corresponding α i . If we arrange the entries of α in descending order asα i1 ≥ α i2 ≥ • • • ≥ α in ,then the indices vector i = (i 1 , . . . , i n ) would be "almost" permutation equivariant, except that indices corresponding to equal entries could have any ordering. However, as we summed up all e i with equal corresponding α i , the summary vectors x i would be exactly permutation equivariant for 1 ≤ i ≤ k, in the sense that x ′ i = P ( ej ∈Bi e j ) = P x i .3. The projections Px ij are themselves permutation equivariant. Since the norm operator ∥ • ∥ and the linear independence of vectors are not affected by permutation, the indicesi 1 < • • • < i d are permutation invariant.4. Using the permutation equivariance of the Gram-Schmidt process (Theorem B.1), we conclude that the whole algorithm is permutation equivariant.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
exploring optimal canonicalization of eigenvectors: 
 In this section, we delve into the sign and basis ambiguity problems of eigenvectors and graph positional encodings. We propose novel canonicalization algorithms that are provably superior to existing approaches and even optimal. Specifically, we aim to design a canonicalization algorithm C operating on eigenvectors U ∈ R n×d , that is invariant to sign/basis transformations, (possibly) equivariant to permutation transformations, and outputs a set of eigenvectors U * ∈ R n×d in the same eigenspace as U . We consider two settings: without (Section 4.1) and with (Section 4.2) permutation equivariance, corresponding to different problem scenarios.First, we consider the case when we do not need to consider the permutation equivariance of eigenvectors, for example, when samples have a specific ordering. Applications broadly include control systems [50] , image segmentation [66] , source separation [42] , fluid dynamics [25] , etc.Sign Invariance. Although SignNet can also be applied to such cases, we show that a simple canonicalization that determines directions with the first non-zero entry of the eigenvector u can also achieve sign invariance and permutation equivariance while preserving universality.Require: The eigenvector u ∈ R n Ensure: The canonical form u * of u Let i be the smallest index such thatu i ̸ = 0 u * ← u if u i > 0, u * ← -u otherwiseBasis Invariance. Inspired by MAP-basis [36] , we design a more general and powerful canonicalization based on the Gram-Schmidt Orthogonalization of projection vectors, named orthogonalized axis projection (OAP). Specifically, let U ∈ R n×d be eigenvectors in a d dimensional eigenspace, and let P = U U ⊤ be the projection matrix onto the eigenspace span(U ). Denote e 1 , . . . , e n as the standard axis vectors of R n , that is, e i has 1 at the i-th entry and 0 at the other entries. Optimality. We show that Algorithm 1 and 2 are optimal, and can canonicalize all eigenvectors. Theorem 4.2. Algorithm 1 is an optimal orbit canonicalization for all eigenvectors u ∈ R n under sign ambiguity. Algorithm 2 is an optimal orbit canonicalization for all eigenvectors U ∈ R n×d under basis ambiguity.These algorithms eliminate ambiguities of eigenvectors, which is useful in many applications. In Appendix D we show their application to achieve orthogonal equivariance in PCA-frame methods.In this section, we further consider the constraint of permutation equivariance when pursuing sign and basis invariance, which is important for certain data structures like graphs.Sign Invariance. We can retain the universality of MAP and SignNet by extending them to perform canonical averaging (Section 3.1) on uncanonicalizable inputs with the following MAP-full canonicalizationEQUATIONSince Ma et al. [36] proved that MAP canonicalizes all sign-canonicalizable eigenvectors, and if the eigenvector is uncanonicalizable, then the optimal size |C(u)| is 2. Thus, MAP-full is optimal.Basis Invariance. Contrary to the sign case, basis invariance is harder to obtain and MAP-basis proposed by Ma et al. [36] is known to be not optimal. Here, we propose a permutation-equivariant basis canonicalization that is provably superior to MAP-basis. Notice that in OAP (Algorithm 2), the way that we construct smallest indices i 1 , . . . , i d is not permutation equivariant. This motivates us to extend OAP with a permutation equivariant procedure to determine the indices. Specifically, we adopt the following permutation-equivariant hash function to rank axis projections:EQUATION) where p i = Pe i . According to the number of distinct values in {α i } (denoted as k), we divide all standard basis vectors {e i } into k disjoint groups B i , in descending order of α i . Then we define a summary vector x i for each group B i as x i = ej ∈Bi e j + c, where c is a tunable constant. In this way, we arrive at a permutation-equivariant version of OAP for LapPE in Algorithm 3. The summary vectors {x ij } are now permutation equivariant (Appendix B.1), in contrast to {e ij } in Algorithm 2. Require: The Laplacian eigenvectors U ∈ R n×d Ensure: The canonical form U * of U Let i 1 < • • • < i d beAnother interesting aspect of OAP is that with a flexible choice of hashing values α i and indices i j , OAP can serve as a unified framework that encompasses many existing canonicalization algorithms for eigenvectors (as well as graphs).First, it is easy to see that the sign canonicalizations (Algorithm 1 and MAP-sign) are special cases of their basis versions with d = 1. For basis canonicalization, there are two existing methods. One is MAP-basis [36] which also utilizes axis projection but a different construction of basis. Another is proposed in Puny et al. [45] as a way to construct frames for graphs which, according to Theorem 3.1, corresponds to a canonicalization for graphs and can also be adapted to canonicalize LapPE (we defer technical details to Appendix E.8). We call it FA-lap. The following theorem reveals that both MAP and FA-lap are special cases of OAP with degenerated hash functions. Theorem 4.3. Let α i (i = 1, . . . , n) be the outputs of the hash function in the OAP algorithm defined in Equation 4, and let i j (j = 1, . . . , d) be the indices found in Algorithm 3. Then, the MAP algorithm [36] is equivalent to the OAP algorithm that takes α i = ∥P i ∥ for all 1 ≤ i ≤ n and i j = j for all 1 ≤ j ≤ d. The FA-lap algorithm [45] is equivalent to the OAP algorithm that takes α i = P ii for all 1 ≤ i ≤ n.From this connection, we can see that the hashes of MAP and FA-lap are not as distinctive as OAP with Eq. 4. As a result, OAP can canonicalize more eigenvectors and is strictly superior to MAP and FA-lap. There is no superiority between MAP and FA-lap. It remains an open problem whether the permutation-equivariant OAP (Algorithm 3) is optimal.Similarly, these canonicalizations can be adapted to canonicalize graphs (which we call MAP-graph, FA-graph, OAP-graph), and have the same complexity hierarchy (more details in Appendix E.8). We summarize them as follows.Corollary 4.4. For eigenvectors, OAP is strictly superior to MAP and FA-lap. For graphs, OAP-graph is strictly superior to MAP-graph and FA-graph. 
experiments: 
 In this section, we evaluate the expressive power and efficiency of CA on the EXP dataset; we apply our canonicalization to the n-body problem for orthogonal equivariance; we also evaluate OAP for LapPE on graph regression tasks.Table 1 : Accuracy on EXP.Model AccuracyGCN 50% GAT 50% GIN 50% ChebNet 82% FA-GIN+ID 100% CA-GIN+ID 100%To validate the universal expressiveness of CA in Theorem 3.3, we conduct experiments on EXP [1] , which is designed to explicitly evaluate the expressiveness of GNNs. It consists of pairs of graphs that are non-isomorphic but 1-WL indistinguishable. We follow the setup of Balcilar et al. [7] . As baselines, we use GCN [67] , GAT [61] , GIN [68] and ChebNet [59] , all of which are permutation equivariant. We also equip GIN with unique node IDs and apply FA/CA on them, which we denote as FA-GIN+ID and CA-GIN+ID. Note that node IDs endow GIN with universality [40] while also breaking permutation equivariance, and FA/CA restore permutation equivariance while preserving universality. Results are shown in Table 1 . All MP-GNNs achieve trivial performance since their expressive power is limited by 1-WL [68] . Both FA and CA achieve perfect accuracy, showing expressiveness beyond 1-WL.To evaluate the efficiency of different methods, we also compare their average frame size |F(X)| or canonicalization size |C(X)| on EXP. As shown in Table 2 , OAP-graph is more efficient than FA-graph, verifying Corollary 4.4. Since |C(X)| < |F(X)|, CA is more efficient than FA, validating Theorem 3.1. We note that although the numbers are still very large in Table 2 and we still need sampling, a smaller frame/canonicalization size would lead to faster convergence rate towards the true average. This is proven in Appendix C.We evaluate OAP on ZINC [24] . We measure the ratio of non-canonicalizable 5 eigenvectors among all eigenvectors by FA-lap, MAP, and OAP. As shown in Table 3 , they are equivalent in addressing sign We conduct experiments on ZINC [24] and OGBG [22] (c.f., Appendix H). We use GatedGCN [9] and PNA [12] as backbones and apply different PE methods: (1) No positional encoding; (2) Laplacian PE combined with random sign (RS) that randomly flips the signs of eigenvectors [14] ; (3) SignNet [33] ; (4) MAP [36] ; (5) OAP; (6) OAP with LSPE layers [15] . On ZINC, we also evaluate the FA-GIN+ID model in Section 5.1, as well as GIN with edge features (i.e., GINE) [21] . Methods implemented by ourselves are marked with *. The results are reported in Table 4 , 5 and 6. In Table 4 , we observe that FA achieves the lowest performance since it breaks permutation equivariance. The results presented in Tables 4, 5 and 6 demonstrate that incorporating LapPE leads to improved performance across nearly all cases compared to no PE, highlighting the advantages of leveraging expressive PEs. Notably, SignNet, MAP, and OAP show significant performance gains over LapPE, emphasizing the benefits of addressing ambiguities of Laplacian eigenvectors. OAP performs best among these methods, consistent with our theoretical expectations of its superiority over MAP and SignNet. Additionally, SignNet experiences memory issues even with fewer parameters in Table 6 , underscoring the increased memory demands associated with incorporating invariant network architectures. Furthermore, in Table 4 , we find that LSPE enhances the performance of OAP across all models.We compare the time and memory of canonicalization methods with their non-FA backbone on ZINC in Table 7 . Using canonicalization algorithms only increases the pre-processing time of the backbone, which is negligible compared to the training time. On the other hand, the two-branch architecture of SignNet increases the training time and memory.Table 7 : Comparison of time and memory of canonicalization methods with their non-FA backbone on ZINC. For the backbone models, the node features are first concatenated with positional encodings and fed to a positional encoding network (we use masked GIN in our experiments), then the outputs of the positional encoding network are used as input for the main network (GatedGCN or PNA).For the SignNet models, the positional encoding network is substituted with SignNet, which has a two-branch architecture. For models with MAP and OAP, the positional encodings are canonicalized before fed to the positional encoding network.  
conclusion and discussion: 
 In this paper, we illustrated canonicalization as a useful view of frames. From this perspective, we established concrete theoretical conditions for determining the complexity of frames, as well as deriving better and even optimal frames. We believe that the canonicalization perspective has the potential to unify different invariant and equivariant learning approaches for a unified characterization.One limitation of this work lies in that we do not fully resolve the optimality of eigenvector canonicalization under permutation equivariance. It is still yet unknown whether the proposed OAP canonicalization is optimal for Laplacian eigenvectors, and there is still much to explore in terms of canonicalization algorithms across other domains.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The data and models in the paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The creators of assets are properly cited in the main text and the licenses are mentioned in Appendix H.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this paper, we introduced canonicalization as a new perspective to learning with symmetry. We demonstrated how shifting from frames to canonicalization could offer valuable new perspectives, enabling us to address the open problem of the universality of SignNet and BasisNet. Theorem 3.1 establishes an equivalence between frames and canonicalization, prompting the question: why should we favor canonicalization over frames? We put forward three primary reasons:1. Frames encounter challenges with symmetric inputs, i.e. those with non-trivial automorphism, like graphs. In such cases, the automorphism group of an input could grow exponentially, consequently expanding the frame size exponentially as well. However, in theory, each graph has a single canonicalization, highlighting the potential for improvement in frames when dealing with invariance. Here we provide a concrete example concerning node features of graphs. As illustrated in Figure 1 , each node in the graph possesses a unique node ID and a color representing its feature. Suppose we define the frame of this graph as the set of all permutations sorting the node features in the order of grey, blue, and green. For instance, one permutation might yield the sorted node IDs: 0, 1, 4, 6, 8, 3, 5, 2, 7. Although the frame size for this graph is calculated as 5! × 2! × 2! = 480, applying elements of the frame results in the same graph. Consequently, the frame size exceeds the canonicalization size by a factor of 480. 2. Frames must adhere to G-equivariance: F(ρ 1 (g)X) = gF(X), posing a stringent requirement. Consequently, constructing frames becomes challenging. While one approach involves constructing a canonicalization first and then inducing its corresponding frame, a preferable option is to directly utilize canonicalization. The presence of input automorphism complicates the analysis and improvement of existing frames. An optimal canonicalization maintains a size of 1 for all inputs, irrespective of input symmetry. In contrast, the size of even optimal frames depends on input automorphism. 3. The principal advantage of canonicalization over frame lies in the presence of uncanonicalizable inputs, offering intriguing theoretical insights. Sign invariance serves as a notable example. According to Ma et al. [36] , an eigenvector u ∈ R n is uncanonicalizable with respect to sign iff there exists a permutation matrix P such that u = -P u. In Theorem 3.4, we further demonstrated that invariant networks applied to Laplacian eigenvectors lose expressive power on such inputs. Since canonicalizability pertains to the input space V rather than G, analyzing the expressiveness of invariant networks through their underlying canonicalization is considerably more convenient. We aim to delve deeper into this insight by exploring the concept of canonicalizability as introduced in Ma et al. [36] . As demonstrated therein, uncanonicalizable inputs emerge when equivariance constraints are imposed on an already invariant canonicalization while ensuring its universality is maintained. It is the trilemma of invariance, equivariance, and universality that gives rise to uncanonicalizable inputs. A frame possesses equivariance inherently, and examining the frame alone suggests that imposing additional equivariance constraints would not result in conflicts, as observed in the input space.The Gram-Schmidt process is heavily used in our canonicalization algorithms; we discuss it in this subsection. The Gram-Schmidt process is a method of constructing an orthonormal basis from a set of vectors in an inner product space, most commonly the Euclidean space R n equipped with the standard inner product. Specifically, the Gram-Schmidt process takes a finite, linearly independent set of vectors {x 1 , x 2 , . . . , x m } in an inner product space V with m ≤ n, and generates an orthogonal set of vectors {v 1 , v 2 , . . . , v m that spans the same m-dimensional subspace of R n , wherev 1 = x 1 , v 2 = x 2 - ⟨x 2 , v 1 ⟩ ∥v 1 ∥ 2 v 1 , v 3 = x 3 - ⟨x 3 , v 1 ⟩ ∥v 1 ∥ 2 v 1 - ⟨x 3 , v 2 ⟩ ∥v 2 ∥ 2 v 2 , . . . v i = x i - i-1 k=1 ⟨x i , v k ⟩ ∥v k ∥ 2 v k , . . . v m = x m - m-1 k=1 ⟨x m , v k ⟩ ∥v k ∥ 2 v k .The Gram-Schmidt process can be implemented in PyTorch [44] using QR decomposition.def orthogonalize(U: Tensor) -> Tensor: Q, R = torch.linalg.qr(U) S = torch.sign(torch.diag(R)) return Q * SIf the input matrix U ∈ R n×d has full rank (in our case it does because U is a matrix of eigenvectors), and if we require the diagonal elements of R to be positive, then Q and R are unique, and (column vectors of) Q ∈ R n×d gives the Gram-Schmidt orthogonalization of (column vectors of) U . The matrix S in the above code is to ensure that diagonal elements of RS are positive.Proof for the correctness of this method can be found in common linear algebra textbooks [11] . Here we are mainly interested in the equivariance properties of this method. In particular, we prove that it is permutation equivariant and orthogonally equivariant. Theorem B.1. The Gram-Schmidt process is permutation equivariant and orthogonally equivariant.Proof. We first prove the permutation equivariance of GS by induction. Let P ∈ R n×n be an arbitrary permutation matrix.Let {x ′ 1 , x ′ 2 , . . . , x ′ m } be defined by x ′ i = P x i for 1 ≤ i ≤ m, and let {v ′ 1 , v ′ 2 , . . . , v ′ m } be the orthogonal basis generated from {x ′ 1 , x ′ 2 , . . . , x ′ m } by GS. Clearly v ′ 1 = x ′ 1 = P x 1 is permutation equivariant. Suppose v ′ 1 , . . . , v ′ k-1 are all permutation equivariant, then v ′ k = x ′ k - k-1 j=1 ⟨x ′ k , v ′ j ⟩ ∥v ′ j ∥ 2 v ′ j = P x k - k-1 j=1 ⟨P x k , P v j ⟩ ∥v j ∥ 2 P v j = P v k ,where the last equality holds because the inner product operator is invariant under permutation. Thus v k is also permutation equivariant, and by induction we conclude that GS is permutation equivariant.The orthogonal equivariance of GS can be proved similarly. Let Q ∈ R n×n be an arbitrary orthogonal matrix. Let {x ′ 1 , x ′ 2 , . . . , x ′ m } be defined byx ′ i = Qx i for 1 ≤ i ≤ m, and let {v ′ 1 , v ′ 2 , . . . , v ′ m } be the orthogonal basis generated from {x ′ 1 , x ′ 2 , . . . , x ′ m }. Clearly v ′ 1 is orthogonally equivariant. Suppose v ′ 1 , . . . , v ′ k-1 are all orthogonally equivariant, then v ′ k = x ′ k - k-1 j=1 ⟨x ′ k , v ′ j ⟩ ∥v ′ j ∥ 2 v ′ j = Qx k - k-1 j=1 ⟨Qx k , Qv j ⟩ ∥v j ∥ 2 Qv j = Qv kis also orthogonally equivariant, where the last equality holds because orthogonal transformations preserve the inner product. Thus GS is also orthogonally equivariant.Recall that in Algorithm 3, we first defined a set of values α i = hash(p ii , { {p ij } } j̸ =i ) for i = 1, . . . , n, where p i = Px i is the projection of standard basis vectors onto the eigenspace V . Suppose there are k distinct values in {α i }, i.e., |{α i }| = k. Then according to the values of α i we divided the standard basis vectors {e i } into k disjoint groups B i (arranged in descending order of the values of α i ), and defined a summary vector x i for each group B i as the sum of standard basis vectors in that group. Consider the projections of these k summary vectors,Px i . Let i 1 < i 2 < • • • < i d be the smallest d indices such that ∥Px ij ∥ > 0 and Px ij are linearly independent, 1 ≤ j ≤ d.In the final step, we applied the Gram-Schmidt process to Px i1 , . . . , Px i d to obtain the resulting canonical form. These steps can be summarized as follows.1. Computeα i = hash(p ii , { {p ij } } j̸ =i ), 1 ≤ i ≤ n.2. Define summary vectors x i = e j , where the summands e j share the same α j value, and the summary vectors are arranged in descending order of these values.In Algorithm 2, we proposed the OAP-eig canonicalization to address the basis ambiguity of eigenvectors without permutation equivariance. The complete pseudo-code of OAP-eig, along with a detailed time complexity analysis, is shown in Algorithm 4.Algorithm 4 OAP-eig canonicalization for eliminating basis ambiguity without permutation equivariance Require: The eigenvectors U ∈ R n×d Ensure: The canonical formU * of U P ← U U ⊤ ▷ O(n 2 d) complexity U span ← empty matrix of shape n × 0 r ← 0 ▷ rank of U span for [ doO(n 2 d 2 ) complexity]i = 1, . . . , n u ← normalize(P i ) ▷ O(n) complexity if ∥u∥ < ε then ▷ floating-point errors are considered continue end if U tmp ← [U span , u ⊤ ] if rank(U tmp ) = r + 1 then ▷ u is linearly independent with U span , O(nd 2 ) complexity U span ← U tmp r ← r + 1 if r = d then ▷ found indices i 1 , . . . , i d break end if end if end for U * ← GS(U span ) ▷ O(nd 2 ) complexity return U *The overall time complexity of Algorithm 4 is O(n 2 d 2 ). Since in real-world datasets the value of d is usually small (Figure 2 in Ma et al. [36] ), Algorithm 4 is more efficient than eigendecomposition itself whose time complexity is O(n 3 ).In the for loop of Algorithm 4, we aim to find indices i 1 , . . . , i d such that ∥Pe ij ∥ = ∥P ij ∥ > 0 and P ij are linearly independent for 1 ≤ j ≤ d. We look for these indices in a iterative fashion. The matrix U span contains all the already-found indices. We initialize U span to be an empty matrix of shape n×0, and every time we find an index i such that ∥P i ∥ > 0 and P i is linearly independent with the already-found columns vectors of U span , we concatenate the normalized P i to U span . Once we have found a total of d indices (denoted as r in Algorithm 4), we break out of the loop and return the Gram-Schmidt orthogonalization of U span . By the properties of GS, U * is still a set of orthonormal basis in the eigenspace. However, as we iterate through Pe 1 , Pe 2 , . . . , Pe n , the algorithm is not permutation equivariant (the standard basis vectors {e i } are permuted by permutations).In Algorithm 3, we proposed the OAP-lap canonicalization to address the basis ambiguity of Laplacian eigenvectors while respecting permutation equivariance. The complete pseudo-code of OAP-lap, along with a detailed time complexity analysis, is shown in Algorithm 5.The overall time complexity of Algorithm 5 is O(n 2 d 2 ), which is also more efficient than eigendecomposition itself. Although Algorithm 5 need to be applied to every eigenspace of the graph, we note that the number of multiple eigenvalues (eigenvalues with multiplicity greater than 1 and thus have basis ambiguity) are usually small in real-world datasets (Table 9 in Ma et al. [36] ).Algorithm 5 consists of two parts. In the first part, we try to divide the standard basis vectors {e i } 1≤i≤n into disjoint groups {B i } 1≤i≤k . To do that, we first calculate a set of values α i , 1 ≤ i ≤ n for each standard basis vector. Any set of permutation-equivariant α i would guarantee the correctness of the algorithm, but to ensure the algorithm canonicalizes as many eigenvectors as possible (i.e., the superiority of canonicalization), we would like the values of α i to have enough "distinguishability" Algorithm 5 OAP-lap canonicalization for eliminating basis ambiguity with permutation equivarianceRequire: The Laplacian eigenvectors U ∈ R n×d Ensure: The canonical form U * of U P ← U U ⊤ ▷ O(n 2 d) complexity α ← hash(P 11 , { {P 1j } } j̸ =1 ), . . . , hash(P nn , { {P nj } } j̸ =n ) ▷ O(n 2 ) complexity val , ind ← sort(α) ▷ O(n log n) complexity val ← unique(val ) ▷ unique values in {α i }, O(n) complexity k ← |val | if k < d then break ▷ impossible to find d indices end if for i = 1, . . . , k do ▷ O(n) complexity x i ← j e ind[j] such that α ind[j] = val [i]▷ sum of standard basis vectors in groupB i x i ← x i + c1▷ the summary vector of group B i end forU span ← empty matrix of shape n × 0 r ← 0 ▷ rank of U span for i = 1, . . . , k do ▷ O(n 2 d 2 ) complexity u ← normalize(Px i ) ▷ O(n) complexity if ∥u∥ < ϵ then ▷ floating-point errors are considered continue end if U tmp ← [U span , u ⊤ ] if rank(U tmp ) = r + 1 then ▷ u is linearly independent with U span , O(nd 2 ) complexity U span ← U tmp r ← r + 1 if r = d then ▷ found indices i 1 , . . . , i d break end if end if end for U * ← GS(U span )▷ O(nd 2 ) complexity return U * (i.e., the values of α i divide the standard basis vectors into more fine-grained groups, in Babai et al. [6] this is called refinement). In Algorithm 5 we define α i = hash(P ii , { {P ij } } j̸ =i ). We proved the permutation equivariance of such α i in Appendix B.1, and in Appendix E we will prove that they are more fine-grained than previous methods, such as α i = P ii in Puny et al. [45] and α i = ∥P i ∥ in Ma et al. [36] .Once we have the values of α i , we can divide {e i } into disjoint groups B i accordingly. Each value α i corresponds to a standard basis vector e i . Two standard basis vectors belong to the same group if and only if their corresponding α i are equal, and different groups are arranged in descending order of the values of α i . For each group, we define its summary vector x i to be the sum of standard basis vectors in that group, for 1 ≤ i ≤ k. In the second part of Algorithm 5, we use the same method as Algorithm 4 to find the indices i 1 , . . . , i d , except that the vectors {Pe i } 1≤i≤n are substituted with {Px i } 1≤i≤k . Note that in contrast to Algorithm 4, now these vectors are permutation-equivariant by construction.The correctness of Algorithm 1 is obvious and we skip that part. In this subsection we verify the correctness of Algorithm 2 through random simulation. Here "correctness" refers to two things: for any eigenvectors U ∈ R n×d the indices i 1 , . . . , i d can always be found; and that the whole algorithm is basis-invariant as desired. The verification program is shown in Algorithm 6. Let U ∈ R n×d be a random orthonormal matrix representing the eigenvectors, and let Q ∈ O(d) be a random orthonormal matrix that rotates the eigenvectors in their corresponding eigenspace. We pass U and U Q to Algorithm 2 (denoted as canonicalize) and compare the results. If our algorithm is correct, U and U Q should produce identical outputs.Algorithm 6 Verify the correctness of Algorithm 2 correct ← 0, total ← 0 for i = 1, 2, . . . , trials do n ← a random positive integer (greater than 1) d ← a random positive integer (less than n)U ← a random orthonormal matrix in R n×d U 0 ← canonicalize(U ) Q ← a random orthonormal matrix in R d×d W ← U Q W 0 ← canonicalize(W ) correct ← correct + 1 if |U 0 -W 0 | < ε ▷ test basis invariance total ← total + 1 endWe conduct 1000 trials. The results are correct = total = 1000, showing the basis invariance of Algorithm 2. The function canonicalize will throw an error and terminate if the indices i 1 , . . . , i d (and thus the canonical form) cannot be found, so the successful execution of this program also shows that we can always find such indices on random eigenvectors. This aligns with the conclusion of Theorem 4.1.We can also modify Algorithm 6 to verify the orthogonal equivariance of canonical averaging in the n-body problem. Let model denote the model with canonical averaging. The program is shown in Algorithm 7. The results show that canonical averaging achieves exact orthogonal equivariance.Algorithm 7 Verify the orthogonal equivariance of canonical averaging in the n-body problem correct ← 0, total ← 0 for i = 1, 2, . . . , trials do X ← node features in the dataset, representing the inital location of particles X 0 ← model(X) Q ← a random orthonormal matrix in R d×d , where d is the dimension of node featuresW ← XQ W 0 ← model(W ) correct ← correct + 1 if |X 0 Q -W 0 | < ε▷ test orthogonal equivariance total ← total + 1 end for print the values of correct and totalIn this subsection we verify the correctness of Algorithm 3. Here "correctness" refers to the permutation equivariance and basis invariance of the canonicalization algorithm. The verification program is shown in Algorithm 8. Let U ∈ R n×d be a random orthonormal matrix representing the Laplacian eigenvectors, P ∈ R n×n be a random permutation matrix that permutes the rows of U , and let Q ∈ O(d) be a random orthonormal matrix that rotates the Laplacian eigenvectors in their corresponding eigenspace. We pass U , P U , U Q, P U Q to Algorithm 3 (denoted as canonicalize) and compare the results. If our algorithm is correct, U Q should produce invariant outputs, while P U and P U Q should produce equivariant outputs.We conduct 1000 trials. The results are p_correct = q_correct = pq_correct = total = 1000, showing the permutation equivariance and basis invariance of Algorithm 3. The function canonicalize will throw an error and terminate if it could not find a canonical form for U . While for LapPE uncanonicalizable eigenvectors do exist [36] , the successful execution of this program show that empirically the probability for random Laplacian eigenvectors to be uncanonicalizable is 0. Ma et al. [36] has a more rigorous discussion on this in Appendix H of their paper.Algorithm 8 Verify the correctness of Algorithm 3 p_correct ← 0, q_correct ← 0, pq_correct ← 0, total ← 0 for i = 1, 2, . . . , trials do n ← a random positive integer (greater than 1) d ← a random positive integer (less than n) U ← a random orthonormal matrix in R n×d U 0 ← canonicalize(U ) P ← a random permutation matrixV ← P U V 0 ← canonicalize(V ) p_correct ← p_correct + 1 if |P U 0 -V 0 | < ε ▷ test permutation equivariance Q ← a random orthonormal matrix in R d×d W ← U Q W 0 ← canonicalize(W ) q_correct ← q_correct + 1 if |U 0 -W 0 | < ε ▷ test basis invariance Y ← P W Y 0 ← canonicalize(Y ) pq_correct ← pq_correct + 1 if |P U 0 -Y 0 | < ε▷ test both total ← total + 1 end for print the values of p_correct, q_correct, pq_correct and totalIn the EXP experiment the frame or canonicalization size is very large (Table 2 ), so we need to randomly sample from the frame or canonicalization. We use the average of model outputs on the sampled graphs to approximate the true average value on all graphs. In this section we prove that a smaller frame/canonicalization size will lead to faster convergence rate towards the true average. Thus, according to Table 2 , CA is more sample efficient than FA, and OAP is more sample efficient than FA-graph.Denote by F a frame averaging scheme, and by C the canonicalization induced by F. Let V F (X) = { {ρ 1 (g) -1 X | g ∈ F(X)} } be all graphs generated by the frame F(X) from the input X (in our EXP experiment, X would be a graph in the dataset). Note that V F (X) is a multi-set, so if k group actions in F(X) result in the same graph when applied to X, then this graph is counted k times in V F (X). Let C(X) be the canonicalization of input X. Let ϕ be the backbone neural network. Sampling from frame/canonicalization works as follows:1. If the frame size F(X) is large, then the exact averaging 1 |F (X)| g∈F (X) ϕ ρ 1 (g) -1 X is intractable. In this case, we randomly sample n graphs X 1 , . . . , X n from V F (X) and use the empirical average 1 n n i=1 ϕ(X i ) as an approximation to the true average. 2. Similarly, if the canonicalization size C(X) is large, then the exact averaging1 |C(X)| X0∈C(X) ϕ(X 0 ) is intractable.In this case, we randomly sample n graphs X 1 , . . . , X n from C(X) and use the empirical average 1 n n i=1 n i=1 ϕ(X i ) as an approximation to the true average. When we sample from V F (X) or C(X), there are two approaches: drawing with replacement and drawing without replacement. However, it is well-known that drawing without replacement is preferable, as illustrated in the following theorem.Theorem C.1 (Hoeffding [19] ). Let X = (x 1 , . . . , x N ) be a finite population of N real points, X 1 , . . . , X n denote a random sample without replacement from X and Y 1 , . . . , Y n denote a random sample with replacement from X . If f : R → R is continuous and convex, thenEf n i=1 X i ≤ Ef n i=1 Y i .In Theorem C.1, we can understand f as the error between the empirical average and the true average, and X as the outputs of ϕ on the frame or canonicalization. Then we should adopt drawing without replacement since it leads to smaller approximation error and thus faster concentration rate.When drawing without replacement, we compare the concentration rate between frame averaging F and the corresponding canonicalization C. By Theorem 3.1 we have |V F (X)| = |C(X)| • |G X |, where G X is the stabilizer of X in group G. In fact V F (X) is just C(X) repeated for |G X | times. To see this, we can divide F(X) into equivalence classes F(X)/G X , and denote by ∼ the corresponding equivalence relation. For two group actions g 1 , g 2 ∈ F(X), g 1 ∼ g 2 if and only if there exists g 0 ∈ G X such that g 1 = g 0 g 2 . Since X = ρ 1 (g 0 )X by definition, group actions in the same equivalence group will result in the same graph when applied to X. Since each equivalence group has size |G X |, the multi-set of graphs generated by the frame V F (X) is just the repetition of C(X) for |G X | times.Intuitively, the frame size |V F (X)| is |G X | times larger than the canonicalization size |C(X)|, thus drawing without replacement on V F (X) would concentrate slower than on C(X). This is shown in the following theorem. Theorem C.2 (Bardenet and Maillard [8] ). Let X = (x 1 , . . . , x N ) be a finite population of N > 1 real points, and (X 1 , . . . , X n ) be a list of size n < N sampled without replacement from X . Then for all ε > 0, the following concentration bounds hold:Pr max n≤k≤N -1 k t=1 (X t -µ) k ≥ ε ≤ exp - 2nε 2 (1 -n/N )(1 + 1/n)(b -a) 2 ,where a = min 1≤i≤N x i , b = max 1≤i≤N x i , and µ = 1N N i=1 x i .In Theorem C.2, let µ be the true average and let X 1 , . . . , X n be the outputs of ϕ on the sampled graphs from the frame or canonicalization. The upper bound in Theorem C.2 decreases as the frame/canonicalization size N decreases, indicating faster concentration rate. Since |C(X)| < |V F (X)|, we conclude that CA is more sample efficient than FA; and since the frame size of OAPgraph is smaller than that of FA-graph, we conclude that OAP-graph is more sample efficient than FA-graph.We can achieve orthogonal equivariance by using PCA-frame methods [32] . Given input X ∈ R n×k , we compute orthonormal eigenvectors R X ∈ O(k) of the covariance matrix cov(X) = (X -1 n 11 ⊤ X) ⊤ (X -1 n 11 ⊤ X), where O(k) is the group of orthogonal matrices in R k×k . Then we transform X into its canonical form XR X and feed it into a network h. Finally, we apply R ⊤ X to the output of the network to transform it back to its original orientation. The whole process can be described as a neural network model f (X) = h(XR X )R ⊤ X . See Figure 2 for an illustration. Intuitively, this first transforms X by R X into a nearly canonical orientation that is unique up to sign flips; this can be seen as writing the points in the principal components basis, or aligning the principal components of X with the coordinate axes. Then we process XR X using the model h, and finally incorporate orientation information back into the output by post-multiplying by R ⊤ X . However, due to the ambiguities of eigenvectors, the canonical form XR X is not unique, and f cannot achieve exact orthogonal equivariance without addressing these ambiguities. Puny et al. [45] averages over all possible sign choices for R X , which requires 2 k forward passes through the base model h. Lim et al. [32] resolves these ambiguities with special sign equivariant architectures for h. In Section 4.1, we propose to address them using optimal canonicalization.We use canonicalization to achieve exact orthogonal equivariance with PCA-frame methods, as introduced in Appendix D. We consider simulating n-body problems Fuchs et al. [18] . For baselines f( ):R h R ⊤ f( ): R h R ⊤ Figure 2:Using PCA-frame methods to achieve orthogonal equivariance, described as a neural network model f (X) = h(XR X )R ⊤ X , where R X is a choice of principal components for the point cloud X ∈ R n×k . We first transform X via R X into an orientation that is unique up to sign flips, then process XR X using a network h, and finally reintegrate orientation information back into the output via R ⊤ X . Figure reproduced with permission from Lim et al. [32] .we consider FA over signs of eigenvectors and sign-equivariant models [32] . We also evaluate CA based on Algorithm 2 (OAP-eig) and Algorithm 3 (OAP-lap) on this task. We scale the dimension d of the problem and report the training time and MSE of different models. In Figure 3a 3b , we observe comparable performance between these methods. CA achieves much better scalability than FA with a small loss in accuracy. F : V → 2 V \∅ defined by C F (X) = {ρ 1 (g) -1 X | g ∈ F(X)}. Then C F is G-invariant because for any g ′ ∈ G, C F ρ 1 (g ′ )X = ρ 1 (g) -1 ρ 1 (g ′ )X | g ∈ F ρ 1 (g ′ )X = {ρ 1 (g) -1 ρ 1 (g ′ )X | g ∈ g ′ F(X)} = {ρ 1 (g) -1 ρ 1 (g ′ ) -1 ρ 1 (g ′ )X | g ∈ F(X)} = {ρ 1 (g) -1 X | g ∈ F(X)} = C F (X).Thus C F is a canonicalization. Clearly it is also an orbit canonicalization since C F (X) ⊂ V G (X) for all X.Let g 1 , g 2 ∈ F(X). We claim that ρ 1 (g 1 ) -1 X = ρ 1 (g 2 ) -1 X if and only if there exists g 0 ∈ G X such that g 1 = g 0 g 2 , where G X = {g ∈ G | ρ 1 (g)X = X} is the stabilizer of X. On the one hand, ifg 1 = g 0 g 2 , then ρ 1 (g 1 ) -1 X = ρ 1 (g 2 ) -1 ρ 1 (g 0 ) -1 X = ρ 1 (g 2 ) -1 X. On the other hand, if ρ 1 (g 1 ) -1 X = ρ 1 (g 2 ) -1 X, then X = ρ 1 (g 1 )ρ 1 (g 2 ) -1 X, which means g 1 g -1 2 ∈ G X . Denote g 1 g -12 = g 0 , then g 1 = g 0 g 2 . Thus, we can divide the frame into equivalence classes F(X)/G X . Group actions in the same equivalence class result in the same element when applied to X, while group actions in different equivalence classes result in different elements. The total number of elements obtained by applyingF(X) to X is |F(X)|/|G X |, i.e., |C F (X)| = |F(X)|/|G X | ≤ |F(X)|. If X has non-trivial automorphism, then |C F (X)| < |F(X)|,meaning canonicalization is strictly more efficient than the frame.Similarly, let C be an orbit canonicalization. Consider the following set-valued functionF C : V → 2 G \∅ defined by F C (X) = {g ∈ G | ρ 1 (g) -1 X ∈ C(X)}. Since C(X) ⊂ V G (X), F C (X) is well-defined. It is also G-equivariant, since for any g ′ ∈ G, F C ρ 1 (g ′ )X = g ∈ G | ρ 1 (g) -1 ρ 1 (g ′ )X ∈ C ρ 1 (g ′ )X = {g ∈ G | ρ 1 (g ′-1 g) -1 X ∈ C(X)} = {g ∈ g ′ G | ρ 1 (g) -1 X ∈ C(X)} = g ′ F C (X).Thus F C is a frame. We can also see that the canonicalization induced by F C is just C itself. Repeating the arguments in the first part of this proof, we conclude that|F C (X)| = |G X | • |C(X)| ≥ |C(X)|.If X has non-trivial automorphism, then canonicalization is strictly more efficient than the frame.Corollary E.1. A frame F is optimal iff the canonicalization that it induces is optimal. We first show that an orbit canonicalization itself is universal. Lemma E.2. An orbit canonicalization C : V → 2 V \∅ is universal.Proof. Recall universality means that for any G-invariant function f : V → W , there exists a welldefined function ϕ :2 V → W such that f (X) = ϕ(C(X)) for all X ∈ V . Since f is G-invariant,all inputs in the same equivalence class induced by G produce the same output when fed to f . This means that for fixed X, f (X ′ ) is constant for all X ′ ∈ V G (X). We can simply take the ϕ function to be ϕ= f . Since C(X) ⊂ V G (X), we have ϕ(C(X)) = f (C(X)) = f (X)for all X, which proves the universality of C.Then we give the proof of Theorem 3.2.Proof. Sufficiency. If g(C(X)) = C c (X) for some orbit canonicalization C c and all X ∈ V , we prove C is universal. By Lemma E.2, for any G-invariant function f : V → W , there exists a well-defined functionϕ c such that f (X) = ϕ c (C c (X)) for all X ∈ V . Letting ϕ = ϕ c • g, we have f (X) = ϕ c (g(C(X))) = ϕ(C(X)) for all X ∈ V , hence C is universal.Necessity. If C is universal, we construct g : 2 V → 2 V such that it maps C(X) to any subset of V G (X), for all X ∈ V . Since C is invariant, this mapping is well-defined; and since the equivalence classes {V G (X)} are disjoint, this mapping is also injective. Clearly, the canonicalization defined by C c (X) := g(C(X)) is an orbit canonicalization.Proof. The invariance of Φ CA is derived from the invariance of C (in fact this does not rely on C to be an orbit canonicalization). For all g ∈ G and X ∈ V ,Φ CA ρ 1 (g)X; C, ϕ = 1 |C(ρ 1 (g)X)| X0∈C(ρ1(g)X) ϕ(X 0 ) = 1 |C(X)| X0∈C(X) ϕ(X 0 ) = Φ CA (X; C, ϕ).For universality, the G-invariance of f implies that the value of f is constant on each equivalence class V G (X). Since C is an orbit canonicalization, this further implies that f is constant on each canonicalization C(X). Thus f (X) = Φ CA (X; C, f ) for all X. For an arbitrary G-invariant function f , the approximation error of Φ CA is bounded by∥f (X) -Φ CA (X; C, ϕ)∥ W = ∥Φ CA (X; C, f ) -Φ CA (X; C, ϕ)∥ W = 1 |C(X)| X0∈C(X) f (X 0 ) - 1 |C(X)| X0∈C(X) ϕ(X 0 ) W ≤ 1 |C(X)| X0∈C(X) ∥f (X 0 ) -ϕ(X 0 )∥ W ≤ max X∈V ∥f (X) -ϕ(X)∥ W .Thus the approximation error of Φ CA is bounded by that of ϕ, and the universality of ϕ implies the universality of Φ CA .A direct corollary is that we can universally approximate any G-invariant function using MLPs under mild conditions. Corollary E.3. Let V, W be compact normed linear spaces. For any continuous G-invariant f : V → W and any ε > 0, there exists an MLP network ϕ : V → W such that ∥f (X) -Φ CA (X; C, ϕ)∥ ≤ ε holds for all X ∈ V .Proof. Since MLP is universal in approximating continuous functions f : V → W [20] , it also universally approximates such f that is G-invariant. Corollary E.3 immediately follows from Theorem 3.3.Notice that in Theorem 3.4, the function ϕ have two inputs. Apart from the canonical form MAP ++ (u), it also takes an indicator 1 u as input, which indicates whether u is canonicalizable. Thus our proof will be divided into two parts, for canonicalizable and uncanonicalizable eigenvectors respectively. Lemma E.4. A function h : R n → R n×dout is permutation equivariant and sign invariant on all canonicalizable inputs u ∈ R n iff there exists a permutation equivariant function ϕ : R n → R n×dout such that h(u) = ϕ(MAP ++ (u))).Proof. Sufficiency. If ϕ is permutation equivariant, since MAP ++ is also permutation equivariant, so is ϕ(MAP ++ (u)). Since MAP ++ is a canonicalization for sign, ϕ(MAP ++ (u)) is also signinvariant.Necessity. Given a permutation equivariant and sign invariant function h, we simple take ϕ = h, where ϕ is defined on all canonical forms output by MAP ++ . Since MAP ++ is universal on canonical inputs (because it is an orbit canonicalization), by Theorem 3.3, such ϕ exists and ϕ(MAP ++ (u)) is sign invariant, while ϕ does not have to be sign invariant. Since h is permutation equivariant, so is ϕ; and since MAP ++ is itself permutation equivariant, so is the entire function ϕ(MAP ++ (u)).Before proving Corollary 3.5, we first give some intuition about why SignNet is non-universal. In Theorem 3.4 we have already seen that, on uncanonicalizable eigenvectors, the inner ϕ function of SignNet is equal to some other function that only takes in the absolute value of the input eigenvector. This may not be a problem if we are only considering one eigenspace, since a permutation equivariant and sign invariant function is supposed to behave that way; there is no loss of information. The problem occurs when SignNet is applied to multiple eigenvectors, where each eigenvector is passed to the ϕ function separately before concatenated and fed to ρ. We can imagine that taking the absolute value of one uncanonicalizable eigenvector would lose some relative positional information about which elements are positive and which elements are negative, with respect to other eigenvectors. This loss of information makes SignNet non-universal.For instance, we may try to construct a simple counterexample where taking the absolute value loses some information and as a result, SignNet fails to distinguish two non-isomorphic matrices. Drawing from the intuition above, here is our first try:U 1 = [u 11 , u 12 ] = 1 -1 1 -1 2 3 4 5 ⊤ , U 2 = [u 21 , u 22 ] = -1 1 1 -1 2 3 4 5 ⊤ .Suppose the first column eigenvector of U 1 and U 2 corresponds to eigenvalue λ 1 = 1, the second column eigenvector of U 1 and U 2 corresponds to eigenvalue λ 2 = 2, and other eigenvectors not shown corresponds to eigenvalue 0 (so we safely ignore them). Then the Laplacian matrices corresponding to U 1 and U 2 are: EQUATION   .L 1 and L 2 are clearly non-isomorphic, as there does not exist a permutation matrix P such that L 1 = P L 2 P ⊤ . However, the second eigenvector of U 1 and U 2 are the same; the first eigenvector of U 1 and U 2 are uncanonicalizable and according to Theorem 3.4, SignNet will treat them as the same. Therefore, SignNet fails to distinguish these two non-isomorphic matrices, and consequently it cannot approximate any permutation equivariant and sign invariant function that assigns different outputs to these matrices. However, as you may already notice, this example is not really legal, since the eigenvectors in U 1 and U 2 are not orthogonal (they are also not normalized, but whether normalizing or not does not affect our claims, so for simplicity we will just keep them unnormalized).Next, we give a valid example with orthogonal eigenvectors, and show how SignNet fails to distinguish two non-isomorphic matrices in this case:U 1 = [u 11 , u 12 ] = -1 1 -1 1 2 2 -2 -2 0 0 1 -1 1 -1 1 1 0 0 -1 -1 ⊤ , U 2 = [u 21 , u 22 ] = 1 1 -1 -1 2 2 -2 -2 0 0 1 -1 -1 1 1 -1 0 0 -1 1 ⊤ .We still assume λ 1 = 1, λ 2 = 2. Their corresponding Laplacian matrices are: Therefore, by Theorem 3.4, SignNet would give identical output for U 1 and U 2 . Thus it cannot approximate permutation equivariant and sign invariant functions that assign different outputs to these matrices. Unconvinced readers could implement a randomly initialized SignNet themselves and verify our claim (we have already done that).L 1 =               3 -3 3 -3 0 0 2 2 -2 -2 -3 3 -3 3 0 0 -2 -2 2 2 3 -3 3 -3 0 0 2 2 -2 -2 -3 3 -3 3 0 0 -2 -2 2 2 0 0 0 0 6 6 -4 -4 -2 -2 0 0 0 0 6 6 -4 -4 -2 -2 2 -2 2 -2 -4 -4 4 4 0 0 2 -2 2 -2 -4 -4 4 4 0 0 -2 2 -2 2 -2 -2 0 0 2 2 -2 2 -2 2 -2 -Next we discuss BasisNet. We first introduce BasisNet. Let U i ∈ R n×di be an orthonormal basis of a d i dimensional eigenspace. Then BasisNet is parameterized byf (U 1 , . . . , U l ) = ρ [ϕ di (U i U ⊤ i )] l i=1, where each ϕ di is shared amongst all subspaces of the same dimension d i , and l is the number of eigenspaces. Since higher-order permutation equivariant networks are intractable, here we mainly focus on using first-order permutation equivariant ϕ di . This means ϕ di (P U i U ⊤ i P ⊤ ) = P ϕ di (U i U ⊤ i ) for all permutation matrix P .As a special case, ifd i = 1, by letting ϕ(u) = ϕ 1 (uu ⊤ ), BasisNet is reduced to SignNet: f (u 1 , . . . , u l ) = ρ [ϕ(u i )] li=1 . Since SignNet is not universal, there exists a permutation equivariant and sign invariant function acting on matrices whose eigenvalue multiplicity is no more than 1, and SignNet is not able to approximate it. Since BasisNet is reduced to SignNet when d i = 1, BasisNet is also incapable of approximating this function. Therefore BasisNet is not universal either.In fact Theorem 3.4 can be extended to basis, showing loss of information in higher dimension eigenspaces as well. By Ma et al. [36] , eigenvectors U ∈ R n×d are uncanonicalizable under basis ambiguity iff there exists a permutation matrix P such that U ̸ = P U and U = P U Q for some orthogonal matrix Q. We have the following theorem. Theorem E.8. If a function h : R n×d → R n×dout is permutation equivariant and basis invariant on any uncanonicalizable eigenvectors U with U = P U Q, then for any i ̸ = j such that U i = U j Q, we have h(U ) i = h(U ) j . That is, the rows of h(U ) are constant on every orbit of the permutation P .Proof. Let h : R n×d → R n×dout be a permutation equivariant and basis invariant function, and let U = P U Q be any uncanonicalizable eigenvectors. For any i ̸ = j such that U i = U j Q, we claim that there exists a permutation matrix P ′ such that U = P ′ U Q and P ′ permutes the i-th row to the j-th row. We prove this claim as follows.Denote the permutation induced by P as P : i → σ(i), and the permutation induced by P ′ as P ′ : i → σ ′ (i). We wish to prove that there exists P ′ such that U = P ′ U Q and j = σ ′ (i). We construct P ′ as follows.• If σ(i) = j, we could simply let P ′ = P .• Otherwise, if σ(i) = j ′ ̸ = j, denote j = σ(i ′ ) where i ′ ̸ = i. We let σ ′ (i) = j, σ ′ (i ′ ) = j ′ , and σ ′ (k) = σ(k) for all other k ̸ = i, i ′ . Then clearly U = P ′ U Q still holds.By the claim above and observing h(U) = h(P ′ U Q) = h(P ′ U ), we have h(U ) j = h(P ′ U ) j = P ′ h(U ) j = h(U ) i .Theorem E.8 indicates loss of information when BasisNet is applied to multiple eigenspaces with uncanonicalizable eigenvectors.Proof. It suffices to show that the projections {Pe i } 1≤i≤n of the standard basis vectors {e i } 1≤i≤n onto the eigenspace still has full rank. Then since the dimension of the eigenspace is d, we can select d projection vectors such that they remain linearly independent. This is easy to prove. For any vector a ∈ R n , there exists a set of coefficients a 1 , . . . , a n such that a = a 1 e 1 + • • • + a n e n . In particular, this holds for vectors in the eigenspace V . Thus multiplying both sides by P we have a = Pa = a 1 Pe 1 + • • • + a n Pe n for all a ∈ V . Thus the projections {Pe i } 1≤i≤n are still a set of basis in the eigenspace, and Theorem 4.1 follows.Proof. When permutation equivariance is not required, all eigenvectors are canonicalizable. Thus "optimal" here means Algorithm 1 and Algorithm 2 can canonicalize all eigenvectors. Algorithm 1 is clearly an optimal orbit canonicalization since:1. It outputs either u or -u and is an orbit canonicalization;2. Every eigenvector has at least one non-zero element, so Algorithm 1 always succeeds;3. It is sign invariant, since u and -u gives the same output (i.e., the one such that its first non-zero entry is positive).Algorithm 2 is also an optimal orbit canonicalization since:1. The Gram-Schmidt orthogonalization of a set of basis in a subspace is still a set of basis in that subspace (but orthogonalized), so Algorithm 2 is an orbit canonicalization; We strongly recommend the readers to read Appendix B first to get some intuition about our algorithm. Before proving its superiority, we note that Algorithm 3 is an orbit canonicalization, and is basis invariant and permutation equivariant:1. The Gram-Schmidt orthogonalization of a set of basis in a subspace is still a set of basis in that subspace (but orthogonalized), so Algorithm 3 is an orbit canonicalization;2. It is basis invariant, since the projections {p i } = {Pe i } are basis invariant, and all procedures that follow remain basis invariant;3. The permutation equivariance of Algorithm 3 is more technical, which is proved in Theorem B.2 in Appendix B.1.We prove the superiority of OAP-lap over MAP.Proof. OAP is strictly superior to MAP in two aspects. Firstly, we notice that the computation of summary vectors x i in these two algorithms is almost the same, except with different values for α i . In OAP, the α i is defined by α i = hash(P ii , { {P ij } } j̸ =i ), while in MAP, their α ′ i = ∥P i ∥ is a special case of ours. Thus:• If α i = α j , then P ii = P jj and { {P ik } } = { {P jk } }. This indicates α ′ i = ∥P i ∥ = ∥P j ∥ = α ′ j .• However, if α ′ i = α ′ j , this does not necessarily mean α i = α j . For instance, letP 1 = P 2 = (1, 0), then α ′ 1 = α ′ 2 but α 1 ̸ = α 2 .This means α i is more "distinctive" than α ′ i , and as a result we will have a better chance finding indices i 1 < • • • < i d such that Px i1 , . . . , Px i d is a basis of the eigenspace. This is because, more "distinctive" α i would lead to more "refined" (smaller) groups B i , and as a result, the rank of the projections {Px i } will not decrease (and possibly increase). By splitting the group B i into several smaller groups, the original summary vector can be expressed as a linear combination of all new summary vectors, thus the rank of projections of summary vectors does not decrease.Secondly, OAP is superior to MAP by allowing flexible choices of i 1 < • • • < i d . In fact, after working out the summary vectors, the rest of the MAP algorithm is equivalent to Algorithm 3 except that they restrict i 1 = 1, . . . , i d = d. Recall that in MAP, given u 1 , . . . , u i-1 already found, they look for u i in the orthogonal complementary space of ⟨u 1 , . . . , u i-1 ⟩ in V by projecting x i onto that space; and if x i is orthogonal to that space, their algorithm fails. This is exactly what Gram-Schmidt process does to the projection vectors {Px i }. Except in our algorithm, instead of looking at projections Px 1 , . . . , Px d , we look for all projections Px 1 , . . . , Px k and try to select a subset of them such that the algorithm succeeds. This is obviously strictly superior, since there may be cases where Px 1 , . . . , Px d is not a basis of the eigenspace but another subset of Px 1 , . . . , Px k is.Next we prove the superiority of OAP-graph over FA-graph.FA-graph works as follows. Assume the graph has k eigenspaces with projection matrices P 1 , . . . , P k . Let s 1 , . . . , s k be the diagonals of these projection matrices, and let S = [s 1 , . . . , s k ] ∈ R n×k . Then the frame of the graph is defined to be all permutations that sort the rows of S in column lexicographic order, and the canonical form of the graph is the set of graphs produced by these permutations (by applying them to the original graph). We call this canonicalization FA-graph.Next we introduce OAP-graph. Let α ℓ i be defined in the same way as α i , except that ℓ = 1, . . . , k denotes that α ℓ i is computed from the projection matrix of the ℓ-th eigenspace P ℓ . Let S ′ ∈ R n×k be a matrix with S iℓ = α ℓ i . The frame of the graph is the set of all permutations that sort the rows of S ′ in column lexicographic order, and the canonicalization of the graph is the set of graphs produced by these permutations. We name this canonicalization OAP-graph. FA-graph in Puny et al. [45] works in a similar fashion except with different definition for α ℓ i . Since the α ℓ i used in OAP-graph is stronger than in FA-graph, OAP-graph is also superior to FA-graph.then coalesce them into a single valueα i = hash(α (s) i , { {α (j) i } } j̸ =s ),where s is the index of the eigenspace that we are trying to canonicalize. In this way, we can canonicalize eigenvectors from one eigenspace using information from all ℓ eigenspaces, instead of this eigenspace alone. Clearly this variant is also superior to the original OAP canonicalization.We can also adopt learnable networks to substitute certain components of the OAP canonicalization. For example, the hash function in the definition of α i can be made learnable:α i = h(P ii , { {P ij } } j̸ =i ), 1 ≤ i ≤ n,where h is a neural network that is invariant to the ordering of { {P ij } } j̸ =i . We can also replace the Gram-Schmidt orthogonalization with a learnable network:U * = h ′ (Px i1 , . . . , Px i d ),where h ′ is a permutation-equivariant neural network. The output vectors may not be orthogonal, but since h ′ almost certainly preserves the rank of (Px i1 , . . . , Px i d ), it does not lose expressive power.There are four main approaches in the mainstream to achieve equivariance. The first approach, as used in Yarotsky [69] , Murphy et al. [40] , is group averaging. This approach involves averaging over the entire group, which becomes impractical when dealing with large groups. For example, the permutation group on graphs and the sign transformation group on single eigenvectors have an exponential number of elements, while the orthogonal transformation group has an infinite number of elements. In such cases, random sampling becomes necessary. For instance, relational pooling can be used for the permutation group [40] , or random sign sampling can be used for the sign transformation group [14] .The second approach is frame averaging, which was proposed by Puny et al. [45] . This method involves averaging over a smaller frame instead of the entire group. However, a drawback of this approach is that it requires the frame to be equivariant, which is a strong assumption and often difficult to fulfill. Duval et al. [13] also suggested stochastic frame averaging by randomly sampling from the frame. They applied this method to a frame of size 8, given by the set {1, -1} 3 .The third approach is learned canonicalization, proposed by Kaba et al. [26] , which can be viewed as frame averaging with a frame size of 1. However, such canonicalization is not possible if the input has non-trivial automorphism. Additionally, even for non-automorphic inputs, the assumption of equivariance makes constructing such canonicalization challenging.The fourth approach involves designing equivariant network architectures tailored to specific equivariant constraints. For example, Fuchs et al. [18] introduced the SE(3)-transformer, which exhibits equivariance to the SE(3) group. Additionally, Zaheer et al. [70] and Segol and Lipman [53] proposed networks that are permutation invariant and equivariant. Furthermore, Lim et al. [33] and Lim et al. [32] presented networks that maintain sign invariance, basis invariance, and sign equivariance. However, this approach's downside lies in the increased complexity and training cost associated with enforcing equivariance at the network level. Moreover, its applicability is limited to specific groups and cannot be extended to arbitrary ones.In our paper, we introduce a different theoretical framework for canonicalization that unifies previous approaches while achieving the highest efficiency.There have been several related works using canonicalization to achieve equivariance. Apart from Kaba et al. [26] discussed in Section 2.1, Dym et al. [16] proved the impossibility of continuity for canonicalizations with single canonical forms, which explains the subpar performance of some current canonization methods. Since in our framework, the canonical form is defined more generally as a set rather than a single element, it allows for more flexibility and continuity with weighted averaging. Lin et al. [34] proposed a framework of canonicalization that assumes a single canonical form, so their framework is essentially a special case of our framework by taking |C(X)| = 1. The "minimal frame" in their paper is just the induced frame of an optimal canonicalization in our framework. However, the assumption of a single canonical form has the following key limitations:• Theoretical Impossibility. A single canonical form may be theoretically impossible under some constraints. For instance, canonicalization of LapPE requires permutation equivariance, in this case it is theoretically impossible to find a single canonical form for some eigenvectors [36] .• Computational Intractability. A single canonical form may be computationally intractable to find. For instance, computing graph canonicalization is NP-hard [5] . In this case, we have to adopt an approximate approach that admits a set of canonical forms, as in our EXP experiment in Section 5.1.Even if we could find a single canonical form for all inputs, as pointed out by Dym et al. [16] such canonicalizations are still not continuous, which hurts their performance.In summary, compared to previous canonicalization works that only consider single-element canonicalization that may be unrealizable, we take canonicalizability into account throughout the analysis and thus gives a more rigorous and general framework that works for both canonicalizable (single canonical form) and uncanonicalizable (no single canonical form) inputs.Canonical forms, a extensively studied topic in mathematics [41] , have found applications in various domains, including machine learning. While limited theoretical discussions have been conducted regarding its application in equivariant learning, several practical implementations of canonical forms have been proposed in prior research. For example, ConDor, a self-supervised method introduced by Sajnani et al. [51] , focuses on learning to canonicalize the 3D orientation and position of 3D point clouds. Another approach, known as Canonical Field Network (CaFi-Net), was presented by Agaram et al. [2] , employing self-supervision to canonicalize the 3D pose of instances represented by neural fields, such as neural radiance fields (NeRFs). Additionally, Sun et al. [56] proposed an unsupervised capsule architecture specifically designed for 3D point clouds. Furthermore, Ma et al. [35] uses canonicalization to achieve state and action invariance in generative models. In this paper, we contribute rigorous theoretical foundations for canonicalization, specifically addressing the eigenvector canonicalization problem, which holds significant practical implications.Several approaches have been proposed in prior research to tackle the issue of sign ambiguity. One commonly used heuristic is Random Sign (RS), which randomly flips the signs of eigenvectors during training to promote insensitivity to different signs [14] . However, this approach still requires the network to learn these signs, resulting in slower convergence and a more challenging curve fitting task. Another method developed by Bro et al. [10] is a data-dependent approach that selects signs for each singular vector of a singular value decomposition. Nevertheless, in the worst case scenario, the chosen signs can be arbitrary, and this method does not handle rotational ambiguities in higher dimensional eigenspaces. Additionally, Kreuzer et al. [29] introduced the use of relative Laplacian embeddings of two nodes, but their approach encounters a significant computational bottleneck with a complexity of O(n 4 ). Another proposal, known as SignNet [33] , feeds both u and -u to the same network, combines the outputs, and then passes them to another network. However, since the outputs for both u and -u need to be computed, this approach increases the training cost. Furthermore, Ma et al. [36] proposed MAP canonicalization to address the ambiguities of Laplacian eigenvectors during pre-processing. However, their method cannot be applied to general eigenvectors.Lim et al. [33] introduced BasisNet, which is basis invariant. However, achieving universality with BasisNet necessitates utilizing higher-order tensors in R n k , where k can reach values as high as n [37, 49] , making BasisNet impractical. Huang et al. [23] extended BasisNet with SPE, which is both basis-invariant and resistant to perturbations in the Laplacian matrix. However, SPE still encounters exponential complexity akin to BasisNet. Zhang et al. [74] theoretically discussed the expressive power of spectral invariant networks, which include BasisNet. While Ma et al. [36] proposed the MAP canonicalization to tackle ambiguities in Laplacian eigenvectors during pre-processing, their approach is limited to specific eigenvectors, and their canonicalization on basis is relatively weak. In our work, we propose the OAP canonicalization, which is strictly superior to previous methods while incurring negligible computational overhead.Beyond GNN, there exists literature exploring Laplacian eigenvectors of graphs and addressing the sign/basis ambiguity issues. Lai and Zhao [31] presented a solution employing optimal transport theory to tackle sign/basis ambiguities, involving the resolution of a non-convex optimization problem. However, this approach may be less efficient compared to canonicalization methods. In a similar vein, Tam and Dunson [58] proposed symmetrizing the embedding using a heuristic measure called ELD, which bears resemblance to the structure of SignNet.EXP [1] (GPL-3.0 License) is a dataset designed to explicitly evaluate the expressiveness of GNN models, and consists of a set of graph instances {G 1 , . . . , G n , H 1 , . . . , H n }, such that each instance is a graph encoding of a propositional formula. The classification task is to determine whether the formula is satisfiable (SAT). Each pair (G i , H i ) respects the following properties:1. G i and H i are non-isomorphic; 2. G i and H i have different SAT outcomes, that is, G i encodes a satisfiable formula, while H i encodes an unsatisfiable formula; 3. G i and H i are 1-WL indistinguishable, so are guaranteed to be classified in the same way by standard MPNNs; 4. G i and H i are 2-WL distinguishable, so can be classified differently by higher-order GNNs.The n-body problem dataset [28, 18] (MIT License) consists of a collection of n = 5 particles systems. Five particles each carry either a positive or a negative charge and exert repulsive or attractive forces on each other. The input to the network is the position of a particle in a specific time step, its velocity, and its charge. The task of the algorithm is then to predict the relative location and velocity 500 time steps into the future. The original problem is conducted in dimension d = 3. To test the scalability of different methods we also extend this experiment to higher dimensions d = 5, 7, 9, 11, as practiced in Lim et al. [32] .ZINC [24] (MIT License) consists of 12K molecular graphs from the ZINC database of commercially available chemical compounds. These molecular graphs are between 9 and 37 nodes large. Each node represents a heavy atom (28 possible atom types) and each edge represents a bond (3 possible types). The task is to regress constrained solubility (logP) of the molecule. The dataset comes with a predefined 10K/1K/1K train/validation/test split.OGBG-MOLTOX21 and OGBG-MOLPCBA [22] (MIT License) are molecular property prediction datasets adopted by OGB from MoleculeNet. These datasets use a common node (atom) and edge (bond) featurization that represent chemophysical properties. OGBG-MOLTOX21 is a multi-mask binary graph classification dataset where a qualitative (active/inactive) binary label is predicted against 12 different toxicity measurements for each molecular graph. OGBG-MOLPCBA is also a multi-task binary graph classification dataset from OGB where an active/inactive binary label is predicted for 128 bioassays.All (preliminary, failed and main) experiments are run on NVIDIA 3090 GPUs with 24GB memory. In the OGBG-MOLPCBA experiment, the values of these hyper-parameters are listed in Table 11 . Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.We can similarly achieve (relaxed) equivariance[26] by letting the canonicalization output an additional canonizing action g0 with ρ1(g0)X = X0, and multiplying ρ2(g0) on each term.It is still possible to achieve universality with higher-order networks[33], but they are computationally intractable in practice[37,49].Here "non-canonicalizable" means that the canonicalization algorithm fails to canonicalize the eigenvectors.We substitute SignNet with a normal GNN (Masked GIN) when using canonicalization as the PE method. 


Decision: After going through the reviews and author’s rebuttal, I find that the reviewers unanimously agree that this paper presents a valuable contribution by establishing a connection between frame averaging and canonization. This connection leads to a better understanding of frame design and the development of improved frames, particularly for sign and basis equivariance. The theoretical results are strong and well-supported by empirical evidence. The reviews also generally agree that the paper is well written.

However there were some concerns on presentation of the problem statements and theorem statements which seems to have been addressed in the rebuttal responses. The empirical evaluation also seems to be an area of weakness, specially over the limited score of application. Additional dataset results and discussions over multiple application scenarios of canonization seems to address this to a certain extent. 

Overall I would **recommend acceptance of this paper with minor revisions**. The paper presents a valuable contribution to the field of equivariant and invariant learning. The theoretical results are strong, and the empirical evidence supports the effectiveness of the proposed methods. 

Addressing the minor concerns, such as adding discussion on scope of application and including empirical evaluations from rebuttal, will further strengthen the paper's impact and make it a valuable addition to the conference. Here are some specifics to be taken care of - 
1. Please include time and memory statistics as discussed in response to reviewer y3Wh
2. Empirical Evaluation: Please Include additional datasets results as discussed in response to reviewr MgpB.
3. Presentation concerns: As discussed in response to reviewer TcMZ, please make necessary changes in problem and theorem statements.
4. Please include discussions with reviewer 8tUB over application scope in the final version.

Also, please consider revising the title to more accurately reflect the paper's specific focus, as well as address the remaining reviewer concerns, such as clarifying certain theoretical points, minor typos and including clarifying discussions.

Reviews: review: paper_summary: paper_summary: This work makes connections between two model-agnostic approaches to designing equivariant networks: frame averaging and canonization. It is first shown that any function obtained using frame-averaging can also be obtained using canonization. Then it is shown that canonization is computationally more efficient than frame averaging. Further, it is shown that not all elements are "canonizable", i.e., some elements may not have a unique canonical form. This insight helps prove that SignNet and BasisNet are not universal, and they further propose Orthogonalizes Axis Projection (OAP) that leads to optimal designs for the problem of sign and basis equivariance when permutation equivariance is not required. The optimality of the case when permutation equivariance is required remains unsolved. Experiments on several graph datasets confirm validate the working of the proposed OAP method.
strength_weakness: strength_weakness: - Could you please provide a comparison of compute memory and time for all the networks in the experiments. Especially, comparison with non-frame-averaging methods such as GIN would give better insights to the readers on their applicability. Currently, it is not clear how much more expensive/cheap FA/canonicalization is compared to baselines such as GIN.
- In Tab. 2, the practical advantage of canonization over frame averaging in computational complexity for graph dataset seems negligible because of the huge absolute compute time. In Tab 2., how is the averaging done over such a large set? Please provide any preprocessing time required for such computations as well (if applicable).
- Although the initial results in the paper are applicable to the general area of equivariant learning, the applications of the initial results seems to be only useful in the context of equivariance to sign and basis. But the title of the paper has no mention about sign and basis, which makes it look more generally useful than what the experiments indicate.
questions: questions: - In Tab. 1, out of curiosity what happens if we use only GIN+ID? I am curious because GIN+ID is universal (unlike GIN), so, the results on GIN+ID would help understand the benefit of permutation equivariance. Also, some results/plots on the convergence benefits from equivariance would help.
- Are there any other domains where the results on the connection between frame averaging and canonization is directly applicable?
limitations: limitations: Yes.
paper_summary: paper_summary: The work establishes a significant connection between canonicalization and frame averaging, demonstrating an equivalence between the two concepts. By establishing such a relationship, the study efficiently compares the complexity of frames and determines the optimality of frames in relation to the symmetries of eigenvectors. This guides the authors in designing novel frames for eigenvectors that are superior to existing methods, achieving optimality in certain simpler cases. These new frames are both theoretically sound and empirically validated, revealing equivalences between previous methods that had not been identified before. The authors conducted experiments showing the proposed frames' effectiveness on benchmark datasets, achieving higher performance.
strength_weakness: strength_weakness: I found the empirical evaluation to be the weak point of the work. The work provides strong theoretical results. However, a more detailed empirical evaluation would make the work more *complete*. For example, considering another molecule dataset (e.g., Alchemy) and texture reconstruction task (section 4.3 SignNet and Basisnet)

1. Line 98: $G_X$ is not define before. I think it should be defined here instead of Line 129
2. proof of theorems in the supplementary is not in order of the main text.
questions: questions: 1. Line 138: “ This converts the problem of finding a G-equivariant subset of the group to finding a G-invariant set of inputs.” - further explanation of this would be great.

2. Line 175: “The canonization size |C(X)| may differ for different inputs.” — what does the size of |C(X)| tell about the input X?
limitations: limitations: The authors discussed the limitations.
paper_summary: paper_summary: This paper highlights a one-to-one connection between frames over finite groups with ‘canonization’ over the space on which the group acts. This allows authors to prove non-universality of SignNets. Furthermore, authors claim that this view helps highlight equivalence of certain existing algorithms (MAP and FA-lap) arising in sign invariance and permutation equivariance problems, and ultimately leads to a proposal of a novel algorithm OAP.
strength_weakness: strength_weakness: This paper reads as if it was extremely rushed, resulting in a completely unreadable manuscript. There are a number of places where terms are not defined, the problem settings are not stated at all, and connections to existing work are not stated/clarified. Theorems are almost always presented without stating the full problem and without a clear outline of the assumptions. This is particularly true for superiority proofs, which clearly assume something about the hash function, but nothing is ever stated in regards to it. In addition to that, it is not immediately clear where the ‘canonization’ view can be useful, beyond the example provided in this paper. 

Unfortunately, I am unable to comment on the numerical section, as I am not familiar with these experiments. However, given the problems in the rest of the manuscript, I urge the other reviewers to have a closer look at the numerical evaluation.
questions: questions: Below I provide a number of comments and questions.

* First and foremost, while I realize the authors must be approaching from the graph side of the literature - within frame averaging the term used in all papers is ‘canonicalization’, and not ’canonization’, and I would suggest for consistency to refer to it as such, to avoid creating confusion.

* In subsection 2.1, as soon as frame averaging is presented, an assumption is made about finiteness of the group - but is never stated. Furthermore, after section 3.2, the vector spaces considered becomes simply finite dimensional Euclidean spaces. 

* Line 87 and 95 - universal approximation is claimed, however neither a citation, nor a theorem reference is provided.

* In 110 you refer to LapPE. Ideally after introducing a term, you would directly provide a reference to it, instead of at the end of the next sentence. 

* Line 128 - why are automorphisms of the input a major obstacle in analyzing complexity of frames? 

* Line 144 - what you refer to as contractive ‘canonization’, is usually referred to as orbit canonicalization. Eg see  https://arxiv.org/abs/2402.16077

* Line 175 - the same thing is stated twice.

* In 3.3 and onwards, MAP is mentioned, however, since the work is built on top of it, an introduction to MAP (or at least an outline of what it is) should be present in the paper. 

* In line 205 what is the norm of a vector? 

* Whenever a theorem is stated, a reference to where the proof can be found should be stated. 

* In both section 3 and 4 the actual problem being solved is never stated, making it very difficult to follow. By this I mean that given a matrix, you find its eigenvectors, and wish to construct a function which is permutation equivariant … 

* Line 262 - what is the hash function? I can not seem to find any information about what it is, not in numerical experiments either, could you point to where this information is located?

* You mention that you have not been able to show that OAP is optimal - given the indices may not exist, how could it be optimal?

* Line 304 - you never say what FA/CA is - I presume this is frame averaging and canonisation averaging? 

* Whenever superiority or optimality is claimed in the sense of the new definitions, it would be useful to refer the reader to the definition, as it is not clear whether superiority is meant as a technical term, or simply as a qualitative assessment. (e.g. line 204)
limitations: limitations: See weaknesses.
paper_summary: paper_summary: The paper introduces a canonization perspective for designing frames in neural networks. Canonization maps inputs to their canonical forms, allowing efficient and even optimal frame design. The paper shows the connection between frames and canonical forms, leading to the development of new frames for eigenvectors under Orthogonal Axis Projection (OAP) that outperform existing methods. The reduction to canonization uncovers equivalences between previous methods and unifies existing invariant and equivariant frame averaging approaches.
strength_weakness: strength_weakness: ### **Major**:
The overall writing could be improved. The authors claim to present a unified and essential view of equivariance learning, but the application is limited to the orthogonal group and eigenvector canonization. I would expect more examples to justify the theorem, such as the canonization view on the translation group or the product group $E(d)\times S_n$, similar to what frame averaging [1] achieves.


### **Minor**:
- The OAP results appear to be marginal, though considering this as a theoretical paper compensates for this shortcoming. I would like to know what is the result of MAP + LSPE in ZINC 500k compared to OAP + LSPE.
- Please add references in the main text to the appendix for proofs and n-body experiments to enhance readability.
- I suggest the authors add related works including [2] and [3]. I also hope the authors can give a discussion about the highly related concurrent works [4] and [5] to strengthen the contribution, not necessarily in this rebuttal since they are both new papers accepted in this ICML 2024, but please do consider it after this rebuttal.

[1] *Frame Averaging for Invariant and Equivariant Network Design*. Omri Puny, et al. ICLR 2022.

[2] *Learning Probabilistic Symmetrization for Architecture Agnostic Equivariance*. Jinwoo Kim, et al. NeurIPS 2023.

[3] *A Hitchhiker’s Guide to Geometric GNNs for 3D Atomic Systems*. Alexandre Duval, et al.

[4] *Equivariant Frames and the Impossibility of Continuous Canonicalization*. Nadav Dym, et al. ICML 2024.

[5] *Equivariance via Minimal Frame Averaging for More Symmetries and Efficiency*. Yuchao Lin, et al. ICML 2024.
questions: questions: In line 992 (Appendix E.6), why is $\\{Pe_i\\}_{1≤i≤n}$ full rank? Shouldn't it have a rank of $\text{min}(n,d)$?
limitations: limitations: The authors do mention one of the limitations is that OAP does not fully resolve the optimality of eigenvector canonization under permutation equivariance.

Comments: title: Thanks
Official Comment by Reviewer 8tUB
Could you please check the revision examples?
Thanks
Thank you for your response
comment: We will definitely revise the paper according to your suggestions. Thanks again and have a nice day!
I would like to thank the author for illustrating the examples of revisions and I would say that these are siginificantly better than their current versions. As long as these are included and overall presentation of the paper is improved, I am happy to raise the score.
Thank you for your responses and I am satisfied with them. Please do include these discussions in the paper in future revisions. I have changed the score accordingly.
Thanks for the response.
Dear Reviewer TcMZ,

We appreciate your valuable feedback and are committed to revising the paper according to your suggestions. However, as NeurIPS does not allow changes to the PDF during the rebuttal period, we have provided some examples of the revisions we plan to make in the final version. We would greatly appreciate it if you could review these examples to see if they address your concerns satisfactorily.

Thank you for your time and consideration.

Best,
Authors
We are glad to hear that our responses have addressed your concerns. We will incorporate references in the main text to the results in the appendix and revise the title to more accurately reflect the content of the paper in the revision. Thank you again and have a good day!
I thank the authors for their clarifications. For readability, please provide references in the main text to the results in the appendix. Overall, I am happy to increase my score since most of my concerns are clarified. I still find the applications/usefulness limited and the title of the paper seems more general than the applications.
We thank Reviewer TcMZ for the prompt response. We clarify our problem statements and theorem statements in the following points, and we will add these discussions to the camera-ready version of our paper for better readability.

---

### Problem Statements

Our paper consists of two parts, each addressing different problems. We describe the problems in these sections in detail as follows:

1. **Section 3** is focused on the theoretical problem of finding a principled way (i.e., canonicalization) to characterize the complexity of frames $\mathcal{F}(X)$ and frame averaging, a general class of invariant and equivariant learning methods. We have included the definitions of invariant and equivariant learning in Section 2, and the definitions of frames frame averaging in Section 2.1. We will state the main problem more clear in the beginning of Section 3 for better readability.
2. Guided by the theoretical insights in Section 3, **Section 4** is to design better or optimal canonicalization algorithms for a widely appeared class of problems, the sign and basis invariance of eigenvectors. Specifically, we aim to design a canonicalization algorithm $\mathcal{C}$ operating on eigenvectors $\mathbf{U}\in\mathbb{R}^{n\times d}$, that is **invariant** to sign/basis transformations, **equivariant** to permutation transformations, and outputs a set of eigenvectors $\mathbf{U}^*\in\mathbb{R}^{n\times d}$ in the **same eigenspace** as $\mathbf{U}$. We consider two settings of sign and basis invariance: without (Section 4.1) and with (Section 4.2) permutation equivariance, corresponding to different problem scenarios. We will make it more clear in the beginning too.

---

### Theorem Statements

We understand that we define some notations out of the theorems, making them less self-contained and easy-to-understand. To ease your concerns, we will define the notations more clearly, point out the key messages of the main theorem, and add references to previous definitions. Below we give two examples of the modified theorem statements:

- **Theorem 4.1.** Given a set of eigenvectors $\mathbf{U}\in\mathbb{R}^{n\times d}$, let $\mathscr{P}=\mathbf{UU}^\mathrm{T}$ denote the projection matrix of the eigenspace. Let $\mathbf e_1,\dots,\mathbf e_n$ denote the standard basis vectors. Then, there exists indices $1\leq i_1<\cdots<i_d\leq n$, such that for all $1\leq j\leq d$, we have $\lVert\mathscr P\mathbf e_{i_j}\rVert>0$, and the vectors $\mathscr P\mathbf e_{i_1},\dots,\mathscr P\mathbf e_{i_d}$ are linearly independent.
- **Theorem 4.3.** Let $\alpha_i\ (i=1,\dots,n)$ be the outputs of the hash function in the OAP algorithm defined in Equation (4), and let $i_j\ (j=1,\dots,d)$ be the indices found in Algorithm 3. Then, the MAP algorithm is equivalent to the OAP algorithm by taking $\alpha_i=\lVert\mathscr P_i\rVert$ for all $1\leq i\leq n$ and $i_j=j$ for all $1\leq j\leq d$. The FA-lap algorithm is equivalent to the OAP algorithm by taking $\alpha_i=\mathscr P_{ii}$ for all $1\leq i\leq n$.

We will modify all the theorems in our paper similarly to enhance readability and self-containedness. These changes will be reflected in the camera-ready revision of our paper. We hope these changes address your concerns. If you have further concerns or suggestions, please feel free to reach out.
Thanks to the authors for their clarifications and answers. I would like to emphasise that my only concern at this point remains in readability of the paper on two fronts: problem statements and theorem statements. As long as these two are improved in the revision in line with the comments, I would be happy to raise my score.