Expressiveness and Approximation Properties of Graph Neural Networks
  Characterizing the separation power of graph neural networks (GNNs) provides
an understanding of their limitations for graph learning tasks. Results
regarding separation power are, however, usually geared at specific GNN
architectures, and tools for understanding arbitrary GNN architectures are
generally lacking. We provide an elegant way to easily obtain bounds on the
separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which
have become the yardstick to measure the separation power of GNNs. The crux is
to view GNNs as expressions in a procedural tensor language describing the
computations in the layers of the GNNs. Then, by a simple analysis of the
obtained expressions, in terms of the number of indexes and the nesting depth
of summations, bounds on the separation power in terms of the WL-tests readily
follow. We use tensor language to define Higher-Order Message-Passing Neural
Networks (or k-MPNNs), a natural extension of MPNNs. Furthermore, the tensor
language point of view allows for the derivation of universality results for
classes of GNNs in a natural way. Our approach provides a toolbox with which
GNN architecture designers can analyze the separation power of their GNNs,
without needing to know the intricacies of the WL-tests. We also provide
insights in what is needed to boost the separation power of GNNs.
