A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks

Abstract

We present a simple proof for the universality of invariant and equivariant tensorized graph neural networks. Our approach considers a restricted intermediate hypothetical model named Graph Homomorphism Model to reach the universality conclusions including an open case for higher-order output. We find that our proposed technique not only leads to simple proofs of the universality properties but also gives a natural explanation for the tensorization of the previously studied models. Finally, we give some remarks on the connection between our model and the continuous representation of graphs.

References in corpus (6)

• Group Equivariant Convolutional Networks
• Predicting multicellular function through multi-layer tissue networks
• On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
• Universal Invariant and Equivariant Graph Neural Networks
• Equivariance Through Parameter-Sharing
• Universal approximations of permutation invariant/equivariant functions by deep neural networks

Cited by in corpus (8)

• On Learning Sets of Symmetric Elements
• On the Universality of Rotation Equivariant Point Cloud Networks
• Expressive Power of Invariant and Equivariant Graph Neural Networks
• Universal Approximation Theorem for Equivariant Maps by Group CNNs
• Reconstruction for Powerful Graph Representations
• Equivariant and Invariant Reynolds Networks
• Neural Trees for Learning on Graphs
• Abelian Neural Networks