Autobahn: Automorphism-based Graph Neural Nets
Authors: Erik Henning Thiede
Wenda Zhou
Risi Kondor
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Networks
Group Equivariance

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.

Autobahn: Automorphism-based Graph Neural Nets
Erik H. Thiede," Wenda Zhou, 12f Risi Kondor
Center for Computational Mathematics, Flatiron Institute, New York NY 10010
Center for Data Science, New York University, New York NY 10011
Department of Computer Science, University of Chicago, Chicago IL 60637
Department of Statistics, University of Chicago, Chicago IL 60637
"ehthiede @ flatironinstituee.rr.. ww22247 @ nyu,edu, 'risi @ uchicago.edu
Abstract
We introduce Automorphism-basee graph neural networks (Autobahn), 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 permuta- tion equivariance. We validate our approach by applying Autobahn to molecular graphs, where achieves results competitive with state-of-the-arr message passing algorithms.
Introduction
The successes of artificial neural networks 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 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 11 5]. Arguably, the most popular approach is to construct Message-Passing Neural Networks (MPNNs)66. 7]. In each layer of an MPNN, every node aggregates the activations of its neigh- bors in a permutation invariant manner and applies linear mixing and nonlincarity 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 '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. 1 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 's structure.
In this work, we introduce new framework for constructing graph neural networks, Automorphism- based Neural Networks (Autobahn). Our research is motivated by our goal of designing neural
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

