  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 applying 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. However, 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 state-of-the-art
results.
