Autobahn: Automorphism-based Graph Neural Nets
Year: 2022

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.

heading: 1 Introduction
text: The successes of artificial neural networks in domains such as computer vision and natural language processing have inspired substantial interest in developing neural architectures on graphs. Since graphs naturally capture relational information, graph-structured data appears in a myriad of fields. However, working with graph data raises new problems. Chief among them is the problem of graph isomorphism: for the output of our neural network to be reliable, it is critical that the network gives the same result independent of trivial changes in graph representation such as permutation of nodes.
Considerable effort has gone into constructing neural network architectures that obey this constraint[1– 5]. Arguably, the most popular approach is to construct Message-Passing Neural Networks (MPNNs)[6, 7]. In each layer of an MPNN, every node aggregates the activations of its neighbors in a permutation invariant manner and applies a linear mixing and nonlinearity to the resulting vector. While subsequent architectures have built on this paradigm, e.g., by improving activations on nodes and graph edges [8, 9], the core paradigm of repeatedly pooling information from neighboring nodes has remained. These architectures are memory efficient, intuitively appealing, and respect the graph’s symmetry under permutation of its nodes. However, practical results have shown that they can oversmooth signals [10] and theoretical work has shown that they have trouble distinguishing certain graphs and counting substructures [8, 11–13]. Moreover, MPNNs do not use the graph’s topology to its fullest extent. For instance, applying an MPNN to highly structured graphs such as grid graphs does not recover powerful known architectures such as convolutional neural networks. It is also not clear how to best adapt MPNNs to families of graphs with radically different topologies: MPNNs for citation graphs and molecular graphs are constructed in largely the same way. This suggests that it should be possible to construct more expressive graph neural networks by directly leveraging the graph’s structure.
In this work, we introduce a new framework for constructing graph neural networks, Automorphismbased Neural Networks (Autobahn). Our research is motivated by our goal of designing neural
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
networks that can learn the properties of small organic molecules accurately enough to make a significant contribution to drug discovery and materials design [14–17]. The properties of these molecules depend crucially on multi-atom substructures, making the difficulties MPNNs have in recognizing substructures a critical problem. We realized that we could circumvent this limitation by making graph substructures themselves the fundamental units of computation. The symmetries of our substructures then inform the computation. For instance, the benzene molecule forms a ring of six atoms and is a common subunit in larger molecules. On this ring we have a very natural and mathematically rigorous notion of convolution: convolution on a one-dimensional, periodic domain. This symmetry is encoded by a graph’s automorphism group: the group that reflects our substructures’ internal symmetries. Our networks directly leverage the automorphism group of subgraphs to construct flexible, efficient neurons. Message passing neural networks arise naturally in this framework when the substructures used are local star graphs, and applying Autobahn to grid graphs can recover standard convolutional architectures such as steerable CNNs. More generally, Autobahn gives practitioners the tools to build bespoke graph neural networks whose substructures reflect their domain knowledge. As an example, in Section 6, we present a novel architecture outside of the message-passing paradigm that nevertheless achieves performance competitive with state-of-the-art MPNNs on molecular learning tasks.

