IsoNN: Isomorphic Neural Network for Graph Representation Learning and Classification
Authors: Lin Meng
Jiawei Zhang
Venue:  (2020)
Keywords: Deep Learning
Graph Neural Network

Abstract: Deep learning models have achieved huge success in numerous fields, such as computer vision and natural language processing. However, unlike such fields, it is hard to apply traditional deep learning models on the graph data due to the ‘node-orderless’ property. Normally, adjacency matrices will cast an artificial and random node-order on the graphs, which renders the performance of deep mod- els on graph classification tasks extremely erratic, and the representations learned by such models lack clear interpretability. To eliminate the unnecessary node- order constraint, we propose a novel model named Isomorphic Neural Network (ISONN), which learns the graph representation by extracting its isomorphic features via the graph matching between input graph and templates. ISONN has two main components: graph isomorphic feature extraction component and classification component. The graph isomorphic feature extraction component utilizes a set of subgraph templates as the kernel variables to learn the possible subgraph patterns existing in the input graph and then computes the isomorphic features. A set of permutation matrices is used in the component to break the node-order brought by the matrix representation. Three fully-connected layers are used as the classification component in ISONN. Extensive experiments are conducted on benchmark datasets, the experimental results can demonstrate the effectiveness of ISONN, especially compared with both classic and state-of-the-art graph classification methods.

Under review as a conference paper at ICLR 2020
ISONN: ISOMORPHIC NEURAL NETWORK FOR GRAPH REPRESENTATION LEARNING AND CLASSIFICATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Deep learning models have achieved huge success in numerous fields, such computer vision and natural language processing. However, unlike such fields, it is hard to apply traditional deep learning models the graph data due the 'node-orderless' property. Normally, adjacency matrices will cast an artificial and random node-order the graphs, which renders the performance of deep mod- els on graph classification tasks extremely erratic, and the representations learned by such models lack clear interpretability. To eliminate the unnecessary node- order constraint, we propose novel model named Isomorphic Neural Network (IsoNN), which learns the graph representation by extracting its isomorphic fea- tures via the graph matching between input graph and templates. ISONN has two main components: graph isomorphic feature extraction component and classifi- cation component. The graph isomorphic feature extraction component utilizes a set of subgraph templates as the kernel variables to learn the possible subgraph patterns existing in the input graph and then computes the isomorphic features. A set of permutation matrices is used the component to break the node-order brought by the matrix representation. Three fully-connected layers are used the classification component in ISONN. Extensive experiments are conducted on benchmark datasets, the experimental results demonstrate the effectiveness of ISONN, especially compared with both classic and state-of-the the- graph classifi- cation methods.
INTRODUCTION
The graph structure attracting increasing interests because of its great representation power on various types of data. Researchers have done many analyses based on different types of graphs, such as social networks, brain networks and biological networks. In this paper, we will focus on the binary graph classification problem, which has extensive applications in the real world. For example, one may wish to identify the social community categories according to the users' social interactions (Gao al. 2017). distinguish the brain states of patients via their brain networks (Wang ctt al. 2017). and classify the functions of proteins in a biological interaction network (Hamilton al. 2017).
To address the graph classification task, many approaches have been proposed. One way to estimate the usefulness of subgraph features is feature evaluation criteria based on both labeled and unlabeled graphs (Kong & Yu 2010). Some other works also proposed to design pattern exploration approach based pattern co-occurrence and build the classification model (Jin et al.) 2009) or develop boosting algorithm (Wu et al., 2014). However, such works based on BFS or DFS cannot avoid computing a large quantity of possible subgraphs, which causes high computational complexity though the explicit subgraphs are maintained. Recently, deep learning models are also widely used to solve the graph-oriented problems. Although some deep models like MPNN (Gilmer et al. 2017) and GCN (Kipf & Welling (016) learn implicit structural features, the explict structural information cannot be maintained for further research. Besides, most existing works on graph classification use the aggregation of the node features in graphs as the graph representation (Xu et al.) 2018 Hamilton et al. 2017). but simply doing aggregation on the whole graph cannot capture the substructure precisely. While there other models capture the subgraphs, they often need more complex computation and mechanism (Wang et al. 20177; Narayanan et al.] (2017) or need additonal node labels to find the subgraph strcuture (Gaüzere et al. 2012 Shervashidze et al. 2011).

---

