Year: 2019

Abstract:
While the celebrated graph neural networks yield effective representations for individual nodes of a graph, there has been relatively less success in extending to deep graph similarity learning. Recent work has considered either global-level graph-graph interactions or low-level node-node interactions, ignoring the rich cross-level interactions between parts of a graph and a whole graph. In this paper, we propose a Hierarchical Graph Matching Network (HGMN) for computing the graph similarity between any pair of graph-structured objects. Our model jointly learns graph representations and a graph matching metric function for computing graph similarity in an end-to-end fashion. The proposed HGMN model consists of a multi-perspective node-graph matching network for effectively learning crosslevel interactions between parts of a graph and a whole graph, and a siamese graph neural network for learning global-level interactions between two graphs. Our comprehensive experiments demonstrate that our proposed HGMN consistently outperforms state-of-the-art graph matching network baselines for both classification and regression tasks.

heading: 1 INTRODUCTION
text: Learning a general similarity metric between arbitrary pairs of graph-structured objects is one of the key challenges in machine learning. Such learning problems often arise in a variety of applications, ranging from graph similar searching in graph-based database (Yan & Han, 2002), to Fewshot 3D Action Recognition (Guo et al., 2018), unknown malware detection (Wang et al., 2019), and promising selection in automatic theory proving (Wang et al., 2017), to name just a few.
Conceptually, classical exact (or inexact) graph matching techniques (Ullmann, 1976; Caetano et al., 2009; Bunke & Allermann, 1983; Riesen et al., 2010) provide a strong tool for learning graph similarity. However, these methods usually either require input graphs with similar sizes or consider mainly the graph structures for finding a correspondence between the nodes of different graphs without taking into account the node representations or features. In contrast, in this paper, we consider the graph matching problem of learning a mapping between a pair of graph inputs pG1, G2q P GˆG and the similarity score y P Y , based on a set of training triplet of structured input pairs and scalar output score pG11, G21, y1q, ..., pG1n, G2n, ynq P G ˆ G ˆ Y drawn from some fixed but unknown probability distribution.
Recent years have seen a surge of interests in graph neural networks (GNNs), which have been demonstrated to be a powerful class of models for learning node embeddings of graph-structured data (Bronstein et al., 2017). Various GNN models have since been developed for learning effective node representations for node classification (Li et al., 2016; Kipf & Welling, 2016; Hamilton et al., 2017; Veličković et al., 2017), or pooling the learned node embeddings into a graph vector for graph classification (Ying et al., 2018; Ma et al., 2019), or combining with variational auto-encoder to learn the graph distribution for graph generation (Simonovsky & Komodakis, 2018; Li et al., 2018; Samanta et al., 2018; You et al., 2018). However, there is relatively less study on learning graph similarity using GNNs.
To learn graph similarity, a simple yet straightforward way is to encode each graph as a vector and combine two vectors of each graph to make a decision. This approach is useful since graphlevel embeddings contain important information of a pair of graphs. One obvious limitation of this approach lies in the fact of the ignorance of more fine-grained interactions among different level
embeddings of two graphs. Very recently, a few of attempts have been made to take into account lowlevel interactions either by considering the histogram information of node-wise similarity matrix of node embeddings (Bai et al., 2019) or improving the node embeddings of one graph by incorporating implicit attentive neighbors of another graphs through a soft attention (Li et al., 2019). However, there are two significant challenges making these graph matching models potentially ineffective: i) how to learn different-level granularity (global level and local level) of interactions between a pair of graphs; ii) how to effectively learn richer cross-level interactions between parts of a graph and a whole graph.
Inspired by these observations, in this paper, we propose a Hierarchical Graph Matching Network (HGMN) for computing the graph similarity between any pair of graph-structured objects. Our model jointly learns graph representations and a graph matching metric function for computing graph similarity in an end-to-end fashion. The proposed HGMN model consists of a novel multiperspective node-graph matching network for effectively learning cross-level interactions between parts of a graph and a whole graph, and a siamese graph neural network for learning global-level interactions between two graphs. Our final small prediction networks consume these feature vectors from both cross-level and global-level interactions to perform either graph-graph classification or graph-graph regression tasks, respectively.
Recently proposed works only compute graph similarity by considering either graph-graph classification problem (with labels Y “ t´1, 1u) (Li et al., 2019), or graph-graph regression problem (with similarity score Y “ r0, 1s) (Bai et al., 2019). To demonstrate the effectiveness of our model, we systematically investigate the performance of our HGMN model compared with these recently proposed graph matching models on four datasets for both graph-graph classification and regression tasks. To bridge the gap of the lack of standard graph matching datasets, we also create one new dataset from a real application together with a previously released dataset by (Xu et al., 2017) for graph-graph classification task 1. One important aspect is previous works did not consider the impact of the size of two input graphs, which often plays an important role in determining the performance of graph matching. Motivated by this observation, we have considered three different ranges of graph sizes from [3, 200], [20,200], and [50,200] in order to evaluate the robustness of each graph matching model.
We highlight our main contributions of this paper as follows:
• We propose a hierarchical graph matching network (HGMN) for computing the graph similarity between any pair of graph-structured objects. Our HGMN model jointly learns graph representations and a graph matching metric function for computing graph similarity in an end-to-end fashion.
• In particular, we propose a multi-perspective node-graph matching network for effectively capturing the cross-level interactions between a node embeddings of a graph and a corresponding attentive graph-level embedding of another graph.
• We systematically investigate different factors on the performance of all graph matching models such as the impact of different tasks (classification and regression) and the sizes of input graphs.
• Our comprehensive experiments demonstrate that our proposed HGMN consistently outperforms state-of-the-art graph matching network baselines for both classification and regression tasks. Compared with previous works, our proposed model HGMN is also more robust when the sizes of the two input graphs increase.

