Graph Automorphism Group Equivariant Neural Networks

2023/07/15 by Edward Pearce-Crump, Pearce-Crump, Edward, Knottenbelt, William J. · 1 citation
Computer Science · Neuroscience · Physics and Astronomy · #Advanced Graph Neural Networks #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Functional Brain Connectivity Studies #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Representation Theory (math.RT)

paper · pdf · doi:10.48550/arxiv.2307.07810

openalex publication_date 2023/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

Cited by

• Learning Group Actions In Disentangled Latent Image Representations

Related

• How Jellyfish Characterise Alternating Group Equivariant Neural Networks
• Brauer's Group Equivariant Neural Networks
• Approximately Equivariant Graph Networks
• A Practical Method for Constructing Equivariant Multilayer Perceptrons\n for Arbitrary Matrix Groups
• E(n) Equivariant Graph Neural Networks