heading: 2 Graph Neural Networks
text: Neural Networks operate by composing several learned mappings known as “layers”. Denoting the `’th layer in the network as φ`, the functional form of a neural network Φ can be written as
Φ = φL ◦ φL−1 ◦ . . . ◦ φ1.
Each layer is typically constructed from a collection of parts, the titular “neurons”. We denote the i’th neuron in the `’th layer as n`i , and denote its output (the “activation” of the neuron) as f ` i . Architectures differ primarily in how the neurons are constructed and how their inputs and outputs are combined.
When constructing a neural network that operates on graph data, care must be taken to preserve the input graphs’ natural symmetries under permutation. Let G be a graph with node set {v1, . . . , vn}, adjacency matrix A∈Rn×n and d-dimensional node labels bi ∈ Rd stacked into a matrix B ∈Rn×d. Permuting the numbering of the nodes of G by some permutation σ : {1, 2, . . . , n} → {1, 2, . . . , n} transforms A 7→ Aσ Aσi,j = Aσ−1(i),σ−1(j), (1) and B 7→ Bσ Bσi,n = Bσ−1(i),n. (2) This transformation does not change the actual topology of G. Consequently, a fundamental requirement on graph neural networks is that they be invariant with respect to such permutations.

heading: 2.1 Message-Passing Neural Networks
text: Message-passing neural networks (MPNNs) have emerged as the dominant paradigm for constructing neural networks on graphs. Every neuron in an MPNN corresponds to a single node in the graph. Neurons aggregate features from neighboring nodes by passing them through a permutation invariant function. They then combine the result with the node’s original message, and pass the result through a learned linear function and nonlinearity (Figure 1)[8]. Since information is transmitted over the graph’s topology, MPNNs are not confounded by permutations of the graph. Specific architectures
may differ in the details of the aggregation function [6, 8, 18, 19], may include additional terms to account for edge features [8, 9], may use complex transformations to construct the node features encoding local structure [20, 21], or may augment the graph with additional nodes [22, 23].

heading: 3 Permutation Equivariance
text: As discussed in the Introduction, MPNNs have fundamental limits to their expressiveness. To construct more powerful neural networks, we turn to the general formalism of group equivariant networks [24–27]. Our desire that permutations of the input graph leave our network’s output unaffected is formalized by the notion of group-invariance. Let us assume that our input data lives in a space X that is acted on by a group G, and for all g ∈ G denote the associated group action on X by Tg . The invariance constraint amounts to requiring:
Φ = Φ ◦ Tg ∀g ∈ G. (3)
One way to satisfy this would be to require that each layer φ` be fully invariant to G. However, in practice this condition can be extremely restrictive. For this reason, networks commonly use group equivariant layers. Let X and Y be the input and output spaces of φ`, with group actions Tg and T ′g , respectively. We say φ` is equivariant to G if it obeys
T ′g ◦ φ` = φ` ◦ Tg ∀g ∈ G. (4)
This condition is weaker than invariance: we recover invariance when T ′g maps every element of Y to itself. Moreover, it is simple to show that the composition of two equivariant layers is also equivariant. Consequently, in all layers but the last we can enforce the weaker condition of equivariance and merely enforce invariance in the final layer. In the case of graph neural networks, the relevant group is the group of permutations: Sn (called the symmetric group of degree n).

