Equivariance Through Parameter-Sharing
Siamak Ravanbakhsh Jeff Schneider Barnabas Poczos












 

 

































































equation(#2#1#3)







#1todo: #1 






























































plain

theoremTheorem[section]
lemma[theorem]Lemma
proposition[theorem]Proposition
observation[theorem]Observation
claim[theorem]Claim
corollary[theorem]Corollary
definition
definitionDefinition[section]





exampleExample[section]

*proofProof


















testexamplectr

Example  

testexample O 

   
  testexamplectr

    testexamplebox
    
    empty,
    title=.  #1,
    
    attach boxed title to top left,
       
       minipage boxed title,
    
    boxed title style=empty,size=minimal,toprule=0pt,top=4pt,left=3mm,overlay=,
    coltitle=colexam,fonttitle=,
    before=,parbox=false,boxsep=0pt,left=3mm,right=0mm,top=2pt,breakable,pad at break=0mm,
       before upper=@totalleftmargin0pt, 
    
    overlay unbroken=[colexam,line width=.5pt] ([xshift=-0pt]title.north west) – ([xshift=-0pt]frame.south west); ,
    
    overlay first=[colexam,line width=.5pt] ([xshift=-0pt]title.north west) – ([xshift=-0pt]frame.south west); ,
    
    overlay middle=[colexam,line width=.5pt] ([xshift=-0pt]frame.north west) – ([xshift=-0pt]frame.south west); ,
    
    overlay last=[colexam,line width=.5pt] ([xshift=-0pt]frame.north west) – ([xshift=-0pt]frame.south west); ,
    


testexamplectrsection




MyFrame
    linecolor=Black,
    outerlinewidth=.3pt,
    roundcorner=5pt,
    innertopmargin=,
    innerbottommargin=,
    innerrightmargin=5pt,
    innerleftmargin=5pt,
    backgroundcolor=RoyalBlue!0!white

MyFrame2
    linecolor=White,
    outerlinewidth=.3pt,
    roundcorner=5pt,
    innertopmargin=,
    innerbottommargin=,
    innerrightmargin=5pt,
    innerleftmargin=5pt,
    backgroundcolor=Gray!10!white
  

  








Equivariance Through Parameter-Sharing

 

[
Equivariance Through Parameter-Sharing


Siamak Ravanbakhshto
Jeff Schneiderto
Barnabás Póczosto


toSchool of Computer Science, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA, USA 15217
Siamak Ravanbakhshmravanba@cs.cmu.edu













equivariance, parameter-sharing, deep learning, neural networks

0.3in
]


 


We propose to study equivariance in deep neural networks through parameter symmetries.
In particular, given a group  that acts discretely on the input and output of a standard neural network layer _: ^M→^N,
we show that _ is equivariant with respect to -action iff  explains the symmetries of the network parameters .
Inspired by this observation, we then propose two parameter-sharing schemes to induce the desirable symmetry on .
Our procedure for tying the parameters achieves -equivariance and, under some conditions on the action of , it guarantees sensitivity 
to all other permutation groups outside .



 



Given enough training data, a multi-layer perceptron would eventually learn the domain invariances
in a classification task. Nevertheless, success of convolutional and recurrent networks
suggests that encoding the domain symmetries through shared parameters can significantly boost
the generalization of deep neural networks. 

The same observation can be made in deep learning for semi-supervised and
unsupervised learning in structured domains.
This raises an important question that is addressed in this paper:
What kind of priors on input/output structure can be encoded through parameter-sharing?



This work is an attempt at answering this question, when our priors are in the form discrete
domain symmetries.

To formalize this type of prior, a family of transformations of input and output to a neural layer 
are expressed as group “action” on the input and output.
The resulting neural network is invariant to this action, if transformations of the input within that particular family, does not change the output (rotation-invariance).
However, if the output is transformed, in a predictable way, as we transform the input, the neural layer is equivariant to the
action of the group. Our goal is to show that parameter-sharing can be used to achieve equivariance to any discrete group action.


Application of group theory in machine learning has been the topic of various works in the past <cit.>.
In particular, many probabilistic inference techniques have been extended to graphical models with known symmetry groups <cit.>.
Deep and hierarchical models have used a variety of techniques to study or obtain representations that isolate
transformations from the 
“content” <cit.>.
The simplest method of achieving equivariance is through data-augmentation <cit.>.  
Going beyond augmentation, several methods directly apply the group-action, in one way or another, 
by transforming the data or its encodings using group members <cit.>.


An alternative path to invariance via harmonic analysis. In particular cascade of wavelet transforms is investigated in <cit.>.
More recently <cit.> study steerable filters <cit.> as a general mean for achieving equivariance in deep networks.
Invariance and equivariance through parameter-sharing is also discussed in several prior works <cit.>.


The desirability of using parameter-sharing for this purpose is mainly due to its simplicity and computational efficiency.
However, it also suggests possible directions for discovering domain symmetries through regularization schemes. 
Following the previous work on the study of symmetry in deep networks, we rely on group theory and group-actions to formulate
invariances and equivariances of a function.
Due to discrete nature of parameter-sharing, our treatment here is limited to permutation groups.
Action of a permutation group  can model discrete transformations of a set of variables, such as translation and 90^∘ rotation of pixels around any center in an image.
If the output of a function transforms with a -action as we transform its input with a different -action, the function is equivariant
with respect to action of . For example, in a convolution layer, as we translate the input,
 the feature-maps are also translated.
If the output does not transform at all, the function is invariant
to the action of . Therefore, invariance is a special equivariance.
In this example, different translations correspond to the action of different members of .

The novelty of this work is its focus on the “model symmetry” as a gateway to
equivariance. This gives us new theoretical guarantees for a “strict” notion of equivariance in neural networks. 
The core idea is simple: consider a colored bipartite graph  representing a neural network layer.
Edges of the same color represent tied parameters.
This neural network layer as a function is equivariant
to the actions of a given group  (and nothing more) iff the action of  is the symmetry group of  –
there is a simple bijection between
parameter symmetries and equivariences of the corresponding neural network.

The problem then boils down to designing colored bipartite graphs with 
 given symmetries, which constitutes a major part of this paper.
<ref> demonstrates this idea.[Throughout this paper, since we deal with finite sets, we use circular shift and circular convolution instead of shift and convolution. The two can be made identical with zero-padding of the input.]



For the necessary background on group theory see the Appendix.
In the following, <ref> formalizes equivariance wrt discrete group action.
<ref> relates the model symmetries a neural layer to its equivariance.
<ref> then builds on this observation to introduce two procedures for parameter-sharing that achieves a desirable equivariance.
Here, we also see how group and graph convolution as well as deep-sets become special instances in our parameter-sharing procedure,
which provides new insight and improved design in the case of group convolution.
Where input and output of the layer have a one-to-one mapping, we see that the design problem reduces a well-known problem in combinatorics.



§ GROUP ACTION AND EQUIVARIANCE

















Let = [x_1,…,x_N] ∈^N  denote a set of variables and = {≫} be a finite group. The discrete action of  on  is in the form of permutation of indices in = {1,…,N}. 
This group is a subgroup of the symmetric group S; the group of all N! permutations of N objects. We use = [1,…,N] to denote the ordered counterpart to  and the -action on this vector ≫ [≫ 1, …, ≫ N] is a simple permutation. Using _ to denote , the discrete action of ≫∈ on ∈^N is given by ≫__≫.

-action on  is a permutation group that is not necessarily isomorphic to  itself.
≤ captures the structure of  when it acts on .
We use ≫ to denote the image of ≫∈ in . 
-action is faithful iff two groups are isomorphic ≅ – that
is -action preserves its structure.
In this case, each ≫∈ maps to a distinct permutation ≫≠≫' ∀≫, ≫' ∈.
Given any -action on  we can efficiently obtain ; see Appendix.

[style=MyFrame2]
[Cyclic Group]
  Consider the cyclic group = ℤ_6 and define its action on ∈^3 by
  defining it on the index set = {1,2,3} as
  ≫ n ≫ + n  3 ∀≫∈ℤ_6.
  This action is not faithful. For example, the action of ≫=1 and ≫ = 4 result in the same permutations of variables in ; single-step of circular shift to the right.
  With the above action, the resulting permutation group  is isomorphic to ℤ_3 < ℤ_6.
  
  Now consider the same group = ℤ_6 with a different action on : ≫ n ≫ - n  3 ∀≫∈ℤ_6, where we replaced (+) with (-).
  Let  be the resulting permutation group. Here again ≅ℤ_3.
  Although isomorphic, ≠, as they are different permutation groups of .












 


































Consider the function : ^N →^M
and let  and  be the action of  on input/output
index sets  and .

The joint permutation group , is a sub-direct product (or pairing) of  and 

    ,  = ⊙{(≫, ≫) |≫∈}.



We are now ready to define equivariance and invariance.
(·) is ,-equivariant iff 

    ≫() = (≫)   ∀∈^N, (≫, ≫) ∈,

Moreover, if = {e} is trivial, we have

    ≫() = ()   ∀∈^N, ≫∈

and (·) is -invariant.


≫ and ≫ can also be represented using permutation matrices
𝐆∈{0,1}^N × N, 
and 𝐆∈{0,1}^M × M.
Equivariance relation of <ref> then becomes

    𝐆() = (𝐆)  ∀∈^N, (𝐆, 𝐆) ∈,


The following observation shows that the subgroup relationship affects equivariance and invariance.

  If the function : ^N→^M is ,-equivariant,
  then it is also ,-equivariant for any permutation group ,  <. 
 

[style=MyFrame2]
[Reverse Convolution]
  Consider the cyclic group = ℤ_6 and for ≫∈, define the action on = {1,2,3} to be ≫ n ≫ + n  3.
  Also let its action on = {1,…,6} be ≫ m ≫ - n  6.
  In other words, -action on  performs circular shift to the right and its action on  shifts variables to the left.

  Examples of the permutation matrix representation for two members of  and 
  are 
  










   
    2 =   ( [ 0 1 0; 0 0 1; 1 0 0;   ])
             2 =    ([ 0 0 1 0 0 0; 0 1 0 0 0 0; 1 0 0 0 0 0; 0 0 0 0 0 1; 0 0 0 0 1 0; 0 0 0 1 0 0;   ])

   corresponding to right and left shift on vectors of different lengths.

     Now consider the function : ^N→^M
     
    _() =   ^𝖳 =  ( [ 0 a b 0 a b; a b 0 a b 0; b 0 a b 0 a;   ] )   ∀ a,b ∈

     Using permutation matrices one could check the equivariance condition  <ref> for this function. We can show that  is equivariant
     to ,. Consider 2∈ℤ_6 and its
     images 2∈ and
     2∈. L.h.s. of <ref> is
     
    2_() =  ([ 0 0 1 0 0 0; 0 1 0 0 0 0; 1 0 0 0 0 0; 0 0 0 0 0 1; 0 0 0 0 1 0; 0 0 0 1 0 0;   ])  ([ 0 a b; a b 0; b 0 a; 0 a b; a b 0; b 0 a;   ] )   =   ([ b 0 a; 0 a b; a b 0; b 0 a; 0 a b; a b 0;   ] )


     which is equal to its r.h.s.
     
    _(2) =   ([ 0 a b; a b 0; b 0 a; 0 a b; a b 0; b 0 a;   ] ) ([ 0 1 0; 0 0 1; 1 0 0;   ] )  =  ([ b 0 a; 0 a b; a b 0; b 0 a; 0 a b; a b 0;   ] )

     for any . One could verify this equality for all ≫∈ℤ_6.

     Now consider the group ,  < ,,
     where = and members of 
      = {0, 2, 4},
      perform left circular shift of length 0, 2 and 4.
      It is easy to see that , ≅ℤ_3.
      Moreover since ,  < ,, (·) above is
      ,-equivariant as well. However, one prefers to characterize the equivariance
      properties of  using , rather than ,.




The observation above suggests that ,-equivariance is not restrictive enough.
As an extreme case, a constant function () = 1 is equivariant to any
permutation group , ≤S×S.
In this case equivariance of  with respect to a particular , is not very informative to us. To remedy this, we define a more strict notion of equivariance.

we say a function : ^N→^M is uniquely -equivariant iff it is
-equivariant and it is “not” -equivariant for any >.









§ SYMMETRY GROUPS OF A NETWORK

Given a group , and its discrete action through ,,
we are interested in defining parameter-sharing
schemes for a parametric class of functions that guarantees their unique ,-equivariance.
We start by looking at a single neural layer and
relate its unique ,-equivariance to the 
symmetries of a colored multi-edged bipartite graph that defines parameter-sharing.
We then show that the idea extends to multiple-layers.




A colored multi-edged bipartite graph = (,, α) is a triple, 
where  and  are its two sets of nodes, and α: ×→ 2^{1,…,C}
is the edge function that assigns multiple edge-colors from the set {1,…,C} to each edge. Non-existing edges receive no color.


We are interested in the symmetries of this structure.
The set of permutations (, ) ∈S×S of nodes (within each part of the bipartite graph) 
that preserve all edge-colors define the Automorphism Group () ≤S×S – that is ∀ (n,m) ∈×

    (, ) ∈()  ⇔ α(n,m) = α( ( n,  m))


Alternatively, to facilitate the notation, we define the same structure (colored multi-edged bipartite graph) 
as a set of binary relations between 
and  – that is
= (, , {_c}_1 ≤ c ≤ C) where each relation is associated with one color 
_c = {(n,m) | c ∈α(n,m) ∀ (n,m) ∈×}. 
This definition of structure, gives an alternative expression for ()

    (, ) ∈()  ⇔
       ( (n,m) ∈_c   ⇔  ( n,  m) ∈_c )    ∀ c, n, m


The significance of this structure is in that, 
it defines a parameter-sharing scheme in a neural layer, where the same edge-colors
correspond to the same parameters. Consider the function [ϕ_1,…,ϕ_M]: ^N→^M

    ϕ_m(; , ) σ(∑_n∑_c ∈α(n,m)θ_c x_n)   ∀ m

where σ: → is a strictly monotonic nonlinearity and
= [θ_1,…θ_c,…,θ_C] is the parameter-vector for this layer.
 
The following key theorem relates the equivariances of (·; , ) to the symmetries of .
[style=MyFrame]

For any ∈^C s.t., w_c ≠ w_c'∀ c,c', the function (·; , ) is uniquely ()-equivariant.



  For any , ≤(), the function (·; , ) is ,-equivariant.

The implication is that to achieve unique equivariance for a given group-action,
we need to define the parameter-sharing using the structure  with symmetry group ,.

[style=MyFrame2]
[Reverse Convolution]
  
  Revisiting Example <ref> we can show that the condition of Theorem <ref> holds.
  In this case () = and the parameter-sharing of the matrix  is visualized below,
  where we used two different line styles for a, b ∈.
  

    
    < g r a p h i c s >

  

In this figure, the
circular shift of variables at the output and input level to the left and right respectively, does not change the
edge-colors. For example in both cases node 1's connection to nodes 3, 6 using dashed-lines is preserved.

Six repetitions of this action produces different permutations corresponding to 
six members of ,. Therefore , ≤(Ω)
and according to Corollary <ref>, ϕ(·) is  , equivariant.
Moreover, using Theorem <ref> of the next section, we can prove that these six permutations are the “only”
edge-color preserving ones for this structure, resulting in unique equivariance.



Matrix Form.
To write <ref> in a matrix form, if there are multiple edges between
two nodes n,m, we need to merge them.
In general, by assigning on distinct color to any set in the range of α: ×→ 2^{1,…,C} we can
  w.l.o.g. reduce multiple edges to a single edge.
In other words we can rewrite  using ∈^M × N

    (; ; ) =  ()     W_m,n = ∑_c ∈α(n,m)θ_c

Using this notation, and due to strict monotonicity of the nonlinearity σ(·), Theorem <ref> simply states that for all (≫,≫) ∈(), ∈^N and  given by <ref>

    𝐆 =  𝐆.



















[style=MyFrame2]
[Permutation-Equivariant Layer]
  Consider all permutations of indices  and =.
  
  

    
    < g r a p h i c s >

  

  
  We want to define a neural layer such that all permutations of the input ≫∈ = S result in the
  same permutation of the output ≫ = ≫.
  Consider the following colored bipartite graph, for a special case where N = M = 4.





    It is easy to show that color-preserving permutations of this structure are () = S⊙S = { (≫, ≫) |≫∈S}≅S:
On one hand, for (,) ∈S×S, having = clearly preserves the colors. On the other hand, if ≠, there exists u ∈ (also in ) such that u ≠ u.
Therefore (, ) does not preserve the relation = {(n,n) | n ∈} corresponding to dashed edges, and therefore (, ) ∉(). This proves () = S⊙S.
The function <ref> for this  is 
    (;  = [θ_1, θ_2], ) =  (θ_1 𝐈 + θ_2 11^𝖳).



<cit.> derive the same permutation equivariant layer,
    by proving the commutativity in <ref>, while here it follows from Corollary <ref>. 


























Multiple Layers. For deep networks,
the equivariance of the composition _2∘_1 to -action
follows from that of individual layer _1:^N→^M and _2:^M→ℤ^O.
Assuming _1 is ,-equivariant and _2 is ,𝕆-equivariant, where -action on  is shared between the two layers, it follows that _2∘_1 is , 𝕆-equivariant, where
, 𝕆 = ⊙𝕆.
This is because ∀≫∈ and ∈^N

    _2(_1(≫)) = _2(≫_1()) = ≫𝕆_2(_1()).



















§ STRUCTURE DESIGN

Consider the definition of neural layer <ref> that employs parameter-sharing according to .
Given -action on  and , we are interested in designing
structures  such that () = ,. According to the Theorem <ref>,
it then follows that  is uniquely ,-equivariant.
Here, we give the sufficient conditions and the design recipe to achieve this. 

For this we briefly review some group properties that are used
in later developments.










  transitivity We say that -action on  is transitive iff ∀ n_1,n_2 ∈, there exists at least one action ≫∈ (or ≫∈) such that ≫ n_1 = n_2. 

  regularity The group action is free or semi-regular iff ∀ n_1,n_2 ∈, there is at most one ≫∈ such at ≫ n_1 = n_2, and the action is regular iff it is both transitive and free – for any pair n_1,n_2 ∈, there is uniquely
  one ≫∈ such that ≫ n_1 = n_2. Any free action is also faithful.
  We use a similar terminology for . That is we call  semi-regular
iff ∀ n_1,n_2 ∈ at most one ≫∈ moves n_1 to n_2 and  is regular if this number is exactly one.

  orbit The orbit of  n ∈ is all the members to which it can be moved, 
n = {≫ n |≫∈}. The orbits of 
n ∈ form an equivalence relation[n ∼ n' ⇔∃≫ s.t.,  n = ≫ n' ⇔ n ∈ n' ⇔ n' ∈ n.]
This equivalence relation partitions  into orbits = ⋃_1 ≤ p ≤ P n_p, where n_p is an arbitrary representative of the partition 
n_p ⊆.
Note that the -action on  is always transitive on its orbits – that is for any n,n' ∈ n_p, there is at least one ≫∈ such that n = ≫ n'. Therefore, for a semi-regular -action, the action of  on the orbits n_p ∀ 1 ≤ p ≤ P is regular.




[style=MyFrame2]
[Mirror Symmetry]
  Consider = ℤ_2 = {e=0,1} (1 + 1 = 0) acting on , where
   the only non-trivial action is defined as flipping the input: 1 [1,…,N] = [N,N-1,…,1]. 
 
    is faithful in its action on , however  is not transitive – N cannot be moved to N-1.
   If N is even, then -action is semi-regular. This is because otherwise the element
   in the middle n = ⌈N/2⌉ is moved to itself by two different actions e, 1∈. Furthermore, if N is even, -action has N/2 orbits and _2 acts on these orbits regularly. If N is odd, -action has ⌈N/2⌉ orbits. However, its action on the orbit of the middle element ⌈N/2⌉ is not regular.



In the following, <ref> proposes a procedure for parameter-sharing in a fully connected layer.
Although simple, this design is dense and does not guarantee “unique” of equivariance. 
<ref> proposes an alternative design with sparse connections that in some settings
ensures unique equivariance. 



<ref> investigates the effect of having multiple input and output channels in the neural layer and <ref> studies a special case of =, where input and output indices
have a one-to-one mapping.



 §.§ Dense Design


Consider a complete bipartite graph with  and  as its two parts and edges (n,m) ∈×.
The action of , partitions the edges into orbits {, (n_p,m_q)}_n_p,m_q, where (n_p,m_q) is a representative
edge from an orbit. Painting each orbit with a different color gives 

    = (, , {_p,q = , (n_p,m_q)}).






Therefore two edges (n,m) and (n',m') have the same color iff an action in , moves one edge to the other.

[style=MyFrame]

,≤ for  of <ref>.



  (·; , ), for structure <ref>, is equivariant to ,.




[style=MyFrame2]
[Nested Subsets and Wreath Product]
  The permutation-equivariant layer that we saw in Example <ref>
  is useful for defining neural layers for set structure. If our data-structure is
  in the form of nested subsets, then we require equivariance to permutation of variables
  within each set as well as permutation of subsets. Here, we show how to use our dense
  design for this purpose.

  We use a special indexing for the input to better identify the exchangeability of variables.
  We assume D subsets, each of which has d variables
  = [x_1,1,…, x_1,d,x_2,1,…, x_D,d].

  The group of our interest is
  the wreath product S_d ≀S_D. This type of group product can be used to build
    hierarchical and nested structures with different type of symmetries at each level.
  Nesting subsets corresponds to the most basic form of such hierarchical constructions.
  We use (n,n') to index input variables and (m,m') for output variables.

  The following figure shows the resulting parameter-sharing for an example with D=2, d=3.
  

    
    < g r a p h i c s >

  

    How did we arrive at this structure ?
    Recall Our objective is to define parameter-sharing so that ϕ_: ^dD→^dD is equivariant to the action of = S_d ≀S_D – permutations within sets at two levels.
  This group-action identifies three partitions of edges (seen in the figure):
  I) ((n,n'), (n,n')) ∀ n,n' connects each variable to its counterpart (dashed orange);
  II) ((n,n'), (n,m')) ∀ n, n'≠ m' connects each variable to other variables within the same subset;
  III) ((n,n'), (m,m')) ∀ n ≠ m is the set of edges from one subset to another.
  According to the Corollary <ref> this parameter-sharing guarantees equivariance.