heading: 2 PROBLEM FORMULATION
text: In this section, we briefly introduce the problem formulation. Given a pair of graph inputs pG1, G2q, the aim of the graph matching problem we consider in this paper is to produce a graph similarity score y “ spG1, G2q P Y . The graph G1 “ pV 1, E1q is represented as a set of N nodes vi P V 1 with a feature matrix X1 P RNˆd, edges pvi, vjq P E1 (binary or weighted) formulating an adjacency matrix A1 P RNˆN , and a degree matrix D1ii “ ř j A 1 ij . Similarly, the graph G
2 “ 1We release these datasets via this link: https://github.com/runningoat/hgmn_dataset.
Our codes will be released as well upon the acceptance of this paper.
pV 2, E2q is represented as a set of M nodes vi P V 2 with a feature matrix X2 P RMˆd, edges pvi, vjq P E2 (binary or weighted) formulating an adjacency matrix A2 P RMˆM , and a degree matrix D2ii “ ř j A 2 ij . Note that, when performing graph-graph classification task the scalar y is the class labels y “ t´1, 1u; when performing graph-graph regression task the scalar y is the the measure of the similarity score y P r0, 1s. We train a graph matching model based on a set of training triplet of structured input pairs and scalar output score pG11, G21, y1q, ..., pG1n, G2n, Ynq P G ˆ G ˆ Y drawn from some fixed but unknown probability distribution in real applications.

heading: 3 HIERARCHICAL GRAPH MATCHING NETWORKS ARCHITECTURE
text: In this section, we will introduce two key components of our HGMN architecture - Siamese Graph Neural Networks (SGNN) and Multi-Perspective Node-Graph Matching Networks (MPNGMN). We first discuss SGNN for learning the global-level interactions between two graphs and then outline MPNGMN for effectively learning the cross-level node-graph interactions between parts of one graph and one whole graph. Our overall model architecture for HGMN is shown in Fig. 1.

