Source-linked AI summary
Equivariance Through Parameter-Sharing
Siamak Ravanbakhsh, Jeff Schneider, Barnabas Poczos
TL;DR
The paper asks how to characterize and construct neural-network equivariance under discrete group actions without confusing it with broader accidental symmetries. It links equivariance to parameter symmetries, proposes two parameter-sharing schemes, and shows that the sparse construction provides unique equivariance under semi-regularity conditions while the designs can extend to multilayer settings.
Problem
The paper addresses how to distinguish a desired group equivariance from broader permutation symmetries, since even constant functions can be equivariant to every permutation group.
Method
The paper relates neural-layer equivariance to symmetries of a colored parameter-sharing structure and proposes dense and sparse schemes for designing those symmetries.
Results
The proposed schemes achieve GN,M-equivariance, and the sparse construction is uniquely GN,M-equivariant when GN and GM are semi-regular.
Takeaways & Limitations
Parameter-sharing offers a simple, computationally efficient route to prescribed discrete equivariance while, under stated conditions, retaining sensitivity to other permutation groups.
Takeaways & Limitations
The dense design can be inefficient, may require filters as large as the input image, and does not guarantee unique equivariance; the stronger sparse guarantee requires conditions such as semi-regularity.
Abstract
from arXiv · showhide
We propose to study equivariance in deep neural networks through parameter symmetries. In particular, given a group $\mathcal{G}$ that acts discretely on the input and output of a standard neural network layer $φ_{W}: \Re^{M} \to \Re^{N}$, we show that $φ_{W}$ is equivariant with respect to $\mathcal{G}$-action iff $\mathcal{G}$ explains the symmetries of the network parameters $W$. Inspired by this observation, we then propose two parameter-sharing schemes to induce the desirable symmetry on $W$. Our procedures for tying the parameters achieve $\mathcal{G}$-equivariance and, under some conditions on the action of $\mathcal{G}$, they guarantee sensitivity to all other permutation groups outside $\mathcal{G}$.
1. Group Action and Equivariance
The paper formalizes discrete group actions as permutations of input and output variables and distinguishes equivariance from invariance. Because ordinary equivariance can be non-informative, it introduces unique equivariance, which excludes larger permutation symmetries.
- Group Actions: Discrete group actions permute indices of variable sets, represented by permutation groups derived from the original finite group.The induced permutation group need not be isomorphic to the acting group unless the action is faithful.
- Equivariance and Invariance: A neural layer is equivariant when transforming its input produces a predictably transformed output, whereas invariance leaves the output unchanged.The input and output transformations are paired through a joint permutation group.
- Subgroups and Symmetry: Equivariance to a group implies equivariance to every subgroup, so subgroup equivariance alone may not identify the layer’s full symmetry.The reverse-convolution example is equivariant to both the full group action and a subgroup.
- Example: In the reverse-convolution example, checking the permutation condition across all elements of Z6 establishes equivariance to the specified right-input and left-output shifts.The construction also illustrates that the same function can remain equivariant under a subgroup.
- Unique Equivariance: A constant function is equivariant to any input-output permutation group, motivating unique equivariance as equivariance to G but not to any larger group H.Unique equivariance makes the specified symmetry characterization informative rather than merely compatible.
2. Symmetry Groups of a Network
The paper connects neural-layer equivariance to automorphisms of a colored bipartite parameter-sharing graph. Distinct edge colors yield unique automorphism-equivariance, while the framework also supports multilayer composition and standard permutation-equivariant constructions.
- Graph-Based Parameter Sharing: A colored bipartite graph encodes parameter sharing by assigning the same parameter to edges of the same color.Its automorphism group consists of node permutations that preserve all edge colors.
- Symmetry–Equivariance Theorem: For distinct parameter values, the neural layer is uniquely equivariant to the automorphism group of its colored graph.The theorem requires wc ≠ wc′ for every pair of distinct colors.
- Design Principle: To obtain unique equivariance for a target group action, the parameter-sharing structure must have that group as its symmetry group.A subgroup of the graph automorphism group still guarantees equivariance, but not necessarily the desired unique characterization.
- Example: The reverse-convolution graph has exactly the six edge-color-preserving permutations associated with GN,M, yielding unique equivariance for that action.The shift of output and input variables preserves the relevant edge colors, and no additional color-preserving permutations remain.
- Permutation-Equivariant Layer: The framework recovers the standard permutation-equivariant layer by constructing a graph whose color-preserving automorphisms pair identical input and output permutations.The construction uses Aut(Ω) = SN ⊙ SN ≅ SN when the input and output index sets coincide.
- Multiple Layers: Equivariance extends through composition when successive layers share the intermediate group action, producing equivariance of the multilayer network.The composed action is GN,O = GN ⊙ GO.
3. Structure Design
The paper designs parameter-sharing structures whose graph symmetries match prescribed permutation actions, yielding equivariance and, under semi-regularity conditions, unique equivariance. It develops dense and sparse constructions, then relates them to group convolution and graph convolution.
- Design objective: The design goal is to construct a parameter-sharing structure Ω with Aut(Ω) = G_N,M, which makes the layer uniquely G_N,M-equivariant.Theorem 2.1 supplies the link between the automorphism group of Ω and unique equivariance.
- Group-action conditions: Transitivity means every index can be moved to every other, while regularity additionally requires exactly one group action between each ordered pair.Semi-regularity requires at most one such action; regularity combines transitivity with freeness.
- Dense design: The dense construction colors edge orbits of a complete bipartite graph, guaranteeing G_N,M-equivariance through parameter tying.Each edge receives the color associated with its orbit under the input/output action.
- Dense design: Dense parameter-sharing covers nested subset symmetries, including the wreath product S_d ≀ S_D for permutations within and across subsets.The construction uses D subsets of d variables and partitions edges according to the relevant symmetry relationships.
- Sparse design: The dense design can be inefficient for smaller groups and does not guarantee unique equivariance; the sparse design addresses these limitations using orbits and symmetric generating sets.For circular convolution, the dense filter can become as large as the input image, whereas sparse structures may use smaller connectivity patterns.
- Sparse design: If G_N and G_M are semi-regular, the sparse construction has Aut(Ω) = G_N,M and therefore yields uniquely G_N,M-equivariant layers.The result holds for any symmetric generating set, while practical design seeks a minimal generating set A.
- Connections: Under M = G and transitive G_N, the sparse construction performs group convolution, while graph-convolution equivariances depend only on a graph’s symmetry group.The graph result states that graphs with identical symmetry groups induce identical equivariances.
4. Conclusion
The work designs neural-network layers with specified equivariance and invariance by relating layer behavior to parameter-matrix symmetries. Two parameter-sharing schemes achieve equivariance to discrete group actions and, under conditions, sensitivity to other group actions.
- The approach relates neural-layer equivariance properties to symmetries of the parameter matrix.
- Two parameter-sharing schemes achieve equivariance with respect to any discrete group action.
- Under some conditions, the schemes guarantee sensitivity with respect to other group actions.
- The work distinguishes equivariance or invariance from sensitivity because constant functions are invariant to all transformations.
A. Proofs
The proofs establish that parameter symmetries characterize equivariance and that the constructed graph designs have exactly the intended automorphism groups under stated orbit conditions.
- Equivariance implies that the output transformation matches the transformed input, and this property descends to every subgroup.
- Theorem 2.1 proves unique Aut(Ω)-equivariance in both directions: graph automorphisms imply equivariance, and universal equivariance implies graph automorphisms.
- The proof uses a one-hot input and parameter assignment to show that unequal edge relations contradict equivariance.
- The constructed group actions preserve graph relations, so GN,M is contained in Aut(Ω).
- When GN and GM are semi-regular, orbit-stabilizer bounds the automorphism-group size, yielding Aut(Ω) = GN,M.
- Regularity makes stabilizers trivial, while generating-set connectivity propagates a fixed pair through the entire bipartite graph.
- The resulting graph connectivity proves the automorphism group equality, with later corollaries connecting the construction to group and graph convolution.
B. Background on Permutation Groups
The background defines groups, subgroups, isomorphisms, generating sets, and Cayley diagrams as the combinatorial language for the paper’s permutation-group constructions.
- A group is a set with a closed, associative binary operation, an identity element, and inverses for all elements.
- A subgroup is a subset that forms a group under the parent group’s operation, while isomorphism preserves the multiplication structure through a bijection.
- A generating set expresses every group element as a combination of its members, and a symmetric generating set is closed under inverses.
- The parameter-sharing scheme’s parameter count grows linearly with the size of the minimal generating set.
- A Cayley diagram visualizes a group as a colored directed graph whose edges encode generators.
B.1. Discrete Group Action
A discrete group action permutes the indices of input variables, inducing a permutation representation of the acting group on the finite index set.
- A group action maps each group element and index to another index while satisfying identity and composition laws.
- For a vector x, the action of g reorders its entries according to the permuted indices.
- Because each action map is a bijection on the finite index set, it is a permutation of the ordered indices.
- The induced permutations form GN, a subgroup of the symmetric group SN.
B.1.1. PROPERTIES OF GROUP ACTION
The paper distinguishes faithful and unfaithful group actions and defines transitive, free, semi-regular, and regular actions as properties relevant to strict equivariance.
- Faithfulness: A group action is faithful when its induced permutation group is isomorphic to G, so distinct group elements act as distinct permutations.Faithfulness preserves G's structure; otherwise, the quotient action G/Kγ captures the effective action.
- Faithfulness: The kernel Kγ contains group elements acting as the identity on every element of N, and the faithful action is the quotient group G/Kγ.This quotient removes transformations indistinguishable on N.
- Action properties: The subsequent definitions and results also extend to right group actions by substituting g with g^-1.This is a convention for translating the treatment between left and right actions.
- Action properties: An action is transitive if some group element maps every n1 ∈ N to every n2 ∈ N.The definition requires at least one such action for each ordered pair.
- Action properties: An action is free or semi-regular when at most one group element maps any n1 to n2, and regular when it is both transitive and free.Any free action is also faithful.
B.1.2. ORBITS
Group actions partition a set into orbits, on which the action is always transitive; permutations can be explicitly represented as products of disjoint cycles.
- Orbits: The orbit of n is the set of elements reachable from n under the group action, written Gn = {gn ∣ n ∈ N}.The orbit relation partitions N into disjoint orbit sets Gnp.
- Orbits: Two elements are in the same orbit exactly when one is obtained from the other by some group action.Within every orbit, the action is transitive.
- Cycle Notation: A permutation decomposes into disjoint cycles, with a length-d cycle sending each bi to the next element modulo d.Cycle notation makes the action of a group element on N explicit.
- Cycle Notation: For example, the permutation [3,1,2,5,4,6] is represented by the disjoint cycles {(1,3,2),(4,5)} after omitting fixed points.The cycles act on separate subsets of the indexed set.