This fully-connected design is useful when the group , is large; for example
when dealing with S_. However, for smaller groups it could be very 
 inefficient in practice,
 as sometimes we can achieve equivariance through a sparse structure Ω.
As an example, consider the 2D circular convolution layer. 
It is easy to show that according to this design, the convolution filter will be the same size as the input image.
While this achieves the desirable equivariance, it is inefficient and does not generalize as well as a convolution layer with small filters.
Moreover, the dense design does not guarantee “unique” equivariance. We next show under some
conditions on , the sparse design can produce this stronger guarantee.



 §.§ Sparse Design

Our sparse construction uses orbits and symmetric generating sets:


  * Let us denote the orbits of -action on  and  by { n_p | 1 ≤ p ≤ P}
and { m_q | 1 ≤ q ≤ Q} respectively, where P and Q are the total number of orbits and
n_p,m_q are (arbitrary) representative members of orbits n_p, m_q respectively.
Note that in contrast to previous section, here we are considering the orbit of variables rather than the edges.

  * The set A⊆ is called the generating set of  (<A> =), 
iff every member of  can be expressed as a combination of members of A. 
If the generating set is closed under inverse å∈A⇒å^-1∈A we call it a symmetric generating set.


Define the structure  as 

    = (, , {_p,q,å}_1 ≤ p ≤ P,  1 ≤ q ≤ Q, å∈A) 
       _p,q,å = {( ≫å n_p, ≫ m_q) | (≫,≫) ∈,}.


