Year: 2019

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 models on graph classification tasks extremely erratic, and the representations learned by such models lack clear interpretability. To eliminate the unnecessary nodeorder 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.

heading: 1 INTRODUCTION
text: The graph structure is 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 et al., 2017), distinguish the brain states of patients via their brain networks (Wang et al., 2017), and classify the functions of proteins in a biological interaction network (Hamilton et 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 a pattern exploration approach based on pattern co-occurrence and build the classification model (Jin et al., 2009) or develop a 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, 2016) 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 are other models can capture the subgraphs, they often need more complex computation and mechanism (Wang et al., 2017; Narayanan et al., 2017) or need additonal node labels to find the subgraph strcuture (Gaüzere et al., 2012; Shervashidze et al., 2011).
However, we 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 a node-order is usually unnecessary and manually defined. The different graph matrix representations 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 discriminative models to discover useful subgraphs for graph classification, and most of them require manual efforts. Nevertheless, how to select the contributing subgraphs automatically without any additional manual involvement is a 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 & Leskovec, 2016; Lin et al., 2015; Lai et al., 2017; Hamilton et al., 2017), whereas learning the representation of the whole graph with clear interpretability is still an open problem requiring more explorations.
• Node-order elimination for subgraphs. Nodes in graphs are orderless, whereas the matrix representations of graphs cast an unnecessary order on nodes, which also renders the features extracted with the existing learning models, e.g., CNN, to be useless for the graphs. For subgraphs, this problem also exists. Thus, how to break such a node-order constraint for subgraphs is 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 a 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 variants, to address the aforementioned challenges in the graph representation learning and classification problem. ISONN is composed of two components: the graph isomorphic feature extraction component and the classification component, aiming at learning isomorphic features and classifying graph instances, respectively. In the graph isomorphic feature extraction component, ISONN automatically learns a group of subgraph templates of useful patterns from the input graph. ISONN makes use of a 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 different 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.