heading: 3.1 SGNN FOR GLOBAL-LEVEL INTERACTION LEARNING
text: The graph-level embeddings contain important information of a graph. Therefore, learning graphlevel interactions between two graphs could be an important component for learning the graph similarity of two graphs. In order to capture the global-level interactions between two graphs, we employ SGNN which is based on Siamese Networks architecture (Bromley et al., 1994), which has achieved great success in many applications such as visual recognition (Bertinetto et al., 2016; Varior et al., 2016) and sentence similarity (He et al., 2015; Mueller & Thyagarajan, 2016). Independently, a similar idea using high-order siamese graph neural networks was presented for brain network analysis (Chaudhuri et al., 2019).
Our SGNN adapts popular Graph Convolution Networks (GCN) (Kipf & Welling, 2016) with siamese neural networks for simplicity. Other variants of graph neural networks such as GraphSAGE (Hamilton et al., 2017) and Gated Graph Neural Networks (Li et al., 2016) can also be used. Our SGNN consists of three components: 1) node embedding layers; 2) graph-level embedding aggregation layers; 3) graph-graph matching and prediction layers.
Node Embedding Layers. We utilize three-layer GCN with the siamese networks to generate node embeddings H l “ thliu tN,Mu i“1 P RtN,Muˆd 1 of both graphs G1 and G2,
H l “ fpX l, Alq “ ReLU ´ sAl ReLU ´ sAl ReLU ´ sAlX lW p0q ¯ W p1q ¯ W p2q ¯ , l “ t1, 2u. (1)
where sAl “ p rDlq´ 12 rAlp rDlq´ 12 is the normalized Laplacian matrix for rAl “ Al`ItN,Mu depending on the graph is G1 or G2, and W piq, i “ t0, 1, 2u are hidden weighted matrices for each layer. Note
that the twin networks share the parameters of GCN when training on the pair of graphs pG1, G2q. The number of GCN layers required depends on the real application graph data. To isolate the effect of overtuning, we choose the three layers after some initial experiments on validation sets.
Graph-level Embedding Aggregation Layers. After we compute the resulting node embeddings H l of each graph from GCN, we need to aggregate these node embeddings to formulate their corresponding graph-level embeddings of each graph.
hlG “ Aggregate ´ thliu tN,Mu i“1 ¯ , l “ t1, 2u. (2)
We employ different aggregation functions such as element-wise max pooling (Max), elementwise max pooling following a transformation by applying a fully connected layer on Hi (FCMax), element-wise mean pooling (Avg), element-wise mean pooling following a transformation by applying a fully connected layer on Hi (FCAvg), and a sophisticated aggregator based on LSTM architecture (Hochreiter & Schmidhuber, 1997a). Note that, among these aggregation functions, the LSTM aggregator is not permutation invariant on a set of node embeddings although LSTM may admit more expressive ability. We adapt LSTMs to operate on these node embeddings by simply applying the LSTMs to a random permutation of the node embeddings.
Graph-Graph Matching and Prediction Layers. After the graph-level embeddings h1G and h2G are computed for the graphs G1 and G2, we then use the resulting graph embeddings to compute the graph similarity score of pG1, G2q. Depending on the specific tasks, we have slightly different ways to calculate the final similarity score. For classification tasks, we simply compute the cosine similarity of two graph-level embeddings,
ry “ spG1, G2q “ cosineph1G,h2Gq (3) where the similarity function s could also be other similarity metric such as Euclidean similarity and dot-product similarity. We find that the cosine similarity function performs generally better across different datasets.
For regression tasks, we first concatenate the two aggregated graph embeddings to rh1G,h2Gs and then employ four standard fully connected layers to gradually project the vector of dimension rh1G,h2Gs down to a scalar of the dimension 1. Since the expected similar score ry should be in range of [0,1], we perform sigmoid function to enforce the final score in this range. We therefore compute the similarity score for graph-graph regression task as following,
ry “ spG1, G2q “ sigmoid ´ MLP ´ rh1G,h2Gs ¯¯ . (4)
For both tasks, we train the SGNN model using mean square error loss function to compare the computed similarity score ry with the groud-truth similarity score y,
L “ 1 n
n ÿ
i“1
´ ry ´ y ¯2 . (5)

heading: 3.2 MPNGMN FOR CROSS-LEVEL NODE-GRAPH INTERACTION LEARNING
text: Although global-level interaction learning could capture the important structural and feature information of two graphs to some extent, it is not enough to capture all important information of two graphs since they ignore other low-level interactions between parts of two graphs. In particular, existing works have considered either global-level graph-graph interactions or low-level node-node interactions, ignoring the rich cross-level interactions between parts of a graph and a whole graph. Inspired by these observations, we propose a novel multi-perspective node-graph matching network to effectively learn the cross-level interaction features. Our MPNGMN model consists of four parts: 1) node embedding layers; 2) node-graph matching layers; 3) aggregation layers; and 4) prediction layers, as shown in Fig. 1. We will illustrate each part in details as follows.
Node Embedding Layers: Similar as described in Sec. 3.1, we choose to employ the three-layer GCN to generate node embeddings H1 “ th1i uNi“1 P RNˆd 1 and H2 “ th2i uMi“1 P RMˆd 1 for graphs G1 and G2. Conceptually, the node embedding layers of MPNGMN (graph encoder) could be chosen to be an independent GCN or a shared GCN with SGNN. As shown in Fig. 1, our MPNGMN shares the same graph encoder with SGNN due to two reasons: i) the shared GCN parameters reduce the number of parameters by half, which helps mitigate possible overfitting; ii) the shared
GCN maintains the consistency of resulting node embeddings for both MPNGMN and SGNN, potentially leading to more aligned global-level interaction and cross-level interaction features. After the node embeddings H1 and H2 have been computed, they will be fed into the following nodegraph matching layers.
Node-Graph Matching Layers: The node-graph matching layer is the key part of our MPNGMN, which can effectively learn the cross-level interactions between parts of a graph and a whole graph. There are generally two steps for this layer: i) calculate the graph-level embedding of a graph; ii) compare the node embeddings of a graph with the associated graph-level embeddings of a whole graph and then produce a similarity feature vector. A simple way to obtain the graph-level embedding of a graph is to perform element-wise mean pooling or max pooling. However, it does not consider any information from the node embedding that the resulting graph-level embedding will compare with later. To build more tight interactions between the two, we calculate the cross-graph attention coefficients between the node vi P V1 in graph G1 and all other nodes vj P V2 in graph G2. Similarly, we calculate the cross-graph attention coefficients between the node vi P V2 in graph G2 and all other nodes vj P V1 in graph G1. These two cross-graph attention coefficients can be computed independently,
αi,j “ fsph1i ,h2j q, j P V2 and βi,j “ fsph2i ,h1j q, j P V1, (6)
where fs is the attention function for computing the similarity score. For simplicity, we use cosine function in our experiments but other similarity metrics can be adopted as well. Then we compute the attentive graph-level embeddings rh1G or rh 2 G P Rd 1 using weighted average of node embeddings of the other graph, rh2G “ ÿ
jPV2 αi,jh
2 j and rh 1 G “
ÿ
jPV1 βi,jh
1 j . (7)
Next, we define our multi-perspective matching function fm to compute the similarity feature vector by comparing two vectors as follows,
rhpiq “ fmpx1,x2,wiq “ fmpx1 dwi,x2 dwiq, i “ 1, . . . , rd (8)
where rh P R rd is a rd-dimension similarity feature vector, andWm “ twiu rd i“1 P Rd 1ˆ rd is a trainable weight matrix and each wi represents a perspective with total rd number of perspectives. Notably, fm could be any similarity function and we use cosine similarity metric in our experiments. It is worth noting that the proposed multi-perspective matching function essentially shares similar spirit with multi-head attention (Vaswani et al., 2017), with the difference that multi-head attention uses rd number of weighted matrices instead of vectors.
Therefore, we can utilize our defined multi-perspective matching function fm to compare the j-th node embeddings of a graph with the corresponding attentive graph-level embeddings to capture the cross-level node-graph interactions. The resulting similarity feature vectors rh1j or rh 2 j P R
rd (w.r.t the node vj in either graph G1 or G2) can thus be computed by
rh1j “ fmph1j , rh2G,Wmq, j P V1 and rh2j “ fmph2j , rh1G,Wmq, j P V2 (9)
After the node-graph matching layers, these newly produced interaction feature matrices rH1 “ trh1i uNi“1 P RNˆ rd and rH2 “ trh2i uMi“1 P RMˆ rd for graphs G1 and G2, are ready to feed them into the aggregation layers.
Aggregation Layers: To aggregate these cross-level interaction feature matrix from the node-graph matching layer, we employ the BiLSTM (Hochreiter & Schmidhuber, 1997b) model to aggregate the unordered feature embeddings,
rhlG “ BiLSTM ´ trhlju tN,Mu j“1 ¯ , l “ t1, 2u. (10)
where rhlG P R2 rd concatenate the last hidden vectors of two directions as the aggregated graph embedding for each graph G1 and G2. Note that other commutative aggregators such as max, average, or attention based aggregation (Veličković et al., 2017) can also be used. However, our extensive experiments showed that BiLSTM aggregator achieved consistent better performance over
other aggregators. Similar LSTM-type aggregator has also been exploited in the previous works (Hamilton et al., 2017; Zhang et al., 2019).
Prediction Layers: After the aggregated graph embeddings rh1G and rh2G are obtained, we then use these two embeddings to compute the similarity score of pG1, G2q. As discussed in Sec.3.1 for graph-graph matching and prediction layers, we use the same prediction layers to predict the similarity score. We also use the same mean square error loss function for the model training. In this way, we can also easily compare the performance difference between SGNN and MPNGMN.

heading: 3.3 DISCUSSIONS ON HGMN MODEL
text: Our model jointly learns graph representations and a graph matching metric function for computing graph similarity in an end-to-end fashion. Our HGMN model combines the advantages of both SGNN and MPNGMN to capture both global-level graph-graph interaction features and novel crosslevel node-graph interaction features between two graphs. Therefore, for final prediction layers of HGMN, we have total six aggregated graph embedding vectors where two of them are h1G and h 2 G from SGNN, and another four are rh1G and rh 2 G from MPNGMN.
The computation complexity of SGNN is Opp|E1| ` |E2|qdd1q, where the most dominant computation is sparse matrix-matrix operations in equation 1. Similarly, the computational complexity of MPNGMN is OpNMd` pN `Mqd1 ` pN `Mqdd1q, where the most computationally extensive operations are in equations 7, 8, and 9. Compared to recently proposed works in (Bai et al., 2019; Li et al., 2019), the computational complexity of them are comparable.