heading: 3.1 Permutation-equivariant networks
text: Recent work has developed a generic recipe for constructing group equivariant networks. In this formalism, any object that transforms under a group action is treated as a function on the group [24] (see Section 1 in the supplement for a brief review). This allows all layers equivariant to the group to be treated using the same formalism, independently of how inputs and outputs transform. In particular, it can be shown that the only group-equivariant linear operation possible is a generalized notion of group convolution. For discrete groups, this convolution can be written as:
(f ∗ w) (u) = ∑ v∈G f(uv−1)w(v). (5)
To construct an equivariant neuron, we apply (5) to convolve our input activation f `−1 with a learned weight function w, add a bias, and then apply a fixed equivariant nonlinearity, ν. Applying this approach to specific groups recovers the standard convolutional layers used in convolutional neural networks (CNNs). For instance, applying (5) to the cyclic group of order n gives
(f ∗ w)j = n∑ k=0 f(rj−k)w(rk), (6)
where r is the group element corresponding to rotation by 360/n degrees. Similarly, applying (5) to one-dimensional or two-dimensional discrete translation groups recovers the standard convolutions used for image processing.
Instantiating this theory with the symmetric group has been successfully used to construct permutation equivariant networks for learning tasks defined on sets [28] and for graph neural networks [29–32]. However, enforcing equivariance to all permutations can be very restrictive. As an example, consider a layer whose domain and range transform according to (2) with cin incoming and cout outgoing channels. Let w1, w2 ∈ Rcout×cin be learned weight matrices, and fj ∈ Rcin be the vector of incoming activations corresponding to node j. The most general possible convolution is then [28]
(f ∗ w)i = w1fi + w2 n∑ j=1 fj , (7)
but this is quite a weak model as activations from different nodes only interact through their sum. Consequently, relationships between nodes can only be captured in aggregate.
Algorithm 1 Automorphism-based Neuron Input:
f `−1 . Incoming activation associated with G AG . Adjacency matrix of G AT . Adjacency matrix of the saved template graph. 1: Find µ ∈ Sn such that AµG = AT . 2: (f `−1)µ ← Tµ(f `−1) . Apply µ to incoming activation. 3: (f `)µ ← ν ( (f `−1)µ ∗ w + b ) . Convolution is over Aut(T ). 4: f ` ← T ′µ−1((f `)µ) . Map output to original ordering
Return: f `
To address this fundamental limitation, several recent works considered improving the expressivity of MPNNs by defining higher order activations corresponding to pairs, triplets, or, in general, k–tuples of nodes [29, 32, 33]. Mathematically, this requires considering not just (1) and (2), but the action of the symmetric group on k’th order tensors, Aσi1,...,ik = Aσ−1(i1),...,σ−1(ik). However, this can be prohibitively expensive for many nodes. For instance, organic chemistry depends crucially on the existence of aromatic rings, typically of six atoms. Manipulating sixth order tensors would be extremely costly.

heading: 4 Permutation-Equivariant Neurons using Automorphism
text: The key theoretical idea underlying our work is that to construct more flexible neural networks, we can exploit the graph topology itself. In particular, the local adjacency matrix itself can be used to judiciously break permutation symmetry, allowing us to identify nodes up to the symmetries of A. Letting G be a graph as before, the automorphism group Aut(G) is:
Aut(G) = {σ ∈ Sn |Aσ = A } , (8)
where Aσ is defined as in (1). Figure 2a shows the automorphism group of four example graphs.
If G and G′ are two isomorphic graphs, then each node or edge in G′ can always be matched to a node or edge in G up to a permutation in Aut(G). If every graph our network observed was in the same isomorphism class, we could construct a neuron in a permutation-equivariant neural network by matching G to a template graph T and convolving over Aut(T ). We give pseudocode for such a neuron, which we call an “Automorphism-based neuron,” in Algorithm 1. Note that although the convolution itself is only equivariant to Aut(T ), the entire neuron is permutation-equivariant. A formal proof of equivariance is given in Section 2 of the Supplement.
For a given input and output space, neurons constructed using Algorithm 1 are more flexible than a neuron constructed using only Sn convolution. As an example, consider a neuron operating on graphs isomorphic to the top left graph in Figure 2a and whose input and output features are a single channel of node features. An Sn-convolution would operate according to (7): Each output node feature would see only the corresponding input feature and an aggregate of all other node features. In contrast, Algorithm 1 completely canonicalizes the graph since this particular graph has no non-trivial automorphisms. Consequently, we do not need to worry about enforcing symmetry and we can simply run a fully connected layer: a richer representation, since it does not require the same degree of "parameter sharing" as (7). Similarly, Figure 2b depicts an analogous neuron constructed in the presence of cyclic graph symmetry. In this case, the matching can be performed up to a cyclic permutation, so convolution must be equivariant to the graph’s automorphism group, C6.
This general strategy was first described by de Haan et al. [34]. While the increased flexibility was noted, the authors also observed rightfully that this strategy is not directly practical. Most graph learning problems consist either of many graphs from different isomorphism classes or a single large graph that is only partially known. In the former case, we would have to construct one network for every isomorphism class and each network would only see a fraction of the data. In the latter, the isomorphism class of the network would be unknown.

heading: 5 Autobahn
text: To motivate our approach we consider MPNNs from the perspective of Algorithm 1. Looking at Figure 1 we see that the message-passing procedure itself forms a star graph, where the leaves of
the star correspond to the neighboring nodes. The automorphism group of a star graph is the set of all permutations that swap the star’s leaves. This is precisely the group structure of a single MPNN neuron. Since we apply a permutation-invariant aggregation function, if we were to permute a neuron’s input data between the leaves of the star, the MPNN neuron would be unaffected. However, permuting the input features for the central node with one of its neighbors would “break” the MPNN.
This suggests a natural generalization of MPNNs. In every layer, we decompose a graph into a collection of subgraphs known as local graphs that are isomorphic to a pre-selected template graph. Although in worst case this may be polynomially expensive, for “real world” graphs we expect that it can be solved efficiently. In particular, one can leverage the well-developed literature of efficient search heuristics [35–38]. We next construct a permutation-equivariant neuron on each local graph, denoting the local graph of neuron n`j as G`j . Each neuron operates by aggregating information from overlapping local graphs and then applying Algorithm 1 to the result. Because of the important role played by convolutions over subgraphs’ automorphism groups, we refer to the resulting networks as Automorphism-based Neural Networks, or Autobahns.
MPNNs are not the only commonly used algorithm that can be recovered by the Autobahn formalism. In Section 3 in the supplement we show that using a grid graph template on a larger grid graph recovers steerable CNNs [26]1. The fact that Autobahn networks naturally recover these architectures when MPNNs do not suggests that considering the local automorphism group is a productive direction for incorporating graph structure.
Our work builds on a considerable body of literature on constructing neural networks with higherorder activations [33, 34, 39, 40]. Arguably, our work is most closely related to natural graph networks (NGNs), the formalism proposed in [34]. However, NGNs associate neurons with neighborhoods of individual nodes and edges, making the direct use of automorphic convolutions impractical for generic graphs. The specific architecture proposed in [34] instead combined multiple message passing networks, each applied to a local neighborhood of the graph. In contrast, Autobahn associates neurons with subgraphs instead of specific nodes or edges. To our knowledge, this is the first work to explicitly consider constructing neurons equivariant to the automorphism group of subgraphs. This additional flexibility allows us to build practical networks using the convolutions described in Section 4
In the discussion that follows, we give a generic treatment of each step in the network, followed by a full description of an Autobahn layer. We do not specify a specific form for the activations: they may correspond to individual nodes, edges, hyper-edges, or be delocalized over the entire local graph. This is in keeping with our philosophy of giving a flexible recipe that practitioners can tailor to their specific problems using their domain knowledge.
1Standard CNNs further break the symmetry of the grid graph by introducing a notion of up/down and left/right. However, if we introduce a notion of edge “color” to distinguish horizontal from vertical edges and extend our definition of automorphism to include color, Autobahn can recover CNNs as well: see Section 3 in the Supplement.

heading: 5.1 Convolutions using the Automorphism Group
text: The convolutions in Autobahn proceed by applying Algorithm 1 to each neuron’s local graph. The precise form of the convolution will depend on how the activation transforms under permutation. In [24] it was observed that for any compact group, one could construct the appropriate notion of group convolution by expressing the activation in the group’s Fourier space and applying the noncommmutative generalization of the convolution theorem. Subsequent work has lead to software libraries that convolve over arbitrary finite groups [41]. Moreover, for specific groups simple convolutions are either known or intuitive to derive. For instance, in Section 6, our architecture uses directed cycle and path graphs as templates. There, group convolutions can be performed using well-known one-dimensional convolutions such as (6).

heading: 5.2 Transferring information across neurons
text: To build a rich representation of the structure graph we must be able to transmit information between neurons operating on different local graphs. In MPNNs and CNNs, each neuron pools information into the central node before transmitting to its neighbors. This simplifies the task of transmitting information to other neurons, as the output of neuron n`j becomes a node feature for neuron n `+1 k . However, this strategy does not necessarily work for the neurons in Autobahn: our local graphs may not have a central node. Even if they do, collapsing each neuron’s output into a single node could limit our network’s expressivity, as it prevents neurons from transmitting equivariant information such as the hidden representations of multiple nodes or (hyper)edges.
Instead, we observe that any part of an activation that corresponds to nodes shared between two local graphs can be freely copied between the associated neurons. To transmit information from n`−1j to n ` j , we define two operations, narrowing and promotion, that extend this copying procedure to arbitrary activations. Narrowing compresses the output of n`−1j into the intersection of the two local graphs, and promotion expands the result to the local graph of n`j .
To ensure that narrowing and promotion are correctly defined for all activations regardless of their specific group actions, we employ the formalism from [24], where activations are treated as functions on the symmetric group. Specifically, the input activation and narrowed activation on m and k nodes respectively are identified with functions from Sm → R and Sk → R. We discuss special cases after the definitions, and depict a specific example operating on edge features in Figure 3.

heading: 5.2.1 Narrowing
text: Narrowing takes an activation f that transforms under permutation of a given set of m nodes and converts it into a function that transforms only with respect to a subset of k <m nodes, {vi1 , . . . , vik}. To construct our narrowed function, we apply an arbitrary permutation that “picks out” the nodes indexed by {i1, . . . , ik} by sending them to the first k positions. (Note this implicitly orders these nodes.) Subsequent permutations of {1, 2, . . . , k} permute our specially chosen nodes amongst each other and permutations of {k+1, . . . ,m} permute the other, less desirable nodes. Narrowing exploits this to construct a function on Sk: we apply the corresponding group element in Sk to the first k positions, average over all permutations of the last m− k, and read off the result. Definition 1. Let (i1, . . . , ik) be an ordered subset of {1, 2, . . . ,m} and t be an (arbitrarily chosen) permutation such that t(ip) = p ∀p ∈ 1, . . . , k. (9) For all u ∈ Sk let ú ∈ Sm be the permutation that applies u to the first k elements and for all s ∈ Sm−k let s̀ ∈ Sm be the permutation that applies s to the last m − k elements. Given f : Sm → Rd we define the narrowing of f to (i1, . . . , ik) as the function:
f↓(i1...ik)(u) = (m− k)! −1 ∑ s∈Sm−k f(ús̀t). (10)
Narrowing obeys a notion of equivariance for permutations restricted to the local graph. Let σ be a permutation that sends {i1, . . . , ik} to itself. Narrowing then obeys:
(f↓(i1...ik)) σ′ = (fσ)↓(i1...ik),
where σ′ is the permutation in Sk obeying:
σ′(p) = q ⇐⇒ σ(ip) = iq. (11)
and the superscripts denote the transformation of the function under permutation,
fσ(g) = f(σg) ∀g ∈ Sm (Sk). When applied to a collection of node features, narrowing simply saves the features in nodes in i1 . . . ik and the average feature and then discards the rest. More generally, if the activation is a multi-index tensor whose indices correspond to individual nodes, narrowing forms new tensors by averaging over the nodes not in {i1 . . . ik}.

heading: 5.2.2 Promotion
text: Promotion is the opposite of narrowing in that it takes a function g : Sk → Rd and extends it to a function on Sm. We therefore apply the same construction as in Definition 1 in reverse. Definition 2. Let (j1, . . . , jm) be an ordered set of indices with an ordered subset (i1, . . . , ik). Let u, s, t, ú, and s̀ be as in Definition 1. Given a function g : Sk → Rd, we define the promotion of g to Sm as the function:
g↑(j1...jm)(τ) = { g(u) if there exist u∈ Sk, s∈ Sm−k such that τ = ús̀t, 0 otherwise.
(12)
In Section 4 of the supplement we show that any such u and s are unique and consequently our definition is independent of the choice of u and s. Narrowing is the pseudoinverse of promotion in the sense that for any g : Sk → Rd
g↑(j1...jm)↓(i1...ik) = g. In contrast, narrowing followed by promotion is typically a lossy operation that does not preserve a function. Similarly to narrowing, promotion obeys the equivariance property:
(gσ ′ )↑(j1...jm) = (g↑(j1...jm))σ,
where σ and σ′ are defined as in (11). In the case of node features, promotion simply copies the node features into the new local graph. For a multi-index tensors whose indices correspond to individual nodes, promotion zero-pads the tensor, adding indices for the new nodes.

heading: 5.3 Autobahn neurons
text: Stated most generally, an Autobahn neuron n`j operates as follows. Let n ` j be a neuron whose local graph G`j is defined on the nodes {va1 , . . . , vam}. Denote by f `−1s1 , . . . , f `−1 sp the activations of the neurons in the previous layers whose local graphs overlap with G`j . We denote the nodes in the local graph of the z’th overlapping neuron by (vaz1 , . . . , vazmz ) and define the intersections:
{bz1, . . . , bzkz} = {a1, . . . , am} ∩ {a z 1, . . . , a z mz}.
The operation performed by n`j in an Autobahn can then be summarized as follows:
T1. Narrow each incoming activation f `−1sz to the corresponding intersection to get f `−1 sz ↓(bz1 ...bzkz ). T2. Promote each of these to (a1, . . . , am) : f̃sz = f
`−1 sz ↓(bz1 ...bzkz )↑ (a1...am).
Note that each f̃sz is (a1, . . . , am)-permutation equivariant.
T3. Combine the results into a single function f̃ by applying an aggregation function that is invariant to permutations of the set {f̃1, . . . , f̃p} within itself (for instance, averaging). T4. Apply one or more convolutions and nonlinearities over the local graph’s automorphism group as described in Algorithm 1.
Sufficient conditions for the resulting network to obey global permutation equivariance are given below.
Theorem 1. Let n`j be an Autobahn neuron in a neural network operating on a graph G. Let G`j be the local graph of n`j and denote G`j ’s node set as {va1 , . . . , vam} ⊂ {v1, . . . , vn} and its edges as E`j = {ekl}k,l∈{va1 ,...,vam}. If the following three conditions hold then the resulting Autobahn obeys permutation equivariance.

