On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups

Risi Kondor; Shubhendu Trivedi

Source-linked AI summary

On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups

Risi Kondor, Shubhendu Trivedi

arXiv:1802.03690v3Feb 11, 2018stat.MLcs.LG

TL;DR

The paper addresses how to define convolution and equivariance for neural networks on data with symmetries beyond translations, including graphs and manifolds. It develops a compact-group framework using representation theory and harmonic analysis, then proves that generalized convolution is necessary and sufficient for equivariance under stated constraints. The resulting theory supplies a mathematical basis for designing symmetry-aware networks, while remaining theoretical rather than algorithmic.

Problem
For graphs, manifolds, and other non-image domains, equivariance matters but the appropriate notion of convolution is not obvious.
Method
The paper develops generalized convolution for compact-group actions using representation theory, noncommutative harmonic analysis, and quotient-space formulations.
Results
A feed-forward network is equivariant to a compact group action if and only if each layer implements a generalized convolution derived from the group convolution formula.
Takeaways & Limitations
The theory gives practitioners a prescription for designing networks on data with non-trivial symmetries, including Fourier-space representations.
Takeaways & Limitations
The paper assumes compact groups in its main theory and does not present new algorithms or neural-network architectures.

Abstract

from arXiv · show

Convolutional neural networks have been extremely successful in the image recognition domain because they ensure equivariance to translations. There have been many recent attempts to generalize this framework to other domains, including graphs and data lying on manifolds. In this paper we give a rigorous, theoretical treatment of convolution and equivariance in neural networks with respect to not just translations, but the action of any compact group. Our main result is to prove that (given some natural constraints) convolutional structure is not just a sufficient, but also a necessary condition for equivariance to the action of a compact group. Our exposition makes use of concepts from representation theory and noncommutative harmonic analysis and derives new generalized convolution formulae.

1. Introduction

The paper generalizes convolution and equivariance from translations to compact-group actions, arguing that convolutional structure is necessary as well as sufficient for equivariant feed-forward networks. It develops this connection theoretically while explicitly not introducing new algorithms or architectures.

Motivation: CNNs apply identical filters across image locations, producing translation-equivariant activations and spatially contiguous receptive fields that support multiscale structure.These roles explain CNNs’ success in image recognition.
Motivation: For graphs, manifolds, and other exotic data, equivariance and multiscale structure remain important, but the appropriate notion of convolution is unclear.
Group-theoretic background: For functions on a compact group G, convolution replaces translation differences with the group operation uv^-1 and integrates using Haar measure.
Contribution: The paper relates group-theoretic convolution to neural-network notions of convolution and proves that a network is equivariant to a compact-group action if and only if every layer implements a derived generalized convolution.
Contribution: The framework handles layer activations defined on homogeneous or quotient spaces rather than directly on the group, requiring a more extensive treatment of group convolution.
Scope: The paper provides theoretical language for future architectures rather than presenting new algorithms or neural-network architectures.

2. Notation

The notation section defines compact set and function-space notation used throughout the paper.

Notation: For a positive integer a, [a] denotes the set {1, 2, ..., a}, and L_V(X) denotes all functions from X to vector space V.

3. Equivariance in neural networks

The paper models neural networks as sequences of function-valued layers, then characterizes convolutional and equivariant structure through group actions on their index spaces.

Network abstraction: A feed-forward network is represented as a sequence of layers whose activations are functions indexed by sets X_l and valued in vector spaces V_l.Each layer applies a linear map followed by a pointwise nonlinearity.
CNNs: In the image setting, inputs are extended from an m × m grid to Z^2 with zero values outside the image region.
CNNs: Traditional CNN layers use discrete convolution with a filter, typically keeping filter width small while stacking multiple layers.The cited examples place filter width around 3–10 and depth from a few layers to several dozen.
CNNs: Convolution shares filters across image locations, reducing parameters and allowing detected features to transfer across translated positions.
Group actions: The general framework begins with a group G acting on a set X and induces a corresponding action on functions over X.
Group actions: When the action is transitive, every point is reachable from any other and X is called a homogeneous space of G.
Equivariance: Equivariance requires maps between function spaces to commute with the induced group actions, while a network is equivariant when each layer transforms correspondingly with the input.
Equivariance: Invariance is the special case where the group action on outputs is the identity, enabling equivariant networks to produce invariant representations through a final layer.

4. Convolution on groups and quotient spaces