Under review as a conference paper at ICLR 2020
However, should notice that when we deal with the graph-structured data, different node-orders will result in very different adjacency matrix representations for most existing deep models which take the adjacency matrices as input if there is no other information on graph. Therefore, compared with the original graph, matrix naturally poses a redundant constraint on the graph node-order. Such node-order is usually unnecessary and manually defined. The different graph matrix represen- tations brought by the node-order differences may render the learning performance of the existing models to be extremely erratic and not robust. Formally, we summarize the encountered challenges in the graph classification problem as follows:
Explicit useful subgraph extraction. The existing works have proposed many discrimina- tive models to discover useful subgraphs for graph classification, and most of them require manual efforts. Nevertheless, how to select the contributing subgraphs automatically with- out any additional manual involvement is challenging problem.
Graph representation learning. Representing graphs in the vector space is an important task since it facilitates the storage, parallelism and the usage of machine learning models for the graph data. Extensive works have been done on node representations (Grover & [eskovee] 2016; 2016) Lin al,) 2015; Lai et al. [0177] Hamillon et al.) (017). whereas learning the representation of the whole graph with clear interpretability is still open problem
requiring more explorations.
Node-order elimination for subgraphs. Nodes in graphs are orderless, whereas the ma- trix representations of graphs cast an unnecessary order on nodes, which also renders the features extracted with the existing learning models, e.g., CNN, be useless for the graphs. For subgraphs. this problem also exists. Thus, how to break such a node-order constraint for subgraphs challenging.
Efficient matching for large subgraphs. To break the node-order, we will try all possible node permutations to find the best permutation for a subgraph. Clearly, trying all possible permutaions is combinatorial explosion problem, which is extremly time-comsuming for finding large subgraph templates. The problem shows that how to accelerate the proposed model for large subgraphs also needs to be solved.
In this paper, we propose a novel model, namely Isomorphic Neural Network (IsoNN) and its vari- ants, to address the aforementioned challenges in the graph representation learning and classification problem. IsONN is composed of two components: the graph isomorphic feature extraction compo- nent and the classification component, aiming at learning isomorphic features and classifying graph instances, respectively. In the graph isomorphic feature extraction component, ISONN automati- cally learns a group of subgraph templates of useful patterns from the input graph. ISONN makes use of set of permutation matrices, which act as the node isomorphism mappings between the templates and the input graph. With the potential isomorphic features learned by all the permutation matrices and the templates, ISONN adopts one min-pooling layer to find the best node permutation for each template and one softmax layer to normalize and fuse all subgraph features learned by dif- ferent kernels, respectively. Such features learned by different kernels will be fused together and fed as the input for the classification component. ISONN further adopts three fully-connected layers as the classification component to project the graph instances to their labels. Moreover, to accelerate the proposed model when dealing with large subgraphs, we also propose two variants of ISONN to gurantee the efficiency.
RELATED WORK
Our work relates to subgraph mining, graph neural networks, network embedding as well as graph classification. We will discuss them briefly in the followings.
Mining subgraph features from graph data has been studied for many years. The aim is extract useful subgraph features from a set of graphs by adopting some specific criteria. One classic unsupervised method (i.e., without label information) is gSpan Yan & Han 2002). which builds lexicographic order among graphs and map each graph to unique minimum DFS code as its canonical label. GRAMI (Elseidy et al. 2014) only stores templates of frequent subgraphs and treat the frequency evaluation as a constraint satisfaction prob- lem to find the minimal set. For the supervised model (i.c., with label information). CORK utilizes labels to guide the feature selection, where the features are generated by gSpan (Thoma et al. 2009). Due to the mature development of the sub-graph mining field, subgraph mining methods have also
Subgraph Mining and Graph Kernel Methods:
2

---