In words, we have one color per each combination of orbits (p, q) and members
of the generating set å∈A. 




The following theorem relates the symmetry group of this structure to .

[style=MyFrame]

  ,≤() for  of <ref>.
  Moreover if  and  are both semi-regular, then , = ().


Note that this result holds for any choice of a symmetric generating set A in defining .
Therefore, in designing sparse layers, one seeks a minimal A.


The function (·, , ), using the structure <ref> is ,-equivariant. 
If  and  are semi-regular, this function is “uniquely” ,-equivariant.  


Now, assuming -action is semi-regular on both 
and , using (arbitrarily chosen) representatives {n_p}_1≤ p ≤ P and {m_q}_1 ≤ q ≤ Q for 
orbits in  and , we can rewrite the expression <ref> of the structured neural layer for the structure above. Here, components of = [ϕ_1,…,ϕ_M] are enumerated for 1 ≤ q ≤ Q, ≫∈:

    ϕ_≫ m_q(; ) = σ (∑_1 ≤ p ≤ P∑_å∈Aθ_q, p, å x_≫å n_p )

where ∈^P × Q × |A| is the set of unique parameters,
  and each element ϕ_≫ m_q depends on
 subset of parameters {θ_q, p, å}_p,å identified by q and a subset of inputs {x_å, ≫ n_p}_p,å identified by ≫. 














 [style=MyFrame2]
