# Autobahn: Automorphism-based Graph Neural Nets

arXiv: https://arxiv.org/abs/2103.01710 · HTML: https://mlsanity.com/paper/2103.01710/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 54 references that are in the map.
- First posted on arXiv 2 Mar 2021.

## Builds on (most cited first, 30 of 35)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Steerable CNNs](https://mlsanity.com/paper/1612.08498/) (2016)
- [On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups](https://mlsanity.com/paper/1802.03690/) (2018)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [A General Theory of Equivariant CNNs on Homogeneous Spaces](https://mlsanity.com/paper/1811.02017/) (2018)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Clebsch-Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network](https://mlsanity.com/paper/1806.09231/) (2018)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Directional Graph Networks](https://mlsanity.com/paper/2010.02863/) (2020)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)
- [Subgraph Neural Networks](https://mlsanity.com/paper/2006.10538/) (2020)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)

## Built on by (most cited first, 30 of 39)

- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Physics-Guided Deep Learning for Dynamical Systems: A Survey](https://mlsanity.com/paper/2107.01272/) (2021)
- [Learning Physical Dynamics with Subequivariant Graph Neural Networks](https://mlsanity.com/paper/2210.06876/) (2022)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [Cooperative Graph Neural Networks](https://mlsanity.com/paper/2310.01267/) (2023)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Learning Probabilistic Symmetrization for Architecture Agnostic Equivariance](https://mlsanity.com/paper/2306.02866/) (2023)
- [From Continuous Dynamics to Graph Neural Networks: Neural Diffusion and Beyond](https://mlsanity.com/paper/2310.10121/) (2023)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)
- [Going Deeper into Permutation-Sensitive Graph Neural Networks](https://mlsanity.com/paper/2205.14368/) (2022)
- [Machine learning and invariant theory](https://mlsanity.com/paper/2209.14991/) (2022)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [PlanE: Representation Learning over Planar Graphs](https://mlsanity.com/paper/2307.01180/) (2023)
- [Expressivity and Generalization: Fragment-Biases for Molecular GNNs](https://mlsanity.com/paper/2406.08210/) (2024)
- [Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Information](https://mlsanity.com/paper/2406.19244/) (2024)
- [Union Subgraph Neural Networks](https://mlsanity.com/paper/2305.15747/) (2023)
- [MuGSI: Distilling GNNs with Multi-Granularity Structural Information for Graph Classification](https://mlsanity.com/paper/2406.19832/) (2024)
- [Transformers are efficient hierarchical chemical graph learners](https://mlsanity.com/paper/2310.01704/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Beyond permutation equivariance in graph networks](https://mlsanity.com/paper/2103.14066/) (2021)

## Abstract (arXiv)

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.