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 (1)

• Predicting multicellular function through multi-layer tissue 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