heading: 4 EXPERIMENTS
text: In this section, we systematically investigate the performance of our HGMN model compared with other recently proposed graph matching models on four datasets for both classification and regression tasks.

heading: 4.1 DATASETS, EXPERIMENTS SETTINGS, AND BASELINES

heading: 4.1.1 DATASETS
text: Classification datasets: we evaluate our model on the problem of detecting similarity between two binary functions, which is the heart of many binary security problems, such as software plagiarism, malware detection, and vulnerability search (Feng et al., 2016; Xu et al., 2017; Ding et al., 2019). In particular, two binary functions that are compiled from the same source code but under different settings (architectures, compilers, optimization levels, etc) are semantically similar to each other. To learn similarity from binary functions, we represent those binaries with control flow graphs, in which the graph nodes represent the basic blocks (a basic block is a sequence of instructions without jumps) and edges represent control flow paths between these basic blocks.
Thus, detecting similarity between two binary functions can be cast as the problem of learning the similarity score spG1, G2q between two control flow graphs G1 and G2, where spG1, G2q “ `1 indicates G1 and G2 are similar; otherwise spG1, G2q “ ´1 indicates dissimilar. We prepare
two benchmark datasets generated from two pieces of popular open-source software: FFmpeg and OpenSSL, with statistics shown in Table 1. For each graph in FFmpeg and OpenSSL, we initialize every node with 6 block-level numeric features. More details about the dataset generation and node features can be found in Appendix A.1.1 and Table 7.
Existing graph matching works do not consider the impact of the sizes of graphs on performance. However, we find that the larger the graph size is, the worse the performance is. Therefore, it is important to evaluate the robustness of any graph matching networks in this setting. We thus further split these two datasets into three sub-datasets according to the size range of graph pairs.
Regression datasets: we evaluate our model on learning the graph edit distance (GED) (Zeng et al., 2009; Gao et al., 2010; Riesen, 2015), which measures the structural similarity between two graphs. Formally, GED is defined as the cost of the least expensive sequence of edit operations that transform one graph into another, where an edit operation can be an insertion or a deletion of a node or an edge.
We evaluate our model on two benchmark datasets AIDS700 and LINUX1000 2. The statistic for the datasets is shown in Table 1, and more details can be found in Appendix A.1.2 and Table 7.

heading: 4.1.2 EXPERIMENTAL SETUP
text: Model Settings. For SGNN, we use 3 GCN layers in node embedding layer and each of the GCNs has an output dimension of 100. We use ReLU as the activation function along with a dropout layer after each GCN layer with dropout rate being 0.1. In the graph-level embedding aggregation layer of SGNN, we can employ different aggregation functions (i,e., Max, FCMax, Avg, FCAvg, BiLSTM, etc.) as stated previously in Section 3.1. For MPNGMN, we exploited different aggregation functions similar to SGNN and we found that BiLSTM aggregator consistently performs better than other aggregation functions (see appendix A.4). Thus, for MPNGMN, we always use BiLSTM as our default aggregation function and we make its hidden size equal to the dimension of node embeddings. For MPNGMN, we set the number of perspectives rd to 100, and use another aggregation function BiLSTM to aggregate the output of node-graph matching layer. For each graph, we concatenate the last hidden vector of two directions of BiLSTM, which results in a 200 dimensions vector as the graph embeddings.
Implementation Details. We implement our model using PyTorch 1.1 (Paszke et al., 2017), and train the model using the Adam optimizer (Kingma & Ba, 2014). The learning rate is set to 0.5e-3 for classification tasks and 5e-3 for regression tasks. For classification tasks, we split each dataset into three disjoint subsets of binary functions for training/validation/testing. We train our model by running 100 epochs. At each epoch, we build the pairwise training data as follows. For each graph G in training subset, we obtain one positive pair tpG,Gposq,`1u and a corresponding negative pair tpG,Gnegq,´1u, where Gpos is randomly selected from all control flow graphs that compiled from the same source function as G, and Gneg is selected from other graphs. By default, for each minibatch in one epoch, we train our model with 5 positive and 5 negative pairs. In regression tasks, we first split graphs of each dataset into training, validation, and testing set, and then build the pairwise training/validation/testing data as previous work Bai et al. (2019). We train our model by 10000 iterations with a mini-batch of 128 graph pairs. Each pair is a tuple of tpG1, G2q, su, where s is the ground-truth GED between G1 and G2. Noted that all experiments are conducted on a computer equipped with 2 Intel Xeon 2.2GHz CPU, 256 GB memory and one NVIDIA GTX 1080 Ti GPU.
Baselines. We compared our HGMN against the following baselines: i) SimGNN (Bai et al. (2019)): SimGNN uses GCN to update node features and aggregates them using an attention mechanism. The final pair representation consists of 2 components: One from the interaction between aggregated pair graph features and the other from a pairwise node comparison. ii) GMN (Li et al. (2019)): This method updates node features according to not only current states and messages aggregated from neighborhoods but also information of attentive neighborhoods using cross-graph attention. After updating node features, it aggregates node features in a way similar to that in Gated Graph Neural Network (Li et al. (2016)) to get graph embedding. We have two variants of HGMN: HGMN(FCMax) stands for HGMN model with SGNN(FCMax) and HGMN(BiLSTM) stands for HGMN model with SGNN(BiLSTM).
2These two datasets are released by Bai et al. (2019) and publicly accessible.
Note that, we report the mean and standard deviation of the experimental results of both baseline and our models by repeating the experiments five times.

