Title: GRAPH MATCHING NETWORKS FOR LEARNING THE SIMILARITY OF GRAPH STRUCTURED OBJECTS Anonymous authors Paper under double-blind review

Abstract: This paper addresses the challenging problem of retrieval and matching of graph structured objects, and makes two key contributions. First, we demonstrate how Graph Neural Networks (GNN), which have emerged as an effective model for various supervised prediction problems defined on structured data, can be trained to produce embedding of graphs in vector spaces that enables efficient similarity reasoning. Second, we propose a novel Graph Matching Network model that, given a pair of graphs as input, computes a similarity score between them by jointly reasoning on the pair through a new cross-graph attention-based matching mechanism. We demonstrate the effectiveness of our models on different domains including the challenging problem of control-flow-graph based function similarity search that plays an important role in the detection of vulnerabilities in software systems. The experimental analysis demonstrates that our models are not only able to exploit structure in the context of similarity learning but they can also outperform domain-specific baseline systems that have been carefully hand-engineered for these problems.

1. INTRODUCTION:

Graphs are natural representations for encoding relational structures that are encountered in many domains. Expectedly, computations defined over graph structured data are employed in a wide variety of fields, from the analysis of molecules for computational biology and chemistry (Gilmer et al., 2017; Yan et al., 2005) , to the analysis of knowledge graphs or graph structured parses for natural language understanding.

In the past few years graph neural networks (GNNs) have emerged as an effective class of models for learning representations of structured data and for solving various supervised prediction problems on graphs. Such models are invariant to permutations of graph elements by design and compute graph node representations through a propagation process which iteratively aggregates local structural information (Scarselli et al., 2009; Li et al., 2015; Gilmer et al., 2017) . These node representations are then used directly for node classification, or pooled into a graph vector for graph classification. Problems beyond supervised classification or regression are relatively less well-studied for GNNs.

In this paper we study the problem of similarity learning for graph structured objects, which appears in many important real world applications, in particular similarity based retrieval in graph databases. One motivating application is the computer security problem of binary function similarity search, where given a binary which may or may not contain code with known vulnerabilities, we wish to check whether any control-flow-graph in this binary is sufficiently similar to a database of known-vulnerable functions. This helps identify vulnerable statically linked libraries in closed-source software, a recurring problem (CVE, 2010; 2018) for which no good solutions are currently available. Figure 1 shows one example from this application, where the binary functions are represented as control flow graphs annotated with assembly instructions. This similarity learning problem is very challenging as subtle differences can make two graphs be semantically very different, while graphs with different structures can still be similar. A successful model for this problem should therefore (1) exploit the graph structures, and (2) be able to reason about the similarity of graphs both from the graph structures as well as from learned semantics. In order to solve the graph similarity learning problem, we investigate the use of GNNs in this context, explore how they can be used to embed graphs into a vector space, and learn this embedding model to make similar graphs close in the vector space, and dissimilar graphs far apart.

One important property of this model is that, it maps each graph independently to an embedding vector, and then all the similarity computation happens in the vector space. Therefore, the embeddings of graphs in a large database can be precomputed and indexed, which enables efficient retrieval with fast nearest neighbor search data structures like k-d trees (Bentley, 1975) or locality sensitive hashing (Gionis et al., 1999) .

We further propose an extension to GNNs which we call Graph Matching Networks (GMNs) for similarity learning. Instead of computing graph representations independently for each graph, the GMNs compute a similarity score through a cross-graph attention mechanism to associate nodes across graphs and identify differences. By making the graph representation computation dependent on the pair, this matching model is more powerful than the embedding model, providing a nice accuracy-computation trade-off.

We evaluate the proposed models and baselines on three tasks: a synthetic graph edit-distance learning task which captures structural similarity only, and two real world tasks -binary function similarity search and mesh retrieval, which require reasoning about both the structural and semantic similarity. On all tasks, the proposed approaches outperform established baselines and structure agnostic models; in more detailed ablation studies, we found that the Graph Matching Networks consistently outperform the graph embedding model and Siamese networks.

To summarize, the contributions of this paper are: (1) we demonstrate how GNNs can be used to produce graph embeddings for similarity learning;

(2) we propose the new Graph Matching Networks that computes similarity through cross-graph attention-based matching;

(3) empirically we show that the proposed graph similarity learning models achieve good performance across a range of applications, outperforming structure agnostic models and established hand-engineered baselines.

2. RELATED WORK:

Graph Neural Networks and Graph Representation Learning The history of graph neural networks (GNNs) goes back to at least the early work by Gori et al. (2005) and Scarselli et al. (2009) , who proposed to use a propagation process to learn node representations. These models have been further developed by incorporating modern deep learning components (Li et al., 2015; Veličković et al., 2017; Bruna et al., 2013) . A separate line of work focuses on generalizing convolutions to graphs (Bruna et al., 2013; Bronstein et al., 2017) . Popular graph convolutional networks also compute node updates by aggregating information in local neighborhoods (Kipf & Welling, 2016) , making them the same family of models as GNNs. GNNs have been successfully used in many domains (Kipf & Welling, 2016; Veličković et al., 2017; Battaglia et al., 2016; 2018; Niepert et al., 2016; Duvenaud et al., 2015; Gilmer et al., 2017; Dai et al., 2017; Li et al., 2018; Wang et al., 2018a; b) . Most of the previous work on GNNs focus on supervised prediction problems (with exceptions like (Dai et al., 2017; Li et al., 2018; Wang et al., 2018a) ). The graph similarity learning problem we study in this paper and the new graph matching model can be good additions to this family of models.

Graph Similarity Search and Graph Kernels Graph similarity search has been studied extensively in database and data mining communities (Yan et al., 2005; Dijkman et al., 2009) . The similarity is typically defined by either exact matches (full-graph or sub-graph isomorphism) (Berretti et al., 2001; Shasha et al., 2002; Yan et al., 2004; Srinivasa & Kumar, 2003) or some measure of structural similarity, e.g. in terms of graph edit distances (Willett et al., 1998; Raymond et al., 2002) . Most of the approaches proposed in this direction are not learning-based, and focus on efficiency.