The paper generalizes convolution from ordinary signals to functions on compact groups and quotient spaces, adapting it to the homogeneous spaces used by neural-network layers. These constructions determine the output space through quotient symmetries and expose structured Fourier sparsity.

Convolution on groups: Ordinary convolution extends naturally from signals on R or Z to higher-dimensional domains, including the compact-group setting studied here.The group formulation replaces translation differences with group operations and uses Haar measure; compactness provides essential uniqueness of that measure.
Convolution on quotient spaces: Neural-network activations live on homogeneous spaces of G, so generalized convolution must connect functions across potentially different quotient spaces.The paper presents the main exposition for finite or countable groups and notes that continuous-group generalization is straightforward.
Convolution on quotient spaces: The paper defines convolution for functions whose domains are left or right quotient spaces of a group, not only for functions on the group itself.Groups themselves are included as quotient spaces using the trivial subgroup, while quotient-space choices can restrict the summation domain or impose output symmetries.
Special cases: When one input is defined on G and the other on G/H, their convolution is constant on left H-cosets and therefore has domain G/H.Analogous reductions show how input symmetries can be transferred into the convolution output or kernel domain.
Special cases: For f on G/H and g on H\G/K, convolution maps G/H to G/K, making this case central for generalized neural-network layers.The construction combines left and right quotient symmetries and is the relevant definition for mapping between homogeneous spaces.
Relationship to Fourier analysis: Fourier transforms on quotient spaces retain the representation-matrix sizes of transforms on G but acquire characteristic sparsity patterns.For G/H, H\G, and H\G/K, nonzero blocks are selected by trivial-representation conditions under the relevant subgroup restrictions.

5. Main result: the connection between convolution and equivariance

The paper defines G-convolutional networks for compact-group actions and proves that equivariance is equivalent to generalized convolutional structure under the stated quotient-space constraints.

Definition: A G-CNN is a feed-forward network whose layer index sets are quotient spaces G/Hi and whose linear maps are generalized convolutions.The definition applies to each linear map φ1, …, φL.
Main theorem: The main result states that a feed-forward network is G-equivariant if and only if each layer implements generalized convolution.The theorem assumes compact G and layer index sets Xℓ=G/Hℓ for subgroups Hℓ.
Proof strategy: The forward proof shows that generalized convolution is equivariant, and pointwise nonlinearities preserve equivariance through every layer.The argument proceeds inductively across layers using transitivity of equivariance.
Proof scope: The equivariance proof extends beyond scalar functions to vector-valued activations and matrix-valued filters.The stated generalization covers fℓ:Xℓ→Vℓ and χℓ:Xℓ→Vℓ−1×Vℓ.
Proof strategy: The converse direction is more technical and is deferred to the Appendix.It requires representation theory and generalized Fourier transforms.

6. Examples of algebraic convolution in neural networks

The paper interprets rotation-equivariant, spherical, and graph message-passing architectures through compact-group actions, quotient spaces, and generalized convolution.

6.1. Rotation equivariant networks: Steerable image models use filters replicated at rotational angles to obtain a group-theoretic generalization of equivariance.The examples include discrete rotations and continuous rotations modeled through SO(2).
6.1. Rotation equivariant networks: Worrall et al.’s Fourier-basis expansion and weighting amount to convolution on SO(2), although its nonlinearity requires an additional equivariance condition.The condition restricts which Fourier components may mix; analyzing it group-theoretically is outside this paper’s scope.
6.2. Spherical networks: Spherical convolutional architectures use SO(3) rotations, with the sphere represented as the quotient space SO(3)/SO(2).The relevant Fourier representations are Wigner matrices, whose middle columns correspond to spherical-harmonic coefficients.
6.2. Spherical networks: Cohen et al.’s spherical networks use noncommutative convolution, pointwise nonlinearities, and SO(3) Fourier transforms to obtain equivariance.They do not prove the converse that equivariance implies convolutional structure.
6.3. Message passing neural networks: Message-passing neural networks can be viewed as group-convolutional networks under permutation actions on vertex subsets.A k-subset is modeled as Sn/(Sk×Sn−k), with non-neighborhood subsets assigned zero labels.
6.3. Message passing neural networks: Permutation equivariance strongly restricts convolutional filters while retaining a richer framework than traditional neighbor-summing message passing.The corresponding layer convolutions can be described in the Fourier domain using sparse representation structures.

7. Conclusions

