Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The authors describe their contributions in the introduction: the analysis of equivariance of self-attention, and how group invariance in the relative positional encoding enables group equivariance of the self-attention.


The authors have a very condensed related work section without going into any detail but with a lot of citations on (non attention) papers about equivariance. Works missed include Equivariant transformer networks by Tai et al., Equivariant multi-view networks (Esteves et al.), SO(3)-equivariant representations (Esteves et al. ), and early work on equivariant function spaces by Hel-Or and Teo (Canonical Decomposition of Steerable Functions).  

But probably most relevant is the missing discussion on equivariance on set networks (incl point cloud networks) and graph networks (Maron and Lipman). There is no positional encoding in point clouds but the value at each element are the coordinates and some parallels can be drawn to positional encodings (for example first few layers of pointnet). 

The authors clearly define self-attention, first with matrices, and then with a functional formulation. The functional formulation is elegant but difficult to follow. The concatenation in the multi-head case is an example of where the vector space formulation allows replacing concatenation with a union. The authors might want to explain the benefits compared to tensor formulation.

Authors first prove permutation equivariance of global self-attention without positional encoding.
The proof in G.4.1 is kind of convoluted and might be clearer using only matrices (if $\Pi$ is permutation than $\sigma(\Pi Q K^T \Pi^T)\Pi V = \Pi \sigma(Q K^T) V$.

Then they prove translational equivariance for relative positional encoding. It is easy to see that relative positional encoding is translation invariant. The step to equivariance has to be followed in the appendix and it would be easier for the reader to provide at least a sketch in the main text. 

The observation about translation paves the ground for generalizing to any group if the positional encoding is invariant to this group. Unfortunately, at this point the discussion becomes very confusing compared to the original "lifting" by Cohen and Welling (2016). While this paper makes the lifting appear as a trick, the main idea of Cohen and Welling is that when one applies group convolution on a quotient space, for example SE(2)-convolution on R^2, the result is automatically invariant in SO(2) since R^2=SE(2)/SO(2). Instead, one performs a group correlation where the output is a function of the group action (not of the quotient space) and after this step one applies a group convolution (also appearing in the spherical CNNs (Cohen)as well as in the icosahedral multi-view networks (Esteves)).

The paper concludes with the claim that linear mappings whose positional encoding is G-invariant are G-equivariant. This is easy to see in the definition of convolution and one can imagine this for linear mappings but it is difficult to see that self-attention is a linear mapping if one looks at eq. 5 and possible definitions of the encoding function (12). I see it through the equivalence proof in Cordonnier but not through the self-attention definition.

Experiments do not show any advantage of equivariant self-attention in z2 or r4 CNNS.

To summarize the paper is interesting but quite difficult to follow. I wish the paper would follow the tensor notation like in the SE(3)-transformers. Authors should justify the superiority of their formalism vs tensors.

Related work should not be condensed with mere listing of citations like \cite{*).

Last: Steerability is claimed in the abstract and the introduction but never mentioned again in the paper. One can somehow see how the positional encoding implies it but a section would be worth to be dedicated to it. 


review_title: This paper studies group equivariance properties of self-attention networks. Permutation equivariance follows from the self-attention definition while group equivariance depends on the definition of the positional encoding.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper develops self-attention mechanisms for group equivariant networks. This is a natural and potentially useful piece of architecture, that, drawing inspiration from its success for text and image analysis, is likely to introduce an effective inductive bias to the group convolution networks. 
The paper is based on the following series of observations. First, represent an image as a set of $N$ feature vectors (e.g.,  pixels). Second, consider group actions $\mathcal{G}$ that can be represented as sub-groups of the permutation group $ֿ\mathbb{S}_N$ acting on the $N$ image pixels. Third, the standard self-attention layer is permutation equivariant. A way to further restrict this equivariance to smaller sub-group of the permutations  $\mathcal{G}<\mathbb{S}_N$ is by adding (or concatenating?) to the set of feature vectors, used as keys in the attention layer, functions which are invariant to this subgroup but not to any larger group. This will lead to operators that are equivariant to the desired sub-group $\mathcal{G}$. Lastly, since doing that directly on the representation of an image leads to larger invariances than desired, the authors work with signals defined over the group and consider regular group action (i.e., change of variables of functions). For example, for the roto-translation group that adds $90$ degrees rotations around the center of the image to the standard translations, this means representing four copies of the image and defining the self-attention layer from the original image and such signals as well as self-attention maps between pairs of such signals. 

Overall, I feel this work offers some interesting observations relating symmetry and equivariance/invariance and self-attention. However, I find this work not fully ready in terms of exposition, ideas delivery and elaboration. The paper is not well balanced between developing and explaining its main contribution (starting page 6), and self-attention background. I understand there is much to cover, but explaining the main constructions in half a page is too short. I think the paper keeps reintroducing positional encoding and self-attention in several formulations and there is much space to save there. Furthermore, the explanations and notations are somewhat not coherent and clear, for example (eqs. 13, 14) are not sufficiently explained and demonstrated. Although i dont think it is a necessary condition for publication of such paper, the results don't show an improvement over "standard" group convolution methods, although the authors claim expressiveness of their self-attention networks is at-least of that of generalized convolutions. Lastly, the last paragraph before section 6, describing the expressive power of these network is not sufficiently developed and justified. 

Some more comments are:
- There are different notations for concat (word and union) and softmax (word and sigma).
- Equation 7 has some repeating unclear part.
- $X_i$ is not defined in equation 5.
- What happens when the group action cannot be represented as subgroup of permutations? (Page 4, lower part). That is, when there is no such injective map as $x$...
- What is $m$ in equation in Proposition 4.1?
- Can $\mathcal{X}$ be continuous space or should is be discrete as well? If continuous how does $y\in\mathcal{X}$ in example 4.2.1 work?
- Sentence after proposition 4.2 is not clear. 
- After definition 4.3 - "we shown" - where?
- What is $m^r$?
- "This allows us to go beyond group discretizations that live in the grid without introducing interpolation artifacts." --> How?
- Before section 5.1 - what is $\mathcal{H}$?
- In Proposition 5.2: shouldn't $\mathcal{L}_g$ also be applied to $\rho$?
- Page 6: "an space".
- Page 7: what are linear mappings on $\mathcal{G}$?
- Last paragraph before section 6: why is this layer maximally expressive for *sub-groups* of $\mathbb{S}_N$.

UPDATE:
I thank the authors for their detailed response and edits. Overall, the authors have addressed my comments, but I have failed to understand some parts. I am still (slightly) positive about this work. >> Please check again for typos.
review_title: good progress, exposition and paper balance not sufficiently good....

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ### Summary
The paper proposes an approach for building group-equivariant self-attention networks. The authors use group-invariant positional encodings, and thus the output of a self-attention layer is equivariant under the actions from the considered group. They empirically demonstrate that group-equivariant self-attention networks have an improvement over their non-equivariant counterparts.

### Pros
1. I enjoyed reading the paper. It has a clear title. The abstract, the intro, and the related work are well-written and give a clear understanding of the content of the paper. The technical sections are coherent and well-structured.
2. The authors propose a general formulation of group-equivariant self-attention networks and rigorously prove their statements.
3. The experiments demonstrate the improvements achieved by the added group-equivariance in image classification on several datasets.

### Cons
I did not find any major weaknesses in the presented paper. I did find some minor issues which, however, do not change the general impression and my decision.
1. While the authors claim that the proposed formulation is general, they only consider 2 compact groups. A group of reflections and a discrete group of rotations. The authors also claim that current computational constraints restrict the possibility of training models with big vicinities until they converge. This issue can be especially important if a group of dilations (scaling group) is considered. The current scale-equivariant models of Bekkers 2020, Sosnovik et al. 2020, Worrall and Welling 2019, Romero et al. 2020 require one to process images with big filters. Is an implementation of a scale-equivariant self-attention network feasible given the current constraints? A discussion of these limitations would make the contribution of the current paper more clear.
2. The authors use long equations with a very nested structure. Reading these equations is complicated given the current notation. The main source of confusion comes from repetitive sequences of brackets. A minor rethinking of the notation may improve the readability. For example, using square brackets when a function is an argument i.e. $\alpha(f)(i, j) \rightarrow \alpha[f](i, j)$

It is a well-written paper. The theory is coherent. The text is easy-to-follow. The experimental section demonstrates a thorough evaluation of the proposed method. 

### After-rebuttal comments
The authors andwered my questions. My decision stays the same

review_title: An interesting paper with good evaluation

final_score: rating: 6: Marginally above acceptance threshold
review_content: ***Summary***

I would firstly like to thank the authors for an interesting read. I enjoyed going through the submission very much.

The submission outlines a general framework to make self-attention equivariant under the action of ‘arbitrary’ groups. The authors go about laying out the mathematical foundations of self-attention from a functional standpoint and then find the conditions that must be satisfied by the individual components of the attention mechanism to make it adhere to the imposed equivariance constraints. Namely, they note that absolute positional encodings must be done away with and that activations must be lifted to a homogenous space of the group in question in order for non-trivial (non-constant) relative positional encodings to be used. They experiment on the MNIST-rot, CIFAR10 and PatchCameylon datasets, but unfortunately the results fall significantly behind standard baselines.



***Pros***

The paper is written very clearly and from what I could see the mathematics appears to be technically sound. 

The authors also provide an in-depth appendix, which contains a lot of details as to group theory and their experiments.

I think the primary objective of making self-attention equivariant is nice. I also think that the conclusion the authors come to makes sense and in someways (with hindsight, having read the paper) is to be expected. 

In the experiments, the choices of which datasets to use make sense from the point of view of the equivariance literature.

I like it how the authors explain that the networks are steerable by design because the group can act on the positional encodings.



***Cons and constructive feedback***

I would like to see a discussion comparing the proposed method with the works of “Affine Self-Convolution” by (Diaconu and Worrall, 2019), and “Attentive group equivariant convolutional networks” (Romero et al., 2019), which are both very close works in this area. What are the differences?

The results are quite disappointing. After the main theory I would have been happy with results en par with existing works, but CIFAR performance of, for instance, 83.7% compared to a baseline of 91.1% really isn’t great. For me this is the main drawback of this work. Furthermore, how are the models comparable with the baselines? Are they matched in terms of numbers of parameters, or size of the activations, or something else? Perhaps this could be a source of the discrepancy between the results.

I would also like to see comparisons with the work of Romero and Diaconu, who have results in their papers.

In the abstract you state that you can impost equivariance to arbitrary groups? Is this really so? Surely just compact, discrete groups?

Equation 1: you introduce the notation ‘sigma’ for the softmax nonlinearity but then immediately use \text{softmax} in eqn 1.

Equation 7: what is the difference between the right hand part of the first line and the second line?

Definition 4.1: is this definition not overly restrictive by focussing on left-regular representations for L and L’? It also precludes the use of irreducible representations as commonly used in the works on group equivariant networks.

Example 4.2.1 I think this could have been stated more simply by specifying the group and action.

Definition 4.3 shown -> show

Proposition 4..2 Nor permutation nor translation -> Neither permutation nor translation

Section 5.2: Good references here would be Theorem 3.1 of “A General Theory of Equivariant CNNs on Homogeneous Spaces”, (Cohen et al., 2018) and Theorem 1 of “B-Spline CNNs on Lie Groups” (Bekkers, 2020). Also, is this statement proven? I couldn’t find it in the submission.

Section 6. Efficient implementation…: I would like to see more detail here since it is not clear in which way the implementation is efficient.

Just a small note: you use American spelling throughout the paper, but missed out behaviour and neighbourhood, which should read behavior and neighborhood.

***Post-rebuttal review***

I have increasing my recommendation to a 6. This is on account of the improvements to the submission by the authors, a detailed rebuttal, and somewhat to align with the recommendations of the other reviewers. I still do find that the experimental results could be improved somewhat, but as another reviewer pointed out, this is not a huge concern within the majority of the equivariance literature. I thank the authors for an interesting read and thank you for a good rebuttal.

review_title: Initial review

Meta-review: The paper introduces group equivariant self attention networks constructed by defining positional encoding that are invariant to the group action considered. This is related to equivariance in set networks . The work is sound and the idea of infusing the inductive bias via the positional encoding is  interesting and leads to improvement  results when comparing transformers with equivariance and without it, nevertheless more work needs to be done to bridge the gap in terms of performance with CNNs as pointed by the reviewers.  Authors made an admirable efforts in the rebuttal and in the revision of the paper clarifying most of the reviewers questions and concerns.   Accept 


Decision: Accept (Poster)