[Dihedral Group of <ref>]
In the example of <ref>, the number of orbits 
of -action on  is P=2 and for  this is Q=1.
The symmetric generating set is the generating set that is used in the
Cayley diagram, with the addition of inverse shift (inverse of the blue arrow).
We then used <ref> to build the structure of <ref> (right).



[Reverse Convolution]
  The parameter-sharing structure of reverse convolution in Examples <ref>
  and  <ref> is produced using our sparse design.
  In these examples, both  and  are
  regular. Therefore the proposed parameter-sharing provides unique equivariance.





 §.§ Multiple Channels

In this section, we extend our results to  multiple input and output channels.
Up to this point, we considered a neural network layer : ^N→^M.
Here, we want to see how to achieve ,-equivariance for
: ^N × K→^M × K',
where K and K' are the number of input and output channels.

First, we extend the action of  on  and  
to ^K = [, …, _K times] as well as ^K',
to accommodate multiple channels.
For this, simply repeat the -action on each component.  
-action on multiple input channels is equivalent
to sub-direct product ⊙…⊙_K times≅. The same applies to .
  
This repetition, multiplies the orbits of , one for each channel, so that instead of having P
and Q orbits on the input  and output  sets, we have K × P and K' × Q orbits on the input
^K and output ^K'.
This increases the number of parameters by a factor of K × K'.