heading: 1. For any permutation σ ∈ Sn applied to G, the resulting new network Φ′ will have a neuron n′`j′
text: with the same parameters that operates on a graph G`j ′ . The nodes of G`j ′ are {vσ(a1), . . . , vσ(am)}
and its edges are { eσ(k)σ(l) | ekl ∈ E`j }. 2. The output of the neuron is invariant with respect to all that permutations of G that leave the
nodes {va1 , . . . , vam} in place. 3. The output of the neuron is equivariant to all permutations of the set {va1 , . . . , vam} within itself.
A proof is given in Section 5 of the supplement.

heading: 5.4 Expressivity of Autobahn
text: To further understand the capabilities of Autobahn we will compare its theoretical expressivity to that of other graph neural networks. First, we analyze Autobahn in the context of the k-Weisfeiler-Lehman (k-WL) algorithm and the k’th order network proposed in [30]. Next, we compare Autobahn to the Graph Substructure Networks (GSN) proposed in [21].
A common tool used to analyze the expressivity of message-passing neural networks is comparison against the k-WL algorithm [42, 43]. Here, information is repeatedly transferred between all possible ordered sets of k nodes and if the output differs between two graphs then they are not isomorphic. It has since been determined that most message-passing neural networks are limited in their expressive power by the 2-WL algorithm, meaning certain graphs are fundamentally indistinguishable by MPNNs [8, 39]. The WL algorithm is also closely related to the k’th order graph neural network from [30], where activations correspond to all possible ordered sets of k nodes and information is transferred between sets using tensor expansions and contractions. This process corresponds to convolutions over all permutations of the graph’s nodes [29]. Here, a k’th order network has the expressive power of the k-WL. However, the size of the activations grows combinatorially as we increase k, making the network infeasible for all but small values of k.
Autobahn, in contrast, constructs activations on specific subgraphs, corresponding to specifically chosen ordered sets of nodes. As depicted in Figure 4, this makes the Autobahn activation sparse in the set of all possible node sets. If these sets are chosen well, the Autobahn network can hopefully leverage the power of higher-order computation without incurring a combinatorial increase in cost. In Subsection 6.1 of the Supplement we formalize this connection by showing that the operations in
Autobahn can be performed "densely" using the k-th order network, and that choosing an Autobahn template that covers all sets of k nodes recovers a k-th order network.
The strategy of using subgraphs to improve the expressiveness of a neural network is shared by the GSN network [21], which augments a message-passing neural network with node features that count the isomorphism classes of subgraphs a particular node is in. Consequently, it is reasonable to ask if using subgraphs for computation (as Autobahn does) gives any advantages compared to merely using them to create initial features. In Subsection 6.2 of the Supplement , we answer this in the affirmative. Moreover, while it was noted that a GSN network would be able to reconstruct a graph from its n−1 subgraphs if the reconstruction conjecture [44, 45] held, it is not clear if this task could be accomplished if the reconstruction conjecture was false. In contrast, we show that the high-order activations and the transfer of information using narrowing and promotion allows Autobahn to reconstruct a graph using neurons operating on its subgraphs of size n−1 independently of the reconstruction conjecture.

