  We introduce Automorphism-based graph neural networks (Autobahn), a new
family of graph neural networks. In an Autobahn, we decompose the graph into a
collection of subgraphs and apply local convolutions that are equivariant to
each subgraph's automorphism group. Specific choices of local neighborhoods and
subgraphs recover existing architectures such as message passing neural
networks. Our formalism also encompasses novel architectures: as an example, we
introduce a graph neural network that decomposes the graph into paths and
cycles. The resulting convolutions reflect the natural way that parts of the
graph can transform, preserving the intuitive meaning of convolution without
sacrificing global permutation equivariance. We validate our approach by
applying Autobahn to molecular graphs, where it achieves results competitive
with state-of-the-art message passing algorithms.
