Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a group-theoretic framework for equivariant subsampling. Based on a similar approach to ref [3] in the case of translations, the idea is to subsample according to intrinsic landmarks and keeping track of the shifts involved. The framework introduced can handle this procedure for general symmetry groups by seeing the subsampled space as a subgroup, and the shifts are stored as elements of the quotient of the original group and the subgroup.
The method is evaluated in the context of VAEs, where it is shown that an architecture using equivariant subsampling and upsampling is capable of fully disentangling covariant from invariant features, and, depending on the group used, is shown to generalize perfectly to unseen object positions.
main_review: Strangely, my main criticism of this paper is also the main reason I find it interesting. A more pedestrian way of describing what has been done is registration of the signal among a collection of possible transformations, according to some intrinsic signal property, while not forgetting the selected registering transformation. In this sense the group-theoretic approach is (an even somewhat restrictive) syntactic sugar. That said, I consider this a neat framework that can represent many previous approaches, that guides implementations, is shown to work in experiments, and may provide leads for extensions in the future. Also, it shows an example of a non-trivial equivariant transformation, where part of the information is absorbed into an index.

It should be noted that registration is inherently unstable no matter what procedure is used to determine the shift (see e.g. https://arxiv.org/abs/1203.1513 2.1ff). There will always be a signal exhibiting the discontinuity of the map from signal to shift parameter (consider a signal with two local maxima in the l1-norm used here, with one peak epsilon/2 lower than the other, but far away in terms of position. A perturbation increasing the lower peak by epsilon will make the registration landmark jump. In general, a map between metric spaces of different dimensionality cannot be continuous in both directions). It may be interesting to explore this a little bit to see whether there are adversarial examples with practical impact.

The groups explored here, while providing a proof of concept, are really not very interesting. I would have been much more delighted to see this framework used to tackle e.g. continuous, or at least more fine-grained discrete rotational steps. The VAE data set samples, by virtue of being one shape on a constant background, would not pose any difficulty (i.e. border effects from e.g. periodic wrap-around) in applying these.

Given the memorization of shifts, can you envision a way of being able to sample from the GAE latent? Would it require putting a probability measure on the shifts?
limitations_and_societal_impact: Some limitations were discussed.
I do not foresee potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a method to equip discrete-group convolutional neural networks (GCNNs) with a perfectly equivariant subsampling layer. The method relies on a non-fixed sampling grid which is dynamically chosen as an equivariant function of the current input. This method enables encoder-decoder architectures where each layer is equivariant to the global action of the discrete group on the input of the model. Experimental results confirm the accurate equivariance and the improved generalization of the models.
main_review: The proposed equivariant subsampling is a clear imrpovement over common down-sampling methods. The main idea seems intuitive and simple to implement, making it probably very easy to adopt in many existing equivariant models.

I found the presentation quite clear overall and I liked the intuitive description of the subsampling idea using the 1D translations as an example. However, I think the introduction to the abstract groups setting was a bit fast; to keep the paper self contained, I think it would be useful to at least define group convolution in the main paper.

There are a number of issues that I think should be addressed more explicitly (see below).

While the reconstruction tasks are certainly important and clearly show the benefit of using this subsampling method, I think some simple experiment on a standard benchmark such as MNIST-rot (for classification) should be included to compare the proposed method with other equivariant models from the literature.

I think the discussion in B.1 should be included more prominently in the main paper. I find the stochastic alternative proposed in B.1 less satisfying. This is not necessarily an issue since I find the subsampling method proposed in the main paper a very nice contribution, but I believe this limitation should be discussed more explicitly in the main paper.

The case of symmetric inputs appears also in Fig. 3 for the ellipse and the square, so some comments about this should also be included in the experimental section.

If I understand correctly, the proposed subsampling method guarantees perfect global equivariance but can reduce the local equivariance. This is because the sampling grid depends on the global image. This means that changing a single pixel in a region of the image far away from a local patter can change the pixels selected around that local patter for the downsampling. Because the downsampling is also performed without any smoothing of the features, this can potentially lead to a completely different prediction for that pattern. Clearly, this is a worst-case scenario and it is not clear yet how this affects the stability of the model in practice.
Still, some comments about this potential instability should be included among the limitations.

Finally, I wonder how this subsampling method affects the performance of a model when using mini-batches, since different samples in the batch might require different sampling grids.

EDIT: Having read the author response, I have decided to maintain my rating.
limitations_and_societal_impact: I don't see any issue with the authors' comments on the societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose subsampling and upsampling layers that are equivariant to common transformation groups. These constructions are used to design autoencoders consisting of layers that alternate between group equivariant convolutions and group equivariant subsampling/upsampling layers. The result is that the entire autoencoder is *exactly* group equivariant. Experiments on translations, translations+rotations, translations+rotations+reflections for simple images with single/multiple objects clearly show the improved performance over subsampling methods that are not group-equivariant.
main_review: The core of the paper is group equivariant subsampling method that is clever and simple to implement. It can be easily integrated with the architectures which already employ group equivariant convolutions and can be composed with each other to form a deep network. Although the simple method shown in Eqn. 11 may not always have a unique solution, as in the case of feature maps with symmetries, the authors propose a way to overcome this problem.  

The main weakness in the paper would be that in all the experiments, the feature maps are all images on the plane. I would have liked to see how easy or difficult it is to integrate these subsampling layers in the case of spherical image inputs with the feature maps defined on SO(3). And whether this would lead to improved performance in practice. It would also be useful to other researchers to add an another line in the tables with coset pooling as the subsampling operation to see how it affects final reconstruction performance. 

The practical significance of this method also deserves more discussion in the paper. The experiments are okay in terms of demonstrating the main strengths of the proposed work. However, I would have like at least one experiment with a more realistic dataset, like a dataset of human faces perhaps undergoing some deformations. Related to this, what about larger transformation groups like piece-wise affine transforms or very large groups like 2D diffeomorphisms (used in facial expression modeling and medical image registration)? My guess is constructing the group-equivariant convolutions for these groups is the much bigger problem rather the group-equivariant subsampling itself. 

The authors do mention that for objects with background, the first step is to remove the background before group-equivariant autoencoding and that local symmetries become more important as most scenes have several objects. These are indeed challenging tasks and perhaps this paper can provide a starting point to attack these problems. 

The related work section should include other works which are similar in spirit to group equivariant autoencoders. This includes the following list of papers that is not exhaustive:

1. Deforming autoencoders: Unsupervised Disentangling of Shape and Appearance ECCV 2018 https://openaccess.thecvf.com/content_ECCV_2018/html/Zhixin_Shu_Deforming_Autoencoders_Unsupervised_ECCV_2018_paper.html

2. Extracting invariant features from images using an equivariant autoencoder, ACML 2018, http://proceedings.mlr.press/v95/kuzminykh18a.html

3. Rotation-Invariant Autoencoders for Signals on Spheres, https://arxiv.org/abs/2012.04474

4. Capsule networks
limitations_and_societal_impact: The authors have discussed the limitations of the paper.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes and evaluates equivariant subsampling and upsampling operations for group convolutional networks, which include vanilla CNNs as a special case. These operations address the issue that conventional subsampling and upsampling operations are only equivariant under the action of a subgroup of symmetries. The models have the property to disentangle the appearance of objects from their G-pose, which allows to build disentangled group equivariant autoencoders.

As a simple introduction, the authors formulate their method initially for the special case of $G = \mathbb{Z}$ being the 1-dimensional translation group. In contrast to conventional subsampling operations, which sample the values on a grid $c\mathbb{Z}$ with spacing $c$, the equivariant subsampling operation samples features on a shifted grid $c\mathbb{Z} + i$, where $i = 0, \dots, c-1$ is an integer offset that is predicted from the signal itself via some equivariant function. The tuple of subsampled features and the integer offset are shown to transform in an equivariant way under the action of the full symmetry group $\mathbb{Z}$. If multiple subsampling layers are successively applied in a deep network, each of them adds a new offset value to a sequence of offsets. When eventually pooling to the trivial group $G=\{e\}$, the resulting feature is position invariant and all position information is encoded in the offset sequence. Upsampling layers are accordingly taking a low-resolution signal and an offset and embed it with this offset into a higher-resolution grid.

These constructions are in the obvious way generalized to feature maps on arbitrary discrete groups $G$: The lower resolution sampling grid is here given by a coset $pK \in G/K$ of a subgroup $K<G$ in $G$. The group equivariant subsampling operation is therefore producing a tuple which consists of a subsampled signal on the coset and the coset (offset) itself. To upsample such a signal, it is embedded in the coset of the supergroup. Lemma 2.1 and Proposition 2.2 assert the full $G$-equivariance of these operations.

The integer offset, or, more generally, coset, needs to be computed via any equivariant map from the input signal to the space of cosets. A simple choice, made by the authors, is that coset $gK$ that consist to the argmax group element $g$ of the signal's l1-norm.

The equivariant subsampling layers are used to construct various group equivariant autoencoders (GEAs), which are evaluated against baseline autoencoders that are constructed from group convolutions but use conventional subsampling and upsampling layers. GEAs are empirically shown to be exactly equivariant and to generalize perfectly out of distribution. This is not the case for the baseline models, whose conventional subsampling and upsampling layers break the models' overall equivariance. The disentanglement of object appearance and $G$-pose in the autoencoders' latent space is in figure 3 (left) shown to allow for an independent manipulation of these factors. GEAs perform on single and multi-object reconstruction tasks significantly better than the baselines.
main_review: The submission addresses an important open problem of conventional and group equivariant convolutional networks, namely the lack of equivariance in their downsampling and upsampling layers. While other common types of layers like convolutions, nonlinearities or batch normalization have equivariant counterparts, contemporary models are usually using non-equivariant or smoothing based subsampling layers, which prevents the exact equivariance of the full model. The proposed method solves this issue, allowing to build fully equivariant models. As demonstrated, this can be used to disentangle an object's pose from its appearance and generally improves the model performance.

The paper is well written and mathematically sound. All claims are proven in the appendix and demonstrated empirically. The decision to introduce the construction on the simple and practically relevant special case of $G=\mathbb{Z}$ being the translation group helps to make the idea accessible to a broader audience. I am confident to be able to reimplement the model and reproduce the experiments.

While any equivariant map is suitable to predict the grid offset (or coset), the authors choose the argmax of the feature vectors' norms. This choice seems to be very unstable under noise on the input, which should be investigated empirically. What happens in degenerate cases like reconstructing the top row in figure 3 (right) with $z_\text{eq}$ taken from the bottom row, whose ellipses are $C_2$-symmetric?
A more robust choice of equivariant map could be based on coset average pooling, followed by an argmax over cosets or on the phase offset of a harmonic basis function expansion of the features on $G$. The authors should discuss different choices of such maps and empirically investigate their stability.

It seems intuitively necessary that equivariant sub/upsampling operations are based on an offset that is computed from the signal itself - can this conjecture be proven formally?

While the experimental section is convincingly demonstrating the merits of the method, it does not include a standard task like image classification. It would be interesting to see the performance gains on such tasks instead of only auto-encoding reconstruction errors.

Overall, the submission solves an important problem of equivariant networks, and I would be happy to give it a very positive score. My low score should be understood as an incentive to extend the empirical evaluation, in particular on the choice of the equivariant offset predictor.
limitations_and_societal_impact: The authors discuss limitations of the method appropriately. No immediate negative societal impacts are to be expected.
review_title: null

Meta-review: This paper introduces a novel method for subsampling along the orbit of a group action, which maintains the equi-variance property. After the rebuttal, all the reviewers agreed that this work is interesting and recommended to accept it. Thus, I will suggest to accept this paper yet the authors should incorporate the relevant suggestions of each reviewer.
Decision: Accept (Poster)