The important implication is that, orbits and multiple channels are treated identically by both dense and sparse designs.






[style=MyFrame2]
[Group Convolution]
  The idea of group-convolution is studied by <cit.>; see also <cit.>.
  The following claim relates the function of this type of layer to our sparse design.
  
    Under the following conditions the neural layer <ref> using our sparse design  <ref> performs group convolution:
    I) there is a bijection between the output and  (=) and; II)  is transitive.
  
  This also identifies the limitations of group-convolution even in the setting where =:
  When  is semi-regular and not transitive (P > 1), group convolution is not guaranteed to be uniquely equivariant while the sparse parameter-sharing of <ref>
  provides this guarantee.

  For demonstration consider the following example in equivariance to mirror symmetry.
  

  
    < g r a p h i c s >
  
  

  This figure shows the bipartite structure for = ℤ_2 = {0,1} and A = {1}. -action is horizontal flip of the input and the output.
  On the right, = while on the left
  -action has two orbits. Orbits are identified by line-style and color of the circles.
  In a neural layer with this parameter-sharing, when we flip the input variables (around the mirror line) the output is also flipped.
  
  The representatives in each orbit on  and  is identified with a star. Note that each combination of orbits p and q has a parameter of its own, identified with different edge-styles. While this construction guarantees “unique” -equivariance, if instead we use the same parameters across orbits (as suggested by the original group convolution) we get the parameter-sharing of the figure below middle.
  

  
    < g r a p h i c s >
  


In this case, the resulting neural layer has the desired equivariance (right).
However, it is equivariant to the action of a larger group , ≅ℤ_2 ×ℤ_2 > ℤ_2, in which 1 in the second ℤ_2 group exchanges variables across the orbits on  (left in figure above).








  














 §.§ =

In semi-supervised and un-supervised applications, we often need to produce a single output y_n  for each input x_n ∀ n ∈ – that is =.
We can ensure this by having a relation _c^* = {(n,n) | n ∈} in  that guarantees any (, ) ∈() applies the same permutation to  and 
= – =. The resulting structure =(,, {_c}_1 ≤ c ≤ C∪{_c^*}} can be also interpreted as a 
colored multi-edged directed graph (digraph). This is because we can collapse the two parts by identifying n ∈ with n ∈.



Therefore, the symmetry-group of the original bipartite structure, is isomorphic to symmetry group of a colored multi-edged digraph on . 
Achieving unique -equivariance then reduces to answering the following question:
when could we express a permutation group ≤S as the symmetry group () of a colored multi-edged digraph with N nodes?


This problem is well-studied under the class of concrete representation problems <cit.>.
Permutation groups  that can be expressed in this way are called 2-closed groups <cit.>. 
The recipe for achieving ≤()
is similar to our dense construction of <ref>[In a fully connected digraph,
  the edges that belong to the same orbit by -action on ×, receive the same color.]


