Neural Subgraph Isomorphism Counting
Authors: Xin Liu
Haojie Pan
Mutian He
Yangqiu Song
Xin Jiang
Venue:  (2020)
Keywords: subgraph isomorphism
graph neural networks

Abstract: 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.

Under review as a conference paper at ICLR 2020
NEURAL SUBGRAPH ISOMORPHISM COUNTING
Anonymous authors
Paper under double-blind review
ABSTRACT
In this paper, we study a new graph learning problem: learning count sub- graph isomorphisms. Although the learning based approach is inexact, we are able generalize count large patterns and data graphs in polynomial time com- pared 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 dynamic interme- dium attention memory network (DIAMNet) which augments different represent- ation 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 (S 4,096 subgraph isomorphisms in each) sets to evaluate different models. Experi- mental 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.
INTRODUCTION
Graphs general data structures widely used in many applications, including social network ana- lysis, molecular structure analysis, natural language processing and knowledge graph modeling, etc. Learning with graphs has recently drawn much attention as neural network approaches to repres- entation learning have been proven to be effective for complex data structures (Niepert et al. 2016 Kipf & Welling 2017; Hamilton al.) 2017b; Schlichtkrull et al.) [0018] Velickovic al. 2011 Xu et 2019). Most of existing graph representation learning algorithms focus on problems such as node classification, linking prediction, community detection, etc. (Hamilton et al. 2017a). These applications are of more local decisions for which learning algorithm can usually make infer- ences by inspecting the local structure of graph. For example, for the node classification problem, after several levels of neighborhood aggregation, the node representation may be able to incorporate sufficient higher-order neighborhood information to discriminate different classes (Xu et al. 2019).
In this paper, study more global learning problem: learning count subgraph isomorphisms (counting examples are shown as Figure []] Although subgraph isomorphism is the key to solve graph representation learning based applications (Xu et al., 2019), tasks of identifying or counting subgraph isomorphisms themselves are also significant and may support broad applications, such as bioinformatics (Milo al. 2002 Alon et al. 2008), chemoinformaties (Huan al. 2003), and online social network analysis KKramochi & Karypis 2004). For example, in social network, we can solve search queries like "groups of people who like X and visited Y-city/state." " In a knowledge graph, we can answer questions like "how many languages are there in Africa speaking by people living near the banks of the Nile River?" Many pattern mining algorithms or graph database indexing based approaches have been proposed to tackle subgraph isomorphism problems (Ullmann) 1976 Cordella et al. 2004 He Singh| 2008 Han et al. 2013) Carletti et al., 2018). However, these approaches cannot be applicd large-scale graphs because of the exponential time complexity.
Thanks to the powerful graph representation learning models which can effectively capture local structural information, we use a learning algorithm to learn how to count subgraph isomorphisms from a lot of examples. Then the algorithm can scan a large graph and memorize all necessary local information based query pattern graph. In this case, although learning based approaches can be inexact, we can roughly estimate the range of the number of subgraph isomorphism. This can already help many applications that do not require exact match need more efficient pre-

---

Under review as a conference paper at ICLR 2020
Homegencous
Heterogenous
Pattern
Graph
Count
Pattern
Graph
Count
Pattern
Graph
Count
A
0
0
0
N
12
X
24
6
2
Figure 1: Subgraph isomorphism counting examples in different settings. The first is the homogen- cous graph counting problem. The second is a heterogeneous vertex graph counting problem where there are types of nodes. The third is a heterogencous vertex and heterogeneous edge graph counting problem where there are two types of nodes and two types of edges.
processing step. To this end, in addition to trying different representation learning architectures, we develop dynamic intermedium attention memory network (DIAMNet) to iteratively attend the query pattern and the target data graph to memorize different local subgraph isomorphisms for global counting. To evaluate the learning effectiveness and efficiency, we develop small (< 1,024 subgraph isomorphisms in each graph) and a large (Σ 4,096 subgraph isomorphisms in each graph) dataset and evaluate different neural network architectures.
Our main contributions are as follows.
To our best knowledge, this is the first work model the subgraph isomorphism counting problem as a learning problem, for which both the training and prediction time complexities are polynomial.
We exploit the representation power of different deep neural network architectures in end-to- end learning framework. In particular, we provide universal encoding methods for both sequence models and graph models, and upon them introduce dynamic intermedium attention memory network to address the more global inference problem for counting.
We conduct extensive experiments developed datasets which demonstrate that framework can achieve good results on both relatively large graphs and large patterns compared to existing studies.
2 RELATED WORK
Subgraph Isomophism Problems. Given a pattern graph and data graph, the subgraph isomorph- ism search aims to find occurrences of the pattern in the data graph with bijection mapping func- tions. Subgraph isomorphism is an NP-complete problem among different types of graph matching problems (monomorphism, isomorphism, and subgraph isomorphism). Most subgraph isomorphism algorithms are based on backtracking. They first obtain series of candidate vertices and update mapping table, then recursively revoke their own subgraph searching functions to match one ver- tex one edge at time. Ullmann's algorithm (Ullmann) 1976). VF2 (Cordella al. 2004). and GraphQL (He Singh, 2008) belong to this type of algorithms. However, it is still hard to perform search when either the pattern the data graph grows since the search space grows exponentially as well. Some other algorithms are designed based on graph-index, such as gIndex (Yan et al.) 2004), which can be used as filters prune out many unnecessary graphs. However, graph-index based algorithms have a problem that the time and space in indexing also increase exponentially with the growth of the graphs (Sun et al. 2012). TurbolSO (Han al. 2013) and VF3 (Carletti et al. 2018) add some weak rules to find candidate subregions and then call the recursive match procedure on subregions. These weak rules can significantly reduce the searching space most cases.
Graph Representation Learning. Graph (or network) representation learning can be directly learn- ing an embedding vector of each graph node (Perozzi et af., 2014, Tang al., 2015 Grover & Leskoved 2016). This approach is not easy to generalize to unseen nodes. On the other hand, graph neural networks (GNNs) (Battaglia et al. 2018) provide a solution to representation learning for nodes which can be generalized to new graphs and unseen nodes. Many graph neural networks have been proposed since 2005 (Gori et al. 2005; Searselli et al., 2005) but rapidly developed in recent years. Most of them focus generalizing the idea of convolutional neural networks for general graph data structures (Niepert et al. 2016 Kipf & Welling 2017 Hamilton et al. al. [2017]] 2017/211///elice Velickovic et al. 2018) relational graph structures with multiple types of relations (Schlichtkrull al. 2018).
2

---