heading: 4.2 COMPARISON ON GRAPH-GRAPH CLASSIFICATION TASK
text: For the classification task of detecting whether two binary functions are similar or not, we measure the Area Under the ROC Curve (AUC) (Bradley, 1997) of different models for classifying graph pairs of the same test set, and summarize the results in Table 2.
The results show that our models clearly achieve state-of-the-art performance on all 6 sub-datasets for both FFmpeg and OpenSSL datasets. Both MPNGMN and HGMN models show better and more robust performance than the SimGNN and GMN baselines, particularly when the graph size of the two graphs increases. Compared with the SGNN (Max), our models (both MPNGMN and HGMN models) significantly outperform it, demonstrating the benefits of multi-perspective nodegraph matching mechanism that captures the cross-level interactions between node embeddings of a graph and graph-level embeddings of another graph. More experiments compared with SGNN models using other aggregation functions can be found in Appendix A.3.

heading: 4.3 COMPARISON ON GRAPH-GRAPH REGRESSION TASK
text: For the regression task of computing the graph edit distance between two graphs, we evaluate the models using Mean Square Error (mse), Spearmans Rank Correlation Coefficient (ρ) (Spearman, 1904), Kendalls Rank Correlation Coefficient (τ ) (Kendall, 1938), and precision at k (p@k). All results of both AIDS700 and LINUX1000 datasets are summarized in Table 3. In terms of all evaluation metrics, our models consistently outperform both SimGNN and GMN baseline models by a significant margin on both AIDS700 and LINUX1000 datasets. On the other hand, compared with SGNN (Max), our models achieve much better performance (see Appendix A.3 for more experiments compared with other SGNN models). The results highlight the importance of our multiperspective node-graph matching mechanism which could effectively capture cross-level node-graph interactions between parts of a graph and a whole graph.

