A Canonicalization Perspective on Invariant and Equivariant Learning

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.

Paper

Similar papers

Peer review

Reviewer 8tUB6/10 · confidence 3/52024-07-11

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.

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. - The primary method, OAP, uses Gram-Schmidt orthogonalization to canonicalize eigenvectors and resolve eigenvalue degeneracy (or basis ambiguity), which is also straightforward.

Weaknesses

### **Major**: The overall writing could be improved. The authors claim to present a unified and essential view of equivariance learning, but the application is limited to the orthogonal group and eigenvector canonization. I would expect more examples to justify the theorem, such as the canonization view on the translation group or the product group $E(d)\times S_n$, similar to what frame averaging [1] achieves. ### **Minor**: - The OAP results appear to be marginal, though considering this as a theoretical paper compensates for this shortcoming. I would like to know what is the result of MAP + LSPE in ZINC 500k compared to OAP + LSPE. - Please add references in the main text to the appendix for proofs and n-body experiments to enhance readability. - I suggest the authors add related works including [2] and [3]. I also hope the authors can give a discussion about the highly related concurrent works [4] and [5] to strengthen the contribution, not necessarily in this rebuttal since they are both new papers accepted in this ICML 2024, but please do consider it after this rebuttal. [1] *Frame Averaging for Invariant and Equivariant Network Design*. Omri Puny, et al. ICLR 2022. [2] *Learning Probabilistic Symmetrization for Architecture Agnostic Equivariance*. Jinwoo Kim, et al. NeurIPS 2023. [3] *A Hitchhiker’s Guide to Geometric GNNs for 3D Atomic Systems*. Alexandre Duval, et al. [4] *Equivariant Frames and the Impossibility of Continuous Canonicalization*. Nadav Dym, et al. ICML 2024. [5] *Equivariance via Minimal Frame Averaging for More Symmetries and Efficiency*. Yuchao Lin, et al. ICML 2024.

Questions

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)$?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors do mention one of the limitations is that OAP does not fully resolve the optimality of eigenvector canonization under permutation equivariance.

Reviewer TcMZ5/10 · confidence 3/52024-07-12

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.

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. The 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. Unfortunately, I am unable to comment on the numerical section, as I am not familiar with these experiments. However, given the problems in the rest of the manuscript, I urge the other reviewers to have a closer look at the numerical evaluation.

Questions

Below I provide a number of comments and questions. * First and foremost, while I realize the authors must be approaching from the graph side of the literature - within frame averaging the term used in all papers is ‘canonicalization’, and not ’canonization’, and I would suggest for consistency to refer to it as such, to avoid creating confusion. * In subsection 2.1, as soon as frame averaging is presented, an assumption is made about finiteness of the group - but is never stated. Furthermore, after section 3.2, the vector spaces considered becomes simply finite dimensional Euclidean spaces. * Line 87 and 95 - universal approximation is claimed, however neither a citation, nor a theorem reference is provided. * In 110 you refer to LapPE. Ideally after introducing a term, you would directly provide a reference to it, instead of at the end of the next sentence. * Line 128 - why are automorphisms of the input a major obstacle in analyzing complexity of frames? * Line 144 - what you refer to as contractive ‘canonization’, is usually referred to as orbit canonicalization. Eg see https://arxiv.org/abs/2402.16077 * Line 175 - the same thing is stated twice. * In 3.3 and onwards, MAP is mentioned, however, since the work is built on top of it, an introduction to MAP (or at least an outline of what it is) should be present in the paper. * In line 205 what is the norm of a vector? * Whenever a theorem is stated, a reference to where the proof can be found should be stated. * In both section 3 and 4 the actual problem being solved is never stated, making it very difficult to follow. By this I mean that given a matrix, you find its eigenvectors, and wish to construct a function which is permutation equivariant … * Line 262 - what is the hash function? I can not seem to find any information about what it is, not in numerical experiments either, could you point to where this information is located? * You mention that you have not been able to show that OAP is optimal - given the indices may not exist, how could it be optimal? * Line 304 - you never say what FA/CA is - I presume this is frame averaging and canonisation averaging? * Whenever superiority or optimality is claimed in the sense of the new definitions, it would be useful to refer the reader to the definition, as it is not clear whether superiority is meant as a technical term, or simply as a qualitative assessment. (e.g. line 204)

Rating

5

Confidence

3

Soundness

3

Presentation

1

Contribution

2

Limitations

See weaknesses.

Reviewer MgpB6/10 · confidence 3/52024-07-14

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.

Strengths

1. The paper is well-written and nicely explained. 2. The paper provides strong theoretical results. 3. 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) 1. Line 98: $G_X$ is not define before. I think it should be defined here instead of Line 129 2. proof of theorems in the supplementary is not in order of the main text.

Questions

1. Line 138: “ This converts the problem of finding a G-equivariant subset of the group to finding a G-invariant set of inputs.” - further explanation of this would be great. 2. Line 175: “The canonization size |C(X)| may differ for different inputs.” — what does the size of |C(X)| tell about the input X?

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

4

Limitations

The authors discussed the limitations.

Reviewer y3Wh6/10 · confidence 3/52024-07-14

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.

Strengths

