A Canonicalization Perspective on Invariant and Equivariant Learning
Authors: George Ma
Yifei Wang
Derek Lim
Stefanie Jegelka
Yisen Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Equivariance
Canonicalization
Invariance
Primary area: graph_neural_networks

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.

A Canonicalization Perspective on Invariant and Equivariant Learning
George Ma
Yifei Wang* 2 Derek Lim²
Stefanie Jegelka²
Yisen Wang
School of EECS, Peking University
2 MIT CSAIL
3 TUM CIT/MCML/MSII MIT EECS/CSAIL. State Key Lab of General Artificial Intelligence,
School of Intelligence Science and Technology. Peking University Institute for Artificial Intelligence, Peking University
Abstract
In many applications, desire neural networks exhibit invariance equivari- ance to certain groups due to symmetries inherent the data. Recently, frame- averaging methods emerged to be unified framework for attaining symmetries efficiently by averaging over input-dependent subsets of the group, i.e., frames. What currently lack is principled understanding of the design of frames. In this work, we introduce a canonicalization perspective that provides an essen- tial and complete view of the design of frames. Canonicalization is classic approach for attaining invariance by mapping inputs to their canonical forms. We show that there exists 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-Sone 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 https: githuu..........g com/PKU-ML www./n/oiiiiiaaaaieaaaaaaaaiai.a iomonccllzaaiion ization.
Introduction
When designing machine learning models, incorporating data symmetry provides 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 arbitrary (non-invariant) base models, and ensure invariance or equivariance through averaging over group actions [40, 69, 45]. This approach attain universal expressive power with first-order backbones, but comes with high computation cost for exponentially large groups (e.g., permutation).
'Equal Contribution. George Ma has graduated from Peking University, and is currently Ph.D. student at UC Berkeley.
Conresponding Author: Yisen Wang (yisen. (yisen.wangōpku eeragppku.ed....o edu. cn).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 (input- dependent) 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 lack of rigorous ways to characterize the complexity of frames, since existing frames 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 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 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 practical yet principled measure for the complexity of frames. Canonicalization is 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 canomicalization C is to map all inputs that are equivalent under group G' to the same canonical form C(X). With the canonical input C(X), any (non-invariant) base neural network e will give a G-invariant mapping. We show that for 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 practical principles for quantifying the complexity and expressiveness of different frames.
set of theoretical conditions and
To illustrate the benefits of this canonicalization framework, we focus on the symmetries of eigenvec- tors (sign and basis group), which covers 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 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
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- for distinguishing non-isomorphic graphs. We also show that permutation-equivane equivariant OAP canonicalizes more eigenvectors than previous methods, resulting 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 9 E G and X E X. we have f(g X) = f()). Similarly, we say f is equivariant to G (or G-equivariant) if for all g E G and X E X we have f(g- X) = g f(X). We treat invariance as a special case of equivariance by letting G act on ) as the identity transformation. Existing research has developed neural networks with specific equivariance properties, such as permutation invariancee/euiivaiiane [70, 53], rotation mvvarianceequiivariance [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 Il- Il. and G be group. The elements y E G act on vectors in V. W with the group's 's representations Pr: G - GL.(V) and P2: G + GW), 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 9 E G such that u == (g)v For each imput X, we denote its orbit or equivalence class by Vo(X) (g) X g E G). and its automorphism group as Gx {g E G
2.1
Averaging Methods
Given network Φ: V + W. the naive way achieve invariance is through group averaging:
1 fGA(X) = GG| E (
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 subset of the group on an input X, f.e., a frame F(X) C G that maintains G-equivariance: F(pi (g) = gF(()= fgh h E F(X)). If an equivariant frame F is easy to compute, and its cardinality [(X) is not too large, then the following frame averaging scheme
SFA FFA F,0)
[F(X) ) (p1(9)
(1)
also provides the required function symmetrization. 4PA is G-invariant, and universally approximates G-invariant functions that approximable by é. Equivariance can be achieved similarly by multi- plying (g) with each term. Puny et al. [45] also proposed variant called invariant frame averaging by averaging over the cosets F(X)/Gx achieve invariance. Since there no established way to find the representatives of F(X)/Gx. they adopt uniform sampling from F(X) to approximate PFA. 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 p2 (e(h()))e ( (((x)))1x) X)) is equivariant and universal. The canonicalization h can be seen frame whose output has size 1. However, such 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.
2.2 Symmetries of Eigenvectors
Denote the Laplacian matrix of graph L= = Laplacian Positional Encoding (LapPE) uses the eigenvectors of 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 unit-norm eigenvector ux; corresponding eigenvalue X; the sign flipped -ux is also unit-norm eigenvector of the same eigenvalue. The second one, termed basis ambiguity. captures that eigenvalues with multiplicity degree d4 can have any orthogonal basis in its eigenspace as valid cigenvectors. 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.
A. where Á is the normalized adjacency matrix.
3 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.
3

---

3.1 A Reduction from Frames to Canonicalizations
Frame averaging reduces the number of forward passes in the averaging step compared with group averaging. However, major obstacle in analyzing the complexity of frames are the automorphisms of the input: Gx = {g G p1 (g) compute. For instance, consider defining g frame of 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.
X which can be exponentially large and intractable to
In this work, we propose an alternative view design frames that overcome the difficulties above. For each X E V, instead of averaging over the group elements as in FA (Eq. 1), one can directly average over the outpur elements of the transformations, which is not affected by the complexity of automorphisms since all automorphisms in Gx 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, the classic literature, this problem is known canonicalization, that achieves invariance by mapping inputs in the same equivalence class to the same canonical form. Formally, we define canonicalization as set- valued function C: V + 22, such that it is G-invariant: (()) = C(X), AX E V.g E 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) C Va(X) (X) for all X E V. With a canonical form, one can instead perform canonical averaging (CA) over C(X) obtain invariant representations:
PCA (X:C,),
[c(X) Σ Xxoexx)) ((Xo).
(2)
The following theorem establishes the equivalence between canonicalizations and frames.
Theorem 3.1. For any frame F there exists orbit canonicalization Cy s.t. for all X E VVg.E. and backbone o, we have FFA (X; F Φ) = &CA (X;C=, Φ) and
(x)(X) [(X)I/IGx| S |F(X)--
In turn, for any orbit canonicalization C there exists a frame Fe s.t. for all E V, g E G. and backbone o, we have &ca (X;C, Ø) 4FA (X; ;FFFF. Fc, Φ) and
[Fe(X) |Gxl (C(X) 2 (C(X)).
Theorem 3.1 reveals that frames and canonicalizations have a fundamental equivalence. In other words, frame is built upon canonicalization, and a canonicalization induces frame. Henceforth, we can reduce the difficult problem of designing (equivariant) frames to designing canonicalizations This simple change of perspective also allows us have 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/canonicalizztion design.
3.2 Theoretical Properties of Canonicalization: Universality, Optimality, and Canonicalizability
Here, we examine the thcoretical 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 universal if for any G-invariant function f: V W. there exists a well-defined function Φ: 2 + W such that f(X) @(C(X)) for all X E V. The following theorem shows that canonicalization universal iff corresponds to an orbit canonicalization.
Theorem 3.2. A canonicalization C is universal iff there exists orbit canonicalization C. and an injective mapping g: 2 > 2 such that g()()) = (X), VX V.
'e can similarly achieve (relaxed) equivariance [26] by letting the canonicalization output an additional canonizing action go with p1 (go) X Xo. and multiplying pa (go) each term.

---

For formal analysis of efficiency, we refer to [c(X) as the complexity of a canonicalization on X V. A canonicalization C superior another canonicalization C' it has smaller complexity on all elements: [c(x) < (x)( VX E 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, &C universal in the sense that it can approximate any continuous G-invariant function f: V W up to arbitrary precision.
The canonicalization size (x)) may differ for different inputs. In the most ideal case, an input X admits single canonical form with [C(X)] 1, which we call X canonicalizable element. Formally, an element X is canonicalizable if there exists an orbit canonicalization C such that [C(X) Otherwise, we call it uncanonicalizable, which may happen under additional constraints on the canonicalization. For example, one cannot determine a canonical sign for [-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 uncanoni- calizable inputs when additional constraints are imposed, a feature absent in existing literature on frames. 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 open problem in the literature [33, 32]. Canonicalizability 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.
3.3 Reducing dign-invariant Networks to Canonicalization
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 the network f: paxk + Rd on cigenvectors U1..... as
f(u ux) p(((())) + po(-u,)l
where @ and p are unrestricted neural networks and [ denotes concatenation of vectors. Ma et al. [36] instead achieved sign invariance on canonicalizable input with
fuu....., ux) (00:0=((MMAA ((MM)(..)))
where MAP denotes their canonicalization algorithm MAP, which leverages the sign-invariant and sermuuation-equivariant projection operator find canonical sign. Empirically, the two approaches attain comparuble performance in practice. Mcanwhile. MAP enjoys better computational efficiency because it only requires input pre-pros preppooesssig while SignNet requires two-branch encoding. Although the two algorithms seem rather different, we prove that any permutation-equive equivariiun 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 - Rrnddous is permutation equivariant and sign invariant iff there exists a permutation equivariant (w.r.t. its first imput) function oz TR x {0, 1} + Rax xdou such that
h(u) = =0 @(MAP+ (w).
R
where MAP MAP++(u) MAP(u), if u is canonicalizable, and 1 E (0,1) indicates whether u [/u), is canonicalizable. Here |u] denotes element-wise absolute value.
otherwise,
Theorem 3.4 indicates that any sign invariant and permutation equivariant function on a single eigenvector can be reduced to 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 cigenvector alone (as in SignNet) will take their absolute values (Theorem 3.4).
5

---

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 special case of first-order BasisNet with multiplicity d = 1. The universality of SignNet has been an open problem in the literature [33, 32] and we show that reduction to the canonicalization perspective can provide a fundamental solution to such problems. Concretely, we also construct two non- -somoosoo graphs that SignNet fails to distinguish in Appendix E.5.
Corollary 3.5. SignNet and BasisNet with first-order permutation equivariant & [37] cannot univer- sally approximate all -etiiiattiio-eivvriiannn and gagn/basii-invariinn function
4 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 eigenvectors U E R= that is invariant to sign/basis transformations, (possibly) equivariant to permutation transformations, and outputs a set of eigenvectors U E Raxd in the same eigenspace U. We consider two settings: without (Section 4. and with (Section 4.2) permutation equivariance, corresponding to different problem scenarios.
4.1 Optimal Canonicalization without Permutation
First, consider the case when do not need 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], elc.
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.
Algorithm 1 Canonicalization for eliminating sign ambiguity of eigenvectors
Require: The eigenvector u E R
Ensure: The canonical form u" of u
Let be the smallest index such that u; + 0
u² +- if
0, u² + -u otherwise
Basis Invariance. Inspired by MAP-basis [36], we design a more general and powerful canonical- ization based on the -chmidt Orthogonalization of projection vectors, named orthogonalized axis projection (OAP). Specifically, let U E R be eigenvectors in d dimensional eigenspace, and let 3 UUT be the projection matrix onto the eigenspace span(U) Denote e1, ....... C22 as the standard axis vectors of RR", that is, has at the i-th entry and 0 at the other entries. The following Algorithm eliminates basis ambiguities all eigenvectors.
Algorithm 2 OAP Canonicalization for eliminating basis ambiguity of eigenvectors
Require: The eigenvectors U E Raxd Ensure: The canonical form U* U
Let i < ... < is be the smallest indices s.t. |e || > 0 and Pei, are linearly independent,
j <
U + GS Per)) where GS denotes Gram-Schmidt Orthogonalization
Intuitively, Algorithm 2 finds set of standard basis vectors with the smallest indices such that their projection the eigenspace is still basis. We note that the indices i,,..., can be found by iteratively checking whether each Pe, is non-zero and linearly independent with the already-found
'It is still possible to achieve universality with higher-order networks [33], but they are computationally intractable in practice [37, 49].

---

projection vectors (2 = .......). n),, and adding them if they satisfy these conditions. This can be done in O(n²) time (the same as eigendecomposition). The following theorem guarantees that we can always find such indices.
Theorem 4.1. Given a set of eigeevecctors U RRxxd, let P UU denote the projection matrix of the eigenspace. Let El....,en denote the standard basis vectors. Then, there exists indices 1 S 11
id n, such that for all S J S we have || Peiil || 0, and the vectors Pe Pis are linearty independent.
Optimality. We show that Algorithm and 2 are optimal, and can canonicalize all cigenvectors. Theorem 4.2. Algorithm I an optimal orbit canonicalization for all eigenvectors u E R under sign ambiguity. Algorithm 2 is optimal orbit canonicalization for all eigenveciors U E <Raxd 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-framm methods.
4.2 Better Canonicalization with Permutation
In this section, 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 uncunonicalizable inputs with the following MAP-full canonicalization
MMAP(u). if u is canonicalizable, [u,--u) otherwise.
(u)
Since 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 Thus, MAP-full optimal.
Basis Invariance. Contrary to the sign case, basis invariance harder to obtain and MAP-basis proposed by Ma et al. [36] is known to be not optimal. Here, propose sermutation-equiiariaa basis canonicalization that is provably superior to MAP-basis. Notice that in OAP (Algorithm 2), the way that we construct smallest indices é ............ da 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-equivarian hash function rank axis projections:
hash(Pu, PPi It }is)) i 1.......
where p: Pe. According to the number distinet values in {a,} (denoted as k), we divide all standard basis vectors {e,} into & disjoint groups B,, in descending order of ag Then we define summary vector æ; for each group B, as æ; = ΣeyeB, ej + c, where e a tunable constant. this way, we arrive at a permutation-equie eequivarian version of OAP for LapPE in Algorithm 3. The summary vectors } } are now permutation equivariant (Appendix B. in contrast to {ei, } in Algorithm 2.
Algorithm 3 OAP Canonicalization for eliminating basis ambiguity of Laplacian positional encoding
Require: The Laplacian eigenvectors U Raxd
Ensure: The canonical form U of U
Let i < < is be the smallest indices |1 0 and Pz. are linearly independent,
< j < d
U GS( Px Pwi.). where GS denotes Gram-Schmidt Orthogonalization
In contrast Algorithm 2, the indices .j...., is may not always exist. The existence and values of these indices can be determined in (n)²d)) time (c.f., Appendix B.3).
4.3 OAP as a Unified Canonicalization for Eigenvectors
Another interesting aspect of OAP is that with flexible choice of hashing values and indices ij. OAP can serve as unified framework that encompasses many existing canonicalization algorithms for cigenvectors (as well as graphs).
7

---

First, it is easy to see that the sign canonicalizations (Algorithm and MiP-sign) are special cases of their basis versions with d I. For basis canonicalization, there are two existing methods. One is MAP-basis [36] which also utilizes axis projection but different construction of basis. Another is proposed in Puny al. [45] as a way to construct frames for graphs which, according to Theorem 3.1, corresponds to 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 special cases of OAP with degenerated hash functions.
Theorem 4.3. Let Ot; (i 1i=11 1.....,,) be the outputs of the hash function in the OAP algorithm defined in Equation 4, and let i; 1i.1.....d be the indices found in Algorithm 3. Then, the MAP algorithm [36] is equivalent to the OAP algorithm that takes a; = Llll for all 1 i S n. and i, = for all 1 S j S d. The FA-lap algorithm [45] is equivalen to the OAP algorithm that takes Os Pi all S S 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 result, OAP can canonicalize more eigenvectors and is strictly superior to MAP and FA-lap. There no superiority between MAP and FA-lap. It remains an open problem whether the jermutation-equiiariian OAP (Algorithm 3) is optimal.
Similarly, these canonicalizations can be adapted to canonicalize graphs (which we call MAP-graph, FA-graph, OAP- -APggraph), 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- FA-graph.
5 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.
5.1 Expressive Power and Frame Size
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 al. [7]. As baselines, we use GCN [67], GAT
Table 1: Accuracy on EXP.
Model
Accuracy
GCN
50%
[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 IA-GINIID 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 Table 1. All MP-GNN- 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.
GAT
50%
GIN
50%
ChebNet
82%
FA-GIN+ID
100%
CA-GIN+ID 100%
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 Table 2, OAP-graph more efficient than FA-graph, verifying Corollary 4.4. Since [C(X)] < [F()), CA is more efficient than FA, validating Theorem 1.1. We note that although the numbers are still very large in Table 2 and we still need sampling, a smaller frame/canonicalizatoo size would lead to faster convergence rate towards the true average. This is proven in Appendix C.
5.2 Graph Regression and Classification
We evaluate OAP ZINC [24]. We measure the ratio of non-canonicalizable eigenvectors among all eigenvectors by FA-lap, MAP, and OAP. As shown in Table 3, they are equivalent in addressing sign
'Hrre "non-canonicalizable" means that the canonicalization algorithm fails canonicalize the eigenvectors.
8

---

Table The average frame size (F) and canonicalization size (C) on ExP with two canonicalization algorithms: FA FA-graph and OAP graph.
Method
Avg F(X)]
Avg c(X)
F/C Ratio
FA-graph
2.10 x 1021
5.84 x 1021
360x
OAP-graph
2.55 x 1022
7.57 x 1019
337X
FA/OAP Ratio
82X
77x
ambiguity, while OAP has the least ratio of non-canonicalizable eigenvectors under basis ambiguity, aligning with Corollary 4.4.
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, and 6.
Table Results on ZINC with 500K parameter budget. All scores are averaged over 4 runs with 4 different seeds.
Model
PE
k
#Param
MSE 4
GIN GINE
ID+
0
495K
0.613 0.023
Table 3: Ratio of non-canonicalizable eigenvec-
ID
0
495K
0,546 + 0.048
tors on ZINC.
None
0
S04K
0,251 + 0.009
Canonicalization
FA-lap
MAP
OAP
LapPE RS
8
505K
0,202 + 0,006
SignNet
495K
0.121 1 0.005
Sign Basis
5,4%
5,4%
5,4%
GateGGCN
MAP
8
486K
0,120 + 0.005
OAP
473K
0.0006
2.2%
1.0%
0.2%
OAP LSPE
491K 8
0.098 0.0009
None
0
369K
0,141 + 0,004
LapPE RS
8
474K
0,132 + 0.010
SignNet
8
476K
0,105 0.007
PNA
MAP
8
462K
0,101 1 0.005
OAP
0.0008
OAP LSPE
8
549K
0,095 + 0.004
Table 5: Results on MOLTOX21. All scores are averaged over runs with 4 different seeds.
Table 6: Results on MOLPCBA. All scores are averaged over 4 runs with different seeds.
Model
PE
&
#parum
ROCAUC
Model
PE
#puram
AP
None
0
1004K
0.772 + 0.006
None
1008K
0.262 0.001
LapPE + RS
3
1004K
0.774 +: 0.007
LapPE RS
3
1009K
0.266 0.002
GatedGCN
SignNet*
1367K
0.773 + 0.003
GatedGCN
SignNett
3
2415K
0.260 = 0.002
MAP
1505K
0.784 = 0.005
MAP
2658K
0.268 0.002
OAP
1542K
0.787 + 0.005
OAP
3
2658K
0.270 0.002
None
O
5245K
0.755 +: 0.008
None
0
6551K
0.279 = 0.003
LapPE RS
16
2453K
0.756 : 0.009
LapPE:
PNA
SignNet*
16
1754K
0.750 + 0.009
PNA
SignNet*
16
4493K
0OM
MAP
16
1951K
0.761 +: 0.002
MAP
16
4612K
0.281 # 0.003
OAP
16
1950K
0.768 + 0.002
OAP
16
4612K
0.279 0.002
In Table 4, we observe that FA achieves the lowest performance since it breaks permutation equiv- ariance. The results presented in Tables 4, and 6 demonstrate that incorporating LapPE leads to improved performance across nearly all cases compared 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 L.SP enhances the performance of OAP across all models.

---

We compare the time and memory of canonicalization methods with their non-FA backbone on ZINC Table Using canonicalization algorithms only increases which is negligible compared to the training time. On the other hand, the two-branch architecture of SignNet increases the training time and memory.
the pre-prcesssing time of the backbone.
Table 7: Comparison of time and memory of canonicalization methods with their non-FA backbone on ZINC. For the backbone models, node features are first concatenated with positional encodings and fed to 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 two-branch architecture. For models with MAP and OAP, the positional encodings are canonicalized before fed to the positional encoding network.
Model
Pre- Pre-processing time
Training time
Total time
Memory
GatedGCN backbone
3h26min
3h26min
1860MiB
GatedGCN + SignNet
30.03s
4h13min
4h13min
2124MiB
GatedGCN + MAP
133.67s
3h20min
3h22min
1850MiB
GatedGCN + OAP
186.38s
3h25min
3h28min
1860MiB
PNA backbone
16h31min
16h31mih
2242MiB
PNA + SignNet
30.03s
18h1min
18h1min
2570MiB
PNA MAP
133.67s
16h47min
16h49min
2244MiB
PNA + OAP
186.38s
14h54min
14h57min
2312Mib
Conclusion and Discussion
In this paper, illustrated canonicalization useful view of frames. From this perspective, 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 canon- icalization under permutation equivariance. 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.
Acknowledgement
Yisen Wang was supported by National Key R&D Program China (2022ZD1160300), National Nat- ural Science Foundation of China (92370129, 62376010), and Beijing Nova Program (20230483344, 20240484642). Derek Lim was supported by an NSF Graduate Fellowship. Yifei Wang and Stefanie Jegelka were supported by NSF AI Institute TILOS (NSF CCF-2112666 NSF award 2134108, and the Alexander von Humboldt Foundation.
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewiez. The Surprising Power of Graph Neural Networks with Random Node Initialization. In IJCAI, 2021.
[2] Rohith Agaram, Shaurya Dewan, Rahul Sajnani, Adrien Poulenard, Madhava Krishna, and Srinath Sridhar. Canonical Fields: Self-Supervised Learning of Cose-Canonicalized Neural Fields. arXiv preprint arXiv:22/2.02443 2022.
[3] Fleonora Andreotti, Dominik Edelmann, Nicola Guglielmi, and Christian Lubich. Measuring the stability of spectral clustering. Linear Algebra and its Applications, 610:673-697, 2021.
[4] Nima Arkani-Hann Hamed, Yuntao Bai, and Thomas Lam. Positive geometries and canonical forms. Journal of High Energy Physies, 2017 2017.
10

---

[5] László Babai and Eugene M Luks. Canonical labeling of graphs. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 171-183, 1983.
[6] László Babai, D Yu Grigoryev, and David M Mount. Isomorphism of Graphs with Bounded Figenvalue Multiplicity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 310-324, 1982.
[7] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the Limits of Message Passing Graph Neural Networks. In ICML, 2021.
[8] Rémi Bardenet and Odalric-Ambrym Maillard. Concentration inequalities for sampling without replacement. Bernoulli, 21(3):1311-1385 2015.
(9] Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNets. arXiv preprint 17X1v:1711.07553 2017.
[10] Rasmus Bro, Evrim Acar, and Tamara G Kolda. Resolving the Sign Ambiguity in the Singular Value Decomposition. Journal of Chemometrics: A Journal of the Chemometrics Society, 22(2): 135-140, 2008
[11] Ward Cheney and David Kincaid. Linear Algebra: Theory and Applications. The Australian Mathematical Society, 110:544-550 550, 2009.
[12] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pictro Liō, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. In NeurIPS, 2020.
[13] Alexandre Agm Duval, Victor Schmidt, Alex Hernández-Garcaá, Santiago Miret, Fragkiskos D Malliaros, Yoshua Bengio, and David Rolnick. FAENet: Frame Averaging Equivariant GNN for Materials Modeling. In ICML, 2023.
[14] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. arXiv preprint arXiv:2003.00982, 2020.
[15] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph Neural Networks with Learnable Structural and Positional Representations. In ICLR, 2022.
[16] Nadav Dym, Hannah Lawrence, and Jonathan W Siegel. Equivariant Frames and the Impossi- bility of Continuous Canonicalization. In ICML, 2024.
[17] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries. In NeurIPS, 2022.
[18] Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. SE(3)-Transformer:: 3D Roto-Trann TisoosTrnslttion Equivariant Attention Networks. In NeurlPS, 2020.
[19] Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, pages 13-30, 1963.
[20] Kurt Hornik, Maxwell Stincheombe, and Halbert White. Multilayer Feedforward Networks Universal Approximators. Neural Networks, 2(5):359-366, 1989.
[21] W Hu, B Liu, J Gomes, M Zitnik, P Liang, V Pande, and Leskovec. Strategies for Pre-training Graph Neural Networks. In ICLR, 2020.
[22] Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.0066) 2020.
[23] Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the Stability of Expressive Positional Encodings for Graph Neural Networks. arXiv preprint ar
2023.
11

---

[24] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. ZINC: A Free Tool Discover Chemistry for Biology. Journal of chemical information and modeling, 52(7):1757-1768, 2012.
[25] Aaron Jones, Joann Kuchera-Mon Morin, and Theodore Kim. Seeing and Hearing the Eigenvectors of a Fluid. In Proceedings of Bridges 2017: Mathematics. Art, Music, Architecture, Education, Culture, pages 305-312. 2017.
[26] Sékou-Oumar Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravan- bakhsh. Equivariance with Learned Canonicalization Functions. In NeurlPS Workshop on Symmetry and Geometry in Neural Representattinns 2022.
[27] Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena. and Chinmay Hegde. On the Compu- tational Complexity of Self-Attention. In International Conference Algorithmic Learning Theory, 2023.
[28] Thomas Kipf, Ethan Fetaya, Kuan-Chich Wang, Max Welling, and Richard Zemel. Neural Relational Inference for Interacting Systems. In ICML, 2018
[29] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létorrnaa, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NeurlPS, 2021.
[30] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet Classification with Deep Convolutional Neural Networks. In NeurlPS, 2012.
[31] Rongjie Lai and Hongkai Zhao. Multiscale Nonrigid Point Cloud Registration Using Rotation- Invariant Sriced-Wasserstein Distance via Suplace-Beltrant Eigenmap. SIAM Journal on Imaging Sciences, 10(2):449-483, 2017.
[32] Derek Lim, Joshua Robinson, Stefanie Jegelka, and Haggai Maron. Expressive Sign Equivariant Networks for Spectral Geometric Learning. In NeurIPS, 2023.
[33] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and Basis Invariant Networks for Spectral Graph Representation Learning. In ICLR, 2023.
[34] Yuchao Lin, Jacob Helwig, Shurui Gui, and Shuiwang Ji. Equivariance via Minimal Frame Averaging for More Symmetries and Efficiency. In ICML, 2024.
[35] Jiangyan Ma, Emmanuel Bengio, Yoshua Bengio, and Dinghuai Zhang. Baking Symmetry into GFlowNets. In NeurlPS Al for Science: from Theory to Practice, 2023.
[36] Jiangyan Ma. Yifei Wang, and Yisen Wang. Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding. In NeurlPS, 2023.
[37] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. ICML, 2019.
[38] Karolis Martinkus, Jan Ludwiczak, Wei-Ching Liang, Julien Lafrance- Vanasse, Isidro Hotzel, Arvind Rajpal, Yan Wu, Kyunghyun Cho, Richard Bonneau, Vladimir Gligorijevic, al. AbDiffuser: Full-Atom Generation of in-vitro Functioning Antibodies. In NewrIPS, 2024.
[39] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. In AAAI, 2019.
[40] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational Pooling for Graph Representations, In ICML, 2019.
[41] Richard S Palais and Chuu-Lian Temg. A General Theory of Canonical Forms. In Transactions of the American Mathematical Society, 1987.
[42] Lucas Parra and Paul Sajda. Blind Source Separation via Generalized Figenvalue Decomposition. The Journal of Machine Learning Research, 4:1261-1269, 2003.
12

---

[43] Saro Passaro and C Lawrence Zitnick. Reducing SO(3) Convolutions to SO(2) for Efficient Equivariant GNNs. ICML, 2023.
[44] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. PyTorch: An Imperative Style, Pelf-PPerformance Deep Learning Library. In NeurIPS, 2019.
[45] Omri Puny, Matan Atzmon, Heli Ben-Hamu, Ishan Misra, Aditya Grover, Edward J Smith, and Yaron Lipman. Frame Averaging for Invariant and Equivariant Network Design. In ICLR, 2022.
[46] Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman. Equivariant Polyno- mials for Graph Neural Networks. In ICML, 2023.
[47] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. PointNet: Deep Learning Point Sets for 3D Classification and Segmentation. In CVPR, 2017.
[48] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space. In NeurIPS, 2017.
[49] Siamak Ravanbakhsh. Universal Equivariant Multilayer Perceptrons. In ICML, 2020.
[50] Joost Rommes. Modal Approximation and Computation of Dominant Poles. In Model Order Reduction: Theory, Research Aspects and Applications, pages 177-193. Springer, 2008.
[51] Rahul Sajnani, Adrien Poulenard, Jivitesh Jain, Radhika Dua, Leonidas Guibas, and Srinath Sridhar. ConDor: Self-Supervised Canonicalization of 3D Pose for Partial Shapes. In CVPR, 2022.
[52] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
[53] Nimrod Segol and Yaron Lipman. On Universal Equivariant Set Networks. In ICLR, 2019.
[54] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research, 12, 2011.
[55] Jure Sokolie, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization error of invariant classifiers. In Artificial Intelligence and Statistics, pages 1094-1103. PMLR, 2017.
[56] Weiwei Sun, Andrea Tagliasacchi. Boyang Deng. Sara Sabour, Soroosh Yazdani, Geoffrey Hinton, and Kwang Moo Yi. Canonical Capsules: Self-Supervised Capsules in Canonical Pose. In NeurlPS, 2021.
[57] Behrooz Tahmascbi and Stefanie Jegelka. The Exact Sample Complexity Gain from Invariances for Kernel Regression, In NeurIPS, 2023.
(58) Edric Tam and David Dunson. Multiscale Graph Comparison via the Embedded Laplacian Discrepancy. arXiv preprint arXiv:2201.12064 2022.
[59] Shanshan Tang, Bo Li, and Haijun Yu. ChebNet: Efficient and Stable Constructions of Deep Neural Networks with Rectified Power Units using Chebyshev Approximations. arXiv preprint 1rXiv:19/1.05466 2019.
[60] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation- and translation-equivarinn neural networks for 3D point clouds. arXiv preprint / 082 2018
[61] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018
[62] Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks. In ICLR, 2022.
13

---

[63] Yifei Wang, Zhengyang Geng, Feng Jiang. Chuming Li, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Residual relaxation for multi-view representation learning, NeurIPS, 2021.
[64] Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey, Symmetric cross entropy for robust learning with noisy labels. In ICCV, 2019.
[65] Boris Weisfeiler and Andrei Leman. The reduction of graph canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
[66] Yair Weiss. Segmentation using eigenvectors: a unifying view. In ICCV, 1999.
[67] Max Welling and Thomas N Kipf. Semi- Somi-Supervised Classification with Graph Convolutional Networks. In ICLR, 2017.
[68] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In ICLR, 2019,
[69] Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, 55(1):007447,, 2022.
[70] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep Sets. In NeurlPS, 2017.
[71] Bohang Zhang, Guhao Feng. Yiheng Du Di He, and Liwei Wang. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehmae Tests. In ICML, 2023.
[72] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the Expressive Power of GNNs via Graph Biconnectivity. In ICLR, 2023.
[73] Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond Weisfeiler- Lehman: A Quantitative Framework for GNN Expressiveness. In ICLR, 2024.
[74] Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the Expressive Power of Spectral Invariant Graph Neural Networks. In ICMI., 2024.
[75] Yan Zhang, David W Zhang. Simon Lacoste- Julien, Gertjan Burghouts, and Cees GM Snoek. Multiset-Equivariiat Set Prediction with Approximate Implicit Differentiation. In ICLR, 2021.
14

---

Appendix
Table of Contents
A Advantages of the canonicalization perspective
16
B Implementation and verification of MAP
17
B.1 The Gram Gram-Schmine Schmidt process
17
Complete pseudo-code of Algorithm
B.3 Complete pscudo-code of Algorithm 3
B.4 Verifying the correctness of Algorithm
20
B.5 Verifying the correctness of Algorithm
21
C Concentration inequality for drawing without replacement
22
PCA-frame methods for orthogonal equivariance
23
PCA-frame methods
23
D.2 Experiments the n-body problem
23
E
Proofs
24
E.1 Proof of Theorem 3.1
24
E.2 Proof of Theorem 3.2
25
E.3 Proof of Theorem 3.3
................................
26
Proof Theorem
26
Proof Corollary 3.5
28
E.6 Proof of Theorem 4.1
30
E.7 Proof of Theorem 4.2
30
E.8
Proof of Theorem 4.3 and Corollary 4.4
31
F Augmentations of the OAP algorithm
32
El
Incorporating node features
32
Incorporating information from other .....e..........................
F3
Learnable canonicalization
................................
33
G Related work
33
G.1 Equivariant learning
33
G.2 Canonicalization
33
G.3 Canonical forms
34
G.4 Sign invariance
34
G.5 Basis invariance
35
H Dataset details
35
Hyper-parameter settings
35
L.1 ExP experiment
36
1.2
n--odyy experiment
36
L.3 ZINC experiment
36
1.4 OGBG experiment.
36
15

---

A Advantages of the canonicalization perspective
In this paper, we introduced canonicalization new perspective to learning with symmetry. We demonstrated how shifting from frames to canonicalization could offer valuable new perspectives, enabling us 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 automor- phism, like graphs. such cases, the automorphism group of an input could grow expo- nentially, consequently expanding the frame size exponentially 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 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, permutation might yield the sorted node IDs: 0, 1, 4, 6, 3, 5, 7. Although the frame size for this graph is calculated as 5! x 2! x 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
7
8
Figure 1: An example where the frame size exceeds the canonicalization by factor of 480.
2. Frames must adhere to G-equivariance: F(P1(g)X) gF(X), posing stringent re- quirement. Consequently, constructing frames becomes challenging. While one approach involves constructing canonicalization first and then inducing its corresponding frame, preferable option 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 izable inputs, offering intriguing theoretical insights. Sign invariance serves as a notable example. According to Ma et al. [36]. an eigenvector E Rº is uncanonicalizable with respect to sign iff there exists permutation matrix P such that u = Puu. 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.
frame lies in the presence of uncanonical-
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 maintained. 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, observed in the input space.
the trilemma of invariance, equivariance, and
16

---

B Implementation and verification of MAP
B.1 The Gram-Schmidt process
The Gram-Schmidt process is heavily used in our canonicalization algorithms; we discuss it in this subsection. The Gram-Schmidt process is a method constructing an orthonormal basis from a set of vectors in inner product space, most commonly the Euclidean space R" equipped with the standard inner product. Specifically, the of vectors {#1 .2,..., Fm in an inner product space V with m n, and generates orthogonal set of vectors {1)) ,0,,,0,--00 .2,...; Um that spans the same m-dimensional subspace of IR",, where
process takes a finite, linearly independent set
31,
2 V1
02 22
|1112 1|
U1
(Iz. 01)
(x3. v2)
03 33
02 /11
01
U2 ||
1-1 (ar;; Tx)
05 2;
||1
k=
m
(m Tk)
1m Fm
2k-
2k
The Cram-Schmidt process can be implemented PyTorch [44] using QR decomposition.
def orthogonalize (U: Tensor) -> Tensor: (U) (U)
Q, R torch. linalg qr
S torch sign (torch.diap. return Q
If the input matrix E gnxd has full rank (in our case does because U is matrix of cigenvectors), and if we require the diagonal elements of R to be positive, then Q and R are unique, and (column vectors of) Q Raxd gives the -chm-it 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 permutation equivariant and orthogonally equivariant.
Theorem B.1. The Gran-Schmidi process is permulation equivariant and orthogonally equivariant.
Proof. We first prove the permutation equivariance of GS by induction. Let P E R be an arbitrary permutation matrix. Let (æ1,, a'...... ) be defined by a; Px, for 1 < m, and let (vi, v/...., v',) } be the orthogonal basis generated from (a1, xy,..... am)) by GS. Clearly of = x Pæi is permutation equivariant. Suppose vi vi...., 1/-1 all permutation equivariant, then
(at,, j=1 10y1
(Par, Pvş) Pu, Pvk. ||ا
1/4 Z'e
Σ
o/ P
where the last equality holds because the inner product operator is invariant under permutation. Thus 0g 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 Rax be an arbitrary orthogonal matrix. (a', atyy ... .²h be defined by a! = Qa: for 1 S S m, and let (w(, v/...., e,,) be the orthogonal basis generated from {Ø 22.... ....... 2 z Clearly oi is orthogonally equivariant.
17

---

Suppose vi..... 0 are all orthogonally equivariant, then
R-1
(a U/) |o,l v/ Q
(Qx). Quy) |0,,12
b/4 2/K
Qu, Qux
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 set of values a; hash(p:. (P,s) j for 1..... n, where Px; is the projection of standard basis vectors onto the eigenspace V. Suppose there are distinct values in {.ra), i.e, [a;]] = Then according to the values of o; we divided the standard basis vectors {e:} into & disjoint groups B; (arranged in descending order of the values of ag), and defined a summary vector æ; for each group B, as the sum of standard basis vectors that group. Consider the projections of these k summary vectors, Px, Let i 12 smallest indices such that || I., > O and Pz, are linearly independent, S j S d. In the final step, applied the Gram-Schmidt process to Piir... ...... Di, to obtain the resulting canonical form. These steps can be summarized as follows.
< ia be the
1. Compute a; = hash(pu, Hpi )1:)) ssisn.
2. Define summary vectors æ; Σ e,, where the summands e, share the same aj value, and the summary vectors are arranged in descending order of these values.
3. Find the smallest indices i <.. is such that ,,, O and Pxi, are linearly independent, و d.
4. Apply GS to ( (Pai,..... Pai,) to obtain the final canonical form.
In this algorithm we mainly make use 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 permutation equivariant.
Theorem B.2. The OAP canonicalization in Algorithm 3 is permutation equivariant.
Proof. Consider the canonical forms U and U PU, where is an arbitrary permutation matrix. We analyze each step of this algorithm. The permutation P acts on the eigenspace by go' PppT well as on the standard basis vectors by e Pe:-
1. In step 1, since each projection p/ 3e = PPppTe: = Pp, is permutation equivariant, the value vector (a1....,,a, an) is also permutation equivariant.
2. In step 2, we summed vectors e; with the same corresponding a, to get the summary vectors, while the summary vectors themselves are arranged in descending order of the corresponding 0g If we arrange the entries a in descending order as
0x 2 042
then the indices vector = (i.....,,,,) would be "almost" permutation equivariant, except that indices corresponding to equal entries could have any ordering. However, summed up all e; with equal corresponding o;, the summary vectors æ; would be exactly permutation equivariant for < k, in the sense that a P(Ee, EB, eg) P
3. The projections Pæ., are themselves permutation equivariant. Since the norm operator || and the linear independence of vectors are not affected by permutation, the indices
11 i 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.
18

---

B.2 Complete pseudo-code of Algorithm 2
In Algorithm we proposed the OAP-eig canonicalization to address the basis ambiguity of eigen- vectors without permutation equivariance. The complete pseudo-code of OAP-eig, along with detailed time complexity analysis, is shown Algorithm 4.
Algorithm 4 OAP-eig canonicalization for eliminating basis ambiguity without permutation equivari- ance
Require: The eigenvectors U Raad
Ensure:
The canonical form U* of U
UU
O(n'd) complexity
U span f empty matrix of shape n. x 0
r r+0
D rank of Uspan
for
[ (oo(n complexity]i = 1, ,,...,,.
<- normalize( P:)
(n) complexity
||u||| < then
floating-pont errors are considered
continue
end
Unmp < USpan; u
if rank(UU (mp) + then
> u is linearly independent with U Uspan. O(nd²) complexity
U Uspan r
Uump
d then break
b found indices i
end if end if
end for
U GS(Uspan) return U
O(nd?) complexity
The overall time complexity of Algorithm is O(n2d)) Since in real-world datasets the value of usually small (Figure in Ma al. [36]), Algorithm more efficient than eigendecomposition itself whose time complexity is (n²)).
In the for loop of Algorithm 4, aim to find indices i1, ......, ,d such that 9e [1, 11 |> and P. are linearly independent for 1 I S d. We look for these indices in iterative fashion. The matrix U Uspan contains all the already-found indices. We initialize U Uspan to be empty matrix of shape n x O, and every time we find an index such that || > O and Pe is linearly independent with the already-found columns vectors of Uspan: have found a total of indices (denoted as r in Algorithm 4), we break out of the loop and return the Gram-Schmidt orthogonalization of U ppan- By the properties of GS, U is still
concatenate the normalized P. Uspan- Once
of orthonormal basis in the eigenspace. However, as we iterate through P Pe,,, Pe2,. P en, the algorithm is not permutation equivariant (the standard basis vectors { are permuted by permutations).
B.3 Complete pseudo-code of Algorithm
In Algorithm 3, we proposed the OAP-Iap 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(ndd)) which is also more efficient than eigende- composition itself. Although Algorithm 5 need to be applied to every eigenspace the graph, we note that the number of multiple cigenvalues (eigenvalues with multiplicity greater than I 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:)isiss into disjoint groups (B, ( To do that, we first calculate a set of values as, 1 S S n for each standard basis vector. Any set of permutation-equivarian of the algorithm, to ensure the algorithm canonicalizes as many eigenvectors as possible (i.e., the superiority of canonicalization), would like the values of a, have enough "distinguishabilit""
would guarantee the correctness
19

---

Algorithm 5 OAP-lap canonicalization for eliminating basis ambiguity with permutation equivariance
Require: The Laplacian eigenvectors U E R
Ensure:
The canonical form U of
3 -U
(n)2d) complexity
(hash( 10ash(991,1 (1 Bist),,.... hash ( Pn mn, 1 Wittn)
(n²) complexity
val, ind sort(a)
O log n) complexity
val t unique(val val)
b unique values in {a,), (n) complexity
+ -/eal]
if k then
break
impossible to find d indices
end
for
i
1, ..... do
(n) complexity D sum of standard basis vectors in group B; > the summary vector of group B;
2; - 2, endlly such that (ndd[ val[t]
2; - x; +c
end for
Uspan < empty matrix of shape n x 0
r+0
rank of Uspan
for i I..... do
O(n d²) complexity (n) complexity
u + normalize Px,)
if | < then
floating point errors considered
continue
end if
Unmp < (Uspan u
rank rank(Ummp) = r 1 then
D u is linearly independent with U Uspan O(ndP) complexity
U spaa Uump
r + +1
if r d then
b found indices i1, .1..... ,dd
break
endi if
end if
end for
U + GS(Uspan))
O(nd²) complexity
return U*
(i.e., the values of a; divide the standard basis vectors into more fine- fie-grained groups, in Babai et al. bash(99.. ff (. Bizz). We proved the
[6] this is called refinement). In Algorithm 5 we define permutation equivariance of such or Appendix B. and Appendix E we will prove that they are more fine-graid fine-grained than previous methods, such as a = Pa in Puny et al. [45] and = || in Ma et al. [36].
Once we have the values of ar we can divide }e,} into disjoint groups B; accordingly. Each value a corresponds
standard basis vector e,, Two standard basis vectors belong to the same group and only if their corresponding a; are equal, and different groups are arranged in descending order of the values of a; For each group, we define summary vector æ; 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 find the indices .,.... ... ig. except that the vectors (Ae,) hehsssn are substituted with P a; higigh Note that in contrast Algorithm 4, now these vectors are by construction.
B.4 Verifying the correctness of Algorithm
The correctness 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 E nnd the indices i,,..., ia can always be found; and that the whole algorithm is basis-invariant as desired. The verification program is shown in Algorithm 6. Let U E Raad be random orthonormal matrix representing the eigenvectors, and Q O(d) be random orthonormal matrix that rotates the eigenvectors in their corresponding eigenspace. We pass U and
20

---

UQ to Algorithm (denoted as canonicalize) and compare the results. If our algorithm is correct, U and UQ should produce identical outputs.
Algorithm 6 Verify the correctness of Algorithm 2
correct t- 0, total +- O
for i 1,2,..., trials do
f a random positive integer (greater than 1) random positive integer (less than n)
U + a random orthonormal matrix in Raxd
Up < canonicalize(
Q a random orthonormal matrix in Rdxdd
W < UQ
Wo & canonicalize( W)
correct + correct + if U - Wol <e
D test basis invariance
total total
end for print the values of correct and total
We conduct 1000 trials. The results are correct = lotal = 1000, showing the basis invariance of Algorithm 2. The function canonicalize will throw an error and terminate if the indices i1, ....... ,'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 also modify Algorithm 6 to verify the orthogonal equivariance of canonical averaging in the n--oddy 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 f- 0, total +- 0
for i 1,2,.... trials do
X + node features in the dataset, representing the inital location of particles
X, model(X)
Q <- random orthonormal matrix in Rdxd where d is the dimension of node features
< XQ
Wo < model(W)
correct + correct + if X Wol <
b test orthogonal equivariance
total t- total +1
end for
print the values of correct and total
B.5 Verifying the correctness of Algorithm 3
In this subsection we verify the correctness of Algorithm Here "correctness" refers to the permuta- tion equivariance and basis invariance of the canonicalization algorithm. The verification program is shown in Algorithm& Let E RRaxd random orthonormal matrix representing the Laplacian eigenvectors, P E Raxn 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 corre- sponding eigenspace. We pass U. PU, UQ, PUQ to Algorithm 3 (denoted as canonicalize) and compare the results. If our algorithm is correct, UQ should produce invariant outputs, while PU and PUQ should produce equivariant outputs.
We conduct 1000 trials. The results are p_correct = Q_ [__oorect- = p9_ hov_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 be uncanonicalizable [36] has more rigorous discussion this in Appendix H of their paper.
Ma et al.
21

---

Algorithm 8 Verify the correctness of Algorithm 3
p_correcl +- 0, q_correcl + 0, parcorvecl + 0, lotal t-
for 1,2,.... trials do
f a random positive integer (greater than 1)
f a random positive integer (less than n)
U < a random orthonormal matrix in Raxd
Un <- canonicalize (U)
P f- a random permutation matrix
V < PU
Vo canonicalize(V)
p_ e_correct + P_correet + 1 IPU Vol <
test permutation equivariance
Q < a random orthonormal matrix in Rddd
W t UQ
Wo < canonicalizo(WW (
9 correct <- correct if Uf - Wol <E
D test basis invariance
Y - PW
Yo canonicalize(()
pq_ pe_corret f- corceee if PUV Yol <
test both
lolal +- tolal +
end for print the values of p_correct, q_correct, porcer and total
C Concentration inequality for drawing without replacement
In the EXP experiment the frame or canonicalization size is very large (Table 2), 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 smaller framn/canonicallizatonn size will lead to faster convergence rate towards the true average. Thus, according to Table 2, CA more sample efficient than FA, and OAP more sample efficient than FA-graph.
Denote by F frame averaging scheme, and by C the canonicalization induced by F. Let (X) [ei (g) -1 X 1.g E 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=(X) multi-set, so if k group actions in F(X) result in the same graph when applied to X, then this graph is counted & times in V=(X). Let C(X) be the canonicalization of input X. Let ø be the backbone neural network. Sampling from Trame/canonicalization works as follows:
1. If the frame size F(X) is large, then the exact averaging [-X ExEF(X ( -x) is intractable. In this case, we randomly sample n graphs X1,.... X, from V>(X) and use the empirical average 1 En ((X;) as approximation to the true average.
2. Similarly, if the canonicalization size C(X) is large, then the exact averaging this case, we randomly sample n graphs X,...., X, from C(X) and use the empirical average D" Ein o(X,) as approxi- mation to the true average.
C[X Ex,ec(x) ((Xo) is intractable.
When we sample from Vx(X) or C(X), there are two approaches: drawing with replacement and drawing without replacement. However, well-known that drawing without replacement is preferable, as illustrated in the following theorem.
Theorem C.1 (Hoeffding [19]). Let X (x1,..., IN) be a finite population of N real points, X1...., Xn, denote a random sample without replacement from X' and Yı...., Y, denote a random sample with replacement from X. If : R P. is continuous and convex, then
a
Ef
Σ
Xi
S
ES
Yi
22

---

In Theorem C.I. we can understand ff as the entor 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 JF and the corresponding canonicalization C. By Theorem 3. we have [Vx(X)] [C(x)] | |Gx|, where Gx is the stabilizer of X in group G. In fact (x(x) is just ((X) repeated for |Gx times. To see this, we can divide F(X) into equivalence classes F(X) //xx x, and denote by ~ the corresponding equivalence relation. For two group actions 91 E F(X). 91 ~ 92 if and only if there exists 9o E Gx such that 91 9u92- Since X = P1 (90) 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 [xx]. |. the multi-set of graphs generated by the frame Vx is just the repetition of C(X) for |Gx| times
Intuitively, the frame size [Vx( is |Gxl times larger than the canonicalization size (C(X)), thus drawing without replacement on (X(X) would concentrate slower than on C(X). This is shown in the following theorem.
Theorem C.2 (Bardenet and Maillard [8]) Let X' (Z1...., IN) be finite population of N >> 1 be a list of size n. < N sampled without replacement from X. Then
real points, and (X1...., X.) for all e > 0, the following concentration bounds hold:
Σt (X, 11)
2ns
Pr
max RSKEN-1
2E
exp (-(1 (1- n/N)(1 1/n) a)
k
where a = minisiss TG b = MAXISISN Ti. and μ = 1 Ei=1
In Theorem C.2, let be the true average and let X1.....X, be the outputs of o on the sampled graphs from the frame or canonicalization. The upper bound in Theorem C.2 decreases as the frame/canonicalizatioo size N decreases, indicating faster concentration rate. Since [C(X) < [V>(X),, conclude that CA is more sample efficient than FA; and since the frame size of OAP- graph is smaller than that of FA-graph, we conclude that OAP-graph is more sample efficient than FA-grap FA-graph.
D PCA-frame methods for orthogonal equivariance
D.1 PCA-frame methods
We can achieve orthogonal equivariance by using PCA-frame methods [32]. Given input X Rank we compute orthonormal eigenvectors Rx O(k) of the covariance matrix cov = (X 111 x) (x 111 X). where O(k) is the group of orthogonal matrices in gx Then we transform into its canonical form X Rxx and feed it into a network h. Finally, we apply R 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
((X) 1-X Rx
See Figure 2 for an illustration. Intuitively, this first transforms X by Rx into nearly canonical orientation that is unique up 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 X Rx using the model h, and finally incorporate orientation information back into the output by post-multiplying by R
However, due to the ambiguities of eigenvectors, the canonical form X X is not unique, and cannot achieve exact orthogonal cquivariance without addressing these ambiguities. Puny et al. [45] averages over all possible sign choices for Rx. which requires 2* 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.
D.2 Experiments the n-body problem
We use canonicalization to achieve exact orthogonal equivariance with PCA-frame methods, as introduced in Appendix D. We consider simulating n-body problems Fuchs al. [18]. For baselines
23

---

R
h
RT
R
R
h
R
Figure 2: Using PCA-frame methods to achieve orthogonal equivariance, described as a neural network model [(X) = ((X Rxx Rx where Rx is choice of principal components for the point cloud X E Bank We first transform X via Rx into orientation that is unique up to sign flips, then process Xx using network h, and finally reintegrate orientation information back into the output via Rx. Figure reproduced with permission from Lim et al. [32].
we consider FA over signs of eigenvectors and sign- egn-equivariant models [32]. We also evaluate CA based on Algorithm (OAP-eig) and Algorithm (OAP-lap) on this task. We scale the dimension d of the problem and report the training time and MSE of different models. Figure 3a, we observe that the training time of FA scales exponentially, since it needs to average 24 sign choices. FA runs out of memory on a 32GB V100 GPU for 11. Both sign-equivariant model and CA have almost constant training time as d increases, while CA is slightly more efficient since it enforces no extra cquivariance restraint on the model. In Figure 3b, we observe comparable performance between these methods. CA achieves much better scalability than FA with small loss in accuracy.
I
FA
FA
Sign
Sign
Seconds epoch
OAP-cig
0.006
OAP-cig
OAP-Iap
OAP-lap
MSE
0.001
4-
0.002
0.000
3
11
9
11
Dimension
Dimension
(a) Training time.
(b) Test MSE.
Figure 3: The training time and test MSE of models in the n-body problem. Results are averaged over runs with diffcrent seeds.
E Proofs
E.1 Proof of Theorem 3.1
Proof. Let be a frame. Consider the following set- valued function Cx: V - 2" \e defined by
Cx(X) = (pi(g) 1 (ge
Then CF is G-invariant because for any g' G,
Cx Cx(x1(()x)) (a(l))'pi(g')) ( (EEF((()))))
(pi(g) -(((6))>pi('') gEg
(o210)"'a(ld)''''(()0) -x -cx(X).

---

Thus Cy is canonicalization. Clearly it is also an orbit canonicalization since Cx(X) C (x( for all X.
- if and only there exists E Gx such that 91 9o92, where Gx = [g E G m =X is the stabilizer of X. On the one
Let 91-91 E F(X). We claim that p pm
()) -X (1 On the other hand, hand, if 91 = 9092. then P1 (91)) X = (1()) p1((0)
then X = pi (1) X, which means 9192" E Gx. Denote if p (g) 1 - pi (1()))
9192 = 90. then 91 = 9092-
Thus, we can divide the frame into equivalence classes F(X)/Gx. 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 applying F(X) to X is G/x)) i.e. Cx( = |/(X)//|x Σ [F(X)]. If X has non-trite noniiaivial automorphism, then (X)( < [F()), meaning canonicalization is strictly more efficient than the frame.
Similarly, let C be an orbit canonicalization. Consider the following set-valued function Fc V 20) @ defined by
Fc(x) = fg E G pı()) E C(X)).
Since C(X) C Va(X), is well-defined. It is also G-equivariant, since for any g' E G.
Fo())( E (t)) (166)1))
G pi ( p -g)Fe(X).
Thus Fc is frame. We can also see that the canonicalization induced by Fe is just C itself. Repeating the arguments in the first part of this proof, we conclude that [Fc(X)] = |Gxl CC((X) 2 [C(X)). If X has non-trivial automorphism, then canonicalization is strictly more efficient than the frame. L
Corollary E.1. A frame F is optimal iff the canonicalization that it induces is optimal.
Proof. Corollary E.1 immediately follows from the definition of optimality and the relation [F(X)
|Gxl (C(()), where F and C induce each other.
E.2 Proof of Theorem 3.2
We first show that an orbit canonicalization itself is universal.
Lemma F.2. An orbit canonicalization C: V - 2 Ø is universal.
Proof. Recall universality means that for any G-invariant function f: V - W, there exists a well- defined function Φ: 2 + W such that s(X) = ((C(X)) for all X E V. Since ʃ 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' VX()). We can simply take the & function to be Ø = f. Since ((X) C (X),), we have ((((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 (C(()) = Cx) ) for some orbit canonicalization C, and all X E V, we prove C is universal. By Lemma E.2, for any G-invariant function f: V + W, there exists well-defined function & such that f(X)= = (C)))) for all X V. Letting & = Φe o 9, we have f(X) = (c(((C()))) o(C(X)) for all X V. hence C is universal.
Necessity.
universal, we construct g: 2V + 2V such that it maps C(X) to any subset of Vx(X), for all X E V. Since C is invariant, this mapping is well-defined; and since the equivalence classes (X) are disjoint, this mapping is also injective. Clearly, the canonicalization defined by Cx(X) = (((()) is orbit canonicalization.
D
25

---

E.3 Proof of Theorem 3.3
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 E G and X E V,
(c)(
E
((xo)
(x)
())
o(Xo) = &c XoEC(X)
Σ
((X)
For universality, the G-invariance of f implies that the value of f is constant on each equivalence class (X(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 &C is bounded by
II((X) &CA (X;C,))llw
| (X; (X;
Σ
f(Xo) |c(x)
Σ
o(Xo)
(c(x)
XoEC(X)
XoEe(X)
Σ
(I((X)) - ~((o)llw
[C(X]
XaEc(X)
max XeV
[I] <(X)llw.
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 mild conditions.
universally approximate any G-invariant function using MLPs under
Corollary E.3. Let V, W be compact normed linear spaces. For any continuous G-invariant f: W and any >> O, there exists an MLP network o: V + W such that [|f(X) (xx((;; (X;C, Se holds for all E V.
Proof. Since MLP is universal in approximating continuous functions f: V - W [20]. it also universally approximates such that is G-invariant. Corollary E.3 immediately follows from Theorem 3.3.
E.4 Proof of Theorem 3.4
Notice that in Theorem 3.4, the function & have two inputs. Apart from the canonical form MAP++ (u), also takes an indicator ll as input, which indicates whether u is canonicalizable. Thus proof will be divided into two parts, for canonicalizable and uncanonicalizable eigenvectors respectively.
Lemma E.4. A function Rn + ggnxd permutation equivariant and sign invariant on all canonicalizable inputs E R iff there exists a permutation equivariant function ob R - doxd such that h(u) = @(MAP (u))).
Proof. Sufficiency. If o is permutation equivariant, since MAP++ is also permutation equivariant, so is (1 Since MAP++ ++ is canonicalization for sign, o(MAP-+ (u)) is also sign- invariant.
Necessity, Given a permutation equivariant and sign invariant function h. we simple take @ h, where 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 have to be sign invariant. Since h permutation equivariant, so is d: and since MAP+4 ++ is itself permutation equivariant, is the entire function 6(MAP_ (u)). L
26

---

Before moving on to the second part, we first introduce some lemmas about the structure of uncanon- icalizable cigenvectors under sign ambiguity.
Lemma E.5. If u is uncanonicalizable then all non-zero values in u are paired opposite values. i.e., the multi-set of all non-zero values in takes the form {a1, a1, 02. -2..... Ok: -0k B for some k.
Proof. Because Pu = u, all zorz values in u have to be permuted by P. For any orbit of the permutation 71 - n2 - + Tek + n1, from the fact Pu - -t, we know
Ung (-1) k+ = Un1
Unz Um1 Unz
Ung u1s
Thus, & has to be even, and all values in the same orbit of the permutation are paired opposite values of the same magnitude, e.g-, f#1, -u D- B- Applying it to all orbits of the permutation finishes the proof.
Lemma E.6. For any uncanonicalizable eigenvector u, there exists pairwise permutation matrix P (which only sweeps two non-zero opposite numbers) such that Pu U.
Proof. Since the non-zero values in appear in pairs, simply choose P such that it sweeps these pairs and keeps all 0's unmoved.
Now for the second part.
Lemma E.7. A function h: R + Raaddut permutation equivariant and sign invariant on all uncanonicalizable inputs u R2 iff there exists a permutation equivariant function o: R I Runddou such that h(u) = =((u))-
Proof. Sufficiency. First, obvious that for any u, h(u)) <((uu) sign invariant. It is also permutation equivariant because for any permutation matrix P, (P)))) = Pul) of P ul) Po([u]) 1 Ph(u).
Necessity. Let h be a permutation equivariant and sign invariant function, then for any uncanoni- calizable eigenvector u with Pu -u, have h ((Pu) = h((=)) = h(u)). Following the proof of Corollary E.6, for any two permuted values u; and u, with u, = -.j. there exists a pairwise permutation matrix P such that (Pu), = u -4; Further combined with à (Pu) h(u), we have h( u); = h (P),; (Ph(u)); = h(u),. Thus, two opposite numbers in always have the same output on their corresponding rows of h(u).
Given this property, we can choose random opposite signs for equal numbers in |ul (i.e., a flipping). denoted as rand rand_flip((ul)) flip(/u)) Let Φi
((uu) h(rand h(rran__fipp((u)) It is easy verify that of ((ll) is well-defined as different flipping leads to the same output. Specifically, this is because:
1. Opposite numbers in u leads to the same output on their corresponding rows of h(u);;
2. u's produced by different flippings differ only by a permutation;
3. à is permutation equivariant.
Thus numbers in u with the same absolute value lead to the same outputs, and these outputs are consistent for different flippings.
Then prove Theorem 3.4.
Proof. We construct & as follows. II, = 1, meaning is canonicalizable, we let á as in Lemma E.4; and if 1,, O, meaning uncanonicalizable. we Φ as in Lemma E.7. Combining the sufficiency and necessity of these two lemmas gives the proof of Theorem 3.4.
D
27

---

E,5 Proof of Corollary 3.5
Before proving Corollary 3.5, we first give some intuition about why SignNet is non-universal. In Theorem 3.4 we have already that, uncanonicalizable cigenvectors, the inner á function of SignNet is equal to some other function that only takes in the absolute value the imput cigenvector. This may not be problem if we are only considering 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 p. We can imagine that taking the absolute value of 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.
eigenspace, since permutation equivariant
For instance, we may try to construct a simple counterexample where taking the absolute value loses some information and as result, SignNet fails to distinguish two non-isomorphic matrices. Drawing from the intuition above, here our first try:
-1
-1
U1 [ul U122
2
3
4
5
1
1
1
-1
U = U221, U22
2
3
4
5
Suppose the first column eigenvector of U, and U2 corresponds to eigenvalue A = the second column eigenvector of U1 and U2 corresponds to eigenvalue X2 = 2, and other eigenvectors
not shown corresponds to eigenvalue 0 (so we safely ignore them). Then the Laplacian matrices corresponding to U1 and U2 are:
9
11
17
19
L Nuanay + Auuizu
11
19
23
31
17
23
33
39
19
31
39
51
9
11
15
21
L2
A Nunin
19
25
29
15
25
33
39
21
29
39
51
L1 and L2 clearly non-isomorphic, there does not exist permutation matrix P such that L, = PL,PT. However, the second eigenvector of U, and U2 are the same; the first eigenvector of U, and U2 uncanonicalizable and according 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, eigenvectors in U1 and U2 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).
you may already notice, this example is not really legal, since the
Next, give valid example with orthogonal eigenvectors, and show how SignNet fails to distinguish two non-isomorphic matrices in this case:
-1
1
2
2
-2
-2
0
U [u11, 2122]
1
-1
-1
1
1
0
0
-1
-1
T
-1
-1
2
2
-2
-2
0
0 1
U2 [121, U22
-1
1
0
-1
28

---

We still assume X1 L, A2
2. Their corresponding Laplacian matrices are:
3
3
-3
0
2
2
-2
-2
3
3
-3
0
-2
-2
3
-3
3
3
0
0
2
2
-2
-2
3
3
-3
0
-2
-2
0
0
0
6
-4
4
-2
-2
L
0
0
6
-4
-4
-2
-2
2
-2
-2
44
-4
4
4
0
2
-2
-2
-4
4
4
-2
2
-2
2
-2
0
0
2
2
2
-2
-2
0
2
-1
-3
4
-2
-
-1
1
3
-3
0
2
-2
2
-2
3
1
2
-2
1
3
-1
3
0
4
2
2
-2
2
4
0
-4
0
6
-4
-4
-2
2
L
0
4
-4
2
-4
-4
2
-2
-2
-2
2
-4
-4
4
4
2
2
2
-4
-4
4
4
0
2
2
-2
-2
0
0
-2
2
-2
-2
2
2
-2
0
0
-2
2
Li and L2 are non-isomorphic. In fact, there 24 0's in Lı but only 16 0's in L2, there is way they are isomorphic. However, we can verify three things:
1. The eigenvectors legal, ie., uhuu u12 u u 0:
2. All four cigenvectors U11, U12, U21, are uncanonicalizable;
3. u11 and U21 have the same absolute value, u12 and u22 have the same absolute value.
Therefore, by Theorem 3.4, SignNet would give identical output for Un and U2. Thus it cannot approximate permutation equivariant and sign invariant functions that assign different outputs to these matrices. Unconvinced readers could implement randomly initialized SignNet themselves and verify our claim (we have already done that).
Next we discuss BasisNet. We first introduce BasisNet. Let U₁ E ma be an orthonormal basis of d, dimensional eigenspace. Then BasisNet is parameterized by
f(U1..... U.) = p (løa, (U,U,
where each Φd, shared amongst all subspaces the same dimension d,, and is the number of eigenspaces. Since higher-order permutation equivariant networks are intractable, here mainly fo- cus on using first-order permutation equivariant Φd,- This means Φs, (PU.U, PT) = Piaa, (U,U,T) for all permutation matrix P.
As special case, if d, 1, by letting ((u) = di (uuT) T), BasisNet reduced SignNet:
f(ui.... un) (lo(u:))==)
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, 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 [36], eigenvectors U E R are uncanonicalizable under basis ambiguity iff there exists permutation matrix P such that U + PU and U PUQ for some orthogonal matrix Q. We have the following theorem.
Theorem E.8. a function h: gxdd - X is permatation equivariant and basis invariant any uncanonicalizable eigenvectors with U PUQ, then for any + such that U, = U,Q we have
h(U); h(U)
That is, the rows of huU)) are constant every orbit of the permutation P.
29

---

Proof. Let h: Raxd + Ruxdout be a permutation equivariant and basis invariant function, and let U U= be any uncanonicalizable eigenvectors. For any * j such that U; = U, claim that there exists permutation matrix P' such that U = P'UQ 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)), and the permutation induced by P as P': i (i). We wish prove that there exists p' such that U P'UQ and j = d()). We construct P' as follows.
If (i) j. we could simply let P'
Otherwise, if (i) = j. denote j a(i) where V' We let (1) =j j'(((") j',
and o' (k) o (k) for all other l: + i, Then clearly U PUUQ still holds.
By the claim above and observing ((U) h(p'UQQ)) h(P'U), we have h(U); = MP'U) (P'M(U)); l(U);
Theorem E.8 indicates loss of information when BasisNet is applied to multiple eigenspaces with uncanonicalizable eigenvectors.
E.6 Proof of Theorem 4.1
Proof. It suffices show that the projections { ee hssign of the standard basis vectors (eisg onto the eigenspace still has full rank. Then since the dimension of the eigenspace is d, we can select projection vectors such that they remain linearly independent.
This is easy to prove. For any vector a E IR", there exists a set of coefficients @i, , Un such that 01 + +.... + en In particular, this holds for vectors in the eigenspace V. Thus multiplying both sides by S we have a Pa a = ee +.... + ag Pe, for all a V. Thus the projections (Peehssn are still a of basis in the eigenspace, and Theorem 4.1 follows.
E.7 Proof of Theorem 4.2
When permutation equivariance is not required, all eigenvectors canonicalizable. Thus "optimal" here means Algorithm and Algorithm 2 can canonicalize all eigenvectors. Algorithm is clearly optimal orbit canonicalization since:
Proof.
It outputs either u or -u and is an orbit canonicalization:
2. Every eigenvector has at least one non-zero element, so Algorithm 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 is also an optimal orbit canonicalization since:
1. The Gram-Schmidt orthogonalization of set of basis in a subspace is still set of basis in that subspace (but orthogonalized),, so Algorithm an orbit canonicalization;
2. By Theorem 1, Algorithm 2 always succeeds finding the indices it < ... < ia and orthogonalizing them;
3. It is basis invariant, since the projections (Pei) are basis invariant, and all procedures that follow remain basis invariant.
30

---

E,8 Proof of Theorem 4.3 and Corollary 4.4
We strongly recommend the readers to read Appendix 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 set of basis in a subspace is still of basis in that subspace (but orthogonalized), so Algorithm is an orbit canonicalization;
2. It is basis invariant, since the projections {p.} ei are basis invariant, and all procedures that follow remain basis invariant:
3. The permutation equivariance of Algorithm is more technical, which is proved in Theo- rem 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 z; these two algorithms almost the same, except with different values for ag In OAP, the a is defined by hash( Pi., $ PipBiss) while in MAP, their af | is special case of ours. Thus:
If a; O;j, then Po. 3s and p { 9f B. 13 =
This indicates of ||
d ay-
However, if af = agz this does not necessarily mean ag = ag. For instance, let P1 = 32 = (1,0), then of = al but on A 02
This means a; more "distinctive" than a', and as result we will have a better chance finding indices i <... < ia such that Pwi....., Pai, is basis of the eigenspace. This is because, more "distinctive" a, would lead to more "refined" (smaller) groups B,, and as result, the rank of the projections {9xx} will not decrease (and possibly increase). By splitting the group B, 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 <... id. In fact, after working out the summary vectors, the rest of the MAP algorithm is equivalent to Algorithm 3 except that they restrict i l......6 is .d d. Recall that in MAP, given u1 U;-1 already found, they look for in the orthogonal complementary space of (u....., u;-1) in V by projecting æ; onto that space; and if æ; is orthogonal to that space, their algorithm fails. This is exactly what Gram- Schmidt process does to the projection vectors { (Pxx). Except in our algorithm, instead of looking at projections P....... Pxs we look for all projections PI...... ...,.r Lxz and try to select a subset of them such that the algorithm succeeds. This is obviously strictly superior, since there may be cases where L P...... Fx is not basis of the eigenspace but another subset P Px.,.... P Dy is. O
Next we prove the superiority of OAP-graph over FA-graph.
FA-graph works follows. Assume the graph has eigenspaces with projection matrices P...... Pn. Let , be the diagonals of these projection matrices, and let S [81, [SI...., Sn] |n Then the frame of the graph is defined 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 the original graph). We call this canonicalization FA-graph.
Next introduce OAP-graph. Let af be defined in the same way a, except that E = 1,.... k denotes that af is computed from the projection matrix of the l-th eigenspace Pt. Let S' E g be a matrix with S₂ af. The frame of the graph is the set of all permutations that sort the rows of S' 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 of. Since the of used OAP-graph is stronger than in FA Frggh,,h, OAP-grape is also superior to FA-graph.
31

---

We will show that FA-graph is equivalent to our algorithm that takes a, = Pv. which is weaker than our definition a; hash iis ig))
Proof. OAP-graph is almost identical to FA-graph, except that instead of sorting of Pa as in FA-graph, we sort values of o; hash P.. H p Dive).
1. If a; = aj. clearly af = Bi 93 = az.
2. However, if a ''j, this does not necessarily mean 0;- Oj. For instance, let 91 11 and 92 (2, 1), then af ag but 01 # 02-
This means ag is more "distinctive" than a/p. We know that the frame obtained by FA-graph or OAP-graph consists of all permutations that sort the values of a, in lexicographic order. Thus, strictly more distinctive a, will lead to strictly less repeating elements and strictly less number of permutations (i.e., strictly smaller frame size).
Finally, we prove the superiority of OAP-lap over FA-lap.
Proof. FA-lap is almost identical to OAP-lap, except that it uses a less distinctive o; P.. When proving the superiority of OAP-graph over FA-graph, we proved that a, used by FA-lap is strictly less distinctive than a; used by OAP-lap, and when proving the superiority of OAP-lap over MAP we proved more distinctive a; would lead to higher chance of finding indices i .... ia. Combining these facts gives the proof of the superiority of OAP-lap over FA-lap.
F Augmentations of the OAP algorithm
In this section, we present three variations of the OAP algorithm. The first two variants enhance the original OAP algorithm (Algorithm 5) through straightforward augmentations, while the third variant extends the OAP algorithm render trainable by neural networks.
F1 Incorporating node features
Recall in Algorithm 5 we defined the germutation-cquuvarinn vector with
a; hash( P.. | (iii)) 1 isism
and used the values of to split the standard basis vectors into different groups From the proof of Theorem B.2, we can see that the permutation equivariance of OAP is guaranteed by the permutation equivariance of a, which is respected as long as the indices of o; are permutation equivariant, i.e.,
(i) hash( @ (i) & 9 (()a Bisss, 1 isisn
for all permutation a. This indicates that we can incorporate any permutation eeqioonriiiiviiiantt features into a, as long as it preserves the permutation equivariance i. If the input graph has node features X E Raxd where is the number of nodes, then the node features X would be permutation equivariant. Using this property, we propose the following variant of OAP, by incorporating X into a
oR hash( (B, ol Pighiii Xt), 1SS ssiss <
where X; is the node feature of the i-th node. It is easy to see that this variant is superior to the original OAP algorithm.
F.2 Incorporating information from other eigenvectors
Another example of permutation equivariant feature is the projection matrices of other eigenspaces. Suppose there are eigenspaces in total, with corresponding projection matrices (1)) ())
For each 1 < i n, we can calculate value of a; for each of these eigenspaces:
(k) a
hash S (k)
( Bit)) 15 k < e,
32

---

then coalesce them into single value
a, hash(a, faa Bstt))
where 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 the original OAP canonicalization.
F.3 Learnable canonicalization
We can also adopt learnable networks to substitute certain components of the OAP canonicalization. For example, the hash function in the definition of a; can be made learnable:
ag h (it. (; isis n,
We can also replace the where h is neural network that is invariant the ordering of P Bi Schm-Schmidt orthogonalization with a learnable network:
U h 1' x
Px.).
where \ is a permutation eettriiriiniiviiiannntt neural network. The output vectors may not be orthogonal, but since h' almost certainly preserves the rank (PIr, Pxi does not lose expressive power.
G Related work
G.1 Equivariant learning
There are four main approaches in the mainstream to achieve equivariance. The first approach, as used in Yarotsky [69], Murphy 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 graphs and the sign transformation group 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 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 al. [45]. This method involves averaging over smaller frame instead of the entire group. However, a drawback of this approach that it requires the frame 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 size given by the set (1,-133
The third approach is learned canonicalization, proposed by Kaba et al. [26]. which can be viewed as frame averaging with frame size of However, such canonicalization is not possible if the input has non-trivial automorphism. Additionally, even for non-automorphii inputs, the assumption of equivariance makes constructing such canonicalization challenging.
The fourth approach involves designing equivariant network architectures tailored to specific equiv- ariant constraints. For example, Fuchs et al. [18] introduced the SE(3) transsfrrrf,,,, which exhibits cquivariance to the SE(3) group. Additionally. Zaheer et al. [70] and Segol and Lipman [53] pro- posed networks that are permutation invariant and equivariant. Furthermore, Lim al. [33] and Lim et al. [32] presented networks that maintain sign invariance, basis invariance, and sign equivariance. However, this approach's downside lies 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.
G.2 Canonicalization
There have been several related works using canonicalization achieve equivariance. Apart from Kaba et al. [26] discussed in Section 2.1, Dym et al. [16] proved the impossibility of continuity for
33

---

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 set rather than single element, it allows for more flexibility and continuity with weighted averaging. Lin al. [34] proposed a framework of canonicalization that assumes single canonical form, so their framework is essentially 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 Intractabiliry. 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 Section 5.1.
Even if could find a single canonical form for all inputs, as pointed out by Dym al. [16] such canonicalizations are still not continuous, which hurts their performance.
In summary, compared to previous canonicalization works that only consider single-clement canoni- calization that may be unrealizable, we take canonicalizability into account throughout the analysis and thus gives more rigorous and general framework that works for both canonicalizable (single canonical form) and uncanonicalizable (no single canonical form) inputs.
G.3 Canonical forms
Canonical forms, 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 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.
G.4 Sign invariance
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 On*)). 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-procssiing. However, their method cannot be applied to general eigenvectors.
34

---

G.5
Basis invariance
Lim et al. [33] introduced BasisNet, which is basis invariant. However, achieving universality with
BasisNet necessitates utilizing higher-order tensors in IR" where 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 strictly superior to previous methods while incurring negligible computational overhead.
Beyond GNN, there cxists literature exploring Laplacian eigenvectors of graphs and addressing the sign/basis ambiguity issues. Lai and Zhao [31] presented a solution employing optimal transport theory tackle sign/basis ambiguities, involving the resolution of 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 heuristic measure called ELD, which bears resemblance to the structure of SignNet.
H Dataset details
ExP [1] (GPL-3.0 License) is dataset designed to explicitly evaluate the expressiveness of GNN models, and consists of a set of graph instances (......, Gn. Hi,..., Hn). such that each instance is graph encoding of a propositional formula. The classification task is to determine whether the formula is satisfiable (SAT). Each pair (9,, Hi) respects the following properties:
1. G. and H4 are non-isomorphic;
2. Ga and Hi have different SAT outcomes, that is, G; encodes a satisfiable formula, while Hi encodes an unsatisfiable formula;
3. G. and Hi are 1-WL indistinguishable, are guaranteed to be classified in the same way by standard MPNNs;
4. Gi and H4 are 2-WL distinguishable, so can be classified differently by higher-order GNNs.
The n-body problem dataset [28, 18] (MIT License) consists a collection of n = particles systems. Five particles each carry either positive or 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 = 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 molccular graphs are between 9 and 37 nodes large. Each node represents a heavy atom (28 possible atom types) and each edge represents bond (3 possible types). The task is to regress constrained solubility (logP) of the molecule. The dataset comes with a predefined 10K/1K/IK train/validation/tesl split.
OGBG-MOLTOX21 and OGBG-MOLPCHR [22] (MIT License) are molecular property prediction datasets adopted by OGB from MoleculeNet. These datasets use common node (atom) and edge (bond) featurization that represent chemophysical properties. OGBG-MOLTOXX2 binary graph classification dataset where a qualitative (active/inactive) binary label is predicted against 12 different toxicity measurements for each molccular graph. OGBG-MOLPCBA is also multi-task binary graph classification dataset from OGB where active/inactive binary label is predicted for 128 bioassays.
a multi-mask
I Hyper-parameter settings
All (preliminary, failed and main) experiments are NVIDIA 3090 GPUs with 24GB memory.
35

---

L.1 EXP experiment
In the EXP experiment, the nyper-parameters are not tuned. We use the same hyper- syper-parameters as in Puny et al. [45]. Additionally, we also use the code base EXP to test FA-GIN+ID and FA-GINE+ID on the ZINC dataset. For both models we use 16-layer GNN, with the hidden dimension set to 176. The output of the GNN is then fed to 2-layer MIP to produce the final regression output. On both EXP and ZINC the frame or canonicalization of graphs are computed during pre-processing time (using the pre_ res_transfor cransfomm orm argument of the dataset class). On ExP, since the frame canonicalization size for some graphs is large shown in Table (because the Exp dataset is highly symmetric), we randomly sample from the frame canonicalization, with the sampling size being 64, All experiments results are averaged over 4 runs with different random seeds.
1.2 n-body experiment
In the n--oddy experiment, we tune the number layers L and the hidden dimension h of our canonical averaging models. Other hyper- syper-parameters such learning are kept the same with Puny et al. [45]. The hyper-parameter settings for different methods with dimension d = are reported in Table 8. For higher dimensions, slightly adjust the hidden dimension h (+3) such that is multiple of d.
Table 8: d = 3.
settings different methods in the n-body experiment with dimension
Method
L
#param
Frame Averaging
4
60
92103
Sign Equivariant
45
201555
OAP-eig
4
63
117817
OAP-lap
63
117817
L.3 ZINC experiment
In the ZINC graph regression experiment, We follow the same settings as Dwivedi al. [15] for models with no PE, LapPE or LSPE, and the same settings as in Lim et al. [33] for models with SignNet, MAP or OAP. We implement FA-GIN+ID and FA-GINE+ID on ZINC by ourselves (their hyper-parameters are already reported above); all other baseline scores reported in Table 4 are taken from the original papers. The main hyper-parc paremerrrseeeers in our experiments are listed as follows.
the number of eigenvectors used the PE.
L the number of layers of the base model.
hy: the hidden dimension of the base model.
f:z: the output dimension of the base model.
the initial learning rate.
t: the patience of the learning rate scheduler.
r: the factor of the learning rate scheduler.
Amin: the minimum learning rate of the learning rate scheduler.
Lz: the number of layers of SignNet or the normal GNN6 (when using canonicalization as PE).
la: the hidden dimension of SignNet or the normal GNN (when using canonicalization as PE).
The values of these hyper-parameters our experiments are listed in Table 9,
I.4 OGBG experiment
In the OGBG-MOLTOX21 experiment, the values of these hyper-parameters are listed in Table 10. We substitute SignNet with normal GNN (Masked GIN) when using canonicalization the PE method.
36

---

Table 9: Hyper-pun syper-parameter settings of different models with different PE methods on ZINC.
Model
PE
k
L1
h
h2
X
Amin
L2
hs
None
16
78
78
0.001
25
0.5
le-6
LapPE + RS
8
16
78
78
0.001
25
0,5
le-6
SignNet
16
67
67
0.001
25
0.5
le-6
8
67
GatedGCN
MAP
8
16
69
67
0.001
25
0,5
le-5
6
69
OAP
16
68
68
0.001
0.5
1e-5
6
68
OAP + LSPE
13
59
59
0.001
25
0.5
1e-5
6
59
None
16
70
70
0.001
25
0.5
le-6
LapPE + RS
16
80
80
0.001
25
0.5
le-6
SignNet
16
70
70
0.001
25
0.5
le-6
8
70
PNA
MAP
16
70
70
0.001
25
0,5
le-6
6
70
OAP
16
70
70
0.001
25
0.5
le-6
6
70
OAP LSPE
13
60
60
0.001
25
0.5
le-6
6
60
Table 10: Hyper-parameter settings of different models with different PE methods MOLTOX21.
Model
PE
k
L
h
hz
X
Amin
L2
h3
None
0
8
154
154
0.001
25
0.5
1e-5
LapPE + RS
3
8
154
154
0.001
25
0.5
le-5
GatedGCN
SignNet*
3
8
150
150
0.001
22
0.14
1e-5
150
MAP
3
8
150
150
0.001
22
0.14
le-5
150
OAP
3
8
160
150
0.001
22
0.14
le-5
160
None
0
206
206
0.0005
10
0.8
2e-5
LapPE RS
16
8
140
140
0.0005
10
0.8
2e-5
PNA
SignNer*
16
110
0.0005
10
0.8
8e-5
110
MAP
16
8
115
113
0,0005
10
0.8
8e-5
115
OAP
16
8
115
113
0.0005
10
0.8
86-5
115
In the OGBG-MOLPCBA experiment, the values of these dyyer-parameteen are listed in Table 11.
Table 11: Hyper-panne Syper-parammetr settings of different models with different PE methods on MOLPCBA.
Model
PE
k
L
h
hz
À
Aminn
L
hg
None
8
154
154
0.001
25
0.5
le-4
LapPE RS
3
8
154
154
0.001
25
0.5
le-4
GatedGCN
SignNet*
8
200
200
0.001
25
0.5
le-5
200
MAP
3
8
200
200
0.001
25
0.5
le-5
8
200
OAP
8
200
200
0.001
25
0.5
1e-5
200
None
12
600
600
0.0005
0.8
2c-5
LapPE RS
16
12
600
600
0.0005
10
0.8
2e-5
PNA
SignNet
16
4
300
300
0.0005
10
0.8
2e-5
8
300
MAP
16
4
304
304
0.0005
10
0.8
2e-5
8
304
OAP
16
4
304
304
0.0005
10
0.8
2e-5
8
304
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims made in the abstract and introduction supported by theoretical discussions and experiments.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work discussed in Section 6.
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 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 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
38

---

Justification:
The full set of assumptions are included in the statements of theorems, while the complete proof is included in Appendix E.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the information needed to reproduce the experimental results the paper is included in Section 5 and Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open Access to Data and Code
39

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The link to our code is attached in the abstract. All datasets used are accessible to the public.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
Poyyccy)) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: http//gguie//ooooeeeeeeeeeeeo
/ //nips. cc/
is hearbbimsssoooooiiiiiiccc onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the training and test details are included in Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are reported in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
40

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The type of compute workers and memory are reported in Appendix The running time and GPU memory of our experiments reported in Table 7.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: //tp::///eeereee http//nuripp..e/ cc hwtppp/liic/tchcccccteeleellllll
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As a general framework for learning with symmetry, we do not foresee immediate positive negative societal outcomes.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
41

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The data and models in the paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 usage guidelines 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: The creators of assets properly cited in the main text and the licenses mentioned in Appendix H.
Guidelines:
The answer NA means that the paper does 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 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.
42

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
43

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
44


Reviews:
[{"review_id": "Cz6e06fk9u", "reviewer": "Reviewer_y3Wh", "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.", "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.\n- Are there any other domains where the results on the connection between frame averaging and canonization is directly applicable?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written.\n- The connection between canonization and frame averaging is very interesting. It helps resolve the issue of universality of sign and basis networks. Further, for the case without permutation, a universal algorithm is also proposed.\n- Experimental results show that the proposed method is expressive and computationally more efficient than frame averaging.\n- Experimental results on various graph datasets show superior performance to prior methods.", "weaknesses": "- 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.\n- 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).\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer y3Wh for the constructive review. We address your concerns as follows.\n\n---\n\n**Q1.** 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.\n\n**A1.** Yes! Methodologically, the proposed canonization algorithm is a pure preprocessing algorithm that does not increase the training time, and the pre-processing time is negligible compared with training time. On the other hand, FA methods such as SignNet increase the training time. The canonization algorithm also has no influence on the memory.\n\nWe compare the time and memory of canonization methods with their non-FA backbone in the following table. Using canonization 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. We will include all compute time and memory statistics in our paper.\n\n| Model | Pre-processing time | Training time | Total Time | Memory |\n| --- | --- | --- | --- | --- |\n| GatedGCN backbone | - | 3h26min | 3h26min | 1860MiB |\n| GatedGCN + SignNet | 30.03s | 4h13min | 4h13min | 2124MiB |\n| GatedGCN + MAP | 133.67s | 3h20min | 3h22min | 1850MiB |\n| GatedGCN + OAP | 186.38s | 3h25min | 3h28min | 1860MiB |\n| PNA backbone | - | 16h31min | 16h31min | 2242MiB |\n| PNA + SignNet | 30.03s | 18h1min | 18h1min | 2570MiB |\n| PNA + MAP | 133.67s | 16h47min | 16h49min | 2244MiB |\n| PNA + OAP | 186.38s | 14h54min | 14h57min | 2312MiB |\n\n---\n\n**Q2.** 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.\n\n**A2.** Since the frame and canonization sizes are both extremely large, we need to subsample them in practice. For fair comparison, we adopt the same subsampling size. In this case, **the advantage of canonization at the averaging complexity translates into a better sample efficiency for approximating the averaging expectation, which leades to faster training convergence, as we proved in Appendix C**. As for computing the frame/canonization of the same size, frame/canonization takes 2.53s and 3.15s for pre-processing, whose difference is negligible compared to the training time of 67.37s.\n\n---\n\n**Q3.** 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.\n\n**A3.** We note that our canonization perspective established in Section 3 is generic and applicable to different types of equivariance. In Section 4, we focus on sign/basis invariance because they are one of the most challenging problems with exponentially large group sizes. Apart from that, we also applied our canonization algorithms to other symmetries, including:\n\n- **permutation equivariance** of graph data in the EXP experiment;\n- **rotational equivariance** of particles In Appendix D.\n\nThese new applications illustrate the generality of our analysis and the proposed algorithms, which leads to the use of a more general title. We will elaborate more on this part to avoid any confusion. Thanks!\n\n---\n\n**Q4.** 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.\n\n**A4.** Following your suggestion, we evaluate GIN with two kinds of commonly used node IDs: one-hot node ID and random node features.\n\n1. Models with only one-hot node IDs is **not robust**: when we apply a random permutation to the input graph during training, the model fails with only 0.5 accuracy, while FA-GIN+ID is not affected. This shows that without permutation equivariance, the model is not able to learn real structural information.\n2. Models with only random features **converges much slower** than the deterministic FA-GIN+ID model (see a training progress comparison in Figure 3 of [1]). This is because it’s hard to learn from random features without exact permutation symmetry. \n\nThe above results show that lacking permutation equivariance hurts the robustness and convergence speed of GNNs. Real-world tasks are much more complex than EXP, thus lacking equivariance could harm the performance of GNN models significantly.\n\n**References:**\n\n[1] Ma et al. Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding. *NeurIPS 2023*.\n\n---\n\n**Q5.** Are there any other domains where the results on the connection between frame averaging and canonization are directly applicable?\n\n**A5.** Since our analysis applies to general groups, the connection applies to any type of equivariance. In this paper, we have explored **sign/basis invariance, permutation equivariance, and orthogonal equivariance**. In future work, it is also possible to apply frame and canonization to the rotational equivariance of point clouds/molecules, the permutation equivariance of multisets, etc. Therefore, we believe that canonization would serve as a new generic perspective for understanding and attaining equivariance.\n\n---\n\nWe hope our response addresses your concerns. If you have further concerns, we will be happy to address them during the discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w9Co1I4w6O", "reviewer": "Reviewer_MgpB", "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.", "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.\n\n2. 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": "The authors discussed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The paper is well-written and nicely explained.\n\n2. The paper provides strong theoretical results.\n\n3. Empirical analysis backs the theoretical reasoning for the proposed architecture achieving higher performance.", "weaknesses": "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)\n\n1. Line 98: $G_X$ is not define before. I think it should be defined here instead of Line 129\n2. proof of theorems in the supplementary is not in order of the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer MgpB for the constructive review. We address your concerns as follows.\n\n---\n\n**Q1.** 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)\n\n**A1.** We provide experiment results on Alchemy in the following table. Due to the limited time of the rebuttal period, we directly followed the SignNet setting and did not tune the hyperparameters for our method, so there is room for improvement. As shown in the table, SignNet, MAP, and OAP all achieve comparable performance. Unfortunately, we are unable to reproduce the texture reconstruction task in SignNet since it was a private code and the authors did not release it (see the [SignNet repo](https://github.com/cptq/SignNet-BasisNet)). Following your suggestion, we will add the full experiment results in our paper to make it more complete.\n\n| Model | Test MAE |\n| --- | --- |\n| GIN | 0.180 ± 0.006 |\n| SignNet | 0.113 ± 0.002 |\n| MAP | 0.114 ± 0.0007 |\n| OAP | 0.115 ± 0.001 |\n\n---\n\n**Q2.** Line 98: $G_X$ is not define before. I think it should be defined here instead of Line 129. Proof of theorems in the supplementary is not in order of the main text.\n\n**A2.** Thanks for pointing this out. We will define $G_X$ before line 98 and adjust the order of proofs in the appendix.\n\n---\n\n**Q3.** 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.\n\n**A3.** Thanks. Here is a more elaborate explanation. In frame averaging, we need to design a \"frame\" $\\mathcal{F}$ that is a subset of the whole group $G$ and is **equivariant** to the group actions in $G$. Theorem 3.1 gives the equivalence of frame and canonization, which allows us to convert the problem of finding a *frame* into finding a *canonization*. In canonization, for each input, we need to find a subset of the input space that is **invariant** to the group actions. This set is called the canonical form of the input. Doing so has several advantages:\n\n- Firstly, since equivariance is a strong requirement, it is often easier to directly construct an invariant canonical form instead of an equivariant frame.\n- Secondly, as proved in Theorem 3.1, the canonization size is $|G_X|$ times smaller than the frame size, making canonization more efficient than frames.\n- Thirdly, canonization theory allows us to characterize the existence of uncanonizable elements when further equivariance constraints are imposed, which further allows us to solve the open problem of the expressivity of SignNet.\n\nWe will add this elaboration in the revision.\n\n---\n\n**Q4.** Line 175: “The canonization size |C(X)| may differ for different inputs.” — what does the size of |C(X)| tell about the input X?\n\n**A4.** The canonization size $|\\mathcal{C}(X)|$ reveals **the extent of symmetry (w.r.t. group** $G$) **of the input**, in that **more symmetric inputs often lead to a larger canonization size**. For example, more symmetric graphs with more automorphism (e.g., a regular graph) often result in a larger canonization size. Specifically, the canonization sizes of graphs in the ZINC molecular datasets are mostly within the order of $10^3$, while in the more symmetric EXP dataset, the canonization sizes are in the order of $10^{19}$. We will elaborate on this point in the revision.\n\n---\n\nWe hope our response addresses your concerns. If you have further concerns, we will be happy to address them during the discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fRuc7XMcjG", "reviewer": "Reviewer_TcMZ", "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.", "questions": "Below I provide a number of comments and questions.\n\n* 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.\n\n* 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. \n\n* Line 87 and 95 - universal approximation is claimed, however neither a citation, nor a theorem reference is provided.\n\n* 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. \n\n* Line 128 - why are automorphisms of the input a major obstacle in analyzing complexity of frames? \n\n* Line 144 - what you refer to as contractive ‘canonization’, is usually referred to as orbit canonicalization. Eg see  https://arxiv.org/abs/2402.16077\n\n* Line 175 - the same thing is stated twice.\n\n* 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. \n\n* In line 205 what is the norm of a vector? \n\n* Whenever a theorem is stated, a reference to where the proof can be found should be stated. \n\n* 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 … \n\n* 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?\n\n* 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?\n\n* Line 304 - you never say what FA/CA is - I presume this is frame averaging and canonisation averaging? \n\n* 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": "See weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Given the recent rise in papers covering the topic of frame averaging, this paper proposes a more useful view, by considering ‘canonizations’ instead, which are always smaller or same in size, compared to the corresponding frames. The proposed view turns out to be useful for proving universality under sign invariance and highlights issues with existing approaches for permutation equivariance - this makes it interesting for investigating in the setting of other groups. \n\nThe appendix seems to be quite informative and well-written.", "weaknesses": "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. \n\nUnfortunately, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer TcMZ for the careful reading and the constructive review. We acknowledged that this paper uses conventional notations from the GNN theory literature, such as hash function, without detailed explanations. We will definitely improve the clarity of the writing and the readability of the paper. Below, we carefully address your main concerns.\n\n---\n\n**Q1.** This is particularly true for superiority proofs, which clearly assume something about the hash function, but nothing is ever stated in regards to it.\n\n**A1.** We note that the hash function in our paper is consistent with the usage in the GNN theory literature, where the hash function is often directly used without further explanation (see, e.g., the seminal work [1] among many others). As a common concept in computer science, in a hash function, identical inputs lead to identical outputs, while different inputs result in distinguishable outputs. In our experiments, we use $\\operatorname{hash}(h_i,\\\\{\\\\!\\\\!\\\\{h_j\\\\}\\\\!\\\\!\\\\})=h_i+\\sum h_j^3$, though it could be substituted with other choices. We will clarify this in our experiments section.\n\n**References:**\n\n[1] Xu, Keyulu, et al. \"How powerful are graph neural networks?\" ICLR 2019.\n\n---\n\n**Q2.** In addition to that, it is not immediately clear where the ‘canonization’ view can be useful, beyond the example provided in this paper.\n\n**A2.** We note that canonization is a generic method, and it can be applied to scenarios beyond those demonstrated in our paper. The major advantage of canonization is two folds. \n\n- Theoretically, it enables us to have an essential view of frames and frame averaging, a formal hierarchy of frame complexity, and a principled path to designing optimal frames.  With this theory, we can show the non-universality of SignNet, which is a critical open problems.\n- Empirically, we show that canonization can be applied in many different scenarios with different types of symmetries:\n    - **sign and basis equivariance**: we design optimal or better algorithms (OAP) for sign and basis equviariance of eigenvectors, and show clear benefits in efficiency and performance.\n    - **permutation equivariance**: in the EXP experiment (Section 5.1), we use canonization to achieve permutation equivariance on graph data (not sign/basis invariance of eigenvectors).\n    - **rotation equivariance:** In Appendix D, we applied canonization to achieve rotational equivariance of particles in PCA-frame methods.\n\n---\n\n**Q3.** 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.\n\n**A3.** Thanks for the suggestion. We agree with this and will switch to \"canonicalization\" in the revision for better consistency.\n\n---\n\n**Q4.** 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.\n\n**A4.** This is true. We will clarify these assumptions in our paper.\n\n---\n\n**Q5.** Line 87 and 95 - universal approximation is claimed, however neither a citation, nor a theorem reference is provided.\n\n**A5.** Thanks for pointing out. We will cite the frame averaging paper after these claims.\n\n---\n\n**Q6.** Line 128 - why are automorphisms of the input a major obstacle in analyzing complexity of frames?\n\n**A6.** The size of the automorphism group (and thus the frame) depends on the input --- more \"symmetric\" inputs with larger automorphism group would lead to larger computational complexity in the averaging step. Instead, the size of canonical forms depends less on the input and is more stable. For example, an optimal canonization would have size 1 on all inputs, while the corresponding frame size could be exponential (e.g., for graphs). For the sign ambiguity of LapPE, some eigenvectors become uncanonizable, but their canonization size is still less than or equal to 2, while their corresponding frame sizes could be exponentially large depending on the input.\n\n---\n\n**Q7.** Line 144 - what you refer to as contractive ‘canonization’, is usually referred to as orbit canonicalization.\n\n**A7**. Thanks for pointing out. We will switch the term to orbit canonicalization for consistency.\n\n---\n\n**Q8.** In line 205 what is the norm of a vector?\n\n**A8.** On line 205 $|\\cdot|$ refers to element-wise absolute value. We apologize for the confusion and will clarify this in the theorem.\n\n---\n\n**Q9.** 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 …\n\n**A9.** Indeed, we would state the problem more clearly for better readability. \n\n---\n\n**Q10.** 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?\n\n**A10.** OAP is optimal iff such indices always exist for **canonizable** inputs. So far we are not able to construct such inputs where these indices do not exist, therefore we are uncertain whether OAP is optimal.\n\n---\n\n**Q11.** Line 304 - you never say what FA/CA is - I presume this is frame averaging and canonisation averaging?\n\n**A11.** This is true. We defined FA on line 29 and CA on line 146. Nevertheless, we will make sure to clarify this in the main text.\n\n---\n\n**Q12.** The mentioned typos and suggestions.\n\n**A12.** We will fix them in the revision. \n\n---\n\nWe thank Reviewer TcMZ again for carefully checking our paper and providing many constructive suggestions. We will surely modify our paper according to your suggestions. If you have further concerns, we are happy to address them in the discussion stage.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VaOpGd8aIS", "reviewer": "Reviewer_8tUB", "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.", "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": "The authors do mention one of the limitations is that OAP does not fully resolve the optimality of eigenvector canonization under permutation equivariance.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Theoretically describing frame through canonization is beneficial. Understanding the equivalence between frame and canonization (Theorem 3.1) is great, and the theoretical definition of optimal canonization (Theorem 3.2) is straightforward.\n- The primary method, OAP, uses Gram-Schmidt orthogonalization to canonicalize eigenvectors and resolve eigenvalue degeneracy (or basis ambiguity), which is also straightforward.", "weaknesses": "### **Major**:\nThe 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.\n\n\n### **Minor**:\n- 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.\n- Please add references in the main text to the appendix for proofs and n-body experiments to enhance readability.\n- 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.\n\n[1] *Frame Averaging for Invariant and Equivariant Network Design*. Omri Puny, et al. ICLR 2022.\n\n[2] *Learning Probabilistic Symmetrization for Architecture Agnostic Equivariance*. Jinwoo Kim, et al. NeurIPS 2023.\n\n[3] *A Hitchhiker’s Guide to Geometric GNNs for 3D Atomic Systems*. Alexandre Duval, et al.\n\n[4] *Equivariant Frames and the Impossibility of Continuous Canonicalization*. Nadav Dym, et al. ICML 2024.\n\n[5] *Equivariance via Minimal Frame Averaging for More Symmetries and Efficiency*. Yuchao Lin, et al. ICML 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 8tUB for the constructive review and acknowledging our theoretical contributions. We address your main concerns as follows.\n\n---\n\n**Q1.** 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.\n\n**A1.** Thanks for the suggestions. We will keep improving the writing to be more clear and readable.\n\nFor the application of canonization, we provided multiple application scenarios of canonization in the paper:\n\n- **sign and basis equivariance**: we design optimal canonization algorithms (OAP) for sign and basis equviariance of eigenvectors, and show clear benefits in efficiency and performance.\n- **permutation equivariance**: in the EXP experiment (Section 5.1), we use canonization to achieve permutation equivariance on graph data (not sign/basis invariance of eigenvectors).\n- **the product group of the permutation group and the sign/basis transformation group:** for the graph case, we do consider the product group and show a strictly better canonization design (OAP for graphs).\n- **rotation equivariance:** In Appendix D, we applied canonization to achieve rotational equivariance of particles in PCA-frame methods.\n\nBesides, it is also easy to extend our results to the **translation group**. For example, a translation that moves the center of the input to the origin is a canonization under translation. Combining this canonization with the orthogonal group gives a canonization under the Euclidean group. \n\nIn summary, we believe that these evidences show that our method has the generality to be applied to various tasks and different symmetries with improved efficiency over frame averaging. We will add these elaborations in the revision following your advice.\n\n---\n\n**Q2.** I would like to know what is the result of MAP + LSPE in ZINC 500k compared to OAP + LSPE.\n\n**A2.** Following your suggestion, we further evaluate MAP + LSPE on ZINC. As shown in the following table, OAP can still outperform MAP under similar parameter constraints.\n\n| Model | #Param | MSE |\n| --- | --- | --- |\n| GatedGCN + MAP + LSPE | 475K | 0.101 ± 0.001 |\n| GatedGCN + OAP + LSPE | 491K | 0.098 ± 0.0009 |\n| PNA + MAP + LSPE | 550K | 0.104 ± 0.005 |\n| PNA + OAP + LSPE | 549K | 0.095 ± 0.004 |\n\n---\n\n**Q3.** Please add references in the main text to the appendix for proofs and n-body experiments to enhance readability.\n\n**A3.** Thanks for the suggestion. We will provide these references in our revision.\n\n---\n\n**Q4.** 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.\n\n**A4.** Thanks for pointing out these related works! They are definitely related to the topic and we will discuss them in the revision. Among them, Kim et al [2] proposed a probabilistic frame averaging to achieve equivariance. Duval et al [3] gave a comprehensive review of geometric GNNs for 3D atomic systems, and introduces a taxonomy of geometric GNNs. We believe canonization methods can serve as a new direction for achieving the required equivariance of 3D atomic systems. \n\nMore relevantly, Dym et al [4] proved the impossibility of continuity for canonizations 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 [5] proposed a framework of canonization that assumes a single canonical form, so their framework is essentially a special case of our framework by taking $|\\mathcal{C}(X)|=1$. The “minimal frame” in their paper is just the induced frame of an optimal canonization in our framework. However, the assumption of a single canonical form has the following key limitations:\n\n1. **Theoretical Impossibility.** A single canonical form may be theoretically impossible under some constraints. For instance, canonization of LapPE requires permutation equivariance, in this case it is theoretically impossible to find a single canonical form for some eigenvectors.\n2. **Computational Intractability.** A single canonical form may be computationally intractable to find. For instance, computing graph canonization is NP-hard. In this case, we have to adopt an approximate approach that admits a set of canonical forms, as in our EXP experiment.\n\nEven if we could find a single canonical form for all inputs, as pointed out by [4] such canonizations are still not continous, which hurts their performance. \n\nIn summary, compared to previous canonization works that only consider single-element canonization that may be unrealizable, we take canonizability into account throughout the analysis and thus gives a more rigorous and general framework that works for both canonizable (single canonical form) and uncanonizable (no single canonical form) inputs. \n\nWe will add these discussions in our paper.\n\n---\n\n**Q5.** In line 992 (Appendix E.6), why is $\\\\{Pe_i\\\\}_{1\\leq i\\leq n}$ full rank? Shouldn't it have a rank of $\\min(n,d)$?\n\n**A5.** In our paper $d$ refers to the dimension of the eigenspace, so we must have $d\\leq n$. We will clarify this point in the proof.\n\n---\n\nWe thank Reviewer 8tUB again for the valuable review. We hope our response addresses your concerns. If you have further concerns, we are happy to address them in the discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)