Hierarchical Graph Matching Networks for Deep Graph Similarity Learning
Authors: Xiang Ling
Lingfei Wu
Saizhuo Wang
Tengfei Ma
Fangli Xu
Chunming Wu
Shouling Ji
Venue:  (2020)
Keywords: Graph Neural Network
Graph Matching Network
Graph Similarity Learning

Abstract: While the celebrated graph neural networks yields 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 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 comprehensive experiments demonstrate that our proposed HGMN consistently outperforms state-of-the-art graph matching networks baselines for both classification and regression tasks. 

Under review as a conference paper at ICLR 2020
HIERARCHICAL GRAPH MATCHING NETWORKS FOR DEEP GRAPH SIMILARITY LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
While the celebrated graph neural networks yield effective representations for in- dividual nodes of 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 Hierarchical Graph Matching Network (HGMN) for computing the graph similarity between any pair of graph-structured objects. Our model jointly learns graph representations and graph matching metric function for computing graph similarity in an end-to-end fashion. The proposed HGMN model consists multi-perspective 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 comprehensive experiments demonstrate that our proposed HGMN consistently outperforms state-of-the-art graph matching network baselines for both classifica- tion and regression tasks.
INTRODUCTION
Learning a general similarity metric between arbitrary pairs of graph-structure objects is one of the key challenges in machine learning. Such learning problems often arise in a variety of applica-
tions, ranging from graph similar searching in graph-based database (Yan & Han 2002). Fewshot
3D Action Recognition (Guo et al.] 2018), unknown malware detection (Wang et al. 2019). and
promising selection in automatic theory proving (Wang 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 sim- llarity. 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 with- out 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 (G', (G²,G²) E G G and the similarity score y V, based on set of training triplet of structured input pairs and scalar output score (G), (1) (G), G2.ynl 3n) G G x 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 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 al.)
2017 Veličković et al. (017), or pooling the learned node embeddings into graph vector for graph classification (Ying et al.] 20018: Ma 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 decision. This approach is useful since graph- level 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

---

Under review as a conference paper at ICLR 2020
embeddings of two graphs. Very recently, few of attempts have been made to take into account low- level interactions either by considering the histogram information of wode-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 effectively learn richer cross-level interactions between parts of graph and whole graph.
Inspired by these observations, in this paper, we propose Hierarchical Graph Matching Network (HGMN) for computing the graph similarity between any pair of graph-structured objects. Our model jointly learns graph representations and graph matching metric function for computing graph similarity in an end-to-end fashion. The proposed HGMN model consists of novel multi- perspective node-graph matching network for effectively learning cross-level interactions between parts of a graph and 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-grap classification or graph-graph regression tasks, respectively.
Recently proposed works only compute graph similarity by considering either graph-graph classi- fication problem (with labels Y (-1,1) (Li et al. 2019), or graph-graph regression problem (with similarity score Y [0, 1] (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 real application together with a previously released dataset by (Xu et al., 2017) for graph-gram graph classification [ 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 hierarchical graph matching network (HGMN) for computing the graph simi- larity between any pair of graph-structured objects. Our HGMN model jointly learns graph representations and 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 node embeddings of graph and a corre- sponding 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 out- performs state-of-the-art graph matching network baselines for both classification and re- gression tasks. Compared with previous works, our proposed model HGMN is also more robust when the sizes of the two input graphs increase.
2 PROBLEM FORMULATION
In this section, we briefly introduce the problem formulation. Given a pair of graph inputs (G', G2), the aim of the graph matching problem we consider in this paper is produce a graph similarity score = s(G G2) E y. The graph G = (V3, 1 ) is represented as set of N nodes v e V with a feature matrix X E Nx edges (v, 12) E' (binary or weighted) formulating an adjacency matrix A E NxN, and a degree matrix D Σ, Aly- Similarly, the graph G²
We release these datasets via this link: https://at thub. com/ runni www.tinngat///oe leiggaat/hgn_dataseeeeee Our codes will he released as well upon the acceptance of this paper.
2

---

Under review as a conference paper at ICLR 2020
Aggregate
fm hj
GCN
BiLSTM
Cosine() or Sigmoid(FC)
Ag
Bi
GCN
BiLSTM
Predicted Similarity Score
Aggregate
Node Embedding
Matching and Aggregation
Graph Embedding
Figure Overall Model Architecture of Hierarchical Graph Matching Networks (HGMN)
(V2,E7 is represented as set of M nodes E V with a feature matrix X E RMxx, edges (ve, U2) E E² (binary or weighted) formulating an adjacency matrix A² E RMM and a degree matrix D Σ, A Note that, when performing graph-graph classification task the sealar y the class labels y = {-1, when performing graph-graph regression task the scalar y is the the measure of the similarity score y [o, 1]. We train graph matching model based set of training triplet of structured input pairs and scalar output score (G), G7, 3/1,,... (G), G²,, Yn) E G x G drawn from some fixed but unknown probability distribution in real applications.
3 HIERARCHICAL GRAPH MATCHING NETWORKS ARCHITECTURE
In this section, we will introduce two key components of our HGMN architecture Siamese Graph Neural Networks (SGNN) and Multi-Perspeetin 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.
3.1 SGNN FOR GLOBAL HOUBAL-LEVEER LEVEL INTERACTION LEARNING
The graph-level embeddings contain important information of a graph. Therefore, learning graph- level interactions between two graphs could be important component for learning the graph simi- larity 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 al. 2015 Mueller & Thyagarajan (016)) Independently, sim-
ilar idea using high-order siamese graph neural networks was presented for brain network analysis
(Chaudhuri et 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 Graph- SAGE (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 generate node embeddings H [b])
(NN E R(N.M)xd of both graphs GH and G²,
H' = f(x,, A ReLU A' ReLU A' ReLU A'x'w(0) w() w(()) 1= (1,2) (I)
where A' (D') ( is the normalized Laplacian matrix for A' A' + (N.ary depending on the graph is G G and W á (0, 1, are hidden weighted matrices for each layer. Note
3

---

Under review as a conference paper at ICLR 2020
that the twin networks share the parameters of GCN when training the pair of graphs (G', G.). 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' of each graph from GCN, we need to aggregate these node embeddings to formulate their corre- sponding graph-level embeddings of each graph.
b'c Aggregate (1))) - (1,2).
We employ different aggregation functions such as element-wise max pooling (Max), element- wise max pooling following a transformation by applying a fully connected layer on H' (FCMax), element-wise mean pooling (Avg), clement-wise mean pooling following transformation by ap- plying a fully connected layer on H' (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 hy and ha are computed for the graphs G' and G², we then use the resulting graph embeddings to compute the graph similarity score of (G', G²)). 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,
-= ( ,G) = cosine(h hg))
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 [b] h and then employ four standard fully connected layers to gradually project the vector of dimension [hgs h2g] down to a scalar of the dimension 1. Since the expected similar score ÿ 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.
ÿ sG' GP) sigmoid (MLP (Ihd hrl)).
(4)
For both tasks, we train the SGNN model using mean square error loss function to compare the computed similarity score with the groud-truth similarity score y.
(5)
n
3.2 MPNGMN FOR CROSS-LEVEL NODE-GRAPH INTERACTION LEARNING
Although global-level interaction learning could capture the important structural and feature infor- mation 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 graph and a whole graph. Inspired by these observations, we propose a novel multi-pprsspective vode-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 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 //2 [h]),²² R xd' and H! [h
M for
Ji=
graphs G¹ and G². Conceptually, the node embedding layers of MPNGMN (graph encoder) could be chosen to be independent GCN shared GCN with SGNN. As shown in Fig. I our MP- NGMN shares the same graph encoder with SGNN due to two reasons: i) the shared GCN parame- ters reduce the number of parameters by half, which helps mitigate possible overfitting: ii) the shared
4

---

Under review as a conference paper at ICLR 2020
GCN maintains the consisteney of resulting node embeddings for both MPNGMN and SGNN, po- tentially leading to more aligned global-level interaction and cross-level interaction features. After the node embeddings H' and H² have been computed, they will be fed into the following node- graph 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 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 obtain the graph-level embed- ding of a graph is to perform element-wiss 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 tross-graph attention coefficients between the node 0 E V in graph G and all other nodes V/ E V2 in graph G Similarly, we calculate the cross-graph attention coefficients between the node U/ V in graph G and all other nodes by E yi in graph G'. These two cross- cross-graph attention coefficients can be computed independently,
(1 fohh,, h3), j V2 and B = fo JeV',
where f. 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 h/c or ha Rd using weighted average of node embeddings of the other graph,
hig
Σ Carhh and h
Bi
JEV
Next, we define our multi perspeccivee matching function fm to compute the similarity feature vector by comparing two vectors as follows,
Ti(i)= fm(( X2, w.) fm O w., X2 2 w.), i = I,...,d d
(8)
where h E Rd is a d-dimension similarity feature vector, and W., (wi) R xd is trainable weight matrix and each w; represents perspective with total d 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 nulti-perspective matching function essentially shares similar spirit with multi-head attention (Vaswani et al. 2017), with the difference that multi-head attention uses d number of weighted matrices instead of vectors.
Therefore, we can utilize our defined multi- multi-persspective 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 h3 or hi E Rd (w.r.t the node uj in either graph G or G2) can thus be computed by
i = fm (h). G6 Wm). jE V1 and h3 =m (h3. b/ Wn), jE E V/2
(9)
After the node-graph matching layers, these newly produced interaction feature matrices 1 (h. 1 E Nxd and 2 (h2) R Mxd for graphs G¹ and G², are ready feed them into
the aggregation layers.
To aggregate these cross-level interaction feature matrix from the mode-graph matching layer, we employ the BiLSTM (Hochreiter & Schmidhuber 1997b) model to aggregate the unordered feature embeddings,
Aggregation Layers:
h' BiLSTM (MMM) 1= (1.2).
(10)
where li/3 E R2d concatenate the last hidden vectors of two directions as the aggregated graph embedding for each graph G' and G Note that other commutative aggregators such max, average, or attention based aggregation (Velicović et al.) 2017) can also used. However, our extensive experiments showed that BTM aggregator achieved consistent better performance over
5

---

Under review as a conference paper at ICLR 2020
other aggregators. Similar LSTM-type aggregator has also been exploited in the previous works (Hailtoon et al. 2017: Zhang et al. 2019).
Prediction Layers: After the aggregated graph embeddings h3 and hy are obtained, we then use these two embeddings compute the similarity score of (G', As discussed in Sec 3.1 for graph-graphe 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.
3.3 DISCUSSIONS ON HGMN MODEL
Our model jointly learns graph representations and 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 capture both global-level graph-graph interaction features and novel cross- level 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 h and h from SGNN, and another four are li and hig from MPNGMN.
The computation complexity of SGNN is O( + E Ddd"), where the most dominant compu- tation is sparse matrix-matrix operations in equation
Similarly, the computational complexity of MPNGMN is O Md (N MMdd' + (N + M)ddd') ) where the most computationally extensive
operations are in equations and 9 Compared to recently proposed works in (Bai et al. 2019
Li al. 2019), the computational complexity of them are comparable.
EXPERIMENTS
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 regres- sion tasks.
Table 1: Summary statistics of datasets for both classification & regression tasks.
Sub- datasets
# of
# of
AVG #
AVG # of Edges
AVG # of
Init Feature
Tasks
Datasets
Graphs
Functions
of Nodes
AVG Degrees
Dimensions
[3, 200]
83008
10376
18.83
27.02
2.59
FFmpeg
[20, 200]
31696
7668
51.02
75.88
2,94
6
classif-
[50, 200]
10824
3178
90.93
136.83
3.00
ication
[3, 200]
73953
4249
15.73
21.97
2.44
OpenSSI.
[20, 200]
1,800
1073
44.89
67.15
2.95
6
[50, 200]
4308
338
83.68
/127.75
regre-
AIDS700
700
8.90
8.80
1.96)
29
ssion
LINUX1000
1000
7.58
6.94
1.81
4.1 DATASETS, EXPERIMENTS SETTINGS, AND BASELINES
4.1.1 DATASETS
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 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 the problem of learning the similarity score s(G", G²) between two control flow graphs G and G2, where s(G', .G²) = +1 indicates G1 and G similar; otherwise s(G', G²) -1 indicates dissimilar. We prepare

---

Under review as a conference paper at ICLR 2020
two benchmark datasets generated from two pieces of popular open-source software: FFmpeg and OpenSSL, with statistics shown in [able 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 and Table
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 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.teoiixxA...... A.1.2 and Table 7
4.1.2 EXPERIMENTAL SETUP
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 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, BiL- STM, 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 default aggregation function and we make its hidden size equal to the dimension of node em- beddings. For MPNGMN, we set the number of perspectives à to 100, and use another aggregation function BiL.TM to aggregate the output of node-graph matching layer. For each graph, we con- catenate the last hidden vector of two directions of BiL.STM, which results in a 200 dimensions vector as the graph embeddings.
Implementation Details. We implement our model using PyTorch 1.1 (Paske et al.) 2017). and train the model using the Adam optimizer (Kingma & Bal 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 We train model by
into three disjoint subsets of binary functions for running 100 epuchs. At each epoch, we build the pairwise training data as follows. For each graph G in training subset, obtain one positive pair {G, GPos), +1} and corresponding negative pair {(G, G -1), where Gpos is randomly selected from all control flow graphs that compiled from the same source function as G, and Gmeg is selected from other graphs. By default, for each mini- batch 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// validattion/eestnng data as previous work Bai et al. 2019). We train our model by 10000 iterations with mini-batch of 128 graph pairs. Each pair is a tuple of {(G', G)), where s the ground-truth GED between G1 and G². Noted that all experiments are conducted on computer equipped with 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. (011)))
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 aggre- gated pair graph features and the other from a pairwise node comparison. ii) GMN (Li 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 way similar to that in Gated Graph Neural Network (Li et al.] (2016)) to get graph embedding. We have two variants of HGMN: HGMN((CMax) stands for HGMN model with SGNN(FCMax) and HGMN(BiLSTM) stands for HGMN model with SGNN(BILSTM).
"These datasets are released by Bai al. (019) and publicly accessible.
7

---

Under review as a conference paper at ICLR 2020
Note that, report the mean and standard deviation of the experimental results of both baseline and our models by repeating the experiments five times.
4.2
COMPARISON ON GRAPH-GRAPH CLASSIFICATION TASK
Table 2: Summary of classification results in terms of AUC scores (%).
FFmpeg
OpenSSL
Model
[3, 200]
[20, 200]
[50, 200]
[3, 200)
[20, 200]
[50, 200]
SimGNN
95.38=0.76
94.31=1.01
93.45=0.54
95.96=0.31
93.58=0.82
94.25=0.85
GMN
9..15=0.62
95.92=1.38
94.76:0.45
96.43:0.61
93.03=3.81
93.91
SGNN (Max)
93.92=0.07
93.82=0.28
1..19+1.39
91.07=0.10
88,94=0.47
12.10=
MPNGMN
97.73=0.11
98.29=0.21
96.81:0.96
96.56=0.12
97.60:0.29
92.89E1.31
HGMN (FCMax)
9.007=0.06
98.29:0.10
9..83
9..27:0.24
97.59
95.58: 1.13
HGMN (BiLSTM)
97,56=0.38
98.12=0.04
97.16=0.53
96.90=0.10
97.31=1.07
95.87=0.88
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
The results show that our models clearly achieve oftte-of-the-art performance 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 penlpipprsseetivee node- graph 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
4.3 COMPARISON ON GRAPH-GRAPH REGRESSION TASK
Table 3: Summary of regression results on AIDS700 and LINUX1000.
Datasets
Model
msc (10 3)
P
p@10 10
p
SimGNN
1.376+0.06
0.824+0.009
0.665=0.011
0.400=0.023
0.489=0.024
GMN
4.610+0.365
0.672+0.036
0.497=0.032
0.200=0.018
0.263+0.018
SGNN (Max)
1.822+0.149
0.765=0.005
0.588=0.004
0.289-0.016
0.373+0.012
AIDS700
MPNGMN
1.19140.048
0.90410.003
0.749-0.005
0.465
0.538
HGMN (FCMax)
1.205=0.039
0.90410.002
0.749=0.003
0.457=0.014
0.532:0.016
HGMN (BiLSTM)
1.169:0.036
0.905
0.751=0.003
0.456=0.019
0.539
SimGNN
2.479
0.912+0.031
0.791=0.046
0.635=0.328
0.650=0.283
GMN
2.571+0.519
0.906+0.023
0.763=0.035
0.888=0.036
0.856+0.040
SGNN (Max)
11.832006998
0.566+0.022
0.404=0.017
0.226=0.10m 106
0.492+0. 190
LINUX 1000
MPNGMIN
1.56110.020
0.94510.002
0.814_0.003
0.74310.085
10.06
HGMN (FCMax)
1.57540.627
0.94610.019
0.817=0.034
0.807
0.78440. 108
HGMN (BiLSTM)
0.439:0.143
0.98510.005
0.919=00016
0.955=0.011
0.943=0.014
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 (p) (Spearman 1904], Kendalls Rank Correlation Coefficient (r) (Kendall 1938). and precision results of both AIDS700 and LINUX1000 datasets are summarized in Table In terms of all eval- uation metrics, our models consistently outperform both SimGNN and GMN baseline models by a significant margin 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 ex- periments compared with other SGNN models). The results highlight the importance of our multi- perspective node- graph matching mechanism which could effectively capture cross-level node-graph interactions between parts of a graph and whole graph.
(p@k). All
8

---

Under review as a conference paper at ICLR 2020
Table 4: Classification results of Multi- PeatiipPesspectiees versus Multi-Heads in terms of AUC scores
FFmpeg
OpenSSL
Model
[3. 200]
[20. 200]
[50. 200]
[00]
[20. 200]
[50. 200]
Multi- Perspectives (d 100)
97.7310.11
98.2910.21
96.8110.96 96.56.10.12
97.6010.29
92.8911.11
Multi Heads (K~ 6) 91.18+5.91
77.49+5.21
68.15=6.97 92.81+5.21 85,43+5.76 56.87+7.53
4.4 FURTHER STUDY ON THE IMPACT OF DIFFERENT ATTENTION FUNCTIONS
We perform a further study on the impact of different attention functions for our proposed MP- NGMN model. In particular, as we discussed in Sec. 3.2 the proposed
matching function shares similar spirits with multi-head attention (Vaswani et al.) 2017). Therefore, it is in- teresting to compare both attention functions in terms of AUC scores for graph-graph classification tasks. Interestingly, our proposed multi- perspectveee attention mechanism consistently outperforms these results of multi-head attention mechanism by quite a large margin. We suspect that our pro- posed 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
4.5 FURTHER STUDY ON THE IMPACT OF DIFFERENT GNNS
Table 5: Classification results of different GNNs in terms of AUC scores (%)
FFmpeg
OpenSSL.
Model
[3, (00)
[20, 200]
[50, 200)
[3, 200]
[20, 200]
[50, 200]
MPNGMN-GCN (Our)
97.73=0.11
98.2910.21
96.81
96.5610.12
97.6010.29
92.8911.31
MPNGMN GraphSAGE
97.31
98.2110.13
97.8810.15
16.1310.30
97.3010.72
93,6613.87
MPNGMN- GININ
97.9710.08
98.0610.22
94.6614.01
96.9810.20
97.42.1.44
92.2912.23
MPNGMN-GGN
98.42:0.41
99.77=0.07
97.93-1.18
99.35=00066
98.51+1.04
94.17+7.74
Table Regression results of different GNNs on AIDS700
and LINUX1000.
Datasets
Model
msse (10 ))
P
p@10
p@20
MPNGMN GCN (Our)
1.191=0.048
0.904=0.003
0.749:0.005
0.465=0.011
0.538=0.007
AIDS
MGNNMMI-(GrapiiSS....
1.27510.054
0.901 10.006
0.74510.008
0.44810.016
0.53310.014
700
MPNGMIN-
1.36710.085
0.88910.008
0.72910.010
0.40011.022
0.49210.021
MPNGMN- (GGNN)
1.87010.082
0.87110.004
0.70610.000
0.38810.015
0.45710.017
MPNGMN-GRS (Our)
1.561:0.020
0.045
0.814
0.743:0.085
0.741
#0.086
LINUX
MIPNGMN-GraphSSAEE
2.784
0.915=0.0019
0.767
0.682:0.18
0.693
1000
MPNGMN-GIN
1.126=0.164
0.963=00000
0.858:0.015
0.792:0.068
0.821=0.035
MPNGMN-GGNN
2.068#0.991
0.938+0.028
0.815=0.055
0.628+0.189
0.654:0.176
We finally investigate the impact of different GNNs adopted by node embedding layers of our MP- NGMN model for both classification and regression tasks. Following the same settings of our pre- vious experiments. we only replace GCN with three variants: GraphSAGE (Hamilron 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 typer-parameter of the three of these three GNNs are listed in Appendix A.2.2
GNN models, and their default
Table 5 and Table 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 quite similar. It indicates that our model 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 model can be further improved by adopting more advanced GNN models or choosing the most appropriate GNN models according to different application tasks.

---

Under review as a conference paper at ICLR 2020
5 RELATED WORKS
Graph Neural Networks. Recently graph neural networks have been proven to be extremely effec- tive and achieved promising results on various graph-structured based prediction tasks (Gao al.)
2019 Chen et al., 2019a). The main goal of graph neural networks is to learn node-level repre- sentations or (sub) graph-leel representations for
data. There is a large body of GNN models (Scarselli et al., 2008 Li et al., 2016: Kipf & Welling 2016: Hamilton et al.) [2017] Veličković 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 classifica- tion and link prediction (Veličković 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 end-to-end fashion. Recent works also exploit extending scquence-to-sequene sequence model using bidirectional GNN for developing graph-to-sequence models in order cope with graph inputs and show promising performance im- provement (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 corre- spondence 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 mea- sure of structure similarity like Graph Edit Distance (GED) (Gao et al.) (0TO), Maximum Common Subgraph (MCS) (Bunke 1997). or even more coarse binary similarity, according to different appli- cation 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 mem- ory 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 developing approximations for graph similarity computations, in which most of them focus on improvements for better efficiency in computation (Gao et al.) 2010 Zeng al. 2009 Riesen| 2015 Wu al. 2019 Yoshida et al. 2019). However, our solution 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 rep- resentation similarity as well as the histogram features from pairwise node-level comparison to learn the graph similarity. However, these two models fail to capture different perspectives of graph- structured data between the pairs of graphs.
6 CONCLUSION AND FUTURE WORK
In this paper, we presented a novel Hierarchical Graph Matching Network (HGMN) for comput- ing 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 new pusti-pprspecctiee 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-an baselines both graph-graph classification and regres- sion tasks.
One interesting future direction is to adapt our proposed HGMN model for solving different real- world applications such as unknown malware detection, text matching and entailment, and knowl- edge graph question answering.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang- Simgnn: neu- ral network approach fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, 384-392, ACM, 2019.
Luca Bertinetto, Jack Valmadre, Joao F Henriques, Andrea Vedaldi, and Philip HS Torr. Fully- convolutional siamese networks for object tracking. European conference on computer vision, pp. 850-865. Springer, 2016.
David Blumenthal and Johann Gamper. On the exact computation of the graph edit distance. Pattern Recognition Letters, 2018.
Andrew Bradley. The use of the area under the roc curve in the evaluation of machine learning algorithms. Pattern Recognition, 1997.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verifi- cation using a" siamese" time delay neural network. In Advances in neural information processing systems, pp. 737-744, 1994.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42 2017.
Horst Bunke. On relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters, 18(8):689-694, 1997.
Horst Bunke and Gudrun Allermann. Inexact graph matching for structural pattern recognition. Pattern Recognition Letters, 144):245-255 1983.
Tibério S Caetano, Julian McAuley, Li Cheng, Quoc V Lc, and Alex J Smola. Learning graph matching. IEEE transactions on pattern analysis and machine intelligence, 31(6):1048-1058 2009.
Ushasi Chaudhuri, Biplab Banerjee, and Avik Bhattacharya. Siamese graph convolutional network for content based remote sensing image retrieval. Computer Vision and Image Understanding. 184:22-30. 2019.
Yu Chen, Lingfei Wu, and Mohammed J Zaki. Graphflow: Exploiting conversation flow with graph neural networks conversational machine comprehension. arXiv preprint arXiv: 100.0099000009 2019a.
Yu Chen, Lingfei Wu, and Mohammed J Zaki. Reinforcement learning based graph-to-sequence model for natural question generation. arXiv preprint arXiv: 04942, 2019b.
Steven HH Ding, Benjamin CM Fung, and Philippe Charland. Asm2vec: Boosting static represen-
tation robustness for binary clone search against code obfuscation and compiler optimization. In IEEE Symposium on Security and Privacy (S&P) 2019, 2019.
Qian Feng, Rundong Zhou, Chengeheng Xu, Yao Cheng, Brian Testa, and Heng Yin. Scalable graph-based bug search for firmware images. In Proceedings of the 2016 ACM SIGSAC Confer- ence on Computer and Communications Security, 2016.
Hongyang Gao and Shuiwang Ji. Graph u-nets. arXiv preprint 1rXiv:1905.0517. 2019.
Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and applications, 13(1):113-129, 2010.
Yuyang Gao, Lingfei Wu, Houman Homayoun, and Liang Zhao. Dyngraph2seq: cenamic-graph-ae sequence interpretable learning for health stage prediction in online health forums. arXiv preprint arXiv: 084977 08497, 2019.
Michelle Guo, Edward Chou, De-An Huang, Shuran Song, Serena Yeung, and Li Fei-Fei. Neural graph matching networks for fewshot 3d action recognition. In Proceedings of the European Conference Computer Vision (ECCV), pp. 653-669, 2018.

---

Under review as a conference paper at ICLR 2020
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, 2017.
Peter E Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions Systems Science and Cybernetics, 4(2):100-107, 1968.
Hua He, Kevin Gimpel, and Jimmy Lin. Multi-perspective sentence similarity modeling with con-
volutional neural networks. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 1576-15866 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997a.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1997b.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 1938.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXivv:412.69880 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv:1609.02907 2016.
Junhyum Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. arXiv preprint 1XXv:1904.08082. 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference Learning Representations, 2016.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 100.033433. 2018.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. /CMI., 2019.
Yao Ma, Suhang Wang, Charu C Aggarwal, and Jiliang Tang. Graph convolutional networks with eigenpooling, arXiv preprini arXiv:1904. 13107,, 2019.
James J McGregor. Backtrack search algorithms and the maximal common subgraph problem. Software: Practice and Experience, 12(1):23-344 1982.
Jonas Mueller and Aditya Thyagarajan. Siamese recurrent architectures for learning sentence simi- larity. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch, 2017.
Kaspar Riesen. Structural pattern recognition with graph edit distance. In Advances in computer vision and patlern recognition. Springer, 2015.
Kaspar Riesen, Xiaoyi Jiang, and Horst Bunke. Exact and inexact graph matching: Methodology and applications. In Managing and Mining Graph Data, pp. 217-247. Springer, 2010.
Kaspar Riesen, Sandro Emmenegger, and Horst Bunke. novel software toolkit for graph edit distance computation. In International Workshop on Craph-Based Representations in Pattern Recognition, pp. 142-151. Springer, 2013.
Bidisha Samanta, Abir De, Niloy Ganguly, and Manuel Godez-Rodriguez. Designing random graph models using variational autoencoders with applications chemical design. arXiv preprint arXiv:1802.05283. 2018
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEFE Transactions Neural Networks, 20(1):61-80. 2008
12

---

Under review as a conference paper at ICLR 2020
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. arXiv preprint arXiv:1802.034: 2018.
C Spearman. The proof and measurement of association between two things. American Journal of Psychology, 1904.
Julian R Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 23(1): 31-42, 1976.
Rahul Rama Varior, Mrinal Haloi, and Gang Wang. Gated siamese convolutional neural network architecture for human re-identification. In European conference on computer vision, pp. 791- 808. Springer, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 2017.
Mingzhe Wang, Yihe Tang, Jian Wang, and Jia Deng. Premise selection for theorem proving by deep graph embedding. Advances in Neural Information Processing Systems, pp. 2017.
Shen Wang, Zhengzhang Chen, Xiao Yu, Ding Li, Jingchao Ni, Lu-An Tang, Jiaping Gui. Zhichun Li, Haifeng Chen, and Philip S Yu. Heterogeneous graph matching networks for unknown mal- ware detection. In Proceedings of International Joint Conference Artificial Intelligence, 2019.
Xiaoli Wang, Xiaofeng Ding, Anthony KH Tung, Shanshan Ying, and Hai Jin. An efficient graph indexing method. In 2012 IEEE 28th International Conference on Data Engineering, 2012.
Lingfei Wu, lan En-Hsu Yen, Zhen Zhang, Kun Xu, Liang Zhao, Xi Peng, Yinglong Xia, and Charu Aggarwal. Scalable global alignment graph kernel using random features: From node embedding to graph embedding. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1418-1428, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00822 2018a.
Kun Xu, Lingfei Wu, Zhiguo Wang, and Vadim Sheinin. Graph2seq: Graph sequence learning with attention-based neural networks. arXiv preprint arXiv: 1804.08040000 00023, 2018b.
Kun Xu, Lingfei Wu, Zhiguo Wang, Mo Yu, Liwei Chen, and Vadim Sheinin. Exploiting rich syntactic information for semantic parsing with graph-to-sequence model. arXiv preprint arXiv:1808.07624, 2018c.
Xiaojun Xu, Chang Liu, Qian Feng, Heng Yin, Le Song, and Dawn Song. Neural network-based graph embedding for cross-platform binary code similarity detection. In Proceedings of the 2017 ACM SIGSAC Conference Computer and Communications Security, 2017.
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In Proceedings of IEEE International Conference on Data Mining, pp. 721-724. IEEE, 2002.
Zhitao Ying. Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-4810, 2018
Tomoki Yoshida, Ichiro Takeuchi, and Masayuki Karasuyama. Learning interpretable metric be- tween graphs: Convex formulation and computation with graph mining. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 1026-1036. ACM, 2019.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovee. Graphrnn Generating realistic graphs with deep auto-regressive models. arXiv preprint
2018.
13

---

Under review as a conference paper at ICLR 2020
Zhiping Zeng, Anthony KH Tung, Jianyong Wang. Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1):25-36) 2009.
Chuxu Zhang. Dongjin Song. Chao Huang, Ananthram Swami, and Nitesh V. Chawla. Heteroge- neous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-511 5175,, 2018.
A APPENDIX
A.I DATASETS
A.1.1 CLASSIFICATION DATASETS
is noted that one source code function, after compiled with different settings (architectures, com- pilers, optimization levels, etc), 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 using 2 different com- pilers gec 5.4.0 and clang 3.8.0, O, and different compiler optimization levels (00-03), and generate 8 different binaries files. Second, these 8 generated binaries are disassembled using IDA Pro which can produce CFGs for all disassembled functions. Finally, for each basic block in CFGs, we extract block-level numeric features as the initial node representation based on IDAPython (a python-based plugin IDA Pro).
OpenSSL is built from OpenSSL (v1.0.1f and v1.0.lu) using gec 5.4 in 3 different architectures (x86, MIPS, and ARM), and different optimization levels (00-03). The OpenSSL dataset we evaluate is previously released by (Xu et al. 2017) and public available 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.
A. 1.2 REGRESSION DATASETS
Instead of directly computing the GED between two graphs G' and G², we try to learn similarity
score s(G', G2), which is the normalized exponential of GED the range of (0, 1]. To specific,
exp normGED(c ,G)), normGED(G' GP) ([G' 1/22 where |G'| or |G?|
GEDIG G2)
denotes the number of nodes of GD or G2, and gormGED(G G2) or GED(G" G²) denotes the normalized/un-nonntn normalized GED between G² and G².
We employ both AIDS700 and LINUX1000 released by (Bai et al. 2019), which are public avail- able Fl Each dataset contains set of graph pairs as well their ground-trute 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) 2 Originally, AIDS dataset contains 42687 chemical compounds, where each them can be represented as a graph with atoms as node and bonds edges. To avoid calculating the ground-truth GED between two graphs with a large number of nodes, Bai et al. (009 create the AIDS700 dataset that contains 700
IDA Pro htt.a//sssaatttaaaa/////...aaaaa
shtml
14

---

Under review as a conference paper at ICLR 2020
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 subset datasct 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 static representation of data flow and control dependency within one func- tion, 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 be- tween two graphs with a large number of nodes, the LINUX 1000 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.
Table 7: Summary statistics of datasets for both classification & regression tasks.
Sub-
of
# of
# of Nodes
# of Edges
AVG # of Degrees
Tasks
Datasets
datasets
Graphs
Functions
(Min/Max/AVG)
(Min/Max/AVG)
(Min/Max//AGG)
[3, 200]
83008
10376
(3/200/18.8)
(2/332/27.02)
(1.25/4.332.55)
FFmpeg
[20, 200]
31696
7668
(20/200/5
(20/352/75.88)
(1.90/4.33/2.994
classif-
[50, 200]
10824
3178
(50/200/90.93)
(52/352/136.83)
(2.00/4.33/3.00
ication
[3. 200]
73953
4249
(3/200/15.73)
(1/376/21.77)
(0.12/3.95/2..44)
OpenSSL
[20, 200]
15800
1073
(20/200/44.89)
(2/376/67.15)
(0.12/3.955)) 95/2.95)
[50, 200]
4308
338
(50/200/83,66 68.6
(52/376/127.75)
2..00/3.5533.4 .44)
regre-
AIDS700
700
(2/10/8.90) 90)
(1/14/8.80 80)
(1.00/2.80) 20W/288/T..5 1966)
ssion
LINUX1000
1000
(4/10/7.58)
(3/13/6,94)
(1.50/2.6071.)
A.2
MORE EXPERIMENTAL SETUP FOR MODELS
1.2.1 MORE EXPERIMENTAL SETUP FOR BASELINE METHODS
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 x 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 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 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- Pnoos-- 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 2, the softmax of which is the predicted label and is compared with ground truth label in one-hot encoding to get the Cross-Entrope 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 x 10-3, We set node feature dimension to 32 and graph representation dimension to 128. As for mode structure, we used I-layer MLP as node encoder which encodes the initial node features to node states h 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 l-yer 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.
15

---

Under review as a conference paper at ICLR 2020
A.2.2 MORE EXPERIMENTAL SETUP FOR DIFFERENT GNNS
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 Geometrid More specifically, for GraphSAGE, we used a 3-layer GraphSAGE GNN with their output dimensions all set 100. For GIN, we used GIN modules with a l-layer MLP with output dimension 100 as the learnable function. For GGNN, we used 3 one-layer propagation models to replace the GCNs in our original setting and also set their output dimensions to 100.
A.3 MORE EXPERIMENTS OF THE SGNN MODEL WITH DIFFERENT AGGREGATION FUNCTIONS FOR BOTH CLASSIFICATION & REGRESSION TASKS
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 classi- fication results and regression results are summarized in T 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 pertpipersee node-graph matching network that adopted in our model.
Table 8: Classification results of SGNN models with different aggregation functions VS. our MP- NGMN and HGMN models in term of AUC scores (%).
FFmpeg
OpenSSL
Model
[00]
[20, 200]
[50, 200]
[3, 200]
[20, 200]
[50, 200]
SGNN (BiLSTM)
9.192:0.13
97.62:0.13
96.35:0.33
95.24=0.06
93.99:0.62 96.30=0.27
SGNN (Max)
93.92=0.07
93.82+0.28
15.19+1.39
91.07=0.10
88.94=0.47
82.10=0.51
SGNN (FCMax)
95.37=0.04
96.29+0.14
95.98+0.32
92.64=0.15
93.79=0.17
93.21=0.82
SGNN (Avg)
95.61=0.05
96.09+0.05
16.70+0.13
92.89=0.09
93.90=0.24
14.12+0.35
SGNN (FCAvg)
95.18-0.03
95.7410.15
16.4310.16
92.70=0.09
93.72.0.19
93,49
MPNGMN
97.7320.11
98.2910.21
96.8110.96
96.56:0.12
97.60 0.29
92.8911.31
HGMN (Max)
97.44_0.32
97.8410.40
97.2210.36
94.7711.80
97.4410.26
94.0611.60
HGMN (FCMax)
98.07
98.2910.10
97.8310.11
96.8710.24
97.5910.24
9..5811.13
HGMN (BiLSTM)
97.56=0.38
98.12+0.04
97.16+0.53
96.90=0.10
97.31=1.07
95.87=0.88
Table 9: Results of SGNN models with different aggregation functions VS. our MPNGMN and HGMN models on AIDS700 and LINUX1000.
Datasets
Model
mae (10 )
P
p@10 10
p@20
SGNN (BiLSTM)
1.422+0.044
0.881 00.005
0.718=0.006
0.376=0.020
0,472+0.014
SGNN (Max)
2.822+0.149
0.765+0.005
0.588=0.000
0.289=0.016
0.373+0.012
SGNN (FCMax)
3.114+0.114
0.735+0.009
0.554=0.008
0.278=0.021
0.364=0.017
AIDS700
SGNN (Avg)
1.553
0.87610.002
0.712-0.002
0.35310.007
0.44410.012
SGNN (FCAvg)
1658100066
0.85710.007
0.68910.008
0.30510.018
0.39910.021
MPNGMN
1.19110.048
0,90410.003
0.749-0.005
0.46510.011
0.538 007
HGMN (Max)
1.21010.020
0.90040.002
0.743=0.003
0.461=0.012
0.534
HGMN (FCMax)
1. 1.205+0.039
0.904=0.002
0.749=0.003
0.457=0.014
0.532+0.0116
HGMN (BiL.TTM)
1.169:0.036
0.005
0.751=0.003
0.456=0.019
0.519
SGNN (BiLSTM)
2.140 1.668
0.93510.050
0.825 100
0.9781
0.965 10.007
SGNN (Max)
11 1..99
0.56610.022
0.404_0.017
0.22610.10 106
0,492.0.1 190
SGNN (FCMax)
10.795
0.36210.021
0.252_0.015
0.23910.000
0.24110.0000
LINUX
SGNN (Avg)
0.933+0.012 0.343+
0.790=0.017
0.778=0.048
0.8100
1000
SGNN (FCAvg)
3.2118
0.909+0.004
0.757=0.008
0.831+0.163
0.813+0.119
MPNGMN
1.56100.02
0.945=0.002
0.814=0.003
0.085
0.741 #0.086
HGMN (Max)
1. 1.54400.066
0.96240.003
0.850=0.000
0.877
4..037
HGMN (FCMax)
1.575:0.627
0.946#0.019
0.817=0.034
0.784 00.17
HGMN (BiLSTM)
0.439:0.143
0.985=0.005
0.919=0.016
0.955=0.011
0.943=0.014
16

---

Under review as a conference paper at ICLR 2020
A.4 MORE EXPERIMENTS OF THE MPNGMN MODEL WITH DIFFERENT AGGREGATION FUNCTIONS FOR BOTH CLASSIFICATION & REGRESSION TASKS
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 set- tings 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 ob- served from Table I0 and Table TT] 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.
Table 10: Classification results of MPNGMN models with different aggregation functions in term of AUC scores (%)
FFmpeg
OpenSSL
Model
[3, 200]
[20, 200]
150, 200]
[3, 200]
[20, 200]
[50, 200]
MPNGMN (Max)
73.74+8.30
13.85=1.76
77.72+2.07
67.1442.70
63.31+3.29
63.02+2.77
MPNGMN (FCMax)
97.28+0.08
96.61=0.17
96.65=0.30
95.
96.08=0.48
95.90.0.73
MPNGMN (Avg)
8..92.1.07
83.2914.49
8..5211.42
80.1014.59
70.8113.41
66.9414.33
MPNGMN (FCAvg)
95.9340.21
73.90-0.70
94.22=0.06
93.3810.80
94.52+1.16
94.71:1.86
MPNGMN (LSTM)
97.1610.42
97.02=0.99
84.65.6.73
96.3010.69
97.51
89,4118.40
MPNGMN (BiLSTM)
97.7310.11
98.29
96.81:0.96
96.5610.12
97.60
12.8911.31
models Table 11: Regression results of MPNGMN models with different aggregation functions AIDS700 and LINUX1000.
Datasets
Model
msse (10
p
p@ 10
p@20
MPNGMN (Max)
2.378=0.244
0.813=0.015
0.642+0.013
0.578=0.199
0.583=0.169
MPNGMN (FCMax)
2.220
0.808 145
0.656=0.122
0.425=0.078
0.50410.064
MPNGMN (Avg)
1.52410.161
0.88010.010
0.717=0.012
0.408=0.044
0.474=0.027
AIDS 700
MPNGMN (FCAvg)
1.281
0.89510,006
0.737+0.008
0.453=0.015
0.52710.016
MPNGMN (LSTM)
1.290=0.037
0.895=0.004
0.737=0.005
0.448=0.007
0.520=0.012
MPNGMN(BBLSSMM)
L191:
0.904:0.003
0.005
0.065
0.538
MPNGMN (Max)*
16.921+0.000
MPNGMN (FCMax)
0.793=0.262
0.829+00006
0.665+0.011
0.764=0.170
0..16
MPNGMN (Avg)
4.05010.594
0.88810,008
0.71910.012
0.53610.112 0.501
LINUX 1000
MPNGMN (FCAvg)
6.95310.195
0.89710.004
0.73610.005
0.4
129
MPNGMN (LSTM)
1.53510.096
0.94510.004
0.695 0.813+0.007
0.698
MPNGMN(BBLSTM)
0.945=0.002 0.020
0. 0.743=0.085 0.814=0.003
00.066
As all duplicated experiments running on this setting do not converge in their training processes, their corresponding result metrics cannot be calculated.
A.5 MORE EXPERIMENTS OF THE MPNGMN MODEL WITH DIFFERENT NUMBER OF PERSPECTIVES FOR THE CLASSIFICATION TASK
We further investigate the impact of different number of perspectives adopted by the Node- Graph 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., d 50/75/ 1100 00012/1150 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 150). When the graph size [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.
17

---

Under review as a conference paper at ICLR 2020
100
AUC (%)
AUC
95
95-
FFmpeg [3. 200]
OpenSSL 200]
FFmpeg [20, 200]
OpenSSL [20, 200]
FFmpeg [50, 200)
OpenSSL (50, 200]
number of perspectives
number of perspectives
(a) classification performance of FFmpeg
(b) classification performance of OpenSSL
Figure 2: (a) and (b) show the impact of the number of perspectives classification performance of FFmpeg and OpenSSL respectively.
Table 12: Classification results of different number of perspectives in terms AUC scores(%).
FFmpeg
OpenSSL
Model
[3,
[20, 200]
200]
[3. 200]
200, 200]
[30, 200]
MPNGMN (d 50)
98.11=0.14
97.76=0.14 96.93=0.52
0.13
97.0320.84
93.38+3.03
MPNGMN (d -75)
97.99-0.09
97.94=0.14
97.41=0.05
97.09:0.25
98.66+0.11
92.10+4.37
MPNGMN (d = 1100
97.73-0.11
98.29-0.21
9..9
96.56:0.12
97.6010.29
92.8911.31
MPNGMN (d 125)
98.10-0.03
98.06=0.08
97.26=0.36
96.73:0.33
98.67:0.11
96.03+2.08
MPNGMN (d -150)
98.32-0.05
98.11=0.07
97.92-0.09
96.50+0.31
98.0440.03
97.1310.36
18


Reviews:
[{"review_id": "rJe9pCD6tH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nSome concerns about the paper are as follows:\n\n1)\tThe novelty of the paper is incremental. The major contribution of the paper lies in the propose of multi-perspective matching function $f_m()$, which is somewhat similar to the Neural Tensor Networks proposed in [1] and utilized in [2] Although, in [2], the Neural Tensor Network is used to measure the similarity between graph-level embeddings.\n2)\tSome of the technical details of the paper is not clearly presented or well explained. \na.\tIn Eq. (7), attentive graph-level embeddings are calculated using weighted average of its node embeddings. However, it is not clear which node $i$ from the other graph should be used to calculate the weights (\\alpha_{I,j}, \\beta_{i,j}). Furthermore, it is also not clear why the attention score should solely base on a single node from the other graph rather than the information of the entire graph. \nb.\tIn Eq. (10), it would be better if the authors could provide more motivations about using Bi-LSTM aggregator. Especially, the embeddings to be aggregated are unordered. What are the two directions in Bi-LSTM in this case? What is the benefit of using Bi-LSTM as aggregator compared with LSTM aggregator or other aggregators? \n\nSome other questions to be clarified:\n1)\tWhy different similarity score functions are adopted for the classification task and the regression task? \n2)\tFor the classification task, the mean squared error loss is adopted. Why not using other more commonly used loss for classification task? \n\nSuggestions:\n\nIt would be better if the authors could empirically show the effectiveness of the Bi-LSTM aggregator.\n\nIt would be helpful if the authors could conduct some investigation on how the number of perspectives affect the performance of the model.\n\n[1] Reasoning With Neural Tensor Networks for Knowledge Base Completion\n[2] SimGNN: A Neural Network Approach to Fast Graph Similarity Computation\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1lZD04oYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a network learning similarity between graphs. In particular, the proposed method focuses on node-graph cross-level interaction which has not been considered by other neural net studies. The performance is evaluated by two datasets on classification and regression tasks respectively.\n\nOverall, the basic idea would be reasonable, and the architecture is clearly described. Any of my comments below are not critical concerns.\n\nThe network considers node-graph interaction, but in general, subgraph-graph interaction can be considered. Rationale that only focusing on node-graph interaction is not mentioned.\n\nThe authors repeatedly mention that the proposed method jointly learns representation and similarity. Is the learned representation can be used for any purpose? Since it depends on a counterpart of the input pair, the representation is seemingly difficult to use.\n\nThe experiments show superior performance of the proposed methods, but the datasets are only two for each tasks. In particular, since graph classification is a popular task, evaluation on a variety of benchmarks would be more convincing. \n\nA baseline with some graph kernel can be informative.\n\nShowing an example of graph pairs, in which cross-level interaction is indispensable to appropriately evaluate similarity, would be convincing.\n\nA related paper being missed would be \n'Yoshida, et al. Learning Interpretable Metric between Graphs: Convex Formulation and Computation with Graph Mining, SIGKDD 2019'. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJgjovGVqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an architecture for (supervised) learning a similarity score between graphs through a series of layers for node embedding, node-graph matching, aggregated graph embedding, and finally prediction.\n\nThe evidence for preferring this architecture over existing one is entirely empirical -- based on experiments on four datasets.  The properties of the graphs used in the experiments are not clear: How many edges do they have on average?What is the exponent of their degree distribution on average? How many triangles do they have?  How much does the graph structure contribute to learning?   What happens if one just trained on the features of nodes?  \n\nThe lack of any theoretical reasons for using this architecture over others (perhaps by linking it to the cut norm of the graphs) or insights as to when and on what types of graphs this architecture performs well reduces the significant of this paper.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes an architecture to learn a similarity metric for graph matching. The architecture uses node-graph information in order to learn a more expressive, multi-level similarity score. The hierarchical approach is empirically validated on a limited set of graphs for which pairwise matching information is available and is shown to outperform other methods for classification and regression tasks.

The reviewers were divided in their scores for this paper, but all noted that the approach was somewhat incremental and empirically motivated, without adequate analysis, theoretical justification, or extensive benchmark validation. 

Although the approach has value, more work is needed to support the method fully. Recommendation is to reject at this time.
Decision: Reject