The paper gives convolution a precise group-theoretic meaning and concludes that, under its setting, equivariance and convolution are equivalent; it recommends Fourier representations for symmetric data.

7. Conclusions: For feed-forward networks subject to a group action, equivariance holds if and only if the network respects the paper’s generalized notion of convolution.This conclusion identifies convolutional structure as necessary as well as sufficient in the stated setting.
7. Conclusions: The theory is intended to guide neural-network design for data with non-trivial symmetries, including spherical data.The paper particularly advocates Fourier-space representations.
7. Conclusions: A homogeneous space is a group action in which every point can be reached from every other point by some group element.Fixing an origin identifies points through group elements, with stabilizers yielding quotient-space descriptions.
7. Conclusions: The framework generalizes ordinary convolution through group actions, including noncommutative settings where Fourier components are matrix-valued.For compact groups, group representations provide the corresponding generalized Fourier transform and convolution theorem.
7. Conclusions: The paper’s generalized convolution extends to vector- and matrix-valued functions, supporting multilayer networks with multiple channels.The definitions cover dot products, matrix-vector products, and reverse matrix-vector products.

C. Proof of Proposition 1

The proposition’s proof uses invariance properties of quotient-space lifts and representation-theoretic orthogonality to characterize Fourier components associated with subgroup actions.

C. Proof of Proposition 1: The proof introduces subgroup and group representation lemmas before establishing the proposition’s Fourier-structure claims.The argument proceeds after presenting the relevant lemmas.
C. Proof of Proposition 1: Functions on quotient spaces lift to group functions with corresponding right, left, or two-sided subgroup invariance.These invariance properties depend on whether the original domain is G/H, H\G, or K\G/H.
C. Proof of Proposition 1: The sum of an irreducible representation over group elements vanishes unless the representation is trivial.This orthogonality fact is used as a key representation-theoretic ingredient.
C. Proof of Proposition 1: Fourier-transform entries are expressed through inner products with representation matrix coefficients, whose orthogonality separates distinct representation components.The transform is treated as a unitary change of basis.
C. Proof of Proposition 1: Restricting an irreducible representation of G to a subgroup H generally produces a reducible representation that decomposes into irreducibles of H.A unitary change of basis realizes this decomposition.

C.0.1. PROOF OF PART 1

The proof factors the Fourier transform using the decomposition of group elements into coset representatives and subgroup elements. Nontrivial subgroup representations eliminate the corresponding Fourier columns.

Every group element is uniquely written as u = gh, with g representing a coset and h belonging to H.
Restricting ρ to H decomposes it into irreducible representations µ1, µ2, and so on.
Terms associated with nontrivial µi vanish, zeroing the corresponding columns of the Fourier transform.

C.0.2. PROOF OF PART 2

The proof of Part 2 proceeds analogously to Part 1, using a factorization based on writing group elements as hg. The resulting argument establishes the corresponding row-wise statement.

The proof uses the decomposition u = hg and a factorization analogous to the one used in Part 1.
The argument concludes by applying the preceding factorization to obtain the required result for the second case.

D. Proof of Proposition 2

The proposition’s proof treats countable groups with sums and extends the argument to continuous compact groups by replacing sums with Haar-measure integrals.

The proof first assumes that G is countable.
For the continuous case, the same argument uses integrals with respect to Haar measure instead of sums.

E. Proof of Theorem 1

The proof characterizes equivariant linear maps through representation-theoretic decomposition and Fourier components. It then shows that the resulting layer maps are precisely generalized convolutions, establishing the reverse direction of Theorem 1.

E. Proof of Theorem 1: The proof uses representation theory, generalized Fourier transforms, and two versions of Schur’s Lemma.
E. Proof of Theorem 1: Equivariant linear maps send irreducible subspaces to irreducible subspaces with equivalent representations.
E. Proof of Theorem 1: Equivariance preserves corresponding isotypic components, so each output Fourier component is a linear function of the matching input component.
E. Proof of Theorem 1: The Fourier-space maps are constrained to right multiplication by matrices, while Schur’s Lemma restricts allowable maps to scalar identities in the relevant cases.
E. Proof of Theorem 1: Because allowable maps are closed under composition, coefficient constraints force each Fourier-space map to have the form M 7→ MB.
E. Proof of Theorem 1: Defining χℓ as the inverse Fourier transform of the matrices Bi yields φℓ(fℓ−1) = fℓ−1 ∗χℓ, proving that each layer is a convolution.