Autobahn: Automorphism-based Graph Neural Nets

Erik H. Thiede, Wenda Zhou, Risi Kondor

TL;DR

Autobahn is a novel Graph Neural Network (GNN) framework that decomposes graphs into subgraphs and applies convolutions based on their internal symmetries (automorphisms). It offers a powerful middle ground between efficient but limited Message-Passing Neural Networks (MPNNs) and highly expressive but computationally explosive higher-order GNNs, achieving state-of-the-art results on molecular property prediction tasks.

The Limits of Message Passing

Standard Message-Passing Neural Networks (MPNNs) are the workhorses of graph machine learning, but they suffer from a well-documented "glass ceiling." Because they aggregate neighbor information in a strictly permutation-invariant way, their expressive power is theoretically limited by the 1-Weisfeiler-Lehman (1-WL) isomorphism test. In practical terms, this means they cannot distinguish between certain complex graph structures—like different types of rings or grids—and they often suffer from "oversmoothing" as network depth increases.

While "higher-order" GNNs exist to solve this expressivity problem, they typically require processing all possible sets of $k$ nodes. This leads to a combinatorial explosion in memory and computational time. The authors of Autobahn ask a critical question: Can we build a network that is more expressive than an MPNN by leveraging the actual topology of the graph, without incurring the massive cost of higher-order methods?

The Autobahn Architecture

The core idea of Autobahn (Automorphism-based Neural Networks) is to treat specific graph substructures as the fundamental units of computation, rather than individual nodes and edges.

Autobahn templates and convolution process
  1. Subgraph Decomposition: The input graph is broken down into a collection of "local graphs" (subgraphs) that match pre-selected templates, such as paths, cycles, or stars.
  2. Automorphism-based Neurons: Instead of a simple sum or mean of neighbors, Autobahn applies convolutions that are equivariant to the subgraph’s automorphism group (its internal symmetries). For example, if a subgraph is a 6-carbon benzene ring, the network uses a 1D periodic convolution that respects the ring's rotational symmetry.
  3. Information Transfer (Narrowing & Promotion): To allow these subgraphs to communicate, the authors introduce two novel operations:
  4. Narrowing: Compressing information from a subgraph into the intersection it shares with another subgraph.
  5. Promotion: Expanding that shared information to fit the structure of the receiving subgraph.
  6. Global Equivariance: By carefully defining these local operations, the authors mathematically prove that the entire network remains globally permutation-equivariant. The output remains consistent regardless of how the nodes are indexed in the input data.

Theoretical Insights

Autobahn provides several elegant theoretical connections to existing architectures:

  • MPNNs are a Special Case: Standard MPNNs are essentially Autobahns where the "template" is restricted to a star graph (a central node and its immediate neighbors).
  • Recovering CNNs: Unlike standard GNNs, which struggle to replicate the success of Convolutional Neural Networks on grids, an Autobahn using a grid template naturally recovers the behavior of a steerable CNN.
  • Domain-Driven Design: Autobahn allows researchers to inject domain knowledge directly into the architecture. In chemistry, rings (cycles) and chains (paths) are physically meaningful. By choosing these as templates, the network's architecture reflects the underlying "physics" of the molecule (such as molecular resonance).
  • Efficiency through Sparsity: While higher-order GNNs evaluate all possible node tuples, Autobahn only evaluates meaningful subgraphs. This makes higher-order computation feasible for real-world graphs.

Empirical Performance

The authors evaluated Autobahn on several standard molecular property prediction benchmarks, demonstrating highly competitive performance:

  • ZINC Dataset: On the task of predicting constrained solubility, Autobahn excelled. On ZINC 10k, it achieved a Mean Absolute Error (MAE) of 0.106, significantly outperforming standard GCNs (0.367) and GINE-E (0.252), and matching or beating other subgraph-based methods like GSN. On the full ZINC dataset, it achieved an MAE of 0.029, setting a very competitive mark against state-of-the-art baselines.
  • OGB (Open Graph Benchmark): The model remained competitive with state-of-the-art MPNNs across the MolPCBA, MolHIV, and MUV datasets, proving that its specialized architecture does not sacrifice general performance on diverse biological activity and toxicity tasks.

Limitations and Future Directions

While Autobahn is a significant step forward, it comes with a few trade-offs:

  • Template Selection: Currently, the choice of templates (e.g., "paths of length 3-6") is a manual design choice made by the researcher based on domain knowledge. Automating this selection or learning the templates end-to-end remains an open challenge.
  • Preprocessing Overhead: The network requires finding all instances of the chosen subgraphs (subgraph isomorphism) before training. While efficient heuristics exist for small templates, this adds a preprocessing step absent in standard MPNNs.

Future work will likely explore more complex "generic" templates and tree-like substructures to determine if they provide better inductive biases for non-molecular graphs, such as social networks or citation graphs.

Summary updated

Abstract

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.
BibTeX
@inproceedings{thiede2021autobahn,
  author = {Erik H. Thiede and Wenda Zhou and Risi Kondor},
  title = {{Autobahn: Automorphism-based Graph Neural Nets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=QRuKBUAg8S},
}
Figure