A Canonicalization Perspective on Invariant and Equivariant Learning

We thank Reviewer 8tUB for the constructive review and acknowledging our theoretical contributions. We address your main concerns as follows.

---

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.

A1. Thanks for the suggestions. We will keep improving the writing to be more clear and readable.

For the application of canonization, we provided multiple application scenarios of canonization in the paper:

• 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.
• 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).
• 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).
• rotation equivariance: In Appendix D, we applied canonization to achieve rotational equivariance of particles in PCA-frame methods.

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

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

---

Q2. I would like to know what is the result of MAP + LSPE in ZINC 500k compared to OAP + LSPE.

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.

---

Q3. Please add references in the main text to the appendix for proofs and n-body experiments to enhance readability.

A3. Thanks for the suggestion. We will provide these references in our revision.

---

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.

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.

More 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:

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

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

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

We will add these discussions in our paper.

---

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

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.

---

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

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.

---

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.

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.

References:

[1] Xu, Keyulu, et al. "How powerful are graph neural networks?" ICLR 2019.

---

Q2. In addition to that, it is not immediately clear where the ‘canonization’ view can be useful, beyond the example provided in this paper.

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.

• 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.
• Empirically, we show that canonization can be applied in many different scenarios with different types of symmetries:
  • 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.
  • 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).
  • rotation equivariance: In Appendix D, we applied canonization to achieve rotational equivariance of particles in PCA-frame methods.

---

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.

A3. Thanks for the suggestion. We agree with this and will switch to "canonicalization" in the revision for better consistency.

---

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.

A4. This is true. We will clarify these assumptions in our paper.

---

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

A5. Thanks for pointing out. We will cite the frame averaging paper after these claims.

---

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

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.

---

Q7. Line 144 - what you refer to as contractive ‘canonization’, is usually referred to as orbit canonicalization.

A7. Thanks for pointing out. We will switch the term to orbit canonicalization for consistency.

---

Q8. In line 205 what is the norm of a vector?

A8. On line 205 $|\cdot|$ refers to element-wise absolute value. We apologize for the confusion and will clarify this in the theorem.

---

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 …

A9. Indeed, we would state the problem more clearly for better readability.

---

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?

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.

---

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

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.

---

Q12. The mentioned typos and suggestions.

A12. We will fix them in the revision.

---

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

We thank Reviewer y3Wh for the constructive review. We address your concerns as follows.

---

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.

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.

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

---

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.

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.

---

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.

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:

• permutation equivariance of graph data in the EXP experiment;
• rotational equivariance of particles In Appendix D.

These 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!

---

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.

A4. Following your suggestion, we evaluate GIN with two kinds of commonly used node IDs: one-hot node ID and random node features.

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

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

References:

[1] Ma et al. Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding. NeurIPS 2023.

---

Q5. Are there any other domains where the results on the connection between frame averaging and canonization are directly applicable?

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.

---

We hope our response addresses your concerns. If you have further concerns, we will be happy to address them during the discussion period.

We thank Reviewer MgpB for the constructive review. We address your concerns as follows.

---

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)

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). Following your suggestion, we will add the full experiment results in our paper to make it more complete.

---

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.

A2. Thanks for pointing this out. We will define $G_X$ before line 98 and adjust the order of proofs in the appendix.

---

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.

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:

• Firstly, since equivariance is a strong requirement, it is often easier to directly construct an invariant canonical form instead of an equivariant frame.
• 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.
• 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.

We will add this elaboration in the revision.

---

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?

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.

---

We hope our response addresses your concerns. If you have further concerns, we will be happy to address them during the discussion period.