Graph kernels are kernels on graphs designed to capture the graph similarity, and can be used in kernel methods for e.g. graph classification (Vishwanathan et al., 2010; Shervashidze et al., 2011) . Popular graph kernels include those that measure the similarity between walks or paths on graphs (Borgwardt & Kriegel, 2005; Kashima et al., 2003; Vishwanathan et al., 2010) , kernels based on limited-sized substructures (Horváth et al., 2004; Shervashidze et al., 2009) and kernels based on sub-tree structures (Shervashidze & Borgwardt, 2009; Shervashidze et al., 2011) . Graph kernels are usually used in models that may have learned components, but the kernels themselves are handdesigned and motivated by graph theory. They can typically be formulated as first computing the feature vectors for each graph (the kernel embedding), and then take inner product between these vectors to compute the kernel value. One exception is (Yanardag & Vishwanathan, 2015) where the co-occurrence of graph elements (substructures, walks, etc.) are learned, but the basic elements are still hand-designed. Compared to these approaches, our graph neural network based similarity learning framework learns the similarity metric end-to-end.

Distance Metric Learning Learning a distance metric between data points is the key focus of the area of metric learning. Most of the early work on metric learning assumes that the data already lies in a vector space, and only a linear metric matrix is learned to properly measure the distance in this space to group similar examples together and dissimilar examples to be far apart (Xing et al., 2003; Weinberger & Saul, 2009; Davis et al., 2007) . More recently the ideas of distance metric learning and representation learning have been combined in applications like face verification, where deep convolutional neural networks are learned to map similar images to similar representation vectors (Chopra et al., 2005; Hu et al., 2014; Sun et al., 2014) . In this paper, we focus on representation and similarity metric learning for graphs, and our graph matching model goes one step beyond the typical representation learning methods by modeling the cross-graph matchings.

Siamese Networks Siamese networks (Bromley et al., 1994; Baldi & Chauvin, 1993) are a family of neural network models for visual similarity learning. These models typically consist of two networks with shared parameters applied to two input images independently to compute representations, a small network is then used to fuse these representations and compute a similarity score. They can be thought of as learning both the representations and the similarity metric. Siamese networks have achieved great success in many visual recognition and verification tasks (Bromley et al., 1994; Baldi & Chauvin, 1993; Koch et al., 2015; Bertinetto et al., 2016; Zagoruyko & Komodakis, 2015) . In the experiments we adapt Siamese networks to handle graphs, but found our graph matching networks to be more powerful as they do cross-graph computations and therefore fuse information from both graphs early in the computation process. Independent of our work, recently (Shyam et al., 2017 ) proposed a cross-example attention model for visual similarity as an alternative to Siamese networks based on similar motivations and achieved good results.

3. DEEP GRAPH SIMILARITY LEARNING:

Given two graphs

G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 )

, we want a model that produces the similarity score s(G 1 , G 2 ) between them. Each graph G = (V, E) is represented as sets of nodes V and edges E, optionally each node i ∈ V can be associated with a feature vector x i , and each edge (i, j) ∈ E associated with a feature vector x ij . These features can represent, e.g. type of a node, direction of an edge, etc. If a node or an edge does not have any associated features, we set the corresponding vector to a constant vector of 1s. We propose two models for graph similarity learning: a model based on standard GNNs for learning graph embeddings, and the new and more powerful GMNs. The two models are illustrated in Figure 2 .

3.1. GRAPH EMBEDDING MODELS:

Graph embedding models embed each graph into a vector, and then use a similarity metric in that vector space to measure the similarity between graphs. Our GNN embedding model comprises 3 parts: (1) an encoder, (2) propagation layers, and (3) an aggregator. Encoder The encoder maps the node and edge features to initial node and edge vectors through separate MLPs:

EQUATION

Propagation Layers A propagation layer maps a set of node representations {h

(t) i } i∈V to new node representations {h (t+1) i

} i∈V , as the following:

EQUATION

Here f message is typically an MLP on the concatenated inputs, and f node can be either an MLP or a recurrent neural network core, e.g. RNN, GRU or LSTM (Li et al., 2015) . To aggregate the messages, we use a simple sum which may be alternatively replaced by other commutative operators such as mean, max or the attention-based weighted sum (Veličković et al., 2017) . Through multiple layers of propagation, the representation for each node will accumulate information in its local neighborhood.

