Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: This paper proposes a new neural network architecture for dealing with graphs dealing with the lack of order of the nodes. The first step called the graph isomorphic layer compute features invariant to the order of nodes by extracting sub-graphs and cosidering all possible permutation of these subgraphs. There is no training involved here as no parameter is learned. Indeed the only learning part is in the so-called classification component which is a (standard) fully connected layer. In my opinion, any classification algorithm could be used on the features extracted from the graphs.
Experiments are then given for the graph classification. I do not understand results of Table 1 as the accuracies reported for MUTAG and PTC in Xu et al with GIN are much higher than the numbers here.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proposes a method to learn graph features by means of neural networks for graph classification.
In the proposed method, a graph is described by bag of sub-graphs and the sub-graph dictionary is learned through isomorphic matching.
The authors present two approaches toward the isomorphic matching; one is a brute-to-force approach to check all the node permutations and the other is based on spectral decomposition toward efficient computation.
In the experiments on the graph classification tasks using several benchmark datasets, the learned features by the proposed method exhibit favorable performance in comparison with the other graph-based methods.

This paper is leaning toward rejection because (1) the proposed method lacks novelty, (2) it contains technically imprecise parts and (3) the effectiveness is not fully validated in the experiments.
The detailed comments are as follows.

* The presented method belongs to the standard feature representation framework that describes graphs by bag of sub-graph templates (dictionary) [a], and this paper's contribution can be found in the way to learn sub-graph dictionary as in learning convolution kernels of CNNs; in contrast to CNN, the graph representation poses a challenging issue of "isomorphism". It, however, simply employs brute-to-force approach toward the graph isomorphism, lacking novelty. On the other hand, the alternative approach relaxes graph matching into Eq.(8) through spectral decomposition. But, it seriously degrades the characteristics of the permutation matrix P and thus the resulting score z does not exhibit a graph matching measure anymore. So, Eq.(8) lacks theoretical justification and is far away from the sub-graph based representation; I cannot understand what kind of features are actually extracted by Eq.(8).

* Though the authors insist that the method retains the explicit graph structural information, are any constraints imposed on the kernel K for embedding the graph structure into K? Namely, the kernel K is required to exhibit the nature of adjacency matrix of sub-graph. It lacks description and/or discussion about the aspect.

* The node-order information still exists in the classification layer (Sec.4.2) since the FC classifier is directly applied to the (flattened) feature map (tensor) Q in which two axes are defined according to the node order in the graph. This contradicts the authors' claim that the method is invariant to node ordering. For accomplishing node-orderless classification, the global pooling such as GAP should be applied to the final feature map before the classifier layer. In addition, I cannot fully understand how to stack the sub-graph based feature extraction (Sec.4.1) in a "deep" manner? After extracting the sub-graph representation first, the resulting matrix is just a feature map of c channels, not an adjacency matrix which contains the pair-wise relationships between nodes. It is unclear how to construct the deeper model by repeatedly applying the sub-graph template matching.

* The method is built upon the local kernel (K) over the adjacency matrix (A). Although it is invariant against the node order "locally" within the local kernel, the method cannot capture the sub-graph structures beyond the locally ordered nodes in A; "locally" ordered nodes in A which exhibits certain sub-graph can be easily spread "globally" via applying node permutation to A. Thus, the method is only applicable to the limited case that node orders of input graphs are "roughly" canonicalized. This paper completely lacks discussion nor analysis about such a limitation/assumption of the method regarding locality.

* In the experiments, the classifier modules are different across the comparison methods. The proposed method that is a feature extraction from graphs should be fairly compared with the other types of graph feature extraction methods in a consistent pipeline on basis of the identical classifier module. And, as to WL method, the performance of 52.4 on MUTAG in Table 1 is significantly inferior to 80.88 which is reported in [b].

[a] Wale, N., Watson, I.A. and Karypis, G., Comparison of descriptor spaces for chemical compound retrieval and classification, Knowl Inf Syst (2008) 14:3, pp.347-375
[b] Schlichtkrull M., Kipf T.N., Bloem P., van den Berg R., Titov I., Welling M. (2018) Modeling Relational Data with Graph Convolutional Networks. In: Gangemi A. et al. (eds) The Semantic Web. ESWC 2018. Lecture Notes in Computer Science, vol 10843. Springer, Cham


Minor comments:
- Improper citation format. Use \citep and \citet properly according to the context.
- This is related to the kernel methods of graph-kernel and string-kernel. It would be better to mention those related kernel functions for clarifying the contributions.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper proposes a neural network architecture to classify graph structure. A graph is specified using its adjacency matrix, and the authors prose to extract features by identifying temples, implemented as small kernels on sub matrices of the adjacency matrix. The main problem is how to handle isomorphism: there is no node order in a graph. The authors propose to test against all permutations of the kernel, and choose the permutation with minimal activation. Thus, the network can learn isomorphic features of the graph. This idea is used for binary graph classification on a number of tasks.

Graph classification is an important problem, and I found the proposed solution to be quite elegant. The paper is mostly well written (it could use some proofreading, but the main ideas are explained well). Overall, I liked the idea and tend towards acceptance.

In the experiments, the authors report using different hyper parameters for each data set (e.g., k). I did not understand how these parameters were chosen, since only training and testing sets were reported. I would like the authors to clarify how model selection was performed.

Also, Figure 1 and the details in Section 4 discuss a 1-layer isomorphic NN. The discussion in Section 4.3.2 discusses multi-layer feature extraction. If I understand correctly, this means to apply the graph isomorphic layer + min pooling + softmax several times, but this should be stated explicitly.
review_title: Official Blind Review #3

Meta-review: This paper proposes a method to learn graph features by means of neural networks for graph classification.
The reviewers find that the paper needs to improve in terms of novelty and experimental comparisons. 
Decision: Reject