Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper presents a natural extension of Message Passing Neural Net (MPNN)  by incorporating structural features. These structural features are computed as the counts from different substructures (like small lines, stars or complete graphs) induced in the original graph. These counts are combined to obtain a new feature per node or per edge. Then these features are used in a standard MPNN. The authors then show that the resulting GNN is more expressive and they validate this claim experimentally.

This idea is interesting and clearly explained in the paper but I think the paper could be greatly improved after addressing the following issues:
 
1- the authors should clarify their position with regards to invariance. Indeed, as explained shortly on page 3 when commenting Loukas(2020), it is easy to make a GNN powerful if we remove the constraint to be invariant (or equivariant). Hence, as I understand it, the authors are proposing an algorithm that is equivariant. If this is the case, it would be great to have a clear formal statement that GSN are equivariant and to give a mathematical proof.

2- the theoretical content of the paper should be improved:

 a- the first part of Proposition 3.1 is straightforward and I find the wording of the second statement unclear: what does '... or any not necessarily induced subgraph...' mean?

 b- from a theoretical perspective, it seems that both GSN-v abd GSN-e have the same expressive power. Is it true?

 c- a similar idea as the one presented in this paper was presented in : Coloring graph neural networks for node disambiguation  by George Dasoulas, Ludovic Dos Santos, Kevin Scaman, Aladin Virmaux https://arxiv.org/abs/1912.06058 [arxiv-col] The main advantage of the current paper as opposed to [arxiv-col] is to propose an explicit coloring thanks to the structural features. But the theoretical analysis made in [arxiv-col]  goes much deeper than this paper and probably could be adapted by the authors. For example, Corollary 3.1 could probably be replaced by a universality property, i.e. GSN with k=n-1 is universal.

3- the experimental evaluation is not convincing. To make it more convincing, the authors should include an ablation study for all their experiments by comparing their performances with the performances obtained with the structural features only. Such an ablation study would show the benefit of adding the MPNN on top of these features. 

[After rebuttal] I think the authors improved their paper by taking into account the remarks. Given the last results obtained in Table 4, it looks like the structural features are indeed very good features in practice as they allow to boost the performances of a very simple invariant architecture like Deepset. I think the authors should explore how they can combine this approach with the coloring approach to get better GNN.
review_title: A natural idea to increase the expressive power of GNNs that would benefit from more theoretical results and more experimental evaluation

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the expressivity of graph neural networks, and proposes a new approach to improve GNN’s expressivity by encoding nodes and edges with features via subgraph isomorphism counting. The proposed solution contains some merit, and the experimental results on graph classification task demonstrates the superiority of the proposed approach.

Pros:
1.	This paper addresses an important problem in GNNs, which is to improve the expressivity of GNNs.
2.	The proposed solution is interesting, which is to include how many isomorphic subgraphs from a given list a node or an edge is contained in as additional features.
3.	The experimental results on multiple datasets and different graph-level tasks are better than baselines.
4.	 Nice theoretical analysis.

Cons:
1.	My biggest concern lies in the time complexity of the proposed approach. Although the paper claims that in practice it is not that bad, the worst time complexity is still high. Also, the substructure selection brings us back to feature engineering, or we will face too many possible substructures.
2.	More challenging graph tasks are expected to demonstrate the necessity of the proposed approach. 

Detailed comments:
1.	In the abstract and introduction, it is mentioned that existing GNNs are bounded by WL-test, and are not able to detect and count graph structures. It is expected to see experiments are on these more challenging tasks, in addition to graph classification and regression tasks. Graph isomorphism test is an interesting task, and the design is smart.
2.	Discussions on how to select substructures on bigger size of graphs are expected.

review_title: This paper studies the expressivity of graph neural networks, and proposes a new approach to improve GNN’s expressivity by encoding nodes and edges with features via subgraph isomorphism counting. The proposed solution contains some merit, and the experimental results on graph classification task demonstrates the superiority of the proposed approach.