heading: 6 Molecular graphs on the Autobahn
text: With the Autobahn formalism defined, we return to our motivating task of learning the properties of molecular graphs. From the structure of organic molecules, we see that they often have a combination of a sparse chain-like “backbone” and cyclic structures such as aromatic rings. The importance of these structures is further justified by the theory of molecular resonance. Whereas in molecular graphs edges correspond to individual pairs of electrons, real electrons cannot be completely localized to single bonds. To re-inject this physics into graph representations of molecules, chemists construct “resonance structures”: alternate molecular graphs formed by concertedly moving the electrons in a molecular graph. Importantly, the rules of chemical valency ensure that these motions occur almost exclusively on paths or cycles within the graph. In fact, cycle and path featurizations have already been used successfully in cheminformatic applications [46].
Motivated by these considerations, we will choose our local graphs to correspond to directed cycles and paths in graph. This has the additional advantage that the one-dimensional convolutions given by (6) are equivariant to the graph’s automorphism group, and can be used directly. To construct the neurons for our architecture, we extract all paths of length three through six in the graph and all cycles of five or six elements. These cycle lengths were chosen because cycles of five and six elements are particularly common in chemical graphs. For each path or cycle, we construct two neurons corresponding to two ways of traversing the graph: for cycles, this corresponds to clockwise or anticlockwise rotation of the cycle, and for paths this sets one of the ends to be the “initial” node.
We then construct initial features for each neuron by embedding atom and bond identities as categorical variables. Embedded atom identities are then directly assigned to the corresponding points in each path or cycle. To assign the embedded bond identities, we arbitrarily assign each bond to the preceding node in the traversals mentioned above. Since we construct a neuron for both traversal directions, this procedure does not break permutation equivariance of the architecture. Following the
initial featurization, we then construct layers using the four step procedure described in Section 5. The layer is illustrated in Figure 5.
Full details of the model, including training hyper-parameters and architecture details, are available in the Supplement; code is freely available at https://github.com/risilab/Autobahn. We present empirical results from an implementation of our architecture on two subsets of the ZINC dataset using the data splits from [23], as well as three standardized tasks from Open Graph Benchmark. All datasets are released under the MIT license. Baselines were taken from [21, 23, 47, 48]. Our automorphism-based neural network achieves results competitive with modern MPNNs.

