Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: ----------Strengths----------

(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.

(2) The paper is well written and reasonably polished. Overall I find the paper not hard to follow.

(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.

----------Weaknesses----------

(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.

----------Overall----------

Overall, 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.

----------After Rebuttal----------

To 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.

limitations_and_societal_impact: The authors have discussed the potential negative social impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

**On the positive side**:

-	The proposed framework is general enough and (although not proven by the authors) clearly more expressive than conventional message passing. 
-	Moreover, 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.
-	The accompanying illustrations (Figure 2, 3, 4) improve the readability and the accessibility of this work to a larger audience.
-	The cycle/path-Autobahn instantiation seems to work relatively well in real-world molecular data.

However, 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:

 **Applicability concerns**:

1.  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,
2.  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).
3.  It requires selecting the subgraphs by domain knowledge.

**Related Work**:
 
1. 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.  
2. 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. 

**Theoretical evidence** :

In 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.

**Experiments**:
1.  More baselines should be added (see the leaderboards for ZINC and ogb),
2. The methods should be sorted according to their performance, 
3. In ZINC, what is the number of parameters (according to the protocol the number of parameters should be ~100K or ~500K)? 
4. 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.

**Additional comments**:

-	Section 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, 
   - 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)}$.
  -  A practical example (e.g., for a cycle graph) would help. 
  - The notation and the explanations of the narrowing and promotion operations are, at least to me, very hard to follow. 
  - L229: the notation is confusing
-	If 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.
-	What happens if a node does not belong in any of the subgraphs?
-	I 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?


**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.


------
## After rebuttal

The 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


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.

*Negative social impacts*: Addressed in Sec. 7.1.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: ### Soundness (Do theorems and experiments answer research questions, assuming they are correct?)

- [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.
- [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.
- [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.
- [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.

### Correctness (Are derivation of theorems and experiments correct?)

- [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.
- [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.
- [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).
- [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).

### Novelty and Significance (Do the paper have novel points? If so, are they significant?)

- [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. 
- [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.
- [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.
- [Nguyen & Maehara, ICML2020] http://proceedings.mlr.press/v119/nguyen20c.html
- [Vignac et al., NeurIPS2020] https://proceedings.neurips.cc//paper_files/paper/2020/hash/a32d7eeaae19821fd9ce317f3ce952a7-Abstract.html
- [Bouritsas et al., arXiv] https://arxiv.org/abs/2006.09252
- [de Haan et al., NeurIPS2020] https://proceedings.neurips.cc//paper/2020/hash/2517756c5a9be6ac007fe9bb7fb92611-Abstract.html

### Clarity (Is the paper clearly written?)

- [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).
- [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.
- [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).

### Other comments

- l.87: One way to accomplish this would to be ... → would be ...
- l.90: $\phi_l$ → $\phi_{\ell}$
- 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.
- 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$.
- l.196: I understand that MPNNs have a central node. But I am not sure what the central node means in CNNs.
- l.257: \tilde{f}\_z → \tilde{f}\_{s\_z} (two places)
- Table 1: compared with ... → Compared with ...

### Post-rebuttal comments

The 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.
limitations_and_societal_impact: - [L1] This paper discussed the technical limitations (l.450)
- [L2] This paper discussed possible negative social impact in the broader impact section (l.334)
review_title: null

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)