  In this paper we cast neural networks defined on graphs as message-passing
neural networks (MPNNs) in order to study the distinguishing power of different
classes of such models. We are interested in whether certain architectures are
able to tell vertices apart based on the feature labels given as input with the
graph. We consider two variants of MPNNS: anonymous MPNNs whose message
functions depend only on the labels of vertices involved; and degree-aware
MPNNs in which message functions can additionally use information regarding the
degree of vertices. The former class covers a popular formalisms for computing
functions on graphs: graph neural networks (GNN). The latter covers the
so-called graph convolutional networks (GCNs), a recently introduced variant of
GNNs by Kipf and Welling. We obtain lower and upper bounds on the
distinguishing power of MPNNs in terms of the distinguishing power of the
Weisfeiler-Lehman (WL) algorithm. Our results imply that (i) the distinguishing
power of GCNs is bounded by the WL algorithm, but that they are one step ahead;
(ii) the WL algorithm cannot be simulated by "plain vanilla" GCNs but the
addition of a trade-off parameter between features of the vertex and those of
its neighbours (as proposed by Kipf and Welling themselves) resolves this
problem.