heading: 7 Conclusion
text: In this paper, we have introduced Automorphism-based Neural Networks (Autobahn), a new framework for constructing neural networks on graphs. To build an Autobahn, we first choose a collection of template graphs. We then break our input graph into a collection of local graphs, each isomorphic to a template. Computation proceeds on each local graph by applying convolutions equivariant to the template’s automorphism group, and by transferring information between the local graphs using two operators we refer to as “narrowing” and “promotion”. MPNNs are specific examples of Autobahn networks constructed by choosing star-shaped templates applied to local neighborhoods. Similarly, applying Autobahn to a grid graph recovers steerable CNNs. Our experimental results show that Autobahn networks can be competitive with modern MPNNs on several molecular learning tasks.
We expect the choice of substructure to critically influence Autobahn performance. In future work we hope to explore the space of new models opened up by our theory. In learning situations where much is known about the graphs’ structure, we believe practitioners will be able to choose templates that correspond to desired inductive biases, giving improved results. For instance, in future work we hope to improve our results on molecular graphs by adding templates that correspond to specific functional groups. For arbitrary graphs, it is not clear that the star graphs used by MPNNs are optimal or just a historical accident. It is possible that other “generic” templates exist that give reasonable results for a wide variety of graphs. For example, [2, 49] used path activations in conjunction with stochastic sampling strategies and the architecture in [50] can be viewed as using tree-like substructures. By further exploring the space of possible templates, we hope to construct richer graph neural networks that more naturally reflect the graphs on which they operate.