=+=+= +E+
Figure 1: Visualization of a single neuron of a simple message passing neural network. Each node aggregates the features from neighboring nodes using permutation-invarian operation (we use summation for simplicity), applies learned weight matrices and biases and finally nonlinearity.
networks that can learn the properties of small organic molecules accurately enough to make 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 common subunit in larger molecules. On this ring we have very natural and mathematically rigorous notion of convolution: convolution on a one-dimensional, periodic domain. This symmetry is encoded by graph's automorphism group: the group that reflects our substructures' internal symmetries. Our networks directly leverage the automorphism group of subgraphs 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 we present novel architecture outside of the message-passing paradigm that nevertheless achieves performance competitive with state-of-the of- MPNNs on molecular learning tasks.
Graph Neural Networks
Neural Networks operate by composing several learned mappings known as "layers". Denoting the f'th layer in the network as te, the functional form of a neural network can be written as
Φr o 0r.1 ....
Each layer is typically constructed from collection of parts, the titular "neurons". We denote the i'th neuron in the f'th layer as nf, and denote its output (the "activation" of the neuron) as f/- Architectures differ primarily in how the neurons are constructed and how their inputs and outputs are combined.
When constructing neural network that operates on graph data, care must be taken to preserve the input graphs' natural symmetries under permutation. Let & be a graph with node set {01.... Vn). adjacency matrix A E R"x" and d-dimensional node labels b, E Rd stacked into matrix B E R nxd Permuting the numbering of the nodes of G by some permutation a (1,2...., + (1,2...... n transforms
+ A
A = A, Ao- A0-+((),0--0)
and
B + B"
B B (0),
This transformation does not change the actual topology of G. Consequently, fundamental require- ment on graph neural networks is that they be invariant with respect such permutations.
2.1
Message-Passing Neural Networks
Message- passsegganinggggg neural networks (MPNNs) have emerged as the dominant paradigm for constructing neural networks on graphs. Every neuron in an MPNN corresponds to 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 transmitted over the graph's '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, 191, may include additional terms to
account for edge features [8. 9], may use complex transformations construct the node features encoding local structure [20, 21]. or may augment the graph with additional nodes [22, 23).
3 Permutation Equivariance
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 's output unaffected is formalized by the notion of group-invariance. Let us assume that our input data lives in space X that is acted on by group G, and for all E G denote the associated group action on X by g.. The invariance constraint amounts to requiring:
T = Φ Tg
Vg E G.
One way to satisfy this would be require that each layer de 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 the input and output spaces of te. with group actions Tg and T respectively. We say de is equivariant to G if it obeys
g²
T- = Φ: T
Vg E G.
(4)
This condition weaker than invariance: we recover invariance when T maps every element 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: S, (called the symmetric group of degree ni).
3.1 cermmutation-equvvriiaa networks
Recent work has developed generic recipe for constructing group equivariant networks. In this formalism, any object that transforms under group action is treated function on the group [24] (see Section 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) Σ f(vv w(v).
(5)
VEG
To construct an equivariant neuron, we apply (5) convolve our input activation fe-1 with learned weight function w, add a bias, and then apply a fixed equivariant nonlinearity, v. Applying this approach 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)2 Σ 5(1 w(r*),
where is the group element corresponding 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 layer whose domain and range transform according to (2) with c.n incoming and Cout outgoing channels. Let W W2 E geous X be learned weight matrices, and fj Reto be the vector of incoming activations corresponding node j. The most general possible convolution is then [28]
(f * w) wifi + W2
f
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.
3

---

Algorithm 1 Automorphism-basee Neuron
Input:
fe-1
Incoming activation associated with G > Adjacency matrix of G Adjacency matrix of the saved template graph.
Ag
AT
1: Find Sn such that A = AT.
2: (ft-13" + Tu(f(-1)
> Apply μ incoming activation. Convolution is over Aut (T).
3: (ft)" +- ((ft-)) 6)
4: I + TT -())))))))
> Map output original ordering
Return:
To address this fundamental limitation, several recent works considered improving the expressivity of MPNNs by defining higher order activations corresponding pairs, triplets. 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 k' th order tensors, A Ai,,... A (4 (())) 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.
4 Permutation-Equivarinn Neurons using Automorphism
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:
Agt {a E,, 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 node or edge in 9 up to a permutation in Aut(G). If every graph our network observed was in the same isomorphism class, by matching G to a template graph T and convolving over Aut (T). We give pscudocode for such neuron, which we call an "Automorphism-basee neuron," in Algorithm 1. Note that although the convolution itself is only equivariant to Aut(T), the entire neuron is formal proof of equivariance is given in Section of the Supplement.
could construct neuron in
neural network
A
For given input and output space, neurons constructed using Algorithm 1 are more flexible than neuron constructed using only S., 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 S,,-oonvolution 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 completely canonicalizes the graph since this particular graph has non- non-trivial automorphisms, Consequently, we do not need to worry about enforcing symmetry and we can simply run fully connected layer: 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 cyclic permutation, so convolution must be equivariant to the graph's 's automorphism group, Co-
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 not directly practical. Most graph learning problems consist either of many graphs from different isomorphism classes graph that is only partially known. the former case, we would have to construct one network for every isomorphism class and each network would only fraction of the data. In the latter, the isomorphism class the network would be unknown.
single large
Autobahn
To motivate our approach we consider MPNNs from the perspective of Algorithm Looking at Figure 1 we see that the message-passing procedure itself forms star graph, where the leaves of

---

So
fd+1
190
Sq x S2
Do
(b)
Figure 2: Figures visualizing the automorphism group of graph and its use in graph learning. (a) Four graphs and their automorphism groups. In each graph, nodes in the same orbit of the graph's automorphism group are the same color. (b) A neuron constructed by applying Algorithm to cyclic directed graph. We consider the simplified setting where the layer operates only on a single channel of node features. Note that the matching step can only be accomplished to an element in the graph's s automorphism group: the cyclic group of order six, C6.
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 precisely the group structure of a single MPNN neuron. Since apply permutation invariann aggregation funetion, if we were to permute neuron's '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 graph into a collection of subgraphs known as local graphs that are isomorphic to a pre-selected template graph. Although 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 permutation-equivarie denoting the local graph of neuron n. as G.P Each neuron operates by aggregating information from overlapping local graphs and then applying Algorithm to the result. Because of the important role played by convolutions
neuron on each local graph,
subgraphs' automorphism groups, refer to the resulting networks as Automorphism-Bee 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 grid graph template on a larger grid graph recovers steerable CNNs [26]*. 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 considerable body of literature on constructing neural networks with higher- order 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 [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. our knowledge, this 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 generic treatment of each step in the network, followed by full description of 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 flexible recipe that practitioners can tailor their specific problems using their domain knowledge.
'Standard CNNs further break the symmetry left/right. However, if we introduce 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.
grid graph by introducing notion of up/down and
5

---

5.1 Convolutions using the Automorphism Group
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 eycle and path graphs as templates. There, group convolutions can be performed using well-known one-dimensional convolutions such as (6).
5.2 Transferring information across neurons
To build rich representation of the structure graph 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, the output of neuron n becomes node feature for neuron n ++ However, this strategy does not necessarily work for the neurons in Autobahn: our local graphs may not have central node. Even if they do, collapsing each neuron's 's output into single node could limit our network's ss expressivity, as it prevents neurons from transmitting equivariant information such 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 nj f-1 to nf.
we define two operations, narrowing and promotion, that extend this copying procedure to arbitrary activations. Narrowing compresses the output of n é-1 into the intersection of the two local graphs, and promotion expands the result to the local graph of n².
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 functions on the symmetric group. Specifically, the input activation and narrowed activation on m and k nodes respectively are identified with functions from S,n + and S + RR. We discuss special cases after the definitions, and depict specific example operating on edge features in Figure 3.
5.2.1 Narrowing
Narrowing takes activation ff that transforms under permutation of given set of m nodes and converts it into function that transforms only with respect to a subset of k < m nodes, ........, To construct our narrowed function, we apply an arbitrary permutation that "picks out" the nodes indexed by (i1,...,ia } by sending them to the first k positions. (Note this implicitly orders these nodes.) Subsequent permutations of .1,2.....k k} permute our specially chosen nodes amongst each other and permutations of {k+ 1, .....,,) permute the other, less desirable nodes. Narrowing exploits this construct function on Sy: we apply the corresponding group element in S₃ the first positions, average over all permutations of the last m k, and read off the result.
V;
Definition 1. Let (f1,...,ái, permutation such that
ix) be an ordered subset of (1,2,.... m) and be an (arbitrarily chosen) lp
t(1,) =p
For all u E Sx let E Sm be the permutation that applies u to the first elements and for all E Sm-k let i E Sm be the permutation that applies to the last m k elements. Given fi Sm + Rd we define the narrowing of f to (iI...., ix) as the function:
(m k)!
Σ f(úst).
(10)
Narrowing obeys notion of equivariance for permutations restricted to the local graph. Let a be permutation that sends (i1,..., ( to itself. Narrowing then obeys:
((hen))))) =I Metennde))
where a' is the permutation in Sy obeying:
o'(p) (p) =
o(ip) ig.
(1I)