The 2-closure  of a group  is then, the greatest permutation group ≤S with the same orbit on × as .
It is known that for example semi-regular permutation groups are 2-closed =.
This result also follows a corollary of our Theorem <ref> for sparse design of <ref>. 

[style=MyFrame2]
[Equivariance to × 90^∘ Rotations]
  Figure below compares the digraph representation of  produced using (left) our sparse design, and (right) our dense design.
  

  
    < g r a p h i c s >
  
  

  
Multiples of ± 90^∘ rotation is produced as the action of cyclic group ℤ_4 on eight input output variables – that is =  = {1,…,8}.
ℤ_4-action is semi-regular with two orbits; these orbits the two inner and outer set of four nodes. The representatives of 
each orbit in our sparse design is indicated using filled circles. The generating set consists of A = {1,3}, rotation by 90^∘ and its inverse, rotation by 270^∘.
Each edge in each of these figures, has a corresponding edge in the opposite direction, within a different relation. To avoid over-crowding the figure,
      we have dropped this edge from the drawing above, unless both edges belong to the same relation.












































[style=MyFrame2]
[Graph Convolution]





  Consider the setting where we use the (normalized) adjacency matrix 𝐁∈{0,1}^N× N (or Laplacian) of a graph Λ, to identify parameter-sharing in a neural network layer.
  For a single input/output channel, this is often in the form of
  𝐀, where ∈^N and 𝐀 = θ_1 𝐁 + θ_2 𝐈 has different parameters for diagonal and off-diagonal values <cit.>; for multiple channels see <ref>.
The following corollary of Theorem <ref> identifies the equivariance of 𝐀.

  Given the digraph Λ and its binary adjacency matrix 𝐁∈{0,1}^N× N, 
  then (θ_1 𝐁 + θ_2 𝐈) is 
  uniquely equivariant to the symmetry-group of Λ.
  
  
  
  

Since two graphs on N nodes can have identical symmetries, one implication of this corollary is
that graph-convolution has identical equivariances for graphs with the same symmetry groups.





§ CONCLUSION

This work is a step towards designing neural network layers with a given
equivariance and invariance properties.
Our approach was to relate the equivariance properties of the neural layer to the symmetries
of the parameter-matrix.

We then proposed two parameter-sharing scheme that achieves equivariance wrt 
any discrete group-action. Moreover under some conditions, we guarantee sensitivity
wrt other group actions. This is important because even a trivial constant function
is invariant to all transformations. It is therefore essential to be able to
draw the line between equivariance/invariance and sensitivity in a function.



To our knowledge, our work presents the first 
results of its kind on guarantees regarding both variance and equivariance with respect to group actions.










§ ACKNOWLEDGMENT

This research is supported in part by DOE grant DESC0011114 and NSF
grant IIS1563887.


icml2017





§ PROOFS


 of Observation <ref>

    ≫() = (≫) ∀≫∈⇒≫() = (≫) ∀≫∈⊂.



 of Theorem <ref>

For unique ()-equivariance we need proofs in two directions.
First we show that

    (, ) ∈() ⇒(; , ) = ^-1(; , )

which in turn shows that
(; , ) = (; , ). Starting from ^-1(; , ) on the r.h.s. of <ref> and considering an index m in = [ϕ_1, …, ϕ_M] we have

    ϕ_^-1 m(; , )    = σ(∑_n ∈, c ∈α(n, ^-1 m)θ_c x_ n) 
       = σ (∑_n ∈, c ∈α(^-1 n, ^-1 m)θ_c x_n) 
       =  σ(∑_n ∈, c ∈α(n, m)θ_c x_n) = ϕ_m(; , )

where in arriving at <ref> we used the fact that (,) ∈()  ⇒ α(n,m) = α( (^-1 n, ^-1 m)).

In the opposite direction we need to show that (; , ) = (^-1; , ) ∀∈^N, ∈^C only if (, ) ∈().

    (; , ) = (^-1; , )  ∀∈^N, ∈^C⇒
       ϕ_m(; , ) = ϕ_ m(^-1; , )  ∀ m, ∈^N, ∈^C⇒
       ∀ m, ∈^N, ∈^C
       ∑_n ∈, c ∈α(n, m)θ_c x_n = ∑_n ∈, c ∈α( n,  m)θ_c  x_^-1 n⇒
       ∑_n ∈, c ∈α(n, m)θ_c x_n = ∑_n ∈, c ∈α( n,  m)θ_c  x_n

where <ref> follows from monotonicity of σ: →.
We need to show that this final equality ∀ m, ∈^N, ∈^C
implies that α( n,  m) = α(n, m), which in turn, according to <ref> means (,)  ∈().

We prove α( n,  m) = α(n, m) by contradiction: assume α( n^*,  m^*) ≠α(n^*, m^*) for some n^*,m^*. 