heading: 7.1 Broader Impacts
text: In our framework, the choice of template reflects practitioners’ beliefs about which graph substructures are important for determining its properties. For social networks communities from different cultural backgrounds might result in graphs with differing topologies. Consequently, when applying Autobahn to these graphs care must be taken that chosen templates do not implicitly bias our networks towards specific cultural understandings.

heading: 8 Acknowledgements
text: This project was supported by DARPA “Physics of AI” grant number HR0011837139, and used computational resources acquired through NSF MRI 1828629. The Flatiron Institute is a division of the Simons Foundation. We thank Sonya Hanson, John Herr, Joe Paggi, and Helen Yu for useful feedback.

Review summaries:
This paper introduces Automorphism-based Graph Neural Networks (Autobahns), which decompose the graph into a collection of subgraphs and apply convolutions that are equivariant to each subgraph’s automorphism group. The specific architecture is determined by the choices of local neighborhoods and subgraphs. The proposed formalism not only generalizes the message passing GNNs but also encompasses novel architectures. Experiments are conducted on molecular graph datasets and demonstrate that Autobahns can achieve state-of-the-art results.

This paper proposed Autobahn, a new GNN model for learning representations of graphs for graph classification tasks. The idea is to extract subgraphs that are isomorphic to predefined graph templates (e.g., cycles, paths) and perform a convolution operation on its automorphism group. This paper proposed two operations to perform interaction between the representations on different subgraphs: narrowing and promoting. This paper applied the proposed model to graph classification tasks on a molecular graph dataset and verified its effectiveness.

This paper proposes Automorphism-based GNNs (Autobahns), a framework that generalises GNNs from operating in star-like neighbourhoods to arbitrary local subgraphs.  In particular, the authors use group-theoretic tools to define linear operators on arbitrary graphs and show that their parameters are constrained by the automorphism group of the graph. However, as also discussed in Natural Graph Networks (de Haan et al., NeurIPS’20), defining a different operator for each graph would make learning impossible since there would be virtually no weight-sharing across training data (generalisation to unseen graphs would be also impossible). To this end, the authors deal with a set of predefined small-sized template graphs on which they define their learnable operators. Then each graph is processed as follows: first, it is decomposed into a collection of overlapping templates. Then, (1) the components (e.g., nodes and edge features) of each matched subgraph are transformed by the operator of the corresponding template and (2) overlapping subgraphs “exchange messages” via the narrowing and promotion operations, as defined by the authors.  Steps (1) and (2) are repeated for each layer. The proposed framework is instantiated with cycle and path templates and evaluated on molecular datasets achieving competitive results.