---

44.44)
f! ( (0,4666
Figure 3: Example demonstrating how narrowing and promotion transfer information between local graphs. For concreteness, we assume the incoming activation fe a collection of edge features. We first narrow to the nodes shared between 9 and Gj For the edge features used here, this corresponds to averaging over nodes 3 and 7; the edge inside the restriction is simply copied. The results then placed into the appropriate position in the local graph of the output.
and the superscripts denote the transformation of the function under permutation,
(g) f(ag) Vg Sm (Sk).
When applied to collection of node features, narrowing simply saves the features in nodes in i 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 {ir ....
5.2.2 Promotion
Promotion is the opposite of narrowing in that takes function g: Sg - RRd and extends to function on Sm. We therefore apply the same construction in Definition 1 in reverse. Definition 2. Let (Ji...., Im) be an ordered set of indices with an ordered subset (i1,...,hu ix). Let u, 9, ú, and be as in Definition Given a function g: Sk. Rd, we define the promotion of g to S. as the function:
g& (m (T) g(u) if there exist u E Sg, 8 Sm such that Lbs, otherwise.
(12)
In Section 4 of the supplement we show that any such u and are unique and consequently our definition is independent of the choice of and s. Narrowing is the pseudoinverse of promotion in the sense that for any g: St Rdd
gf (1 (2)..)))) g-
In contrast, narrowing followed by promotion is typically lossy operation that does preserve function. Similarly to narrowing, promotion obeys the equivariance property:
(g ((in (1))))))))
where and o' defined (11). In the case of node features, promotion simply copies the node features into the new local graph. For multi-index tensors whose indices correspond to individual nodes, promotion zero-pads the tensor, adding indices for the new nodes.
5.3 Autobahn neurons
Stated most generally, an Autobahn neuron n² operates as follows. Let nł be neuron whose local graph O is defined on the nodes {Na...... Ne... Denote by fć-1 ..... #t-1 -.. the activations of the neurons the previous layers whose local graphs overlap with G We denote the nodes in the local graph of the 2 'th overlapping neuron by (Vaj ...,, Vag m..
and define the intersections:
(bi.... ......,bg by. = fa...... am fai..... .
The operation performed by nz in an Autobahn can then be summarized as follows:
T1. Narrow each incoming activation fe-1 to the corresponding intersection get f f (bF
T2. Promote each of these to (a1,.... a00)
f., = ft- 1 bg. aa)
Note that each fo, is (a am
) perrmutation equivariant.

---

4-VL
2023
27.33
3832
33.32
6123
7123
6312
6332
6554
6333
6425
Figure 4: Visual comparison of the activations in Autobahn with the data structures used in the k-WL algorithm and in a k'th order graph neural network. Whereas the k-WL and k'th order GNN operate over all possible ordered sequences of k nodes (here = 4), Autobahn specifically targets sequences believed be important by identifying them through the isomorphism class of the corresponding subgraph. Here, one subgraph is isomorphic to the blue template and two are isomorphic to the green. Sequences corresponding their automorphism groups are highlighted in the corresponding color. Using subsets of sequences corresponding to specific substructures allows Autobahn to perform higher-order computation without the combinatorial explosion in cost.
T3. Combine the results into single function f by applying an aggregation function that is invariant to permutations of the set (Ji.... fp} within itself (for instance, averaging). T4. Apply one or more convolutions and nonlincarities over the local graph's 's automorphism group as described in Algorithm 1.
Sufficient conditions for the resulting network obey global permutation equivariance given below.
Theorem 1.
Let nt be an Autobahn neuron in a neural network operating on a graph G. Let Gf be the local graph of and denote G 's node set (Vay...., Vam } C (V1....,2,, and its edges as Ej = (exs) (eRK)h, (, (E "v............."""" If the following three conditions hold then the resulting Autobahn obeys permutation equivariance.
1. For any permutation a S, applied to G. the resulting new network 4' will have a neuron n² with the same parameters that operates on graph 9. The nodes of 93," are (Volar)..... Valam)) and its edges are { (a(lia(()) Cka E E }.
2. The output of the neuron is invariant with respect to all that permutations of 9 that leave the nodes (Uars...y Vam.) } in place.
3. The oulpul of the neuron is equivariant to all permutations of the set {Vays..., Va... within itself.
A proof is given in Section 5 of the supplement.
5.4 Expressivity of Autobahn
To further understand the capabilities of Autobahn we will compare its theoretical expressivity to that of other graph neural networks. First, analyze Autobahn in the context of the l- Leeiseeellr--ehmman (k-WL) algorithm and the k thth order network proposed in [30]. Next, we compare Autobahn to the Graph Substructure Networks (GSN) proposed in [21].
common tool used to analyze the expressivity of pessage-passing neural networks comparison against the &-WL algorithm [42, 43]. Here, information is repeatedly transferred between all possible ordered sets of & nodes and if the output differs between two graphs then they are not isomorphic, has since been determined that most message-passie
neural networks are limited in their expressive power by the 2- 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 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 &-WL. However, the size of the activations grows combinatorially as increase k making the network infeasible for all but small values k.
Autobahn, in contrast, constructs activations on specific subgraphs, corresponding to specifically chosen ordered sets of nodes. As depicted 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
8

---

Path Cycle Conv
ReLU
Path / Cycle Conv
ReLU
Figure 5: The internal structure of single layer in the Autobahn architecture. We extract all path and cycle subgraphs of fixed length and their corresponding activations. (For compactness and readability, only some activations are shown.) We then apply series of convolutional layers. A block diagram for this step is given on the right; each isomorphism class of reference domains has its own weights. Finally, we construct the activations for the next layer by narrowing and promoting between subgraphs and summing over the resulting promoted activations.
Autobahn can be performed "densely" using the k-th order network, and that choosing an Autobahn template that covers all sets of l nodes recovers k-th order network.
The strategy of using subgraphs improve the expressiveness of neural network is shared by the GSN network [21], which augments a message- 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 GSN network would be able to reconstruct graph from its n subgraphs if the reconstruction conjecture [44, 45] held, 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 graph using neurons operating on its subgraphs of size n 1 independently of the reconstruction conjecture.
Molecular graphs on the Autobahn
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 sparse chain-like "backbone" and cyclic structures such as aromatic rings. The importance of these structures further justified by the theory of molecular resonance. Whereas in molecular graphs edges correspond 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 molecular graph. Importantly, the rules of chemical valency ensure that these motions occur almost exclusively 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 '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 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 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 categor- ical 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

---

Model
ZINC 10k
ZINC full (MAE, 4)
MolPCBA (AP f)
MolHIV
MUV
(MAE, 4)
(ROCAUC T)
(AP
GCN
0.367 + 0.011
N/A
0.222 + 0.002
0.788
N/A
GSN
0.108 + 0.018
N/A
N/A
0.780 0.010
N/A
DGN
0.169 1 0.003
N/A
N/A
0.797 + 0.010
N/A
GINE-E
0.252 1 0.015
0.088 + 0.002
0.227 + 0.003
0.788 1 0.080
0.091
HIMP
0.151 + 0.006
0.032 + 0.002
0.274 + 0.003
0.788 + 0.080
0.114 - 0.041
Ours
0.106 + 0.004
0.029 - 0.001
0.270
0.780 = 0.003
0.119 - 0.005
Table I: Performance of our Autobahn architecture on two splits of the ZINC dataset and three
datasets in the OGB benchmark family, compared with other recent message passing architectures.
ZINC experiments use MAE (lower is better); for all other metrics higher is better. Baselines were taken from [23, 47, 48] and [21].
initial featurization, we then construct layers using the four step procedure described in Section 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: : / ////tttttub..//. com com/risillan lab/ laallaaabbbaaaa AAtooban.. 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 automorphismm-aat based neural network achieves results competitive with modern MPNNs
7 Conclusion
In this paper, we have introduced Automorphism-basee Neural Networks (Autobahn), a new frame- work for constructing neural networks on graphs. To build an Autobahn, we first choose collection of template graphs. We then break our input graph into a collection of local graphs, each isomorphic template. Computation proceeds on each local graph by applying convolutions equivariant the template's '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 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 known about the graphs" structure, believe practitioners will be able choose templates that correspond to desired inductive biases, giving improved results. For instance, in future work we hope 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 historical accident. It possible that other "generic" templates exist that give reasonable results for wide variety of graphs. For example, [2, 49] used path activations in conjunction with stochastic sampling strategies and the architecture [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.
7.1 Broader Impacts
In our framework, the choice of template reflects practitioners' belief's about which graph substructures 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.
8 Acknowledgements
This project was supported by DARPA "Physics of AI" grant number HR001 and used computational resources acquired through NSF MRI 1828629. The Flatiron Institute is division of the Simons Foundation. We thank Sonya Hanson, John Herr, Joe Paggi, and Helen Yu for useful feedback.
10

---

References
[1] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
[2] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 701-710, 2014.
[3] M. Henaff, J. Bruna, and Y. LeCun. Deep convolutional networks on graph-structured data. arXiv preprini arXiv:/50..05/60 06 2015.
[4] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering Advances in Neural Information Processing Systems (NeurIPS), 2016.
[5] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
[6] T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks In International Conference on Learning Representations (ICLR), 2017.
[7] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. Proceedings of International Conference on Machine Learning (ICML), 2017.
[8] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2019.
[9] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference Learning Representations (ICLR), 2020.
[10] Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. DeepGCNs: Can GCNs go as deep as CNNs? In JEEE/CVF International Conference on Computer Vision, ICCV, 2019.
[11] Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler- Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 1 113:42-59, 2020.
[12) Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems (NeurIPS), 2020.
[13] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In icml, pages 3419-3430. PMLR, 2020.
[14] Alexandru Korotcov, Valery Tkachenko, Daniel P Russo, and Sean Ekins. Comparison of deep learning with multiple machine learning methods and metrics using diverse drug discovery data sets. Molecular Pharmaceutics, 14(12):4462 4475, 2017.
[15] Frederic E Bock, Roland C Aydin, Christian J Cyron, Norbert Huber, Surya R Kalidindi, and Benjamin Klusemann. A review of the application of machine learning and data mining approaches in continuum materials mechanics. Frontiers in Materials, 6:1 10, 2019.
[16] Mojtaba Haghighatlari and Johannes Hachmann. Advances of machine learning in molecular modeling and simulation. Current Opinion in Chemical Engineering. 23:51-57, 2019.
[17] Robert Pollice, Gabriel dos Passos Gomes, Matteo Aldeghi, Riley Hickman, Mario Krenn, Cyrille Lavigne, Michael Lindner-D' Addario, AkshatKumar Nigam, Cher Tian Ser, Zhenpeng Yao, et al. Data-driven strategies for accelerated materials design. Accounts of Chemical Research, 54(4))849-860, 2021.
11

---

[18] David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Ipann Iparraguirre, Rafael Timothy Hirzel, Alan Aspuru- and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
[19] William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), pages 1025-1035, 2017.
[20] Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik. Subgraph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
[21] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.099 09252,, 2020.
[22] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of International Conference Machine Learning (ICML), 2018.
[23] Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. In Graph Representation Learning and Beyond (GRL+) Workshop at ICML 2020, 2020.
[24] Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In Proceedings of International Conference on Machine Learning (ICML), 2018.
[25] Taco S. Cohen and Max Welling, Group equivariant convolutional networks. In Proceedings of International Conference on Machine Learning (ICML), 2016.
[26] Taco S. Cohen and Max Welling. Steerable CNNs. In International Conference on Learning Representations (ICLR), 2017.
[27] Taco S. Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant CNNs on homogeneous spaces. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[28) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Póczos, Russ R Salakhutdinov. and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[29] Erik H. Thiede, Truong Son Hy, and Risi Kondor. The general theory of permutation equivariant neural networks and higher order graph variational encoders. arXiv preprint arXiv:2004.03990. 2020.
[30] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations (ICLR), 2018.
[31] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. Proceedings of International Conference on Machine Learning (ICML), 2019.
[32] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[33] Truong Son Hy, Shubhendu Trivedi, Horace Pan, Brandon M. Anderson, and Risi Kondor. Predicting molecular properties with covariant compositional networks. The Journal of Chemical Physics, 148(24):241745, 2018.
[34] Pim de Haan, Taco S. Cohen, and Max Welling. Natural graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[35] Luigi Pietro Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. An improved algo- rithm for matching large graphs. In 3rd IAPR-TCI5 Workshop on Graph-bused Representations in Pattern Recognition. Citeseer, 2001.
12

---

[36] Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10):1367-1372, 2004.
[37] Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2007.
[38] Wook-Shin Han, Jinsoo Lee, and Jeong-Hoor Hoon Lee. Turboiso: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In Proceedings of the 2013 ACM SIGMOD International Conference Management of Data, 2013.
[39] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
[40] Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing arXiv preprint arXiv:2006.1511 15107, 2020.
[41] Mare Finzi, Max Welling, and Andrew Gordon Wilson. A practical method for constructing equivariant multilayer perceptrons for arbitrary matrix groups arXiv preprint arXiv:2104.0945: 099499, 2021.
[42] Jin-Yi Cai, Martin Fürer,, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4))389-410, 1992.
[43] Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv preprint wwX1::2007.22055. 2020.
[44] Paul Kelly. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1)9611-968 1957.
[45] Stanislaw M Ulam. A collection of mathematical problems. Interscience Publishers, 1960.
[46] Steven L Dixon, Alexander M Smondyrev, Eric H Knoll, Shashidhar N Rao, David E Shaw, and Richard A Friesner. PHASE: a new engine for pharmacophore perception, 3D QSAR model development, and 3D datahase screening: 1. Methodology and preliminary results. Journal of Computer-Aided Molecular Design, 20 (6)6667777,, 2006.
[47] Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. arXiv preprint arXiv:2011. 2020.
[48] Dominique Beaini, Saro Passaro, Vincent Létourneau, William L Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In ICLR 2021 Workshop Geometrical and Topological Representation Learning. 2021.
[49] Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Graph learning with 1D convolutions random walks. arXiv preprint (oXix:2102.08777 2021.
[50] Daniel Flam-Shepherd, Tony Wu, Pascal Friederich, and Alan Aspuru- Guzik. Neural message passing on high order paths. Machine Learning: Science and Technology, 2021.
13


Reviews:
[{"review_id": "kzeO_htSj1F", "reviewer": "Reviewer_jtWY", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper falls under the category of structure-aware GNNs. In particular, ever since the first impossibility results were proposed for traditional message passing, most notably the fact that its expressivity is upper bounded by the 1-Weisfeiler Leman test and that it cannot count the vast majority of substructures, several extensions have been proposed in order to increase the expressivity of GNNs by providing them with richer structural information (see below for details). This paper takes a similar approach making use of the group-theoretic perspective of convolutions as formalised in Cohen and Welling, “Group Equivariant Convolutional Networks”, ICML’16 and Kondor and Trivedi, “On the generalization of equivariance and convolution in neural networks to the action of compact groups”, ICML’18. \n\n**On the positive side**:\n\n-\tThe proposed framework is general enough and (although not proven by the authors) clearly more expressive than conventional message passing. \n-\tMoreover, group theoretic formulations are elegant and provide a principled way to define neural operators in the presence of symmetries. Section 4 is quite intuitive and provides insights in how to define expressive linear operators over simple structures that are governed by symmetries.\n-\tThe accompanying illustrations (Figure 2, 3, 4) improve the readability and the accessibility of this work to a larger audience.\n-\tThe cycle/path-Autobahn instantiation seems to work relatively well in real-world molecular data.\n\nHowever, I have some reservations because (1) the proposed method has certain drawbacks that may limit its applicability and (2) some of the ideas in this paper are not entirely new and unfortunately the authors have not adequately discussed the connections of their work with the relevant literature. I believe it would be beneficial (and perhaps necessary) to draw these connections at a conceptual level and provide some theoretical evidence to support the merits of the approach. In particular:\n\n **Applicability concerns**:\n\n1.  The method cannot be seamlessly extended to arbitrary graph templates, since one needs to derive a new automorphism-equivariant operator every time a new template is added,\n2.  it can become computationally cumbersome during training (for subgraphs of up to k nodes one may encounter ${n \\choose k}$ subgraphs, where $n$ the number of nodes).\n3.  It requires selecting the subgraphs by domain knowledge.\n\n**Related Work**:\n \n1. Most notably the paper by de Haan et al., “Natural Graph Networks”, NeurIPS'20 proposed quite similar ideas with Autobahn with small differences (e.g., in NGN the authors take into account all edge-wise isomorphism classes, which makes it quite hard to generalise, and computation is performed at node/edge level, while here it is performed at a subgraph level). I think the authors should dedicate a few sentences to clearly compare with this paper.  \n2. Additionally, in some papers, subgraph information is incorporated in the message passing in the form of subgraph counts (e.g., GSNs: Bouritsas et al., “Improving graph neural network expressivity via subgraph isomorphism counting”, arxiv’20). The authors refer to this method in L78, but in my opinion, the comparison is insufficient and potentially interesting connections remain unidentified. GSNs also share the same limitation w.r.t. the selection of the template subgraphs, but they are more computationally efficient (the same computational burden is encountered for the pre-processing in both methods, but during training, GSN is $O(m)$, where $m$ the number of edges), it is easier to implement and can be seamlessly extended to arbitrary subgraphs. I suspect that Autobahns can be proven to be more expressive than GSNs, since each node does not only possess the information of the number of subgraphs it belongs to, but also its position in each subgraph. This brings me to my next concern. \n\n**Theoretical evidence** :\n\nIn my opinion, the paper would benefit a lot from a theoretical analysis w.r.t. the expressive power of Autobahns. Currently, the method is reasonable at an intuitive level, but I suspect that strong expressivity results can be obtained (which would outweigh the above drawbacks), and thus I would encourage the authors to look into this direction.\n\n**Experiments**:\n1.  More baselines should be added (see the leaderboards for ZINC and ogb),\n2. The methods should be sorted according to their performance, \n3. In ZINC, what is the number of parameters (according to the protocol the number of parameters should be ~100K or ~500K)? \n4. Perhaps it would be better to relax a bit the SOTA claims (Autobahn is on SOTA ZINC – on par with GSN, but not in the other datasets). Just to clarify, this is not an issue (at least for me), but right now the claim is misleading.\n\n**Additional comments**:\n\n-\tSection 5 is hard to follow and the method seems to be quite involved, although I am not sure if this is actually the case, especially for the template graphs the authors use in practice. In particular, \n   - Eq. (9) should have been explained more thoroughly and the notation is a bit confusing. Currently, it is not very intuitive. Should the index of the summation in the second term have been $k$? Maybe also $f_{\\sigma(k)}$ --> $f_{\\sigma^{-1}(k)}$.\n  -  A practical example (e.g., for a cycle graph) would help. \n  - The notation and the explanations of the narrowing and promotion operations are, at least to me, very hard to follow. \n  - L229: the notation is confusing\n-\tIf I understand correctly from Algorithm 1, this approach requires matching the nodes of the subgraph to the template, which is NP-complete, unless the size of the template is constant. I can see that the authors mention that in a footnote in P5 and thus it might go unnoticed. I think it should be clearly stated along with the worst-case training complexity.\n-\tWhat happens if a node does not belong in any of the subgraphs?\n-\tI am confused with the claim of L116, but maybe I misunderstood. In case one deals with a single graph, using the general group convolution of Eq. (5) one should obtain different weights per vertex (as in the global version of natural graph networks and in section 4 of this paper). Is that correct?\n\n\n**Justification of rating**: To summarise, I like the approach, I find it elegant and it provides a generic recipe for convolutions in arbitrary graphical structures. However, the limitations and drawbacks of the approach should be clearly stated, along with a more elaborate comparison of the related work. Moreover, in my opinion, given that the experiments do not show a clear advantage of the approach, I think that theoretical evidence will improve the impact of the paper a lot. At this stage, I am not sure if the paper is ready for publication. Hence, I will choose a baseline rating that I am happy to change after the discussion with the authors.\n\n\n------\n## After rebuttal\n\nThe authors did provide theoretical evidence that supports and explains their approach, hence I have increased my score and I will recommend acceptance. I still have some reservations given that this evidence is a major modification to the paper and because of the fact that the method still suffers from some limitations w.r.t. its applicability. Please see my comment below for more information\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "*Limitations*: The authors do mention the limitation of the template graph selection and make a brief reference on the subgraph isomorphism problem they have to solve. As I mentioned in my main review, the latter, together with the training complexity, should be more clearly stated.\n\n*Negative social impacts*: Addressed in Sec. 7.1.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "_pMwBKuFADF", "reviewer": "Reviewer_NsaB", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Soundness (Do theorems and experiments answer research questions, assuming they are correct?)\n\n- [S1] The research question of this paper is to construct GNNs that exploit the topological information of graphs and to use it to learn effective representations of molecular graphs.\n- [S2] From a theoretical point of view, Autobahn is an answer to the research question. It is a model that explicitly utilizes structural information in its construction.\n- [S3] On the other hand, although Autobahn is an extension of MPNN, if my understanding is correct, there is no theoretical support for whether Autobahn learns molecular graph representations better than MPNN. For example, it is not known that Autobahn is strictly more expressive than MPNN.\n- [S4] Regarding empirical evaluation, the ZINC dataset and the Open Graph Benchmark are typical benchmarks for molecular graph tasks. Therefore, I think the experiments are good evidence that Autobahn empirically extracts molecular graph representations.\n\n### Correctness (Are derivation of theorems and experiments correct?)\n\n- [C1] As far as I checked, I did not find significant mistakes in the proofs or experimental setup. However, I have several questions regarding the mathematical description of the proposed model. Here are some examples.\n- [C2] In Figure 2, the method matches the input graph to the template graph $T$ using $\\mu=(1, 3)$. However, I think the choice of $\\mu$ is not unique. In the case of Figure 2, we can also use $\\mu=(2, 1, 6, 3, 4, 5)$ (or its inverse?) to match the graphs.\n- [C3] l.168: It is not clear to me how we define the local graph $\\mathcal{G}^\\ell_j$ for the node $j$. At first sight, I thought that the local graph for the ndoe j is a subgraph containing the node j such that it is isomorphic to some template graph. However, I am not sure how we should define $\\mathcal{G}^\\ell_j$ when we find two subgraphs that match the template(s).\n- [C4] I understood that Algorithm 1 is the aggregation of an MPNN when the template graph is a star graph (Section 5.1). However, Autobahn has narrowing and promotion operations, too. Therefore, it is unclear whether Autobahn includes MPNN as a special case (the same is true for Steerable CNNs).\n\n### Novelty and Significance (Do the paper have novel points? If so, are they significant?)\n\n- [N1] The idea of utilizing subgraph information into graph representation learning appeared in several existing studies such as Graph Homomorphism Network (GHN) [Nguyen and Maehara, ICML2020], Graph Substructure Networks (GSN) [Bouritsas et al. al., arXiv], and Structural Message Passing (SMP) [Vignac et al., NeurIPS2020]. In particular, GSN and SMP are similar to this paper in that they are extensions of MPNN. \n- [N2] However, I think this paper has novel points compared with these models. Specifically, existing models incorporated subgraph information explicitly (GHN, GSN) or implicitly (SMP) for creating input features (i.e., feature extraction stage). On the other hand, this paper tried to incorporate subgraph structure into convolutional operations.\n- [N3] If I understand correctly, Autobahn performed an equivariant message passing on two isomorphic local subgraphs in an input graph. Natural Graph Neural Network also employed the idea of equivariant message passing [de Haan et al., NeurIPS2020]. I would like the authors to clarify and discuss the relationship between Autobahn and Natural Graph Neural Network.\n- [Nguyen & Maehara, ICML2020] http://proceedings.mlr.press/v119/nguyen20c.html\n- [Vignac et al., NeurIPS2020] https://proceedings.neurips.cc//paper_files/paper/2020/hash/a32d7eeaae19821fd9ce317f3ce952a7-Abstract.html\n- [Bouritsas et al., arXiv] https://arxiv.org/abs/2006.09252\n- [de Haan et al., NeurIPS2020] https://proceedings.neurips.cc//paper/2020/hash/2517756c5a9be6ac007fe9bb7fb92611-Abstract.html\n\n### Clarity (Is the paper clearly written?)\n\n- [C1] The organization of the paper is OK. The structure of this paper is in line with the reader's understanding, starting with a simple case (Section 4) and then explaining the general case (Section 5).\n- [C2] However, it took me much effort to figure out what the description of the proposed model mathematically means. In addition, there were many cases in which I could not understand the text just by reading it once.\n- [C3] In addition, I could grasp the intention of some part of the text after completing reading the whole paper and understanding the architecture of Autobahn (e.g., l.41).\n\n### Other comments\n\n- l.87: One way to accomplish this would to be ... → would be ...\n- l.90: $\\phi_l$ → $\\phi_{\\ell}$\n- l.107, Eq. (6): If I understand correctly, Eq. (6) seems to be a bit of an abuse of notation. Specifically, in the left-hand side, $(f\\ast w)_j$ is the value at the point $j$ in the underlying space. However, in the right-hand side, $f$ and $w$ are interpreted as functions on the group which acts on the underlying space.\n- l. 187, Eq. (9): There seems some typos. First, $w_\\sigma(1)$ in the first term on the right-hand side has only one subscript, while $w_{jk}$ in the second terms has two subscripts. Also, I think $\\sum_j$ is supposed to be $\\sum_k$.\n- l.196: I understand that MPNNs have a central node. But I am not sure what the central node means in CNNs.\n- l.257: \\tilde{f}\\_z → \\tilde{f}\\_{s\\_z} (two places)\n- Table 1: compared with ... → Compared with ...\n\n### Post-rebuttal comments\n\nThe authors answered my questions and they solved most of my questions. In addition, I admit the novelty and significance of this paper. However, I still think that this paper is hard to access for those who are not familiar with this topic, although I understand that the authors have made considerable efforts to improve the readability. Therefore, I want to keep my score (5) and ask the authors to enhance the accessibility.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- [L1] This paper discussed the technical limitations (l.450)\n- [L2] This paper discussed possible negative social impact in the broader impact section (l.334)", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "MlMEnZ7Thq", "reviewer": "Reviewer_3yjU", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "----------Strengths----------\n\n(1) The idea is novel and beautiful since it naturally provides a formalism of constructing permutation equivariant GNNs (proved by Theorem 1 in the paper, although I did not check the proof details) while being much more flexible than conventional GNNs. Autobahn generalizes message passing neural networks (MPNNs) and leads us to some novel architectures.\n\n(2) The paper is well written and reasonably polished. Overall I find the paper not hard to follow.\n\n(3) The paper provides us deeper insights on the formulation of GNNs and opens up a potential new viewpoint. As discussed in the conclusion section, I agree it is an interesting question to ask how certain choices of substructure influence the expressive power of resulting architectures, i.e., the inductive bias problem. Although it is not the scope of this paper, this work can motivate future research on the inductive bias problem of GNNs.\n\n----------Weaknesses----------\n\n(1) Since the construction of an Autobahn network requires solving a subgraph isomorphism problem in general, the efficiency of Autobahn might be a critical issue. However, I think more details on the efficiency of Autobahn could be provided. Moreover, I think it is interesting to know how the choice of the heuristic algorithm, which solves the subgraph isomorphism problem, affects the overall performance.\n\n----------Overall----------\n\nOverall, I think this paper presents a novel and interesting formulation of GNNs, which beautifully incorporate the automorphism groups of subgraphs. I like this work as it opens up a potential new viewpoint and can motivate future research. Hence, I recommend acceptance.\n\n----------After Rebuttal----------\n\nTo conclude, because I am now more concerned about the final presentation of the theoretical results and the overall performance of Autobahn, I think I should be more cautious in recommending this paper. I would prefer to lower the score to 6 and also my confidence to 2. Please see the reply below for the details.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the potential negative social impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel structure-aware GNN architecture based on partitioning the graph into subgraphs. 
The authors provided extensive responses to the reviewers' comments in the rebuttal and followup discussion. There was also an extensive discussion among the reviewers. The reviewers recognize the novelty of the paper. While after rebuttal and discussion some reviewers believe the paper still requires significant editing to improve the clarity, the AC is of the opinion that the novelty outweighs these drawbacks and would like to give the authors the benefit of the doubt recommending to accept the paper and hoping the authors will improve the presentation and introduce edits according to the reviewers' suggestions. 
Decision: Accept (Poster)