Foundations of Equivariant Deep Learning: Unifying Graph and Sheaf Neural Networks

We develop order-equivariant neural networks (OENN), which generalize standard graph message passing and sheaf neural networks via the face-poset viewpoint. We (i) characterize all linear order-equivariant maps, (ii) build OENN layers, and (iii) prove a universal approximation theorem (UAT) for continuous order-equivariant maps, which is a new result even when restricted to sheaf neural networks (for which no UAT was known before). We illustrate the framework on graph and sheaf models. Our results can also be seen as extending the UAT for graph neural networks to a more general setting that subsumes sheaf neural networks as well.