Aggregator After a certain number T rounds of propagations, an aggregator takes the set of node representations {h (T )

i } as input, and computes a graph level representation h G = f G ({h

EQUATION

which transforms node representations and then uses a weighted sum with gating vectors to aggregate across nodes. The weighted sum can focus only on the important nodes, it is more powerful than a simple sum and also works significantly better empirically.

After the graph representations h G1 and h G2 are computed for the pair (G 1 , G 2 ), we compute the similarity between them using a similarity metric in the vector space, for example the Euclidean, cosine or Hamming similarities.

Note that without the propagation layers (or with 0 propagation steps), this model becomes an instance of the Deep Set (Zaheer et al., 2017) or PointNet (Qi et al., 2017) , which does computation on the individual nodes, and then pool the node representations into a representation for the whole graph. Such a model, however, ignores the structure and only treats the data as a set of independent nodes.

3.2. GRAPH MATCHING NETWORKS:

Graph matching networks take a pair of graphs as input and compute a similarity score between them.

Compared to the embedding models, these matching models compute the similarity score jointly on the pair, rather than first independently mapping each graph to a vector. Therefore these models are potentially stronger than the embedding models, at the cost of some extra computation efficiency.

We propose the following graph matching network, which changes the node update module in each propagation layer to take into account not only the aggregated messages on the edges for each graph as before, but also a cross-graph matching vector which measures how well a node in one graph can be matched to one or more nodes in the other:

EQUATION

Here f s is a standard vector space similarity between h G1 and h G2 . f match is a function that communicates cross-graph information, which we propose to use an attention-based module:

a j→i = exp(s h (h (t) i , h (t) j )) j exp(s h (h (t) i , h (t) j )) , µ j→i = a j→i (h (t) i -h (t)

j ) and therefore (8)

EQUATION

)

s h is again a vector space similarity metric, like Euclidean or cosine similarity, a j→i are the attention weights, and j µ j→i intuitively measures the difference between h (t)

i and its closest neighbor in the other graph. Note that because of the normalization in a j→i , the function f match implicitly depends on the whole set of {h Note By construction, the attention module has a nice property that, when the two graphs can be perfectly matched, and when the attention weights are peaked at the exact match, we have Compared to the graph embedding model, the matching model has the ability to change the representation of the graphs based on the other graph it is compared against. The model will adjust graph representations to make them become more different if they do not match.

3.3. LEARNING:

The proposed graph similarity learning models can be trained on a set of example pairs or triplets. Pairwise training requires us to have a dataset of pairs labeled as positive (similar) or negative (dissimilar), while triplet training only needs relative similarity, i.e. whether G 1 is closer to G 2 or G 3 . We describe the losses on pairs and triplets we used below, which are then optimized with gradient descent based algorithms.

When using Euclidean similarity, we use the following margin-based pairwise loss:

EQUATION

where t ∈ {-1, 1} is the label for this pair, γ > 0 is a margin parameter, and

d(G 1 , G 2 ) = h G1 -h G2 2

is the Euclidean distance. This loss encourages d(G 1 , G 2 ) < 1 -γ when the pair is similar (t = 1), and d(G 1 , G 2 ) > 1 + γ when t = -1. Given triplets where G 1 and G 2 are closer than G 1 and G 3 , we optimize the following margin-based triplet loss:

EQUATION

This loss encourages d(G 1 , G 2 ) to be smaller than d(G 1 , G 3 ) by at least a margin γ.

For applications where it is necessary to search through a large database of graphs with low latency, it is beneficial to have the graph representation vectors be binary, i.e. h G ∈ {-1, 1} H , so that efficient nearest neighbor search algorithms (Gionis et al., 1999 ) may be applied. In such cases, we can minimize the Hamming distance of positive pairs and maximize it for negative pairs. With this restriction the graph vectors can no longer freely occupy the whole Euclidean space, but we gain the efficiency for fast retrieval and indexing. To achieve this we propose to pass the h G vectors through a tanh transformation, and optimize the following pair and triplet losses:

EQUATION

EQUATION

where

s(G 1 , G 2 ) = 1 H H i=1 tanh(h G1i ) • tanh(h G2i

) is the approximate average Hamming similarity. Both losses are bounded in [0, 1], and they push positive pairs to have Hamming similarity close to 1, and negative pairs to have similarity close to -1. We found these losses to be a bit more stable than margin based losses for Hamming similarity.

4. EXPERIMENTS:

In this section, we evaluate the graph similarity learning (GSL) framework and the graph embedding (GNNs) and graph matching networks (GMNs) on three tasks and compare these models with other competing methods. Overall the empirical results demonstrate that the GMNs excel on graph similarity learning, consistently outperforming all other approaches.

4.1. LEARNING GRAPH EDIT DISTANCES:

Problem Background Graph edit distance between graphs G 1 and G 2 is defined as the minimum number of edit operations needed to transform G 1 to G 2 . Typically the edit operations include add/remove/substitute nodes and edges. Graph edit distance is naturally a measure of similarity between graphs and has many applications in graph similarity search (Dijkman et al., 2009; Zeng et al., 2009; Gao et al., 2010) . However computing the graph edit distance is NP-hard in general (Zeng et al., 2009) , therefore approximations have to be used. Through this experiment we show that the GSL models can learn structural similarity between graphs on very challenging problems.

Training Setup We generated training data by sampling random binomial graphs G 1 with n nodes and edge probability p (Erdös & Rényi, 1959) , and then create positive example G 2 by randomly substituting k p edges from G 1 with new edges, and negative example G 3 by substituting k n edges from G 1 , where k p < k n1 . A model needs to predict a higher similarity score for positive pair (G 1 , G 2 ) than negative pair (G 1 , G 3 ). Throughout the experiments we fixed the dimensionality of node vectors to 32, and the dimensionality of graph vectors to 128 without further tuning. We also tried different number of propagation steps T from 1 to 5, and observed consistently better performance with increasing T . The results reported in this section are all with T = 5 unless stated otherwise. More details are included in Appendix B.1.

Baseline We compare our models with the popular Weisfeiler Lehman (WL) kernel (Shervashidze et al., 2011) , which has been shown to be very competitive on graph classification tasks and the Weisfeiler Lehman algorithm behind this kernel is a strong method for checking graph isomorphism (edit distance of 0), a closely related task (Weisfeiler & Lehman, 1968; Shervashidze et al., 2011) .

Evaluation The performance of different models are evaluated using two metrics: (1) pair AUCthe area under the ROC curve for classifying pairs of graphs as similar or not on a fixed set of 1000 pairs and (2) triplet accuracy -the accuracy of correctly assigning higher similarity to the positive pair in a triplet than the negative pair on a fixed set of 1000 triplets.

Results:

We trained and evaluated the GSL models on graphs of a few specific distributions with different n, p, with k p = 1 and k n = 2 fixed. The evaluation results are shown in Table 1 . We can see that by learning on graphs of specific distributions, the GSL models are able to do better than generic baselines, and the GMNs consistently outperform the embedding model (GNNs).

For the GMNs, we can visualize the cross-graph attention to gain further insight into how it is working. Figure 3 tested on graphs of 10 nodes. The cross-graph attention weights are shown in green, with the scale of the weights shown as the transparency of the green edges. We can see that the attention weights can align nodes well when the two graphs match, and tend to focus on nodes with higher degrees when they don't. However the pattern is not as interpretable as in standard attention models.

More experiments on generalization capabilities of these models (train on small graphs, test on larger graphs, train on graphs with some k p , k n combinations, test on others) are included in Appendix B.1.

4.2. CONTROL FLOW GRAPH BASED BINARY FUNCTION SIMILARITY SEARCH:

Problem Background Binary function similarity search is an important problem in computer security. The need to analyze and search through binaries emerges when we do not have access to the source code, for example when dealing with commercial or embedded software or suspicious executables. Combining a disassembler and a code analyzer, we can extract a control-flow graph (CFG) which contains all the information in a binary function in a structured format. See Figure 1 and Appendix B.2 for a few example CFGs. In a CFG, each node is a basic block of assembly instructions, and the edges between nodes represent the control flow, indicated by for example a jump or a return instruction used in branching, loops or function calls. In this section, we target the vulnerability search problem, where a piece of binary known to have some vulnerabilities is used as the query, and we search through a library to find similar binaries that may have the same vulnerabilities.2 Accurate identification of similar vulnerabilities enables security engineers to quickly narrow down the search space and apply patches.

In the past the binary function similarity search problem has been tackled with classical graph theoretical matching algorithms (Eschweiler et al., 2016; Pewny et al., 2015) , and Xu et al. (2017) and Feng et al. (2016) proposed to learn embeddings of CFGs and do similarity search in the embedding space. Xu et al. (2017) in particular proposed an embedding method based on graph neural networks, starting from some hand selected feature vectors for each node. Here we study further the performance of graph embedding and matching models, with pair and triplet training, different number of propagation steps, and learning node features from the assembly instructions. models were trained to learn a similarity metric on CFGs such that the CFGs for the same function have high similarity, and low similarity otherwise. Once trained, this similarity metric can be used to search through library of binaries and be invariant to compiler type and optimization levels.

We compare our graph embedding and matching models with Google's open source function similarity search tool (Dullien, 2018) , which has been used to successfully find vulnerabilities in binaries in the past. This tool computes representations of CFGs through a hand-engineered graph hashing process which encodes the neighborhood structure of each node by hashing the degree sequence from a traversal of a 3-hop neighborhood, and also encodes the assembly instructions for each basic block by hashing the trigrams of assembly instruction types. These features are then combined by using a SimHash-style (Charikar, 2002) algorithm with learned weights to form a 128-dimensional binary code. An LSH-based search index is then used to perform approximate nearest neighbor search using hamming distance.

Following (Dullien, 2018) , we also map the CFGs to 128-dimensional binary vectors, and use the Hamming similarity formulation described in Section 3 for training. We further studied two variants of the data, one that only uses the graph structure, and one that uses both the graph structure and the assembly instructions with learned node features. When assembly instructions are available, we embed each instruction type into a vector, and then sum up all the embedding vectors for instructions in a basic block as the initial representation vector (the x i 's) for each node, these embeddings are learned jointly with the rest of the model.

Figure 4 shows the performance of different models with different number of propagation steps and in different data settings. We again evaluate the performance of these models on pair AUC and triplet accuracy on fixed sets of pairs and triplets from the test set. It is clear from results that: (1) the performance of both the graph embedding and matching models consistently go up with more propagation steps, and in particular significantly outperforming the structure agnostic model special case which uses 0 propagation steps; (2) the graph embedding model is consistently better than the baselines with enough propagation steps; and (3) graph matching models outperforms the embedding models across all settings and propagation steps. Additionally, we have tried the WL kernel on this task using only the graph structure, and it achieved 0.619 AUC and 24.5% triplet accuracy. This is not surprising as the WL kernel is not designed for solving this task, while our models learn the features useful for the task of interest, and can achieve better performance than generic similarity metrics.

4.3. MORE BASELINES AND ABLATION STUDIES:

In this section, we carefully examine the effects of the design decisions we made in the GMN model and compare it against a few more alternatives. In particular, we evaluate the popular Graph Convolutional Network (GCN) model by Kipf & Welling (2016) as an alternative to our GNN model, and Siamese versions of the GNN/GCN embedding models. The GCN model replaces the message passing in Eq. 2 with graph convolutions, and the Siamese model predicts a distance value by concatenating two graph vectors and then pass through a 2 layer MLP. The comparison with Siamese networks can in particular show the importance of the cross-graph attention early on in the similarity computation process, as Siamese networks fuse the representations for 2 graphs only at the very end.

We focus on the function similarity search task, and also conduct experiments on an extra COIL-DEL mesh graph dataset (Riesen & Bunke, 2008) , which contains 100 classes of mesh graphs corresponding to 100 types of objects. We treat graphs in the same class as similar, and used identical setup as the function similarity search task for training and evaluation. (2) using Siamese network architecture to learn similarity on top of graph representations is better than using a prespecified similarity metric (Euclidean, Hamming etc.); (3) the GMNs outperform the Siamese models showing the importance of cross-graph information communication early in the computation process.

5. CONCLUSIONS AND DISCUSSION:

In this paper we studied the problem of graph similarity learning using graph neural networks. Compared to standard prediction problems for graphs, similarity learning poses a unique set of challenges and potential benefits. For example, the graph embedding models can be learned through a classification setting when we do have a set of classes in the dataset, but formulating it as a similarity learning problem can handle cases where we have a very large number of classes and only very few examples for each class. The representations learned from the similarity learning setting can also easily generalize to data from classes unseen during training (zero-shot generalization).

We proposed the new graph matching networks as a stronger alternative to the graph embedding models. The added power for the graph matching models comes from the fact that they are not independently mapping each graph to an embedding, but rather doing comparisons at all levels across the pair of graphs, in addition to the embedding computation. The model can then learn to properly allocate capacity toward the embedding part or the matching part. The price to pay for this expressivity is the added computation cost in two aspects: (1) since each cross-graph matching step requires the computation of the full attention matrices, which requires at least O(|V 1 ||V 2 |) time, this may be expensive for large graphs;

(2) the matching models operate on pairs, and cannot directly be used for indexing and searching through large graph databases. Therefore it is best to use the graph matching networks when we (1) only care about the similarity between individual pairs, or (2) use them in a retrieval setting together with a faster filtering model like the graph embedding model or standard graph similarity search methods, to narrow down the search to a smaller candidate set, and then use the more expensive matching model to rerank the candidates to improve precision.

Developing neural models for graph similarity learning is an important research direction with many applications. There are still many interesting challenges to resolve, for example to improve the efficiency of the matching models, study different matching architectures, adapt the GNN capacity to graphs of different sizes, and applying these models to new application domains. We hope our work can spur further research in this direction.

A EXTRA DETAILS ON MODEL ARCHITECTURES

In the propagation layers of the graph embedding and matching models, we used an MLP with one hidden layer as the f message module, with a ReLU nonlinearity on the hidden layer. For node state vectors (the h (t)

i vectors) of dimension D, the size of the hidden layer and the output is set to 2D. We found it to be beneficial to initialize the weights of this f message module to be small, which helps stablizing training. We used the standard Glorot initialization with an extra scaling factor of 0.1. When not using this small scaling factor, at the begining of training the message vectors when summed up can have huge scales, which is bad for learning.

One extra thing to note about the propagation layers is that we can make all the propagation layers share the same set of parameters, which can be useful if this is a suitable inductive bias to have.

We tried different f node modules in both experiments, and found GRUs to generally work better than one-hidden layer MLPs, and all the results reported uses GRUs as f node , with the sum over edge messages j m j→i treated as the input to the GRU for the embedding model, and the concatenation of j m j→i and j µ j →i as the input to the GRU for the matching model.

In the aggregator module, we used a single linear layer for the node transformation MLP and the gating MLP gate in Eq.3. The output of this linear layer has a dimensionality the same as the required dimensionality for the graph vectors. σ(x) = 1 1+e -x is the logistic sigmoid function, and is the element-wise product. After the weighted sum, another MLP with one hidden layers is used to further transform the graph vector. The hidden layer has the same size as the output, with a ReLU nonlinearity.

For the matching model, the attention weights are computed as

EQUATION

.

We have tried the Euclidean similarity s h (h i , h j ) = -h i -h j 2 for s h , as well as the dot-product similarity s h (h i , h j ) = h i h j , and they perform similarly without significant difference.

B EXTRA EXPERIMENT DETAILS:

We fixed the node state vector dimensionality to 32, and graph vector dimensionality to 128 throughout both the graph edit distance learning and binary function similarity search tasks. We tuned this initially on the function similarity search task, which clearly performs better than smaller models. Increasing the model size however leads to overfitting for that task. We directly used the same setting for the edit distance learning task without further tuning. Using larger models there should further improve model performance.

B.1 LEARNING GRAPH EDIT DISTANCES:

In this task the nodes and edges have no extra features associated with them, we therefore initialized the x i and x ij vectors as vectors of 1s, and the encoder MLP in Eq.1 is simply a linear layer for the nodes and an identity mapping for the edges.

We searched through the following hyperparameters: (1) triplet vs pair training; (2) number of propagation layers; (3) share parameters on different propagation layers or not. Learning rate is fixed at 0.001 for all runs and we used the Adam optimizer Kingma & Ba (2014) . Overall we found:

(1) triplet and pair training performs similarly, with pair training slightly better, (2) using more propagation layers consistently helps, and increasing the number of propagation layers T beyond 5 may help even more, (3) sharing parameters is useful for performance more often than not.

Intuitively, the baseline WL kernel starts by labeling each node by its degree, and then iteratively updates a node's representation as the histogram of neighbor node patterns, which is effectively also a graph propagation process. The kernel value is then computed as a dot product of graph representation vectors, which is the histogram of different node representations. When using the kernel with T iterations of computation, a pair of graphs of size Figure 5 : Example control flow graphs for the same binary function, compiled with different compilers (clang for the leftmost one, gcc for the others) and optimization levels. Note that each node in the graphs also contains a set of assembly instructions which we also take into account when computing similarity using learned features.

In addition to the results reported in the main paper, we have also tried the same models on another dataset obtained by compiling the compression software unrar with different compilers and optimization levels. Our graph similarity learning methods also perform very well on the unrar data, but this dataset is a lot smaller, with around 400 functions only, and overfitting is therefore a big problem for any learning based model, so the results on this dataset are not very reliable to draw any conclusions.

A few more control-flow graph examples are shown in Figure 5 . The distribution of graph sizes in the training set is shown in Figure 6 .

C EXTRA ATTENTION VISUALIZATIONS:

A few more attention visualizations are included in Figure 7 , Figure 8 and Figure 9 . Here the graph matching model we used has shared parameters for all the propagation and matching layers and was trained with 5 propagation layers. Therefore we can use a number T different from the number of propagation layers the model is being trained on to test the model's performance. In both visualizations, we unrolled the propagation for up to 9 steps and the model still computes sensible attention maps even with T > 5. Here the two graphs are isomorphic, with graph edit distance 0. Note that in the end a lot of the matchings concentrated on the correct match.

:

j µ j→i = 0, which means the cross-graph communications will be reduced to zero vectors, and the two graphs will continue to compute identical representations in the next round of propagation. On the other hand, the differences across graphs will be captured in the cross-graph matching vector j µ j→i , which will be amplified through the propagation process, making the matching model more sensitive to these differences.

Note that even though G2 is created with kp edge substitutions from G1, the actual edit-distance between G1 and G2 can be smaller than kp due to symmetry and isomorphism, same for G3 and kn. However the probability of such cases is typically low and decreases rapidly with increasing graph sizes.

Note that our formulation is general and can also be applied to source code directly if they are available.

Figures and Tables:

Figure 2: Illustration of the graph embedding (left) and matching models (right).

which we omitted in Eq. 8 for a cleaner notation. Since attention weights are required for every pair of nodes across two graphs, this operation has a computation cost of O(|V 1 ||V 2 |), while for the GNN embedding model the cost for each round of propagation is O(|V | + |E|). The extra power of the GMNs comes from utilizing the extra computation.

Figure 3: Visualization of cross-graph attention for GMNs after 5 propagation layers. In each pair of graphs the left figure shows the attention from left graph to the right, the right figure shows the opposite.

Figure 4: Performance (×100) of different models on the binary function similarity search task.

Figure 8: The change of cross-graph attention over propagation layers. Here the two graphs are isomorphic, with graph edit distance 0. Note that in the end a lot of the matchings concentrated on the correct match.

shows two examples of this for a matching model trained with n sampled from [20, 50],

Table content: <table><tr><td colspan="2">Graph Distribution WL kernel</td><td>GNN</td><td>GMN</td></tr><tr><td>n = 20, p = 0.2</td><td colspan="3">80.8 / 83.2 88.8 / 94.0 95.0 / 95.6</td></tr><tr><td>n = 20, p = 0.5</td><td colspan="3">74.5 / 78.0 92.1 / 93.4 96.6 / 98.0</td></tr><tr><td>n = 50, p = 0.2</td><td colspan="3">93.9 / 97.8 95.9 / 97.2 97.4 / 97.6</td></tr><tr><td>n = 50, p = 0.5</td><td colspan="3">82.3 / 89.0 88.5 / 91.0 93.8 / 92.6</td></tr><tr><td colspan="4">Table 1: Comparing the graph embedding (GNN) and matching (GMN) models trained on graphs</td></tr><tr><td colspan="4">from different distributions with the baseline, measuring pair AUC / triplet accuracy (×100).</td></tr><tr><td>graph edit distance = 1</td><td/><td/><td>graph edit distance = 2</td></tr></table>

Training Setup and Baseline We train and evaluate our model on data generated by compiling the popular open source video processing software ffmpeg using different compilers gcc and clang,

Table content: <table><tr><td/><td>100</td><td/><td/><td/><td/><td/><td/><td>100</td><td/><td/><td/><td/></tr><tr><td>Pair AUC</td><td>85 90 95</td><td>0</td><td>1</td><td>2 #propagation steps 3 4 5</td><td>6</td><td>7</td><td>Triplet Accuracy</td><td>80 85 90 95</td><td>0</td><td>1</td><td>2 #propagation steps 3 4 5 baseline: struct only baseline: struct + node features 6 embedding: struct only embedding: struct + node features matching: struct only matching: struct + node features</td><td>7</td></tr></table>

More results on the function similarity search task and the extra COIL-DEL dataset.Table 2 summarizes the experiment results, which clearly show that: (1) the GNN embedding model is a competitive model (more powerful than the GCN model);

Table content: <table><tr><td>Model Pair AUC Triplet Acc Baseline 96.09 96.35 GCN 96.67 96.57 Siamese-GCN 97.54 97.51 GNN 97.71 97.83 Siamese-GNN 97.76 97.58 GMN 99.28 99.18</td><td>Model Pair AUC Triplet Acc GCN 94.80 94.95 Siamese-GCN 95.90 96.10 GNN 98.58 98.70 Siamese-GNN 98.76 98.55 GMN 98.97 98.80</td></tr><tr><td>Function Similarity Search</td><td>COIL-DEL</td></tr></table>

|V | can have as large as a 2|V |T

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">0x1ceba</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">sub</td><td/><td colspan="2">RSP , 38</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">[RSP + c], EDI</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">[RSP + 8], ESI</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">[RSP + 4], EDX</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="2">RAX , [28]</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">[RSP + 28 ], RAX</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">xor</td><td/><td colspan="2">EAX , EAX</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="2">EDI , 560</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">call</td><td>fb8</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">0x1cee4</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">[RSP + 20 ], RAX</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">EAX , [RSP + c]</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">add</td><td/><td colspan="2">EAX , f</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">and</td><td/><td colspan="2">EAX , f0</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">[RSP + 18 ], EAX</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">EAX , [RSP + c]</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">add</td><td/><td colspan="2">EAX , f</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">lea</td><td/><td colspan="3">EDX , RAX + f</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">test</td><td colspan="2">EAX , EAX</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">cmovs</td><td colspan="2">EAX , EDX</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">sar</td><td/><td colspan="2">EAX , 4</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">add</td><td/><td colspan="2">EAX , 2</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td/><td colspan="3">[RSP + 1c ], EAX</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">cmp</td><td/><td colspan="3">[RSP + 20 ], 0</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">jnz</td><td/><td colspan="2">1cf22</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td>0x1cf22 mov lea</td><td colspan="4">RAX , [RSP + 20 ] RDX , 220cd9</td><td colspan="2">0x1cf18</td><td/><td/><td/><td/><td>0xf90 push</td><td>R15 , RSP</td></tr><tr><td/><td/><td/><td/><td/><td/><td>mov mov and test jz</td><td colspan="3">[RAX ], RDX EAX , [RSP + 4] EAX , 8 EAX , EAX 1cf69</td><td/><td colspan="2">mov jmp</td><td>EAX , 0 1d088</td><td/><td/><td/><td>push mov push push mov</td><td>R14 , RSP R14D , ESI R13 , RSP R12 , RSP R13D , EDI</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>push</td><td>RBP , RSP</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>push</td><td>RBX , RSP</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>mov</td><td>EDI , 560</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="3">0x1cf3c</td><td/><td/><td/><td/><td/><td>mov sub</td><td>EBP , EDX RSP , 18</td></tr><tr><td/><td/><td/><td/><td/><td>0x1cf69</td><td/><td/><td/><td colspan="2">mov and mov mov</td><td/><td colspan="2">EAX , [RSP + 4] EAX , 3 EDX , EAX RAX , [RSP + 20 ]</td><td/><td/><td/><td>mov mov xor call</td><td>RAX , [28] [RSP + 8], RAX EAX , EAX f70</td></tr><tr><td/><td/><td/><td/><td/><td>mov mov mov mov</td><td colspan="3">RAX , [RSP + 20 ] [RAX + 520 ], 1 RAX , [RSP + 20 ] [RAX + 524 ], 1</td><td colspan="2">mov mov sar and mov</td><td/><td colspan="2">[RAX + 520 ], EDX EAX , [RSP + 4] EAX , 4 EAX , 3 EDX , EAX</td><td/><td/><td/><td>0xfc0</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov mov jmp</td><td/><td colspan="2">RAX , [RSP + 20 ] [RAX + 524 ], EDX 1cf87</td><td/><td/><td/><td>mov lea mov</td><td>RBX , RAX EAX , R13 + f ECX , 10</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>mov</td><td>R15D , EAX</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>cdq</td><td>EDX , EAX</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>and</td><td>R15D , f0</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>0x1cf87</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>idiv test</td><td>EDX , EAX , ECX RBX , RBX</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>mov</td><td/><td colspan="3">EAX , [RSP + 4]</td><td/><td/><td/><td/><td/><td>jz</td><td>108a</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>and</td><td/><td colspan="2">EAX , 80000</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>test</td><td/><td colspan="2">EAX , EAX</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>jz</td><td/><td>1cfab</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>0xfdf</td></tr><tr><td/><td/><td/><td/><td/><td>0x1cfab</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>0x108a</td><td>lea lea</td><td>R12 D, RAX + 2 RAX , 2179f9</td></tr><tr><td/><td/><td>0x1950 push</td><td colspan="2">RBP , RSP</td><td>mov mov cmp jns</td><td colspan="3">RAX , [RSP + 20 ] 1cfdc [RSP + 4], 0 [RAX + 514 ], 0</td><td colspan="3">0x1cf94 call</td><td>f50</td><td/><td/><td colspan="2">0x1752b</td><td>xor</td><td>EAX , EAX</td><td>jz test mov</td><td>100e BPL , 8 [RBX ], RAX</td></tr><tr><td/><td/><td>push push push push push push mov mov mov mov call</td><td colspan="2">R15 , RSP R14 , RSP R13 , RSP R12 , RSP RBX , RSP RAX , RSP EBP , EDX R14D , ESI R15D , EDI EDI , 560 1028</td><td>0x1cfc1 mov mov or mov mov mov</td><td colspan="4">RAX , [RSP + 20 ] EAX , [RAX + 514 ] EAX , 1 EDX , EAX RAX , [RSP + 20 ] [RAX + 514 ], EDX</td><td colspan="2">0x1cf99 mov mov mov jmp</td><td colspan="2">EDX , EAX RAX , [RSP + 20 ] [RAX + 514 ], EDX 1d054</td><td/><td colspan="2">push push push push push xor mov call push sub mov mov mov mov mov</td><td>R15 , RSP R14 , RSP R13 , RSP R12 , RSP RBP , RSP EAX , EAX f38 EDI , 560 RBX , RSP RSP , 18 R12 D, EDI R13D , ESI EBP , EDX RAX , [28] [RSP + 8], RAX</td><td>0x100e mov mov</td><td>[RBX + 520 ], 1 [RBX + 524 ], 1</td><td>0xff3 jmp mov mov and mov mov sar and</td><td>1022 [RBX + 524 ], EAX EAX , EBP EAX , 3 [RBX + 520 ], EAX EAX , EBP EAX , 4 EAX , 3</td></tr><tr><td/><td/><td>0x196d</td><td/><td/><td>0x1cfdc</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>mov test jz</td><td colspan="2">RBX , RAX RBX , RBX 19ac</td><td>mov and test jz</td><td colspan="3">EAX , [RSP + 4] EAX , 20000000 EAX , EAX 1d004</td><td/><td/><td/><td/><td/><td/><td colspan="2">0x1755b and mov lea mov</td><td>R14D , f0 RBX , RAX EAX , R12 + f R14D , EAX</td><td>0x1022 bt jnb</td><td>EBP , 13 1035</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td>ECX , 10</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">cdq</td><td>EDX , EAX</td></tr><tr><td>0x19ac xor jmp</td><td/><td>EBX , EBX 1a44</td><td>0x1975 lea mov sar shr lea sar lea mov test jnz</td><td colspan="2">R12 D, R15 + f EAX , R12 D EAX , 1f EAX , 1c R13D , R15 + RAX * 1 + f R13D , 4 RAX , 21bcc9 [RBX ], RAX BPL , 8 19b3</td><td/><td>0x1cfe9 mov mov or mov mov mov</td><td/><td colspan="3">RAX , [RSP + 20 ] EAX , [RAX + 514 ] EAX , 2 EDX , EAX RAX , [RSP + 20 ] [RAX + 514 ], EDX</td><td/><td/><td>jz xor mov 0x175db</td><td colspan="3">idiv lea mov test jz RSI , [28] 1763a RSI , [RSP + 8]</td><td>EDX , EAX , ECX R15D , RAX + 2 EAX , 0 RBX , RBX 175db lea mov test jz 0x17580</td><td>175f0 BPL , 8 [RBX ], RAX RAX , 21aa19</td><td>0x1035 mov shr bt mov jnb</td><td>EAX , EBP EAX , 1f EBP , 1d [RBX + 514 ], EAX 104d</td><td>0x1028 call</td><td>f10</td></tr><tr><td/><td/><td/><td/><td/><td/><td>0x1d004</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>0x1046</td><td>0x102d</td></tr><tr><td>0x19b3 mov and mov mov shr and</td><td/><td colspan="2">EAX , EBP EAX , 3 [RBX + 520 ], EAX EAX , EBP EAX , 4 EAX , 3</td><td>0x199b mov mov jmp</td><td>[RBX + 520 ], 1 EAX , 1 19c6</td><td>mov and test jz</td><td colspan="5">EAX , [RSP + 4] EAX , 40000000 EAX , EAX 1d02c 0x1d011 mov RAX , [RSP + 20 ]</td><td/><td>0x1763a add pop pop pop pop pop pop ret near</td><td>RSP , 18 RBX , RSP RBP , RSP R12 , RSP R13 , RSP R14 , RSP R15 , RSP [RSP ]</td><td colspan="2">0x175eb call</td><td>ee8</td><td>0x17590 mov and mov mov sar and mov</td><td>EAX , EBP EAX , 3 [RBX + 520 ], EAX EAX , EBP EAX , 4 EAX , 3 [RBX + 524 ], EAX</td><td>or</td><td>0x104d bt jnb</td><td>[RBX + 514 ], 2 EBP , 1e 105a</td><td>mov jmp</td><td>[RBX + 514 ], EAX 1067</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>mov</td><td/><td colspan="3">EAX , [RAX + 514 ]</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>or</td><td/><td>EAX , 4</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>0x19c6 and add mov</td><td colspan="2">R12 D, f0 R13D , 2 [RBX + 524 ], EAX</td><td/><td/><td>mov mov mov</td><td/><td colspan="3">EDX , EAX RAX , [RSP + 20 ] [RAX + 514 ], EDX</td><td/><td/><td/><td>0x175f0 mov mov jmp</td><td colspan="2">[RBX + 520 ], 1 [RBX + 524 ], 1 175a9</td><td>0x1053 or</td><td>[RBX + 514 ], 4</td></tr><tr><td/><td/><td>test</td><td colspan="2">EBP , 80000</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>jnz</td><td>1a1b</td><td/><td/><td>0x1d02c</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td>mov</td><td colspan="3">EAX , [RSP + 4]</td><td/><td/><td/><td/><td/><td colspan="2">0x175a9</td><td>0x105a</td></tr><tr><td/><td/><td/><td>0x19dc</td><td/><td/><td>and test jz</td><td colspan="3">EAX , 10000000 EAX , EAX 1d054</td><td/><td/><td/><td/><td/><td colspan="2">bt jnb</td><td>EBP , 13 17606</td><td>bt jnb</td><td>EBP , 1c 1067</td></tr><tr><td/><td/><td/><td>mov</td><td>ECX , EBP</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="2">0x1a1b call</td><td>fc0</td><td>shr mov shr and lea test lea cmovne mov test</td><td colspan="2">ECX , 1f EAX , EBP EAX , 1c EAX , 2 EDX , RAX + RCX * 1 EBP , 40000000 ECX , RAX + RCX * 1 + 4 EDX , ECX [RBX + 514 ], EDX EBP , 10000000</td><td/><td>0x1d039 mov mov or mov mov mov</td><td/><td colspan="3">RAX , [RSP + 20 ] EAX , [RAX + 514 ] EAX , 1 EDX , EAX RAX , [RSP + 20 ] [RAX + 514 ], EDX</td><td/><td/><td>0x17606 mov shr mov bt jnb</td><td colspan="2">EAX , EBP EAX , 1f [RBX + 514 ], EAX EBP , 1d 1761e</td><td>0x175af call</td><td>ee0</td><td>0x1060 or 0x1067</td><td>[RBX + 514 ], 1</td></tr><tr><td/><td/><td/><td>jz</td><td>1a26</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>0x17617</td><td/><td/><td>0x175b4</td><td>mov</td><td>R8D, R12 D</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>or</td><td colspan="2">[RBX + 514 ], 2</td><td>mov</td><td>[RBX + 514 ], EAX</td><td>mov mov</td><td>ECX , R15D EDX , R14D</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>0x1d054</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>mov mov</td><td>ESI , R13D RDI , RBX</td></tr><tr><td>0x1a20 mov</td><td colspan="3">[RBX + 514 ], EAX</td><td>0x1a07 test cmove or mov jmp</td><td>EBP , 40000000 ECX , EAX ECX , 1 [RBX + 514 ], ECX 1a26</td><td/><td>mov mov mov mov mov mov mov</td><td/><td colspan="3">EDI , [RSP + 1c ] ECX , [RSP + 18 ] EDX , [RSP + 8] ESI , [RSP + c] RAX , [RSP + 20 ] R8D, EDI RDI , RAX</td><td/><td/><td>0x1761e bt jnb</td><td>EBP , 1e 1762b</td><td/><td>call 0x107b</td><td>4ab0</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>call</td><td/><td>1cc23</td><td/><td/><td/><td/><td/><td colspan="2">0x17624 or</td><td>[RBX + 514 ], 4</td><td>mov mov jmp</td><td>[RBX + 510 ], ffffffff RAX , RBX 108c</td></tr><tr><td/><td/><td colspan="2">0x1a26</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td colspan="2">mov mov mov mov mov call</td><td>RDI , RBX ESI , R15D EDX , R14D ECX , R12 D R8D, R13D 1a56</td><td/><td colspan="2">0x1d074 mov mov mov</td><td colspan="5">RAX , [RSP + 20 ] [RAX + 510 ], ffffffff RAX , [RSP + 20 ]</td><td/><td/><td>0x1762b bt jnb</td><td colspan="2">EBP , 1c 175ba</td><td>0x108c mov xor jz</td><td>RSI , [RSP + 8] RSI , [28] 10a1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">0x1d088</td><td/><td/><td/><td/><td/><td colspan="2">0x17631</td></tr><tr><td/><td/><td>0x1a3a</td><td/><td/><td/><td/><td>mov</td><td/><td colspan="4">RCX , [RSP + 28 ]</td><td/><td/><td>or jmp</td><td/><td>[RBX + 514 ], 1 175ba</td><td>0x109c</td></tr><tr><td/><td/><td>mov</td><td colspan="3">[RBX + 510 ], ffffffff</td><td/><td>xor jz</td><td/><td colspan="3">RCX , [28] 1d09d</td><td/><td/><td/><td/><td/><td>call</td><td>f20</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">0x175ba</td></tr><tr><td/><td/><td>0x1a44 mov add pop pop pop pop pop pop ret near</td><td>RAX , RBX RSP , 8 RBX , RSP R12 , RSP R13 , RSP R14 , RSP R15 , RSP RBP , RSP [RSP ]</td><td/><td/><td/><td colspan="2">0x1d09d add ret near</td><td colspan="2">0x1d098 call RSP , 38 [RSP ]</td><td>f60</td><td/><td/><td/><td colspan="3">mov mov mov mov mov call 0x175ce mov</td><td>R8D, R15D ECX , R14D EDX , R13D ESI , R12 D RDI , RBX 61e4 [RBX + 510 ], ffffffff</td><td>0x10a1 add pop pop pop pop pop pop ret near</td><td>RSP , 18 RBX , RSP RBP , RSP R12 , RSP R13 , RSP R14 , RSP R15 , RSP [RSP ]</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">mov</td><td>RAX , RBX</td></tr></table>

Peer review (iclr2019):
 The authors present two methods for learning a similarity score between pairs of graphs. They first is to use a shared GNN for each graph to produce independent graph embeddings on which a similarity score is computed. The authors improve this model using pairs of graphs as input and utilizing a cross-graph attention-mechanism in combination with graph convolution. The proposed approach is evaluated on synthetic and real world tasks. It is clearly shown that the proposed approach of cross-graph attention is useful for the given task (at the cost of extra computation). A main contribution of the article is that ideas from graph matching are introduced to graph neural networks and it is clearly shown that this is beneficial. However, in my opinion the intuition, effect and limitations of the cross-graph attention mechanism should be described in more detail. I like the visualizations of the cross-graph attention, which gives the impression that the process converges to a bijection between the nodes. However, this is not the case for graphs with symmetries (automorphisms); consider, e.g., two star graphs. A discussion of such examples would be helpful and would make the concept of cross-graph attention clearer. The experimental comparison is largely convincing. However, the proposed approach is motivated by graph matching and a connection to the graph edit distance is implied. However, in the experimental comparison graph kernels are used as baseline. I would like to suggest to also use a simple heuristics for the graph edit distance as a baseline (Riesen, Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 27(7), 2009). There are several other questions that have not been sufficiently addressed in the article. * In Eq. 3, self-attention is used to compute graph level representations to "only focus on important nodes in the graph". How can this be reconciled with the idea of measuring similarities across the whole graph? Can you give more insights in how the attention coefficients vary for positive as well as negative examples? How much does the self-attention affects the performance of the model in contrast to mean or sum aggregation? * Why do you chose the cross-graph similarity to be non-trainable? Might there be any benefits in doing so? * The note on page 5 is misleading because two isomorphic graphs will lead to identical representations even if communication is not reduced to zero vectors (this happens neither theoretically nor in practice). * Although theoretical complexity of the proposed approach is mentioned, how much slower is the proposed approach in practice? As similarity is computed for every pair of nodes across two graphs, the proposed approach, as you said, will not scale. In practice, how would one solve this problem given two very large graphs which do not fit into GPU memory? To what extent can sampling strategies be used (e.g., from GraphSAGE)? Some discussion on this would be very fruitful. In summary, I think that this is an interesting article, which can be accepted for ICLR provided that the cross-graph attention mechanism is discussed in more detail. Minor remarks: * p3: The references provided for the graph edit distance in fact consider the (more specific) maximum common subgraph problem.