Graph Automorphism Group Equivariant Neural Networks

Edward Pearce-Crump, William Knottenbelt
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:40051-40077, 2024.

Abstract

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 Sn 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 Rn. In particular, we find a spanning set of matrices for these layer functions in the standard basis of Rn. 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v235-pearce-crump24a, title = {Graph Automorphism Group Equivariant Neural Networks}, author = {Pearce-Crump, Edward and Knottenbelt, William}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {40051--40077}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/pearce-crump24a/pearce-crump24a.pdf}, url = {https://proceedings.mlr.press/v235/pearce-crump24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Graph Automorphism Group Equivariant Neural Networks %A Edward Pearce-Crump %A William Knottenbelt %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-pearce-crump24a %I PMLR %P 40051--40077 %U https://proceedings.mlr.press/v235/pearce-crump24a.html %V 235 %X 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.
APA
Pearce-Crump, E. & Knottenbelt, W.. (2024). Graph Automorphism Group Equivariant Neural Networks. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:40051-40077 Available from https://proceedings.mlr.press/v235/pearce-crump24a.html.

Related Material