heading: 2 RELATED WORK
text: Our work relates to subgraph mining, graph neural networks, network embedding as well as graph classification. We will discuss them briefly in the followings.
Subgraph Mining and Graph Kernel Methods: Mining subgraph features from graph data has been studied for many years. The aim is to 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 a lexicographic order among graphs and map each graph to a 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 problem to find the minimal set. For the supervised model (i.e., 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
been adopted in life sciences (Mrzic et al., 2018). Moreover, several parallel computing based methods (Qiao et al., 2018; Hill et al., 2012; Lin et al., 2014) have proposed to reduce the time cost. On the other hand, graph kernel methods are also applied to discover the subgraph structures (Kashima et al., 2003; Vishwanathan et al., 2010; Gaüzere et al., 2012; Shervashidze et al., 2011). Among them, most existing works focus on the graph with node labels and the kernels methods only computes 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.
Graph Neural Network and Network Embedding: Graph Neural Networks (Monti et al., 2017; Atwood & Towsley, 2016; Masci et al., 2015; Kipf & Welling, 2016; Battaglia et al., 2018) 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 adjacency matrix to learn the node features for node classification; (Bai et al., 2018) proposes the multiscale convolutional model for pairwise graph similarity with a 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 to maintain the explicit structural information. Another important topic related to this paper is network embedding (Bordes et al., 2013; Lin et al., 2015; Lai et al., 2017; Abu-El-Haija et al., 2018; Hamilton et al., 2017), 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.
Graph Classification: Graph classification is an important problem with many practical applications. 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 patients diagnosis (Tong et al., 2017; 2015) respectively. Traditionally, researchers mine the subgraphs by DFS or BFS (Saigo et al., 2009; Kong et al., 2013), and use them as the features. With the rapid development of deep learning (DL), many works are done based on DL methods. GAM builds the model by RNN with self-attention mechanism (Lee et al., 2018). DCNN extend CNN to general graph-structured data by introducing a ‘diffusion-convolution’ operation (Atwood & Towsley, 2016).

heading: 3 TERMINOLOGY AND PROBLEM DEFINITION
text: In this section, we will define the notations and the terminologies used in this paper and give the formulation for the graph classification problem.

heading: 3.1 NOTATIONS
text: 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 xi 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 x> and X> denote the transpose of vector x and matrix X respectively. Besides, the F -norm of matrix X can be represented as ‖X‖F = ( ∑ i,j |Xi,j |2) 1 2 .

heading: 3.2 PROBLEM FORMULATION
text: Many real-world inter-connected data can be formally represented as the graph-structured data.
DEFINITION 1 (Graph): Formally, a graph can be represented as G = (V, E), where the sets V and E 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
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 G = {G1, G2, · · · , Gn} with a small number of labeled graph instances, the graph classification problem aims at learning a mapping, i.e., f : G → Y , 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 or multi-label as well.

heading: 4 PROPOSED METHOD
text: The overall architecture of ISONN is shown in Figure 1. 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 minpooling layer as well as a softmax layer and the classification component is composed by three fully-connected layers. They will be discussed in detail in the following subsections.

heading: 4.1 GRAPH ISOMORPHIC FEATURE EXTRACTION COMPONENT
text: 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 learning. 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 components 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.

heading: 4.1.1 GRAPH ISOMORPHIC LAYER
text: Graph isomorphic layer is the first effective layer in deep learning that handles the node-order restriction in graph representations. Assume we have a graph G = {V, E}, and its adjacency matrix to be A ∈ R|V|×|V|. In order to find the existence of specific subgraph patterns in the input graph, ISONN matches the input graph with a set of subgraph templates. Each template is denoted as a kernel variable Ki ∈ Rk×k,∀i ∈ {1, 2, · · · , c}. Here, k denotes the node number in subgraphs and c is the channel number (i.e., total template count). Meanwhile, to match one template with regions in the input graph (i.e., sub-matrices in A), we use a set of permutation matrices, which map both rows and columns of the kernel variable to the subgraphs effectively. The permutation matrix can be represented as P ∈ {0, 1}k×k that shares the same dimension with the kernel variable. Therefore, given a kernel Ki and a sub-matrix M(s,t) ∈ Rk×k in A (i.e., a region in the input graph G and s, t ∈ {1, 2, · · · , (|V|−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 P∈P ∥∥PKiP> −M(s,t)∥∥2F , (1)
where P = {P1,P2, · · · ,Pk!} covers all the potential permutation matrices. Formally, the isomorphic feature extracted based on the kernel Ki for the regional sub-matrix M(s,t) in A can be represented as
zi,(s,t) = ∥∥P∗Ki(P∗)> −M(s,t)∥∥2F = min{∥∥PKiP> −M(s,t)∥∥2F }P∈P
= min(z̄i,(s,t)(1 : k!)), (2)
where vector z̄i,(s,t) ∈ Rk! contains entry z̄i,(s,t)(j) = ∥∥PjKiP>j −M(s,t)∥∥2F ,∀j ∈ {1, 2, · · · , k!} denoting the isomorphic features computed by the j-th permutation matrix Pj ∈ P . As indicated by the Figure 1, ISONN computes the final isomorphic features for the kernel variable Ki 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-pooling layer and softmax layer to be introduced as follows. By shifting one kernel matrix Ki on regional sub-matrices, ISONN extracts the isomorphic features on the matrix A, which can be denoted as a 3-way tensor Z̄i ∈ Rk!×(|V|−k+1)×(|V|−k+1), where Z̄i(1 : k!, s, t) = z̄i,(s,t)(1 : k!). In a similar way, we can also compute the isomorphic feature tensors based on the other kernels, which can be denoted as Z̄1, Z̄2, · · · , Z̄c respectively.

heading: 4.1.2 MIN-POOLING LAYER
text: Given the tensor Z̄i computed by Ki 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 Z̄i as matrix Zi:
Zi(s, t) = min{Z̄i(1 : k!, s, t)}. (3)
The min-pooling layer learns the optimal matrix Zi for kernel Ki along the first dimension (i.e., 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 Z1, Z2, · · · , Zc respectively.

heading: 4.1.3 SOFTMAX LAYER
text: Based on the above descriptions, a perfect matching between the subgraph templates with the input graph will lead to a very small isomorphic feature, e.g., a 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 in the end. Meanwhile, the feature values computed in 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, Z2, · · · , Zc across all c kernels. Compared with the raw features, e.g., Zi, softmax as a non-linear mapping can also effectively highlight the useful features in Zi by rescaling them to relatively larger values especially compared with the useless ones. Formally, we can represent the fused graph isomorphic features after rescaling by all the kernels as a 3-way tensor Q, where slices along first dimension can be denoted as:
Q(i, :, :) = Ẑi , where Ẑi = softmax(−Zi), ∀i ∈ {1, . . . , c}. (4)

heading: 4.2 CLASSIFICATION COMPONENT
text: After the isomorphic feature tensor Q is obtained, we feed it into a classification component. Let q denote the flattened vector representation of feature tensorQ, and we pass it to three fully-connected layers to get the predicted label vector ŷ. For the graph binary classification, suppose we have the ground truth y = (yg1 , y g 2) and the predicted label vector ŷ g = (ŷg1 , ŷ g 2) for the sample g from the training batch set B. We use cross-entropy as the loss function in ISONN. Formally, the fullyconnected (FC) layers and the objective function can be represented as follows respectively:
FC Layers: { d1 = σ(W1q + b1), d2 = σ(W2d1 + b2), ŷ = σ(W3d2 + b3), Objective Function: L = − ∑ g∈B 2∑ j=1 ygj log ŷ g j , (5)
where Wi and bi represent the weights and biases in i-th layer respectively for i ∈ {1, 2, 3}. The σ 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.

heading: 4.3 MORE DISCUSSIONS ON GRAPH ISOMORPHIC FEATURE EXTRACTION IN ISONN
text: 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)2 regional sub-matrices (orO(n2) regional submatrices for notation simplicity). Here, we assume ISONN has only one isomorphic layer involving c different kernels. In the forward propagation, the introduced time cost in computing the graph isomorphic features can be denoted as O(ck!k3n2), where term k! is introduced in enumerating all the potential permutation matrices and k3 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 c 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 perspectives: (1) compute the optimal permutation matrix in a faster manner, and (2) use deeper model architectures with small-sized kernels.

heading: 4.3.1 FAST PERMUTATION MATRIX COMPUTATION
text: Instead of enumerating all the permutation matrices in the graph isomorphic feature extraction as indicated by Equations (2)-(3), here we introduce a fast way to compute the optimal permutation matrix for the provided kernel variable matrix, e.g., Ki, and input regional sub-matrix, M(s,t), directly according to the following theorem.
THEOREM 1 Formally, let the kernel variable Ki and the input regional sub-matrix M(s,t) be k×k real symmetric matrices with k distinct eigenvalues α1 > α2 > · · · > αk and β1 > β2 > · · · > βk, respectively, and their eigendecomposition be represented by
Ki = UKiΛKiU > Ki , and M(s,t) = UM(s,t)ΛM(s,t)U > M(s,t)
(6)
where UKi and UM(s,t) are orthogonal matrices of eigenvectors and ΛKi = diag(αj),ΛM(s,t) = diag(βj). The minimum of ||PKiP> −M(s,t)||2 is attained for the following P’s:
P∗ = UM(s,t)SU > Ki (7)
where S ∈ S = {diag(s1, s2, · · · , sk)|si = 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, to avoid such time costs, we introduce to take the upper bound value of UM(s,t)SU > Ki
as the approximated optimal permutation matrix instead, which together with the corresponding optimal feature zi,(s,t) can be denoted as follows:
P∗ = |UM(s,t) ||U > Ki | and zi,(s,t) = ||P ∗K(P∗)> −M(s,t)||2, (8)
where |·| denotes the absolute value operator and |UM(s,t) ||U>Ki | ≥ UM(s,t)SU > Ki hold for ∀S ∈ S. By replacing Equations (2)-(3) with Equation (7), we can compute the optimal graph isomorphic feature for the kernel Ki and input regional sub-matrix M(s,t) with a much lower time cost. Furthermore, since the eigendecomposition time complexity of a k × k matrix is O(k3), based on the above theorem, we will be able to lower down the total time cost in graph isomorphic feature extraction to O(ck3n2), which can be optimized with the method introduced in the following subsection.

heading: 4.3.2 DEEP GRAPH ISOMORPHIC FEATURE EXTRACTION
text: 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 a deep model in appendix. Here, we 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 1 involves 2 kernels of size 3, and layer 2 involves 3
kernels of size 4.
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 O(6(123)n2) and O(2(33)n2 + 3(43)n2), 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 a 1-layer ISONN model with c large kernels of size k, its graph isomorphic feature extraction time complexity can be denoted as O(ck3n2). Inspired by Figure 2, without affecting the representation capacity, such a model can be replaced by a max{dlogc2e , ⌈ logk3 ⌉ }-layers deep ISONN model instead, where each layer involves 2 kernels of size 3. The graph isomorphic feature extraction time complexity of the deep model will be O ( (max{dlogc2e , ⌈ logk3 ⌉ }) · 2 · 33n2 ) (or O ( (max{dlogce , ⌈ logk ⌉ }) · n2 ) for simplicity).

heading: 5 EXPERIMENTS
text: To evaluate the performance of ISONN, in this section, we will talk about the experimental settings as well as five benchmark datasets. Finally, we will discuss the experimental results with parameter analyses on kernel size , channel number and time complexity.

heading: 5.1 EXPERIMENTAL SETTINGS
text: In this subsection, we will use five real-world benchmark datasets: HIV-fMRI (Cao et al., 2015a), HIV-DTI (Cao et al., 2015a), BP-fMRI (Cao et al., 2015b), MUTAG1 and PTC1. 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 × 90 matrices (Cao et al., 2015a). BP-fMRI has 52 positive and 45 negative instances and each instance is presented by an 82× 82 matrix Cao et al. (2015b). MUTAG and PTC are two datasets which have been widely used in academia Xu et al. (2018); Shervashidze et al. (2011). 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 in this paper and then talk about the experimental setups and the adopted evaluation metrics in detail.

heading: 5.1.1 COMPARISON METHODS
text: • ISONN & ISONN-fast : 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-fast uses the Equation 8 to compute the optimal permutation matrices and other settings remain unchanged.
• Freq: The method uses the top-k frequent subgraphs as its features. This is also an unsupervised 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 is the convolutional model (Krizhevsky et al., 2012) learns the structural information within small regions of the whole graph. We adopt one convolution layer and three fully-connected layer to be the classification module.
1https://ls11-www.cs.tu-dortmund.de/people/morris/graphkerneldatasets/

heading: 5.1.2 EXPERIMENTAL SETUP AND EVALUATION METRICS
text: In our experiments, to make the results more reliable, we partition the datasets into 3 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 is the testing data. We select top-100 features for Freq as stated in (Wang et al., 2017) with a 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 × 5 × 50, a max-pooling layer with kernel size 2 × 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 an activation layer, where the parameters are the same as 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, we 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-0. Here, to make a fair comparison, we will use the adjacency matrices as features (i.e., no node label 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 η = 0.001, and then we report the average results on balanced datasets.

heading: 5.2 EXPERIMENTAL RESULTS
text: In this section, we investigate the effectiveness of the learned subgraph-based graph feature representations for graphs. We adopt one isomorphic layer where the kernel size k = 2 and channel number c = 3 for HIV-fMRI, one isomorphic layer with (k = 4, c = 2), (k = 3, c = 1), (k = 4, c = 1) and (k = 4, c = 2) for the HIV-DTI, BP-fMRI, MUTAG and PTC, respectively. The results are shown in Table 1. 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
AE do not contain any structural information. For HIV-DTI, AE gets 0 in F1. This is because the dataset contains too many zeros, which makes the AE learns trivial features. Also, for PTC, its F1 is higher than other models, but the accuracy only get 50.0, which indicates AE actually have a 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 on 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 information without node labels, but GIN cannot work with the adjacency matrix as input. ISONN-fast achieves the best scores on MUTAG and second-best on HIV-fMRI, yet worse than several other methods on other datasets. This can be the approximation on P may impair the performance. Comparing ISONN with AE, ISONN achieves better results. This means the structural information is more important than only connectivity information for the classification problem. If 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.

heading: 5.3 PARAMETER ANALYSIS
text: 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 in appendix.
• Kernel Size: We show the effectiveness of different k in Figure 3. Based on the previous 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 channel number c = 1. As Figure 3 shows, different datasets have different appropriate kernel 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 subfigures in Figure 4, we can 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 c = 3, 2, 1, 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 we use, the more complex our model would be. With such a 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.

heading: 5.4 TIME COMPLEXITY STUDY
text: To study the efficiency of ISONN and ISONN-fast, we collect the actual running time on training model, which is shown in Figure 5. In both Figures 5(a) and 5(b) 2, the x-axis denotes its value for k 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 k 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 5(b), 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-fast 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.

heading: 6 CONCLUSION
text: In this paper, we proposed a novel graph neural network named ISONN to solve the graph classification problem. ISONN consists of two components: (1) isomorphic component, where a set of permutation matrices is used to break the randomness order posed by matrix representation for a bunch of templates and one min-pooling layer and one softmax layer are used to get the best isomorphic 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-world datasets. The experimental results show the proposed method outperforms all comparison methods, which demonstrates the superiority of our proposed method. The experimental analysis on time complexity illustrates the efficiency of the ISONN-fast.
2Since the PTC is a 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 show the results on PTC.

heading: 7 APPENDIX

heading: 7.1 PROOF OF THEOREM 1 AND DISCUSSION ABOUT EQUATION (8)
text: Before giving the proof of Theorem 1, we need to introduce Lemma 1 first.
LEMMA 1 If A and B are Hermitian matrices with eigenvalues α1 ≥ α2 ≥ · · · ≥ αn and β1 ≥ β2 ≥ · · · ≥ βn respectively, then ||A−B|| ≥ ∑n i=1(αi − βi)2.
Based on Lemma 1, we can derive the proof of Theorem 1 as follows.
PROOF 1 From Lemma 1, Equation 9 holds for any orthogonal matrix R since the eigenvalues of RKiR > are the same as those of Ki.
||RKiR> −M(s,t)||2 ≥ n∑
j=1
(αj − βj)2 (9)
On the other hand, if we use P in 7, we have
||PKiP> −M(s,t)||2 = ||UM(s,t)SU>KiUKiΛKiU > Ki UKiSU > M(s,t) −UM(s,t)ΛM(s,t)U>M(s,t) || 2
= ||UM(s,t)(SΛKiS−ΛM(s,t))U>M(s,t) || 2
= ||SΛKiS−ΛM(s,t) ||2
= ||ΛKi −ΛM(s,t) ||2
= ∑n
j=1(αj − βj)2 (10)
where we use the equations that ||UX|| = ||UX>|| = ||X|| for any orthogonal matrix U and SΛKiS = S 2ΛKi = ΛKi since S and ΛKiare both orthogonal matrices and S 2 = I.
Moreover, it is clear that
tr(P>UM(s,t)SU > Ki) ≤ tr ( P>|UM(s,t) ||U > Ki | )
(11)
because of the elements in S are either −1 or +1. Also, since each row vector of UM(s,t) and UKi is unit vector, thus we can have
tr(P>|UM(s,t) ||U > Ki |) ≤ n (12)
If there exists a perfect permutaion matrix, P∗, then there exists such S∗, s.t.
tr(P∗>UM(s,t)S ∗U>Ki) = tr(P ∗>P∗) = n (13)
Thus, based on Equation (11), Equation (12) and Equation (13), we can get
tr(P∗>|UM(s,t) ||U > Ki |) ≤ n. (14)
This means that P maximizes tr(P>|UM(s,t) ||U>Ki |) since tr(P >|UM(s,t) ||U>Ki |) for any permutation matrix P. Therefore, when Ki and M(s,t) are isomorphic, the optimal permutation matrix can be obtained as a permutation matrix P which maximizes tr(P>|UM(s,t) ||U>Ki |). Therefore, we take P∗ = |UM(s,t) ||U>Ki | directly.

heading: 7.2 AN EXAMPLE FOR DEEP ISOMORPHIC NEURAL NETWORK
text: To better illustrate the idea of our deep model, we also provide the model architecture involves two graph isomorphic feature extraction components. Suppose the kernel size for the first graph isomorphic layer is k1 with c channels, whereas the kernel size of the second graph isomorphic layer is k2 with m channels. The model is shown in Figure 6. After the first graph isomorphic feature extraction component, we get the first feature tensor Q1 and each element in Q1 denotes matching
score between one subgraph to one kernel template. Thus, we can also regard each element in Q1 as a kernel template. Since we have c channel in the first component, the second component will be used on every channel of Q1. If the channel number of the second component is m, then the first dimension of the learned feature tensor Q2 of the second component is c ∗m. For a deeper model 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 Q will be the product of channels in all former graph isomorphic layers.

heading: 7.3 CONVERGENCE ANALYSIS
text: The Figure 7 shows the convergence trend of ISONN on five datasets, where the x-axis denotes the epoch number and the y-axis is the training loss, respectively. From these sub-figures, we can know that the proposed method can achieve a stable optimal solution within 50 iterations except for MUTAG (it needs almost 130 epochs to converge), which also illustrates our method would converge relatively fast.

Review summaries:
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.

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.