Under review as a conference paper at ICLR 2020
been adopted in life sciences (Mrzic al. 2018). 8). Moreover, several parallel computing based meth- 2014) have proposed to reduce the time cost. On the other hand, graph kernel methods are also applied to discover the subgraph structures (Kashimal et al. 2003) Vishwanathan et al., 2010 Gaüzere et al. 2012 Shervashidze et al.] 2011). Among them, most existing works focus on the graph with node labels and the kerness methods only com- putes the similarity between pairwise graphs. Yet, in this paper, we are handling the graph without node labels. Moreover, we can not only compute the similarity between pairwise graphs but also learn subgraph templates, which can be further analyzed.
ods (Qiao et al. 2018: Hill et al. 2012; Lin et al.
Graph Neural Network and Network Embedding: Graph Neural Networks (Monti et al., 2017 Atwood & Towsley [016]] Masci et al. 2015; Kipf & Welling, 2016 Battaglia et al.] (0188) have been studied in recent years because of the prosperity of deep learning. Traditional deep models cannot be directly applied to graphs due to the special data structure. The general graph neural model MoNet (Monti et al., 2017) employs CNN architectures on non-Euclidean domains such as graphs and manifold. The GCN proposed in (Kipf & Welling, 2016) utilizes the normalized adja- cency matrix to learn the node features for node classification; Bai et al. 2018) proposes the multi- scale convolutional model for pairwise graph similarity with set matching based graph similarity computation. However, these existing works based on graph neural networks all fail to investigate the node-orderless property of the graph data and maintain the explicit structural information. Another important topic related to this paper is network emhedding (Bordes et al., 2013] Lin et al.) et al. 2018 Hamilton al., (017). which aims at learning the feature representation of each individual node in a network based on either the network structure or attribute information. Distinct from these network embedding works, the graph representation learning problem studied in this paper treats each graph as an individual instance and focuses on learning the representation of the whole graph instead.
2015 Lai et al., 2017:
Graph classification is an important problem with many practical appli- cations. Data like social networks, chemical compounds, brain networks can be represented as graphs naturally and they can have applications such as community detection (Zhang et al.) 2018), anti-cancer activity identification (Kong et al., 2013: Kong & Yu 2010) and Alzheimer's s patients diagnosis (Tong et al. 2017| 2015) respectively. Traditionally, researchers mine the subgraphs by DFS or BFS (Saigo et al.J 2009 Kong et al., 2013), and use them as the features. With the rapid development of deep learning (DL), many works are done based DL methods. GAM builds the model by RNN with self-ateention mechanism (Lee et al. 2018). DCNN extend CNN to gen- eral graph-structured data by introducing cdiffusion-coovvluuioon operation (Atwood & Towsley 2016).
Graph Classification:
3 TERMINOLOGY AND PROBLEM DEFINITION
In this section, we will define the notations and the terminologies used in this paper and give the formulation for the graph classification problem.
3.1 NOTATIONS
In the following sections, we will use lower case letters like x to denote scalars, lower case bold letters (e.g. x) to represent vectors, bold-face capital letters (e.g. X) to show the matrices. For tensors or sets, capital calligraphic letters are used to denote them. We use x; to represent the i-th element in x. Given a matrix X, we use X(i,j) to express the element in i-th row and j-th column. For i-th row vector and j-th column vector, we use X(i.:) :) and X(:j) to denote respectively. Moreover, notations x7 and X denote the transpose of vector x and matrix X respectively. Besides, the Forom of matrix X can be represented || r
(E.s 1
3.2 PROBLEM FORMULATION
Many woal-world inter-connected data can be formally represented as the graph-structured data.
DEFINITION (Graph): Formally, a graph can be represented as G (V,E), where the sets V and ε denote the nodes and links involved in the graph, respectively.
Some representative examples include the human brain graphs (where the nodes denote brain regions and links represent the correlations among these regions), biological molecule graphs (with the nodes represent the atoms and links denote the atomic bonds), as well as the geographical graphs in the offline world (where the nodes denote the communities and the links represent the commute
3

---

Under review as a conference paper at ICLR 2020
Input
Sub-graph Templates
Isomorphic Features
Diagnosis Result
Graph Isomorphic Layer
Min-pooting Layer
Softmax Layer
Fully Cornected Layers
DSH
Paalfty Soie
Emin
Graph Isomorphic Feature Extraction
Classification
Figure IsoNN Framework Architecture. (The left subplot provides the outline of the proposed framework, including the graph isomorphic feature extraction component and the classification component respectively. Meanwhile, the right subplot illustrates the detailed architecture of the proposed framework, where the graph isomorphic features are extracted with the graph isomorphic layer, min-pot pooling layer and softmax layer, and the graphs are further classified with three fully- connected layers.)
feature
routes among communities). Meanwhile, many concrete real-world application problems, e.g., brain graph based patient disease diagnosis, molecule function classification and community vibrancy prediction can also be formulated as the graph classification problems.
Problem Definition: Formally, given a graph set = {G1, G2, , with a small number of labeled graph instances, the graph classification problem aims at learning a mapping, i.e., f - V. to project each graph instance into a pre-defined label space y = (+1.-1}.
In this paper, we will take the graph binary classification as an example to illustrate the problem setting for ISONN. A simple extension of the model can be applied to handle more complicated learning scenarios with multi-class multi-label as well.
4 PROPOSED METHOD
The overall architecture of ISONN is shown in Figure I The ISONN framework includes two main components: graph isomorphic feature extraction component and classification component. The graph isomorphic feature extraction component includes a graph isomorphic layer. a min- pooling layer well as softmax layer and the classification component is composed by three fully-connected layers. They will be discussed in detail in the following subsections.
4.1 GRAPH ISOMORPHIC FEATURE EXTRACTION COMPONENT
Graph isomorphic feature extraction component targets at learning the graph features. To achieve that objective, ISONN adopts an automatic feature extraction strategy for graph representation learn- ing. In ISONN, one graph isomorphic feature extraction component involves three layers: the graph isomorphic layer, the min-pooling layer and the softmax layer. In addition, we can further construct a deep graph isomorphic neural network by applying multiple isomorphic feature extraction com- ponents on top of each other, i.e., apply the combination of "graph isomorphic layer, min pooling layer, softmax layer" several times. For the second and latter components, they will be used on every feature matrix learned by the combination of channels of all former components.
4.1.1 GRAPH ISOMORPHIC LAYER
Graph isomorphic layer is the first effective layer in deep learning that handles the node-order striction in graph representations. Assume we have a graph G = (V, 8}. and its adjacency matrix to be A E R In order to find the existence of specific subgraph patterns in the input graph, ISONN matches the input graph with set of subgraph templates. Fach template is denoted kernel variable K; E R Vi E (1,2, ,c,- Here, & denotes the node number in subgraphs and is the channel number (i.e., total template count). Meanwhile, match one template with regions in the input graph (i.e., sub-matrices in A), we use set of permutation matrices, which map both rows and columns of the kernel variable the subgraphs effectively. The permutation matrix can be represented as P E {0. k that shares the same dimension with the kernel variable. Therefore, given a kernel K; and a sub-matrix M(e.t) E x in A (i.e., a region in the input graph and s,t E 21,2,-- (DV) k k 1)} denotes a starting index pair in A), there may exist k! different such permutation matrices. The optimal should be the matrix P that minimizes the following term.
p'
arg min PK.PT Mss.)).
PEP
4

---

