A key requirement for graph neural networks is that they must process a graph
in a way that does not depend on how the graph is described. Traditionally this
has been taken to mean that a graph network must be equivariant to node
permutations. Here we show that instead of equivariance, the more general
concept of naturality is sufficient for a graph network to be well-defined,
opening up a larger class of graph networks. We define global and local natural
graph networks, the latter of which are as scalable as conventional message
passing graph neural networks while being more flexible. We give one practical
instantiation of a natural network on graphs which uses an equivariant message
network parameterization, yielding good performance on several benchmarks.