Expressive Power of Invariant and Equivariant Graph Neural Networks

Understand

Various classes of Graph Neural Networks (GNN) have been proposed and shown to be successful in a wide range of applications with graph structured data.

• In this paper, we propose a theoretical framework able to compare the expressive power of these GNN architectures.
• The current universality theorems only apply to intractable classes of GNNs.
• Here, we prove the first approximation guarantees for practical GNNs, paving the way for a better understanding of their generalization.