Since α( n^*,  m^*) ≠α(n^*, m^*), we can
w.l.o.g. assume ∃ c^* ∈α(n^*,m^*) s.t.  c^* ∉α( n^*,  m^*) (the reverse direction, where c^* ∈α( n^*,  m^*) ∧ c^* ∉α(n^*,  m^*) is similar).
We show that an assignment of ∈^N and θ∈^C contradicts <ref>.
For this, define  such that x_n = δ(n, n^*), is non-zero only at index n^*. Moreover, assigning θ_c = δ(c, c^*) the r.h.s. of <ref> is
∑_n ∈, c ∈α( n,  m^*)θ_c  x_n = 0
while the l.h.s. is
∑_n ∈, c ∈α(m, n)θ_c x_n = θ_c^* x_n^*≠ 0.
Therefore α( n,  m) = α(n, m)  ∀ n,m, which by definition of () means (, ) ∈().



 of Proposition <ref>

  To prove ,≤() we simply show that all (≫,≫) ∈, preserve the relations in ().
  
  From <ref>, 
  
    ≫, = (≫,≫) ∈() ⇐
       ( (n,m) ∈_p,q ⇔  (≫n,≫m) ∈_p,q)    ∀ (p,q), n, m

  The r.h.s holds for all (≫,≫) ∈, because in constructing relations _p,q in the dense design,
  we used edge-orbits:
  
    (n,m) ∈_p,q⇔ (≫ n, ≫ m) ∈_p,q  ∀ (p,q), n, m.

  Therefore ≫,∈,⇒≫,∈().


 of Theorem <ref>

  We first show that any permutation (≫,≫) ∈,
  is also in (). The major part of the proof is to show that when
   and  are semi-regular, then |()| ≤ |,|.
  Combination of these two proves ()  = ,.

  I) to prove that (,) ∈,⇒ (,) ∈(),
  we simply apply (,) to an arbitrary edge (m,n) in a relation of .
  According to <ref> 
    _p,q, a = { (≫a n_p, ≫ m_q) | (≫,≫) ∈, }.

  Application of (,) to (≫a n_p, ≫ m_q) gives
  (≫a n_p, ≫ m_q) = (≫'a n_p, ≫' m_q) ∈_p,q,a.
  From <ref>, it follows that ,≤().

  
  












II)
  For this part, we use the orbit-stabilizer theorem. The orbit of each pair (n,m) ∈_p,q,a
wrt , is defined as , (n,m) = { ( n, m) |,∈,}.
The stabilizer ,^(n,m) of (n,m) ∈_p,q,a is
,^(n,m) = {, ∈, |,  (n,m) = (n,m)},
the group of all actions that fix (n,m). 
The orbit-stabilizer theorem states that |,| = |, ^(n,m)| × |, (n,m)|.
In our argument, we apply this theorem to bound |()| using |()^(n,m)|
and |() (n,m)|. 

The orbit-size, |() (n,m)|, for a pair (n,m) is bounded by the size of its relation |_p,q,a|, 
for some p,q,a. This is because, according to <ref>, 

    ∈() ⇒ ((n,m) ∈_p,q,a⇒  (n,m) ∈_p,q,a).

From <ref>, |_p,q,a| = |,|, and therefore |() (n,m)| < |, |.

Now, it only remains to show that if  and  are regular orbits (or semi-regular), 
the stabilizer is trivial ()^(n,m) = {e}. Because in this case the size of ()
is bounded by the size of orbit |()| = |()(n,m)| ≤ |, |, which combined with the result of part (I) gives , = ().

Since, according to our assumption,  acts regularly on n_p  ∀ p,
going back to definition of _p,q,å = {(≫å n_p, ≫ m_q) |≫, ∈, },
this (see definition of regularity) implies that for each n ∈ n_p, å∈A and m_q, we can identify a single ≫'∈
such that for some (n, m) = (å≫' n_p, ≫' m_q) ∈_p,q,å. This means that the edges (or pairs) adjacent to each node n ∈ n_p
all have distinct colors. The same argument using regularity of -action on m_q  ∀ q shows that
edges (or pairs) adjacent to m ∈ m_q all have distinct colors.

Therefore if we fix a pair (m,n), all their neighboring edges (adjacent on n or m) are unambiguously fixed. The same goes for the neighbors of the newly fixed nodes and so on.
If we can show that the bipartite graph representing  is connected
then fixing a pair guarantees that all pairs in all relations of  are fixed and therefore
(n,m) has a trivial stabilizer.

Two properties guarantee the connectedness of :


  * Since A = A^-1 is a generating set of , the bipartite subset consisting of subset of nodes n_p and m_q are connected.
  To show this, it is enough to show that we can reach any node n_z starting from an arbitrary representative n_p and zigzagging through the bipartite structure.
  Since n_z,n_p ∈ n_p ⇒∃≫_z ∈ s.t.  n_z = ≫_z n_p. Since <A> = ,, we can write
    ≫_z = å_1 …å_L.
The path that starts from n_p and takes the connections corresponding to _p,q,å_L, _p,q,å^-1_L-1, _p,q,å_L-2,…, _p,q,å^-1_1 takes us through a zigzag path from n_p to n_z. 

  * Since we have a relation _p,q, å for all pairs p,q, all the induced bipartite subgraphs on n_p-m_q are connected.

This proves that the whole bipartite
graph is connected and unambiguously fixed if we fix any pair (n,m). Therefore, (n,m) has a trivial stabilizer, proving that () = ,.


 of Corollary <ref>
  Follows directly from Theorems <ref> and <ref>.













   of Claim <ref>

To see this, note that  acts on = regularly, with the natural (group) action ≫.
Set the representative from the resulting single orbit as m_q = e.
Then <ref> becomes
= [ϕ_≫]_≫∈ with components

    ϕ_≫(; ) = σ (∑_1 ≤ p ≤ P∑_å∈Aθ_å, p x_≫å n_p )

If we further tie the parameters across the orbits so that θ_å, p = θ_å, p'∀ p,p',
the <ref> above is equivalent to formulation of <cit.> for a single input/output channels (see <ref> for multiple channels).    
  


 of Corollary <ref>

First we show this assuming a single channel K=1. For multiple channels see <ref>.