heading: 4.4 FURTHER STUDY ON THE IMPACT OF DIFFERENT ATTENTION FUNCTIONS
text: We perform a further study on the impact of different attention functions for our proposed MPNGMN model. In particular, as we discussed in Sec. 3.2, the proposed multi-perspective matching function shares similar spirits with multi-head attention (Vaswani et al., 2017). Therefore, it is interesting to compare both attention functions in terms of AUC scores for graph-graph classification tasks. Interestingly, our proposed multi-perspective attention mechanism consistently outperforms these results of multi-head attention mechanism by quite a large margin. We suspect that our proposed multi-perspective attention uses vectors attention weights which may significantly reduce the potential overfitting. We also performed a study on the impact of the number of the perspectives on the performance and our model is not sensitive with this hyperparameter (see the appendix A.5).

heading: 4.5 FURTHER STUDY ON THE IMPACT OF DIFFERENT GNNS
text: We finally investigate the impact of different GNNs adopted by node embedding layers of our MPNGMN model for both classification and regression tasks. Following the same settings of our previous experiments, we only replace GCN with three variants: GraphSAGE (Hamilton et al., 2017), GIN (Xu et al., 2018a), and GGNN (Li et al., 2016), whose output dimensions are kept the same with GCN (i.e, 100) in our experiments. Note that, we do not fine-tune any hyper-parameter of the three GNN models, and their default hyper-parameters of these three GNNs are listed in Appendix A.2.2.
Table 5 and Table 6 present the results of GCN versus GraphSAGE/GIN/GGNN in MPNGMN for the classification and regression tasks, respectively. For all datasets of classification and regression tasks, the performance of different GNNs is quite similar. It indicates that our model is not sensitive to the choice of GNN models in node embedding layers. Moreover, we can see from Table 5 that MPNGMN models using GGNN perform even better than our default MPNGMN using GCN on both FFmpeg and OpenSSL datasets for the classification task. It is also observed from Table 6 that MPNGMN models using GIN also outperform our default model using GCN on LINUX1000 dataset for the regression task. These observations show that our model can be further improved by adopting more advanced GNN models or choosing the most appropriate GNN models according to different application tasks.

heading: 5 RELATED WORKS
text: Graph Neural Networks. Recently graph neural networks have been proven to be extremely effective and achieved promising results on various graph-structured based prediction tasks (Gao et al., 2019; Chen et al., 2019a). The main goal of graph neural networks is to learn node-level representations or (sub)graph-level representations for graph-structured data. There is a large body of GNN models (Scarselli et al., 2008; Li et al., 2016; Kipf & Welling, 2016; Hamilton et al., 2017; Veličković et al., 2017; Xu et al., 2018a) that have been proposed to learn node representations. With the learned node representations, various tasks on graphs can be performed such as node classification and link prediction (Veličković et al., 2017; Zhang & Chen, 2018). In addition to learning node representation, some studies try to extend pooling operations to GNNs (Ying et al., 2018; Gao & Ji, 2019; Lee et al., 2019; Ma et al., 2019). These pooling operations are expected to learn scaled-down graph representations from node representations, and can be trained in an end-to-end fashion. Recent works also exploit extending sequence-to-sequence model using bidirectional GNN for developing graph-to-sequence models in order to cope with graph inputs and show promising performance improvement (Xu et al., 2018b;c; Chen et al., 2019b) in various natural language processing tasks.
Conventional Graph Matching. In general, graph matching can be categorized into exact graph matching and error-tolerant graph matching. Exact graph matching aims to find a strict correspondence between two (in large parts) identical graphs being matched, while error-tolerant graph matching allows matching between completely nonidentical graphs (Riesen, 2015). In real-world applications, the constraint of exact graph matching is too rigid, and thus a large number of work has been proposed to solve the error-tolerant graph matching problem, which is usually quantified by a specific similarity metric. In fact, the matching similarity metrics can be defined by some measure of structure similarity like Graph Edit Distance (GED) (Gao et al., 2010), Maximum Common Subgraph (MCS) (Bunke, 1997), or even more coarse binary similarity, according to different application backgrounds. For GED and MCS, both of them are well-studies NP-hard problems (Bunke, 1997; McGregor, 1982), and thus suffer from exponential computational complexity and huge memory requirements for exact solutions in practice (Zeng et al., 2009; Blumenthal & Gamper, 2018).
Graph Similarity Computation and Graph Matching Networks. A popular line of research of graph matching focuses on developing approximations for graph similarity computations, in which most of them focus on improvements for better efficiency in computation (Gao et al., 2010; Zeng et al., 2009; Riesen, 2015; Wu et al., 2019; Yoshida et al., 2019). However, our solution is a learnable model based on GNN to approximate graph similarity in terms of GED and binary similarity for pairwise graph-based data.
The closely relevant work to our solution are two GNN based models: GMN (Li et al., 2019) and SimGNN (Bai et al., 2019). GMN directly updates the node representations of one graph by adding artificial attention-based connections for another graph. SimGNN considers the graph-level representation similarity as well as the histogram features from a pairwise node-level comparison to learn the graph similarity. However, these two models fail to capture different perspectives of graphstructured data between the pairs of graphs.