- The paper is well-written. - 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. - Experimental results show that the proposed method is expressive and computationally more efficient than frame averaging. - 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. - In Tab. 2, the practical advantage of canonization over frame averaging in computational complexity for graph dataset seems negligible because of the huge absolute compute time. In Tab 2., how is the averaging done over such a large set? Please provide any preprocessing time required for such computations as well (if applicable). - Although the initial results in the paper are applicable to the general area of equivariant learning, the applications of the initial results seems to be only useful in the context of equivariance to sign and basis. But the title of the paper has no mention about sign and basis, which makes it look more generally useful than what the experiments indicate.

Questions

- In Tab. 1, out of curiosity what happens if we use only GIN+ID? I am curious because GIN+ID is universal (unlike GIN), so, the results on GIN+ID would help understand the benefit of permutation equivariance. Also, some results/plots on the convergence benefits from equivariance would help. - Are there any other domains where the results on the connection between frame averaging and canonization is directly applicable?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Reviewer TcMZ2024-08-09

Thanks to the authors for their clarifications and answers. I would like to emphasise that my only concern at this point remains in readability of the paper on two fronts: problem statements and theorem statements. As long as these two are improved in the revision in line with the comments, I would be happy to raise my score.

Authorsrebuttal2024-08-10

We thank Reviewer TcMZ for the prompt response. We clarify our problem statements and theorem statements in the following points, and we will add these discussions to the camera-ready version of our paper for better readability. --- ### Problem Statements Our paper consists of two parts, each addressing different problems. We describe the problems in these sections in detail as follows: 1. **Section 3** is focused on the theoretical problem of finding a principled way (i.e., canonicalization) to characterize the complexity of frames $\mathcal{F}(X)$ and frame averaging, a general class of invariant and equivariant learning methods. We have included the definitions of invariant and equivariant learning in Section 2, and the definitions of frames frame averaging in Section 2.1. We will state the main problem more clear in the beginning of Section 3 for better readability. 2. Guided by the theoretical insights in Section 3, **Section 4** is to design better or optimal canonicalization algorithms for a widely appeared class of problems, the sign and basis invariance of eigenvectors. Specifically, we aim to design a canonicalization algorithm $\mathcal{C}$ operating on eigenvectors $\mathbf{U}\in\mathbb{R}^{n\times d}$, that is **invariant** to sign/basis transformations, **equivariant** to permutation transformations, and outputs a set of eigenvectors $\mathbf{U}^*\in\mathbb{R}^{n\times d}$ in the **same eigenspace** as $\mathbf{U}$. We consider two settings of sign and basis invariance: without (Section 4.1) and with (Section 4.2) permutation equivariance, corresponding to different problem scenarios. We will make it more clear in the beginning too. --- ### Theorem Statements We understand that we define some notations out of the theorems, making them less self-contained and easy-to-understand. To ease your concerns, we will define the notations more clearly, point out the key messages of the main theorem, and add references to previous definitions. Below we give two examples of the modified theorem statements: - **Theorem 4.1.** Given a set of eigenvectors $\mathbf{U}\in\mathbb{R}^{n\times d}$, let $\mathscr{P}=\mathbf{UU}^\mathrm{T}$ denote the projection matrix of the eigenspace. Let $\mathbf e_1,\dots,\mathbf e_n$ denote the standard basis vectors. Then, there exists indices $1\leq i_1<\cdots<i_d\leq n$, such that for all $1\leq j\leq d$, we have $\lVert\mathscr P\mathbf e_{i_j}\rVert>0$, and the vectors $\mathscr P\mathbf e_{i_1},\dots,\mathscr P\mathbf e_{i_d}$ are linearly independent. - **Theorem 4.3.** Let $\alpha_i\ (i=1,\dots,n)$ be the outputs of the hash function in the OAP algorithm defined in Equation (4), and let $i_j\ (j=1,\dots,d)$ be the indices found in Algorithm 3. Then, the MAP algorithm is equivalent to the OAP algorithm by taking $\alpha_i=\lVert\mathscr P_i\rVert$ for all $1\leq i\leq n$ and $i_j=j$ for all $1\leq j\leq d$. The FA-lap algorithm is equivalent to the OAP algorithm by taking $\alpha_i=\mathscr P_{ii}$ for all $1\leq i\leq n$. We will modify all the theorems in our paper similarly to enhance readability and self-containedness. These changes will be reflected in the camera-ready revision of our paper. We hope these changes address your concerns. If you have further concerns or suggestions, please feel free to reach out.

Authorsrebuttal2024-08-12

Could you please check the revision examples?

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

Reviewer TcMZ2024-08-13

I would like to thank the author for illustrating the examples of revisions and I would say that these are siginificantly better than their current versions. As long as these are included and overall presentation of the paper is improved, I am happy to raise the score.

Authorsrebuttal2024-08-13

Thanks

We will definitely revise the paper according to your suggestions. Thanks again and have a nice day!

Reviewer y3Wh2024-08-11

Thank you for your response

I thank the authors for their clarifications. For readability, please provide references in the main text to the results in the appendix. Overall, I am happy to increase my score since most of my concerns are clarified. I still find the applications/usefulness limited and the title of the paper seems more general than the applications.

Authorsrebuttal2024-08-12

Thanks

We are glad to hear that our responses have addressed your concerns. We will incorporate references in the main text to the results in the appendix and revise the title to more accurately reflect the content of the paper in the revision. Thank you again and have a good day!

Reviewer MgpB2024-08-12

Thanks for the response.

Reviewer 8tUB2024-08-12

Official Comment by Reviewer 8tUB

Thank you for your responses and I am satisfied with them. Please do include these discussions in the paper in future revisions. I have changed the score accordingly.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC