Research map / Graph learning / GNN architectures

Graph Automorphism Group Equivariant Neural Networks

ICML 2024 · Graph learning › GNN architectures · approach: Oversmoothing and heterophily · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterises all linear maps between tensor powers of R^n that are equivariant to a graph's automorphism group Aut(G), giving a spanning set via bilabelled graphs and G-homomorphism matrices, using Frucht's theorem to cover any finite group.

Problem

Permutation-equivariant networks ignore the graph structure of the symmetry; the true symmetry group of a graph is its automorphism group, so equivariant layers to Aut(G) are needed.

Approach

Relate spanning-set elements of Hom_{Aut(G)}((R^n)^{⊗k},(R^n)^{⊗l}) to isomorphism classes of (k,l)-bilabelled graphs via G-homomorphism matrices, leveraging the quantum-isomorphism framework of Mancinska and Roberson, and apply Frucht's theorem so any finite group can be realised as Aut(G).

Key results

• Spanning set for Hom_{Aut(G)}((R^n)^{⊗k},(R^n)^{⊗l}) is given by all G-homomorphism matrices of (k,l)-bilabelled graphs (Theorem on spanning set).
• Recovers the set-partition diagram basis for S_n-equivariant linear maps by using the complement of K_n (Aut = S_n).
• Worked example gives a basis for Hom_{D_4}(R^4,R^4) for the automorphism group of 2K_2, a case the authors say is missing from the literature.

Limitations

• Number of bilabelled graph isomorphism classes, and hence spanning set size, grows exponentially with n, k and l
• Practical implementation of high-order equivariant layers is memory-intensive, requiring custom kernels
• Purely theoretical; no experiments on learning tasks

Experimental setup

Builds on: Mancinska and Roberson quantum isomorphism / G-homomorphism matrices Pearce-Crump partition-diagram characterisation of S_n-equivariant layers Chassaniol's generating set Frucht's theorem

Closest papers by meaning

• Permutation Equivariant Neural Networks for Symmetric Tensors (ICML 2025 · similarity 0.91)
• A Characterization Theorem for Equivariant Networks with Point-wise Activations (ICLR 2024 · similarity 0.89)
• On Universality Classes of Equivariant Networks (NeurIPS 2025 · similarity 0.88)
• Improving Equivariant Networks with Probabilistic Symmetry Breaking (ICLR 2025 · similarity 0.88)
• Schur Nets: exploiting local structure for equivariance in higher order graph neural networks (NeurIPS 2024 · similarity 0.88)
• Are High-Degree Representations Really Unnecessary in Equivariant Graph Neural Networks? (NeurIPS 2024 · similarity 0.88)