Autobahn: Automorphism-based Graph Neural Nets

Erik Henning Thiede, Wenda Zhou, Risi Kondor

Abstract

Standard Graph Neural Networks (GNNs) primarily rely on node-level message passing, which limits their ability to capture complex structural motifs such as chemical rings. We present Autobahn, a framework that elevates the fundamental unit of computation from individual nodes to entire subgraphs. By employing convolutions equivariant to subgraph automorphism groups, Autobahn achieves high expressivity—comparable to higher-order GNNs—while maintaining computational efficiency by operating only on existing subgraphs.

Introduction

Message-Passing Neural Networks (MPNNs) are the standard for graph-based deep learning due to their efficiency and permutation invariance. However, they possess a fundamental limitation: they cannot distinguish certain non-isomorphic graphs or count critical substructures like triangles and large cycles. This is particularly problematic in organic chemistry, where molecular properties are often determined by multi-atom structures like aromatic rings rather than isolated bonds.

While higher-order GNNs (e.g., $k$-WL based models) offer greater expressivity, they suffer from $O(N^k)$ complexity, making them impractical for large-scale applications. Autobahn addresses this gap by leveraging the graph's inherent topology to build expressive yet sparse neural architectures.

Methods: Subgraph-Based Learning

The Autobahn framework shifts the focus from nodes to local subgraphs that match pre-defined "templates."

Template Matching and Symmetry

Instead of aggregating neighbor features at each node, the graph is decomposed into subgraphs matching specific templates, such as paths or cycles. Each subgraph is assigned a neuron that performs a convolution respecting the subgraph's automorphism group—the set of symmetries (rotations, reflections) that leave the structure invariant.

Examples of subgraph templates and their corresponding automorphism groups, ranging from simple nodes to cycles and stars.

The Autobahn Framework

The core of Autobahn lies in its ability to process these subgraphs equivariantly. For a given template, the network applies a weight matrix that is constrained by the symmetries of that template. This ensures that the learned features are consistent regardless of how the nodes within the subgraph are indexed.

A detailed view of an equivariant convolution on a cycle template, illustrating how weight sharing and permutations maintain symmetry.

To facilitate information flow across the graph, Autobahn introduces two operations:

  1. Narrowing: Compresses a subgraph neuron's output to the nodes it shares with overlapping structures.
  2. Promotion: Expands these compressed signals into the shape of a new receiving subgraph.

Theoretical Insights

Autobahn provides a unifying perspective on graph learning:

  • Generalization: Standard MPNNs are recovered when using a "star graph" template. Traditional CNNs are recovered when applying Autobahn to a grid graph with a grid template.
  • Sparse Higher-Order Expressivity: By computing only on existing subgraphs rather than all possible node combinations, Autobahn achieves the power of higher-order GNNs without the combinatorial cost.
  • Computation vs. Counting: Unlike models that merely use subgraph counts as features, Autobahn performs convolutions over the symmetries of those subgraphs, providing a strictly more expressive representation.

Experimental Results

Autobahn was evaluated on molecular property prediction benchmarks, demonstrating state-of-the-art performance. On the ZINC 10k dataset, it achieved a Mean Absolute Error (MAE) of 0.106, outperforming strong baselines like GSN (0.108) and standard GCNs (0.367). Similar success was seen on the Open Graph Benchmark (OGB), where Autobahn achieved an Average Precision of 0.119 on MUV and a ROC-AUC of 0.780 on MolHIV.

Conclusion

Autobahn offers a powerful middle ground between simple MPNNs and expensive higher-order GNNs. By centering computation on subgraphs and their symmetries, it captures the structural essence of complex data like molecules. Future work will focus on automating template selection and exploring generic templates to reduce the reliance on domain-specific knowledge.

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 Henning 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