Under review as a conference paper at ICLR 2020
P2. }kt} covers all the potential permutation matrices. Formally, the iso- morphic feature extracted based on the kernel K; for the regional sub-matrix Ms.t)) in A can be represented
where p
(o = IP'K Mo.oll min PK,P" - -M..oll
(2)
= min (2.,0) (s.0) (1 k!)),
where vector Zz.is.)) E Rtl contains entry (. -M p Vj
- (M.
21, k!] denoting the isomorphic features computed by the j-th permutation matrix P, EpEr P.
As indicated by the Figure 1 IsONN computes the final isomorphic features for the kernel variable K; via two steps: (1) computing all the potential isomorphic features via different permutation matrices with the graph isomorphic layer, and (2) identifying and fusing the optimal features with the min-pooli min-pooling layer and softmax layer to be introduced as follows. By shifting one kernel matrix K; regional sub-matrices, ISONN extracts the isomorphic features the matrix A, which can be denoted as a 3-way tensor 2, E (BV-<(VV)-+1)))((V In a similar way, we can also compute the isomorphic feature tensors based on the other kernels, which can be denoted Z1, Zz, Ze respectively.
where (1 k!. t) = (e.().)) (1: k!).
4.1.2 MIN-POOLING LAYER
Given the tensor 2, computed by K, in the graph isomorphic layer. ISONN will identify the optimal permutation matrices via the min-pooling layer. Formally, we can represent results of the optimal permutation selection with 2, as matrix Ze
(3) The min-pooling layer learns the optimal matrix Z, for kernel K, along the first dimension (i.c., the dimension indexed by different permutation matrices), which can effectively identify the isomorphic features created by the optimal permutation matrices. For the remaining kernel matrices, we can also achieve their corresponding graph isomorphic feature matrices as Z, Zz. ... Ze respectively.
(s, t) min 2, s,)).
4.1.3 SOFTMAX LAYER
Based on the above descriptions, perfect matching between the subgraph templates with the input graph will lead to a very small isomorphic feature, e.g., value approaching to 0. If we feed the small features into the classification component, the useful information will vanish and the relative useless
information (i.e., features learned by the subgraphs dismatch the kernels) dominates the learning feature vector the end. Meanwhile, the feature values computed Equation (3) can also be in different scales for different kernels. To effectively normalize these features, we propose to apply the softmax function to matrices Z1, Zz. Ze across all kernels. Compared with the raw features, e.g., Z, softmax rescaling them to relatively larger values especially compared with the useless ones. Formally, we represent the fused graph isomorphic features after rescaling by all the kernels 3-way tensor Q, where slices along first dimension can be denoted as:
non-linear mapping can also effectively highlight the useful features in Z; by
Q(i,:::) 2: where 2, softmarl - Z,), Vi E (1,...,c).
(4)
4.2 CLASSIFICATION COMPONENT
After the isomorphic feature tensor Q is obtained, feed it into classification component. Let denote the flattened vector representation of feature tensor Q. and we pass it to three fully-connected layers get the predicted label vector For the graph binary classification, suppose we have the ground truth y = (v" yg) and the predicted label vector 3 (fi 12 for the sample g from the training batch set B. We use cross-entropy as the loss function ISONN, Formally, the fully- connected (FC) layers and the objective function can be represented as follows respectively:
{
di (Wiqq + b));
2
FC Layers:
d, a (W,d, + bg), y (W3d2 + ba).
Objective Function: -=
ΣV
Σ
3 log 0), (5)
9EB j=1
where W; and b, represent the weights and biases in i-th layer respectively for i E {1, 2, The a denotes the adopted the relu activation function. To train the proposed model, we adopt the back propagation algorithm to learn both the subgraph templates and the other involved variables.
5

---

Under review as a conference paper at ICLR 2020
4.3 MORE DISCUSSIONS ON GRAPH ISOMORPHIC FEATURE EXTRACTION ISONN
Before introducing the empirical experiments to test the effectiveness of ISONN, we would like to provide more discussions about the computation time complexity of the graph isomorphic feature extraction component involved in ISONN. Formally, given the input graph G with n = [V] nodes, by shifting the kernel variables (of size k k) among the dimensions of the corresponding graph adjacency matrix, we will be able to obtain (n-k+1)² regional sub-matrices (or (nn)) regional sub- matrices for notation simplicity). Here, we assume IsONN has only one isomorphic layer involving different kernels. In the forward propagation, the introduced time cost in computing the graph isomorphic features can be denoted as (cck!>"n²) where term k! is introduced in enumerating all the potential permutation matrices and k corresponds to the matrix multiplication time cost.
According to the notation, we observe that n is fixed for the input graph. Once the kernel channel number is decided, the time cost notation will be mainly dominated by k. To lower down the above time complexity notation, in this part, we propose to further improve IsONN from two per- spectives: (I) compute the optimal permutation matrix in faster manner, and (2) use deeper model architectures with small-sized kernels.
4.3.1 FAST PERMUTATION MATRIX COMPUTATION
Instead of enumerating all the permutation matrices in the graph isomorphic feature extraction as indicated by Equations 33 here introduce fast way compute the optimal permutation matrix for the provided kernel variable matrix, e.g., K;, and input regional sub-matrix, ((s.)) directly according to the following theorem.
THEOREM 1 Formally, let the kernel variable K, and the input regional sub-matrix M(s.)) be k real symmetric matrices with is distinct eigenvalues on > 0r > ...... >> 0g and B1 > f2 > ... > Bk. respectively, and their eigendeconposition be represented by
K, = UK k, and (ss)) = U Moses Mans U UM...
M(n.))
(6)
where UK, and U Mi..) are orthogonal matrices of eigenvectors and Ak, diag(a;), AM diag(3,). The minimum of |PK,P" - Msss,) attained for the following P's:
P U MM,,, SUk;
sn)) where S E S {diag ,
1 or 1}.
The proof of the theorem will be provided in appendix. In computing the optimal permutation matrix P', trials of different S will be needed. Meanwhile, avoid such time costs, we introduce to take the upper bound value of U M SUK, K; as the approximated optimal permutation matrix instead, which together with the corresponding optimal feature 21,(s.t) can be denoted as follows:
P = (M.
|UK, and Zi,(0.) = |P'K(P') - M (s;111
(8)
where |-| denotes the absolute value operator and |UM | UM SUk, hold for VS e S.
By replacing Equations 22 (3 with Equation 7 we can compute the optimal graph isomorphic feature for the kernel K, and input regional sub-matrix M(..)) with much lower time cost. Fur- thermore, since the eigendecomposition time complexity of & x k matrix is O(R3), based on the above theorem, we will be able to lower down the total time cost in graph isomorphic feature extrac- tion to O(ck)n²)) which can be optimized with the method introduced in the following subsection.
4.3.2 DEEP GRAPH ISOMORPHIC FEATURE EXTRACTION
Since graph isomorphic layer is the main functional layer, we simply use multi-layer for short to denote the mutiple graph isomorphic feature extraction components (i.e., deep model). We also provide an example of deep model in appendix. Here, will illustrate the advantages of deep ISONN model with small-sized kernels compared against shallow ISONN model with large kernels. In Figure 2
we provide an example two IsoNN models with different model architectures
the left model has one single layer and 6 kernels, where the kernel size k- = 12;
the right model has two layers: layer involves kernels of size 3, and layer involves kernels of size 4.

---

