A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks
This provides a foundational theoretical insight for researchers in graph neural networks, though it is incremental as it builds on prior work.
The paper tackles the problem of proving universality for invariant and equivariant graph neural networks, presenting a simple proof that resolves an open case for higher-order output and explains tensorization in existing models.
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.