Graph Automorphism Group Equivariant Neural Networks
This work addresses the need for more precise symmetry handling in graph neural networks, with potential applications in domains where finite group symmetries are relevant, though it appears incremental as it builds on existing equivariant network frameworks.
The paper tackles the problem of designing neural networks that are equivariant to the automorphism group of a graph, rather than the symmetric group, to better capture graph symmetries. It provides a full characterization of learnable linear Aut(G)-equivariant functions and finds a spanning set of matrices for these functions.
Permutation equivariant neural networks are typically used to learn from data that lives on a graph. However, for any graph $G$ that has $n$ vertices, using the symmetric group $S_n$ as its group of symmetries does not take into account the relations that exist between the vertices. Given that the actual group of symmetries is the automorphism group Aut$(G)$, we show how to construct neural networks that are equivariant to Aut$(G)$ by obtaining a full characterisation of the learnable, linear, Aut$(G)$-equivariant functions between layers that are some tensor power of $\mathbb{R}^{n}$. In particular, we find a spanning set of matrices for these layer functions in the standard basis of $\mathbb{R}^{n}$. This result has important consequences for learning from data whose group of symmetries is a finite group because a theorem by Frucht (1938) showed that any finite group is isomorphic to the automorphism group of a graph.