Equivariance Through Parameter-Sharing

Group Action and Equivariance

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

Symmetry Groups of a Network

Structure Design

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

2 Sparse Design

Our sparse construction uses orbits and symmetric generating sets:

The set ${\mathcal{A}}\subseteq{\mathcal{G}}$ is called the generating set of ${\mathcal{G}}$ ($<{\mathcal{A}}>={\mathcal{G}}$), iff every member of ${\mathcal{G}}$ can be expressed as a combination of members of ${\mathcal{A}}$. If the generating set is closed under inverse ${\mathcal{a}}\in{\mathcal{A}}\Rightarrow{\mathcal{a}}^{-1}\in{\mathcal{A}}$ we call it a symmetric generating set.

In words, we have one color per each combination of orbits ($p$, $q$) and members of the generating set ${\mathcal{a}}\in{\mathcal{A}}$. The following theorem relates the symmetry group of this structure to ${\mathcal{G}}$.

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

3 Multiple Channels

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

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.

References

Appendix A Proofs

of Theorem 2.1 For unique $\mathcal{Aut}({\Omega})$-equivariance we need proofs in two directions. First we show that

The orbit-size, $|\mathcal{Aut}({\Omega}){(n,m)}|$, for a pair $(n,m)$ is bounded by the size of its relation $|\Delta_{p,q,{\mathcal{a}}}|$, for some $p,q,{\mathcal{a}}$. This is because, according to Eq. 3,

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 ${\Omega}$ is connected then fixing a pair guarantees that all pairs in all relations of ${\Omega}$ are fixed and therefore $(n,m)$ has a trivial stabilizer.

Two properties guarantee the connectedness of ${\Omega}$:

of Corollary 3.4 Follows directly from Theorems 2.1 and 3.3. $\blacksquare$

If we further tie the parameters across the orbits so that ${w}_{{\mathcal{a}},p}={w}_{{\mathcal{a}},p^{\prime}}\forall p,p^{\prime}$, the Eq. 19 above is equivalent to formulation of (Cohen & Welling, 2016a) for a single input/output channels (see Section 3.3 for multiple channels). $\blacksquare$

of Corollary 3.6 First we show this assuming a single channel $K=1$. For multiple channels see Section 3.3.

Appendix B Background on Permutation Groups

Cayley Diagram. The set ${\mathcal{A}}\subseteq{\mathcal{G}}$ is called the generating set of ${\mathcal{G}}$ ($<{\mathcal{A}}>={\mathcal{G}}$), iff every member of ${\mathcal{G}}$ can be expressed as a combination of members of ${\mathcal{A}}$. If the generating set is closed under inverse ${\mathcal{a}}\in{\mathcal{A}}\Rightarrow{\mathcal{a}}^{-1}\in{\mathcal{A}}$ we call it a symmetric generating set. ${\mathcal{A}}$ is the minimal generating set if it has the least number of members among the generating sets of ${\mathcal{G}}$. Note that the minimal generating sets are generally not unique. The size of the minimal generating set of a group ${\mathcal{G}}$ becomes important because, the number of parameters in our parameter-sharing scheme grows linearly with $|{\mathcal{A}}|$. A group ${\mathcal{G}}$ is often visualized by its Cayley diagram; a colored digraph in which the node-set is ${\mathcal{G}}$ and directed edge $({\mathcal{g}},{\mathcal{a}}{\mathcal{g}})\forall{\mathcal{g}}\in{\mathcal{G}},{\mathcal{a}}\in{\mathcal{A}}$ is colored by ${\mathcal{a}}\in{\mathcal{A}}$. Fig. 1(lower-left) shows the Cayley diagram of ${\mathcal{G}}={\mathcal{D}}_{5}$.

B.1.2 Orbits