heading: 6 CONCLUSION AND FUTURE WORK
text: In this paper, we presented a novel Hierarchical Graph Matching Network (HGMN) for computing the graph similarity between any pair of graph-structured objects. Our model jointly learned graph embeddings and a data-driven graph matching metric for computing graph similarity in an end-to-end fashion. We further proposed a new multi-perspective node-graph matching network for effectively learning cross-level interactions between two graphs beyond low-level node-node and global-level graph-graph interactions. Our extensive experimental results correlated the superior performance compared with state-of-the-art baselines on both graph-graph classification and regression tasks.
One interesting future direction is to adapt our proposed HGMN model for solving different realworld applications such as unknown malware detection, text matching and entailment, and knowledge graph question answering.

heading: A APPENDIX

heading: A.1 DATASETS

heading: A.1.1 CLASSIFICATION DATASETS
text: It is noted that one source code function, after compiled with different settings (architectures, compilers, optimization levels, etc), can generate various binary functions with different control flow graphs.
For FFmpeg dataset, we prepare the corresponding control flow graphs dataset as the benchmark dataset to detect binary function similarity. First, we compile FFmpeg 4.1.4 using 2 different compilers gcc 5.4.0 and clang 3.8.0, and 4 different compiler optimization levels (O0-O3), and generate 8 different binaries files. Second, these 8 generated binaries are disassembled using IDA Pro,3 which can produce CFGs for all disassembled functions. Finally, for each basic block in CFGs, we extract 6 block-level numeric features as the initial node representation based on IDAPython (a python-based plugin in IDA Pro).
OpenSSL is built from OpenSSL (v1.0.1f and v1.0.1u) using gcc 5.4 in 3 different architectures (x86, MIPS, and ARM), and 4 different optimization levels (O0-O3). The OpenSSL dataset we evaluate is previously released by (Xu et al., 2017) and public available4 with prepared 6 block-level numeric features.
Overall, for both FFmpeg and OpenSSL, each node in the control flow graphs are initialized with 6 block-level numeric features: # of string constants, # of numeric constants, # of total instructions, # of transfer instructions, # of call instructions, and # of arithmetic instructions.