final_score: rating: 3: Clear rejection
review_content: Reasons for score:
The idea of using small graphs to characterize local topologies and guide message passing in interesting. However, the graph isomorphism computation part has problem. Experimental results are not conclusive. The written need improvement in some part of the manuscript.  

Pros: A new method (GSN: Graph Substructure Network) is proposed to a topologically-aware message passing method that better utilize graph substructure information. The method tries to tackles the limitation of traditional GNN in exploring graph structure.  It is a good idea to pass messages differently depending on their local topologies. This is done through using a set of predefine small graphs to characterize local topologies. The authors showed that GSN was more expressive than traditional GNNs. A good number of experimental evaluations were performed.
 
Cons: It is not clear priorly how to define a good set of small graphs, especially when considering beyond immediate neighbors. In addition, node features are not considered in graph isomorphism, which can lead to incorrect subgraph matching. The experimental results on some of the datasets (such as, MUTAG, PTC, Proteins and NCI1 in table 1) do not appear to be significantly better than those of the previous approaches when considering the variances of different runs. In addition, much better results were reported on the ogb-molhiv leaderboard (https://ogb.stanford.edu/docs/leader_graphprop/#ogbg-molhiv). Figure 1 is confusing.  Should the number in the yellow square on the left be 5? A more self-contained explanation of the figure is appreciated. It will help readers if the authors can visualize a few examples (e.g., contributions of small graphs) to explain why their approach works better.
review_title: Propose a new method (Graph Substructure Network) for topologically-aware message passing.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work proposes the Graph Substructure Network (GSN) to encode structural roles for different nodes so that the expressivity of Graph Neural Networks is improved. The core idea is to count the number of certain substructures, such as cycles, cliques, and triangles. Then the proposed MPNN encodes such substructure counting information into the message passing. Experimental results show that the proposed method can obtain better performance than the comparing methods. 

Strengths:
+ The proposed method can encode important substructure information. It is important for graphs since, in many applications, the substructures can determine the functionality of graphs.
 
+ The proposed method leads to better performance on different graph classification datasets. The experimental results can show the effectiveness of the proposed method.

Weaknesses:
- The main contribution of this work is counting the substructure information, which can be regarded as the preprocessing of graphs. However, how to properly select the graph set {H_1, … ,H_K}?  With different datasets at hand, the best choice can be quite different. Then how should we apply the proposed method? 

- The second concern is the complexity of the proposed methods. Counting different types of substructures can be very time-consuming. As mentioned in this work, the worst case can have O(n^k) complexity. When the graph size is large, we may need to count too many types of substructures. 

- The datasets are relatively small; most of them have less than 100 nodes per graph. Then larger datasets, such as RDT-B, RDT-M5K, and RDT-M12K, should be considered. I am wondering how many types of substructures need to be considered for these larger datasets to get better performance. 

- This work explicitly encodes substructure information into GNNs. Other existing methods, such as graph pooling methods, which can be considered to implicitly encode structural information. Then advanced pooling methods, such as Diffpool, Structpool, Min-cut Pool, etc., should be discussed and compared. 

I am willing to adjust my score if my concerns are properly addressed. 

=====Update after rebuttal=====

I have read the authors' rebuttal. Considering the limitations and non-superior performance for larger datasets, I am keeping my score unchanged. 
review_title: Official Blind Review #1

Meta-review: We thank the authors for their detailed responses and the revised version, which addresses several of the questions raised by the reviewers.

The paper is correct and clearly written. All reviewers agree that the idea to add structural features in the message passing of graph neural networks is sensible. While different from previous work, the novelty is a bit incremental though, particularly given the previous work on colored graph neural network. The significance of the work is weak, given 1) the need to select "by hand" structural features that are passed as information, 2) the increased time complexity to compute the structural features compared to other GCNN, and 3) the experimental results that suggest that the benefit of the new approach is limited, particularly on challenging task.

To summarize, this is not a bad paper, but we consider it below the standard of ICLR in terms of originality and significance.
Decision: Reject