Under review as a conference paper at ICLR 2020
More recently, Xu et al. (2019) propose a graph isomorphism network (GIN) and show its discrimin- ative power. Others use the idea of recurrent neural networks (RNNs) which are originally proposed to deal with sequence data to work with graph data @Li et al. 2016 You et al. 2018). Interestingly, with external memory, sequence models can work well on complicated tasks such as language mod- eling (Sukhbaatar et al.) 2015] Kumar al. (016) and shortest path finding on graphs (Graves al.,
2016). There is another branch of research called graph kernels (Vishwanathan et al. [2010] Sher- vashidze et al., 2011; Yanardag Vishwanathan, 2015: Togninalli al. 2019 Chen et al. 2019) which also convert graph isomorphism to similarity learning problem. However, they usually work
on small graphs and do not focus on subgraph isomorphism identification or counting problems.
PRELIMINARIES
We begin by introducing the subgraph isomophism problems and then provide the general idea of our work by analyzing the time complexities of the problems.
3.1 PROBLEM DEFINITION
Traditionally, the subgraph isomorphism problem is defined between two simple graphs or two dir- ected simple graphs, which is an NP-complete problem. We generalize the problem to counting problem over directed heterogeneous multigraphs, whose decision problem is still NP-complete.
A graph pattern is defined as G = (V, E) where V is the set of vertices. & CVV* x V is the set of edges, is label function that maps a vertex to vertex label, and y a label function that maps edge to set of edge labels. We use edge with a set of edge labels to represent multiedges with the same source and the same target for clarity. That is, there are no two edges in graph such that they have the same source, same target, and the same edge label. To simplify the statement, we assume ((u, v)) = & if (u, v) E.
In this paper, we discuss isomorphic mappings that preserve graph topology, vertex labels and edge labels, but not vertex ids. More precisely, a pattern Gp = (Vp. Xp, vp) is isomorphic to a graph Ga (Va, &a, NG, Vc) if there is a bijection f Va Vp such that:
Vu E Va, No(()) = Xr(S(v)),
Vu Vp, Xol (v)),
V(, E Ea, Ea,Ju, v)) = Vr((I(u),
(u, E Ep,
Furthermore, Gp being isomorphic to a graph GG denoted Op GG and the function f is named as an isomorphism.
is isomorphic a subgraph G/ (V E/ Va) of graph Go = (Ve, Xa, Va): Va C V.. E Eg n (V% x Voy) if 9p ~ gg. The bijection function f: V/ + Vp is named as a subgraph isomorphism.
pattern Gp Ep, Xp) E'p,
The subgraph isomorphism counting problem is defined as to find the number of all different sub- graph isomorphisms between a pattern graph Gp and a graph Gg. Examples are shown in Figure
3.2 GENERAL IDEA
Intuitively, need compute O(Perm [rl) Vell) to solve the subgraph isomorphism counting problem by enumeration, where Perm(n,k k) (.-
a! MVal is the number of graph nodes,
|Vr| the number of pattern nodes, d is the maximum degree. The first subgraph isomorphism algorithm, Ullmann's ' algorithm (Ullmann 1976). reduces the seaching time to O(Drr -Pal)) the pattern and the graph are both small, the time is acceptable because both two factors are not horrendously large. However, since the computational cost grows exponentially, it is impossible to count as either the graph size or the pattern size increases. If we use neural networks to learn distributed representations for Ve and Vp Eg and εp, can reduce the complexity to O(Vpl [Val + [Val") or O1Ep) |Eal + [Eq via source attention and self-attention. Assuming that we can further learn much higher level abstraction without loss of representation power for Gr. then
3

---

Under review as a conference paper at ICLR 2020
Partern
Representation
Interaction
Count
Graph
Representation
Figure 2: General framework of neural subgraph isomorphism counting models.
I 2
6 6
2
6
8
2 5
7 8
Graph
Sequence view
Graph view
Two views of different encoding methods. There are three labels of vertices (marked as orange, blue, and yellow) and two labels of edges (marked as solid and dashed lines). The numbers affixed show one possible set of ids for the vertices.
Figure 3:
the computational cost can be further reduced to O or O(EEa))). However, the complexity of the latter framework is still not acceptable when querying over large graphs. If do consider self-attention, the computational cost will be ((Val) O(E&a)), but missing the self-attention will hurt the performance. In this work, we hope to use attention mechanism and additional memory networks to further reduce the complexity compared with ((Vall? or O((Eg?? while keeping the performance acceptable on the counting problem.
4 METHODOLOGIES
A graph (or a pattern) can be represented as sequence of edges series of adjacent matrices and vertex features. For sequence inputs we can use CNNs (Kim 2014), RNNs such as GRU (Cho et al., 2014), or Transformer-XI. (Dai al. 2019) extract high-level features. While if the inputs modeled as series of adjacent matrices and vertex features, we can use RGCN (Schlichtkrull et al.] 2018) learn vertex representations with message passing from neighborhoods. After obtaining the pattern representation and the graph representation, we feed them into an interaction module to extract the correlated features from each side. Then we feed the output context of the interaction module into conneced layer to make predictions. A general framework is shown in Figure and the difference between sequence encoding and graph encoding shown Figure
4.1 SEQUENCE MODELS
4.1.1 SEQUENCE ENCODING
In sequence models, the minimal element of graph (or pattern) is an edge. By definition, at least three attributes are required identify an edge e, which are the source vertex id u, the target vertex id v, and its edge label y E )ee).. We further add two attributes of vertices' labels to form a 5-tuple (u, v, (u),, y, (w)) to represent an edge e, where X'uw) is the source vertex label and ((()) is the target vertex label. A list of 5-tuple is referred as code. We follow the order defined in gSpan (aan & Han 2002) to compare pairs of code lexicographically: the detailed definition is given in Appendix A The minimum code is the code with the minimum lexicographic order with the same elements. Finally, each graph can be represented by the corresponding minimum code, and vice versa.
Given that a graph is represented as a minimum code, or list of 5-tuples, the next encoding step to encode each 5-tuple into vector. Assuming that know the max values of \V] [2'). [}]]

---

Under review as a conference paper at ICLR 2020
in dataset in advance. nary digits, where B is the base and each digit d E {0,1. B 18-1] 13. It is easy to replace each digit with a one-hot vector that each 5-tuple can be vectorized as multi-hot vector which is the concatenation of one-hot vectors. The length of the multi-hot vector a 5-tuple is B x (2 Then minimum is achieved when B = 2 and de = 2 x (2- [log2 (Max (1)) + [logz (ar((X))
encode each vertex id vertex label and edge label y into B-
[logg(Maz(())
2 [logg(M
+ (ogg((Mrr(()))))
Then we can easily calculate the graph dimension d, and the pattern dimension dy. Furthermore,
the minimum code can be encoded into multi-hot matrix, G Rl for a graph 9G or P RlErlxd, for pattern Gp according this encoding method.
This encoding method can be extended when we have larger values of [V], 1.), (3). A larger value, e.g.. 1/. only increases the length of one-hot vectors corresponding to its field. Therefore, we can regard new digits as the same number of zeros in previous data. As long as we process previous one-hot vectors carefully to keep these new dimensions from modifying the original distributed representations, we can also extend these multi-hot vectors without affecting previous models. A simple but effective way is to initialize additional new weights related new dimensions as zeros.
4.1.2 SEQUENCE NEURAL NETWORKS
Given the encoding method in Section 4.1.1 we can simply embed graphs as multi-hot matrices. Then we can use general strategies of sequence modeling to learn dependencies among edges in graphs.
Convolutional Neural Networks (CNNs) have been proved to be effective in sequence modeling (Kim 2014). In our experiments, we apply multiple layers of the convolution operation to obtain sequence of high-level features.
Recurrent Neural Networks (RNNs), such as GRU (Cho al.) 2014). are widely used in many sequence modeling tasks.
Transformer-XL (TXL) (Dai et al. 2019) a variant of the Transformer architecture (Vaswani et al. 2017) and enables learning long dependencies beyond a fixed length without disrupting tem- poral coherence. Unlike the original autoregressive settings, in our model the Transformer- XL en- coder works as feature extractor, in which the attention mechanism has full, unmasked scope over the whole sequence. However, its computational cost grows quadratically with the size of inputs, so the tradeoff between performance and efficiency would be considered.
4.2
GRAPH MODELS
4.2.1
GRAPH ENCODING
In graph models, each vertex has feature vector and edges are used to pass information from its source to its sink. GNNs do not need vertex ids and edge ids explicitly because the adjacency information included adjacent matrix. As explained labels into multi-hot vectors as vertex features. In a simple graph or simple directed graph, the adjacent information can be stored in sparse matrix to reduce the memory usage and improve the computation speed. As for heterogeneous graphs, behaviors of edges should depend on edge labels. RGCNs have relation-specifie transformations so that each edge label and topological information are mixed into the message to the sink. We follow this method and use basis-decomposition for parameter sharing (Schlichtkrull et al. 2018).
Section[411.1 we can vectorize vertex
4.2.2 GRAPH NEURAL NETWORKS
Relational Graph Convolutional Networks (RGCNs) (Schlichtkrull al., 2018) are developed specifically to handle multi-relational data in realistic knowledge bases. Each relation corresponds to a transformation matrix to transform relation-specific information from a neighbor to the center vertex. Two decomposition methods are proposed to address the rapid growth in the number of para- meters with the number of relations: basis- deciipsdcooooitiionnn and block-
We use the first method, which is equivalent to the MLPs in GIN (Xu et al. 2019). The original RGCN uses the mean aggregator, but Xu et al. (2019) find that the baseb GNNs can capture graph structures better. We implement both and named them as RGCN and RGCN-SUM respectively.
5

---

Under review as a conference paper at ICLR 2020
Panam Reyu Rigetccctttooo
4
joite
Grash Repocietttton
Figure 4: Illustration of dynamic intermedium attention memory network (DIAMNet). +1 repres- and and two types of gates are Eqs. and
ents Eqs.
and 2 represents Eqs.
4.3 DYNAMIC INTERMEDIUM ATTENTION MEMORY NETWORK
After obtaining a graph representation G and pattern representation P from sequence model or graph model where their column vectors d-dimensional, feed them inputs of interaction layers to extract the correlated context between the pattern and the graph. A naive idea is to use attention modules (Bahdanau al. 2015) to model interactions between these two representations and interactions over the graph itself. However, this method is not practical due to its complexity, up to O(EEp1 &&l |& 2) for sequence modeling and ((Vrr] |Vel + (Vl??) for graph modeling.
To address the problem of high computational cost in the attention mechanism, we propose the Dynamic Intermedium Attention Memory Network (DIAMNet), using an external memory as an intermedium to attend both the pattern and the graph in order. To make sure that the memory has the knowledge of the pattern while attending the graph and vice-versa, this dynamic memory is designed as gated recurrent network shown in Figure 4 Assuming that the memory size is M and we have recurrent steps, the time complexity is decreased into O M (|Erl + (Egl)) or OTT M. (IVrl + [Vl)), which means the method can be easily applied to large-scale graphs.
The external memory is divided into M blocks {mı, ; ..., mar) [m,] is updated by the pattern and the graph in order via multi-head attention mechanism (Vaswani et al. 2017). Specifically, the update equations of our DIAMNet are given by:
where m, Rd. At each time step 4
= M MultiHead(mss (0) P)
(1)
2 (6) (UPm)) + Vps.") (t)
8 2," o mm.) + (1 (0 5
(3)
9 MultiHead(( (0) G. ))
(4)
z (UGo))" +o3 (1)
(5)
m
((+1) 2 oo (1) + (1 - (00 o 88
(6)
Here MultiHead is the attention method described Vaswani et al. 2017), a represents the logistic sigmoid function, 8, is the intermediate state of the jth block of memory that summarizes information from the pattern, and for information from both the pattern and the graph. z; and ž; are two gates designed to control the updates on the states in the jth block. Up, Vp, Ua. Va E gdxd are trainable parameters.
EXPERIMENTS
In this section, report major experimental results. More results be found in the Appendix.

---

Under review as a conference paper at ICLR 2020
5.1 DATASETS
In order to train and evaluate our neural models for the subgraph isomorphism counting problem. need to generate enough graph-pattern data. As there's no special constraint the pattern, the pattern generator may produce any connected multigraph without identical edges, i.e., parallel edges with identical label. In contrast, the ground truth number of subgraph isomorphisms must be tractable in our synthetic graph data. Therefore, our graph generator first generates multiple discon- nected components, possibly with some subgraph isomorphisms. We use the idea of neighborhood equivalence class (NEC) in TurboISO (Han et al.) 2013) to control the necessary conditions of subgraph isomorphism in the graph generation process. The detailed algorithms are shown in Ap- pendix B Then the generator merges these components into larger graph and ensures that there is no more subgraph isomorphism generated in the merge process. The subgraph isomorphism search can be done during these components subgraphs in parallel.
Using the pattern generator and the graph generator above, we can generate many patterns and graphs for neural models. We are interested in follow research questions: whether sequence models and graph convolutional networks can perform well given limited data, whether their running time acceptable, and whether memory can help models make better predictions even faced with NP- complete problem. To evaluate different neural architectures and different prediction networks, we generate two datasets in different graph scales and the statistics are reported in Table There are 187 unique patterns in whole pairs, where 75 patterns belong to the small dataset, 122 patterns belong to the large dataset. Target data graphs are not required similar so they are generated randomly. The generation details are reported in Appendix C
Table 1: Statisties of the datasets.
#Training
#Dev
#Test
Mean((VGl)
Mean Mean((EG))
Counts
Small Large
398,088
49,761 39,528
49,761 39,528
32.6
76.3
{ce Nlc S 0244
316,224
240.0
560.0
{ce N 096)
5.2
IMPLEMENTATION DETAILS
Instead of directly feeding multi-hot encoding vectors into representation modules, we two simple linear layers separately to transform graph multi-hot vectors and pattern multi-hot vectors lower-dimensional, distributed ones. To improve the efffciency, we also add filtering layer to filter out irrelevant parts before all representation modules. The details of this filter layer is shown in Section D.1
5.2.1 REPRESENTATION MODELS
In our experiments, we implemented five different representation models: (1) CNN is 3-layer con- volutional layers followed by max-pooling layers. The convolutional kernels are 2,3,4 respectively and strides are 1. The pooling kernels are 2,3,4 and strides 1. (2) RNN is simple 3-layer GRU model. (3) TXL is 6-layer Transformer encoder with additional memory. (4) RGCN is a 3-layer RGCN with the basis decomposition. We follow the same setting in that ordinal paper to mean- pooling in the message propagation part. (5) RGCN-SUM is a modification of RGCN to replace the mean-pooling with sum-pooling.
5.2.2 INTERACTION NETWORKS
After getting graph representation & and pattern representation PO from the representation learn- ing modules, we feed them into the following different types of interaction layers for comparison.
SumPool: A simple sum-pooling is applied for & and P to obtain ğ and p. and the model sends Concate P. - p. 9 ④ p) with the graph size and the pattern size information into the next fully connected (FC) layers.
McanPool: Similar settings as SumPool, but to replace the pooling method with mean-pooling.
MaxPool: Similar settings as SumPool, but replace the pooling method with max-pooling.

---

Under review as a conference paper at ICLR 2020
We want to use attention modules without much computational cost the self-attention is not acceptable. We simplify the attention by first applying a pooling mechanism for the pattern graph and then use the pooled vector to perform attention over the data graph rather than simply perform pooling over it. Other settings are similar with pooling methods. The detailed information provided in Appendix [D.2 We only report results of mean-pooling based attention, because it is the best of the three variants,
AttnPool:
DIAMNet: We compare the performance and efficiency of our DIAMNet proposed in Section 4.3 with above interaction networks. The initialization strategy we used is shown in Appendix D.3 And we feed the whole memory with size information into the next FC layers.
5.3 EXPERIMENT SETTINGS
For fair comparison, we set embedding dimensions, dimensions of all representation models, and the numbers of filters all 64. The segment size and memory size in TXL. also 64 due to the computation complexity. The length of memory is fixed to 4 and the number of recurrent steps is fixed to 3 in the DIAMNet for both small and large datasets. We the mean squared error (MSE) to train models and evaluate the validation set to choose best models. The optimizer is Adam with learning rate 0.001. L2 penalty added and the coefficient is set as 0.001. To avoid gradient explosion and overfitting, we add gradient clipping and dropout with a dropout rate 0.2. We use Leaky ReLU as activation functions in all modules. Due to the limited number of patterns, the representation module for patterns are easy to overfit. Therefore, we use the same module with shared parameters to produce representation for both the pattern and the graph. We also find that using curriculum learning (Bengio et al., (2009) can help models to converge better. Hence, all models in Table lare are fine-tuned based on the best models in small in the same settings. Training and evaluating were finished on one single NVIDIA GTX 1080 Ti GPU under the PyTorch framework.
5.4 EVALUATION METRICS
As we model this subgraph isomorphism counting problem as regression problem, we use common metrics in regression tasks, including the root mean square eгror (RMSE) and the mean absolute error (MAE). In this task, negative predictions meaningless, we only evaluate ReLU as final prediction results. Considering that about 75% of countings are O's in our dataset, we also use evaluation metrics for the binary classification analyze behaviors of different models. We report F1 scores for both zero data (F1 zero) and nonzero data nowzero) Two trivial baselines, Zero that always predicts O and Avg that always predicts the average counting of training data, are also used in comparison.
5.5 RESULTS AND ANALYSIS
We first report results for small dataset in Table results for large dataset in Table In addition to the trivial all-zero and average baselines and other neural network learning based baselines, we also curious about what extent neural models can be faster than traditional searching algorithms. Therefore, we also compare the running time. Considering the graph generation strategy we used, we decide to compare with VF2 algorithm (Cordella et al. (0044) to avoid unnecessary interference from the similar searching strategy. From the experiments, we can draw following observations and conclusions.
Comparison of different representation architectures. As shown in Table in general, graph models outperform most of the sequence models but cost more time do inference. CNN is the worst model for the graph isomorphism counting problem. The most possible reason is that the se- quence encoding method is not suitable for CNN. The code order does not consider the connectivity of adjacent vertices and relevant label information. Hence, convolutional operations and pooling operations cannot extract useful local information but may introduce much noise. From results of the large dataset, we can see that Fl 0. 180 is even worse than others. In fact, we find that CNN always predicts for large graphs. RNN and TXL are widely used in modeling sequences in many applications. The two models with simple pooling with sum- num-pooling is better than TXL with memory. RNN itself holds a memory but TXL also has much longer memory. However, the memory in RNN can somehow memorize all information that
perform well. We note that RNN
8

---

Under review as a conference paper at ICLR 2020
Table 2: Results of different models on the small dataset. Time is evaluated on the whole test set.
Test Flaaro
Models
RMSE
MAE
Fl monnzero
Time (sec)
SumPool
55.429
11.057
0.807
0.397
0.29
MeanPool
57.298
10.517
0.821
0.475
0.27
CNN
MaxPool
47.353
11.212
0.832
0.539
0.27
AttnPool
55.963
12.717
0.796
0.340
0.54
DIAMNet
34.448
6.953
0.884
0.753
0.90
SumPool
29.955
5.740
0.908
0,819
0.55
MeanPool
31.010
6.447
0.912
0.833
0.54
RNN
MaxPool
30.824
6.236
0.869
0.690
0.58
AttnPool
31.857
6.025
0.899
0.793
0.79
DIAMNet
29.743
5,547
0,927
0.877
1.15
SumPool
34.391
7.042
0.899
0.798
1.98
McanPool
32.569
6.656
0,882
0.754
1.98
TXL
MaxPool
65.152
30.289
0.572
0.669
1.99
AttnPool
37.721
7,426
0.869
0.719
2.22
DIAMNet
31.649
6.680
0.900
0.811
2.48
SumPool
32.414
6.578
0.900
0.796
6.05
MeanPool
33.829
7.152
0.878
0.735
5,99
RGCN
MaxPool
50.851
9.707
0.869
0.704
6.04
AttnPool
32.526
6.523
0.870
0.697
6.27
DIAMNet
28.712
5.782
0.918
0.868
6.69
SumPool
22.379
3.958
0.920
0.845
5.78
McanPool
22.483
4.254
0.903
0,803
5,81
RGCN-SUM
MaxPool
42.434
7,900
0.874
0.709
6.08
AttnPool
24.875
5.131
0.840
0.569
6.49
DIAMNet
21.734
3.853
0.924
0.864
6.55
Zero
67.195
13.716
0.761
0.0
Avg
65.780
21,986
0.0
0.557
VF2
0.0
0.0
1.0
1.0
120
Table 3: Results of different models on the large dataset. Time is evaluated on the whole test set.
Test
Model
RMSE
MAE
Fl zero
FI Floeeee
Time (sec)
MaxPool
234.215
33.859
0.787
0.180
2.01
CNN
DIAMNet
193.410
29.726
0.831
0.523
5.82
SumPool
136.031
20.234
0.905
0.799
16.40
RNN
DIAMNet
134.786
21.595
0.911
0.844
19.98
MeanPool
182.637
35.749
0.842
0.587
61.83
TXL
DIAMNet
167.480
26.954
0.881
0.749
67.95
SumPool
149.060
23.051
0,927
0.864
25.74
RGCN
DIAMNet
147.511
24.398
0.926
0.883
29.63
SumPool
125.022
16.551
0.903
0.788
25.14
RGCN-SUM
DIAMNet
118.433
16.152
0,930
0.879
30.72
Zero
237.904
35.445
0.769
0.0
Avg
235.253
60.260
0.0
0.545
VF2
0.0
0.0
1.0
1.0
x 10"
has been seen previously but the memory of TXL is the representation of the previous segment. In our experiments, the segment size is 64 so that TXL can not learn the global information time. part of the structure information misleads TXL. which is consistent with CNN. longer segment set for TXL may lead to better results, but it will require much more GPU memory and much longer time for training. RGCN-SUM is much better than RGCN and other sequence models, which shows that sum aggregator is good at modeling vertex representation in this task. The mean aggregator can model the distribution of neighbor but the distribution can also misguide models.
Effectiveness of the memory. Table 2 shows the effectiveness of our dynamic attention memory network as the prediction layer. outperforms the other three pooling methods as well as the simple attention mechanism for all representation architectures. Sum, Mean, and Attention pooling all

---

Under review as a conference paper at ICLR 2020
1200
1200
1200
conntnngpredlicsi Sampoii
900
900
ountinggrdictoo
conntng
600
600
400
300
300-
300-
10090
20000 30000 exumplc id
20000
50009
commple, id
example
(a) CNN
MaxPool
(b) CNN + DIAMNet
(c) RGCN-SUM DIAMNet
Figure 5: Model behaviors of three models in small dataset. The x-axis is the example id and the y-axis is the count value. We mark the ground truth value as orange + and the predictions as blue x. We use two green dashed lines to separate patterns into three blocks based on numbers of vertices (3,4, and 8). In each block, the examples are sorted based on the data graphs' sizes.
comparable with each other, because they all gather the global information of the pattern and graph representations. Prediction layer based on max pooling, however, performs the worst, and even worse when the representation layer is CNN or Transformer-X XL. This observation indicates that every context of the pattern representation should be counted and we need a better way to compute the weights between each context. The dynamic attention memory with global information of both the pattern and the graph achieves the best results in most of the cases. One of the most interesting observations is that it can even help extract the context of pattern and graph while the representation layer (such as CNN) does not perform very well, which proves the power of our proposed method of DIAMNet.
Performance on larger graphs. Table 3 shows our models can be applied to larger-scale graphs. For the large dataset, we only choose the best pooling method for each of the baselines to report. We can find most of the results are consistent to the small dataset, which means RGCN is the best representation method in task and the dynamic memory is effective. In terms of the running time, all learning based models are much faster than the traditional VF2 algorithm for subgraph isomorphism counting.
Model behaviors. As shown in Figure 5 we compare the model behaviors of the best model (RGCN+SUM) and the worst model (CNN), as well as the great improvement of CNN when memory is added. We can find that CNN+SumPool tends to predict the count value below 400 and has the same behavior between three patterns. This results may come from the fact that CNN can only extract local information of sequence and Sum pooling is not a good way to aggregate it. However, the memory can memorize local information to each memory cell so can improve the representation power of CNN and can gain better performance. RGCN, better represent the graph structure, so it achieves a better result, especially on the largest pattern (the third block of each figure) compared with CNN. More results can be found in Appendix F
the other hand, can
CONCLUSIONS
In this paper, study the challenging subgraph isomorphism counting problem. With the help of deep graph representation learning, we are able to convert the NP-complete problem to a learning based problem. Then we can use the learned model to predict the subgraph isomorphism counts in polynomial time. Counting problem is more related to a global inference rather than only learn- ing node or edge representations. Therefore, have developed a dynamic intermedium attention memory network to memorize local information and summarize for the global output. We build two datasets to evaluate different representation learning models and global inference models. Results show that learning based method is a promising direction for subgraph isomorphism detection and counting and memory networks indeed help the global inference. We also performed detailed ana- lysis of model behaviors for different pattern and graph sizes and labels. Results show that there is much space to improve when the vertex label size large. Moreover, we have seen the potential real-world applications of subgraph isomorphism counting problems such question answering and information retrieval. It would be very interesting to see the domain adaptation power of our developed pretrained models on more real-world applications.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and Süleyman Cenk Sahin- alp. Biomolecular network motif counting and discovery by color coding. ISMB, pp. 241-2491 2008.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, 2015.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1 806.01261, 2018.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In ICML, pp. 41 41-48, 2009.
Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. Challenging the time com- plexity of exact subgraph isomorphism for huge and dense graphs with VF3. IEEE Trans. Pattern Anal. Mach. Intell., 40(4):804 818, 2018.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NeurlPS, 2019.
Kyunghyun Cho, Bart van Merrienhoer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In EMNLP, pp. 1724-1734, 2014.
Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell., 167011113 2004.
Zihang Dai, Zhilin Yang. Yiming Yang, Jaime G. Carbonell, Quoe Viet Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In ACL, pp. 2978-2988, 2019.
Michele Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph do- mains. IJCNN, 2:729-734, 2005.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gomez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, Adrià Puigdomênech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626): 471 2016.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning networks. SIGKDD, pp. 855-864, 2016.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 2017a.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017b.
Wook-Shin Han, Jinsoo Lee, and Jeong- Hoon Lee. Turbo towards ultrafast and robust subgraph isomorphism search in large graph databases. In SIGMOD, pp. 337-348, 2013.
Huahai He and Ambuj K. Singh. Graphs-at-a query language and access methods for graph databases. In SIGMOD, pp. 405-418, 2008.
11

---

Under review as a conference paper at ICLR 2020
Jun Huan, Wei Wang, and Jan F. Prins. Efficient mining of frequent subgraphs in the presence of isomorphism. In ICDM, pp. 349-552, 2003.
Yoon Kim. Convolutional neural networks for sentence classification. In EMNLP, pp. 1746-1751 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Ankit Kumar, Ozan Irsoy, Peter Ondruska, Mohit lyyer, James Bradbury, Ishaan Gulrajani, Victor Zhong, Romain Paulus, and Richard Socher. Ask me anything: Dynamic memory networks for natural language processing. In ICML, pp. 1378-1387, 2016.
Michihiro Kuramochi and George Karypis. GREW-A scalable frequent subgraph discovery al- gorithm. In ICDM, pp. 439-442, 2004.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In ICLR, 2016.
R. Milo, S. Shen-Om, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-888 827, October 2002.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In ICML, pp. 2014-2023, 2016.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representa- tions. In SIGKDD, pp. 701-710, 2014.
Franco Scarselli, Sweah Liang Yong. Marco Gori, Markus Hagenbuchner, Ah Chung Tsoi, and Marco Maggini. Graph neural networks for ranking web pages. In Web Intelligence, pp. 666- 672. IEEE Computer Society, 2005.
Michael Sejr Schlichtkrull, Thomas N. Kipf. Peter Bloem, Rianne van den Berg. Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. The Semantic Web International Conference, ESWC, pp. 593-607, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kemels.. J. Mach. Learn. Res., 12:2539-2561, 2011.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In NIPS, pp. 2440-2448, 2015.
Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li. Efficient subgraph matching on billion node graphs. PVLDB, 5(9):788-799, 2012.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang. Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding. In WWW, pp. 1067-1077, 2015.
Matteo Togninalli, M. Elisabetta Ghisu, Felipe Lópeezes-López, Bastian Rieck, and Karsten M. Borgwardt. Wasserstein weisfeiler-lehman graph kernels. In NewrlPS, 2019.
Julian R. Ullmann. An algorithm for subgraph isomorphism. J. ACM, 23(1):31 42, 1976.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NIPS, pp.
2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. J. Mach. Learn. Res., 1:1201-1242, 2010.
Keyulu Xu. Weihua Hu. Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
12

---

Under review as a conference paper at ICLR 2020
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In ICDM, pp. 721- 724, 2002.
Xifeng Yan, Philip S. Yu, and Jiawei Han. Graph indexing: A frequent structure-based approach. In SIGMOD, pp. 335-346, 2004.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In KDD, pp. 1365-1374. ACM, 2015.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrmn: Generating realistic graphs with deep auto-regressive models. In ICML, pp. 5694-5703, 2018.
13

---

Under review as a conference paper at ICLR 2020
A
LEXICOGRAPHIC ORDER OF CODES
The lexicographic order is a linear order defined as follows:
If A (og: "1."." amm) and B (Do- .,. b,)) the codes, then A B iff either of the following is true:
31, S min(m, n), 1, ag = bbs ar th Dt.
2. 44 S m, og bb: and n 2 m.
In our setting, 0; (Ner Va, K(var) You ((aa)) Ke bj (ub, Ub, X(ub,)), yb,, ((v,,) iff one of the following is true:
1. Un: < "Bb
2. Uo. Ub, Un; < Ub,"
3. Va: Ub, Va. Ub Yas Yby-
B PATTERN GENERATOR AND GRAPH GENERATOR
As proposed in Section 5.1 two generators required to generate datasets. The algorithm about the pattern generator shown in Algorithm | The algorithm first uniformly generates a directed tree. Then it adds the remaining edges with random labels. Vertex labels and edge labels also uniformly generated but each label is required to appear at least once. Algorithm226 Shoows the process of graph generation. Two hyperparameters control the density of subisomorphisms: decides the probability of adding subisomorphisms rather than random edges; (2) B E N is the parameter Dirichlet distribution sample sizes of components. After generating several directed trees and satisfying the vertex number requirement, the algorithm starts to add remaining edges. It can add edges in one component and try to add subgraph isomorphisms, or it can randomly add edges between two components or in one component. The following merge subroutine aims to merge these components into large graph. Shuffling is also required to make datasets hard to be hacked. The search of subisomorphisms in the whole graph is equivalent to the search in components respectively because edges between any two components do not satisfy the necessary conditions.
[0, 1]
Algorithm Pattern Generator.
Input: the number of vertices N,, the number of edges No, the number of vertex labels Ly, the number of edge labels Le-
P GenertieDiretteeTTre(((...
2: AssignNodessLaeelss L.)
3: AddRandomFdges(P P, rull, No N₂ 1)
4: ShignEdgesLabbls((" La)
Output: the generated pattern P
In Algorithm and Algorithm 2 the function AddRandomEdges adds required edges from one component to the other without generating new subgraph isomorphisms. The two component can also be the same one, which means to add in one component. The NEC tree is utilized Tur- bolSO (Han et al. 2013) to explore the candidate region for further matching. It takes O()), time but can significant reduce the searching space the data graph. records the equivalence classes and necessary conditions of the pattern. We make sure edges between two components dis- satisfy necessary conditions in the NEC tree when adding random edges between them. This data structure and this idea help to generate more data and search subisomorphisms compared with random generation and traditional subgraph isomorphism searching.
C DETAILS OF DATASETS
We can generate as many examples as possible using two graph generators. However, we limit the numbers of training, dev, and test examples whether learning based models generalize to
14

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Graph Generator.
Input: pattern P, the number of vertices No. the number of edges Ne, the number of vertex labels L., the number of edge labels Le, hyperparameters a and
1: Ns DrrichletSamplingNN. ()
2: Gs =0
3: de :
4: for each v. in N' do
5:
GenteratDirrccte(Teeee))) AssignNodessLabels/ n)
6:
7:
AssignEdgesLabelsgg
8:
Gs 9 {g}
9:
d=:
10: end for
Tp RewriteNECTree(P)
12: Ne.P := EdgeCount(P)
13: while de > do
14:
91. 92- = RandomPick(Gss. 2)
Pick two components randomly
15:
r= R=RndomNuum(,, 1)
16:
if de < Ne, then
17:
de == de AdddRandomEdgessqq, 92, Tp. de)
Add de edges between Ø1 and Ø2
18:
else
19:
r < a then
de = de AddPattems((g,. P)
> Add necessary edges 9i add patterns
21: else
de = de AddRandomEdgessgn, 92. Tp. Ne,P)
23:
end if
end if
25: end while
26: G. f == MergeComponents((aa))
f is the graph id mapping f' is the shuffled graph id mapping
27: G. f = ShuffleGraph(()
28: Is == 0 0
29: for each g in Gs do
30: Is := Sew.erreaaasssnneeeeeeee SeeerhhSSublommrhhsnnnsg. P)
31: for each / in Is do
32:
1 : Updateel(DDL. f.
33:
Is Is + (1}
34:
end for
end for
Output: the generated graph G, the subgraph isomorphisms Is
new unseen examples. Pattern and data graphs in different scales have been generated. Parameters for two generators and constraints are listed in Table 4 Two constraints are added to make this task easier. The average degree constraint N- N. < 4) is used to keep graphs not so dense, and the
subisomorphism counting constraints (fc E Níc < 1024) for small, (c N/c < 4096) for large)
ensure the difficulty of two datasets are different.
We use server with an 8-core Intel E5-2620v4 CPU (16 threads) and 512GB RAM to generate and record running time parallel. The distributions of countings two datasets are shown in Figure From the figure we can see that both datasets follow the long tail distributions.
D MORE IMPLEMENTATION DETAILS
In this section, we provide more implementation details other than the representation architectures and the DIAMNet modules.
15

---

Under review as a conference paper at ICLR 2020
Table 4: Parameters and constraints for datasets
Hyperparameters
small
large
N₂
[3, 4, 8
3. 16
Pattern
No
2, 4,4,85
2, 4,
8, 16
L
{2, 4, 8
[2 4, 16
Le
{2, 4,
{2. 4, 8. 16]
N.
{8, 16, 32, 64)
{64, 128, 256, 512]
Ne
{8. 16, ...,,.... 256}
(64, 128, ..., 2.048)
Graph
L
8, 16)
{16, 32, 64)
Le
(4 16)
{16, 32, 64)
{0.1, 0.2, .... 0.8}
{0.05, 0.1, 0.15} {512)
{512)
10
10*
number of counting
number counting
10a
10'
10a
10a
10'
10'
10
10
10
10
10
10²
10
10'
10
10"
counting
counting
(a) Test data distribution of the small dataset.
(b) Test data distribution of the large dataset.
Figure 6: Subgraph isomorphism counting distributions of two datasets.
D.1 FILTER NETWORK
Intuitively, not all vertices and edges in graphs can match certain subisomorphisms so we simply add FilterNet adjust graph encoding as follows:
MazPool(P))
(7)
G GW
(8)
f: = (Wr 0
(9)
G. f:O Gi,
(10)
where G is the graph representation in the pattern space, o is the sigmoid function, fi is the gate that decides to filter the jth vertex the jrh edge, Wo xd,, and WF Ix,,, trainable. Thanks to the multi-hot encoding, We can simply use Eq. (7) to accumulate label information of pat- terns. After this filter layer, only relevant parts of the graphs will be passed the next representation layer.
D.2 ATTNPOOL
The computation process of the AttnPool (Mean) is:
p MeanPool(P),
(11)
g MultiHeaddpp G.G).
(12)
Combing with the pooling strategy to make P as P Rixd, the time complexity is decreased to O(Dr] (Vol) O O(Erl E.l). We also implement three variants with sum-pooling, mean-
16

---

Under review as a conference paper at ICLR 2020
pooling, and max- max-pooling respectively. Results of AttnPool (Sum) and AttPPool (Max) are shown in the Appendix E
D.3 DIAMNET INITIALIZATION
There are many ways to initialize the memory {ml ..... tialize m, (0)
,'. mm ). experiments, we simply ini-
by
VVal
8
M l.
(13)
k = VVll - (M - 1),
(14)
m (0)
Meam ((Gre -ra+k-IH),
(15)
where 8 is the stride and & is the kernel size. In Table we compared two additional pooling
methods with MeanPool in Eq. 15
Table 5: Detailed results of different models with different predict networks on the small dataset.
Test Lazo
Models
RMSE
MAE
Paro
Razro
Pozzzzo
Ramaze
Eecuscro
SumPool
55,429
11.057
0.997
0.678
0.807
0.249
0.980
0.397
McanPool
0.999
0.312
0.995
MaxPool
47.353
11.212
0.993
0.715
0.832
0.372
0.973
0.539
AttnPool (Sum)
57,800
15.642
0.753
0.747
0.655
CNN
AttnPool (Mean)
55.963
12.717
0.991
0.665
0.796
0.207
0.937
0,340
AltnPool (Max)
57.102
11.196
0,989
0.682
0.807
0.267
0.936
0.416
DIAMNet (SumInit)
43.312
10.284
0.900
0.871
0.885
0.789
0.833
0,810
DIAMNet (MeanInit)
34.448
6.953
0.980
0. 80805
0.884
0.623
0.952
0.753
DIAMNel (MaxInit)
35,055
7.188
0,980
0.617
0,951
SunPooo
29.955
5,740
0.979
0.846
0,908
0.717
0.956
0.819
MeanPool
31.010
6.447
0.971
0.859
0.912
0.746
0.942
0.833
MaxPaol
30.824
6.236
0.994
0.771
0.869
0.532
0.982
0.690
AttnPoal (Sum)
32.481
6,262
0.977
0.853
0.911
0.733
0.953
0.829
RNN
AttaPool (Mean)
31.857
0.985
0. 0.827
0.899
0.672
0.793
AttaPool (Max)
41.186
11.011
0.948
0.888
0.917
0.811
0.908
0.857
DIAMNet (Sominit)
29.682
5.632
0.925
0.949
0.937
0.921
0.885
0.903
DIAMNet (MeanInit)
29.743
5,547
0.948
0.907
0.927
0.846
0.911
0,877
DIAMNet (MaxInit)
29.778
5,827
0.951
0.926
0.938
0.879
0.919
0.899
SumPool
34,391
7,042
0.976
0.833
0.690
0.947
MeanPool
32.569
6.656
0.972
D. 0.808
0.882
0.632
0.935
0.754
MaxPool
30.289
0.406
0.965
0.977
0.509
AttaPool (Sum)
55.166
12.748
0.870
0.832
0.851
0.721
0.778
0.748
TXL.
AttPooal (Mean)
37.721
7.426
0.965
0.790
0.869
0.592
0.914
0.719
AttnPool (Max)
60.196
18.916
0.529
0.
0.664
0.898
0.545
0.679
DIAMNer (SumInit)
32.659
6,904
0.907
0. 0.940
0.923
0.908
0.861
0.884
DIAMNet (Meantnat)
DIAMNet (MaxInit)
37,877
8,317
0.914
0.884
0.899
0.810
0.856
0.832
SumPool
32.414
6.578
0.984
0.5 0.829
0.900
0.677
0.965
0.796
McanPool
33,829
7.152
0.795
0.878
0.599
0.951
0.735
MaxPool
50,851
9,707
0.982
0.780
0.869
0.559
0.952
0.704
AttnPool (Sum)
0.991
0.977
RGCN
AtnPoaa (Mean)
32.526
6,523
0.994
0.774
0.870
0.540
0.982
0.697
AttnPool (Max)
42.970
8,850
0.964
0.
0.902
0.724
0.928
0.813
DIAMNet (Sumlnit)
29.459
5.688
0.964
0.871
0.915
0.772
0.931
0.844
DIAMNet (MeanInit)
28.712
5.782
0.924
0.912
0.918
0.859
0.877
0.868
DIAMNet (MaxInit)
29.345
5,501
0.937
0.918
0.927
0.866
0. 0.896
0,881
SumPool
22.379
3.958
0.988
0.860
0.920
0.746
0.974
0.845
McanPool
22.483
4.254
0.987
0.
0.903
0.685
0.971
0.803
MaxPool
42.434
7,900
0.994
0.780
0.874
0.554
0.984
0.709
AttnPoal (Sum)
23,214
4.149
0.992
0.830
0.904
0.679
0.981
0.802
RGCN-SUM AttPProl (Mean)
24.875
5.131
0.998
0.725
0.840
0.399
0.991
0.569
AttaPool (Max)
35.037
6,845
0.987
0.794
0.880
0.593
0.967
0.735
DIAMNet (SumInit)
0.962
0.803
0.930
DIAMNet (MeanInit)
21.734
3,853
0.964
0.887
0.924
0.504
0.934
0.864
DIAMNet (MaxInit)
23,940
4.156
0.966
0. 0.882
0.922
0.794
0.937
0.860
7em
67.195
13.716
1.0
0.614
0.761
0.0
0.0
0.0
Avg
65.780
21,986
0.0
0.0
0.0
1.0
0.386
0.557
VF2
0.0
0.0
1.0
1.0
1.0
1.0
1.0
1.0
17

---

Under review as a conference paper at ICLR 2020
E DETAILED RESULTS OF DIFFERENT PREDICTNETS
Simple pooling, attention based pooing, and attention with memory can be used to fuse pattern and graph representations in our framework. AttnPool (Sum) and AttnPool (Max) can be regarded as two variants of AttnPool (Mean) by replacing pooling methods. Table [5 shows results of different representation models with different interaction networks in the small dataset. AttnPool (Mean) and DIAMNet (MeanInit) usually perform better compared with other pooling methods.
F FURTHER DISCUSSIONS
As shown in Figure 7 different interaction modules perform differently in different views. We can find MaxPool always predicts higher counting values when the pattern small and the graph is large, while AttnPool always predicts very small numbers except when the pattern vertex size is 8, and the graph vertex size 64. The same result appears when we use edge sizes as the x-axis. This observation shows that AttnPool has difficulties predicting counting values when either of the pattern and the graph is small. shows that attention focuses more on the zero vector we added rather than the pattern pooling result. Our DIAMNet, however, performs the best in all pattern/gran When the bins are ordered by vertex label sizes or edge label sizes, the performance of all the three interaction modules among the distribution similar. When bins ordered by vertex label sizes, we have the same discovery that AttnPool prefers to predict zeros when then patterns are small. MaxPool fails when facing complex patterns with more vertex labels. DIAMNet also performs not so good over these patterns. As for edge labels, results look good for MaxPool and DIAMNet but AttnPool is not satisfactory.
sizes.
As shown in Figure different representation modules perform differently in different views. CNN performs badly when the graph size is large (shown in Figure Sa and (d) and patterns become complicated (show in Figure and [j] which further indicates that CNN can only extract the local information and suffers from issues when global information need in larger graphs. RNN, on the other hand, performs worse when the graph are large, especially when patterns are small (show in Figure Se). which consistent with its nature, intuitively. On the contrary. RGCN-SUM with DeAMNet is not affected by the edge sizes because it directly learns vertex representations rather than edge representations.
18

---

Under review as a conference paper at ICLR 2020
60
mergge cwnntnppredeetttt
averge orunting/peeetttte
85
30
30
0
(.. 16)
(3,30)
(8. 64)
(4.9)
(4.16)
(4.30)
(4, (4)
(8.9)
08, 16)
08 11-32)
0% 64)
01.50
16)
65 (2)
(4.3)
8.00
06.99
& 160
18. 16.33
0% 04)
03.50
13 1.300
(4.99
10:30
(5.9)
18, 30
veries Mee
paltenigrrah vertes
size
(a) Ov, MaxPool
(b) Ov, AttPPool
(c) Ov. DIAMNet
309
average conningjrrettttot
228
359
2500
250
patter graph
patteniggaaph edge
pattern graph edge
(d) Og, MaxPool
(c) Og, AttnPool
Oc. DIAMNet
40
38-
30-
vverage comnding
0.41
10
10
70)
10
pattern graph vertes label
patturnigrap graagggrpphhho vertux Iabel
pattern graph
vertes Jubel size
(g) Ox, MaxPool
(h) Ox, AttnPool
(i) Ox. DIAMNet
average wwntto
average cuntosgrreet
10
(K. 169
10
160
(4-0)
16)
20
100
(l, 10-
patteralgraph edge
pattero graph
pattern/graph edge
( Oy, MaxPool
(k) Oy, AttmPoo
Oy: DIAMNet
Figure 7: Model behaviors of three CNN based models on the small dataset. We compare MaxPool, AttnPool, and DIAMNet four different view settings. Here Oy means that on the x-axis the bins are ordered by the size of pattern/graph vertex, Og by the size of edge, Ox by the size of vertex label, and Oy by the size edge label. The orange color refers to the ground truth and the blue color refers to the predictions.
19

---

Under review as a conference paper at ICLR 2020
160
160
169
avcerge wwanggggoiiiiieereeeeee
80-
50
80-
(3 0..00
125
2001
3131
(4.13) 129
150)
513
I8 515
116 64
(16 120
0.000
1231
250
1L.113
150
515
I 150
513)
[1h 60
(16) 120
120
125)
13 150
51511
515
121
00.000
(16 125
(16 250
IM
(16,
patteraggrah
patheniggagh
patterngraph
(a) Ov, CNN
(h) Ov, RNN
(c) Oy, RGCN-SUM
1040
1100
1009
200
200
200
patternigraph odlge
palleernlgra eerren odge
pattersigraph edge
(d) Og. CNN
(e) Og. RNN
(I) Og. RGCN-SUM
160
160
Intragg coantingrredeet
120
1.0
320-
40-
10
(2. 531
(2. 641
10
33
64
1 10
(R 641
(16 13)
(16, (4)
331
100
(K 64
(16, 531
33
10
(10. 33)
12.
12.
pattemigragh vertas label sie
pattorn graph vurter lahil ebu
pattery graph vertex label size
(g) Oxx CNN
(h) Ox RNN
(i) Ox. RGCN-SUM
average portitt
KVEPAR comttingg www.ttigggeelleetteao prediictin
30
30
5
12. 10
(2. 33)
14. 10
12)
14. 60
10
IR 33)
64)
(16, t0
23
(16, 64)
12. 10
59
12. mI
90
1K 10 50
18 60
(16. 331
64)
(2. 10
22. 64
JR 10
IR 60
(16 32)
patteraigraph odge label size
patternggaah edge label dice
pattera/graph odge label size
Oy. CNN
(k) Oy. RNN
() Oy. RGCN-SUM
Figure Model behaviors of three models on the large dataset. We compare CNN, RNN, and RGCN-SUM with our DIAMNet in four different view settings. Here Oy means that on the x-axis the bins are ordered by the size pattern/graph vertex, Og by the size of edge, Ox by the size of vertex label, and Oy by the size of edge label. The orange color refers to the ground truth and the blue color refers to the predictions.
20


Reviews:
[{"review_id": "r1x1gwAcYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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. \n\nIn 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.\n\nRMSE 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).\n\nWhy 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.\n\nThe 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.\n\nMinor comment:\nAt the third line of Sec 3.2: '|V_G| is the number of pattern nodes' should be |V_P|.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SylbC532YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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'.\n\n1) 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'. \n\nAlso, 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. \n\n2) 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. \n\nAlso, 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. \n\n3) 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. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Hkeg_NnxoB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nAlthough 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. \n\nAlso, 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. \n\n[1]  A Neural Graph Isomorphism Algorithm Based on Local Invariants, ESANN'2003\n[2] Subgraph Isomorphism in Polynomial Time\n[3] FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling\n\nIn 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. \n\nFinally, 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. \n\nMinor comments:\n\n|V_G| is is the number of pattern nodes -> |V_p| is is the number of pattern nodes", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lIjMJPjr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nSince 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.\n\nThe 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.\n\nOne 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.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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