Under review as a conference paper at ICLR 2020
1-layer sub-graph (kernel size: 12)
2-layer IsoNN
layer kernels, size
leyer 2
kemels, size
V. S
Figure 2: An Illustration of Deep Architecture of ISONN.
By comparing these two different models, we observe that they have identical representation learning capacity. However, the time cost in feature extraction introduced by the left model is much higher than that introduced by the right model, which can be denoted as (6(123))n² and ((2(39) Jn? + 3(4%) respectively.
Therefore, for the ISONN model, we tend to use small-sized kernels. Formally, according to the fast method provided in the previous part, given 1-layer IsONN model with e large kernels of size k. its graph isomorphic feature extraction time complexity can be denoted as Occk"n²). In- spired by Figure 2 without affecting the representation capacity, such model can be replaced by [ log3 J-layers deep IsoNN model instead, where each layer involves 2 ker- nels of size 3. The graph isomorphic feature extraction time complexity of the deep model will be O (max [log5].
loga - -2232n² (or O (Imax{ [log",, log" }) n²) for simplicity).
EXPERIMENTS
To evaluate the performance of ISONN, in this section, we will talk about the experimental settings well five benchmark datasets. Finally, will discuss the experimental results with parameter analyses on kernel size, channel number and time complexity.
5.1 EXPERIMENTAL. SETTINGS
In this subsection, we will use five real-world benchmark datasets: HIV-IMRI (Cao al. 2015a), HIV-DTI (Cao et al. 2015a), BP-MMRI (Cao et al. 2015b), MUTAG and PT Both HIV-fMRI and HIV-DTI have 56 positive instances and 21 negative instances. Also, graph instances in both of them are represented as 90 x 90 matrices (Cao et al., 2015a). BP-fMRI has 52 positive and 45 negative instances and each instance is presented by 82 x 82 matrix Cao al. (0155) MUTAG and PTC are two datasets which have been widely used in academia Xu et al. (2018) Shervashidze al. (201T). MUTAG has 125 positive and 63 negative graph instances with graph size 28 28. PTC is a relative large dataset, which has 152 positive and 192 negative graph instances with graph size 109 109. With these datasets, we first introduce the comparison methods used this paper and then talk about the experimental setups and the adopted evaluation metrics in detail.
5.1.1
COMPARISON METHODS
: The proposed method IsoNN uses a set of template variables as well as the permutation matrices to extract the isomorphic features and feed these features to the classification component. The variant model named IsoNN-fat uses the Equation to compute the optimal permutation matrices and other settings remain unchanged.
ISONN & IsoNN-fast:
Freq: The method uses the top-k frequent subgraphs as its features. This is also an unsu- pervised feature selection method based on frequency.
AE: We use the autoencoder model (AE) (Vincent et al. 2010) to get the features of graphs without label information. It is an unsupervised learning method, which learns the latent representations of connections in the graphs without considering the structural information.
CNN: It the convolutional model (Krizhevsky et 2012) learns the structural informa- tion within small regions of the whole graph. We adopt one convolution layer and three fully-connected layer be the classification module.
1 http:://lll-www......ddddommmmm www.w//wwww....ooooooo/o/o/aaaea

---

node label Under review as a conference paper at ICLR 2020
Table I: Classification Results of the Comparison Methods.
Methods
Dataset
Metric
Freq
AE
CNN
SDBN
WL
GCN
GIN
IsONN-fast
ISONN
Acc.
54.3
46.9
59.3
66.5
44.2
58.3
52.5
70.5
73.4
HIV-MMR
58.2
35.5
66.3
66.7
27.2
56.4
35.6
69.9
72.2
Acc.
64.6
62,4
54.3
65,9
47.1
57.7
55.1
60.1
67.5
HIV-DTI
63.9
0.0
55.7
65.6
48.4
54.4
53.6
61.9
68.3
Acc. 56,8
53.6
54.6
64.8
56.2
60.7
45.4
62.3
64.9
BP-IMRI
F1
57.6
69.5
52.8
63.7
58.8
61.2
42.3
63.2
69.7
Acc.
76.2
50.0
81.7
54.0
52.4
63.5
54.0
83.3
83.3
MUTAG
F1 76.9
66.7
82.3
66.7
49.9
61.9
66.7
83.6
83.0
Acc. 57.8
50.0
54.6
50.0
49.0
49.0
49.0
53.0
59.9
PTC
54.9
66.5
58.9
66.5
48.9
48.9
47.5
55.8
59.9
SDBN: A model proposed in (Wang et al., 2017). which reorders the nodes in the graph first and then feeds the reordered graph into an augmented CNN. In this way, not only learns the structural information but also tries to minimize the effect of the order constraint.
WL: WL (Shervashidze et al. 2011 is a classic algorithm to do the graph isomorphism test. For the graph classification, computes the similarity scores for test graphs and train graph. The mean of all similarity scores between each test graph and train graphs will be used to do the classification.
GCN: GCN is proposed in (Kipf & Welling 2016) use the adjacent matrix to learn the implicit structure information in graphs. Here, we use two graph convolutional layers to learn node features and then take the all nodes features the graph features. One fully- connected layer will be used as graph classification module.
GIN: GIN proposed in (Xu et al. 2018) can be used to do graph classification with node features. We adopt the same experimental setting GIN-O stated in (Xu et al. 2018).
5.1.2 EXPERIMENTAL SETUP AND EVALUATION METRICS
reliable, we partition the datasets into folds and then set the ratio of train/test according to 2 1, where two folds are treated as the training data and the remaining one the testing data. We select top-100 features for Freq as stated in (Wang al. 2017) with three layer MLP classifier, where the neuron numbers are 1024, 128, 2. For Auto-encoder, we apply the two-layer encoder and two-layer decoder. For the CNN, we apply the one convolutional layer with the size 5 x 5 x 50, max-pooling layer with kernel size 2 x 2, one gating relu layer as activation layer and we set parameters in the classification module the same as Freq classifier. For the SDBN, we set the architecture as follows: we use two layers of "convolution layer + max pooling layer + activation layer" and concatenate a fully connected layer with 100 neurons as well as activation layer, where the parameters are the same those in CNN. We also set the dropout rate in SDBN being 0.5 to avoid overfitting. For WL kernel, if the average similarity score for one test graph greater than 0.5, assign the test graph positive label, otherwise, assign negative label. We follow the setting in (Kipf & Welling 2016) and (Xu et al.) 2018) to do GCN and GIN-O. the adjacency matrices as features (i.e.,
In our experiments, make the results
Here, make fair comparison, we will information) for WL, GCN and GIN. In the experiments, we set the kernel size k in the isomorphic layer for three datasets as 2, 4, 3, 4, 4, respectively, and then set the parameters in classification component the same as those in Freq classifier. In this experiment, we adopt Adam optimizer and the set the learning rate 17 = 0.001, and then we report the average results on balanced datasets.
5.2 EXPERIMENTAL RESULTS
In this section, we investigate the effectiveness of the learned subgraph- based graph feature represen- tations for graphs. We adopt one isomorphic layer where the kernel size k and channel number
= 3 for HIV-fMRI, one isomorphic layer with (I: = 4, c 2), (1: 3, 1). (k 4, = 1) and 2) for the HIV-DTI. BP-IMRI, MUTAG and PTC, respectively. The results are shown in Table I From that table, we can observe that ISONN outperforms all other baseline methods on these all datasets. We need to remark that ISONN and IsoNN-fast are very close on MUTAG, and IsONN has the best performance in total on PTC. Compared with Freq, the proposed method achieves a better performance without searching for all possible subgraphs manually. AE has almost the worst performance among all comparison methods. This is because the features learned from
(A: 4, 4,
8

---

Under review as a conference paper at ICLR 2020
471
(a) HIV-MMII
(b) HIV-DTI
BP-MRRI
Azunyy
02
(d) MUTAG
(c) PTC
Figure 3: Effectiveness of Different k
AE do not contain any structural information. For HIV-DTI, AE gets F1. This because the dataset contains too many zeros, which makes the AE learns trivial features. Also, for PTC, its F1 higher than other models, but the accuracy only get 50.0, which indicates AE actually have bad performance since it cannot discriminate the classes of the instances (i.e., predicting all positive classes). CNN performs better than AE but still worse than ISONN. The reason can be that it learns some structural information but fails to learn representative structural patterns. SDBN is designed for brain images, so it may not work for MUTAG and PTC. One possible reason for WL got bad results is the isomorphism test is done the whole graph, which may lead to erratic results. GCN performs better than GIN but worse than ISONN, showing that GCN can learn some sturctual infor- mation without node labels, but GIN cannot work with the adjacency matrix as input. IsoNN-fas achieves the best scores on MUTAG and second-best on HIV-IMRI, yet worse than several other methods on other datasets. This can be the approximation on may impair the performance. Com- paring IsONN with AE, IsONN achieves better results. This means the structural information is more important than only connectivity information for the classification problem. compared with CNN, the results also show the contribution of breaking the node-order in learning the subgraph templates. Similar to SDBN, IsONN also finds the features from subgraphs, but IsONN gets better performance with more concise architecture. Contrasting with GCN and GIN, IsONN can maintain the explict subgraph structures in graph representations, while the GCN and GIN simply use the aggragation of the neighboring node features, losing the graph-level substructure infomation.
5.3 PARAMETER ANALYSIS
To further study the proposed method, we will discuss the effects of different kernel size and channel number in ISONN. The model convergence analysis will be provided appendix.
Kernel Size: We show the effectiveness of different l in Figure 3 Based on the previ- ous statement, parameter k can affect the final results since it controls the size of learned subgraph templates. To investigate the best kernel size for each dataset, we fix the chan- nel number 1. As Figure 3 shows, different datasets have different appropriate kernl sizes. The best kernel sizes are 2, 4. 3, 4, 4 for the three datasets, respectively.
Channel Number: We also study the effectiveness of multiple channels (i.e., multiple templates in one layer). To discuss how the channel number influences the results, we choose the best kernel size for each dataset (i.e., 2, 4, 3, 4, 4 respectively). From all sub- figures in Figure 4 we see that the differences among the different channel numbers by using only one isomorphic layer. As shown in Figure 4 IsONN achieves the best results by == 3, 2, 1, 2. respectively, which means the increase of the channel number can improve the performance, but more channels do not necessarily lead to better results. The reason could be the more templates complex model, it is easy to learn an overfitting model on train data, especially when the dataset is quite small. Thus, increasing the channel number can improve the performance but the effectiveness will still depend on the quality and the quantity of the dataset.
use, the
complex model would be. With such

---

Under review as a conference paper at ICLR 2020
041
04-
02-
05-
(a) HIV-MMII
(b) HIV-DTI
(c) BP-MRRI
Aearecy
(d) MUTAG
(c) PTC
Figure 4: Effectiveness of Different
(a) Different k
(b) Different
(c) IsoNN & ISONN-far
Figure 5: Time Complexity Study
5.4 TIME COMPLEXITY STUDY
To study the efficiency of ISONN and IsoNN-fast, we collect the actual running time on training model, which is shown in Figure In both Figures 5(a) and 5(b) the x-axis denotes its value for or c and the y-axis denotes the time cost with different parameters. From Figure 5(a) four lines show the same pattern. When the & increases, the time cost grows exponentially. This pattern can be directly explained by the size of the permutation matrix set. When we increase the kernel size by one, the number of corresponding permutation matrices grows exponentially. While changing c, shown in Figure Figu it is easy to observe that those curves are basically linear with different slopes. This is also natural since whenever we add one channel, we only need to add a constant number of the permutation matrices. To study the efficiency of IsoNN-fast. Figure 5(c) shows the running times of IsoNN and IsoNN-fas: on MUTAG. As it shows, IsoNN- fast use less time when the kernel size greater than 4, otherwise ISONN and IsONN will have little difference since the eigen decomposition has nearly the same time complexity as calculating all possible node permutaions. The results also verify the theoretical time complexity analysis in 4.3
6 CONCLUSION
In this paper, proposed novel graph neural network named ISONN to solve the graph classi- fication problem. ISONN consists of two components: (1) isomorphic component, where a set of permutation matrices is used break the randomness order posed by matrix representation for bunch of templates and one min-poolin poolinooing layer and one softmax layer are used to get the best iso- morphic features, and (2) classification component, which contains three fully-connected layers. We further discuss the two efficient variants of ISONN to accelerate the model. Next, we perform the experiments on five real-worke datasets. The experimental results show the proposed method out- performs all comparison methods, which demonstrates the superiority of our proposed method. The experimental analysis on time complexity illustrates the efficiency of the IsoNN-fast.
"Since the PTC is relative large dataset compared with the others, its running time is in different scale compared with the other datasets, which makes the time growth curve of other datasets not obvious. Thus, we don't 't show the results on PTC.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Rami AI-Rfou, and Alexander A Alemi. Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems, pp. 9180-9190, 2018.
James Atwood and Don Towsley. Diffuusin--oovollutioaal neural networks. In Advances in Neural Information Processing Systems, pp. 1993-2001, 2016.
Yunsheng Bai, Hao Ding, Yizhou Sun, and Wei Wang. Convolutional set matching for graph simi- larity, arXiv preprini urXiv:1810 10866, 2018.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1106iv8806.01200 2018.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Pro- cessing Systems 26, pp. 2787-2795. Curran Associates, Inc., 2013.
Bokai Cao, Xiangnan Kong, Jingyuan Zhang. S Yu Philip, and Ann B Ragin. Identifying hiv-induced subgraph patterns in brain networks with side information. Brain informatics, 2(4):211 2015a.
Bokai Cao, Liang Zhan, Xiangnan Kong, S Yu Philip, Nathalie Vizueta, Lori L Altshuler, and Alex D Leow. Identification of discriminative subgraph patters in fmri brain networks in bipolar affective disorder. In International Conference on Brain Informatics and Health, pp. 105-114. Springer, 2015b.
Mohammed Elseidy, Ehab Abdelhamid, Spiros Skiadopoulos, and Panos Kalnis. Grami: Frequent subgraph and pattern mining in a single large graph. Proceedings of the VLDB Endowment, 7(7): 517-528, 2014.
Qiang Gao, Fan Zhou, Kumpeng Zhang, Goce Trajcevski, Xucheng Luo, and Fengli Zhang. Identi- fying human mobility via trajectory embeddings. In International Joint Conferences on Artificial Intelligence, volume 17, pp. 1689-1695, 2017.
Benoit Gaüzere, Lue Brun, and Didier Villemin. Two new graphs kernels in chemoinformatics. Pattern Recognition Letters, 33(15) 20477200777 2012.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Learning-Volume 70, pp. 1272-1272. JMLR. org, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Steven Hill, Bismita Srichandan, and Rajshekhar Sunderraman. An iterative mapreduce approach to frequent subgraph mining in biological datasets. In Proceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine, pp. 661-666. ACM, 2012.
Ning Jin, Calvin Young, and Wei Wang. Graph classification based on pattern co-occurrence. In Proceedings of the 18th ACM conference on Information and knowledge management, pp. 573- 582. ACM, 2009.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th international conference on machine learning (ICML-03), pp. 321- 328, 2003.
11

---

Under review as a conference paper at ICLR 2020
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint 169.000799 2016.
Xiangnan Kong and Philip S Yu. Semi-supervised feature selection for graph classification. In Proceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 793-802 ACM, 2010.
Xiangnan Kong, Philip Yu, Xue Wang, and Ann Ragin. Discriminative feature selection for uncertain graph classification. In Proceedings of the 2013 SIAM International Conference Data Mining, pp. 82-93. SIAM, 2013.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yi-An Lai, Chin-Chi Hsu, Wen Hao Chen, Mi-Yen Yeh, and Shou-De Lin. Prune: Preserving prox- imity and global ranking for network embedding. In Advances in neural information processing systems, pp- 5257-5266, 2017.
John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1666-1674. ACM, 2018.
Wenqing Lin, Xiaokui Xiao, and Gabriel Ghinita. Large-scale frequent subgraph mining in mapre- duce. In 2014 IEEE 30th International Conference on Data Engineering, pp. 844-855, IEEE, 2014.
Yankai Lin. Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In Twenty-ninth AAAI conference on artificial intelligence, 2015.
Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. Geodesic con- volutional neural networks on riemannian manifolds. In Proceedings of the IEEE international conference on computer vision workshops, pp- 37-45, 2015.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model enns. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pp. 5115- 5124, 2017.
Aida Mrzic, Pieter Meysman, Wout Bittremieux, Pieter Moris, Boris Cule, Bart Goethals, and Kris Laukens. Grasping frequent subgraph mining for bioinformatics applications. BioDala mining, 11(1):20, 2018
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint 1rXiv:1707.05005, 2017.
Fengcai Qiao, Xin Zhang, Pei Li, Zhaoyun Ding, Shanshan Jia, and Hui Wang. A parallel approach for frequent subgraph mining in single large graph using spark. Applied Sciences. 8(2):230, 2018.
Hiroto Saigo, Sebastian Nowozin, Tadashi Kadowaki, Taku Kudo, and Koji Tsuda, gboost: a math- ematical programming approach to graph classification and regression. Machine Learning, 75(1): 69-89, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisneiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep):2539- 2561, 2011.
Marisa Thoma, Hong Cheng, Arthur Gretton, Jiawei Han, Hans- Peter Kriegel, Alex Smola, Le Song, Philip Yu, Xifeng Yan, and Karsten Borgwardt. Near-optimal supervised feature selection among frequent subgraphs. In Proceedings of the 2009 SIAM International Conference on Data Mining, pp. 1076-1087. SIAM, 2009.
12

---

Under review as a conference paper at ICLR 2020
Tong Tong, Katherine Gray, Qinquan Gao, Liang Chen, and Daniel Rueckert. Nonlinear graph fu- sion for multi-modal classification of alzheimer's 's disease. In International Workshop on Machine Learning in Medical Imaging, pp. 77-84. Springer, 2015.
Tong Tong, Katherine Gray, Qinquan Gao, Liang Chen, Daniel Rueckert, Alzheimer's Disease Neu- roimaging Initiative, et al. Multi-modal classification of alzheimer's s disease using nonlinear graph fusion. Pattern recognition, 63:171-181, 2017.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked denoising autoencoders: Learning useful representations in a deep network with local denoising criterion. Journal of machine learning research, 1(Dec):3371-340S 2010.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11(Apr):1201-1244 2010.
Shen Wang, Lifang He, Bokai Cao, Chun-Ta Lu. Philip Yu, and Ann B Ragin. Structural deep brain network mining. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 475 484. ACM, 2017.
Jia Wu, Shirui Pan, Xingquan Zhu, and Zhihua Cai. Boosting for multi-graph classification. IEEE transactions cybernetics, 45(3):116-425 2014.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 11000018 2018.
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In 2002 IEEE Inter- national Conference on Data Mining, 2002. Proceedings. pp. 721-724. IEEE, 2002.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
13

---

Under review as a conference paper at ICLR 2020
7 APPENDIX
7.1 PROOF OF THEOREM AND DISCUSSION ABOUT EQUATION
(
Before giving the proof of Theorem need introduce Lemma first.
LEMMA If A and are Hermitian matrices with eigenvalues an 02 2 ...2. an and 31 2 82 2 ... 2 3n respectively, then ||A - B (a= -3:)²
Based on Lemma we can derive the proof of Theorem | as follows.
[ Equation holds for any orthogonal matrix R since the eigenvalues of RK,R are the same those of K,
PROOF 1 From Lemma
n
RRKR M
Σ j=1
aaj - 3,)²
(9)
On the other hand, if we use P in we have
IPK,PT M(s,2)1
|UM SU UK UK Ki
UK SK. SUM(nn
UMi A M 11
M(n))
=IUMMG. (SAK,S- AMC..)) ) UN
-ISSAK, S A
= =IIAK; AM
-E==(aa (aj B,)²
(10)
where we use the equations that ||XX| ||UX = |X| for any orthogonal matrix U and SAK, S Ak AK, since S and K, are both orthogonal matrices and S =
Moreover, it is clear that
tr(P U UM SU S tr ( U IUk)))
(11)
because of the elements in S are either -1 -1or Also, since each row vector of U M. and Uk, is unit vector, thus we can have
M || n
(12)
If there exists perfect permutaion matrix, P then there exists such St, s.t.
tr(P
U M..., S'U)) tr(p"
(13)
Thus, based on Equation
11 Equation
12 and Equation 13). we can get
tr(P*
U UM |UU,D < n.
(14)
This means that P maximizes tr(P |U M..., ||Uk,)) I) since tr(P U MM... |Uk 1) for any permuta- tion matrix P. Therefore, when K, and M(.)) are isomorphic, the optimal permutation matrix can be obtained as permutation matrix P which maximizes tr(P |U | K. Therefore, we take
P JU ||U] directly.
7.2 AN EXAMPLE FOR DEEP ISOMORPHIC NEURAL NETWORK
To better illustrate the idea of our deep model, also provide the model architecture involves two graph isomorphic feature extraction components. Suppose the kemel size for the first graph isomorphic layer is hı with channels, whereas the kernel size of the second graph isomorphic layer 122 with m channels. The model is shown in Figure (6 After the first graph isomorphic feature extraction component, get the first feature tensor Q and each element in Q denotes matching
14

---

Under review as a conference paper at ICLR 2020
Graph Isoorppiic Layert
Wiroodeg
Sefroar
Graph leomompic
Lapar2
Layers
Figure Deep IsoNN Framework Architecture with Two Graph Isomorphic Layers.
Epace
Spoch Number
(a) HIV-IMRI
(b) HIV-DTI
(c) BP-IMRI
Epsch Number
Epoch Number
(d) MUTAG
(e) PTC
Figure 7: Convergence Analysis
score between one subgraph to one kernel template. Thus, we can also regard each clement in Q1 kernel template. Since have channel in the first component, the second component will be used on every channel of Q1. the channel number of the second component is m, then the first dimension of the learned feature tensor 22 of the second component with 3 or more graph isomorphic feature extraction components, our will do similar operations to the second isomorphic components. The first dimension of the final tensor will be the product of channels in all former graph isomorphic layers.
m. For deeper model
7.3 CONVERGENCE ANALYSIS
The Figure 7 shows the convergence trend IsONN on five datasets, where the x-axis denotes the epoch number and the y y-axis is the training loss, respectively. From these sub-figures, we know that the proposed method can achieve stable optimal solution within 50 iterations except for MUTAG (it needs almost 130 epochs converge), which also illustrates method would converge relatively fast.
15


Reviews:
[{"review_id": "rke32mHAYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 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.\nExperiments 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeRPECaFr", "reviewer": "AnonReviewer1", "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 to learn graph features by means of neural networks for graph classification.\nIn the proposed method, a graph is described by bag of sub-graphs and the sub-graph dictionary is learned through isomorphic matching.\nThe 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.\nIn 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.\n\nThis 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.\nThe detailed comments are as follows.\n\n* 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).\n\n* 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.\n\n* 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.\n\n* 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.\n\n* 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].\n\n[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\n[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\n\n\nMinor comments:\n- Improper citation format. Use \\citep and \\citet properly according to the context.\n- 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJgiqXjrYB", "reviewer": "AnonReviewer3", "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 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.\n\nGraph 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.\n\nIn 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.\n\nAlso, 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.", "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 made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

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