  The pairwise interaction paradigm of graph machine learning has predominantly
governed the modelling of relational systems. However, graphs alone cannot
capture the multi-level interactions present in many complex systems and the
expressive power of such schemes was proven to be limited. To overcome these
limitations, we propose Message Passing Simplicial Networks (MPSNs), a class of
models that perform message passing on simplicial complexes (SCs) - topological
objects generalising graphs to higher dimensions. To theoretically analyse the
expressivity of our model we introduce a Simplicial Weisfeiler-Lehman (SWL)
colouring procedure for distinguishing non-isomorphic SCs. We relate the power
of SWL to the problem of distinguishing non-isomorphic graphs and show that SWL
and MPSNs are strictly more powerful than the WL test and not less powerful
than the 3-WL test. We deepen the analysis by comparing our model with
traditional graph neural networks with ReLU activations in terms of the number
of linear regions of the functions they can represent. We empirically support
our theoretical claims by showing that MPSNs can distinguish challenging
strongly regular graphs for which GNNs fail and, when equipped with orientation
equivariant layers, they can improve classification accuracy in oriented SCs
compared to a GNN baseline. Additionally, we implement a library for message
passing on simplicial complexes that we envision to release in due course.