Consider the bipartite structure constructed from Λ:
= (, , {{(n,n) | n ∈}, {(n,n') | (n,n') ∈(Λ)}}).
Applying the result of Theorem <ref> using () = tells us that the function 𝐀 is uniquely ()-equivariant – that is
(𝐁_·,k) = 𝐁 (_·,k) ∀π∈().
Because of the relation _c^* = {{(n,n) | n ∈} in , the same bipartite structure ,
can be interpreted as a digraph; here with a single color, since  has only one relation in addition to _c^*.
Since this relation defines Λ,  () = (Λ), which means  𝐁 is uniquely (Λ)-equivariant.






§ BACKGROUND ON PERMUTATION GROUPS

Let = [x_1,…,x_N] ∈^N be a vector of N variables taking value in the same domain .
A group  is a set, equipped with a binary operation, with the following properties: I)  is closed under its binary operation; II) the group operation is associative –(≫_1 ≫_2)  ≫_3 = ≫_1 (≫_2  ≫_3) ∀ ≫_1,≫_2,≫_3 ∈; III) there exists an identity e∈ such that ≫e = e≫ = ≫ and ; IV) every element ≫∈ has an inverse ≫^-1∈, such that ≫≫^-1 = ≫^-1≫ = e. A subset ⊆ is a subgroup of  (≤) iff  equipped with the binary operation of  forms a group. Moreover, if  is a proper subset of ,  is a proper subgroup of , <.  
Two groups are isomorphic ≅ if there exists a bijection β: →, such that ≫_1 ≫_2 = ≫_3 ⇔β(≫_1) β(≫_2) = β(≫_3) ∀≫_1,≫_2, ≫_3. If this last relation holds for a surjective mapping (not necessarily one-to-one) then β is a homomorphic mapping and  is isomorphic to a subgroup of .  


Cayley Diagram. 
The set A⊆ is called the generating set of  (<A> =), 
iff every member of  can be expressed as a combination of members of A. 
If the generating set is closed under inverse å∈A⇒å^-1∈A we call it a symmetric generating set.

A is the minimal generating set if it has the least number of members among the
generating sets of . Note that the minimal generating sets are generally not unique.
The size of the minimal generating set of a group  becomes important because, 
the number of parameters in our parameter-sharing scheme grows linearly with |A|.
A group  is often visualized by its Cayley diagram; a colored digraph in which the node-set is  and 
directed edge (≫, å≫) ∀≫∈, å∈A is colored by å∈A. <ref>(lower-left) shows the
Cayley diagram of = D_5.



 §.§ Discrete Group Action

We are interested on the way a group “acts” on the input and output of a deep network.
Function γ: ×→ is the left action of group  on  iff
I) γ(e, ) = and; II) γ(g_1, γ(g_2, )) = γ(g_1 g_2, ).[All the following definitions and results may be extended to the “right” group action by substituting ≫↔≫^-1∀≫∈.]




For our purpose we limit this action to actions on the indices = of = [x_n] – function γ: ×→ satisfies γ(e, n) = n and γ(g_1, γ(g_2, n)) = γ(g_1  g_2, n).
We often use ≫ n as a shorthand for γ(≫, n), and also use ≫ to denote {≫ n | n ∈}.
The action of ≫ on a vector/sequence = is defined similarly ≫ [≫ 1,…, ≫ N].
Considering this, the -action on = [x_1,…,x_N] is ≫ [x_≫ 1, … x_≫ N].



From the properties of group and its action it follows that
  γ(≫, ·): → is a bijection with γ^-1(≫, n) = γ(≫^-1, n)  ∀ n ∈, ≫∈.
Since  is a finite set, this bijection for each ≫∈ is a permutation of 
 – ≫ [γ(≫, 1), …, γ(≫, N)] is a permutation of . 
Let = {γ(≫, ·) |≫∈} with (function composition as the binary group operation) 
denote the group of permutations of  induced by ≫∈.
This group is a subgroup of the symmetric group S; the group of all N! permutations of .
 captures the structure of  when it acts on the set 
and it is indeed a homomorphic image of .
We use ≫ to denote  γ(≫, ·), the the image of ≫∈ in . 






















  §.§.§ Properties of Group Action

-action is faithful iff two groups are isomorphic ≅.
In this case all actions of ≫∈ are distinct permutations
– that is ≫≠≫' ∀≫, ≫' ∈.
Given any -action on  we can obtain its faithful subgroup that is isomorphic to .
The importance of faithfulness of -action is because it preserves the structure of ,
and if an action is not faithful, we might as well focus on -action.

Given any unfaithful  -action γ: ×→, let K_γ be the normal subgroup of  that corresponds to identity permutation
–K_γ = {≫∈ | γ(g, n) = n ∀ n ∈}.
One obtains the group  that acts faithfully on  as the quotient group =  / K_γ.



We now define some group properties that are important in guaranteeing the “strict” equivariance with respect to -action.
-action on  is transitive iff ∀ n_1,n_2 ∈, there exists at least one action ≫∈ such that ≫ n_1 = n_2. 
The group action is free or semi-regular iff ∀ n_1,n_2 ∈, there is at most one ≫∈ such at ≫ n_1 = n_2, and the action is regular iff it is both transitive and free – for any pair n_1,n_2 ∈, there is uniquely
one ≫∈ such that ≫ n_1 = n_2. Any free action is also faithful. 



  §.§.§ Orbits


Given -action on , the orbit of  n ∈ is all the members to which it can be moved, 
n = {≫ n | n ∈}. The orbits of 
n ∈ form an equivalence relation, where n ∼ n' ⇔∃ g  s.t.,  n = ≫ n' ⇔ n ∈ n' ⇔ n' ∈ n.
This equivalence relation partitions  into orbits = ⋃_1 ≤ p ≤ P n_p, where n_p is an arbitrary representative of the partition 
n_p ⊆.
Note that the -action on  is always transitive on its orbits – that is for any n,n' ∈ n_p, there is at least one ≫∈ such that n = ≫ n'. Therefore, for a semi-regular -action, the action of  on the orbits n_p ∀ 1 ≤ p ≤ P is regular.
As we see the number of distinct parameters in our parameter-sharing scheme grows with the number of orbits.






Cycle Notation. To explicitly show the action of ≫∈ on the set
, we sometimes use the cycle notation of a permutation.
Any permutation ∈S is decomposable to product of disjoint cycles. 
A cycle of length d, (b_1,…,b_d) sends b_i → b_i+1  d. Here b_i ∈ and a cycle acts on a subset of . 
For example, the action of (1,3,2) on [1,…,6] is 
[3,1,2,4,5,6]. We can write the permutation ≫ where ≫ [1,…,6]= [3,1,2,5,4,6] as the product of disjoint cycles 
{(1,3,2),(6),(4,5)} = {(1,3,2),(4,5)}. 






 

















































































 












