  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). 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 (GNNs) 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.

Machine Learning;Social and Information Networks