Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes a dynamic inter-medium attention memory network and model the sub-graph isomorphism counting problem as a learning problem with both polynomial training and prediction time complexities.
Since the testing time is reported in this paper, and the time complexity is one of the main contribution of this paper. The hardware and software used to run the algorithm should be reported in the main article.

The author argues that if we use neural networks to learn distributed representations for V_G and V_p or \xi_G and \xi_P without self-attention, the computational cost will acceptable for large graphs, but the missing of self-attention will hurt the performance. It’s encouraged to do corresponding experiments to compare it with the proposed method and better support the algorithm.

One of the main advantages of this paper is that the proposed method can efficiently deal with large graph tasks, so the model behaviors of different models in large dataset similar to Figure 5 is encouraged to be given.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper studied how to leverage the power of graph neural networks for counting subgraph isomorphism. The motivation is that the current subgraph isomorphism detection is NP-complete problem and a proposed approach based on GNN could approximately solve the counting problem in polynomial time. Then they relaxed original subgraph isomorphism (which is equivalent to the exact subgraph matching problem)  and proposed the problem of doing subgraph isomorphism counting task. The GNN and sequence modeling methods are discussed for solving this problem. The experimental results confirmed the effectiveness of these methods. 

Although I found the subgraph isomorphism counting problem is an interesting problem, I did not know how much practical usefulness of this task. More practical use case would be search for the matched subgraphs given the sub-graph query using subgraph isomorphism detection. 

Also, although authors mentioned some approximation systems/methods in graph database community such as TurboISO (Han et al., 2013), VF3 (Carletti et al., 2018), and other approximation techniques [1][2], authors did not consider them as baselines to compare. These methods may also have limitations to deal with real-large graph but for the graph size that this paper studied I think they are fine to deal with. A parallel issue is that GNN also has scalability issues as well when dealing with large graphs [3]. Without comparing these existing fast (approximation) methods, it is really unfair to compare with only non-DL baseline VF2, which seems served as ground-truth as well. 

[1]  A Neural Graph Isomorphism Algorithm Based on Local Invariants, ESANN'2003
[2] Subgraph Isomorphism in Polynomial Time
[3] FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling

In terms of technical contributions, they leverage some existing sequence models (CNN, RNN and so on) and graph models (RGNN) and the whole framework is similar to doing a graph matching networks (without considering node alignment) for a regression task. The DYNAMIC INTERMEDIUM ATTENTION MEMORY NETWORK is interesting yet simple. I am not entirely clear what's the output  of this interactional module. The figure 4 shows the overall architecture of subgraph isomorphism counting model, which needs better descriptions to understand exact input and output for each module. In general, the novelty of this part is incremental. 

Finally, this subgraph isomorphism counting problem is closely related to graphlet counting problem. In the paper, the subgraph pattern considered seems like almost identical to graphlets the previous research extensively studied. I did not see any discussion about the connection of these two tasks either. 

Minor comments:

|V_G| is is the number of pattern nodes -> |V_p| is is the number of pattern nodes
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: This paper proposes a method called Dynamic Intermedium Attention Memory Network (DIAMNet) to learn the subgraph isomorphism counting for a given pattern graph P and target graph G. This requires global information unlike usual GNN cases such as node classification, link prediction, community detection. First, input graphs P and G are converted embedding vectors through sequence models (CNN, RNN, Transformer-XL) or graph models (RGCN), and fed into their DIAMNet that uses an external memory as an intermedium to attend both the pattern and the graph. The external memory is updated based on multi-head attention as in Transformer. The output of DIAMNet is passed to FC that outputs 'count' directly. The training is based on minimizing MSE loss as a regression problem. Extensive experimental evaluations report that DIAMNet showed superior performance over competing methods and baselines.

This paper targets subgraph isomorphism counting as a learning problem for the first time I guess, and the proposed method combined with both graph- and sequence-based encoding is technically interesting. However, there are still two major issues of 1) why counting? 2) the RMSE loss for regression on counts 3) baseline of 'Zero'.

1) the most unclear point is 'why counting?'. If I understand it, this method can be applied to subgraph isomorphism (NP-hard) or graph isomorphism (unknown complexity) as binary classification, and experimental evaluations can use the datasets used in evaluating VF2 or Naughty. It would be better to start this fundamental problem that would have many clear applications. Compared to subgraph isomorphism or graph isomorphism, the need for knowing accurate 'counts' of subgraph isomorphisms is unconvincing (given that we cannot explicitly obtains all subgraph matchings). Note that there is some existing research on GNNs targeted 'graph matching' and 'graph similarity'. 

Also, the used datasets intentionally restrict the possible values for the number of subgraph isomorphisms, but the counts would be exponentially large if we consider practical (dense) graphs. 

2) the method fits the model using (R)MSE loss, but minimizing log errors ((R)MSLE) would be better considering distributions of response values (counts) of the used datasets in Figure 6. Fitting the MSE loss is not good for such highly skewed cases, and for example, might focus only on the few instances having very large count values. Or, if such instances are very small, training ignores all such extreme instances. Either way would be questionable when we consider learning 'subgraph isomorphism counting' in general. 

Also, the error of counts by MSE or MAE would be less informative and it would be unclear how much errors are tolerant in practical use cases of this method. 

3) To interpret the RMSE and MAE values, Table 2 has the value for 'Zero'. This is for a constant predictor always returning zeros for any inputs. However, given that the loss is MSE, constant prediction values should be the average counts in the training data, not zero. 

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper proposed NN based subgraph counting. By using synthetically generated graphs, NN learns the number of occurences of a given queried graph called 'pattern'. The author proposes a specific architecture for learning the count based on the multi-head attention method. The authors empirically evaluated the performance on the synthetic dataset.

The problem setting would be interesting. Applying NN to counting a subgraph is novel as far as I know. My current concerns are mainly on the appropriateness of the experimental evaluation. 

In the tables, the trivial baseline 'Zero' is shown as F1_zero = 0, but is this correct? I think this should be non-zero. If zero is 'positive' in F1_zero, recall is 1 and precision is 0.75 (because the author set 75% of data as zero). F-score is harmonic mean of them, which is 0.86.

RMSE and MAE of the Zero prediction is shown, but the more standard baseline of the error would be a constant prediction (e.g., the average of test points is often used, which can evaluate how much variance can be explained by the model).

Why were 75 percent of countings set as 0 in the evaluation dataset? This rate is seemingly a bit large for the evaluation purpose. I guess that when this percentage is much more smaller, MSE would increase. In other words, current MSE/MAE values might be underestiamted compared with when all the test points have non-zero countings.

The evaluation is only for synthetic dataset for which generating process is designed by the authors. If possible, evaluation on benchmark graph datasets would be convincing though creating the ground truth might be difficult for larger graphs.

Minor comment:
At the third line of Sec 3.2: '|V_G| is the number of pattern nodes' should be |V_P|.

review_title: Official Blind Review #3

Meta-review: This paper proposes a method called Dynamic Intermedium Attention Memory Network (DIAMNet) to learn the subgraph isomorphism counting for a given pattern graph P and target graph G. However, the reviewers think the experimental comparisons are insufficient. Furthermore,  the evaluation is only for synthetic dataset for which generating process is designed by the authors. If possible, evaluation on benchmark graph datasets would be convincing though creating the ground truth might be difficult for larger graphs.

Decision: Reject