heading: A.1.2 REGRESSION DATASETS
text: Instead of directly computing the GED between two graphs G1 and G2, we try to learn a similarity score spG1, G2q, which is the normalized exponential of GED in the range of p0, 1s. To be specific, spG1, G2q “ exp´normGEDpG1,G2q, normGEDpG1, G2q “ GEDpG
1,G2q p|G1|`|G2|q{2 , where |G
1| or |G2| denotes the number of nodes of G1 or G2, and normGEDpG1, G2q or GEDpG1, G2q denotes the normalized/un-normalized GED between G1 and G2.
We employ both AIDS700 and LINUX1000 released by (Bai et al., 2019), which are public available.5 Each dataset contains a set of graph pairs as well as their ground-truth GED scores, which are computed by exponential-time exact GED computation algorithm A˚ (Hart et al., 1968; Riesen et al., 2013). As the ground-truth GEDs of another dataset IMDB-MULTI is provided with in-exact approximation, we thus do not consider this dataset in our experiments.
AIDS700 is a subset of AIDS dataset, a collection of AIDS antiviral screen chemical compounds from Development Therapeutics Program (DTP) in the National Cancer Institute (NCI).6 Originally, AIDS dataset contains 42687 chemical compounds, where each of them can be represented as a graph with atoms as node and bonds as edges. To avoid calculating the ground-truth GED between two graphs with a large number of nodes, Bai et al. (2019) create the AIDS700 dataset that contains 700
3IDA Pro disassembler, https://www.hex-rays.com/products/ida/index.shtml. 4https://github.com/xiaojunxu/dnn-binary-code-similarity. 5https://github.com/yunshengb/SimGNN. 6https://wiki.nci.nih.gov/display/NCIDTPdata/AIDS+Antiviral+Screen+Data
graphs with 10 or fewer nodes. For each graph in AIDS700, every node is labeled with the element type of its atom and every edge is unlabeled (i.e., bonds features are ignored).
LINUX1000 is also a subset dataset of Linux that introduced in Wang et al. (2012). The original Linux dataset is a collection of 48747 program dependence graphs generated from Linux kernel. In this case, each graph is a static representation of data flow and control dependency within one function, with each node assigned to one statement and each edge describing the dependency between two statements. For the same reason as above that avoiding calculating the ground-truth GED between two graphs with a large number of nodes, the LINUX1000 dataset used in Bai et al. (2019) is randomly selected and contains 1000 graphs with 10 or fewer nodes. For each graph in LINUX1000, both nodes and edges are unlabeled.
For both classification and regression datasets, Table 7 provides more detailed statistics.

heading: A.2 MORE EXPERIMENTAL SETUP FOR MODELS

heading: A.2.1 MORE EXPERIMENTAL SETUP FOR BASELINE METHODS
text: We modified some experimental settings in baselines to fit specific tasks. Detailed settings are given in the following.
SimGNN: For regression task, we set batch size to 128 and trained the model for 10000 iterations. We used MSE loss as the training loss and set learning rate to 1.0 ˆ 10´3. Validation starts at the 9000-th iteration and is performed every 50 iterations. The best model among all the validation runs is used for the testing phase. As for the model structure, we used 3 GCNs in the first place to propagate node features, whose output dimension is set to 64, 64, and 32 respectively. Then we applied an ANPM layer implemented by author of SimGNN to perform graph-level interaction. The pair feature vector generated by this layer then passes 4 fully-connected layers and finally a 1-D scalar, which is the predicted similarity score. For classification task, we modified the training settings so now the model is trained in epoches with the same learning rate and the batch size becomes 5. Validation is carried out every iteration and the best model is saved at this time. For training loss, we used Cross-Entropy loss and applied the same learning rate as that in regression task. The model structure is the same as that in regression task except that the final output dimension of fully-connected layers is 2, the softmax of which is the predicted label and is compared with ground truth label in one-hot encoding to get the Cross-Entropy loss.
GMN: For classification task, we trained the model for 100 epoches where validation is carried out per epoch. We set batch size to 10 and learning rate to 1.0ˆ10´3. We set node feature dimension to 32 and graph representation dimension to 128. As for mode structure, we used 1-layer MLP as node encoder which encodes the initial node features to node states hp0qi . Then there are 5 propagation layers with the same structure as mentioned in the original paper (Li et al. (2019)). Besides, in this task we applied the pairwise loss based on hamming similarity defined by the author in paper. For regression task, we concatenated representation vectors of 2 graphs in the pair and passed it to a 4-layer MLP to get similarity score. As for training, we set batch size to 128 and used the same training strategy as that in the regression task of SimGNN. MSE loss is applied in this task for learning. Other settings remain the same as in classification task.

heading: A.2.2 MORE EXPERIMENTAL SETUP FOR DIFFERENT GNNS
text: When performing experiments to see how different GNNs affect performance of MPNGMN model, we only replace GCN with GraphSAGE, GIN, and GGNN using the geometric deep learning library - PyTorch Geometric7. More specifically, for GraphSAGE, we used a 3-layer GraphSAGE GNN with their output dimensions all set to 100. For GIN, we used 3 GIN modules with a 1-layer MLP with output dimension 100 as the learnable function. For GGNN, we used 3 one-layer propagation models to replace the 3 GCNs in our original setting and also set their output dimensions to 100.

heading: A.3 MORE EXPERIMENTS OF THE SGNN MODEL WITH DIFFERENT AGGREGATION FUNCTIONS FOR BOTH CLASSIFICATION & REGRESSION TASKS
text: To further compare our models with SGNN models, we train and evaluate several SGNN models with different aggregation functions, such as Max, FCMax, Avg, FCAvg, and BiLSTM. Both classification results and regression results are summarized in Table 8 and Table 9. For both classification and regression tasks, our models show statistically significantly improvement over all SGNN models with different aggregation functions, which indicates the advantage of multi-perspective node-graph matching network that adopted in our model.

heading: A.4 MORE EXPERIMENTS OF THE MPNGMN MODEL WITH DIFFERENT AGGREGATION FUNCTIONS FOR BOTH CLASSIFICATION & REGRESSION TASKS
text: We investigate the impact of different aggregation functions adopted by Aggregation Layers of the MPNGMN model for both classification and regression tasks. Following the default and same settings of previous experiments, we only change the aggregation layer of MPNGMN and use five possible aggregation functions: Max, FCMax, Avg, FCAvg, LSTM, and BiLSTM. As can be observed from Table 10 and Table 11, BiLSTM offers superior performance over all datasets of both classification and regression tasks in terms of most evaluation metrics. Therefore, we take BiLSTM as the default aggregation function for MPNGMN, and fix it for the MPNGMN part in HGMN models.

heading: A.5 MORE EXPERIMENTS OF THE MPNGMN MODEL WITH DIFFERENT NUMBER OF PERSPECTIVES FOR THE CLASSIFICATION TASK
text: We further investigate the impact of different number of perspectives adopted by the NodeGraph Matching Layer of the MPNGMN model for classification tasks. Following the default and same settings of previous experiments, we only change the number of perspectives (i.e., rd “ 50{75{100{125{150) of MPNGMN. As shown in Figure 2 and Table 12, when the graph size is [3, 200] and [20, 200] (more training samples), our model performance is not sensitive to the number of perspectives (from 50 to 150). When the graph size is [50,200] (fewer training samples), the variance of the model becomes relatively larger than these on [3, 200] and [20, 200]. However, when we used more perspectives (like 150), the variance of the model reduced significantly.

Review summaries:
In this paper, a hierarchical graph matching network, which considers both graph-graph interaction and node-graph interaction, is proposed. Specifically, the graph-graph interaction is modeled through graph level embeddings learned by GCN with pooling layers. While node-graph interaction is modeled using node embedding learned by GCN and attentive graph embedding aggregated from node embedding.