In this paper, we study a new graph learning problem: learning to count subgraph isomorphisms. Although the learning based approach is inexact, we are able to generalize to count large patterns and data graphs in polynomial time compared to the exponential time of the original NP-complete problem. Different from other traditional graph learning problems such as node classification and link prediction, subgraph isomorphism counting requires more global inference to oversee the whole graph. To tackle this problem, we propose a dynamic intermedium attention memory network (DIAMNet) which augments different representation learning architectures and iteratively attends pattern and target data graphs to memorize different subgraph isomorphisms for the global counting. We develop both small graphs (≤ 1,024 subgraph isomorphisms in each) and large graphs (≤ 4,096 subgraph isomorphisms in each) sets to evaluate different models. Experimental results show that learning based subgraph isomorphism counting can help reduce the time complexity with acceptable accuracy. Our DIAMNet can further improve existing representation learning models for this more global problem.
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.